用混合式基因演算法求解具容量限制之多點網路設計問題

Abstract

本論文的主旨是在探討用混合式基因演算法求解具容量限制之多點網路設計問題。此問題求解的困難度是屬於NP-Complete。運用基因演算法求解單目標與多目標具容量限制之多點網路設計問題將在本論文中討論。基因演算法其基本觀念係透過基因運算子模擬生物基因系統的演化來解決各式各樣複雜的最佳化問題。對一個具容量限制之多點網路設計問題的解答，我們運用Prufer encoding來表示。但是Prufer encoding有一個重大缺點，就是透過傳統的基因演算法運算子它無法維持相近的位置關係（locality），任何一個向量中元素的改變，將導致其所對應之樹狀結構圖完全不一樣，以致於無法運用相似性的概念找到最佳解。針對上述Prufer encoding的缺點，本論文提出一個新的基因運算子，稱之為 substituting Prufer vector (SPV)，它有效地解決Prufer encoding基因演算法應用上的致命缺點。本論文運用此運算子於基因演算法中，發展出兩個演算法，SGA及MOHGA以分別求解單目標與多目標具容量限制之多點網路設計問題。 為了驗證SGA的效用，我們探討以成本為唯一設計考量的單目標網路拓樸設計問題，對照比較的方法則為Palmer所提出演算法，簡稱PGA。依據由模擬實驗所得的結果數據分析，從CPU的執行時間而言，SGA隨著網路規模增長，其CPU執行時間效能明顯優於PGA。從求出成本來分析，SGA求出的成本也低於PGA，且隨著網路規模增長其成本差距愈大。所以，不論從CPU的執行時間或者是求出的成本等不同角度來看，SGA皆優於PGA。 我們採納Shaffer的族群切割的概念，將一族群分割成4個大小相等的子族群，然後運用SPV基因運算子，菁英保留策略､完全隨機法及Baker的隨機通用抽樣法以產生下一代的新族群。我們稱此種多目標混合式基因演算法為Multiobjective Hybrid Genetic Algorithm，簡稱MOHGA。對照比較的方法則為VEGA與SOGA。依據由模擬實驗所得的結果數據分析，從CPU的執行時間而言，隨著網路規模增長，其CPU執行時間效能明顯優於SOGA與VEGA。

The capacitated multipoint network design problems (CMNDPs) are studied. The CMNDP is NP-complete. In this dissertation, both the single objective (cost) and the multiobjective (cost and delay) CMNDPs are considered. Genetic algorithms, which employ genetic operators to simulate the process of biological evolution, are effective search methods for solving many kinds of complex optimization problems. A solution for CMNDPs can be encoded into a chromosome by using Prufer encoding. However, Prufer encoding does not preserve locality. Changing one element of a Prufer vector causes dramatically change in its corresponding tree topology. In this dissertation, we introduce a new genetic operator to remedy this well-known problem, called the substituting Prufer vector (SPV), and use it for solving CMNDPs. SPV-based Genetic Algorithm (SGA) and Multi-Objective Hybrid Genetic Algorithm (MOHGA) are proposed to solve the single objective and the multiobjective CMNDPs, respectively. By examining computational results, we notice that the rate of increase of the running time of SGA is close to a linear function while that of Palmer's Genetic Algorithm (PGA) is close to an exponential function. The SGA is very efficient and effective than PGA. The MOHGA is based on the subpopulation concept-the mixed method. The elitism reservation strategy, the substituting Prufer vector, the stochastic universal sampling, and the complete random method are used to produce the next generation population. The MOHGA has been applied to CMNDP. By examining computational and analytical results, we notice that the MOHGA finds most non-dominated solutions and is much more effective and efficient than the Single-Objective Genetic Algorithm (SOGA) and the Vector Evaluated Genetic Algorithm (VEGA).