改良適應性粒子群演算法求解TSP問題

An effective PSO-based algorithm for the traveling-salesman problem

蕭碧芬(Pi-Fen Hsiao)

指導教授 ： 張翠蘋

共同指導教授 ： 張志忠(Jhih-Chung Chang)

嶺東科技大學/資訊學院/資訊科技應用研究所/碩士(2013年)

摘要

本篇論文主要以粒子群演算法(Particle Swarm Optimization，PSO)為基礎，提出的新的解決旅行推銷員TSP問題之方法為「潮汐法」。由於TSP已被證明為NP-Hard問題，因此，運用傳統PSO演算法，經常容易陷入區域解無法跳脫。本研究主要針對旅行路徑城市節點如何進行分解與重組其旅行順序，意即將所有城市節點打散後，並以我們所提出的方法重組後，以最佳解可能性的機率高低類似潮汐的變化做為路徑組合依據，並在PSO的演算過程中引用基因演算法的突變概念，使得演算法具有較大幅度跳脫區域解的能力，可改善PSO對於廣域搜尋能力的不足，此演算模式我們稱為(Modify Adaptive Particle Swarm Optimization，MAPSO)。本研究主要貢獻為利用傳統PSO結合基因演算法的突變機制以利跳脫區域解，並以較快速度達到最佳解。
本研究以TSPLIB國際標竿例題[7]進行實驗，發現經由我們所提出的MAPSO可以擁有良好的求解效能。MAPSO可以改善傳統PSO演算法在廣域搜尋能力上明顯優於傳統的GA演算法。MAPSO針對100個城市節點以內進行實驗時，平均可在100個世代(回合)內求得已知最佳解或更優解，某些題目在100世代的實驗中，平均求解的回合數低於10回合。此外在經反覆地實驗後，求得最佳解或更優解的成功率達100%，證明本研究所提出之演算模型不僅具有求解精確的能力，也具有相當優良的穩定性。

關鍵字

粒子群演算法 ； 旅行推銷員問題

並列摘要

The article Primarily based on Particle Swarm Optimization to raise new solution of solving Traveling Salesman Problem(TSP);that is “Tidal Method”. Due to the TSP has been proved as a NP-Hard issue, therefore, applying conventional PSO would frequently causing pbest unable to escape. The research mainly focus on how traveling paths and urban nodes carrying out the decomposition and restructure of travel sequences, which meaning by scattering urban nodes and basing of methods we raised to conduct restructure, using optimal solutions’ odds, similar to tidal changes, as basis of path combinations. Afterwards, in process of PSO, applying the mutations of Genetic Algorithm concepts, makes the optimization possesses larger margin of escaping pbest abilities, also, in able to improve insufficient capabilities of large-scale search of PSO. This model of optimization is called: “Modify Adaptive Particle Swarm Optimization (MAPSO).” The main contribution of the research is in using of conventional PSO, with combination of Genetic Algorithm to facilitate the escaping of pbest, and capability to be more rapidly obtain the optimal solution.
The research utilizing TSPLIB[7] example to conduct experiment, obtaining fine solving efficacy by discovering MAPSO we have raised. MAPSO could improve conventional PSO’s capability of large-scale search than conventional GA optimization does. While applying MAPSO conduction experiment and aiming at the range of 100urban nodes， in average, researchers could expect of receiving know optimal solutions or best solutions in 100 generations. Moreover, after taking tests respectively, the rate of obtaining optimal or best solutions reach up to 100%, proving that the optimization model of this research is not only in possess of precise solving ability, but also relatively excellent stability.

並列關鍵字

PSO ； TSP

參考文獻

[1]. 吳永春、韓宇德， “貪婪演算法結合區域搜尋演算法求解TSP組合最佳化問題”， 2007， 立德管理學院應用資訊研究所碩士論文。

[2]. 陳惠國、林正章、汪進財、卓訓榮、顏上堯、李宗儒、許巧鶯、韓復華、李治綱、蘇雄義、陳春益， ”運輸網路分析”， 五南圖書出版股份有限公司， 2001。

[3]. 黃志鵬、賴柏諭， “適應模糊度配對基因演算法之應用”， 2011， 嶺東科技大學資訊應用研究所畢業論文。

[4]. D. S. Johnson， and L. A. McGeoch， "The traveling salesman problem: a case study in local optimization，" in Local Search in Combinatorial Optimization， 2003， pp 4-103.

[5]. Held， Michal， Karp， Richard M.， “A Dynamic Programming Approach to Sequencing Problems”， Journal of the Society for Industrial and Applied Mathematics. 1962， pp 196-210.