Genetic Algorithm (GA)
유전 알고리즘
- 자연세계의 진화과정(돌연변이, 교배 연산 등)을 기초로 한 전역 최적해 계산 모델로,
최적화 문제를 해결하는 Metaheuristic Algorithm 중 하나이다.
- 자연계의 생물 유전학과 다윈의 적자생존에 기본 이론을 두며, 병렬적이고 전역적인 탐색 알고리즘이다.
- 비선형 또는 계산 불가능한 복잡한 문제를 해결하는 데 널리 응용되고 있다.
- Neural Network(NN) 개념이 대두되기 전까지 가장 주목받던 알고리즘이며,
NN이 나온 이후에도 딥러닝에서의 초깃값을 설정할 때 사용되는 등 아직도 중요한 역할을 담당하고 있다.
* Neural Network Overview (신경망 개요) (URL)
[Artificial Intelligence] Neural Network Overview | 신경망 개요
Neural Network Overview (NN Overview) 신경망 개요 * Neural Network = Artificial Neural Network = NN - Neural Network(신경망)이란, 인간 두뇌의 생물학적 뉴런의 작용('학습'과 '인지')을 모방하여 여러 뉴런들로부터 들
dad-rock.tistory.com
Operations (연산)
- 유전 알고리즘은 아래와 같은 주요 연산들로 구성된다:
- Initialize (초기화)
- Selection (선택)
- Crossover (교차)
- Mutation (변이)
- Replace (대치)
- 위 연산들을 반복하다가 아래와 같은 기준들을 만족시키면 유전 알고리즘을 종료한다:
- Minimum Criteria를 만족한 경우
- 기준 세대에 도달한 경우
- 기준 예산을 소진한 경우 (Computation Time 또는 Money 등)
- Iteration을 계속 수행해도 더 이상 나은 해를 도출하지 못하는 경우
- 수기 수정이 필요한 경우
Initialize Operation (초기화 연산)
- 유전 알고리즘에서는 해결하고자 하는 해를 유전자로 표현한다.
- 초기화 연산은 랜덤하게 구성된 초기 유전자(초기해)를 적당한 개수만큼 준비하는 연산이다.
- 초기해 집단은 이후의 해를 구하는 데 있어 필요한 초기 개체로서의 역할만을 위한 것으로,
우수한 해들로 이루어질 필요는 없다.
- 초기해 집단에 대한 교차 연산을 통해 다음 세대의 해의 집합이 생성되며,
이들 중 우수한 해들을 선택 연산하고 다시금 교차 연산을 수행하는 것을 반복하며
해들은 점점 전역 최적해에 근접하게 된다.
Selection Operation (선택 연산)
- 다음 세대로 전달할 해들을 일정 기준에 의거하여 선택하는 연산이다.
- 일반적으로, 가장 좋은 해의 순으로 선택될 확률을 높게 부여하는 방법이 사용된다.
- 나쁜 해라 할지라도 그 해에 포함된 좋은 인자를 퍼뜨릴 기회를 부여하며,
무조건적으로 배제하지 않음으로써 유전자의 다양성을 유지한다.
Crossover Operation (교차 연산)
- 일반적으로 두 개의 해를 선택한 후 둘 간의 교차(교배) 연산을 수행하게 되는데,
이를 통해 생성된 해는 각각의 부모 해의 유전인자를 받아 새로운 유전자를 구성한 해이다.
- 교차 연산의 실제 수행 방법은 비트 단위 교차에서 블록 단위 교차까지 다양하게 구현될 수 있으며,
교차를 한 번만 수행할 지 전 영역에 대해 수행할 지에 대한 여부 역시 다양하게 결정할 수 있다.
- 모든 해에 대해 교차연산을 수행할 경우, 우수한 해가 다른 해와의 교배를 통해 우수성이 희석될 수 있는데,
이를 방지하기 위해 확률적으로 교차연산을 수행하여 우수해가 온전히 다음 세대로 전해질 확률을 높이는 방법도 존재한다.
Mutation Operation (변이 연산)
- 유전자 내의 유전 인자의 순서 혹은 값을 임의로 변경하여 다른 해로 변형하는 연산이다.
- 전체 세대가 함께 지역 최적해에 빠져드는 경우를 방지하기 위한 주요 기법이며, 해집단의 다양성을 높여준다.
Replace Operation (대치 연산)
- 교차・변이 연산을 거쳐 만들어진 새로운 해를 해집단에 추가하고,
기존 해 중 열등한 해를 가려내어 제외시키는 연산이다.
- 해의 품질은 Fitness Function(적합도 함수)를 통해 가려낸다.
- 가장 품질이 나쁜 해를 대치하거나, 새로운 해의 부모해 중에서 새로운 해와 가장 비슷한 해를 대치시키는 방법 등이 있다.
