Chap. 9 Genetic Algorithms

Presentation on theme: "Chap. 9 Genetic Algorithms"— Presentation transcript:

1 Chap. 9 Genetic Algorithms
유전 알고리즘 김정집

2 GA(Genetic Algorithms)란?
자연계의 유전 현상을 모방하여 적합한 가설을 얻어내는 방법 특성 진화는 자연계에서 성공적이고 정교한 적응 방법이다. 부분별로 모델하기 힘든 복잡한 문제에도 적용 가능하다. 병렬화 가능하고 ,H/W의 성능에 도움을 받을 수 있다.

3 GA 대량의 탐색공간에서 최적의 fitness의 해를 찾는 일적인 최적화 과정

4 GA에서 쓰이는 용어 Fitness-산술적인 단위로 가설의 적합도를 표시한다. Population-가설들의 집합
Evaluate-모든 population에 대해 fitness값을 구한다.

5 기본적인 GA

6 가설의 표현 Bit-string(다른 표현도 있음) Outlook={Sunny,Overcast,Rain},
Wind={String,Weak} Outlook Wind IF Wind=Strong THEN PlayTennis = yes Outlook Wind PlayTennins

7 유전 연산자 교차(crossover) 돌연변이(mutation)
single-point,two-point,uniform crossover 돌연변이(mutation) point mutation

8 유전 연산자(2)

9 적합도 함수와 선택 적합도 함수(fitness function) 선택(selection)
다음 세대까지 존재 가능한 정도를 표시 분류 정확도, 규칙의 복잡도, 규칙의 일반성 선택(selection) fitness proportionate selection(roulette wheel selection) tournament selection p-> 승자, (1-p)-> 패자,다양성 ranking selection

10 GABIL Concept learning에 GA를 사용한 예(De Jong) table 9.1. 과 동일한 과정
learn boolean concepts represented by a distinctive set of propositional rules breast cancer diagnosis판별 문제 table 9.1. 과 동일한 과정 r=0.6 m= p=100~1000 정확도:92.1% 다른 방법(91.2%~96.6%)

11 GABIL(2) 가설 표현 돌연변이 교차-표현 구조가 깨지지 않도록 교정 적합도 함수

12 GABIL(3)

13 GABIL의 확장(1) AddAlternative DropCondition 효과
어떤 attribute의 bit에서 0을 1로 바꿈 p=0.01 DropCondition 어떤 attribute를 1로 채움 p=0.60 효과 정확도 95.2%(이전 92.1%)

14 GABIL의 확장(2) Bit-string의 확장 효과 AA:AddAlternative 허가
DC:DropCondition 허가 효과 성능 향상은 없었으나, 흥미로운 현상을 보였다.

15 가설 공간 탐색 다른 탐색 방법과의 비교 crowding local minima에 빠질 확률이 적다.(급격한 움직임 가능)
유사한 개체들이 개체군의 다수를 점유하는 현상 다양성을 감소시킨다.

16 Crowding Crowding의 해결법 선택방법을 바꾼다. “fitness sharing” 결합하는 개체들을 제한
Tournament selection,ranking selection “fitness sharing” 유사한 개체가 많으면 fitness를 감소시킨다. 결합하는 개체들을 제한 가장 비슷한 개체끼리 결합 개체들을 부분적으로 분포시키고 근처의 것끼리만 결합가능하게 함

17 Schema Theorem Schema any string composed of 0s, 1s, and *’s
*->don’t care : 00**, 0*10, ***, etc m(s,t) : 시간 t에서 스키마 s에 속하는 원소수 f(h) : bit string h의 적합도 값 : 시간 t에서 평균 적합도 값 : 시간 t에서 스키마 s의 평균 적합도 E[m(s,t+1)] : 시간 t+1에서 m의 기대값

18 Schema Theorem-(2) 선택과정

