📂최적화이론

유전 알고리즘에서 엘리트주의

정의 ^{1 2}

유전 알고리즘에서 엘리트주의^elitism란 자연선택이 일어나는 매 세대마다 가장 적합도가 높은 개체 몇 개를 다음 세대로 무조건 넘기는 전략을 말한다.

설명

엘리트주의는 자연선택에서 말하는 랭크 선택^{rank selection}을 극단화 했다고 볼 수 있으며, 확률적 요소 없이 조건을 만족한 일부 개체를 다음 세대로 넘기는 절삭선택^{truncation selection}의 다른 이름이라고 볼 수도 있다. 엘리트주의를 채택한 유전 알고리즘에서 세대에 따른 목적함수의 개형은 단조함수의 꼴이 된다.

의외로 최적화 문제에서 ‘역사상 가장 뛰어났던’ 해를 잃어버리는 것은 흔한 일이며, 이것은 심지어 경사하강법에서도 마찬가지다. 가령 학습 중에 꽤 빠른 타이밍에 가장 좋은 해를 얻었는데, 에포크를 끝까지 가져가자 오버피팅이 일어나면서 막상 마지막 해는 그보다 못한 경우가 그렇다. 물론 보통은 체크포인트를 두어 가장 좋은 해를 저장해두는 식으로 피할 수 있는 문제다.

한편 유전 알고리즘에서 엘리트주의는 체크포인트로써 계속 전승될 뿐만이 아니라 진화의 과정에서 해집합에 계속해서 영향을 미치는 점이 다르다. 아무래도 자식 세대는 엘리트 부모를 닮아 비슷한 유전형을 가지며, 사실 자식들도 높은 적합도를 가질 확률이 높아 그 다음 세대로도 그 유전자가 계속 전해질 가능성이 크기 때문이다. 개체군 메서드의 관점으로 보면 국소최적해 근방을 조금 더 꼼꼼하게 탐색하겠다는 의도로 볼 수 있다.