平行演算之優加劣減蟻拓優化法求解旅行銷售員問題

Parallel Superior/Inferior Segment-Discriminated Ant System for Travelling Salesman Problems

李湛(Chan Lee)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2013年)

https://doi.org/10.6342/NTU.2013.01706

摘要

啟發式演算法為眾所皆知處理高複雜度問題的技術，但仍在現實中的高維度問題下的運算時間上仍有物理的計算瓶頸存在；而近二十多年來，多執行緒(Multi-Thread)的平行運算的程式開發技術儼然已經成了加速演算速度的重要趨勢。因此本研究使用nVDIA的CUDA平行運算開發平台搭配優加劣減蟻拓優化法(Superior/Inferior Segment-Discriminated Ant System,SDAS)來求解旅行銷售員問題(Travelling Salesman Problem)，並針對平行運算搭配SDAS下的不同演算策略進行進一步的研究分析。

關鍵字

CUDA ； 平行運算 ； 蟻拓最佳化技術 ； 優加劣減蟻拓優化法 ； 旅行銷售員問題

並列摘要

The meta-heuristic algorithm, known as a technique coping with high complexity problems, has still been encountered the physical bottleneck calculating under the high dimension problems in realistic problems. Recent twenty years, moreover, the Multi-Thread parallel calculating program developing techniques has obviously became a vital trend accelerating the speed in calculation speed and effeciency of algorithm.
Therefore, the thesis approaches the Travelling Salesman Problem ( TSP ) , based on the CUDA, a parallel computing platform and programming model created by nVDIA, together with the Superior/Inferior Segment-Discriminated Ant System ( SDAS ). This thesis also looks for further research analysis in connection with different algorithm strategies in collection with the CUDA and the SDAS.

並列關鍵字

CUDA ； SDAS ； TSP ； parallelization

參考文獻

林典翰. (2004). 優加劣減螞蟻擇段系統應用於組合問題. 臺灣大學工業工程學研究所學位論文, 臺灣大學.

Catala, A., Jaen, J., & Modioli, J. A. (2007, 25-28 Sept. 2007). Strategies for accelerating ant colony optimization algorithms on graphical processing units. Paper presented at the Evolutionary Computation, 2007. CEC 2007. IEEE Congress on.

Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 26(1), 29-41. doi: 10.1109/3477.484436

Pedemonte, Martin, Nesmachnow∗, Sergio, & Cancela, Hector. (2011). A survey on parallel ant colony optimization. Applied Soft Computing, 11(71), 5181–5197. doi: 10.1016/j.asoc.2011.05.042

The, x, Van, Luong, Melab, N., & Talbi, E. (2013). GPU Computing for Parallel Local Search Metaheuristic Algorithms. Computers, IEEE Transactions on, 62(1), 173-185. doi: 10.1109/TC.2011.206