:적자생존을 모방하여 나온 최적의 해(정답이 아닌)를 찾는 알고리즘
배경
(Exhaustive Search)따져봐야하는 경우의 수가 매우 많을 때, 이에 관한 정답을 찾는 것은 실질적으로 불가능하다.
(Local Search)경우의 수를 일부분만 가져와서 따져 본다면, 효율적인 연산이 가능하겠지만 이는 Optimal solution과는 거리가 멀다.
Meta-Heuristic Approach
복잡한 문제를 효율적으로 trials and error함으로써 푸는 접근법.
Algorithm Loop
Initiation
염색체를 Chromosome이라고 부르고 이 염색체를 구성하는 요소를 gene이라고 부른다.
- Parameter Initialization
- Population: 한 세대에서 생성할 Chromosome의 개수
- Fitness Function: 생성한 Chromosome의 quality를 평가
- Crossover mechanism: Chromosome간의 교배 방식
- The rate of mutation: Mutation시킬 확률
- Stopping criteria: 종료 조건
Chromosome에 대한 gene의 값을 생성해야한다. (보통 randomly)
Fitness Evaluation
Chromosome에게 해당 알고리즘의 목적에 따른 점수를 부여한다.
그 점수들에 따른 Chromosome의 순위를 매긴다.
그리고 동시에 (각 Chromosome의Fitness Score / Sum of Chromosome)의 값을 weight로 부여한다. 이 weight는 Crossover에서 사용될 중요한 지표이다.
Selection
우수한 Chromosome을 선택하여, 다음 세대의 부모로 사용한다.
- Deterministic Selection: 상위 N%의 Chromosome만을 선택한다. 하위는 다 폐기한다.
- Probabilistic Selection: 모든 Chromosome에게 Fitness Evaluation에서 계산한 weight만큼의 확률기회를 제공한다. 그리고 random하게 0~1사이의 소수값를 생성하여 이 중에서 Chromosome을 선택한다. 이때 선택되는 개수는… It depends on.
Crossover (Reproduction)
두 개의 Chromosomes의 gene을 서로 섞어서 자녀 생성.
Crossover points: Crossover points의 개수에 따라서 자녀가 가지게 되는 Chromosome의 내용이 달라진다. 최대 개수는 gene의 총 개수이다.
- Example with 1 crossover point.
- Example with 2 crossover point.
- Example with the number of maximum gene.
랜덤 넘버를 생성하여 0.5기준으로 그 이상인 것만 Flip하여 적용.
Mutation
현재의 solution이 Local optima에 빠질 수 있음을 방지하는 방법.
Mutation rate가 너무 높으면 수렴하는 시간이 많이 증가한다.
Find the Best Solution
위와 같은 스탭을 계속해서 반복하다보면 어느 시점에서 Stopping criteria를 만족하게 되고 최적의 해를 가진 chromosome을 선택하게 된다.
이때, 위와 같은 스탭을 밟을 때 흔히 쓰는 약간의 안전장치가 있다.
Loop형식으로 계속해서 알고리즘을 돌 때, Top1 & Top2 Chromosome은 Crossover&Mutation을 시키지 않고 그대로 후대에 물려준다. 이러한 방식은, 후대에서 부모를 이길 수 있는 Fitness가 없을 수 있음을 방지하고 만약 등장할 시에 이 자리를 물려줄 수 있는 장치가 되는 것이다.
