10. Evolutionary programming Part 3: Evolutionary Algorithms and Their Standard Instances On book : Evolutionary Computation – Basic Algorithms and Operators CHAPTERS 7. Introduction to evolutionary algorithms 8.Genetic algorithms 9. Evolution strategies 10. Evolutionary programming 11. Derivative methods in genetic programming Presented by Bado Lee

Introduction to evolutionary algorithms What is Evolutionary algorithm? 집단 유전학의 개체 진화 원리를 이용하는 solution space search 방법 Evolutionary algorithm 이 소용없는 문제들 Deterministic algorithm으로 쉽게 풀 수 있는 문제들 Ex) shortest path 같은 문제들 NP hard 이더라도 문제 공간이 아주 작은 문제들 (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

(C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/ History of EA 1950~60 독자적인 그룹이 생김 GA (Genetic Algorithm) – John Holland 미국사람 Crossover중요하게 생각 Mutation 의 중요도는 상대적으로 별로 중요 하지 않음 EP (Evolutionary Programming) Fogel, Owens, Walsh - 미국사람 Crossover 가 필요없다고 주장하는 사람들 ES Rechenberg – 독일사람 Real valued vector 사용 Parent 와 offspring의 population 이 일반적으로 같지 않음 (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

(C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/ Genetic Algorithm First proposed and analyzed by John Holland (1975) Representation - Bitstring representation Method of selection – proportional selection Primary method of producing variations – crossover Most important characteristic is CROSSOVER! (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Pseudocode for genetic algorithm In original version Only one pair is selected for mating per cycle Fixed size of population (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Crossover and mutation Chromosome – 염색체 (정보의 표현형) 또는 문제공간에서 하나의 solution으로 볼 수 있음 John Holland 는 binary representation을 선호 다양한 솔루션을 생성 할 수 있다는 믿음 때문. 하지만 mutation을 늘리면 같은 효과를 얻을 수 있다. 따라서 불필요한 constraint Crossover - exploitation 두 chromosome 을 부분결합하여 하나의 chromosome을 생성 Mutation - exploration Chromosome의 미소변형 (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Generation Gap : Replacement of k chromosomes among p population Generation gap : k/p If k->p :generational GA 수렴이 느리고 computational cost 가 크다. If k->1 : steady-state GA 수렴이 빠른 대신에 Local optimal 한 solution에 도달할 가능성이 크다. 즉 premature convergence (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Problem Representation Binary : k-ary Gray coding 인접한 두 수는 한 bit만 차이나도록 하는 Cyclic coding의 대표적 예 5 6 2 4 9 :decimal 0101 0110 0010 0100 0000 1001 :binary (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Problem Representation cont. Inversion Inverse a seq. of genes in the middle of GA running Gene의 인접성을 고려하여 재배치함 Messy GA Allows variable-length chromosomes Overspecification, underspecification overspecification (1,1) (2,0) (2,1) (4,0) (1,0) 10*0 This means overspecification (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Problem Representation cont. Locus based encoding Graph bisection 의 문제 같은 경우에 용이한 표현형 Order based edcoding 인접성을 잘 표현할 수 있음 Crossover에 취약 Multi-dimensional encoding 등등 많은 표현형이 존재 가능하고 문제 specific하게 적용 되어야 함 절대적인 representation 존재 X (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

(C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/ Selection operator Selection oprator Crossover을 위한 selection 에서 어떤 Chromosome 을 선택할 지 결정 Premature convergence를 피하기 위하여 다양한 method존재 Roulette-wheel selection Tournament selection Rank-based selection Sharing (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Crossover operator –GA 대표 연산자 One-point crossover Two point crossover Multipoint crossover Cut and splice Uniform Crossover (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Evolutionary Strategy Emphasis on Problem-dependent representations!!! Real valued search space Traditionally on Euclidean search space Archetype of ES If better than previous solution then ->>accept new solution (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Problem Representation Real encoding 실수값을 유전자에 할당 수의 크기 개념을 반영하기 유리 Crossover 는 산술교차 사용 인자의 속성이 실수인 경우, 인자와 유전자가 1:1대응 Phenotype genotype 1.3 34 5.656 23.34 … 34.1 -0.004 (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Rechenberg’s Magic number 0.2 Until Success ratio more than 0.2 Increase alpha – exploration When it drops below 0.2 Decrease alpha – exploitation Schwefel’s proposal (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Contemporary evolution strategies General algorithmic framework – by Schwefel So simple ES can be expressed as (1+1)ES ->not in use Generates lambda offspring from mu parents and selects the mu best individuals form the lambda+mu individuals in total Always is (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Contemporary evolution strategies Generates lambda offspring form mu parents but selects the mu best individuals only form lambda offspring Always is (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Contemporary evolution strategies (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Nested evolution strategies (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Evolutionary programming Basic EC’s 4 main components Initialization Variation – only mutation Evaluation (scoring) -fitness Selection Mostly size of the population remains constant But this is no restriction Different from GA because EP is a top down versus bottom-up approach to optimization Selection operates only on the phenotypic expressions of genotype (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Different from GA because cont. Underlying coding of the phenotype is only affected indirectly Because Realization that a sum of optimal parts rarely leads to an optimal overall solution Do not believe in schemata theory Solutions in an EP algorithms are judged solely on their fitness with respect to the given environment No attempt is made to partition credit to individual components of the solutions NO CROSSOVER – philosophically very important (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Genetic Programming - Koza Uses trees as chromosomes Suitable for LISP (s-expression) Data structures are executable computer programs (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Crossover : recombination in genetic programming Terminals : and or not … Functions : d0 d1 … inputs (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Initialization & Recombination Initial population should be constructed under several constraints SA. Number of Available terminals Number of arguments required by functions Recombined program should also satisfy constraints (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

Fitness value of a individual Performance of the program should be measured somehow… (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

(C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/ Why is GP interesting? Conceptual shift of the problem being solved by the genetic algorithm Parameter discovery ->> search for program directly Changed way we think about solving problems Capable of integrating a wide variety of existing capabilities Parents : programs … children : also programs (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/

(C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/ Many Thanks. (C) 2010, SNU Biointelligence Lab, http://bi.snu.ac.kr/