유전 알고리즘

유전 알고리즘은 최적화 문제를 해결하는 기법의 하나로, 전역 최적화 기법이다. 생물의 진화를 모방한 기법인 진화 연산의 대표로서, 생명체에 적용되는 많은 방식을 차용하여, 변이(돌연변이), 교차(교배) 연산 등이 존재하며, 세대, 인구와 같은 용어도 사용한다.

개요

용어

• 세대 : 세대는 특정한 순간의 해의 집합을 의미한다. 각 세대의 해는 교배나 변이를 통해 다음 세대의 해를 만들어낸다. 좀더 설명하자면 해의 집합이란 어떤 문제에 대한 답의 집합이다. 예를들어 2X = 4 라는 문제가 있다면 최초의 해 집합을 무작위로 1, 4, 8 이런 식으로 만드는 것이다.

• 적합도 함수 : 위의 세대에서 부연 설명한 문제에 해당하는 것이다. 즉, 무작위로 만들어진 답을 모두 문제에 대입해보아 가장 근사하게 맞는 답들을 찾아 상위권 혹은 기타 교배 방법을 통해 교배하기 위한 채점 시스템이라 할 수 있다. 위의 설명에서 적합도 함수는 바로 2X = 4 가 적합도 함수가 되는 것이다.(함수에는 조건( = 4)도 포함됨)
• 인구 : 인구는 특정한 세대의 해의 개수를 의미한다.
• 유전 알고리즘은 유전자 알고리즘이라고도 한다. 그러나 유전 알고리즘은 유전 현상을 문제 해결이나 시뮬레이션에 이용하는 것일 뿐, 유전자의 이용에 초점을 두지 않는다. 따라서 genetic algorithm을 유전자 알고리즘으로 번역한 것은 오역이라고 볼 수 있다.

요구 조건

유전 알고리즘을 어떤 문제에 적용하기 위해서는 유전자 표기와 적합도 함수를 정의해야한다. 일반 생명체의 특성이 유전체의 집합인 유전자로 나타나는 것과 같이, 유전자 표기는 문제의 특성을 숫자나 문자열과 같은 값의 집합으로 표시하게 된다. 적합도 함수는 특정 해가 얼마나 적합한지 나타내는 함수이다. 일반 생명체가 유전자에 따라 특정 환경이나 질병에서 살아 남을 수 있는 확률이 존재하는 것과 같이, 적합도 함수는 주어진 해가 다음 세대를 생산할 수 있을지, 혹은 세대를 남기지 못하고 없어질지를 정하게 된다.

흐름

어떤 문제에 대해 유전자 표기와 적합도 함수가 정의되었다면, 문제에 대한 초기 해의 집합을 구한다. 초기 해는 좋을 필요가 없으며, 단순히 이후의 해를 구하는 데 있어 필요한 아담과 하와와 같은 초기 개체로서의 역할을 한다. 생명체가 교배를 통해 다음 세대를 생성하는 것과 마찬가지로, 초기 해의 집합 내부의 해의 교배를 통해 다음 세대의 해의 집합을 생성하게 된다. 교배시에는 적합도 함수를 이용해 적합한 유전자를 가진 개체를 찾는 과정이 있게되며, 보다 나은 유전자를 가진 해가 다음 세대에 자신의 유전자를 넘겨줄 확률이 높게 된다. 비록 교배를 통해 후손을 남기지 못하더라도, 변이를 통해 새로운 유전자를 형성하여 다음 세대로 넘겨줄 수 있으며, 변이는 지역 최적점에 빠지지 않도록 하는 주요한 기법이다.

유전 알고리즘이 전역 최적해를 구하려면, 많은 인구를 유지하면서 많은 세대를 내려갈 필요가 있다. 따라서, 대부분의 경우는 세대가 일정 수준 진행되었거나, 해가 특정 범위에 들게되면 알고리즘을 종료하게 된다.

연산

유전 알고리즘은 선택, 교차, 변이, 대치 등 몇가지 주요 연산으로 구성된다.

선택

한 세대에서 다음 세대로 전해지는 해의 후보가 되는 해들을 선택한다. 선택 방법에는 균등 비례 룰렛휠 선택, 토너먼트 선택, 순위 기반 선택 등이 있다.

선택의 문제는 중요한 문제일 수 있다. 어떤 방법을 쓰느냐에 따라 최적해로 다가가는 속도가 더디게 되거나, 아니면 지역최적화에 쉽게 빠질 수 있기 때문이다. 또한 우수한 해가 보유한 나쁜 인자가 전체 인구에 퍼질 수도 있다. 반대로 나쁜 해가 보유한 우수한 인자가 영구히 사장될 수도 있기때문이다. 때문에 선택의 문제는 곰니이 필요한 부분이라 할 수 있다. 일반적으로는 가장 좋은 해의 순으로 선택될 확률이 높게 부여하는 방법론이 많이 쓰인다고 한다. 즉 나쁜 해라 할지라도 그 해속에 포함된 좋은 인자를 퍼뜨릴 기회를 주자는 것이다. 머리도 좋고 잘생겼지만 매사 법대로 논리대로만 진행하는 사람과 머리도 그리좋지 못하고 평균적으로 떨어지지만 유대관계도 좋고 평판이 좋은 사람 누가 좋은가는 아무도 모르는 것이므로 시스템을 구현하는 사람의 의지가 짙게 깔리는 부분이라고도 할 수 있다.