19 Schema Theorem-(3) 교차와 돌연변이를 고려한 경우 o(s) : defined bits(0,1)의 수
d(s) : 가장 왼쪽과 오른쪽 defined bit사이의 거리 l : bit string의 길이 o(s),d(s)가 작고 적합도값이 큰 스키마가 증가

20 GP(Genetic Programming)
개체는 bit string이 아닌 컴퓨터 프로그램으로 표시된다. 프로그램의 표현 프로그램의 parse tree 예)

21 GP-(2) 교차 subtree의 교환

22 GP-(3) Fitness Koza의 방법 training set에 대한 실행 결과 10%의 개체는 다음 세대로 전달.
현재 개체끼리 교차해서 나머지 수를 채움. 돌연변이는 사용하지 않음.

23 GP의 예제(Koza) 최초의 배치에 관계없이 단어 ‘universal’을 순서대로 만드는 문제
한번에 한 개의 블록만 이동 가능. 최상위 블록만이 탁자에 내려갈 수 있다. 혼자 놓여진 것만이 최상위 블록 위로 올라갈 수 있다.

24 GP의 예제-(2) 인자(단말 노드) CS(current stack) TB(top correct block)
스택의 최상위 원소, 없으면 F TB(top correct block) 아래 쪽이 정확한 배열이 된 최상위 블록의 이름 NN(next necessary) TB위로 올라가야 하는 블록의 이름,없으면 F

25 GP의 예제-(3) 기본 함수(비단말 노드) (MS x) : x가 탁자에 있으면 스택위로 올림
(MT x) : x가 스택에 있으면 스택의 최상위 원소를 탁자로 내림 (EQ x y):x가 y와 같으면 T를 되돌려 줌 (NOT x):x가 F이면 T를 되돌려 줌 (DU x y):y가 T가 되는 동안 x를 실행

26 GP의 예제-(4) 결과 10세대 만에 모든 training set을 만족하는 프로그램을 찾음 첫번째 DU 두번째 DU
(EQ (DU (MT CS) (NOT CS)) (DU (MS NN) (NOT NN)) ) 첫번째 DU 모든 스택을 비움 두번째 DU 순서대로 스택을 쌓음

27 GP의 확장 전자회로 구성문제에 적용 GP의 성능은 개체 표현과 적합도 함수의 선택에 의존한다.
10% 유지, 89% 교차로 생성, 1% 돌연변이로 생성 137세대 만에 원하는 명세와 유사한 결과를 얻음 GP의 성능은 개체 표현과 적합도 함수의 선택에 의존한다.

28 진화와 학습의 모델 자연계 생물학적,사회적인 과정 Lamarckian Evolution Baldwin Effect
개체는 일생동안 적응을 한다. 생물학적,사회적인 과정 종은 많은 세대동안에 변화한다. Lamarckian Evolution Baldwin Effect

29 Lamarckian Evolution 개체가 얻은 경험을 자식에게 유전한다. 생물학적으로 부정됨 GA에서 효율향상이 있음

30 Baldwin Effect 개체의 학습이 유전되지는 않지만 진화의 방향을 바꾼다.
변화하는 환경에서는 학습 능력이 뛰어난 개체가 선택되는 경향이 있다. 유전적으로 뛰어나게 최적화된 것 보다는 학습능력이 뛰어난 개체가 적응을 잘한다. 학습을 잘 하는 개체는 유전자의 오류에 덜 영향을 받는다. 개체의 학습능력은 진화속도를 증가시킨다.

31 Baldwin Effect-ANN에 응용
‘lifetime’동안 weight가 변하지 않는 것과 훈련가능 한 것과의 비교 초기 세대:훈련 가능한 것이 다수 유전적으로 fixed, correct network weights를 가진 것이 증가

32 병렬 유전 알고리즘(PGA) Coarse grain approach Fine-grained approach
전체 개체들이 부분 개체군(demes)에 나뉘어 존재 migration : deme 사이에서 개체 교환 crowding 감소 Fine-grained approach 1프로세서에 1개체 인접하는 개체 사이에 유전자 조합 여러 인접방법 : planar ,torus