Genetic Algorithm
- 생물학을 기반으로 하고 있다
- 문제를 chromosome을 나타내는 vector로 표현함
- 주요 연산은 Mutation과 combination
장점
- population(모집단) 기반이라서 simulatied Annealing보다 더 빠름
- 여러 selection 기법이나 mutation을 통해 자연스럽게 randomness을 갖추어서 near global optima에 가깝게 됨
- Encoding scheme과 그에 맞는 Genetic operator가 정의되어 있어서 어느 문제든 적용하기에 용이함
1. Selection
1) Rangking selection
- 평가함수의 값이 좋은 순서대로 정렬해서 상위의 몇 개만 선택함
- local optima에 위험이 있어보이지만 mutation이 있어서 randomness를 갖출 수는 있음
2) Roulette wheel selection
- 어떤 염색체가 선택될 확률은 fitness 평가값에 비례함
- 룰렛의 랜덤성으로 인해 안좋은 염색체가 선택될 여지가 있음
3) Tournament selection
- 염색체들 중 랜덤으로 두 개를 뽑아서 그 중 fitness값이 좋은 것을 선택함
- 가장 좋은 염색체랑만 붙지 않으면 안 좋은 염색체로 선택될 수 있는 가능성이 큼
2. Crossover
- single-point, multi-point, uniform crossover등의 방식이 존재함
3. Mutation
- 랜덤하게 아무 포지션이나 잡아서 숫자를 교체함
- 해공간의 다른 부분에도 탐색 기회를 주기 위한 요소
4. Insertion
- n세대에서 어떤 것을 n+1세대로 선택할 것인지에 대한 요소
- 네 가지 방식 존재
1) k세대 생존자가 아무도 없고 전부 다 새로운 염색체
2) 한 번에 한 쌍의 부모만 만들고 그들의 자식을 생성, 기존 세대 자식을 갈아끼움
3) Eilitist 전략 - 정말 우수한 부모들은 유지
4) Hall of frame
- 우수한 성질만 계속 살아남는 것을 방지하기 위해 best를 기억해두었다가 다음 자손을 생성 시 선택되지 않게 함
과정 요약
- 염색체와 염색체에 대한 Encoding scheme 정의
- 초기화 (randomness, population size etc)
- 평가함수 정의
- 부모 선택 (selection 방식에 따라)
- Genetic operator 정의 (mutation, crossover)
- parameter 튜닝
Informed search 기법과 비교했을 때
1. fitness function 기반으로 probabilistic transition rule을 사용하여 local optima에 빠질 확률이 거의 없다
2. population 기반으로 여러 point에서 searching 하기 때문에 분산시스템으로 하기 쉽고 더 빠르게 답을 찾을 수 있다
