Basic Concepts Chromosome: individual Population: many individuals Gene: each characteristics of chromosome(one parameter) Allele: the value of a gene Crossover generate offspring by combining parts of the parents Mutation: introduce new genetic material into an existing individual Fitness: the survival strength of an individual Culling (removing)and elitism(copy ing) 2021/1/30 EIE426-AICV
2021/1/30 EIE426-AICV 6 Basic Concepts • Chromosome: individual • Population: many individuals • Gene: each characteristics of chromosome (one parameter) • Allele: the value of a gene • Crossover: generate offspring by combining parts of the parents. • Mutation: introduce new genetic material into an existing individual. • Fitness: the survival strength of an individual • Culling (removing) and elitism (copying)
Evolutionary Computation Selection Parents Recombination Crossover Population Mutation The Replacement evolutionary Offspring cvcle 2021/1/30 EIE426-AICV
2021/1/30 EIE426-AICV 7 Evolutionary Computation Recombination (Crossover) Mutation Population Offspring Parents Selection The Replacement evolutionary cycle
Genetic Algorithms The Ga was the first Ec paradigm developed and applied (Holland 1975 The features of the original Gas (1) A bit string representation 2) Proportional selection (3) Cross-over as the primary method to produce new individuals Several changes have been made: (1) Different representation schemes (2) Different selection methods (3) Different GA operators(cross-over, mutation and elitism) 2021/1/30 EIE426-AICV
2021/1/30 EIE426-AICV 8 Genetic Algorithms ◼ The GA was the first EC paradigm developed and applied (Holland 1975). ◼ The features of the original GA’s: (1) A bit string representation (2) Proportional selection (3) Cross-over as the primary method to produce new individuals. ◼ Several changes have been made: (1) Different representation schemes (2) Different selection methods (3) Different GA operators (cross-over, mutation and elitism)
Random search The Ga is a search procedure Random search is possibly the simplest search procedure. Its training time may be very long before an acceptable solution is obtained Procedure (1) Start from an initial search point or a set of initial points (2) Random perturbations to the points (3)Repeat until an acceptable solution is reached or a maximum number of iterations is exceeded 2021/1/30 EIE426-AICV
2021/1/30 EIE426-AICV 9 Random Search ◼ The GA is a search procedure. ◼ Random search is possibly the simplest search procedure. Its training time may be very long before an acceptable solution is obtained. ◼ Procedure: (1) Start from an initial search point or a set of initial points. (2) Random perturbations to the points (3) Repeat until an acceptable solution is reached or a maximum number of iterations is exceeded
General Genetic Algorithm Let g=0 (2) Initialize the initial generation Cg While no stopping criterion is satisfied (a)Evaluate the fitness of each individual in Cg (b)g<g+1. c)Select parents from Ca-1 (d) Recombine selected parents through cross-over to form offspring oa with a probability p) (e)Mutate offspring in Oa with a probability pm) (f select the new generation Ca from (the previous generation Ca-1, e.g the best individuals are copied and the offspring g g: generation Note: The things in 0 might or might not be carried out 2021/1/30 EIE426-AICV
2021/1/30 EIE426-AICV 10 General Genetic Algorithm (1) Let g = 0. (2) Initialize the initial generation Cg . (3) While no stopping criterion is satisfied (a) Evaluate the fitness of each individual in Cg . (b) g g+1. (c) Select parents from Cg-1 . (d) Recombine selected parents through cross-over to form offspring Og (with a probability pc ). (e) Mutate offspring in Og (with a probability pm). (f) Select the new generation Cg from (the previous generation Cg-1 , e.g., the best individuals are copied) and the offspring Og . g: generation Note: The things in () might or might not be carried out