[논문]외판원 문제를 위한 난수 키 표현법 기반 차분 진화 알고리즘

이상욱

doi:10.5392/jkca.2020.20.11.636

외판원 문제를 위한 난수 키 표현법 기반 차분 진화 알고리즘
Differential Evolution Algorithm based on Random Key Representation for Traveling Salesman Problems 원문보기

한국콘텐츠학회논문지 = The Journal of the Korea Contents Association, v.20 no.11, 2020년, pp.636 - 643

초록
AI-Helper

차분 진화 알고리즘은 연속적인 문제 공간인 실수 최적화 문제를 해결하기 위해 개발된 메타휴리스틱 기법 중에 하나이다. 본 연구에서는 차분 진화 알고리즘을 불연속적인 문제 공간인 외판원 문제 해결에 사용하기 위하여 차분 진화 알고리즘에 난수 키 표현법을 적용하였다. 차분 진화 알고리즘은 실수 공간을 탐색하고 오름 차순으로 정렬된 해의 인덱스의 순서를 도시 방문 순서로 하여 적합도를 구한다. TSPLIB에서 제공하는 표준 외판원 문제에 적용하여 실험한 결과 제안한 난수 키 표현법 기반 차분 진화 알고리즘이 외판원 문제 해결에 가능성을 가지고 있음을 확인하였다.

Abstract ▼ AI-Helper

The differential evolution algorithm is one of the meta-heuristic techniques developed to solve the real optimization problem, which is a continuous problem space. In this study, in order to use the differential evolution algorithm to solve the traveling salesman problem, which is a discontinuous problem space, a random key representation method is applied to the differential evolution algorithm. The differential evolution algorithm searches for a real space and uses the order of the indexes of the solutions sorted in ascending order as the order of city visits to find the fitness. As a result of experimentation by applying it to the benchmark traveling salesman problems which are provided in TSPLIB, it was confirmed that the proposed differential evolution algorithm based on the random key representation method has the potential to solve the traveling salesman problems.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 연구에서는 연속공간 탐색 기법인 차분 진화 알고리즘을 조합 최적화 문제인 외판원 문제 해결에 적용하기 위해 복잡한 연산을 추가한 기존 연구와는 달리 난수 키 표현법을 사용하여 기존의 연산만으로도 적용 가능하도록 설계한다.

가설 설정

외판원 순회 문제는 다음과 같이 그래프 이론의 용어로도 정의할 수 있다. 주어진 완전 그래프 G=(V, E)가, 연결되어 있고(connected) 가중치가 있는(weighted) 완전한(complete) 그래프라고 가정하자. 이 그래프에서 출발 정점에서 다른 모든 정점들을 방문하고 원래의 출발 정점으로 되돌아 오는 순환 경로들 중에서 가중치의 합이 최소가 되는 순환 경로를 찾는 문제가 된다.

제안 방법

