適應模糊度配對基因演算法之應用

Genetic Algorithm equipped with the Adaptive Fuzzy Degree Crossover method and applications

賴柏諭(Po-Yu Lai)

指導教授 ： 黃志鵬

嶺東科技大學/資訊學院/資訊科技應用研究所/碩士(2011年)

https://doi.org/10.6823/LTU.2011.00046

摘要

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

關鍵字

基因演算法 ； 模糊分群 ； 旅行推銷員問題

並列摘要

This study mainly investigates the genetic algorithm (GA) associated with the notation of fuzzy theory and applications. The proposed crossover model for GA algorithm is guided via the grade of fuzzy membership functions, and the applicability is demonstrated by solving the travel salesman problem (TSP). The crossover model for the traditional GA use the probability rule to produce the next generation, where it always cause the time consumption for the useless evaluation. Thus, we study a distinct crossover model for GA algorithm associate with the fuzzy grade notion; this dynamic guide mode for GA algorithm can speed up the convergent process and improve the efficiency and the error rate for simulating results. The experiments are demonstrated and verified by the international benchmarks with TSPLIB and compared with the other GA proposed by LaLena.M. When the experiments use less than 500 city’s samples and set 1000 iterations as the terminal conditions, the error rate of the obtained solutions can be less then 1% contrasting with the existing optimal solution. Especially, in the cases with 100 city’s samples, the optimal solutions or the better solutions can be frequently attained within 100 generations. The experiment results demonstrate that the evaluating efficiency, the error rate, and the convergent stability of the proposed method are indeed superior to the traditional GA.

並列關鍵字

Genetic algorithm ； Fuzzy clustering ； Travel salesman problem ； TSP

參考文獻

[1] 王文俊，「認識Fuzzy」，全華科技圖書股份有限公司，民國94年

[2] 林豐澤，2005，演化式計算上篇：演化式演算法的三種理論模式，智慧科技與應用統計學報，第3卷，第1期，第18-22頁。

[3] 林豐澤，2005，演化式計算下篇：演化式演算法的三種理論模式，智慧科技與應用統計學報，第3卷，第1期，第35-40頁。

[4] 陳惠國、林正章、汪進財、卓訓榮、顏上堯、李宗儒、許巧鶯、韓復華、李治綱、蘇雄義、陳春益，「運輸網路分析」，五南圖書出版股份有限公司，第203-221頁。

[5] 韓宇德，2007，貪婪演算法結合區域搜尋演算法求解TSP 組合最佳化問題，立德管理學院應用資訊研究所碩士論文，第19-34頁。