# Genetic Algorithms and Evolutionary Computing

Ga naar: navigatie, zoeken

# Genetic Algorithms and Evolutionary Computing

## 2010-01-22 10u30

• Explain the terms epistasis and deception. What is the difference?

Given some o(1) schemata

```**1*...**** (1*)
****...*1** (*1)
**0*...**** (0*)
****...*0** (*0)
```

and some o(2) schemata

```**1*...*0** (10)
**1*...*1** (11)
**0*...*0** (00)
**0*...*1** (01)
```

Define minimal conditions for which deception occurs in this case.

• Discussion of rank-based selection. Which parameters can be used to adapt the behavior of these methods? When would you want to use a rank-based selection method?
• Discussion of the paper Evolving 3D morphology and behavior by competition by K. Sims. The fitness function is different from the fitness functions we are used to. Explain how and why.
• Explain in maximum five minutes the most important outcomes of your project.

## 2009-01-26 PM

• Handling constraints: Explain the difference between algorithms based on repair methods and algorithms based on decoders. Why these strategies can lead to a better performance compared with algorithms based on penalty functions? How would you take into account the constraints arising in a timetabling problem?
• Suppose you want to solve an optimization problem, for which the objective function (function to be maximized) is known. Why it is usually not appropriate to use the objective function as the fitness function? Give several reasons if possible. How can you construct a good fitness function? Give an example of such a construction of a fitness function in one of the texts that we have discussed.
• Paper: Evolving 3D morphologies. De fitness van chromosomen bepalen gebeurt op een vreemde manier (tov eerder besproken problemen) leg uit hoe en waarom.

## 2009-01-14 16u30

• Leg het verschil uit bij constrained problemen tussen repair en het gebruik van een decoder. Waarom kunnen deze methodes beter werken dan het toekennen van penalties? Hoe zie je dit bij de constraints bij time tabling?
• Waarom is het bij optimisatie problemen beter om niet de objectief functie (de functie die gemaximaliseerd moet worden) rechtstreeks te gebruiken als fitness? Op welke manieren kunnen we de objectief functie verbeteren? In welke tekst die we gezien hebben wordt dit toegepast?
```  Merk op dat er in het boek van de cursus een fout staat bij sigma truncation op p66, er staat "f'_i = f_i + (f_avg - c * std_dev)".
Dit moet zijn: "f'_i = f_i - (f_avg - c * std_dev)"
De gevraagde toepassing staat in de paper over load balancing onderaan de 2de pagina, daar gebeurt linear scaling.
```
• In de paper "Using genetic algorithms for supervised concept learning" worden GABIL en ID5R vergeleken voor 12 concepten. Leg de resultaten in fig 1-7 in detail uit.
• Bespreking project

## 2008-01-21 14u

• Waarom is "Schemata Theorem" belangrijk? Wat zijn de beperkingen? Als er een schema is met fitness 20% boven de gemiddelde fitness, kan je berekenen hoe lang het duurt totdat de hele populatie dit schema bevat?
• Roulette wheel selection: wat zijn de problemen die kunnen optreden? Hoe kunnen deze opgelost worden, of welke alternatieven bestaan er?
• Paper load balancing: welke manieren worden gebruikt om het geheel beter te laten presteren? Zijn deze manieren ook voor andere toepassingen te gebruiken?
• Bespreking project

## 2007-08-20 8u30

1) Handling constraints: Explain the difference between algorithms based on repair methods and algorithms based on decoders. Why these strategies can lead to a better performance compared with algorithms based on penalty functions? How would you take into account the constraints arising in a timetabling problem?

2) Discuss some drawbacks of the roulette wheel selection mechanism, and describe some methods to avoid (or to minimise) these drawbacks.

3) In het paper over GABIL vs. ID5R. leg Fig. 1-7 uit in detail

4) Bespreking project TSP

## 2006-02-03 14u

