趙禮峰，紀亞寶

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

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

趙禮峰，紀亞寶

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

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

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

0 引 言

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

尋找網(wǎng)絡最小截問題，經(jīng)典方法是采用Ford-Fulkerson[2-3]。隨著網(wǎng)絡規(guī)模的增大，算法的計算量呈指數(shù)級增長，而采用啟發(fā)式算法可以有效解決該問題。啟發(fā)式算法并不能保證給出最優(yōu)解，但其優(yōu)點在于算法的實現(xiàn)較簡單，復雜度不高，可以有效解決最大流最小截問題。

近年來，遺傳算法得到了迅速發(fā)展。目前遺傳算法在求解TSP問題[4-5]、最短路徑問題[6-7]、最小費用最大流問題[8]、Steiner樹問題[9-10]等眾多領域中都有著廣泛的應用，對于最大流最小截問題和遺傳算法的Matlab實現(xiàn)已充分研究[11-12]。運用遺傳算法同樣可以求解最大流最小截問題。

文中給出了最大流最小截的相關定義，給出了遺傳算法的原理，并且根據(jù)以上理論基礎設計了具體的最大流最小截問題的遺傳算法。設計了二進制編碼方法和解碼方法表示遺傳算法中的個體，隨機生成N個個體作為初始群體，計算適應度函數(shù)和歸一化適應值，選擇個體進行變異和交叉操作，形成新的群體。最后求出最優(yōu)個體。

1 相關知識

(1)

定理1[13](最大流最小截定理)：任何帶發(fā)點和收點的容量網(wǎng)絡中都存在最大流和最小截，并且最大流的流值等于最小截的容量。

2 遺傳算法

2.1 基本原理

遺傳算法是一種基于生物進化原理構想出來的搜索最優(yōu)解的仿生算法，它模擬基因交叉變異進化的自然過程，把所需解決問題的個體編成二進制碼或十進制碼，稱為染色體，即個體。類似于生物進化的過程，許多染色體進行選擇、交叉和變異運算，經(jīng)過多次迭代得到最優(yōu)個體[14]。

2.2 遺傳算子

(1)選擇算子。就是按照某種法則來確定如何從父代群體中選取個體進行交叉和變異運算遺傳到下一代群體。常見的選擇算子包括輪盤賭選擇、最佳保留選擇、隨機聯(lián)賽選擇等。

(2)交叉算子。是按照較大的概率在群體中選擇兩個個體進行交叉運算，交換兩個個體的某些位基因。常見的交叉方法包括單點交叉、兩點交叉、均勻交叉、啟發(fā)式交叉等。

(3)變異算子。變異是將染色體編碼串口中的某些基因值更換為其他等位基因，而形成新個體。常見變異方法包括基本位變異、均勻變異、邊界變異等。

2.3 執(zhí)行過程

Step1：初始化。確定種群規(guī)模N、交叉概率Pc、變異概率Pm和終止進化的準則，隨機生成N個個體為初始種群X。

Step2：個體評價。計算或估價X中各個個體的適應度。

Step3：種群進化。

3 最大流最小截問題遺傳算法解法

3.1 編碼方法與群體初始化

群體初始化方法：用一個n維向量存儲個體，對向量中每個元素隨機賦值0或1。但是由定義2可知，節(jié)點1∈S，節(jié)點n∈S，所以a1必須取值為1，an必須取值為0，其他元素均隨機賦0或1。用此方法隨機生成N個個體，作為遺傳算法的初始群體。

3.2 適應度函數(shù)與選擇算子

(1)適應度函數(shù)。

(2)選擇算子。

由于傳統(tǒng)的遺傳算法中適應度越大的個體越接近最優(yōu)解，而最大流最小截的遺傳算法中適應度越小的個體越接近最優(yōu)解，所以在設計選擇算子之前，將由適應度函數(shù)計算出來的適應度進行歸一化。計算公式為：

(2)

