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

Abstract

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

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.