Evolutionary Algorithms PDF

Evolutionary Algorithms Mills, Correia EA material – Overview Artificial Life / Vida Artificial Evolutionary algorithms in Evolutionary Algorithms I general GAs GAs step-by-step Rob Mills Luı́s Correia Recommend- ations Informatics &...

Evolutionary Algorithms Mills, Correia EA material – Overview Artificial Life / Vida Artificial Evolutionary algorithms in Evolutionary Algorithms I general GAs GAs step-by-step Rob Mills Luı́s Correia Recommend- ations Informatics & BioISI FCUL October 2015  Evolutionary Algorithms Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms in What are they? Extracting an algorithm from natural general process GAs GAs step-by-step Recommend- ations  Evolutionary Algorithms Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms in What are they? Extracting an algorithm from natural general process GAs Who interested? Biology, Physics, engineering/CS GAs step-by-step Recommend- ations  Evolutionary Algorithms Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms in What are they? Extracting an algorithm from natural general process GAs Who interested? Biology, Physics, engineering/CS GAs step-by-step Recommend- ations  Evolutionary Algorithms Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms in What are they? Extracting an algorithm from natural general process GAs Who interested? Biology, Physics, engineering/CS GAs step-by-step Recommend- ations  Evolutionary Algorithms Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms in What are they? Extracting an algorithm from natural general process GAs Who interested? Biology, Physics, engineering/CS GAs step-by-step Problem solving: scheduling; financial forecasting; neural Recommend- ations network design...  Evolutionary Algorithms TSP Evolutionary Algorithms Mills, Correia EA material – Problem: visit these cities Overview Evolutionary algorithms in general GAs GAs step-by-step Recommend- ations  Evolutionary Algorithms TSP Evolutionary Algorithms Mills, Correia EA material – An initial path Overview Evolutionary algorithms in general GAs GAs step-by-step Recommend- ations  Evolutionary Algorithms TSP Evolutionary Algorithms Mills, Correia EA material – An initial path A (locally) optimal path Overview Evolutionary algorithms in general GAs GAs step-by-step Recommend- ations  Evolutionary Algorithms TSP Evolutionary Algorithms Mills, Correia EA material – An initial path Another optimum Overview Evolutionary algorithms in general GAs GAs step-by-step Recommend- ations  Outline Evolutionary Algorithms Mills, Correia EA material – 1 EA material – Overview Overview Evolutionary algorithms in 2 Evolutionary algorithms in general general GAs GAs 3 GAs step-by-step Recommend- ations 4 GAs step-by-step 5 Recommendations  Outline Evolutionary Algorithms Mills, Correia EA material – 1 EA material – Overview Overview Evolutionary algorithms in 2 Evolutionary algorithms in general general GAs GAs 3 GAs step-by-step Recommend- ations 4 GAs step-by-step 5 Recommendations  Contents in this course Evolutionary Algorithms Mills, Correia EAs I covers the basic paradigms, and GAs in detail EA material – Overview lecture: RM TP: using an EA – exploring roles of key operators; Evolutionary algorithms in cumulative action of search vs. random search general GAs GAs step-by-step Recommend- ations  Contents in this course Evolutionary Algorithms Mills, Correia EAs I covers the basic paradigms, and GAs in detail EA material – Overview lecture: RM TP: using an EA – exploring roles of key operators; Evolutionary algorithms in cumulative action of search vs. random search general GAs EAs II covers alternative variants (ES, EP) and derivatives GAs (EDA); more advanced topics (schema theory) step-by-step lecture: RM Recommend- TP: explore EAs further, using the MuGA framework ations  Contents in this course Evolutionary Algorithms Mills, Correia EAs I covers the basic paradigms, and GAs in detail EA material – Overview lecture: RM TP: using an EA – exploring roles of key operators; Evolutionary algorithms in cumulative action of search vs. random search general GAs EAs II covers alternative variants (ES, EP) and derivatives GAs (EDA); more advanced topics (schema theory) step-by-step lecture: RM Recommend- TP: explore EAs further, using the MuGA framework ations GP in the family of EAs, but evolves programs rather than encoded solutions lecture: Sara Silva TP: presentations of projects/proposals  Outline Evolutionary Algorithms Mills, Correia EA material – 1 EA material – Overview Overview Evolutionary algorithms in 2 Evolutionary algorithms in general general GAs GAs 3 GAs step-by-step Recommend- ations 4 GAs step-by-step 5 Recommendations  Evolutionary algorithms From a high level Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms in Techniques for optimisation general GAs A search method that looks for solutions GAs Using a set of solutions = a population step-by-step Recommend- That evolves over time = in generations ations  A family of algorithms Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms Evolutionary algorithms in GA general GP GAs (classifier systems) GAs step-by-step evolutionary strategies Recommend- ations evolutionary programming cultural/memetic algorithms  General properties Evolutionary Algorithms Mills, Correia EA material – Inspired by evolution by natural selection (ENS) Overview Evolutionary algorithms in general GAs GAs step-by-step Recommend- ations  General properties Evolutionary Algorithms Mills, Correia EA material – Inspired by evolution by natural selection (ENS) Overview Evolutionary The method is intrinsically parallel algorithms in general GAs GAs step-by-step Recommend- ations  General properties Evolutionary Algorithms Mills, Correia EA material – Inspired by evolution by natural selection (ENS) Overview Evolutionary The method is intrinsically parallel algorithms in general in contrast to other methods of optimisation GAs GAs step-by-step Recommend- ations  General properties Evolutionary Algorithms Mills, Correia EA material – Inspired by evolution by natural selection (ENS) Overview Evolutionary The method is intrinsically parallel algorithms in general in contrast to other methods of optimisation GAs General GAs step-by-step Recommend- ations  General properties Evolutionary Algorithms Mills, Correia EA material – Inspired by evolution by natural selection (ENS) Overview Evolutionary The method is intrinsically parallel algorithms in general in contrast to other methods of optimisation GAs General GAs In contrast to other methods designed for linear problems step-by-step (which need the space to be at least twice-differenciable) Recommend- ations  General properties Evolutionary Algorithms Mills, Correia EA material – Inspired by evolution by natural selection (ENS) Overview Evolutionary The method is intrinsically parallel algorithms in general in contrast to other methods of optimisation GAs General GAs In contrast to other methods designed for linear problems step-by-step (which need the space to be at least twice-differenciable) Recommend- ations They find good solutions in less than exponential time (for non-linear problems)  General properties Evolutionary Algorithms Mills, Correia EA material – Inspired by evolution by natural selection (ENS) Overview Evolutionary The method is intrinsically parallel algorithms in general in contrast to other methods of optimisation GAs General GAs In contrast to other methods designed for linear problems step-by-step (which need the space to be at least twice-differenciable) Recommend- ations They find good solutions in less than exponential time (for non-linear problems) Well proven results (including in the real world)  EAs yes... but without abuse ?? Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary They are robust methods algorithms in general but they are not specialised GAs Only use if the conventional approaches to optimisation: GAs step-by-step do not exist for the problem under consideration Recommend- are not applicable ations fail  Notions of robustness Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms in general GAs GAs step-by-step Recommend- ations  Alternatives to EAs Evolutionary Algorithms Mills, Correia EA material – Overview Give consideration to the alternatives: Evolutionary exhaustive search algorithms in general sequential search random search GAs other heuristic methods GAs step-by-step other methods of brute force Recommend- ations  Alternatives to EAs Evolutionary Algorithms Mills, Correia EA material – Overview Give consideration to the alternatives: Evolutionary exhaustive search algorithms in general sequential search random search GAs other heuristic methods GAs step-by-step other methods of brute force Recommend- Better yet: ations Hybridised methods  Alternatives to EAs Evolutionary Algorithms Mills, Correia EA material – Overview Give consideration to the alternatives: Evolutionary exhaustive search algorithms in general sequential search random search GAs other heuristic methods GAs step-by-step other methods of brute force Recommend- Better yet: ations Hybridised methods Trade-offs (time to solution, your time)  On runtime scaling exponential vs polynomial scaling Evolutionary Algorithms Mills, Correia EA material – How long does it take to Overview Evolutionary find a solution? algorithms in general What happens when the GAs problem gets bigger? GAs step-by-step Recommend- ations  On runtime scaling exponential vs polynomial scaling Evolutionary Algorithms Mills, Correia EA material – How long does it take to Overview Evolutionary find a solution? algorithms in general What happens when the GAs problem gets bigger? GAs step-by-step CS often considers Recommend- method cost as a function ations of problem size  On runtime scaling exponential vs polynomial scaling Evolutionary Algorithms Mills, Correia EA material – How long does it take to Overview Evolutionary find a solution? 10 algorithms in general What happens when the 8 GAs problem gets bigger? 6 time (h) GAs step-by-step CS often considers 4 Recommend- method cost as a function 2 ations of problem size 0 9 10 11 12 13 14 15 16 which algorithm is problem size (bits) preferred?  On runtime scaling exponential vs polynomial scaling Evolutionary Algorithms Mills, Correia EA material – How long does it take to Overview Evolutionary find a solution? 10 algorithms in general What happens when the 8 GAs problem gets bigger? 6 time (h) GAs step-by-step CS often considers 4 Recommend- method cost as a function 2 ations of problem size 0 10 12 14 16 18 20 which algorithm is problem size (bits) preferred?  On runtime scaling exponential vs polynomial scaling Evolutionary Algorithms Mills, Correia How long does it take to find a solution? EA material – Overview What happens when the 10 Evolutionary algorithms in problem gets bigger? O(n log n) general 8 O ( n2 ) CS often considers O ( n4 ) GAs O(2n ) method cost as a function 6 time (h) GAs step-by-step of problem size 4 Recommend- ations which algorithm is 2 preferred? 0 10 12 14 16 18 20 Combinatorial problems: problem size (bits) worst case (should be!) exponential. O (2n ). Why?  On runtime scaling Identifying polynomial scaling Evolutionary Algorithms Mills, Correia EA material – Overview O(n log n) Evolutionary Big-Oh classes: linear, 106 O ( n2 ) algorithms in general log-linear, polynomial,... 105 O ( n4 ) O(2n ) 104 time (h) GAs Worse than polynomial? 103 GAs step-by-step (exponential, weakly 102 Recommend- exponential) 101 ations 100 Log-log plots indicative 101 102 problem size (bits)  Characteristics common to EAs Evolutionary Algorithms Mills, Correia EA material – Overview Based on simplified models of evolution (typ. at the Evolutionary species level) algorithms in general GAs GAs step-by-step Recommend- ations  Characteristics common to EAs Evolutionary Algorithms Mills, Correia EA material – Overview Based on simplified models of evolution (typ. at the Evolutionary species level) algorithms in general They try to obtain improvements of candidates in the GAs population over several generations GAs step-by-step Recommend- ations  Characteristics common to EAs Evolutionary Algorithms Mills, Correia EA material – Overview Based on simplified models of evolution (typ. at the Evolutionary species level) algorithms in general They try to obtain improvements of candidates in the GAs population over several generations GAs step-by-step The best-adapted individuals (those that solve the problem Recommend- the best) are increased in frequency in the next generation ations  Characteristics common to EAs Evolutionary Algorithms Mills, Correia EA material – Overview Based on simplified models of evolution (typ. at the Evolutionary species level) algorithms in general They try to obtain improvements of candidates in the GAs population over several generations GAs step-by-step The best-adapted individuals (those that solve the problem Recommend- the best) are increased in frequency in the next generation ations They do not need any additional information besides the objective function  Evolution Evolutionary Algorithms Mills, Correia EA material – Overview Two types of evolution Evolutionary Guided or directed: The user defines criteria/on of adaptation algorithms in general according to the task (e.g. GAs) – artificial GAs Open: There is no fixed criterion for the adaptation; GAs step-by-step instead the criteria emerge from the interaction of Recommend- individuals with an appropriate environment, ations which also evolves – natural (and also artificial = co-evolution)  The general scheme of EAs Evolutionary Algorithms Mills, Correia EA material – Operations that manipulate Operations that manipulate Overview the population the individuals Evolutionary algorithms in general Selection Reproduction GAs GAs step-by-step P0 Mutation Recommend- ations Substitution Decimation  Operation [I] Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary 1 Generate an initial population randomly algorithms in general GAs GAs step-by-step Recommend- ations  Operation [I] Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary 1 Generate an initial population randomly algorithms in general 2 Selection: select a restricted group for mating GAs based on the assessment of the individuals in population GAs step-by-step Recommend- ations  Operation [I] Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary 1 Generate an initial population randomly algorithms in general 2 Selection: select a restricted group for mating GAs based on the assessment of the individuals in population GAs step-by-step 3 Reproduction: recombine the genetic material Recommend- to create offspring, based on the group of mating ations individuals  Operation [II] Evolutionary Algorithms Mills, Correia EA material – 1 Mutation: randomly modify the details of an individual Overview to provide variation in available material in the population Evolutionary algorithms in general GAs GAs step-by-step Recommend- ations  Operation [II] Evolutionary Algorithms Mills, Correia EA material – 1 Mutation: randomly modify the details of an individual Overview to provide variation in available material in the population Evolutionary algorithms in general 2 Decimation (optional): Eliminate some individuals from GAs the current generation GAs e.g., remove solutions that are outside problem domain step-by-step Recommend- ations  Operation [II] Evolutionary Algorithms Mills, Correia EA material – 1 Mutation: randomly modify the details of an individual Overview to provide variation in available material in the population Evolutionary algorithms in general 2 Decimation (optional): Eliminate some individuals from GAs the current generation GAs e.g., remove solutions that are outside problem domain step-by-step Recommend- 3 Substitution: substitute (partially or totally) the ations population of the previous generation replace with the newly generated offspring, expected to include (some) improvements  The general scheme of EAs Evolutionary Algorithms Mills, Correia EA material – Operations that manipulate Operations that manipulate Overview the population the individuals Evolutionary algorithms in general Selection Reproduction GAs GAs step-by-step P0 Mutation Recommend- ations Substitution Decimation  Important characteristic of EAs Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms in general EAs do not require any information about the domain the GAs GAs problem or the objective function step-by-step Recommend- ations  Outline Evolutionary Algorithms Mills, Correia EA material – 1 EA material – Overview Overview Evolutionary algorithms in 2 Evolutionary algorithms in general general GAs GAs 3 GAs step-by-step Recommend- ations 4 GAs step-by-step 5 Recommendations  Genetic algorithms Origin Evolutionary Algorithms Mills, Correia EA material – Created by John Holland (∼1960s–70s) Overview Evolutionary Original objectives for GAs algorithms in general To abstract and rigorously explain adaptive processes in GAs nature GAs step-by-step To produce programs that are capable of using the Recommend- important mechanisms of natural systems ations  Genetic algorithms Origin Evolutionary Algorithms Mills, Correia EA material – Created by John Holland (∼1960s–70s) Overview Evolutionary Original objectives for GAs algorithms in general To abstract and rigorously explain adaptive processes in GAs nature GAs step-by-step To produce programs that are capable of using the Recommend- important mechanisms of natural systems ations Much later used as an optimisation tool for computational models  Characterisics of GAs Evolutionary Algorithms Mills, Correia EA material – Overview Individual = chromosome Evolutionary algorithms in a sequence of bits (encoding the set of parameters) general GAs Uses probabilistic rules GAs step-by-step instead of determinstic rules Recommend- ations Fitness function interprets and evaluates the chromosome (∼ objective function)  The canonical model (1) of GAs Evolutionary Algorithms Mills, Correia EA material – Overview Limited to three operations: Evolutionary Selection algorithms in general by ‘roulette wheel’ GAs crossover GAs step-by-step single-point Recommend- mutation ations bit-complement The most analogous to natural selction (Darwinian)  The canonical model (2) of GAs Evolutionary Algorithms Mills, Correia All strings are of the same length EA material – Overview Populations of constant size Evolutionary algorithms in general GAs GAs step-by-step Recommend- ations  The canonical model (2) of GAs Evolutionary Algorithms Mills, Correia All strings are of the same length EA material – Overview Populations of constant size Evolutionary algorithms in Mutation is probabilistic, and indepdendent of fitness general GAs GAs step-by-step Recommend- ations  The canonical model (2) of GAs Evolutionary Algorithms Mills, Correia All strings are of the same length EA material – Overview Populations of constant size Evolutionary algorithms in Mutation is probabilistic, and indepdendent of fitness general 2 offspring for every individual GAs and each individual has a sibling GAs step-by-step Recommend- ations  The canonical model (2) of GAs Evolutionary Algorithms Mills, Correia All strings are of the same length EA material – Overview Populations of constant size Evolutionary algorithms in Mutation is probabilistic, and indepdendent of fitness general 2 offspring for every individual GAs and each individual has a sibling GAs step-by-step Mating is restricted to crossover Recommend- ations An offspring: symbols 1... i are from one parent, and symbols i + 1... l are from the other with i chosen uniformly at random (l = the chromosome length)  Outline Evolutionary Algorithms Mills, Correia EA material – 1 EA material – Overview Overview Evolutionary algorithms in 2 Evolutionary algorithms in general general GAs GAs 3 GAs step-by-step Recommend- ations 4 GAs step-by-step 5 Recommendations  GA step-by-step (1) The problem Evolutionary Algorithms Mills, Correia The function to optimise (unimodal) EA material – Overview f (x) = 1024 − (x − 32)2 with x ∈ [0, 63], x ∈ N Evolutionary algorithms in general 1200 Fitness function GAs 1000 GAs step-by-step 800 f(x) Recommend- 600 ations 400 200 0 0 10 20 30 40 50 60 x  GA step-by-step (1) The representation Evolutionary Algorithms Mills, Correia EA material – Overview The function to optimise (unimodal) Evolutionary algorithms in general f (x) = 1024 − (x − 32)2 with x ∈ [0, 63], x ∈ N GAs GAs Representation: binary encoding of x. ex. 001011 step-by-step To evaluate an individual: Recommend- ations decoding: 010110 → 22 evaluate: f (22) = 1024 − (−10)2 = 924  The general scheme of EAs Evolutionary Algorithms Mills, Correia EA material – Operations that manipulate Operations that manipulate Overview the population the individuals Evolutionary algorithms in general Selection Reproduction GAs GAs step-by-step P0 Mutation Recommend- ations Substitution Decimation  GA step-by-step (2) An initial population Evolutionary Algorithms Mills, Correia EA material – With 4 individuals Overview Evolutionary algorithms in i Binary xi f (xi ) %f (xi ) E[n(xi )] Roulette general a 000100 4 240 9.6 0.38 0 GAs b 110111 55 495 19.7 0.59 1 GAs step-by-step c 011001 25 975 38.9 1.55 3 Recommend- d 101111 47 799 31.8 1.27 0 ations P — — 2509 100.0 4 4 Mean — — 627 — — — Max. — — 975 — — —  GA step-by-step (3) Selection Evolutionary Algorithms Mills, Correia EA material – The roulette wheel Overview Evolutionary a algorithms in general i %f (xi ) No. selected 1 a 9.6 0 b d 4 GAs GAs b 19.7 1 2 step-by-step c 38.9 3 Recommend- ations d 31.8 0 c (Note: RWS vs SUS) 3  GA step-by-step (4) Crossover Evolutionary Algorithms Mills, Correia Mating EA material – Overview For each pair pick a random number between 1 and 5 Evolutionary (l = 6, p ∈ [1, l − 1]) algorithms in general GAs GAs (b) 11:0111 −→ 111001 (a0 ) step-by-step (c) 01:1001 010111 (b0 ) Recommend- ations  GA step-by-step (4) Crossover Evolutionary Algorithms Mills, Correia Mating EA material – Overview For each pair pick a random number between 1 and 5 Evolutionary (l = 6, p ∈ [1, l − 1]) algorithms in general GAs GAs (b) 11:0111 −→ 111001 (a0 ) step-by-step (c) 01:1001 010111 (b0 ) Recommend- ations (c)01100:1 011001 (c0 ) −→ (c)01100:1 011001 (d0 )  GA step-by-step (5) After one generation Evolutionary Algorithms Mills, Correia Mutation (low probability) alters only the 2nd bit of the EA material – last individual Overview Completely replace the whole population with a new one Evolutionary algorithms in general i binary xi f (xi ) %f (xi ) GAs a0 111001 57 399 14.2 GAs step-by-step b0 010111 23 942 33.5 Recommend- c0 011001 25 975 34.7 ations d00 001001 9 495 17.6 P — — 2812 100.0 mean — — 703 — max. — — 975 —  Characteristic observations in observed in most GAs Evolutionary Algorithms Mills, Correia EA material – Preservation, and greater reproduction, of the fittest Overview individuals – selection Evolutionary algorithms in general GAs GAs step-by-step Recommend- ations  Characteristic observations in observed in most GAs Evolutionary Algorithms Mills, Correia EA material – Preservation, and greater reproduction, of the fittest Overview individuals – selection Evolutionary algorithms in combination of chromosomes can lead to better sequences general than the original – crossover GAs GAs step-by-step Recommend- ations  Characteristic observations in observed in most GAs Evolutionary Algorithms Mills, Correia EA material – Preservation, and greater reproduction, of the fittest Overview individuals – selection Evolutionary algorithms in combination of chromosomes can lead to better sequences general than the original – crossover GAs GAs Selection and reproduction perform a robust search in the step-by-step solution space Recommend- ations  Characteristic observations in observed in most GAs Evolutionary Algorithms Mills, Correia EA material – Preservation, and greater reproduction, of the fittest Overview individuals – selection Evolutionary algorithms in combination of chromosomes can lead to better sequences general than the original – crossover GAs GAs Selection and reproduction perform a robust search in the step-by-step solution space Recommend- ations The mutation operator is secondary  Characteristic observations in observed in most GAs Evolutionary Algorithms Mills, Correia EA material – Preservation, and greater reproduction, of the fittest Overview individuals – selection Evolutionary algorithms in combination of chromosomes can lead to better sequences general than the original – crossover GAs GAs Selection and reproduction perform a robust search in the step-by-step solution space Recommend- ations The mutation operator is secondary it is mainly used to retrieve alleles that have been lost from the entire population  Characteristic observations in observed in most GAs Evolutionary Algorithms Mills, Correia EA material – Preservation, and greater reproduction, of the fittest Overview individuals – selection Evolutionary algorithms in combination of chromosomes can lead to better sequences general than the original – crossover GAs GAs Selection and reproduction perform a robust search in the step-by-step solution space Recommend- ations The mutation operator is secondary it is mainly used to retrieve alleles that have been lost from the entire population alone it can tend towards random search  Visualisation of GAs Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms in general GAs GAs step-by-step Recommend- ations xpdf  Outline Evolutionary Algorithms Mills, Correia EA material – 1 EA material – Overview Overview Evolutionary algorithms in 2 Evolutionary algorithms in general general GAs GAs 3 GAs step-by-step Recommend- ations 4 GAs step-by-step 5 Recommendations  Recommendations for operation of GAs Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms in The operation of the canonical GA has many limitations general particularly in complex problems (real-world) GAs There is a great diversity of choice for each operator GAs step-by-step We can make some recommendations Recommend- ations but they do not create miracles...  Tournament selection Evolutionary Algorithms Mills, Correia EA material – Overview Selection for a tournament of size k Evolutionary pick k individuals at random algorithms in general the highest fitness reaches the next generation GAs repeat the process N times (for pop size N ) GAs step-by-step The selection pressure is controlled by k Recommend- stronger pressure for higher k ations (consider k = n, k = 1) typical values between 2 and 4  Uniform crossover Evolutionary Algorithms Mills, Correia EA material – For the offspring A0 Overview select each bit from one of the two parents, A and B with Evolutionary algorithms in equal probability general GAs The other bits (those not used in A0 ) are used in the GAs sibling, B 0 step-by-step Recommend- Only use if there are reasons for it ations It is necessary to mix the genetic material Otherwise, use single-point crossover (if you know variable ordering a priori! – more next lecture)  Mutation rate Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary Mutation should not cause major changes in the algorithms in general population GAs otherwise it tends to a random search (cf. sim annealing) GAs Try not to exceed an average of 10% of the individuals in step-by-step Recommend- the population ations A typical mutation rate (for binary optimisation) is 1/n  Population Evolutionary Algorithms Mills, Correia Limited size EA material – Overview O (100) Too large a population does not pay in time/quality Evolutionary algorithms in tradeoff general (but too small likely lacks diversity) GAs GAs High level of replacement step-by-step Keep up to 10% of individuals from the previous generation Recommend- ations Elitism always retain the fittest individual(s) found so far this improves performance on unimodal functions but deteriorates in multimodal functions (due to premature convergence)  Final aspects Evolutionary Algorithms Mills, Correia EA material – Overview Evolutionary algorithms in general GAs GAs step-by-step Recommend- ations  Steady-state GA Variant in generational update Evolutionary Algorithms Mills, Correia EA material – Overview no central coordination is Evolutionary 2 parents necessary algorithms in general good for parallel GAs implementation 1 child substitues GAs repeat 1 member of popln evaluation of step-by-step N times individuals can be Recommend- distributed ations tournament selection is highly appropriate  Hybrid solutions/hybrid algorithms Evolutionary Algorithms Mills, Correia EA material – Overview Genetic Evolutionary pesquisa de zonas elevadas algorithms in Algorithm general search for high-quality regions GAs GAs step-by-step Recommend- ations Local pesquisa dos picos Optimisation search for peaks in that region  Other aspects Evolutionary Algorithms Mills, Correia Sexual differentiation EA material – Overview can give rise to specialisation – useful for finding niches Evolutionary algorithms in Parallel implementations general Various micro-operators GAs inversion GAs step-by-step duplication and deletion (of duplicates) of genes Recommend-... ations Complex representations diploidy structured chromosomes...  liberalisation of GAs Evolutionary Algorithms Mills, Correia Darwin EA material – Overview Genetic traits are inherited from parent to offspring – with Evolutionary mutations (the most usual in GAs) algorithms in general Lamarck GAs Genetic transmission of both genetic and learned traits GAs (can increase the speed of convergence in GAs) problem step-by-step Recommend- solving – not biol plausible ations Baldwin effect Ontogenetic learning enhances favourable genetic changes multi-parent reproduction...