趙禮峰，紀(jì)亞寶

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

最大流最小截問(wèn)題的遺傳算法研究

趙禮峰，紀(jì)亞寶

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

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

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

0 引 言

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

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

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

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

1 相關(guān)知識(shí)

(1)

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

2 遺傳算法

2.1 基本原理

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

2.2 遺傳算子

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

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

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

2.3 執(zhí)行過(guò)程

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

Step2：個(gè)體評(píng)價(jià)。計(jì)算或估價(jià)X中各個(gè)個(gè)體的適應(yīng)度。

Step3：種群進(jìn)化。

3 最大流最小截問(wèn)題遺傳算法解法

3.1 編碼方法與群體初始化

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

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

(1)適應(yīng)度函數(shù)。

(2)選擇算子。

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

(2)

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

3.3 交叉算子與變異算子

(1)交叉算子。

(2)變異算子。

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

3.4 算法步驟

Step1：初始化群體，隨機(jī)生成N個(gè)個(gè)體。

Step2：計(jì)算N個(gè)個(gè)體的適應(yīng)值，再計(jì)算歸一化適應(yīng)值。將歸一化適應(yīng)值最高的個(gè)體作為下一代的第一個(gè)個(gè)體。

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

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

Step5：判斷是否滿足終止條件，如果達(dá)到終止條件，輸出最優(yōu)個(gè)體和個(gè)體適應(yīng)值；如果沒(méi)有達(dá)到終止條件，則轉(zhuǎn)Step2。

4 實(shí)例測(cè)試

通過(guò)Matlab工具對(duì)最大流最小截問(wèn)題的遺傳算法進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)中，Pc取0.9，Pm取0.04。

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

圖1 6個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)圖

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

圖2 6個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

接著對(duì)網(wǎng)絡(luò)容量為100個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)。由dinic算法求出的最大流為198。

在遺傳算法中，群體個(gè)數(shù)為10，迭代次數(shù)為30，并進(jìn)行了100次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖3所示。在100次實(shí)驗(yàn)中，只有一次沒(méi)有求出正確結(jié)果。

圖3 100個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

最后對(duì)網(wǎng)絡(luò)容量為1 000個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)。由dinic算法求出的最大流為151。

在遺傳算法中，群體個(gè)數(shù)為20，迭代次數(shù)為30，并進(jìn)行了100次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 1 000個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

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

圖5 不同迭代次數(shù)的實(shí)驗(yàn)結(jié)果

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

5 結(jié)束語(yǔ)

將最大流最小截問(wèn)題與遺傳算法相結(jié)合，設(shè)計(jì)出

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

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

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

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

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

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

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

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

[8] 厙向陽(yáng).網(wǎng)絡(luò)最小費(fèi)用最大流雙目標(biāo)遺傳優(yōu)化算法[J].江蘇大學(xué)學(xué)報(bào):自然科學(xué)版，2011,32(3)：341-345.

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

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

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

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

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

[14] 葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究，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

時(shí)間：2017-03-07

國(guó)家自然科學(xué)基金青年基金項(xiàng)目(61304169)

趙禮峰(1959-)，男，教授，碩士研究生導(dǎo)師，研究方向?yàn)閳D論及其在通信中的應(yīng)用；紀(jì)亞寶(1990-)，男，碩士研究生，研究方向?yàn)閳D論及其在通信中的應(yīng)用。

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