文化基因算法課件

1、Memetic Algorithm,Member：楊勇佳、易科、朱家驊、蘇航,1,學(xué)習(xí)交流PPT,Contents,1 Introduction 2 The development of MAs 2.1 1st generation 2.2 2nd generation 2.3 3rd generation 3 Applications 4 Example,2,學(xué)習(xí)交流PPT,Introduction,Hawkins(1976) raised meme notion,3,學(xué)習(xí)交流PPT,Introduction,Inspired by both Darwinian principles of

2、natural evolution and Dawkins notion of a meme, the term “Memetic Algorithm” (MA) was introduced by Moscato in 1989 where he viewed MA as being close to a form of population-based hybrid genetic algorithm (GA) coupled with an individual learning procedure capable of performing local refinements.,In

3、general, using the ideas of memetics within a computational framework is called Memetic Computing or Memetic Computation (MC). MA is a more constrained notion of MC. More specifically, MA covers one area of MC,4,學(xué)習(xí)交流PPT,The development of MAs 1st generation,a marriage between a population-based glob

4、al search (often in the form of an evolutionary algorithm) coupled with a cultural evolutionary stage. This suggests why the term MA stirred up criticisms and controversies among researchers when first introduced.,Pseudo code: Procedure Memetic Algorithm Initialize: Generate an initial population; w

5、hile Stopping conditions are not satisfied do Evaluate all individuals in the population. Evolve a new population using stochastic search operators. Select the subset of individuals, that should undergo the individual improvement procedure. for each individual in do Perform individual learning using

6、 meme(s) with frequency or probability of for a period of . Proceed with Lamarckian or Baldwinian learning. end for end while,HybridAlgorithms,5,學(xué)習(xí)交流PPT,The development of MAs 2nd generation,exhibiting the principles of memetic transmission and selection in their design. In Multi-meme MA, the memeti

7、c material is encoded as part of thegenotype. MA considering multiple individual learning methods within an evolutionary system, the reader is referred to.,Multi-meme, Hyper-heuristic and Meta-Lamarckian MA,6,學(xué)習(xí)交流PPT,The development of MAs 3nd generation,Co-evolution8and self-generating MAs9 In cont

8、rast to 2nd generation MA which assumes that the memes to be used are known a priori, 3rd generation MA utilizes a rule-based local search to supplement candidate solutions within the evolutionary system, thus capturing regularly repeated features or patterns in the problem space.,7,學(xué)習(xí)交流PPT,The basi

9、c model of MAs,8,學(xué)習(xí)交流PPT,MA Method,For all the problems we want to find the optimal solution .facing a fundamental question how to generation,Pseudo code: Process Do-Generation ( pop : individual ) variables breeders, newpop : Individual ; begin breeders Select-From-Population(pop); newpop Generate-

10、New-Population(breeders); pop Update-Population (pop, newpop) end,9,學(xué)習(xí)交流PPT,MA Method,For Generate-New-Population process , the most typical situation involves utilizing just two operators:recombination and mutation.,Pseudo code: Process Generate-New-Population ( pop : Individual , op : Operator ) I

11、ndividual variables buffer : Individual ; j : 1.|op|; begin buffer0 pop; for j 1:|op| do bufferj Apply-Operator (opj, bufferj 1); End for;,10,學(xué)習(xí)交流PPT,In essence, a mutation operator must generate a new solution by partly modifying an existing solution. This modification can be random as it is typica

12、lly the case or can be endowed with problem-dependent information so as to bias the search to probably-good regions of the search space,MA Method,11,學(xué)習(xí)交流PPT,MA Method,Pseudo code: Process Local-Improver ( current : Individual, op : Operator)variablesnew : Individualbeginrep eatnew Apply-Operator(op,

13、 current);if ( Fg (new) Fg(current) thencurrent new;end ifuntil Local-Improver-Termination-Criterion();return current;end,12,學(xué)習(xí)交流PPT,MA Method,After having presented the innards of the generation process, we can now have access to the larger picture. The functioning of a MA consists of the iteration

14、 of this basic generational step,Pseudo code: Process MA () Individual variablespop : Individual ;beginpop Generate-Initial-Population();rep eatpop Do-Generation (pop)if Converged(pop) thenpop Restart-Population(pop);end ifuntil MA-Termination-Criterion()end,13,學(xué)習(xí)交流PPT,MA Method,The Generate-Initial

15、-Population process is responsible for creating the initial set of | pop| configurations,Pseudo code: Process Generate-Initial-Population ( : N) Individual variablespop : Individual ;ind : Individual;j : 1.;beginfor j 1: doind Generate-Random-Solution();popj Local-Improver (ind);endforreturn popend,

16、14,學(xué)習(xí)交流PPT,MA Method,Consider that the population may reach a state in which the generation of new improved solution be very unlikely,Pseudo code: Pro cess Restart-Population ( pop : Individual ) Individual variablesnewpop : Individual ;j, #preserved : 1.|pop| ;b egin#preserved |pop| %PRESERV E;for

17、j 1:#preserved donewpopj ithBest(pop, j);endforfor j (#preserved + 1) : |pop| donewpopj Generate-Random-Configuration();newpopj Local-Improver (newpopj);endfor;return newpopend,15,學(xué)習(xí)交流PPT,MAs,In fact, MAs is a genetic algorithm framework, is a concept, in this framework, using different search strat

18、egies can constitute different MAs, such as global search strategy can be used genetic algorithms, evolution strategies, evolutionary programming, etc. local search strategy can be used to climb the search, simulated annealing, greedy algorithms, tabu search, guided local search.,16,學(xué)習(xí)交流PPT,Applicat

19、ions,many classicalNPproblem For example graph partitioning,multidimensional knapsack,travelling salesman problem,quadratic assignment problem,set cover problem,minimal graph coloring,max independent set problem,bin packing problem. Comparison with the genetic algorithm converges faster, better resu

20、lts.,17,學(xué)習(xí)交流PPT,Example,18,學(xué)習(xí)交流PPT,Example,19,學(xué)習(xí)交流PPT,Example,20,學(xué)習(xí)交流PPT,Example,21,學(xué)習(xí)交流PPT,Example,22,學(xué)習(xí)交流PPT,Example,Step using simulated annealing algorithm for local search STEP 1 Given an initial temperature, Individual as the initial state of the simulated annealing algorithm; STEP 2 Generate a new state, the neighborhood function defined as In other states of the two items to choose; STEP 3 calculate the number of old and new state energy, the energy functional Is defined as the reciprocal of the fitness function; STEP 4 accept the new state according to guidelines Metr