Browse

An Adaptive Method of Mating Schemes in Genetic Algorithms
유전 알고리즘에서의 적응적 짝짓기 제도

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors
정찬주
Advisor
문병로
Major
공과대학 전기·컴퓨터공학부
Issue Date
2017-02
Publisher
서울대학교 대학원
Keywords
genetic algorithmselection operatormating schemesHungarian methodcombinatorial optimizationtreveling salesman problemgraph partition
Description
학위논문 (박사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2017. 2. 문병로.
Abstract
짝짓기 제도는 자식 해를 만들기 위하여 두 부모를 선택하는 방법을
말한다. 이는 유전 알고리즘의 동작 전반에 영향을 끼친다. 본 논문에서
는,헝가리안방법을사용한짝짓기제도에대해연구하였다.그제도들은
대응되는 거리의 합을 최소화하는 방법, 최대화하는 방법, 그리고 비교를
위해 랜덤하게 대응시키는 방법들을 가리킨다. 본 논문에서는 이 제도들
을잘알려진문제인순회판매원문제와그래프분할문제에적용하였다.
또한 세대별로 가장 좋은 해가 어떻게 변화하는지 분석하였다. 이러한 분
석에 기초하여, 본 논문에서는 간단히 결합된 짝짓기 제도를 제안하였다.
제안된 제도는 결합되지 않은 제도에 비해 더 좋은 결과를 보였다.
본 논문에서는 또한, 본 논문의 핵심 방법인 짝짓기 제도를 결합하는
방법을 제안한다. 본 논문의 적응적인 짝짓기 방법은 세 헝가리안 제도
중하나를선택한다.모든짝지어진쌍은다음세대를위한짝짓기방법을
결정할 투표권을 갖게 된다. 각각의 선호도는 부모해간 거리와 부모해와
자식해의 거리의 비율을 통해 결정된다. 제안된 적응적 방법은 모든 단일
헝가리안짝짓기제도,비적응적으로결합된방법,전통적인룰렛휠선택,
기존의다른거리기준방법들보다좋은결과를보였다.제안된적응적방
법은정기적인해집단의유입과지역최적화와결합된환경에서도적절한
제도를 선택했다. 본 논문에서는 헝가리안 방법을 최대 혹은 최소의 지역
최적점을찾는방법으로교체했다.이방식역시지역최적점을찾는단일
방법들보다 좋은 결과를 보였다
Language
English
URI
https://hdl.handle.net/10371/119241
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Electrical and Computer Engineering (전기·정보공학부)Theses (Ph.D. / Sc.D._전기·정보공학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse