(1차시) 유전 알고리즘

1차시 - 권욱제 선배님의 『유전 알고리즘을 이용한 자동 주행 시뮬레이션』

사용 언어, 엔진 : c++, cocos2d

-유전 알고리즘 

머신러닝의 알고리즘 중 하나. 다윈의 적자 생존 이론을 기본 개념으로 한다. 처음 무작위 유전자들을 세대를 거듭할수록 문제 해결에 가까워질 수 있도록 해준다.

-용어 정리

1. 염색체 : 유전정보를 담고 있는 데이터 집합

2. 유전자 : 염색체를 구성하는 요소

3. 초기화 : 문제 해결을 위해 임의로 염색체를 만드는 과정

4. 선택 : 다음 세대를 생성하기 위한 염색체를 선택하는 과정

5. 교차 : 선택된 유전자들을 이용해 다음 세대 염색체를 생성하는 과정

6. 돌연변이 : 교차 과정에서 일정 확률로 유전자의 정보에 변형을 주는 과정

-학습 과정

(1) 염색체 10개를 랜덤 생성.(1세대 구성)

각 염색체는 길이가 10인 주행데이터[바퀴각도, 주행시간]로 구성

(2) 생성한 염색체로 주행 시뮬레이션 해서 각 염색체에 적합도 부여.

적합도 = 거리*시간/주행데이터

(3) 적합도가 높은 상위 10%의 염색체는 다음 세대로, 나머지 염색체 중 2개를 룰렛 휠 방식으로 선정, 교차시킴.

(2)와(3) 반복하며 문제를 해결할 수 있는 유전자 발견할 수 있다.

-교차

위의 학습과정 (3) => 염색체 2개(염색체 A, 염색체 B)를 고른다.

(1) 염색체 A에서 무작위 기준점을 지정한다. (단, 첫번째 유전자와 마지막 유전자 사이)

(2) 그 기준점에서부터 염색체 B를 이어붙인다.

(3) 염색체 길이가 10이 넘어가면, 앞의 10개만 남기고 뒤는 삭제한다.

(4) 1%확률로 돌연변이를 발생(모든 값 랜덤으로 재설정), 무한루프를 막는다.