Python Algorithm Chapter5
Python Algorithm
5 유전 알고리즘
5.1 생물학적 배경
한정된 자원과 환경에서 유기체는 세대를 거듭할수록 더 잘 적응한 개체만이 살아남는다. 이것을 자연 선택이라고 한다. 유전적 돌연변이가 생존에 더 잘 적응한다면 돌연변이의 개체수가 증가한다.
유전 알고리즘은 염색체 개체들의 집단이 문제 해결을 위해 경쟁한다. 그 기준은 적합도 함수가 된다.
세대를 거치며 적합한 염색체는 재생산에서 선택될 가능성이 크다. 세대마다 두개의 염색체가 유전자를 합칠수도 있다. 이것이 크로스 오버이다. 염색체가 랜덤하게 변이 될 수도 있다.
세대를 거칠 때 설정한 만족도를 넘는 염색체가 존재하거나, 지정된 최대 세대 수를 거치면 가장 적합한 개체를 반환한다.
유전 알고리즘이 항상 좋은 해결책이아니다. 확률적으로 이루어지기 때문이다.(선택, 크로스오버, 돌연변이) 빠른 결정론적 알고리즘이 존재하지 않을 때 좋다.
5.2 제네릭 유전 알고리즘
염색체 추상 클래스의 필수 기능
- 자체 적합도 결정
- 무작위로 첫 세대 유전자로 인스턴스 생성
- 크로스오버 구현
- 돌연변이 구현
유전자 알고리즘 단계
- 1세대 무작위 염색체 초기 모집단 생성
- 1세대 각 염색체 적합도 측정 ( 임곗값 초과가 있다면 이것을 반환하고 종료)
- 개체 재생산을 위한 가장 높은 적합도 개체 선택
- 다음 세대 자식 생성을 위해 일정확률로 선택한 염색체 크로스오버
- 낮은 확률로 돌연변이 발생. 이것이 새로운 세대이며 앞의 세대를 대체한다.
- 임곗값 초과가 없다면 2단계로 반복
생성, 측정, 선택, 크로스오버, 돌연변이
룰렛휠 선택과 토너먼트 선택
-
룰렛휠 선택 : 적합도 비례 선택
-
토너먼트 선택 : 가장 높은 적합도 개체 선택
시딩 : 1세대 염색체 구성시 사전 지식으로 무작위가 아닌 솔루션에 가까운 염색체 포함
5.3 간단한 방정식
특정 방정식의 최댓값이 되는 x와 y의 값을 유전 알고리즘으로 구해볼 수 있다.
5.4 SEND+MORE=MONEY 다시보기
3장 제약 만족 프레임워크에서 본 문제를 유전 알고리즘을 통해 해결해 볼 수 있다.
5.5 최적화 리스트 압축
궁극적인 해결책에 실제로 최적인지 모를 때 최적의 솔루션을 찾으려고 할때 유전 알고리즘이 적합할 수 있다.