제 4 장 유전자 알고리즘 (Genetic Algorithm)

Presentation on theme: "제 4 장 유전자 알고리즘 (Genetic Algorithm)"— Presentation transcript:

1 제 4 장 유전자 알고리즘 (Genetic Algorithm)
Slide 1 (of 25)

2 Genetic Algorithm 1975년 미국 미시간 대학의 John Holland 교수가 세포의 작용 을 연구하던 중 제안한 것으로, 생물학계의 적자생존 원리 즉, 자연도태 원리를 기초로 한 최적화 알고리즘. 생물의 유전과 진화알고리즘을 공학적으로 모델화하여 문제해 결이나 시스템의 학습등에 응용하려는 알고리즘 어떤 세대(generation)을 형성하는 개체( individual)들의 집합, 즉 개체군(population)중에서 환경에 대한 적합도(fitness)가 높은 개체가 높은 확률로 살아 남아 재생(reproduction)할 수 있게 되며 이때 교배(crossover) 및 돌연변이(mutation)로서 다 음 세대의 개체군을 형성하게 되는 생물의 진화과정을 인공적 으로 모델링한 알고리즘 진화적 알고리즘(evolutionary algorithm)이라고도 함 2000년대 붐을 일으키고 있으며, Job shop scheduling, 훈련신 경회로망, 이미지 특징 추출 및 인식, 최적화 문제등에 응용 Slide 2 (of 25)

3 진화적 알고리즘의 흐름 진화적 알고리즘(Evolutionary Algorithm, EA) 흐름
유전자 알고리즘(Genetic Algorithm, GA) 협의의 알고리즘으로 고정길이의 이진 스트링 염색체 사용 유전자 프로그래밍(Genetic Programming, GP) 그래프와 트리 등을 염색체 표현에 사용, 90년대 개발 진화적 프로그래밍(Evolutionary Programming, EP) 진화적 전략(Evolutionary Strategy, ES) 실수의 값을 갖는 염색체 사용 Slide 3 (of 25)

4 진화적 알고리즘 종류 비교 Slide 4 (of 25) 진화적 전략(ES) 진화적 프로그래밍(EP) 유전자 알고리즘(GA)
진화적 전략(ES) 진화적 프로그래밍(EP) 유전자 알고리즘(GA) 유젼자 프로그래밍(GP) 기원 Rechenberg, I.(1963) Fogel, L.J. Holland, J.H.(1975) Koza, J.(1990) 표현 방식 실수. 길이 고정 실수, 이산치. 크기 고정 이진 문자열 실수형도 가능(0/1). 기본함수. 크기가변 자기 적응성 표준편차와 상호분산 표준편차(메타-진화프로그래밍의 경우) 없음(메타-유전자 알고리즘의 경우는 가능) 적합도 목적함수 값 비율에 의해 조정된 목적함수 값 문제표현 벡터 그래프 스트링 트리 돌연변이 주요 연산자 유일한 연산자 보조 연산자 교배 자기-적응성에 중요 없음 선택 결정론적이며 소멸성있음 승자승 원리를 통한 확률적 선택 소멸성 있음 확률적이지만 보존성이 있음 특징 및 응용분야 종에 속한 개체의 수준에서 진화를 모방한 것으로 다양한 교배 과정이 있을 수 있음. 실수치 탐색 종의 수준에서 진화를 모방한 것으로 교배 과정이 없음. 오토마타 합성 종에 속한 개체의 수준에서 진화를 모방한 것으로 다양한 교배과정이 있을 수 있음. 자연 진화원리에 가장 가까움. 문자열 벡터열 탐색 프로그램 합성 Slide 4 (of 25)

