- 學位論文
粒子群最佳化演算法求解旅行者推銷員問題
Particle Swarm Optimization Survey for Traveling Salesman Problem
摘要
粒子群最佳化（Particle Swarm Optimization, PSO）為自1995年來，所新發展出之啟發式演算法，是由Eberhart 和 Kennedy所提出之具有群體智慧概念並且屬於進化搜尋領域的一種演算法，已經在連續性最佳化問題裡得到許多文獻證明其優越的搜尋能力。而在其他離散性的問題如指派、排程等，也有許多這方面研究之文獻。其中，旅行者推銷員問題（Traveling Salesman Problem, TSP）為組合最佳化中相當著名的一問題，已被證明為一NP-Complete問題。不僅在學術上有相當的價值，可做為許多最佳化方法之比較基準，加上其產業可應用的領域廣大，於這方面之研究資料也相當廣泛；大致上有途程規劃、物流等問題。 本研究以文獻中加拿大學者提出之合成函數（Composition Function）為核心，使用三種機制「啟發式初始解」、「突變」及「鄰域搜尋法」，來加強其搜尋組合最佳化問題之能力並命名為「IPSO」，再與先前文獻之實驗結果做比較。並嘗試以「模糊適應共振理論（Fuzzy ART）」作分群來求解大型TSP，最後再將IPSO與基因演算法（Genetic Algorithm, GA）之搜尋結果做比較。由實驗結果可知IPSO在一百個節點內的TSP求解誤差劣於GA，但在四百個節點以上之TSP使用Fuzzy ART分群配合IPSO求解，則可在解題誤差與時間上皆優於GA。
並列摘要
Particle Swarm Optimization (PSO), a new developed heuristic algorithm, is a searching algorithm with intelligence of colony advanced by Eberhart and Kennedy in 1995. The algorithm has been proved the ability of searching that is useful in lots of field, but a few of combinatorial optimization. This study surveys PSO for solving “traveling salesman problem (TSP),” further, discusses the advantage and disadvantage in the field and tries to research the most capability of PSO for solving TSP. Applies “Composition Function,” which is advanced by Gallad and Hawary in Canada, be the main algorithm, then uses three additional methods: “heuristic initial solution,” “mutation,” and “local search” to improve its searching ability. Furthermore, test 9 different data of TSPLIB and verify the proposed additional methods that are efficient or not. In the end, named the algorithm “IPSO” and compare the result with Genetic Algorithm (GA), which is powerful for solving TSP in a lot of reference.