• Waarom is "Schemata Theorem" belangrijk? Wat zijn de beperkingen? Als er een schema is met fitness 20% boven de gemiddelde fitness, kan je berekenen hoe lang het duurt totdat de hele populatie dit schema bevat?
• Roulette wheel selection: wat zijn de problemen die kunnen optreden? Hoe kunnen deze opgelost worden, of welke alternatieven bestaan er?
• Paper 3D morphologies: de fitness value wordt op een vreemde manier bepaald. Hoe en waarom gebeurt dit?
• Bespreking project

## 2006-01-30 11u

1. Genetic Aglorithm with varying population size:

a. Discuss the various strategies to assign the "lifetime" to a chromosome.
b. Does this strategy influence very much the performance?
c. Explain fig. 4.5 - 4.8 in detail.

2. Hoofdstuk 9: het lineaire transport-probleem.

a. Leg de genetische operatoren uit.
b. Uit figuur 9.1 blijkt dat er een of meerdere genetische operatoren niet goed presteert. Ga je hiermee akkoord? Leg Uit.

3. Paper: Evolving 3D morphologies. De fitness van chromosomen bepalen gebeurt op een vreemde manier (tov eerder besproken problemen) leg uit hoe en waarom.

4. Bespreking project TSP (Stel in 5 minuten je algemene bevindingen en conclusies voor)

## 2006-01-30 10u

Je krijgt 1u15min de tijd om schriftelijk voor te bereiden.

1. Constraint handling: Repair en decoder algoritme uitleggen. Waarom presteren deze soms beter dan 'penalty algorithm'? In paper over timetabling: wordt contraint handling consistent met regels in Michalewicz gebruikt? (ja, is logaritmische versie van penalty function: 1/1+pen is ongeveer de logaritme vd penalty)

2. Evolution Strategies: werking toelichten, specifiek vergeleken met Genetic Algorithms (gelijkenis en verschillen geven, staan opgesomd in hfdst 8 in tekstvorm)

3. In het paper over GABIL vs. ID5R. leg Fig. 1-7 uit in detail (= procent vd 10 laatste classificaties die juist zijn; complexere problemen=>GABIL beter, robuuster; zeker voor geval 4D1C; bijvraag: wat is ...D...C => aantal disjuncties en conjuncties in classificatie => veel disjuncties = losse classificatie, veel conjucties = srenge classificatie)

4. Bespreking project TSP

## 2005-01-31 AM

1. een searchspace[a,b] van real values

hoe representeren?
voor- en nadelen van twee representaties

2.handling constraints : verschil tussen repair en decoder

waarom is dat beter qua performantie als penalties
hoe constraints behandelen bij timetabling

3.verschil tussen GABIL en ID5R (die grafieken uitleggen)

4. bespreking TSP

1. Bespreek het nut en de beperkingen van het schema theorem. Van welke (onrealistische) assumpties gaat men uit in de afleiding?

2. Wat zijn de beperkingen van roulette-wiel selectie? Welke aanpakken bestaan er om deze beperkingen op te lossen/rekening mee te houden?

3. Wat is evolutionary programming? Is dit nog altijd een genetisch algoritme? Geef 1 of 2 voorbeelden waar deze aanpak gebruikt wordt.

4. Bespreking verslag TSP

## 2005-01-17 10u

1) Handling constraints: Explain the difference between algorithms based on repair methods and algorithms based on decoders. Why these strategies can lead to a better performance compared with algorithms based on penalty functions? How would you take into account the constraints arising in a timetabling problem?

2) Suppose you want to solve an optimization problem, for which the objective function (function to be maximized) is known. Why it is usually not appropriate to use the objective function as the fitness function? Give several reasons if possible. How can you construct a good fitness function? Give an example of such a construction of a fitness function in one of the texts that we have discussed.

3) In the paper of Load Balancing with Genetic algorithms, by R. Van Driessche and R.Piessens, the performance of the genetic algorithm is improved by the incorporation of 'problem specific heuristics'. Discuss the improvement (what is improved? how much?). Did we discuss other problems where the addition of a problem specific heuristic improves the genetic algorithm?

