Genetic Algorithm 20015159 신희성.

Presentation on theme: "Genetic Algorithm 20015159 신희성."— Presentation transcript:

1 Genetic Algorithm 신희성

2 Overview Motivation 유전자 알고리즘의 개요 유전자 알고리즘의 구성요소 유전자 알고리즘의 특성 다윈의 진화론
예제 : Minimum of function 유전자 알고리즘의 구성요소 Encoding Scheme Fitness Function Genetic Operators Parameter Setting 유전자 알고리즘의 특성 예제 : Traveling Salesman Problem (TSP)

3 Where are we at? Search Uninformed Search
Breadth-First, Unform-Cost, Depth-First, Depth-Limited, Iterative Deepening, Bidirectional Search Informed Search Best-First Search (Greedy Search) A* Search Memory Bounded Search IDA*, SMA* Iterative Improvement Algorithm Hill-Climbing, Simulated Annealing

4 Motivation

5 다윈의 진화론 다산  생존경쟁  변이  자연선택  진화 e.g.) 똑똑한 토끼가 살아 남는다? 초기 토끼집단
진화된 토끼집단 느리고 영리하지 못한 토끼 빠르고 영리한 토끼

6 History of Genetic Algorithm (1/3)
1965년 Rechenberg(독일) 진화전략(Evolutionary Strategy) 발표 단 두개의 해로 이루어진 해 집단 사용 교차 연산자 사용 안함 1966년 Fogel, Owens, Walsh 진화 프로그램 제안 교차 연산이 없는 변이만을 사용

7 History of Genetic Algorithm (2/3)
Developed by John Holland in the early 70’s 유전 알고리즘의 대부 해 집단에 근거, 교차와 변이를 포함한 GA의 골격 마련 1975년 역사적 저서 [Adaptation in Natural and Artificial Systems] 발표 1984년 산타페 연구소에 합류, 연구 방향을 [Complex System]에서 [Adaptive Complex System]으로 선회

8 History of Genetic Algorithm (3/3)
1985년 제 1회 International Conference on Genetic Algorithms 개최 90년대 많은 주목을 받은 Artificial Life의 주된 도구로 활용됨 1997년 IEEE Transactions on Evolutionary Computing 개설

9 유전자 알고리즘 (GA: Genetic Algorithm)
진화의 원리를 문제 풀이 또는 모의 실험에 이용하는 연구의 한 방법 Solutions are encoded as chromosomes Search proceeds through maintenance of a population of solutions Reproduction favors “better” chromosomes New chromosomes are generated during reproduction through processes of mutation and cross over, etc.

10 Genetic Algorithm GA가 필요 없는 문제 GA의 적용이 효과적인 문제
최단 경로 탐색 문제, Sorting 등 GA의 적용이 효과적인 문제 Traveling salesman problem (TSP) 함수 값을 최대화하는 변수 NP Complete 문제

11 Basic Terminology in Biology
DNA, Chromosome : 염색체, 유전물질 유전자(gene) : 염색체 상의 각 인자 유전자형(genotype) : 유전자의 조합 표현형(phenotype) : 관찰되는 형질 생물학적 진화 개체는 교차에 의해 염색체를 부분 결합과 돌연변이에 의해 새로운 염색체를 가진 새로운 개체 생성 환경에 적응하기 유리한 개체만이 선택적으로 번성

12 Basic Terminology in GA
염색체 (chromosome) : 임의의 solution 해집단 (population) : 정해진 개수의 염색체 집단 유전자 (gene) : 염색체의 인자 하나 유전자 형 : 염색체 자체 표현형 : 유전자형에 대응하는 해의 모양

13 유전자 알고리즘의 구조 selection cross over mutation Substitution Fitness
1 selection cross over Search space 1 1 population A B C D mutation Fitness evaluation 1 reproduction Substitution

14 유전자 알고리즘 function GENETIC-ALGORITHM(population, FITNESS-FN) returns an individual input: population, a set of individuals FITNESS-FN, a function that measures the fitness of an individual repeat parents  SELECTION(population,FITNESS-FN) population  REPRODUCTION(parents) until some individual is fit enough return the best individual in population, according to FITNESS-FN % REPRODUCTION = cross-over + mutation

15 예1 : Minimum of Function Minimum of Function
: 함수의 최소값을 찾는 문제 Example Function minimum value

16 State after evolutions
예1 : Minimum of Function Initial state State after evolutions

