Genetic Algorithms and Evolutionary Computing
Genetic Algorithms and Evolutionary Computing
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 VM
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 14h
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?