4) TSP project

## 2004-06-11 AM

1. Explain the terms "epistasis" and "deception". What is the difference? Given some o(1) schemata

```**1*...**** (1*)
****...*1** (*1)
**0*...**** (0*)
****...*0** (*0)
```

and some o(2) schemata

```**1*...*0** (10)
**1*...*1** (11)
**0*...*0** (00)
**0*...*1** (01)
```

Define minimal conditions for which deception occurs in this case.

2. In chapter 9 of [Michaelewicz] a matrix representation is used. Explain the mutation and crossover operators of this representation. Look at Figure 9.1. It shows a failure of some basic mechanisms of the GA. Do you agree with this? Why (not)?

3. In the paper about GABIL it is compared with ID5R. Explain Fig. 1-7 in detail.

4. Discussion about the TSP project

## 2002-06-27

1. bespreek paper (5 minuten)

2. varying population size GAs

• doel?
• waarom is de life parameter belangrijk? (vervangt selectie)
• bespreek eerste grafiek in boek

3. transportation problem

• bespreek eerste grafiek van lineair, welk onderdeel van onze GA werkt niet/doet niets?
• bespreek welke aanpassingen er gemaakt worden voor niet lineaire problemen
+ waarom?

4. load balancing, bespreek de 2 parallellisatie approaches uit de paper

Prof is zeer vriendelijk, zeer aangenaam examen.

## 2002-06-22

• paper (in 5 minuten, en ie kijkt dus echt naar zijn horloge he...)
• inversie operator uitleggen + zeggen bij welke toepassingen ie gebruikt wordt in boek
• bespreek voor- en nadelen van matrixrepresentatie bij TSP
• leg uit hoe je uit de autocorrelatie van de fitnessfunctie kan afleiden hoe goed een mutatie-operator is. Leg hierbij ook uit waarom Gray-encoding nuttig kan zijn.

## 2002-06-20

1. Bespreek de paper dadde gezocht hebt in 5 minuten.

2. Schemata Theorem: Het belang duiden en problemen ermee. + Wat is de fout in het bewijs?

3. Er staat een fout(en) in de eerste paragraaf op pag 243. Hfdst 10 en blz 239-242 verondersteld juist. Duid de fout(en).

4. Paper over Creature behavior. Wat is er speciaal aan de fitness functie en waarom?

## 2002-06-14 14u

1) Present in 5' general conclusions after reading and summarizing the paper on GA's & Machine Learning

2) Difference between repair algorithms and decoders. Do one of these performs better than using penalty functions?

3) Linear Transportation Problem: matrix representation. Crossover operator: explain how DIV and REM are created and why this crossover operator perfoms well. (p.190/191)

4) Paper GA & the Structure of the Fitness Landscape: explain the table with correlation coefficients for the 4 crossover operators. Explain relation between correlation coefficient and performance of the algorithm.

1) Present in 5' general conclusions after reading and summarizing the paper on GA's & Machine Learning

2) Discuss GAs with varying popsize: why? does the choice of lifetime influence performance? explain fig4.4 (p77)

3) Discuss & compare PMX with ER

4) Load balancing paper: discuss the various models for parallelisation of the GA, explain figs 5&6

1. present in 5 min. the main conclusion from the paper concerning GA en ML

2. Suppose you want to solve an optimization problem, for which the objective function (function to be maximized) is known. Why is it usually not appropriate to use the objective function as the fitness function. Did such a problem appear in the textbook or in the texts discussed?

3. Describe the main characteristics of an 'evolution strategy' as discussed in chapter 8 (focus on differences with GAs)

4. Load balancing paper, performance of GA is improved by incorporation of 'problem specific heuristics' Discuss this improveent (what is improved, how much?) Did we discuss other problems where the addition of a problem specific heuristic improves the GA?