유전 알고리즘: 두 판 사이의 차이

유전 알고리즘을 어떤 문제에 적용하기 위해서는 해를 [[유전자]]의 형식으로 표현할 수 있어야 하며, 이 해가 얼마나 적합한지를 [[적합도 함수]]를 통해 계산할 수 있어야 한다. 일반 생명체의 특성이 [[유전체]]의 집합인 [[유전자]]로 나타나는 것과 같이, 유전 알고리즘에서는 해의 특성을 숫자의 배열이나 문자열과 같은 자료 구조를 통해서 표시하게 된다. 적합도 함수는 이렇게 나타내어진 해가 얼마나 문제의 답으로 적합한지를 평가하기 위한 함수이다. 이는 실세계의 생명체가 유전적 특성에 따라 환경에 얼마나 잘 적응할 수 있는지가 결정되는 것과 비교할 수 있다.

어떤 문제에 대해 유전자 형식이 정의되었다면, 어떤 해들의 유전자들을 서로 조합함으로써 기존의 해로부터 새로운 해를 만들어낼 수 있다. 이런 조합 연산은 교배(Crossover)에 비유할 수 있다. 우수한 해들을 선택하여 이들을 교배하면, 만들어진 해는 우수한 해들이 가지는 특성을 물려받을 가능성이 높게 된다. 우수한 해의 선택에는 앞에서 정의한 적합도 함수를 이용할 수 있으며, 적합도가 높은 해가 선택될 확률을 높게 만들면, 보다 나은 유전자를 가진 해가 다음 세대에 자신의 유전자를 넘겨줄 확률이 높게 되고, 따라서 다음 세대의 해들은 최적해에 점차 가까워지게 된다. 또 비록 교배를 통해 후손을 남기지 못하더라도, 변이를 통해 새로운 유전자를 형성하여 다음 세대로 넘겨주도록 할 수 있으며, 이는 [[지역 최적점]]에 빠지지 않도록 하는 주요한 기법이다.

해들을 교배하기 위해서는 [[아담과 하와]]처럼 초기 해의 집단이 필요하다. 초기해 집단은 단지 이후의 해를 구하는 데 있어 필요한 초기 개체로서의 역할만을 위한 것이므로, 우수한 해들로 이루어질 필요는 없다. 일반적으로는 유전자를 랜덤하게 생성하여 초기 해 집단을 구성한다. 초기해 집단이 구성되면, 이들 내부의 해의 교배를 통해 다음 세대의 해의 집합을 생성하게 되며, 이를 세대를 거듭하면서 반복해 가면, 해들은 점점 정답에 가까워지게 된다.

해의 선택은 유전 알고리즘의 성능에 큰 영향을 미친다. 어떤 방법을 쓰느냐에 따라 최적해로 다가가는 속도가 더디게 되거나, 아니면 지역 최적해에 빠지는 경우가 생길 수도 있기 때문이다. 또는 우수한 해가 보유한 나쁜 인자가 전체 인구에 퍼지거나, 반대로 나쁜 해가 보유한 우수한 인자가 영구히 사장될 수도 있다. 따라서 어떤 해를 선택하는지는 유전 알고리즘의 성능을 위해서 중요한 요소라고 할 수 있다.

생명체는 세대 내에서의 교배를 통해 다음 세대를 생성한다. 이와 마찬가지로 유전 알고리즘에서 자연 선택된 해들은 교배를 통하여 다음 세대의 해들을 생성하게 된다. 일반적으로 두 개의 해를 선택한 후 둘 간에 교배 연산을 수행하게 되며, 이를 통해 생성된 해는 각각의 부모 해의 교차 연산을 통해서 서로 겹치지 않는 위치의 유전인자를 받아 새로운 유전자를 구성하게 된다.

실제 생명체의 염색체가 재조합되는 과정에서 부모 염색체의 일부분이 특정 위치를 기준으로 서로 바뀌어 결합되는 경우가 있는데, 이 현상을 교차라고 한다. 유전 알고리즘의 교차 연산은 이 현상을 본따, 부모 해의 유전자들을 서로 교차시켜서 자식해를 만들어낸다. 교차 연산의 실제 수행 방법은 비트 단위 교차에서부터 블록 단위 교차까지 다양한 방법으로 구현할 수 있으며, 교차를 한 번만 수행할지 전 영역에 대해서 교차시킬지 역시 결정할 수 있다.

* {{서적 인용 |저자= [[존 홀랜드]]|제목= Adaptation in Natural and Artificial Systems|발행년도연도= 1975|출판사= University of Michigan Press|id= ISBN 978-0-262-58111-0}}

* {{서적 인용 |저자= [[데이비드 골드버그]]|제목= Genetic algorithms in search, optimization and machine learning|발행년도연도= 1989|출판사= Addison Wesley|id= ISBN 978-0-201-15767-3}}

* {{서적 인용 |저자= [[데이비드 골드버그]]|제목= The Design of Innovation (Genetic Algorithms and Evolutionary Computation)|발행년도연도= 2002|출판사= Springer|id= ISBN 978-1-4020-7098-3}}

* {{서적 인용 |저자= [[멜라니 미첼]]|제목= An Introduction to Genetic Algorithms|발행년도연도= 1998|출판사= The MIT Press|id= ISBN 978-0-262-63185-3}}

* {{서적 인용 |저자= Zbigniew Michalewicz|제목= Genetic Algorithms + Data Structures = Evolution Programs|발행년도연도= 1998|출판사= Springer|id= ISBN 978-3-540-60676-5}}

* {{서적 인용 |저자= 문병로|제목= 쉽게 배우는 유전 알고리즘:진화적 접근법|발행년도연도= 2008|출판사= 한빛미디어|id= ISBN 978-89-7914-576-2}}

* {{서적 인용 |저자= 김효일, 진강규, 전승환|제목= LabVIEW로 배우는 유전 알고리즘|발행년도연도= 2012|출판사= 인피니티북스|id= ISBN 978-89-92649-80-3}}