第八次课-遗传算法.pptVIP

Genetic Algorithms By L. Qu Xian Jiaotong University January, 2001 Genetic Algorithms Charles Robert Darwin (1809-1882) ‘The Origin of Species’: ‘Survival of the fittest’. John H. Holand (1975) ‘Adaptation of natural and artificial systems’ self repair; self guidance; reproduction. David E. Goldberg (1989) ‘Genetic Algorithm in Search, Optimization, and Machine Learning’. John Koza (1989): Genetic Programming International Conference on GA: since 1985. International Conference on ‘Solving Parallel Problems From Nature’, since 1990. Principle Advantages ? GAs search from a population of points, not a single point: robustness. ? GAs use object function, do not require gradient, Hessian matrix, etc. other information. ? No special requirements, e.g. Continuity and single mode, etc. are required. ? GAs use probabilistic transition rules, not deterministic rules. ? GAs work with coding of a parameter set and posess higher optimization capability. Michalewicz Function f(x,y)=21.5+xsin(4pix)+ysin(20piy) Michalewicz Function zmax = 39.050 ( x = 11.626; y = 5.925) Michalewicz Function Michalewicz Function Michalewicz Function Michalewicz Functioin Coding and Decoding Coding Evolutionary Operation Fitness Evaluation Decoding Binary Coding ? Determine the defining domain xmax,xmin of parameter x; ? determine the discrete interval or precision xdelta of x; ? transfer the defining domain from(xmax,xmin) to(2^m,1). Binary Decoding Genetic Operation: Reproduction The reproduction allocates offspring strings using a roulette wheel with slots sized according to fitness. Genetic Operation: Crossover Genetic Operation: Mutation Genetic Operation: Inversion Schema and Schemata A schemata composing of 24 =16 cromosomes: x 0 x 1 x x 0 0 1 1 1