[note] 유전 알고리즘
0. 유전 알고리즘을 정리한 글이다.
1. 개요
자연계 생물 유전학에 기본이론을 둔다.
병렬적이고 전역적 탐색 알고리즘이다.
다윈의 적자생존 이론을 기본 개념으로 한다.
문제에 대한 가능한 해들을 자료구조로 표현하고 이 해를 점차적으로 변형시켜 더 좋은 해를 만든다. (자료구조 = 유전자) (변형 = 진화)
2. 요구조건
문제의 해를 유전자 형식으로 표현할 수 있어야 한다.
해의 적합성을 판단할 수 있어야 한다.
3. 흐름
해를 유전자 형식으로 표현했다면, 해들을 조합함으로써 기존의 해로부터 새로운 해를 만든다. (이를 교배라 하자.)
해의 적합성 판단으로 우수한 해들을 교배한다. 여기서 나온 결과 해는 우수한 특성을 물려받을 가능성이 높다. 이를 반복하면 최적해에 가까워 진다.
변이를 통해서도 우수한 특성이 생길 수 있다. 변이는 지역 최저점에 빠지지 않기 위한 중요한 기법이다.
교배 및 변이를 위해 초기 해 집단이 필요하다. 초기 해 집단은 우수한 해로 이루어질 필요는 없으며 랜덤으로 생성하여 초기해 집단을 구성한다.
유전알고리즘이 전역 최적해를 구하려면 많은 인구를 유지하면서 많은 세대를 내려가야 한다. 알고리즘을 종료하기 위해서는 해의 목표값을 정하거나 세대 진행의 목표값을 정하고 진행해야 한다.
4. 연산
선택, 교차, 변이, 대치등의 연산으로 구성됨
4_1. 선택
다음세대로 전해지는 해의 후보를 선택한다.
선택 방법에는 균등비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택이 있다.
해의 선택은 유전 알고리즘 성능에 큰 영향을 미치며, 방법에 따라서 최적해로 가는 속도가 더니거나 지역 최적해에 빠질수도 있다. 혹은 나쁜 인자가 전체 인구에 퍼지거나 좋은 해가 사장될 수도 있다.
일반적으로 지역 최적해 순으로 선택될 확률을 높이는 방법이 있다.
최적해가 어디에 있는지 알 수 없기 때문에 평균 적합도를 높이면서 유전자의 다양성을 유지하는 것이 전역최적해에 빠지는 것을 가능한 방지하는 방법이다.
4_2. 교차
생명체는 세대내에서의 교배를 통해 다음 세대를 생성한다.
두 해의 교배 연산은 서로 겹치지 않는 위치의 유전 인자를 받아 새로운 유전자 즉 해를 구성한다. 교차 연산의 실제 수행 방법은 비트 단위 교체에서부터 블럭단위 교차 연산까지 다양하게 구현 가능하다.
교차연산시 인자의 우수성을 잃을 확률도 있기 때문에 교차에 확률을 부여하여 우수한 해가 다음 세대로 전해질 확률을 높이는 방법도 있다.
4_3. 변이
변이 연산은 주어진 해의 유전자 내 인자의 순서 혹은 값자체가 변경되어 해가 변형되는 연산이다.
약간의 확률로 변이 연산을 수행하면 전체 세대가 함께 지역 최적해에 빠져드는 것을 방지하고 해집단의 다양성을 높여준다.
4_4. 대치
교차, 변이등을 거쳐 만들어진 새로운 해를 해집단에 추가하고 기존 해중 열등한 해를 가려내서 제외시키는 연산.
부모해 중 새로운 해와 가장 비슷한 해를 대치 시키는 방법
5. 참조
https://ko.wikipedia.org/wiki/%EC%9C%A0%EC%A0%84_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
댓글
댓글 쓰기