An Adaptive Method of Mating Schemes in Genetic Algorithms

Abstract

짝짓기 제도는 자식 해를 만들기 위하여 두 부모를 선택하는 방법을 말한다. 이는 유전 알고리즘의 동작 전반에 영향을 끼친다. 본 논문에서 는,헝가리안방법을사용한짝짓기제도에대해연구하였다.그제도들은 대응되는 거리의 합을 최소화하는 방법, 최대화하는 방법, 그리고 비교를 위해 랜덤하게 대응시키는 방법들을 가리킨다. 본 논문에서는 이 제도들 을잘알려진문제인순회판매원문제와그래프분할문제에적용하였다. 또한 세대별로 가장 좋은 해가 어떻게 변화하는지 분석하였다. 이러한 분 석에 기초하여, 본 논문에서는 간단히 결합된 짝짓기 제도를 제안하였다. 제안된 제도는 결합되지 않은 제도에 비해 더 좋은 결과를 보였다. 본 논문에서는 또한, 본 논문의 핵심 방법인 짝짓기 제도를 결합하는 방법을 제안한다. 본 논문의 적응적인 짝짓기 방법은 세 헝가리안 제도 중하나를선택한다.모든짝지어진쌍은다음세대를위한짝짓기방법을 결정할 투표권을 갖게 된다. 각각의 선호도는 부모해간 거리와 부모해와 자식해의 거리의 비율을 통해 결정된다. 제안된 적응적 방법은 모든 단일 헝가리안짝짓기제도,비적응적으로결합된방법,전통적인룰렛휠선택, 기존의다른거리기준방법들보다좋은결과를보였다.제안된적응적방 법은정기적인해집단의유입과지역최적화와결합된환경에서도적절한 제도를 선택했다. 본 논문에서는 헝가리안 방법을 최대 혹은 최소의 지역 최적점을찾는방법으로교체했다.이방식역시지역최적점을찾는단일 방법들보다 좋은 결과를 보였다