臺灣博碩士論文加值系統

基因演算法(Genetic Algorithm, GA)與蟻行最佳化系統(Ant Colony Optimization, ACO)都是屬於啟發式演算法(Heuristic Algorithm)，其中蟻行最佳化是由真實螞蟻的生物行為啟發而來的，它被發展出來在達成求解推論組合最佳化上成為一種高性能之可行方法。雖然蟻行最佳化在求解全域最佳化問題上是有效的，但這種演算法在搜尋過程含有釵h影響演算法性能的隱式和顯式參數，因此，蟻行最佳化系統若能有適選的參數將能導致佳的性能。本論文提出以基因演算法來演化蟻行最佳化系統，建立一種演化式蟻行最佳化系統(Evolving Ant Colony Optimization)，利用GA求解ACO演算法之最佳化參數組合導入蟻行最佳化系統中並應用於大型旅行銷售員問題(Traveling Salesman Problem, TSP)，期能得到最佳的路徑搜尋結果。用蟻行最佳化計算基因演算法所需的環境適應值並執行最佳化過程後決定出使用蟻行最佳化演算法之最佳參數，本論文中計有10個參數包含螞蟻數量m、利用機率與探勘機率之權衡比重q0；費洛蒙揮發權衡參數ㄐF距離權衡參數β；區域更新的參數ρlocal；全域更新的參數ρglobal；相關費洛蒙之一固定參數值Q；候選名單數l；疊代數h；重複運算的次數i。計算從14至225個節點數的旅行銷售員標準，案例經由演化蟻行最佳化後歸納出一組最佳化參數來應用到超過300節點數的大型旅行銷售員問題上。由結果顯示，本論文發展出之演化式蟻行最佳化系統將可提昇路徑搜尋之準確性與加速演算法之收斂性。

Genetic algorithm (GA) and ant colony optimization (ACO) are the two of heuristic algorithms. The ACO is inspired from the biological behavior of real ants. It was developed as a viable approach with high performance for achieving stochastic combinatorial optimizations. Although the ACO is effective in solving the global optimization problems, there are many parameters, both explicit and implicit, affect the performance of the algorithms since the search processes of the two algorithms are nonlinear and complex. Therefore, the ACO with well-selected parameter settings may result in good performance. This thesis proposes an evolving ant colony optimization, which employs a GA to find the best set of parameters employed in the ACO, and apply to the large traveling salesman problem (TSP) for the purpose of obtaining the optimal searching tour. In this thesis, there are ten designed parameters include the number of ant m, three weighting factors q0 , ?and β , local and global evaporation coefficients ρlocal and ρglobal , parameter of pheromone Q , number of table list l , number of iteration h , and repeated run number i . The benchmarking cases of traveling salesman problem (TSP) from 14 to 225 nodes are computed to generalize a set of optimal parameters through the evolving ACO for applying to large TSPs with over 300 nodes. The results demonstrated that the presented evolving ACO significantly enhances the solution accuracy and speed up the algorithmic convergence.

中文摘要 …………………………………………………………………. i
英文摘要 …………………………………………………………………. iii
誌謝 …………………………………………………………………. v
目錄 …………………………………………………………………. vi
表目錄 …………………………………………………………………. vii
圖目錄 …………………………………………………………………. viii
第壹章 緒論……………………………………………………………. 1
第一節 研究背景與動機………………………………………………. 1
第二節 研究問題………………………………………………………. 1
第三節 研究目的………………………………………………………. 2
第四節 研究流程………………………………………………………. 3
第貳章 文獻探討………………………………………………………. 4
第一節 基因演算法之理論……………………………………………. 4
第二節 蟻行最佳化系統之理論………………………………………. 11
第參章 研究內容與方法………………………………………………. 19
第一節 演化式蟻行最佳化系統………………………………………. 19
第二節 演化參數及適值函數…………………………………………. 21
第肆章 結果與討論……………………………………………………. 23
第一節 Burma14測試例驗證結果與討論……………………………. 25
第二節 Oliver30測試例驗證結果與討論…………………………….. 27
第三節 Eil51測試例驗證結果與討論……………………………........ 29
第四節 St70測試例驗證結果與討論……………………………......... 31
第五節 KroA100測試例驗證結果與討論……………………………. 33
第六節 KroC100測試例驗證結果與討論……………………………. 35
第七節 Ch150測試例驗證結果與討論………………………………. 37
第八節 KroA200測試例驗證結果與討論……………………………. 40
第九節 TSP225測試例驗證結果與討論…………..…………………. 43
第十節 將演化的參數驗證於A280、Pr299及Lin318範例………... 45
第伍章 結論……………………………………………………………. 64
參考文獻 …………………………………………………………………. 65
附件一 已發表論文:以蟻行演算法建構最佳化之消防路徑派遣系統-以台南市行政區為例(發表於第十一屆資訊管理暨實務研討會，實踐大學，94年12月10日) 67
附件二 已發表論文:以基因演算法演化蟻行最佳化系統(發表於第十一屆人工智慧與應用研討會，高雄應用科技大學，95年12月15、16日) 87
簡歷 …………………………………………………………………. 96