5 생물학과 GA 용어비교 <염색체, 유전자, 유전자자리> Slide 5 (of 25) 생물학 유전자 알고리즘(GA)
개체(individual) 염색체에 의해 특징지어지는 자율적인 하나의 작은 집단 집단 (population) 집단 내의 개체의 수 유전자(gene) 개체의 형질을 규정하는 기본 구성요소 즉, 특성(feature), 형질(character) 등 염색체 (chromosome) 복수의 유전자 모임. 문자열(string)로 표현 대립 유전자(allele) 유전자가 갖는 특성 값(feature value). 유전자 자리(locus) 염색체상의 유전자의 위치 즉, 문자열의 위치 (string position) 적합도 또는 적응도(fitness) 유전자의 각 개체의 환경에 대한 적합의 비율을 평가하는 값 즉, 평가치로 최적화 문제를 대상으로 하는 경우 목적함수 값이나 제약조건을 고려하여 페널티 함수 값의 적응도로 설정된다. 코딩(coding) 표현 디코딩에서 유전자형으로 매핑하는 것 디코딩 (decoding) 유전자 형에서 표현형으로 역 매핑하는 것 유전자형 (genotype) 형질의 염색체에 의한 내부적으로 표현하는 방법으로 구조체(structure)로 표현 표현형 (phenotype) 염색체에 의해 규정된 형질을 외부적으로 표현하는 방법으로 파라메터 집합(parameter set), 대체해(alternative solution),디코드화를 위한 구조체(decoded structure)로 표현 염색체 유전자 유전자 자리 <염색체, 유전자, 유전자자리> Slide 5 (of 25)

6 GA Background 스키마(schema) 정해진 스트링 위치에 같은 비트값을 가진 가능한 스트링들의 부분집합
개체중에 부분적 유전자좌에 주목하여 *(don't care simbol)로 표현하여 개체를 평가하는 방법을 부여하는 수학적 도구 (예)1*01, 000*, *1**, 0101 : 스키마 4개의 비트를 가진 H = 1**0 인 스키마: 첫 번째 자리에 1의 값을 그리고 4번째 자리에 0의 값을 가지는 모든 스트링을 나타냄. H = 1**0 = {1000, 1010, 1100, 1110} 인스턴스(instance) :스키마에 의해 표현되는 각각의 스트링 위에서 1000, 1010 등은 스키마 1**0의 인스턴스들이다 고정위치(pixed position) :스키마에서 0 또는 1의 값을 가진 유전자의 위치 스키마의 차수(order : o(H)) :고정위치의 개수 스키마의 길이(defining length : δ(H)) 가장 왼쪽 고정위치와 가장 오른쪽 고정위치 사이의 길이 (예) 스키마 H = *10**0* 가 있을 때 o(H) = 3, δ(H) = 4 가 된다 Slide 6 (of 25)

7 Implicit Parallelism Slide 7 (of 25)

8 GA 프로세스 시 작 선택(selection) : 집단 중에서 적응도의 분포에 따라서 다음의 단계로 교배를 행하는 개체의 생존 분포를 결정한다. 적응도의 분포에 기초하고 있기 때문에 적응도가 높은 개체일수록 보다 많은 자손을 남기기 쉽게 된다.   b) 교배(crossover) : 2개의 염색체 사이에서 유전자를 바꾸어 넣어 새로운 개체를 발생시킨다.   c) 돌연변이(mutation) : 유전자의 어떤 부분의 값을 강제적으로 변화시킨다. 단계1: 유전자 형들의 결정 단계2: 초기 유전자 집단의 결정 단계3: 각 개체의 적합도와 평가기준을 만족하는가? 예 아니오 단계4: 선택(도태와 증식)의 실행 종 료 단계5:교배의 실행 Slide 8 (of 25) 단계6: 돌연변이의 실행

9 Characteristics 파라메터를 코딩한 것을 직접이용
점(point)이 아닌 다점(multi points, : 군(population)) 탐색 방 법 탐색에 비용 정보(fitness function)를 이용하며, blind search 수행(미분값이나 다른 부가적인 지식을 요구하지 않음) 결정론적인 규칙이 없고 확률적 연산자를 사용하여 수행됨 다른 탐색방법이나 최적화 방법 보다 효율적 Slide 9 (of 25)

10 GA의 구성요소 개체 풀고자 하는 문제의 변수값을 binary string으로 표현 표현법 다양
(예) 변수 x1, x2인 경우 각각 4 bit, 7 bit로 표현한다면 x1 = 0100=> 6(20-5)/(24-1) +5=11 x2 = => 89( )/(27-1)-10=11.37 (예) TSP 문제인 경우 ( )으로 표현: 숫자는 도시의 위치 각 유전자의 비트에 의미를 두고 디코딩시 해석함 Slide 10 (of 25)

11 선택메커니즘(Fitness Function)
목적 함수(objective function) 즉, 최적화 하고자 하는 함수는 각 개체의 적합도를 평가하는 기반이 된다. 목적함수의 값의 범위는 문제마다 다르기 때문에 보통 정해진 구간 사이 의 양수값을 갖도록 표준화된 값을 사용한다. 즉, 표준화하기 이전의 적 합도의 값을 raw fitness라고 하며 표준화되어서 실제로 개체 선택의 기 준이 되는 함수를 적합도 함수 (fitness function)라고 한다. 집단 중 다음 단계로 교배를 수행하는 개체의 생존분포를 결정하는 것을 의미한다. raw fitness를 표준화(또는 스케일링)하는 방법 선형 표준화(linear scaling) σ절단(σ truncation) :계산된 적합도의 표준편차를 고려하는 방법 거듭제곱 표준화(power law scaling) Slide 11 (of 25)

12 선택 메커니즘 종류 자연선택(natural selection)현상을 모델링하여 잘 적응한 해들 은 살아남고 잘 적응하지 못한 해들은 도태되도록 유도한다. 방법 기본 모델 : 적합도 비례 선택(proportionate selection), 룰렛 선택법(roulette selection) 각 개체 si 의 적합도 f(si)(＞0), i = 1, …, N 의 총합을 구해, 각 개체 si의 선택 확률을 와 같이 정하는 방법 엘리트 보존 선택(elitist preserving selection) 확률에 따라 개체를 선택하여 교배 및 돌연변이의 결과로 특별히 좋은 해가 소실되는 것을 막기 위해 가장 좋은 해를 보존하여 다음 세대에 남기는 방법 일반적으로 다른 선택 방법과 융합하여 사용가능 Slide 12 (of 25)

13 선택 메커니즘(cont.) 기대치 선택법(expected-value selection)
적합도 비례선택의 문제점은 개체군의 크기가 크지 않을 경우에 적합도가 정확히 반영되지 않을 가능성이 있다. 이런 문제점의 대안으로 제안된 것이 기대치 선택법이다. 적합도에 대한 각 개체의 확률적인 재생 개체수를 구하여 선택하는 것이 기본적인 방법이다 순위 선택법(ranking selection) 적합도의 크기 순서에 따라 순위를 매긴 후 순위에 따라 다음세대에 자손을 남길 확률을 결정하는 방법 토너먼트 선택법(tournament selection) 개체군 중에서 일정한 개수의 개체를 임의로 선택하여 그 중에 최고의 적합도를 가지는 개체를 다음 세대에 남기는 방법(토너먼트 방식). 다음 세대의 개체수가 모두 찰 때까지 반복적으로 계속 수행 기타 GENITOR 알고리즘 등 Slide 13 (of 25)

14 GA 기본연산: Crossover 교배(crossover) :교배는 2개의 개체간에 염색체를 부분적으로 서로 바꿈으로써 새로운 개체를 생성하는 것이다. 이 때 부모의 형질이 자손에게 적절히 계승되어야 하며 이것을 형질 유전성 (character preservingness) 또는 교배 근접(crossover neighborhood)이라 한다. ① 단순 교배(simple crossover) ② 복수점 교배(multipoint crossover) : 교배점이 2개 이상 Slide 14 (of 25)

15 GA Operators(cont.) ③ 균일 교배(uniform crossover): 마스크에 의한 교배
④ 부분 일치 교배(partially matched crossover : PMX) ⑤ 순서 교배(ordered crossover : OX) ⑥ 주기 교배(cycle crossover : CX) → C' = → C' = D' = Slide 15 (of 25)

16 GA Operator: Mutation 개체의 각 유전자자리의 유전자에 대하여 일정한 돌연변이 확 률(pm) 을 적용하여 대립 유전자의 값으로 바꾸는 것 개체에 근접한 새로운 개체를 생성하는 국소적인 랜덤 탐색의 일종 또한 집단에서 잃어버린 유전형질을 복구하여 다양성을 유지 하기 위한 수단으로도 사용됨. 이때 전형적인 돌연변이 확률은 0.05이하 (예) 세 번째 비트인 a3 가 A3 로 바뀌었음 Slide 16 (of 25)

17 Other GA Operators 치환(displacement): 염색체의 일부분을 다른 염색체의 일부분 으로 대치하는 방법
역위(inversion) : 두 개의 역위점을 구하여 그 사이의 비트들의 순서를 반대로 바꾼다 중복(duplication) :염색체상의 코드의 일부분을 중복시킨다. 추가(addition) :염색체상에 어떤 길이의 부분 문자열을 삽입시 킨다. 이 결과 염색체의 길이가 길어지게 된다. 제거(deletion) : 염색체상에 어떤 길이의 부분 문자열을 제거시 킨다. 이 결과 염색체의 길이가 짧아지게 된다. Slide 17 (of 25)

18 GA의 장단점, 응용분야 장점 단점 응용분야 복수개의 개체사이의 상호협력에 의한 해의 탐색이 가능함
번거로운 미분연산이 불필요함 단점 대상으로 하는 문제를 GA로 표현하는 방법상의 어려움발생 개체수, 선택 메카니즘, 교배법 결정, 돌연변이 비율 등 선택해야 할 파라메터 수가 많다. 응용분야 최적화, 자동 프로그래밍, 기계학습, 경제학, 면역체계, 생태학, 집단유전학, 진화와 학습, 사회적 시스템 등 많은 과학 및 공학 문제의 모델링에 사용되어 왔으며 앞으로도 사용 가능함 Slide 18 (of 25)

19 GA Example:TSP problem
정의: n개의 도시와 도시 사이의 거리가 주어졌을 때, 어떤 도시에서 시작하여 모든 도시를 단 한번만 방문하고 원래의 출발지로 되돌아오는 최단 길이의 여행을 찾는 문제 도시들의 가능한 방문의 모든 순열이 주어질 때 각 도시와 다음 도시와의 Euclidean distance의 합이 최소가 되는 여행을 선택하는 것 탐색공간 = {T1, T2, …, Tn!}= n!(크기) 120 1 4 1: 대전 2: 광주 3: 부산 4: 서울 97 140 176 203 Slide 19 (of 25) 2 3 197 <4개 도시사이의 직선거리>

20 å TSP D = ( x - x ) 2 + ( y - y ) 2 T1 = 1-2-3-4 D1=555
……. T24 = D24 = 555 최단경로는 T1=T6=T8=T10=T15=T17=T19=T24=555 Euclidian Distance n å D = ( x - x ) 2 + ( y - y ) 2 j j - 1 j j - 1 j = 1 Slide 20 (of 25)

21 GA의 다른 응용문제 단순한 함수의 최적화 문제 등반과 시뮬레이티드 어닐링
Holland의 ESCAPE BRITTLENESS 문제 죄수의 딜레마 반복적 죄수의 딜레마 Slide 21 (of 25)