교차

일반 생명체는 세대 내에서의 교배를 통해 다음 세대를 생성한다. 일반적으로 두 개의 해가 교배를 해서 다음 세대의 해를 생성하게 되며, 새로운 해는 각각의 부모 해로부터 서로 겹치지 않는 위치의 유전체를 받아 새로운 유전자를 구성하게 된다. 이때 염색체가 재조합되는 과정에서 부모 염색체의 일부분이 특정 위치를 기준으로 서로 바뀌어 결합되는 경우가 있는데 이 현상을 교차라고 한다. 유전 알고리즘에서는 이 교차 현상을 의도적으로 이용, 부모해를 교차시켜서 자식해를 만들어낸다.

변이

일반 생명체에서, 유전자의 교배 뿐 아니라, 하나의 유전자가 직접적으로 변이를 일으켜서 주어진 환경에서 살아남을 확률 역시 존재한다. 변이 연산은 주어진 해의 유전자 내의 유전체가 순서를 바꿔서 다른 유전자 표기로 되는 것이다.

대치

교차·변이 등을 거쳐서 만들어진 새로운 해를 해집단에 추가하고 기존 해 중 열등한 해를 가려내서 제외시키는 연산이다. 가장 품질이 나쁜 해를 대치하는 방법, 새로운 해의 부모해 중에서 새로운 해와 가장 비슷한 해를 대치시키는 방법(해집단의 다양성을 유지하기 위함) 등이 있다.

예

{1, 5, 6, 8, 3, 7, 3, 5, 9, 0} 중 3개를 골라서 20으로 만드는 문제가 있다고 하자. 여기서 유전체는 각 숫자이며, 유전자는 (1,5,3)와 같이 유전체 3개의 집합으로 이루어진다. 적합도 함수를 20과 얼마나 가까운지를 나타내는 값으로 둔다면, (1,5,3)에 대한 적합도는 f( (1,5,3) ) = 11이 된다.

먼저 첫 세대를 아무렇게나 생성한다. 첫 세대가 만약 { (1,5,3) (8,0,9) (9,9,8) (3,7,5) } 으로 형성되었다고 하자. 각각의 적합도를 구하면, { 11, 3, 7, 5 }이 되며, 이 값이 높을수록 20에서 멀기 때문에 해로서 부적당하다는 것을 의미하며, 따라서 세대를 거침에 따라 살아남을 확률이 낮게 된다.

다음 세대를 형성하기 위해, 이 세대의 개체중 2개의 유전자를 선택한다. 이때 선택은 적합도를 기준으로 확률적선택(룰렛 알고리즘이 자주 쓰인다)이다. 따라서 위의 예에서 (8,0,9)는 (9,9,8)에 비해 훨씬 높은 선택 기회를 가진다. 선택된 2개의 유전자의 유전체는 랜덤한 위치에서 교환되어 새로운 세대가 형성된다. 예로 (8,0,9), (9,9,8) 이 선택되었고 교배위치가 2번째 자리로 무작위로 결정되었다면 다음 세대의 개체는 (8,9,8) ,(9,0,9)로 된다.

관련 기법

• 개미 집단 최적화 (ACO): 먹이를 찾아다니는 개미 집단의 행동에서 영감을 얻은 기법이다.
• 담금질 기법 (SA): 해를 하나만 사용한다는 점이 가장 큰 차이점이다.
• 미미틱 알고리즘: 지역 탐색 기법과 유전 알고리즘을 결합하여 빠른 시간 안에 좋은 해를 찾아내려고 하는 방법이다.
• 유전 프로그래밍 교차와 변이를 사용하는 등 유전 알고리즘과 많이 닮은 기법이다. 해를 프로그램으로 표현한다는 점이 특징이다.
• 진화 연산 생물의 진화에서 영감을 얻은 기법의 총칭이다. 현재는 진화 연산에 속하는 기법들의 차이가 점점 없어지고 있다.
• 진화 전략: 교차를 사용하지 않고 변이에 의존하는 탐색 기법이다.
• 진화 프로그래밍: 변이를 주로 사용하는 기법으로 진화 전략과 유사하다. 초기에는 해를 유한 오토마타로 나타내었고 지금도 고정된 표현을 쓰지 않는 것이 특징이다.

참고문헌

• 존 홀랜드. 《Adaptation in Natural and Artificial Systems》. University of Michigan Press. ISBN 9780262581110. 
• 데이비드 골드버그. 《Genetic algorithms in search, optimization and machine learning》. Addison Wesley. ISBN 9780201157673. 
• 데이비드 골드버그. 《The Design of Innovation (Genetic Algorithms and Evolutionary Computation)》. Springer. ISBN 9781402070983. 
• 멜라니 미첼. 《An Introduction to Genetic Algorithms》. The MIT Press. ISBN 9780262631853. 
• Zbigniew Michalewicz. 《Genetic Algorithms + Data Structures = Evolution Programs》. Springer. ISBN 9783540606765. 
• 문병로. 《쉽게 배우는 유전 알고리즘:진화적 접근법》. 한빛미디어. ISBN 9788979145762.