(復(fù)雜系統(tǒng)的性能評價與優(yōu)化課件資料）genetic_algorithm

1、( (復(fù)雜系統(tǒng)的性復(fù)雜系統(tǒng)的性能評價與優(yōu)化課能評價與優(yōu)化課件資料）件資料）genetic_algoritgenetic_algorithmhm6ExamplenTraveling Salesman ProblemnA design/chromosome, the traveling order of the cities:a b c d f eabdcfeN7The AlgorithmStep 0: Randomly generate an initial population.Step 1: Select parents and “reproduce” the next generation

2、Step 2: Evaluate the fitness of the new generationStep 3: Replace the old generation with the new generationStep 4: Repeat step 1 though 3 till iteration TN8SelectionnDesigns with a better fitness value have a better chance to be chosen as a parentnTo insure that the good “information” from the good

3、 parents is being passed onto the next generationN9ReproductionnCross-overnPick the parentsa b c d e f and b c d a f enPick the cross-over pointa b c d | e f and b c d a | f enReproducea b c d e f b c d a e fb c d a f e a b c d f enCorrection if necessaryN10Reproduction (cont.)nMutationnPick the par

4、enta b c d e fnPick the mutation point and valuea b c d e f: e cnReproducea b c d e f a b c d c fnCorrection if necessarya b c d c f a b e d c fN11IssuesnPros:nRobustnCons:nWhat is the best way to encode the designs?nRequirement:nEvaluation function must be relatively fast12ReferencesnWhitley, D., “A Genetic Algorithm Tutorial,” Statistics and Computing, Volume 4, pp. 65-85, 1994.nHolland, J., Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.nHeitktter, J. a