17 유전자 알고리즘의 구성요소 개체 표현 방법 (Encoding Scheme) 적합도 함수 (Fitness Function)
문제의 해가 될 가능성이 있는 것의 유전자적 표현 방법 적합도 함수 (Fitness Function) 유전자를 평가하는 함수 Solution에 가까운 유전자일 수록 높게 평가 유전 연산자 (Genetic Operators) 자손의 합성을 변화시키는 유전 연산자들 알고리즘 제어 파라미터 (Parameter Setting) 유전자 알고리즘이 사용하는 여러 가지 매개변수의 값 개체 집단의 크기, 유전 연산자를 적용시키는 확률 등

18 개체 표현 방법 (Encoding Scheme)
문제의 해가 될 가능성이 있는 것을 유전자로 표현하는 것 전형적인 표현 양식은 이진수 0과 1을 이용한 일차원적 표현 표현 양식이 결정된 후 이에 맞는 교차 연산자 및 변이 연산자 결정

19 스키마 (Schema) 염색체에 들어 있는 패턴 개체 표현 방법
1101에는 1***, *1**,…11**, 1*0*, …, 110*, *101, ..., 1101, ****의 16개 스키마가 포함됨 * : don’t care symbol 1 또는 0 : specific symbol 유전 알고리즘이란 초기의 작은 스키마가 결합하여 점점 더 큰 스키마를 이루어가는 과정 마지막 return value는 하나의 거대한 스키마

20 1. 이진수 표현, k진수 표현 Binary Encoding, n-ary Encoding
개체 표현 방법 1. 이진수 표현, k진수 표현 Binary Encoding, n-ary Encoding vs 이진수 표현할 경우 교차시 자름 선 위치가 많아져 추가 변이 효과 발생 교차의 다양성 제공 k진수의 경우 의미 있는 스키마 보존 가능성 높음 교차의 다양성은 시뮬레이션으로 가능

21 개체 표현 방법 2. Gray Coding 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, … 2진수 표현의 한 변형 인접한 수는 단 한 비트만 차이가 나도록 하는 코드 체계 의미상으로 유사한 두 해가 문제 공간에서 가까이 위치하도록 만든 코드 체계 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

22 3. 순열 표현 (Permutation Encoding)
개체 표현 방법 3. 순열 표현 (Permutation Encoding) 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, … 순열을 유전자형으로 가짐 순서 기반형 표현 Traveling salesman problem (TSP)

23 4. 실수 표현 (Value Encoding) 독일의 진화 전략 그룹 Bremermann이 교차 연산에 실수를 처음 사용
개체 표현 방법 4. 실수 표현 (Value Encoding) 독일의 진화 전략 그룹 교차 연산자를 사용 안 함 이진연산자 사용 불필요, 실수 사용 Bremermann이 교차 연산에 실수를 처음 사용 실수 하나를 하나의 유전자로 사용 크기의 개념을 연산자에 적용 가능 부모의 값을 평균하여 자식의 값에 적용시키는 산술 교차를 사용할 수 있음 Finding weights for neural network

24 5. 가변 표현 대부분의 GA는 수행이 완료될 때까지 표현 방식을 바꾸지 않음 표현상의 비효율로 인한 한계 극복 불가능
개체 표현 방법 5. 가변 표현 대부분의 GA는 수행이 완료될 때까지 표현 방식을 바꾸지 않음 표현상의 비효율로 인한 한계 극복 불가능 표현 방식을 미리 고정하지 않고 알고리즘 수행 중 표현 방식을 변화하는 방법 고안 역치, 메시 유전 알고리즘, 유전 프로그래밍 유전자 재배열

25 개체 표현 방법 정리 여러가지 표현형태들 주로 0과 1의 Binary encoding을 많이 사용 개체 표현 방법
Permutation Encoding Value Encoding 주로 0과 1의 Binary encoding을 많이 사용 1 e.g.) 1 5 3 2 6 8 4 7 e.g.) 1.2 5.3 0.4 2.3 5 3.1 06 7.2 A B D J E I e.g.)

26 적합도 함수 (Fitness Function)
염색체의 해(solution)로서의 적합도를 평가 1 64 361 169 576 염색체 적합도 e.g.)

27 유전 연산자 (Operators of GA)
선택 연산자 (Selection) 교차를 위해 해집단(population)에서 2개의 염색체를 선택 우수한 해에게 선택 가능성을 높게 해 준다 교차 연산자 (Crossover) 선택된 두개의 parent로부터 하나의 offspring을 생성 GA의 대표적 연산자 변이 연산자 (Mutation) 해를 임의로 변환 대치 연산자 (Substitution) 부모의 염색체를 생성된 염색체로 대치

