[인공지능] Genetic Algorithm

박민주·2021년 10월 27일
0

Genetic Algorithm

  • 생물학을 기반으로 하고 있다
  • 문제를 chromosome을 나타내는 vector로 표현함
  • 주요 연산은 Mutation과 combination

장점

  1. population(모집단) 기반이라서 simulatied Annealing보다 더 빠름
  2. 여러 selection 기법이나 mutation을 통해 자연스럽게 randomness을 갖추어서 near global optima에 가깝게 됨
  3. 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를 기억해두었다가 다음 자손을 생성 시 선택되지 않게 함

과정 요약

  1. 염색체와 염색체에 대한 Encoding scheme 정의
  2. 초기화 (randomness, population size etc)
  3. 평가함수 정의
  4. 부모 선택 (selection 방식에 따라)
  5. Genetic operator 정의 (mutation, crossover)
  6. parameter 튜닝

Informed search 기법과 비교했을 때
1. fitness function 기반으로 probabilistic transition rule을 사용하여 local optima에 빠질 확률이 거의 없다
2. population 기반으로 여러 point에서 searching 하기 때문에 분산시스템으로 하기 쉽고 더 빠르게 답을 찾을 수 있다

profile
Game Programmer

0개의 댓글