比較三種萬用啓發式演算法於TSP問題之探討

劉昱德 ； 黃士滔

《工程科技與教育學刊》 8卷3期 (2011/09) Pp. 443-452

https://doi.org/10.6451/JETE.201109.0443

摘要

萬用啓發式演算法(Metaheuristics)是一種新興的最佳化演算法，這類演算法的概念經常是由觀察自然界所獲得的靈感，例如：人工免疫演算法啓發於當人體中抗體對抗抗原的免疫反應過程、蟻群演算法習自蟻群的覓食、粒子群演算法係效法鳥類的覓食。由於這些演算法非常具有彈性，可求解許多不同問題，且作法簡單、求解效率高，因此目前已經成爲數量方法中最熱門、最重要的方法之一。近年各類工程問題的優化計算已成爲人們急需解決的問題，如在系統控制、模式識別、生產調度、VLSI技術、計算機工程等，而萬用啓發式演算法強而有力的優化計算方式正能解決這樣的問題。不同的啓發式算法各有其特長及局限，爲了了解不同的演算法對求解的結果以及計算效率的影響，本研究根據三種啓發式演算法：粒子群演算法(Particle Swarm Optimization algorithms, PSO)、蟻群演算法(Ant Colony Optimal, ACO)、人工免疫演算法(Artificial Immune Algorithm, AI)，比較求解非線性規劃問題－旅行推銷員問題(Traveling Salesman Problem, TSP)時解的品質以及求解的計算效率。最後探討三種啓發式演算法中各個算子、對求解品質及效率產生的影響。研究結果發現，演算法中的參數設定，會影響演算法求解的多樣性、收斂性，進而影響到求解的品質與計算的效率。研究中發現粒子群演算法在跳脫局部解上的隨機性過於強大，導致解的多樣性不足，進而提早收斂。人工免疫演算法與粒子群比較下求解多樣性較強，所以在求解多樣性較強的前提下，提升迭代參數，可以改進求解的能力，設定後的參數得到的解甚至優於優化後的螞蟻演算法。

關鍵字

粒子群演算法 ； 蟻群演算法 ； 人工免疫演算法 ； TSP