[논문]외판원문제에 대한 유전알고리즘 성능평가

김동훈; 김종율; 조정복

외판원문제에 대한 유전알고리즘 성능평가
Performance Evaluation of Genetic Algorithm for Traveling Salesman Problem 원문보기

김동훈 (동서대학교 컴퓨터정보공학부) , 김종율 (동서대학교 컴퓨터정보공학부) , 조정복 (동서대학교 컴퓨터정보공학부)

외판원문제(Traveling Salesman problem: TSP)는 전형적인 조합최적화 문제로 위치하는 n개의 모든 지점을 오직 한번씩만 방문하는 순회경로를 결정하는 과정에서 순회비용 또는 순회거리를 최소화한다. 따라서 본 논문에서는 종래의 NP-hard문제로 널리 알려진 TSP를 해결하기 위해서 메타 휴리스틱기법 중에서 가장 널리 이용되고 있는 유전 알고리즘(Genetic Algorithm: GA)을 이용한다. 마지막으로, 유전 알고리즘을 이용해 외판원문제에 적합한 성능을 보이는 유전 연산자를 찾아내기 위해 수치 실험을 통해 그 성능에 대한 평가를 한다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 메타휴리스틱기법 중에서 가장 널리 이용되고 있는 유전 알고리즘을 이용한 유전연사자의 성능을 평가 하고자 한다. 유전 알고리즘을 이용함에 있어서 외판원문제에 적합한 성능을 보이는 유전 연산자의 조합을 찾아 내기 위해서 수치 실험을 통해 그 성능에 대한 평가를 한다

제안 방법

각각의 유전 연산자에 대한 비교를 위해 노드의 수를 일정하게 的아개로 하고 노드의 위치를 원형으로 정해 놓았다. 이 문제에서는 원형으로 이루어 졌을 때가 최적이 될 때이다.
국부적 최적해(local minimum)에 빠질 위험을 배제할 수 있다. 돌연변이 연산자로는 교환(Excahange) 연산자, 전환 (Displacement) 연산자, 삽입 (Insertion) 연산자를 사용하였다.
본 논문에서는 TSP에 대해서 유전 연산자인 순열 교차, 순서기반 교차, 위치기반 교차와 삽입 돌연변이, 전환 돌연변이, 교환 돌연변이를 이용하여 각각에 대한 성능을 비교하였다.
본 논문에서는 제안한 유전 연산자의 성능을 평가하기 위해 수치 데이터를 수집하고 TSP를 위한 각각의 교차와 돌연변이를 이용한 9가지 방법을 이용하여 비교하였다. 실험을 위해 Int 니 Pentium(TM)2 Duo CPU 2.
이는 유전 알고리즘에 있어서 새로운 해 영역을 탐색할 때, 중!! 영역의 지역탐색이라 한다. 순열 교차(Permutation Crossover) 연산자, 순서기반 교차(Order-based Crossover)연산자, 위치기반 교차(Position-based Crossover) 연산자를 교차연산자로 사용하였다.
성능을 평가 하고자 한다. 유전 알고리즘을 이용함에 있어서 외판원문제에 적합한 성능을 보이는 유전 연산자의 조합을 찾아 내기 위해서 수치 실험을 통해 그 성능에 대한 평가를 한다

데이터처리

각각의 유전 연산자에 따라 초기모집단수(Population)는 2Q0으로 하여 실험을 수행하였다. 모든 실험 데이터상에서 각 알고리즘을 10번씩 수행하였으며, 실험 결과는 수행 후 출력된 결과값에 대해 최소 세대수(Min Generation), 최대 세대수(Max Generation), 평균 세대수(Average Generation), 표준편차(STDV), 그리고 이에 대한 평균시간(Average Time)을 중심으로 나타내었고, 그 결과 데이터는 표 2와 같다. 순열 교차와 조합오로는 삽입 돌연변이가 가장 좋은 최소 세대수, 최대 세대수, 평균 세대수, 표준편차' 평균시간을 얻어 낼 수 있었다.

이론/모형

위치기반교차와 순서기반교차는 Syswerda[4]에 의해 제안 되었다. 이 교차는 임의로 몇 개의 위치를 선택하여 한 부모에서 선택된 인자의 위치와 인자값을 자손에 그대로 상속하고, 다른 부모에서 선택된 인자값을 갖는 인자들을 지우고 나타난 순서대로 미확정된 자손의 인자위치에 유전하는 교차이다.

성능/효과

산출함이 증명되었다. 따라서 1SP에 있어서 순서기반 교차와 삽입 돌연변이가 가장 적합하다는 것을 확언 할 수 있었다.
본 실험을 통해 9가지의 유전 연산자를 비교해 본 결과 순서기반 교차와 삽입 돌연변이가 다른 연산자들에 비해 가장 안정되고 최적의 비용 값을 산출함이 증명되었다. 따라서 1SP에 있어서 순서기반 교차와 삽입 돌연변이가 가장 적합하다는 것을 확언 할 수 있었다.
모든 실험 데이터상에서 각 알고리즘을 10번씩 수행하였으며, 실험 결과는 수행 후 출력된 결과값에 대해 최소 세대수(Min Generation), 최대 세대수(Max Generation), 평균 세대수(Average Generation), 표준편차(STDV), 그리고 이에 대한 평균시간(Average Time)을 중심으로 나타내었고, 그 결과 데이터는 표 2와 같다. 순열 교차와 조합오로는 삽입 돌연변이가 가장 좋은 최소 세대수, 최대 세대수, 평균 세대수, 표준편차' 평균시간을 얻어 낼 수 있었다. 순서기반교차와의 조합으로는 삽입 돌연변이가 가장 좋은 최소 세대수, 최대 세대수, 평균 세대수, 표준편차, 평균시간을 얻어 낼 수 있었다* 마지막으로 위치기반 교차와 전환 돌연변이의 조합으로는 최소 세대수와 최소 세대수가 가장 좋게 나왔고, 삽입 돌연변이와의 조합으로는 평균 세대수, 표준편차, 평균시간이 가장 좋은 값을 얻을 수 있었다
위치기반 교차는 전환 돌연변이와 조합 했을경우, 최소 세대수와 최소 세대수가 가장 좋게 나왔고’ 삽입 돌연변이와 조합 했을 경우, 평균 세대수' 표준편차, 평균시간이 가장 좋은 값을 얻을 수 있었다

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

외판원문제에 대한 유전알고리즘 성능평가
Performance Evaluation of Genetic Algorithm for Traveling Salesman Problem 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

데이터처리

이론/모형

성능/효과

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

외판원문제에 대한 유전알고리즘 성능평가 Performance Evaluation of Genetic Algorithm for Traveling Salesman Problem 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

데이터처리

이론/모형

성능/효과

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

외판원문제에 대한 유전알고리즘 성능평가
Performance Evaluation of Genetic Algorithm for Traveling Salesman Problem 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper