基於MapReduce之改良式粒子群最佳化演算法求解旅行銷售員問題

Improved particle swarm optimization for solving traveling salesman problem using MapReduce.

鍾宇杰(Yu-Chieh Chung)

指導教授 ： 張志忠

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

https://doi.org/10.6823/LTU.2014.00058

摘要

旅行銷售員問題(TSP)是一個經典的NP-hard問題，多年來許多學者發展啟發式演算法進而解決旅行銷售員問題的速度與效率，無論如何，當所求解的城市節點愈大時，於單機運算時之計算複雜度也隨之大增。現今一種新穎的運算技術，配合著網路的蓬勃興盛更是發展出各種零瑯滿目的服務型態，而此技術就是「雲端運算」，如何將雲端運算應用於旅行銷售員問題將是一熱門議題。本研究提出一種基於MapReduce架構下之改良式粒子群最佳化(Particle Swarm Optimization, PSO)演算法，並使用此一架構模式來針對TSP問題進行求解。所提出之PSO演算法是利用粒子分組的概念讓各組之間彼此競爭，讓各組分別收斂並利用分組內部機制讓各組能互相溝通來修正自己的路徑。同時，也結合了基因演算法的適者生存的概念讓表現較差的組別有脫離區域最佳解的能力，此外，也對區域搜尋技術(2-opt)作改良，研究中將針對所提出之PSO演算法於單一電腦中運作的效能以及基於雲端運算的結合方式做進一步的說明。研究結果顯示，本研究所提出之改良式PSO演算法，於單機環境下求解TSP時均能有效地獲得最佳解，同時，基於MapReduce雲端架構之PSO演算法，在解決TSP問題時也能順利獲取最佳解，並且比單機求解更快速，確實有助於解決TSP問題效率的提升。此外，在獲得相同最佳解的情況下，本研究所提出的方法確實能降低其運算成本。
關鍵字：旅行銷售員問題、雲端運算、粒子群最佳化、2opt

關鍵字

旅行銷售員問題 ； 雲端運算 ； 粒子群最佳化 ； 2opt

並列摘要

Traveling salesmen problem (TSP) is a typical NP-hard problem. Researchers have proposed many strategies of algorithm to improve the efficiency of solving TSP. However, it also greatly increases the computational complexity, when the numbers of city nodes reasonably increase. Nowadays, cloud computing is very popular solution for these types of service. Implementing cloud computing to solve problems for salesman will be a top issue these days.
In this study, we propose an improved particle swarm optimization (PSO) algorithm based on MapReduce framework to solve TSP. The proposed approach uses swarm grouping mechanism combined with crossover operation of genetic algorithm (GA) for efficiently solving TSP. The algorithm divides the swarm into many groups, and each group flies toward its own global best particle which can share the information simultaneously in order to correct their path. Adopting the swarm grouping mechanism, the algorithm avoids of being premature. Moreover, an improved 2-opt local search algorithm is proposed for optimizing the TSP. The numerical results have showed that the proposed improved PSO can efficiently obtain the optimal solution for solving TSP in a standalone machine. Similarly, for improved PSO based on the MapReduce framework, which can really help to improve the efficiency of solving TSP compared with standalone machine. In other words, under the same conditions, this study proposes a method to reduce the cost of solving TSP.
Keywords ： Traveling salesmen problem 、cloud computing、particle swarm optimization、2-opt

並列關鍵字

Traveling salesmen problem ； cloud computing ； particle swarm optimization ； 2-opt

參考文獻

[1] J. Dean and S. Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters," Sixth Symposium on Operating System Design and Implementation, 2004.

[2] H. Er and N. Erdoğan, "Parallel genetic algorithm to solve traveling salesman problem on MapReduce framework using hadoop cluster," International Journal of Soft Computing and Software Engineering, vol. 3,no. 3, pp. 380-386, 2013

[3] A. Mohan and Remya G, "A parallel implementation of ant colony optimization for TSP based on MapReduce framework," International Journal of Computer Applications, vol. 88, no. 8, pp. 9-12, 2014

[4] R. C. Eberhart and J. Kennedy, "A new optimizer using particles swarm theory," Proceedings of IEEE International Conference on Neural Networks, vol. 4, pp. 1942-1948, 1995.

[5] Hadoop簡介 http://hadoop.apache.org/