22 진화적 전략(ES) 다수개체로 구성된 집단 개념을 도입함으로써 랜덤 교배, 돌연변이와 선택이라는 진화 원리를 사용할 수 있도록 한 전략 진화적 전략은 개체의 평가방법 외에는 문제에 대한 정보를 거의 필요 로 하지 않기 때문에 거의 모든 종류의 최적화 문제에 적용할 수 있다. 선형 및 비선형 제약조건을 갖는 고차원, 멀티모달의 비선형 문제를 해결할 수 있다. 진화적 전략의 알고리즘 [1단계 초기화 ] 부모벡터의 초기화된 개체집단 Xi(i=1, …, μ)는 실행범위로부터 랜덤하게 선 택된다. [2단계 돌연변이] 자손벡터 Xi(j=1, …, μ)는 각각의 Xi의 구성에 대한 Gaussian의 랜덤인 변화 를 기하는 것에 의해 각각의 부모 Xi로 부터 만들어진다. [3단계  평가] Xi와 Xj의 적합도를 평가한다 [4단계 선택] 다음세대의 새로운 부모를 그들의 적응도로 기초한 개체집단으로부터 선택 한다. [5단계 반복]     단계2)로 부터 (단계4)까지를 해가 수렴할 때까지 반복한다 Slide 22 (of 25)

23 진화적 프로그래밍(EP) 유전자 연산자로써 교배연산을 사용하지 않고, 돌연변이에 사 용되는 표준편차값을 돌연변이 시키는 메타 진화 프로그래밍 을 사용함으로써 해가 최적한 값에 도달하도록 조절하는 프로 그래밍 방법 진화적 프로그래밍의 알고리즘 [단계 1] 초기 집단을 임의의 값으로 초기화한다. 집단에서 개체 (해) 의 숫자는 최적화 속도에 큰 영향을 주지만, 집단 크기를 얼마로 해야 적당하지에 대한 답은 없다. [단계 2] 개체는 새로운 집단으로 복제되고, 이 개체가 돌연변이 된다. 돌연변이의 강도는 부모 개체에 할당된 변화 요구에 의존한다. 메타- 진화프로그래밍에서는 목적변수의 돌연변이에 앞서 표준편차를 먼저 돌연변이 해야 한다. 돌연변이 연산자로는 표준 정규분포 돌연변이, 로그정규분포 돌연변이, 평균 돌연변이 및 자기-적응성을 갖는 평균 돌연변이 가운데 하나를 사용한다. [단계 3] 자식 개체는 적합도 평가를 받고, 확률적인 승자승 선택을 사 용하여 다음 세대 집단을 구성한다 Slide 23 (of 25)

24 유전자 프로그래밍(GP) 컴퓨터가 인간에 의해 프로그램 되지 않은 상태에서 스스로 문제해결 을 위한 프로그램을 자동 생성할 수 있도록 한 프로그래밍 전략 유전자 알고리즘에 근본을 두고있으나, 차이점은 유전자 프로그래밍 이 프로그램으로 해석되는 동적인 트리 구조를 진화시키는데 있다. 즉, 유전자 알고리즘의 출력이 정량적인데 비해 유전자 프로그래밍의 출 력은 컴퓨터 프로그램이다. GP를 정의하려면 프로그램을 구성할 원시함수와 터미널 집합의 정의 가 필요. 가장 구현하기 어렵고 중요한 개념은 적합도 함수이다. GP에서 가장 중요한 연산자는 교배연산이다.(예제 1, 2, 3 참조) GP활용분야 최적해 분야, 자동 컴퓨터 프로그래밍 분야(로봇, 제어 등), 모델링, 예측, 데이터마이닝 등… Slide 24 (of 25)

25 유전자 프로그래밍 문제풀이과정 Slide 25 (of 25) 적합도에 의해 두 개체 선택
특정 가능성에 의한 교환 연산 아키텍처 선택 교환연산 아키텍처 수행 새로운 집단에 개체 삽입 돌연변이 연산 수행 새로운 집단에 돌연변이 개체 삽입 교배 연산 수행 Run:=0 Gen:=0 Run에 대한 초기 랜덤 집단(population) 생성 END Run:=N? Run := Run + 1 Run을 만족시키는 조건 종료 Run에 대한 결과 i := 0 집단내의 각 개체에 적합도 적용 i := M? No Yes i := i + 1 Gen := Gen + 1 유전자 연산방법 선택 적합도에 의해 한 개체 선택 생식 연산 수행 새로운 집단으로 복사 Pr Pc Pm Pa Slide 25 (of 25)