求解一般性排序優化問題的仿水流優化演算法

Water Flow-like Algorithm for Sequencing Problems

潘嘉琪(Chia-Chi Pan)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.02898

摘要

仿水流優化演算法(Water Flow-like Algorithm, WFA)是新創的尋優演算法。WFA係仿效水流在地理空間逐步流向最低點的特性，將代理人模擬成水流，在解空間中搜尋最佳解。WFA模仿水流的分流和匯流特性，動態調整代理人的數量，有效地進行集中或分散搜尋。此外WFA亦模擬水流蒸發和降水的特性，使搜尋能有機會跳脫區域最佳解。WFA最先提出是用於求解物件分群優化問題，本研究提出求解一般性物件排序優化問題的仿水流優化演算法(Water Flow-like Algorithm for Sequencing Problems, WFA4SP)。在WFA的演算程序規範下，規劃符合物件排序問題限制的仿水流搜尋機制。本研究提出仿連續空間位置指定法、子序列變動法、和鏈結關係繼承法三種求解排序問題的分流移步法，以設定每一演化代次水流移動的位置。接著提出循環比對法以計算物件排序解的相似度，供匯流作業使用。為驗證本研究所提的WFA4SP演算機制，本研究以旅行推銷員標竿問題為測試對象。比較三種分流移步法的成效，並與典型的遺傳演算法比較求解結果，探究本研究所提方法可行性。結果顯示在共同目標函式求算次數下，WFA4SP表現較遺傳演算法優異。因匯流作業的循環比對作業會耗費大量計算資源，在共同求解時間下求解大維度問題時仍有改善空間。

關鍵字

啟發式演算法 ； 仿水流優化演算法 ； 物件排序優化問題 ； 旅行推銷員問題

並列摘要

Water Flow-like Algorithm, WFA, is a newly developed optimization algorithm that simulates a solution searching agent as a water flow traversing the lowest point of a terrain. The number of water flows is dynamically changed while water flows split into subflows against rough terrain and merge several flows into one single flow. Flow splitting and merging are mimicked by the WAF to conduct efficient optimum search in the solution space. In addition, water evaporation and precipitation are simulated in WFA to jump out of local optima or to broaden the searching area. WFA was originally proposed for grouping problems. This paper presents a WFA for solving object sequencing problems, namely WFA for Sequencing Problem, WFA4SP. Based on the original WFA computation structure, WFA4SP conducts the water flows to stand for feasible solutions of a sequencing problem, where the coordinates of the position of a water flow must be mutual exclusive. This paper presents three water flow methods: continuous space-like position assignment (CPA), subtour shuffle (SS), and link relationship inheritance (LRI), to assign feasible flow positions in water splitting operation of the WFA4SP. In addition, a cyclic similarity computation procedure is developed to evaluate the closeness of two flow positions to facilitate the water flow merging operation of the WFA4SP. Several TSP benchmarks were used to test the WFA4SP and results were compared with those from the best GA methods that uses GSX and TSP dedicated GX crossover operators. Numerical tests showed that the LRI position assignment method generated the best results than those from the CPA and SS methods. Result comparison showed that based on the same limit of the number of objective function calls, the WFA4SP outperforms the GA methods with GSX and GX crossover operators. Nevertheless, the high computation complexity of the flow merging operation results in costly computation overhead than other operations of WFA4SP.

並列關鍵字

heuristic algorithm ； water flow-like algorithm ； sequencing problems ； traveling salesman problems

參考文獻

王元鵬 (2006). 仿水流離散優化演算法. 工業工程學硏究所, 國立臺灣大學. 碩士論文.

Dorigo, M., V. Maniezzo, et al. (1996). "Ant system: optimization by a colony of cooperating agents." Systems, Man, and Cybernetics, Part B, IEEE Transactions on 26(1): 29-41.

Flood, M. M. (1956). "The traveling salesman problem." Operations research 4(1): 61.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc.

Holland, J. H. (1992). Adaptation in natural and artificial systems, MIT Press.