[1]Gillett, B., and Miller, L. (1974), “A Heuristic Algorithm for the Vehicle Dispatch Problem”, Operational Research, 22, 340-349.

[2]Michalewicz, Z. (1996), Genetic Algorithms + Data Structures = Evolution Programs, Berlin: Springer-Verlag, pp.13-88.

[3]Goldberg, D.E. (1989), Genetic Algorithms in Search, Optimization, and Machine Learning, Reading, MA: Addison-Wesley, pp.69-93.

[4]Sengoku, H. and Yoshihara, I. (1993), “A Fast TSP Solution using Genetic Algorithm,” Information Processing Society of Japan 46th , 121-125.

[5]Grefenstette, J., Gopal, R., Rosimaita, B., and van Gucht, D. (1985), “Genetic Algorithms of Traveling Salesman Problem.”, Proc. Int. Conf. Genetics Algorithms and Their Applications, 160-168.

[6]Lin, F.T., Kao, C.Y., and Hsu, C.C. (1993), “Applying the Genetic Approach to Simulated Annealing in Solving Some NP-Hard Problems,”IEEE Trans. Syst. Man Cybern, 23:1752-1767.

[7]Dorigo, M., Maniezzo, V., and Colorni, A. (1996), “The Ant System: Optimization by a Colony of Cooperation Agents,” IEEE Transactions of Systems, Man and Cybernetics, Part B, 26(2), 29-41.

[8]Dorigo, M., and Gambardella, L.M. (1997), “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, 1(1), 53-66.

[9]Dorigo, M., Di Caro, G., and Gambardella, L.M. (1999), “Ant Algorithms for Discredte Optimization,” Artificaial Life, 5(2), 137-172.

[10]Dorigo, M., Bonabeau, E., and Theraulaz, G. (2000a), “Ant Algorithms and Stigmergy,” Future Generation computer Systems, 16(8), 889-914.

[11]Dorigo, M. (2004), Ant Colony Optimization, London: The Mit Press, pp.65-119.

[12]Maniezzo, V. and Colorni, A. (1998), “The ant system applied to the quadratic assignment problem,”IEEE Trans. Knowledge and Data Engineer, 11(5): 769-778.

[13]Holland, J.H. (1973), “Genetic Algorithm and the Optimal Allocation of Trials,” SIMA J. Computing, 2(2), 88-105.

[14]Holland, J.H. (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, pp.173-202.

[15]Eiben, A.E. and Smith, J.E. (2003), Introduction to Evolutionary Computing, New York:Springer, pp.37-69.

[16]Botee, H.M. and Bonabeau, E. (1998), “Evolving Ant Colony Optimization,” Adv. Complex Systems, 1, 149-159.

[17]蘇純繪和翁瑞聰 (2003)，「以螞蟻群聚最佳化整合噪音擾動法求解TSP問題」，商管科技季刊，第四卷第四期，359-375頁。

[18]孫力娟、王良俊和王汝傳(2004)，「改進的蟻群算法及其在TSP中的應用研究」，通信學報，第二十五卷第十期，111-116頁。

[19]鄭炳強和侯雍聰(2004)，混合基因及螞蟻演算法的TSP解法，2004智慧型知識經濟研討會暨第二屆演化式計算應用專題研討會，台北，3-5頁。

[20]TSPLIB(2003), Library of Treveling Salesman Problems, Interdisciplinary Center for Scientific Computing, http://www.iwr.uni-heidelberg.de/groups/
comopt/software/TSPLIB95/index.html