由式(2)可知，歸一化適應值越大的個體越接近最優(yōu)解，并且gfi∈(0,1)。針對歸一化適應值而設計的選擇算子為：隨機生成一個0～1之間的數(shù)ri，如果gfi>ri，則被選擇為下一代的母體。從該選擇算子的方法中可以看出：個體的歸一化適應值越大，則被選擇為母體的可能性就越大。選擇算子設計了最佳保留選擇，即在每一代群體中選擇最接近最優(yōu)解的個體作為下一代群體中的第一個個體。

3.3 交叉算子與變異算子

(1)交叉算子。

(2)變異算子。

對由交叉操作產(chǎn)生的新個體，按概率Pm進行變異產(chǎn)生新的個體。具體操作方法為：隨機產(chǎn)生一個2～(n-1)之間的數(shù)i，將個體中第i個節(jié)點換到另外一個截集中。根據(jù)變異操作方法，可設計出二進制編碼的變異方法。

3.4 算法步驟

Step1：初始化群體，隨機生成N個個體。

Step2：計算N個個體的適應值，再計算歸一化適應值。將歸一化適應值最高的個體作為下一代的第一個個體。

Step3：根據(jù)計算出來的歸一化適應值選擇母體，與選擇出來的父體按概率Pc進行交叉操作，產(chǎn)生新個體。

Step4：對由交叉操作產(chǎn)生的新個體，按概率Pm進行變異操作，產(chǎn)生的個體作為下一代中的個體。若下一代中的個體達到N個，則轉Step5，否則轉Step3。

Step5：判斷是否滿足終止條件，如果達到終止條件，輸出最優(yōu)個體和個體適應值；如果沒有達到終止條件，則轉Step2。

4 實例測試

通過Matlab工具對最大流最小截問題的遺傳算法進行仿真實驗。實驗中，Pc取0.9，Pm取0.04。

對圖1中含有6個節(jié)點的網(wǎng)絡進行實驗。由定理1可知，最大流即為最小截，將遺傳算法求出的最小截的截容量和由經(jīng)典dinic算法求出的最大流進行比較。實驗結果如下：

圖1 6個節(jié)點網(wǎng)絡圖

在遺傳算法中群體個數(shù)為10，迭代次數(shù)為30，并進行了100次實驗，實驗結果如圖2所示。100次實驗中只有兩次沒有求出正確結果。求得最小截容量為8時，截集的二進制編碼為(1,1,0,1,0,0)，符合dinic算法求出的結果。

圖2 6個節(jié)點的網(wǎng)絡實驗結果

接著對網(wǎng)絡容量為100個節(jié)點的隨機網(wǎng)絡進行實驗。由dinic算法求出的最大流為198。

在遺傳算法中，群體個數(shù)為10，迭代次數(shù)為30，并進行了100次實驗，實驗結果如圖3所示。在100次實驗中，只有一次沒有求出正確結果。

圖3 100個節(jié)點的隨機網(wǎng)絡實驗結果

最后對網(wǎng)絡容量為1 000個節(jié)點的隨機網(wǎng)絡進行實驗。由dinic算法求出的最大流為151。

在遺傳算法中，群體個數(shù)為20，迭代次數(shù)為30，并進行了100次實驗，實驗結果如圖4所示。

圖4 1 000個節(jié)點的隨機網(wǎng)絡實驗結果

對于1 000個節(jié)點的隨機網(wǎng)絡的不同迭代次數(shù)進行實驗，迭代次數(shù)為5～30，對于每種迭代次數(shù)均進行了10次實驗，再對10次實驗求得的最小截容量求平均值。實驗結果如圖5所示。

圖5 不同迭代次數(shù)的實驗結果

由圖5可以看出，隨著迭代次數(shù)的增加，算法求解的結果趨近于最優(yōu)解，并且算法迭代次數(shù)在15次以上時，算法求解結果穩(wěn)定于最優(yōu)解。

5 結束語

將最大流最小截問題與遺傳算法相結合，設計出

