유전 알고리즘 (Genetic Algorithm)

1. 정의

유전적 알고리즘(genetic algorithm, 약칭: GA)은 1975년에 미시간 대학의 존 H. 홀랜드(John Henry Holland)가 제안한 근사해를 탐색하는 메타휴리스틱 알고리즘이다. 컴퓨터 과학 및 운영 연구에서 유전 알고리즘은 더 큰 진화 알고리즘의 클래스 클래스 (Evolutionary algorithm, 약어 : EA)에 속하는 자연 선택의 과정에서 영감을 메타 휴리스틱. 네 가지 주요 진화 알고리즘 중 하나이며, 그 중에서도 유전 알고리즘이 가장 일반적으로 사용됩니다. 다윈의 진화론에 기초하여, 생물 돌연변이, 교차, 선택 등을 사용하여 유전 알고리즘은 최적화 및 검색 문제에 대한 고품질 솔루션을 생성하는 데 사용됩니다.

2. 알고리즘의 흐름

네 가지 주요 단계가 있습니다 :

솔루션 암호화

초기 집단 생성

유전적 수학 및 적응 평가 사용

선택에 의해 새로운 집단을 생성한다

3. 주요 요인

1. 선택

선택은 생물의 자연 도태를 모델화한 것으로, 적응도에 기초하여 개체를 늘리거나 삭제하는 조작이다. 선택의 알고리즘에는 다음과 같은 것이 있다.

룰렛 선택

룰렛 선택은 개인 i를 선택할 확률을 pi로 놓았을 때,

Pi =Fi/𝝨fk (1≤k≤N)

하는 선택 방식이다. 위의 방정식의 fi는 개인 i의 적응도를 나타냅니다. 이 방식은 홀랜드가 최초로 제안했을 때에 사용된 선택 방식이며, 가장 유명한 선택 방식이지만 적응도가 음수를 취하지 않는 것이 전제로 되어 있다. 또 적응도가 높은 것이 전제가 되어 있기 때문에 최소값을 구하는 문제에서는 사용의 적응도의 격차가 심한 경우는 적응도가 높은 개체의 선택될 확률이 매우 높아져 초기 수렴(후술)의 원인도 된다. 이 때문에, 실제로는 적응도를 스케일링한 값을 사용하는 경우가 많다.

랭킹 선택

랭킹 선택은 각 개체를 적응도에 따라 순위를 매기고, "1위라면 확률 p1, 2위라면 확률 p2, 3위라면…"라는 식으로 랭크마다 미리 확률을 결정해 두는 방식이다.

이 방법은 룰렛 선택과 달리 선택 확률이 적응도 격차에 영향을받지 않습니다. 그러나, 이것은 반대로 적응도에 별로 차이가없는 개체 사이에서도 선택 확률에 큰 차이가 발생할 가능성이 있다. 또한 개체에 순위를 매기기 위해 차세대가 갖추어질 때마다 정렬을 할 필요가 있다.

2. 교차

교차(재조합)는 생물이 교배에 의해 자손을 남기는 것을 모델화한 것으로, 개체의 유전자의 일부를 바꾸는 조작이다. 교차는 그 성격상 가장 중요한 유전적 조작이라고 할 수 있다.

3. 돌연변이

돌연변이는 생물체에서 발견되는 유전자의 돌연변이를 모델링 한 것으로, 개체의 유전자의 일부를 변화시키는 조작이다. 국소(적) 최적해에 빠지는 것을 막는 효과가 있다.
돌연변이의 확률은 0.1%~1%, 높아도 수%이다. 확률이 너무 낮으면 국소(적) 최적해에 빠지기 쉬워지고, 너무 높으면 랜덤 탐색에 접근해 버린다(해가 수렴하기 어려워진다).