分散式基因演算法執行效率最佳化之研究

The Optimal Execution Parameters Design for Distributed Genetic Algorithms

洪光鈞(KuangChun Hung)

指導教授 ： 邱昭彰

元智大學/資訊學院/資訊管理學系/碩士(2005年)

摘要

本研究旨在探討分散式基因演算法中，相關的演化參數對於其計算成本與解題精確度的影響分析。由於分散式基因演算法解題的精確度與運算成本均比傳統基因演算法表現較好，因此是一個特別適合運用於複雜性高的最佳化問題之演算法，且可運用的問題領域極廣，但隨著問題複雜度的提高與範圍的擴大，解題的品質與效能一直是各方研究的焦點。
由最佳化的觀點出發，我們將調整群體規模、遷移時機以及遷移率進行多次求解實驗，針對結果探討如何利用調整相關參數改善演化效能，並嘗試利用資料探勘推導出各遷移參數與適應值的關係式，以找出最佳的遷移參數組合，進一步提升預測解題的效果與品質，最後我們將其結果應用於最大值求解、生產排程最佳化、旅行銷售員與具時窗限制之車輛途程含回程取貨等不同領域的最佳化問題。

關鍵字

分散式基因演算法 ； 資料探勘 ； 遷移策略 ； 生產排程 ； 旅行銷售員 ； 具時窗限制之車輛途程含回程取貨 ； 最佳化

並列摘要

While probing into distributed genetic algorithms (DGAs) in this research purport. The design of distributed genetic algorithms (DGAs) aims to achieve computation efficiency than that of genetic algorithms. DGAs are suitable for solving complex optimization problems in many areas. As the optimization problems become more complex, more attention will focus on the problem-solving quality and efficiency of DGAs.
Our research is trying to determine the optimal parameters of DGAs Initial Migration Generation, Migration Rate and Migration Interval to improve the Fitness Values of objective function in a more efficient way. We apply the obtained parameters in solving the Max Ones and Job Shop optimization problems. At present these optimal migration parameters are derived by observing summary statistics. We apply the results in Max Ones, Job Shop Scheduling, Traveling Salesman Problem, and Vehicle Routing Problem with Time Windows Constraint. The outcomes of the experiments indicate better computation performance can be derived. In the future, we will construct a formula consisted of the three migration parameters, Starting Migration Generation, Migration Rate and Migration Interval, and the Fitness Value.

並列關鍵字

Distributed Genetic Algorithms ； Migration Strategy ； Job Shop Scheduling ； Traveling Salesman Problem ； Vehicle Routing Problem with Time Windows Constraint ； Optimization