演化计算（PPT讲稿）Evolutionary Computation（EC）

Evolutionary Computation (ec) eie426-eC-200809. ppt 2021/1/30 EIE426-AICV

2021/1/30 EIE426-AICV 1 Evolutionary Computation (EC) eie426-ec-200809.ppt

Contents Basic concepts of ec Genetic Algorithms An Example Chromosome Representation Stopping Criteria Initial Population Selection Mechanisms Crossover and mutation Fⅰ itness Functions Another Example Application Routing Optimization Advantages and disadvantages of ec 2021/1/30 EIE426-AICV

2021/1/30 EIE426-AICV 2 Contents ◼ Basic Concepts of EC ◼ Genetic Algorithms ◼ An Example ◼ Chromosome Representation ◼ Stopping Criteria ◼ Initial Population ◼ Selection Mechanisms ◼ Crossover and Mutation ◼ Fitness Functions ◼ Another Example ◼ Application: Routing Optimization ◼ Advantages and Disadvantages of EC

Evolution and search Evolution-search through the enormous genetic parameter space for the best genetic make-up Borrow ideas from nature to help us solve problems that have equally large search spaces or similarly changing environment 2021/1/30 EIE426-AICV

2021/1/30 EIE426-AICV 3 Evolution and Search ◼ Evolution - search through the enormous genetic parameter space for the best genetic make-up. ◼ Borrow ideas from nature to help us solve problems that have equally large search spaces or similarly changing environment

Natural Evolution and Evolutionary Computation Natural Evolutionary Evolution Computing Individual Candidate Solution Fitness Quality Environment Problem 2021/1/30 EIE426-AICV

2021/1/30 EIE426-AICV 4 Natural Evolution and Evolutionary Computation Natural Evolution Individual Fitness Environment Evolutionary Computing Candidate Solution Quality Problem

Different ecs Several classes of EC algorithms have been developed Genetic algorithms(GAs): model genetic evolution Genetic programming: based on GAs, but individuals are programs (represented as trees Evolutionary programming: from the simulation of adaptive behavior in evolution(phenotype evolution Evolution strategies: model the strategic parameters that control variation in evolution i e. the evolution of evolution Culture evolution: models the evolution of culture of a population and how the culture influences the evolution of individuals Co-evolution: individuals evolve through cooperation, or in competition with one other 2021/1/30 EIE426-AICV

2021/1/30 EIE426-AICV 5 Different ECs Several classes of EC algorithms have been developed: - Genetic algorithms (GA’s): model genetic evolution - Genetic programming: based on GA’s, but individuals are programs (represented as trees) - Evolutionary programming: from the simulation of adaptive behavior in evolution (phenotype evolution) - Evolution strategies: model the strategic parameters that control variation in evolution, i.e., the evolution of evolution - Culture evolution: models the evolution of culture of a population and how the culture influences the evolution of individuals. - Co-evolution: individuals evolve through cooperation, or in competition with one other

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