應用混合式基因演算法求解旅行銷售員問題

A Hybrid Genetic Algorithm for the Traveling Salesman Problem

謝明志(Ming-Chih Hsieh)

指導教授 ： 林志浩

中原大學/商學院/資訊管理研究所/碩士(2009年)

https://doi.org/10.6840/cycu200900499

摘要

摘 要

旅行銷售員問題（Traveling Salesman Problem，TSP）為典型的組合最佳化問題之一。自西元1930年以來，它便吸引許多不同領域的學者投入研究，然而旅行銷售員問題已被證明是NP-Complete問題，因此如何發展出在有限時間內能找出全域最佳解的方法，便是研究學者的最大挑戰。本研究針對旅行銷售員問題這類典型的計算難題嘗試找尋更穩定且更有效率的解題方式，本研究的主要目的在於研發改良式基因演算法，以找到旅行銷售員問題的最短路徑。
基因演算法是一種高階的萬用啟發式方法，具有跳脫區域最佳解的能力，專門用來解決組合最佳化的問題，能在一合理的時間內求得一近似或最佳解。本研究提出一種創新的基因交換機制應用於基因演算法，並透過演算流程整合鄰域搜尋法，以期能有效應用於求解旅行銷售員問題的研究上，使其兩者達到更完善的搜尋效果與求解品質。本研究利用基因演算法進行對整個解空間的探尋，並利用LKH（Lin-Kernighan Helsgaun）局部最佳化演算法，對解空間中的較小區域進行搜尋，做局部最佳化的處理，以加速求解的收斂速度，充分利用並結合基因演算法及LKH演算法兩者的優點。
實驗結果中得知，使用旅行銷售員問題國際標竿例題中，節點數目由48到3038的例題，測試結果十分令人滿意，10個測試例題中，有8個例題可以在每次執行後找到最佳解，最大的例題為2152個節點，也證明了GA-LKH在旅行銷售員問題上的解題能力。本研究搜尋方法相較於目前表現較佳的LKH演算法，及其它旅行銷售員問題求解方法相比，有相當不錯的求解品質與效能表現。經由實驗結果證明，GA-LKH搜尋法能夠更集中搜尋的力量以提升求解速度，此外也藉由LKH加入演化流程，有效連結了全域搜尋與區域搜尋的合作機制，使其兩者相輔相成達到更完善的搜尋效果與求解品質。

關鍵字

基因演算法 ； 啟發式演算法 ； LKH ； 旅行銷售員問題

並列摘要

Abstract

Traveling salesman problem(TSP) is a well-known NP-hard problem which can not be solved within a polynomial bounded computation time. It has been shown to be NP-complete, and is an often-used benchmark for new optimization techniques. Genetic algorithm(GA) is a familiar heuristic algorithm to obtain near-optimal solutions within reasonable time for TSPs.

In this paper we proposed a new algorithm based on crossover operator and use Lin-Kernighan Helsgaun(LKH) local search algorithm hybrid genetic algorithm(GA-LKH), to exploit local optimal tour segments and enhance the searching process in order to reduce the execution time and improve the quality of the offspring. GA-LKH is an effective heuristic for this problem. This paper presents an algorithm that uses GA in combination with a variation of the LKH local optimization algorithm to solve the TSP.

The GA-LKH is an effective algorithm for solving TSPs. The method combines a GA with a local tour improvement heuristic. Our experiment proves that this method provides expert-level solutions for traveling salesman problems. If the case is not focused on the optimal solution, the GA-LKH can provide good near-optimal solutions rapidly. Results from a computational experiment show that the proposed technique outperforms the conventional genetic heuristic procedures, providing good solutions more quickly.

並列關鍵字

Genetic Algorithm ； Local Search Optimization ； Traveling Salesman Problem ； Lin-Kemighan

參考文獻

28. 李捷隆，分散式基因演算法應用於旅行家銷售員問題，中原大學資訊工程研究所碩士論文，民國92年。

1. Carter, A.E., Ragsdale, C.T., “A new approach to solving the multiple traveling salesperson problem using genetic algorithms” European Journal of Operational Research, vol. 175, pp. 246-257, 2006.

2. Chatterjee, S., Carrera, C., Lynch, L.A., “Genetic algorithms and traveling salesman problems” European Journal of Operational Research, vol. 93, pp. 490-510, 1996.

4. Daoxiong, G., Xiaogang, R., “A hybrid approach of GA and ACO for TSP” Fifth World Congress on Intelligent Control and Automation (WCICA), vol. 3, pp. 2068-2072, 2004.

5. Fischer, T., Merz, P., “A distributed chained Lin-Kernighan algorithm for TSP problems” Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05), vol. 1, pp. 1-10, 2005.