最大流最小截問題的遺傳算法研究

趙禮峰，紀亞寶

(南京郵電大學 理學院，江蘇 南京 210023)

最大流最小截問題的遺傳算法研究

趙禮峰，紀亞寶

(南京郵電大學 理學院，江蘇 南京 210023)

遺傳算法在眾多領域中均有重要應用，運用遺傳算法同樣可以求解最大流最小截問題。遺傳算法解決最大流最小截問題可以有效地解決對于網絡規模增長，傳統算法計算量呈指數級增長的局限性。根據最大流最小截問題的相關理論和遺傳算法的原理，設計出最大流最小截問題的遺傳算法，根據最大流最小截問題的定義設計了遺傳算法中的編碼方法、解碼方法以及群體初始化方法，形成算法的初始個體。設計適應度函數計算個體適應度，根據個體適應度設計算法的選擇算子選擇個體，設計了交叉算子和變異算子，將選擇的個體進行交叉變異產生新的個體，并且設計了具體的算法步驟。通過仿真實驗發現，對于小型網絡和大型網絡，該算法均能穩定求解，并且隨著算法迭代次數的增加，算法求得最優解就越接近于真實解。

最大流最小截；遺傳算法；選擇；交叉；變異

0 引 言

最大流最小截問題是一個經典的組合優化問題。最大流最小截算法是對網絡進行劃分，從而求出網絡中的瓶頸部位,其在交通、計算機、通信、電力網絡中有著廣泛的應用[1]。

尋找網絡最小截問題，經典方法是采用Ford-Fulkerson[2-3]。隨著網絡規模的增大，算法的計算量呈指數級增長，而采用啟發式算法可以有效解決該問題。啟發式算法并不能保證給出最優解，但其優點在于算法的實現較簡單，復雜度不高，可以有效解決最大流最小截問題。……