순열 기반 조합 최적화를 위한 지역 탐색의 이웃해 생성 전략
Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization
1
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
지역 탐색은 다양한 조합 최적화 문제들을 해결하기 위해 활용되어 왔다. 지역 탐색에 있어서가장 중요한 요소 중 하나가 이웃해를 생성하는 방법이다. 본 논문에서는 순열 기반 조합 최적화를 위한 지역 탐색의 이웃해 생성 전략들을 제안하고, 순회 외판원 문제를 대상으로 각 전략들의성능을 비교한다. 본 논문에서는 총 10가지 이웃해 생성 전략을 제안한다. 기본적으로 기존에 많이 사용했던 Swap 등 4가지 전략 이외에 Rotation 등 4가지 기법을 새롭게 제안한다. 이외에 기본이웃해 생성 전략들을 결합하여 만든 Combined1과 Combined2가 있다. 실험은 기본적인 지역 탐색을 적용하되 이웃해 생성 전략만 변경하여 수행하였다. 실험 결과, 이웃해 생성 전략에 따라 성능차이가 큰 것을 확인하였으며 아울러 Combined2의 성능이 가장 좋음을 확인하였다. 뿐만 아니라Combined2는 기존의 지역 탐색 기법들보다 더 좋은 성능을 발휘함을 확인하였다.
Abstract
Local search has been used to solve various combinatorial optimization problems. One of the most important factors in local search is the method of generating a neighbor solution. In this paper, we propose neighbor generation strategies of local search for permutation-based combinatorial optimization, and compare the performance of each strategies targeting the traveling salesman problem. In this paper, we propose a total of 10 neighbor generation strategies. Basically, we propose 4 new strategies such as Rotation in addition to the 4 strategies such as Swap which have been widely used in the past. In addition, there are Combined1 and Combined2, which are made by combining basic neighbor generation strategies. The experiment was performed by applying the basic local search, but changing only the neighbor generation strategy. As a result of the experiment, it was confirmed that the performance difference is large according to the neighbor generation strategy, and also confirmed that the performance of Combined2 is the best. In addition, it was confirmed that Combined2 shows better performance than the existing local search methods.
참고문헌 (12)
- J. Ceberio, "A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems", Progress in Artificial Intelligence, 1(1), pp.103~117 (2012)
- M. Baghel, "Survey of metaheuristic algorithms for combinatorial optimization", International Journal of Computer Applications, 58(19), pp.21~31 (2012)
- D. Abramson, "Simulated annealing cooling schedules for the school timetabling problem", Asia-Pacific Journal of Operational Research, 16, pp.1~22 (1999)
- R. Khairuddin, "A comparison of simulated annealing cooling strategies for redesigning a warehouse network problem", Journal of Physics: Conference Series, 1366(1), pp.012078~ (2019)
- V. K. Prajapati, "Tabu search algorithm(TSA) : A comprehensive survey", Proceedings of 3rd International Conference on Emerging Technologies in Computer Engineering : Machine Learning and Internet of Things(ICETCE), pp.1~8 (2020)
- A. Panghal, "A comparative study of searching and optimization techniques in artificial intelligence", International Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), 6(3), pp.72~80 (2020)
- A. Hussain, "Genetic algorithm for traveling salesman Problem with modified cycle crossover operator", Computational Intelligence and Neuroscience, 2017, pp.7430125~ (2017)
- G. Laporte, "The traveling salesman problem : An overview of exact and approximate algorithms", European Journal of Operational Research, 59(2), pp.231~247 (1992)
- R. Purkayastha, "Study and analysis of various heuristic algorithms for solving travelling salesman problem—A Survey", Proceedings of the Global AI Congress 2019, pp.61~70 (2020)
- M. A. Rahman, "Repetitive nearest neighbor based simulated annealing search optimization algorithm for traveling salesman problem", Open Access Library Journal, 8(6), pp.e7520~ (2021)
- S. Hore, "Improving variable neighborhood search to solve the traveling salesman problem", Applied Soft Computing, 68, pp.83~91 (2018)
- "TSPLIB"[URL]