28 선택 연산자 (1/2) Roulette wheel selection Elitist preserving selection
유전 연산자 선택 연산자 (1/2) Roulette wheel selection 각 염색체의 적합도에 비례하는 만큼 roulette의 영역을 할당한 다음, roulette을 돌려 화살표가 가리키는 영역의 염색체를 선택 적합도가 높은 것은 선택될 확률이 그만큼 많고 적합도가 낮을 것은 선택될 확률이 상대적으로 낮다 Elitist preserving selection e.g.) 염색체 적합도 % of total A B C D 01000 10011 01101 11000 64 361 169 576 5.5 30.9 14.4 49.2 Roulette Wheel

29 선택 연산자 (2/2) Expected-value selection Ranking selection 유전 연산자
: 적합도에 대한 각 개체의 확률적인 재생 개체수를 구하여 선택 Ranking selection : 적합도의 크기 순서에 따라 순위를 매기고 순위에 따라 확률을 결정 적합도 6 1 10 11 17 32 4 12 5 2 기대치 0.6 0.1 1.1 1.7 3.2 0.4 1.2 0.5 0.2 재생수 3 적합도 32 17 12 11 10 6 5 4 2 1 순위 3 7 8 9 재생수

30 교배 연산자 (1/4) 두 부모의 염색체를 부분적으로 바꾸어 자식의 염색체를 생성 Single point crossover
유전 연산자 교배 연산자 (1/4) 두 부모의 염색체를 부분적으로 바꾸어 자식의 염색체를 생성 Single point crossover Two point crossover 1 1

31 교배 연산자 (2/4) Uniform crossover (균등 교차) Initialize threshold P0 ;
유전 연산자 교배 연산자 (2/4) Uniform crossover (균등 교차) 자름 선을 이용하지 않음 스키마의 결합 형태가 다양 스키마 내의 특정 기호의 위치가 거의 영향을 미치지 않음 교란의 정도가 크므로 수렴 시간이 오래 걸림 Initialize threshold P0 ; for each gene in chromosome { generate random number t ; if (t < P0) copy the gene from S1 ; else copy the gene from S2 ; }

32 교배 연산자 (3/4) S1 : a b c d e f g h i j S2 : k l m n o p q r s t
유전 연산자 교배 연산자 (3/4) 균등 교차의 예 S1 : a b c d e f g h i j S2 : k l m n o p q r s t t : P0 = 0.6 O : a l m d e f q h s t

33 유전 연산자 교배 연산자 (4/4) Arithmetic crossover (산술적 교차) 실수 표현(Value Encoding)일 경우 사용 가능 염색체의 각 위치에 대해 두 부모 염색체의 유전자의 평균값을 내어 자식 유전자로 삼는다. 매우 빠른 수렴을 보이므로, 변이 등을 적절히 조절하여 설익은 수렴이 되지 않도록 주의하여야 한다. s1 : s2 : offspring :

34 변이 연산자 (1/2) 유전자를 일정한 확률로 변화시키는 조작 개체군의 다양성 유지 cf. 유전 연산자
돌연변이가 없는 경우 초기 유전자 조합 이외의 공간을 탐색할 수 없어 초기 조합에 적절한 해가 없을 경우 원하는 해를 구할 수 없다.  local optimum 방지 1 Hill-climbing Method GA Search Method cf.

35 변이 연산자 (2/2) 부모 해에 없는 속성을 도입하여 탐색 공간을 넓힘 전형적 변이 비균등 변이 변이의 확률이 높아지면
유전 연산자 변이 연산자 (2/2) 부모 해에 없는 속성을 도입하여 탐색 공간을 넓힘 전형적 변이 난수를 발생시켜 변이 비균등 변이 초기에는 품질이 좋지 않은 해가 많으므로 변이의 강도를 높임 후반에는 변이가 강할 경우 품질 향상이 일어나지 않으므로 변이의 강도를 낮춤 변이의 확률이 높아지면 다양한 해 생성에 의해 GA의 역동성이 높아짐 수렴성이 떨어져 수행 시간이 많이 걸림 개선의 속도가 느려짐

36 대치 연산자 (1/3) 대치가 GA성능을 크게 좌우 Steady state GA : Generational GA :
유전 연산자 대치 연산자 (1/3) 대치가 GA성능을 크게 좌우 Steady state GA : 가장 성능이 낮은 해를 선택 대치하는 것이 가장 보편적 빠른 수렴 보장 설익은 수렴 가능성 Generational GA : 가장 우수한 해만을 제외한 나머지 전부 대치 (Elitism)

37 대치 연산자 (2/3) 그 이외의 것들 유전 연산자 두 부모 해 중 품질이 나쁜 해와 대치 (preselection)
해집단의 다양성 유지에 좋다 부모 해 중 하나보다 폼질이 좋을 경우 부모 해와 대치하고 그렇지 않을 경우 해집단에서 가장 나쁜 해와 대치 부모 해보다 품질이 좋을 경우 대치, 그렇지 않으면 대치 포기 수렴에 시간이 너무 오래 걸린다. 해집단 전체를 비교하여 자신과 가장 가까운 해를 대치 해집단 중 일부를 임의로 선정, 이 중 가장 닮은 해를 대치(군집 대치, crowding)

38 대치 연산자 (3/3) 대치 연산자의 선택 유전 연산자 해집단의 다양성을 합리적으로 유지시킬 수 있는 연산자의 선택이 중요
교차, 변이 연산자와 연관하여 결정 perturbation이 강할 경우 교차, 변이 연산자 쌍이 부모 해를 많이 변형시킬 경우 수렴성이 강한 대치 연산자 사용 perturbation이 약할 경우 수렴성 보다는 해집단의 다양성을 유지시키도록 하는 대치 연산자를 선택

39 알고리즘 제어 파라미터 개체군의 크기 (Population size)
How many chromosomes are in population Too few chromosome  small part of search space Too many chromosome  GA slow down Recommendation : 20-30, 교배 확률 (Probability of crossover) How often will be crossover performed Recommendation : 80% -95% 돌연변이 확률 (Probability of mutation) How often will be parts of chromosome mutated Recommendation : 0.5% - 1%

40 Questions 개체 표현 방식은 어떤 것이 좋은가? 개체군의 크기는 어느 정도로 정할까? 적합도 함수는 어떻게 정의할까?
문제를 잘 고려 하여 선택한다. 이것을 잘 선택하면 문제의 반은 푼 것이다. 개체군의 크기는 어느 정도로 정할까? 적합도 함수는 어떻게 정의할까? 선택 연산자는 무엇을 사용할까? 교배 확률을 어느 정도로 정할까? 돌연변이 확률은 어느 정도로 정할까? 대치 연산자는 어떻게 정할까? 교배 연산자와 변이 연산자를 고려하여 선택

41 일차원 vs. 다차원 많은 경우 1차원 표현 과정에서 정보의 손실이 일어남
개체 표현 방식 일차원 vs. 다차원 많은 경우 1차원 표현 과정에서 정보의 손실이 일어남 1986, Cohoon 등이 VLSI 회로 최적 재배치 문제에서 2차원 격자형 염색체 사용 2차원 배열, Tree Encoding

42 위치기반 vs. 순서기반 (1/2) 위치 기반 순서 기반 개체 표현 방식 유전자의 위치가 유전자의 속성을 결정
n번째 유전자는 n번째 속성을 결정 한 해에 대해 유일한 염색체를 갖는 장점이 있으나 유전자의 배치로 인한 한계 극복에 어려움 순서 기반 유전자 값의 상대적 순서가 의미를 가짐 동일한 해에 대해 n개의 표현이 존재 밀접한 관계를 갖는 염색체가 인접하여 교차시 생존 확률이 높음

43 개체 표현 방식 위치기반 vs. 순서기반 (2/2) 순서기반 … 위치기반 2 1 6 3 4 5 7 8 9 Traveling Salesman Problem

44 예2 : Traveling Salesman Problem

45 유전자 알고리즘의 특성 어려운 비선형 문제에서 최적 해를 찾는데 적합하다.
선로 라우팅, 적응제어, 게임놀이, 인지 모델링, 운송문제, 순회 판매원문제, 최적제어문제, … Local optima를 피해갈 능력이 있는 메커니즘을 가지고 있다. 해를 나타내는 파라미터를 염색체 형태로 코드화하여 이용한다. 점(point)이 아닌 다점(multi points) 탐색 방법이다. 탐색에 적합도 함수(fitness function)을 이용하며 blind search를 한다. 결정론적인 규칙이 없고 확률적 연산자를 사용하여 수행된다.

46 Reference 공성곤 외, 유전자 알고리즘, 그린, 1996.