10. Evolutionary programming

Slides:



Advertisements
Similar presentations
인공지능 소개 부산대학교 인공지능연구실. 인공 + 지능 인공지능이란 ? 2.
Advertisements

15 장. 알고리즘의 설계 알고리즘 설계 학습목표 기본 패턴 패턴의 한계점 일곱 가지 패턴의 알고리즘 설계 기법을 이해한다.
Master Thesis Progress
Capstone Design - Concept & Management
Chapter 9. 컴퓨터설계기초 9-1 머리말 9-2 데이터 처리장치 (Datapath)
Sources of the Magnetic Field
스테레오 비젼을 위한 3장 영상의 효율적인 영상정렬 기법
Development and Initial Validation of Quality-of-Life Questionnaires for Intermittent Exotropia Ophthalmology 2010;117:163–168 Pf. 임혜빈 / R2 정병주.
TSP 알고리즘 구현 서왕덕.
Chap. 9 Genetic Algorithms
Chaper 2 ~ chaper 3 허승현 제어시스템 설계.
REINFORCEMENT LEARNING
Problems of Finite Difference Method (유한차분법)
7장 : 캐시와 메모리.
On the computation of multidimensional Aggregates
Numerical Analysis - preliminaries -
Christopher G. Langton (1989) 인지과학 협동과정 강 소 영
Ch. 5 : Analog Transmission
제 5장. Context-Free Languages
Genetic Algorithm 신희성.
Dynamic Programming.
Ch. 10 Algorithm Efficiency & Sorting
제 14 장 거시경제학의 개관 PowerPoint® Slides by Can Erbil
1 도시차원의 쇠퇴실태와 경향 Trends and Features of Urban Decline in Korea
Chapter 2. Finite Automata Exercises
5. 비제약 최적설계의 수치해법 (Numerical Methods for Unconstrained Optimum Design)
숭실대학교 마이닝연구실 김완섭 2009년 2월 8일 아이디어  - 상관분석에 대한 연구
Deterministic Problems
for Robust Facial Landmark Localization
발표자 : 홍익대학교 소프트웨어 공학 연구실 변은영 지도교수 : 김영철
Fault Diagnosis for Embedded Read-Only Memories
Medical Instrumentation
진대제 장관이 말하는 '100점짜리 인생의 조건' ▲ 진대제 정보통신부 장관    `인생을 100점짜리로 만들기 위한 조건은 무엇일까요`  진대제 정보통신부 장관이 대한상의 초청 조찬 간담회를 시작하며 참석자 들에게 던진 `조크성` 질문이다. 진 장관은 "제가 재미있는 얘기하나 하겠습니다"고 말하고, 
Parallel software Lab. 박 창 규
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
Genetic Programmed Soccer Softbot
Data Mining Final Project
Changing Objectives of Optimization
패러다임과 과학혁명.
Chip-based Computing + UMDA
Modeling one measurement variable against another Regression analysis (회귀분석) Chapter 12.
Ch.03 Dynamic Programming (동적 프로그래밍 or 동적 계획법)
Introduction to Programming Language
Inferences concerning two populations and paired comparisons
Course Guide - Algorithms and Practice -
브레인스토밍이란? 공학입문 설계 네번째 시간 공학입문설계
Ch01. 지능형 시스템 개론.
Statistical inference I (통계적 추론)
Speaking -두 번째 강의 (Part 1 실전테스트 1,2) RACHEL 선생님
Machine Evolution.
제 4 장 유전자 알고리즘 (Genetic Algorithm)
Modeling one measurement variable against another Regression analysis (회귀분석) Chapter 12.
점화와 응용 (Recurrence and Its Applications)
창 병 모 숙명여대 전산학과 자바 언어를 위한 CFA 창 병 모 숙명여대 전산학과
해양생태학 2016년 1학기 안순모.
Definitions (정의) Statistics란?
The general form of 0-1 programming problem based on DNA computing
성경의 맥을 잡아라 박소원
Bug Localization Based on Code Change Histories and Bug Reports
Additional fitness measures for Sequence Generation
CH557 진화연산 2003년도 제 2학기.
Hongik Univ. Software Engineering Laboratory Jin Hyub Lee
A SMALL TRUTH TO MAKE LIFE 100%
A SMALL TRUTH TO MAKE LIFE 100%
[CPA340] Algorithms and Practice Youn-Hee Han
6.1 Changing the View Point
CSI 진화연산 2008년도 제 1학기.
Traditional Methods – Part 1
Chapter 7: Deadlocks.
Speaking -여섯 번째 강의 (Review ) RACHEL 선생님
Presentation transcript:

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/