유전 알고리즘 (Genetic Algorithm) 컴퓨터학부 원동건

가설 공간 ...... 결정트리, 유전알고리즘 같은 기계학습 방법론들의 목표 문제를 해결하는데 필요한, 가능성 있는 가설 후보군들의 집합 문제: “오늘 운동을 할 것인가?” 가설 A : 오늘 비가 안 오면 운동을 할 것이다. 가설 B : 오늘 저녁으로 고기를 먹으면 운동을 할 것이다. ...... 가설 N : 오늘 X 를 하면 운동을 할 것이다. 가설 X : 오늘 데이터마이닝 수업을 들으면 운동을 할 것이다. 결정트리, 유전알고리즘 같은 기계학습 방법론들의 목표 최적의 가설 집합 서로 연관될 수도 있는 가설들

탐색 알고리즘 최적의 해를 찾는 방법론 유전학(Genetics)에 기반 병렬적, 전역적 진화론 유전자와 변이(mutation) Beam search 유전학(Genetics)에 기반 진화론 적자생존 유전자와 변이(mutation) 세대(population) 개념 변이의 방법도 여러가지

유전(Genetic) 생명  번식 적자생존: 주어진 환경에 적합한 개체가 생존 유전자 시스템 (DNA) 환경 -> 목표 적합 -> 평가 생존 개체 -> 최적의 해 유전자 시스템 (DNA) ATGC로 이뤄진 분자 서열 형질에 대한 정보를 저장

알고리즘 방향성? 변화와 조합 (진화의 방법) 가장 좋은 특성을 가장 먼저 고려 General to specific? / Simple to complex? 변화와 조합 (진화의 방법) 적자(최적의 해)가 생존 후 번식 세대가 지날수록 집단이 강화됨 가장 좋은 특성을 가장 먼저 고려 일종의 Beam search

근거 생명체에서, 적응을 위한 성공적인 방법 가설공간에서, 복잡한 경우에 유리함 구현할 때, 병렬화하기에 좋음 강건함 가설공간에서, 복잡한 경우에 유리함 서로 영향을 끼치는 가설들 영향력을 측정하기 힘든 경우 구현할 때, 병렬화하기에 좋음 하드웨어 성능에 크게 영향 받지 않음 로봇 조종, 위상기하학 최적화 문제, 인공신경망 파라미터 학습 진화 연산이라고 불리는, 조합을 통한 프로그래밍 기법에서 가장 인기 있는 유전 알고리즘

과정 초기화 처음 가설 집합, 무작위 선택 적합도 함수 교차 (Crossover) 변이 (Mutation) 세대 이동 반복

유전 알고리즘 다양한 적용 특징 어떻게 선택하는가 어떻게 평가하는가 반복적으로 업데이트 되는 가설 집합 적합도 검정 함수로 평가 가장 적합한 구성원을 확률론적으로 선택 일부는 다음세대로 선택된 구성원을 변이 교차 & 변이 다양한 적용 어떻게 선택하는가 어떻게 평가하는가

가설의 유전자화 생명체의 유전자 알고리즘에서의 유전자 GATCGTTCGGTCCC Bit string Play tennis 예시 날씨 = 100 (태양, 구름, 비) 바람 = 10 (강함, 약함) 테니스 = 10 (yes, no) 111 10 11 같은 경우 (encoding이 중요) 혹은 평가함수에서 낮은 점수를 줘버리면 된다. Bit string이 아니라 기호를 사용하는 경우도 있음. 뒤에서 더 설명

Genetic Operator 새로운 세대의 가설 생성 교차 교차 (Crossover) 변이 (Mutation) 생물학적 진화에서 따옴 교차 2명의 부모로부터 2명의 자손 생성 각 부모의 일부분을 조합 Crossover mask (bit 연산) Single point, Two point, Uniform 등

Genetic Operator (2) 변이 (Mutation) 그 외의 operator Bit 1개를 무작위로 선택 Point mutation 교차 이후에 진행 그 외의 operator Grefenstette et al. (1991) Janikow (1993) Rule specified operator

적합도 (Fitness) 현재 세대의 가설들을 평가 평가기준 이후 세대를 선택하는 기준 다음 세대에 포함될 가설들을 선택 Accuracy for classification Performance for robot control 이후 세대를 선택하는 기준 Fitness proportionate selection (roulette wheel selection) Pr ℎ 𝑖 = 𝐹𝑖𝑡𝑛𝑒𝑠𝑠( ℎ 𝑖 ) 𝑗=1 𝑝 𝐹𝑖𝑡𝑛𝑒𝑠𝑠( ℎ 𝑖 ) 토너먼트 선택, 랭크선택등의 방법도 있다.

1111 (2) 예시

1111 (2) 예시

가설 공간 탐색 무작위 빔 서치 Crowding problem 최대의 적합도를 갖는 가설 탐색 Abrupt 한 방법 따라서 local minima에 빠질 확률이 적다 Crowding problem 다양성의 감소 선택 방법 토너먼트, rank selection 적합도 처리 Clustering 독특하다 모두 유전학에서 아이디어 얻은 방법들

유전 프로그래밍 Genetic programing (GP) Parse tree Bit 배열 대신 program을 구성원으로 Function  node Argument  자식 node

블록 쌓기 문제 MS MT EQ Not Du (EQ(DU(MT CS)(NOT CS)) (Du (MS NN)(Not NN)))

유전 프로그래밍의 적용 Designing electronic filter circuit Inserting or deleting circuit 다양한 input 상황에서 error율로 평가 한 세대 640,000개 circuit 10% 선택, 89% 교차, 1% 변이 64 node 병렬 프로세서 137 세대에서 최적의 해 Classifying segments of protein

병렬 유전 알고리즘 Coarse grain approach Fine grain approach Grouping individual Demes Communication, cross-fertilization Migration Reduce crowding problem Fine grain approach One processor per one individual

볼드윈 효과 – 진화와 학습 적응과 진화 Neural network Lamarckian evolution Baldwin Effect 학습능력이 뛰어나면, 진화는 가속화된다. 더 높은 다양성을 갖출 기회 Neural network Learning individual 빠른 적합도 향상

References Melanie Mitchell, “An introduction to genetic algorithms”, A Bradford Book, 1998. Tom M. Mitchell, “Machine learning”, chap 9 Genetic Algorithm, Carnegie Mellon university. 게임에 적용한 유전 알고리즘, http://gall.dcinside.com/board/view/?id=hearthstone&no=1100005, Dcinside 하스스톤 갤러리, 고2때 하스스톤으로 진화론 연구했던 썰