適應模糊度配對之基因演算法應用於TSP問題

10.29850/LTJ.201112.0005

黃志鵬；賴柏諭

基因演算法 ； 模糊分群 ； 旅行推銷員問題 ； TSP (Travel Salesman Problem)

嶺東學報

30期（2011 / 12 / 01）

129 - 154

繁體中文

本研究主要探討基因演算法（GA）結合模糊理論（Fuzzy）之相關實務應用。傳統基因演算法以純粹的「機率規則」來決定演算過程中的基因配對，常常會導致基因演算法耗費大量時間於無效的搜尋，因此在本研究中我們提出了一套以歸屬度做為基因配對基準的引導演化模式，以動態方式計算各個資料點之歸屬度，並以所得結果做為引導門檻，以提昇基因演算法的收斂速度，達到改善基因演算法的效能與偏差率。本研究以TSPLIB所提供之國際標準範例做為演算法之驗證，並以LaLena.M所提供之基因演算法解TSP（Travel Salesman Problem）問題程式做為效能與偏差率的比較，在反覆測試過程中，以500個城市點內，設定演化1000代為終止條件，所得結果與國際標準範例所提供已知最佳解比較，皆能將誤差範圍控制在1％以內。對於100個城市點中，有極高的比率可在100代內求得已知最佳或更優解。根據實驗結果，所提出方法的運算效能、偏差率與穩定性皆明顯優於傳統式的基因演算法。

1. M. Lalena (2010), Traveling Salesman Problem Using Genetic Algorithms, http://www.lalena.com/ai/tsp/
2. TSBLIB, http://comopt.ifi.uni-heidelberg.de/software/index.html
3. The Traveling Salesman Problem, http://www.tsp.gatech.edu/
4. Al-Dulaimi, B. F.,Ali, H. A.(2008).Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA).World Academy of Science, Engineering and Technology,296-302.
5. Zadeh, L. A.(1965).Fuzzy sets.Information and Control,338-353.
6. Zhang, W.,Looks, M.(2005).A Novel Local Search Algorithm for the Traveling Salesman Problem that Exploits Backbones.Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI)
7. 林豐澤(2005)。演化式計算下篇：演化式演算法的三種理論模式。智慧科技與應用統計學報，3(1)，35-40。
8. 陳建緯(2001)。交通大學運輸管理研究所。
9. 黃志鵬、林志和(2008)。最短路徑之探索研究—使用模糊分群與基因演算。數位科技與創新管理研討會
10. 韓宇德(2007)。立德管理學院應用資訊研究所。