burma14에서의 실험을 통해 확인한 3개의 차분 진화 알고리즘에 대한 최적의 돌연변이 변수 및 교차 확률을 사용하여 다양한 외판원 문제에 적용하여 성능을 테스트 해보았으며 그 결과는 [표 3]과 같다.
생성한 난수를 오름차순 또는 내림차순으로 정렬한다. 난수 생성 시 붙인 차원의 인덱스를 정렬한 순서대로 나열하여 해를 해석한다.
다음으로 최적의 교차 확률(CR)를 찾기 위하여 돌연변이 변수(F)를 DE1에서는 0.4, DE2와 DE3에서는 0.9의 값으로 고정시키고 교차 확률의 값을 0.1 만큼 변화시키며 [0, 1] 사이의 범위에서 실험하였다. 실험 결과는 [표 2]와 같이 3가지의 차분 진화 알고리즘에서 모두 [0.
돌연변이 및 교차 과정을 통해 생성한 자식해를 III.2에서 설명한 ‘초기해 평가’와 같은 방법을 평가하여 적합도를 구한다.
본 연구에서는 연속공간 탐색 기법인 차분 진화 알고리즘을 불연속 공간 문제인 외판원 문제에 적용하기 위하여 난수 키 기반 표현법을 사용하였다. 시행 벡터 생성 방법에 따라 3가지의 차분 진화 알고리즘을 제안하였으며 다양한 외판원 표준 문제에 적용하는 실험을 통해 성능을 검증해 보았다. 실험 결과 제안한 난수 키 기반 차분 진화 알고리즘이 외판원 문제 해결에 가능성을 가지고 있음을 확인하였다.
외판원 문제에서 난수 키 기반 차분 진화 알고리즘의 성능을 극대화할 수 있는 최적의 돌연변이 변수(F)를 찾기 위하여 교차 확률(CR)을 [0, 1] 사이의 값 중 가운데인 0.5의 값으로 고정시키고 돌연변이 변수의 값을 0.2 만큼 변화시키며 [0, 2] 사이의 범위에서 실험하였다. 실험 결과는 [표 1]과 같이 DE1에서는 돌연변이 변수의 값이 0.
해를 오름차순으로 정렬하고 난수 생성 시 붙인 차원의 인덱스를 정렬한 순서대로 나열하여 해를 해석한다. [그림 4]에서 ‘평가에 사용되는 해’를 사용하여 적합도 값을 구한다.

대상 데이터

실험에 사용한 해집단의 수는 30으로 설정하였고 최대 세대(Generation) 수는 최적의 돌연변이 변수 및 교차 확률 설정 실험(burma14 문제)에서는 1,000으로 설정하였고, 다양한 외판원 문제에 대한 성능 실험에서는 10,000으로 설정하였다. 여기서 세대수란 진화계산 알고리즘이 평가 후 돌연변이 및 교차 과정을 거처 자식해를 생성하거나 해를 업데이트하는 과정의 반복 수를 뜻한다.
실험에 사용한 외판원 문제는 TSPLIB 웹 사이트에서 Symmetric traveling salesman problem(TSP)의 표준 문제(Benchmark Problems)를 활용하였다[17]. 특히 최적의 돌연변이 변수 설정 실험에서는 표준 문제 중에서 도시 수가 가장 적어 난이도가 가장 낮은 burma14 문제를 사용하였다.

데이터처리

여기서 세대수란 진화계산 알고리즘이 평가 후 돌연변이 및 교차 과정을 거처 자식해를 생성하거나 해를 업데이트하는 과정의 반복 수를 뜻한다. 모든 실험은 10번 반복 실험하여 평균한 값을 작성하였다.

이론/모형

본 연구에서는 연속공간 탐색 기법인 차분 진화 알고리즘을 불연속 공간 문제인 외판원 문제에 적용하기 위하여 난수 키 기반 표현법을 사용하였다. 시행 벡터 생성 방법에 따라 3가지의 차분 진화 알고리즘을 제안하였으며 다양한 외판원 표준 문제에 적용하는 실험을 통해 성능을 검증해 보았다.
실험에 사용한 외판원 문제는 TSPLIB 웹 사이트에서 Symmetric traveling salesman problem(TSP)의 표준 문제(Benchmark Problems)를 활용하였다[17]. 특히 최적의 돌연변이 변수 설정 실험에서는 표준 문제 중에서 도시 수가 가장 적어 난이도가 가장 낮은 burma14 문제를 사용하였다.

성능/효과

문제의 복잡도가 올라갈수록 DE1의 성능이 가장 우수하고 DE의 성능이 가장 좋지 않은 경향을 확인할 수 있다. 이러한 경향을 보이는 이유는 문제의 복잡도가 올라갈수록 지역 최적해가 다수 존재하는데 DE3의 경우 현재 발견된 가장 우수한 해 주변만 탐색하여 수렴 속도는 빠르나 지역 최적해에서 빠져나오기 어렵기 때문인 것으로 생각된다.
시행 벡터 생성 방법에 따라 3가지의 차분 진화 알고리즘을 제안하였으며 다양한 외판원 표준 문제에 적용하는 실험을 통해 성능을 검증해 보았다. 실험 결과 제안한 난수 키 기반 차분 진화 알고리즘이 외판원 문제 해결에 가능성을 가지고 있음을 확인하였다. 이 결과를 통해 수렴성은 좋으나 연속공간 문제 해결에 국한되었던 차분 진화 알고리즘을 복잡한 연산을 추가하지 않고도 조합 최적화 문제에 적용할 수 있는 가능성을 확인하였다.
2 만큼 변화시키며 [0, 2] 사이의 범위에서 실험하였다. 실험 결과는 [표 1]과 같이 DE1에서는 돌연변이 변수의 값이 0.5 일 때, DE2와 DE2에서는 0.8 및 1.0일때 성능이 가장 우수하였다.
1 만큼 변화시키며 [0, 1] 사이의 범위에서 실험하였다. 실험 결과는 [표 2]와 같이 3가지의 차분 진화 알고리즘에서 모두 [0.5, 0.9] 사이의 값에서 성능이 가장 우수하였다.
실험 결과 제안한 난수 키 기반 차분 진화 알고리즘이 외판원 문제 해결에 가능성을 가지고 있음을 확인하였다. 이 결과를 통해 수렴성은 좋으나 연속공간 문제 해결에 국한되었던 차분 진화 알고리즘을 복잡한 연산을 추가하지 않고도 조합 최적화 문제에 적용할 수 있는 가능성을 확인하였다. 그러나 본 연구에서는 도시 수와 관계없이 동일한 평가수인 300,000회(해집단 수: 30 × 세대 수: 10,000)를 적용 하여 도시 수가 적은 문제에서는 수렴 결과를 확인하였으나 도시 수가 많아 복잡도가 높은 외판원 문제에 대해서는 수렴한 결과를 확인하지 못하였다.

후속연구

이 결과를 통해 수렴성은 좋으나 연속공간 문제 해결에 국한되었던 차분 진화 알고리즘을 복잡한 연산을 추가하지 않고도 조합 최적화 문제에 적용할 수 있는 가능성을 확인하였다. 그러나 본 연구에서는 도시 수와 관계없이 동일한 평가수인 300,000회(해집단 수: 30 × 세대 수: 10,000)를 적용 하여 도시 수가 적은 문제에서는 수렴 결과를 확인하였으나 도시 수가 많아 복잡도가 높은 외판원 문제에 대해서는 수렴한 결과를 확인하지 못하였다. 향후 연구로 도시 수가 많은 외판원 문제에 대해서는 평가의 수를 늘려 얼마만큼의 성능 향상을 할 수 있는지 확인해야할 필요가 있다.
그러나 본 연구에서는 도시 수와 관계없이 동일한 평가수인 300,000회(해집단 수: 30 × 세대 수: 10,000)를 적용 하여 도시 수가 적은 문제에서는 수렴 결과를 확인하였으나 도시 수가 많아 복잡도가 높은 외판원 문제에 대해서는 수렴한 결과를 확인하지 못하였다. 향후 연구로 도시 수가 많은 외판원 문제에 대해서는 평가의 수를 늘려 얼마만큼의 성능 향상을 할 수 있는지 확인해야할 필요가 있다.

참고문헌 (17)

P. Larranaga, C. M. H. Kuijpers, R. H. Murga, I. Inza, and S. Dizdarevic, "Genetic algorithms for the travelling salesman problem: a review of representations and operators," Artificial Intelligence Review, Vol.13, No.2, pp.129-170, 1999.
G. Finke, A. Claus, and E. Gunn, "A two-commodity network flow approach to the traveling salesman problem," Vol.41, pp.167-178, 1984.
P. Miliotis, "Using cutting planes to solve the symmetric Travelling Salesman problem," Mathematical Programming, Vol.15, No.1, pp.177-188, 1978.

상세보기
S. Lin and B. W. Kernighan, "An effective heuristic 0algorithm for the traveling-salesman problem," O0perations Research, Vol.21, pp.498-516, 1973.

상세보기
J. Kennedy, R. C. Eberhart, and Y. Shi, Swarm intelligence, morgan kaufmann publishers, Inc., San Francisco, CA, USA, 2001.
S. Kirkpatrick and G. Toulouse, "Configuration space analysis of travelling salesman problems," Le Journal de Physique, Vol.46, No.8, pp.1277-1292, 1985.

상세보기
M. Dorigo and L. M. Gambardella, "Ant colony system: a coop erative learning approach to the traveling salesman problem," IEEE Transactions on Evolutionary Computation, Vol.1, No.1, pp.53-66, 1997.

상세보기
S. Bhide, N. John, and M. R. Kabuka, "A Boolean Neural Network Approach for the Traveling Salesman Problem," IEEE Transactions on Computers, Vol.42, No.10, pp.1271-1278, 1993.

상세보기
F. Glover, "Artificial intelligence, heuristic frameworks and tabu search," Managerial and Decision Economics, Vol.11, No.5, pp.365-375, 1990.

상세보기
P. Larranaga, C. M. H. Kuijpers, R. H. Murga, I. Inza, and S. Dizdarevic, "Genetic algorithms for the travelling salesman problem: a review of representations and operators," Artificial Intelligence Review, Vol.13, No.2, pp.129-170, 1999.
A. Hussain and Y. S. Muhammad, "Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator," Computational Intelligence and Neuroscience, Vol.2017, Article ID 7430125, pp.1-7, 2017.
C. Fu, L. Zhang, X. Wang, and L. Qiao, "Solving TSP problem with improved genetic algorithm," AIP Conference Proceedings 1967, 040057, 2018.
S Saud, H Kodaz, and I Babaoglu, "Solving travelling salesman problem by using optimization algorithms," KnE Social Sciences, Vol.3, No.3, pp.17-32, 2018.
I. M. Ali, D. Essam, and K. Kasmarik, "A novel design of differential evolution for solving discrete traveling salesman problems," Swarm Evolution Computation, Vol.52, Article 100607, 2020.
R. Strorn and K. Price, "Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces," Journal of Global Optimization, Vol.11, No.4, pp.341-359, 1997.
J. C. Bean, "Genetic algorithm and random keys for sequencing and optimization," ORSA Journal on Computing, Vol.6, No.2, pp.154-160, 1994.

상세보기
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증