一種基于遺傳算法的最大流最小截問題的算法。在該算法中，根據(jù)最大流最小截問題的定義設計遺傳算法中的編碼方法、解碼方法以及群體初始化方法，設計適應度函數(shù)計算個體適應度，根據(jù)個體適應度設計了算法的選擇算子選擇個體。設計了交叉算子和變異算子產(chǎn)生新的個體，并且給出了具體的算法步驟。通過仿真實驗發(fā)現(xiàn)，對于小型網(wǎng)絡和大型網(wǎng)絡，該算法均能穩(wěn)定求解。

[1]AhujiaRK,MagnantiTL,OrlinJB.Networkflows:theory,algorithmsandapplications[M].[s.l.]:Prentice-Hall,1993.

[2] 劉舒燕.一種改進的求網(wǎng)絡最小截集的算法[J].武漢理工大學學報:交通科學與工程版,2001,25(2)：121-123.

[3]FordLR,FulkersonDR.Maximumflowthroughanetwork[J].CanadianJournalofMath,1956,8(5):399-404.

[4] 李 飛，白艷萍.用遺傳算法求解旅行商問題[J].中北大學學報:自然科學版，2007,28(1)：49-52.

[5]ZhangWendong,BaiYanping.Ahybridelasticnetmethodforsolvingthetravelingsalesmanproblem[J].InternationalJournalofSoftwareEngineeringandKnowledgeEngineering,2015,15(2):447-453.

[6] 鄒 亮，徐建閩.基于遺傳算法的動態(tài)網(wǎng)絡中最短路徑問題算法[J].計算機應用，2005,25(4)：742-744.

[7] 徐 瓊，陳榮清，官云蘭，等.基于遺傳算法最短路徑問題的探討[J].華東地質學院學報，2003,26(2)：168-172.

[8] 厙向陽.網(wǎng)絡最小費用最大流雙目標遺傳優(yōu)化算法[J].江蘇大學學報:自然科學版，2011,32(3)：341-345.

[9]HwangFK,RichardsDS.Steinertreeproblems[J].Networks,1992,22(1):55-89．

[10] 趙禮峰，王小龍.圖的Steiner最小樹問題的混合遺傳算法[J].計算機技術與發(fā)展，2014,24(10)：110-114.

[11] 王海英.圖論算法及其MATLAB實現(xiàn)[M].北京:北京航空航天大學出版社，2010．

[12] 雷英杰.MATLAB遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社，2005．

[13] 謝 政.網(wǎng)絡算法與復雜性理論[M].長沙:國防科技大學出版社，2003.

[14] 葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計算機應用研究，2008,25(10)：2911-2916.

Investigation on Genetic Algorithm for Maximum Flow Minimum Cut Problem

ZHAO Li-feng，JI Ya-bao

(College of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

Genetic algorithm has important applications in many fields,so the problems of maximum flow minimum cut also can be solved by it.Genetic algorithm solving the maximum flow minimum cut problem can be a solution for the exponential growth limitations of calculating amount for traditional algorithms with the increasing of the network size.Based on theory of maximum flow minimum cut problem and genetic algorithm principle,a genetic algorithm is designed for maximum flow minimum cut problem.According to the definition of maximum flow minimum cut,the encoding method,decoding method and a group initialization method of genetic algorithm are designed to form the initial individual of algorithm.The fitness function is designed to calculate individual fitness by which the selection operator is designed to select individual,and design of crossover and mutation operator,the selected individuals are carried out crossover and mutation to produce new individuals,introducing specific algorithm steps.Simulation results show that for small and large networks,this algorithm is stable,and with increasing number of iterations,it can obtain the optimal solution much closer to the true solution.

maximum flow minimum cut;genetic algorithm;selection;crossing;mutation

2016-06-03

2016-09-14

時間：2017-03-07

國家自然科學基金青年基金項目(61304169)

趙禮峰(1959-)，男，教授，碩士研究生導師，研究方向為圖論及其在通信中的應用；紀亞寶(1990-)，男，碩士研究生，研究方向為圖論及其在通信中的應用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0922.064.html

TP301.6

A

1673-629X(2017)04-0069-04

10.3969/j.issn.1673-629X.2017.04.016