Genetic Algorithm

전역 최적화 기법의 일종으로 최적화 문제를 다룸

풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 낸다. 여기에서 해들을 나타내는 자료구조는 유전자, 이들을 변형함으로써 더 좋은 해를 만들어 내는 과정은 진화로 표현한다.

GA의 요구 조건 : 유전 알고리즘을 어떤 문제에 적용하기 위해서는 해를 유전자의 형식으로 표현할 수 있어야 하며, 이 해가 얼마나 적합한지에 대해 적합도 함수를 통해 계산되어야 한다.

해의 표현 형식 : 숫자(numeric), 문자(characteristic)열 형식으로 표현

교배(Crossover) : 정의된 유전자 형식을 조합함으로써 기존의 해로부터 새로운 해를 만들어 내는 과정. 이 때, 우수한 해(적합도가 높음)가 선택될 확률을 높임으로서 최적해에 가까워지도록 한다.

초기해 집단 : 교배를 위해서 필수적인 요건임.

연산 : 선택, 교차, 변이, 대치 등

선택 : 균등 비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등이 있으며 실제 전역 최적해가 어디에 있는지 알 수 없는 일이므로 가능한 해들의 평균적인 적합도를 높여가면서도 유전자의 다양성을 유지하는 것이 지역 최적해가 도출되는 것을 방지할 수 있는 방법이다.

교차 : 일반적으로 두 개의 해를 선택한 후 둘 간에 교배 연산을 수행하게 됨. 모든 해에 대해 교차연산을 수행할 경우 우수한 해가 다른 해와의 교배를 통해서 우수성을 잃어버릴 수 있으므로 이런 경우를 방지하기 위하여 교차를 확률적으로 수행하여 우수한 해가 변형되지 않고 그대로 다음 세대에 전해질 확률을 부여하는 방법도 사용

변이 : 해의 유전자들을 가상의 공간에 맵핑할 경우 교배 연산은 부모해들 사이의 어떤 지점에 자식해를 생성하는 것이라고 볼 수 있다면, 변이 연산은 임의의 위치로 점프하는 것에 비견할 수 있다. 따라서 약간의 확률로 변이 연산을 수행시켜 주는 것은 전체 세대가 함께 지역 최적해에 빠져드는 경우를 방지하는 주요한 기법이며 해집단의 다양성을 높여준다.

대치 : 가장 품질이 나쁜 해를 대치하는 방법, 새로운 해의 부모해 중에서 새로운 해와 가장 비슷한 해를 대치시키는 방법 등