采用遺傳算法的網(wǎng)絡(luò)優(yōu)化技術(shù)

李國(guó)慶, 尹洪勝

(中國(guó)礦業(yè)大學(xué) 信息與電氣工程學(xué)院, 江蘇 徐州 221008)

采用遺傳算法的網(wǎng)絡(luò)優(yōu)化技術(shù)

李國(guó)慶, 尹洪勝

(中國(guó)礦業(yè)大學(xué) 信息與電氣工程學(xué)院, 江蘇 徐州 221008)

針對(duì)樹(shù)型網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和數(shù)學(xué)模型，從個(gè)體編碼、種群初始化、種群進(jìn)化、適應(yīng)度函數(shù)等方面構(gòu)建基于遺傳算法的網(wǎng)絡(luò)優(yōu)化方法.實(shí)驗(yàn)結(jié)果表明：所構(gòu)建的方法進(jìn)一步修正了適應(yīng)度函數(shù)，增強(qiáng)了弱勢(shì)個(gè)體被選擇的概率，避免遺傳算法優(yōu)化過(guò)程的過(guò)早收斂問(wèn)題，縮短了執(zhí)行時(shí)間，取得了較佳的網(wǎng)絡(luò)優(yōu)化結(jié)果.

樹(shù)型網(wǎng)絡(luò); 網(wǎng)絡(luò)優(yōu)化; 遺傳算法; 適應(yīng)度函數(shù).

網(wǎng)絡(luò)優(yōu)化是諸多領(lǐng)域的關(guān)鍵技術(shù)，如通信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等[1].無(wú)論是何種類型的網(wǎng)絡(luò)，都會(huì)涉及到網(wǎng)絡(luò)組建的成本最小化、網(wǎng)絡(luò)節(jié)點(diǎn)連接代價(jià)最小化的問(wèn)題，而這些問(wèn)題又與網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)密切相關(guān)[2].在各領(lǐng)域的網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)中，設(shè)計(jì)人員的經(jīng)驗(yàn)起到至關(guān)重要的作用[3].但依托于人工手段實(shí)現(xiàn)的網(wǎng)絡(luò)優(yōu)化，優(yōu)化效率和結(jié)果都難以達(dá)到最佳.在這種背景下，依托于計(jì)算機(jī)輔助手段的網(wǎng)絡(luò)優(yōu)化技術(shù)開(kāi)始出現(xiàn).在計(jì)算機(jī)輔助優(yōu)化框架下，網(wǎng)絡(luò)優(yōu)化問(wèn)題映射為全局優(yōu)化的復(fù)雜性求解問(wèn)題[4].很多全局優(yōu)化算法都被引入到網(wǎng)絡(luò)優(yōu)化中，如禁忌搜索法、神經(jīng)網(wǎng)絡(luò)法、蟻群算法、粒子群算法等[5-6].趙云豐等[7]在人工免疫算法的基礎(chǔ)上，構(gòu)建了一種新的禁忌搜索機(jī)制，通過(guò)特赦準(zhǔn)則和高斯變異實(shí)現(xiàn)網(wǎng)絡(luò)優(yōu)化，但該算法復(fù)雜度較高.李柞泳等[8]針對(duì)BP網(wǎng)絡(luò)的實(shí)際問(wèn)題，根據(jù)訓(xùn)練誤差和檢驗(yàn)誤差更新信息素濃度，但該法只針對(duì)BP網(wǎng)絡(luò)，具有一定的局限性.喬俊飛等[9]針對(duì)排污網(wǎng)絡(luò)的具體問(wèn)題，設(shè)計(jì)新的隸屬度函數(shù)，構(gòu)建了基于粒子群算法的網(wǎng)絡(luò)智能優(yōu)化系統(tǒng).樊富有等[10]為了實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)的優(yōu)化，設(shè)計(jì)了一種基于優(yōu)化量子旋轉(zhuǎn)門(mén)的遺傳算法.然而，遺傳算法在網(wǎng)絡(luò)優(yōu)化時(shí)，容易過(guò)早收斂.從已有的研究成果看，遺傳算法在網(wǎng)絡(luò)優(yōu)化問(wèn)題中已有比較成功的應(yīng)用[11]，但也存在一些問(wèn)題.因此，本文在前人研究成果的基礎(chǔ)上，借助遺傳算法并重點(diǎn)解決其過(guò)早收斂問(wèn)題，以期實(shí)現(xiàn)對(duì)樹(shù)狀網(wǎng)絡(luò)的拓?fù)鋬?yōu)化.

圖1 樹(shù)型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

1 樹(shù)型網(wǎng)絡(luò)及其數(shù)學(xué)模型

典型的網(wǎng)絡(luò)結(jié)構(gòu)有星型拓?fù)浣Y(jié)構(gòu)、環(huán)型拓?fù)浣Y(jié)構(gòu)、總線型拓?fù)浣Y(jié)構(gòu)、樹(shù)型拓?fù)浣Y(jié)構(gòu)等.樹(shù)型拓?fù)浣Y(jié)構(gòu)從總線型拓?fù)浣Y(jié)構(gòu)演變而來(lái)，不僅易于終端擴(kuò)展，也有利于故障隔離.一般性的樹(shù)型網(wǎng)絡(luò)，如圖1所示.

對(duì)樹(shù)型網(wǎng)絡(luò)的優(yōu)化就是實(shí)現(xiàn)各個(gè)節(jié)點(diǎn)的更合理連通，使網(wǎng)絡(luò)投資更小、網(wǎng)絡(luò)連接代價(jià)更低.針對(duì)圖1的網(wǎng)絡(luò)結(jié)構(gòu)，假設(shè)其中存在n個(gè)節(jié)點(diǎn)P，m個(gè)連接L，則其網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可以描述為T(mén)(P,L)，并且具備屬性為

式(1)，(2)分別描述了節(jié)點(diǎn)集合中的節(jié)點(diǎn)數(shù)量和各節(jié)點(diǎn)的最大可能連接.

對(duì)于節(jié)點(diǎn)i和節(jié)點(diǎn)j，判斷它們之間是否存在連接的表達(dá)式為

式(3)中:li,j為2個(gè)節(jié)點(diǎn)之間的連接狀況.

如果用{li,j}表示一個(gè)樹(shù)型網(wǎng)絡(luò)的所有連接集合，用{ci，j}表示所有連接對(duì)應(yīng)的連接代價(jià)集合，則樹(shù)型網(wǎng)絡(luò)的優(yōu)化問(wèn)題就變成是對(duì){ci，j}集合的優(yōu)化問(wèn)題，對(duì)應(yīng)的數(shù)學(xué)模型為

式(4)中：R(l)為網(wǎng)絡(luò)連接的優(yōu)化函數(shù).

2 基于遺傳算法的網(wǎng)絡(luò)優(yōu)化方法的構(gòu)建

遺傳算法的執(zhí)行環(huán)節(jié)：個(gè)體編碼、種群初始化、種群進(jìn)化(選擇、交叉、變異)、計(jì)算適應(yīng)度函數(shù).

假設(shè)網(wǎng)絡(luò)(圖1)節(jié)點(diǎn)為12個(gè)，即n=12；同時(shí)，每個(gè)節(jié)點(diǎn)和其他節(jié)點(diǎn)的最大連接數(shù)目不超過(guò)4個(gè).根據(jù)圖1的具體結(jié)構(gòu)，存在4個(gè)分支結(jié)構(gòu).為了從數(shù)學(xué)意義上描述當(dāng)前連接狀態(tài)，為種群的初始狀態(tài)構(gòu)建一個(gè)連接編碼集合，即

之后，以隨機(jī)生成的方式，按照一定規(guī)模對(duì)網(wǎng)絡(luò)各節(jié)點(diǎn)連接的初始狀態(tài)進(jìn)行初始化.以這些個(gè)體狀態(tài)作為初始種群，按照遺傳算法的典型操作執(zhí)行網(wǎng)絡(luò)優(yōu)化.其中，交叉操作是以初始種群中的個(gè)體作為父代繁殖子代.繁殖過(guò)程中,個(gè)體被選擇的概率，根據(jù)適應(yīng)度函數(shù)計(jì)算，即

式(6)中：k為的是種群代數(shù).交叉操作的結(jié)果形成新的網(wǎng)絡(luò)連接，如果滿足預(yù)先設(shè)定的各種約束條件,則保留;如果不滿足,則選擇另外的雙親執(zhí)行新的交叉操作生成.

變異操作，是對(duì)個(gè)體狀態(tài)的某個(gè)位進(jìn)行隨機(jī)變異，也是生成新個(gè)體的重要方法.每一輪遺傳操作處理后，那些最優(yōu)的個(gè)體會(huì)被保留，依據(jù)式(4)進(jìn)行優(yōu)化操作.

按照上述過(guò)程執(zhí)行網(wǎng)絡(luò)優(yōu)化時(shí)，遺傳算法存在早熟或局部收斂的問(wèn)題，導(dǎo)致無(wú)法形成最優(yōu)優(yōu)化結(jié)果或非全局最優(yōu)結(jié)果.其原因在于適應(yīng)度函數(shù)的設(shè)置，使部分候選個(gè)體被選擇的概率過(guò)小，而早早地被淘汰.為此，對(duì)適應(yīng)度函數(shù)進(jìn)行修改，增強(qiáng)弱勢(shì)個(gè)體被選擇的概率[12]，即

至此，針對(duì)樹(shù)型網(wǎng)絡(luò)模型構(gòu)造了基于遺傳算法的優(yōu)化過(guò)程，并對(duì)早熟和局部收斂問(wèn)題進(jìn)行了抑制.

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)所用的計(jì)算機(jī)硬件配置為酷睿雙核主頻2.0 GHz的CPU，8 G內(nèi)存；軟件配置為Windows XP操作系統(tǒng)、Visual C++程序編譯平臺(tái).

圖2 優(yōu)化結(jié)果顯示界面

網(wǎng)絡(luò)模型約束條件為12個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)和其他節(jié)點(diǎn)最多不超過(guò)4個(gè)連接.遺傳算法的群體規(guī)模最大為60，遺傳迭代的代數(shù)為200.

根據(jù)文中方法獲得的網(wǎng)絡(luò)優(yōu)化結(jié)果，如圖2所示.圖2中：左上位置是“最優(yōu)網(wǎng)絡(luò)連接視覺(jué)效果”顯示區(qū)，用于顯示最佳的網(wǎng)絡(luò)連接拓?fù)浣Y(jié)構(gòu)；右上位置是“參數(shù)設(shè)置區(qū)”，包括節(jié)點(diǎn)個(gè)數(shù)、節(jié)點(diǎn)負(fù)載、遺傳代數(shù)的設(shè)置；右下位置是“優(yōu)化排名”顯示區(qū)，用于將排名前5位的最小代價(jià)顯示出來(lái)，排名第一的最小代價(jià)，就對(duì)應(yīng)視覺(jué)效果顯示區(qū)的網(wǎng)絡(luò)連接拓?fù)浣Y(jié)構(gòu)；左下位置是3個(gè)按鈕，分別鏈接到3種網(wǎng)絡(luò)優(yōu)化算法(禁忌搜索法、傳統(tǒng)遺傳法、文中算法).

根據(jù)當(dāng)前的優(yōu)化結(jié)果可以看出：在文中算法的優(yōu)化后，整個(gè)網(wǎng)絡(luò)連接的最低代價(jià)為280.29，網(wǎng)絡(luò)連接的拓?fù)浣Y(jié)構(gòu)和初始狀態(tài)比，從4個(gè)分支更新到3個(gè)分支.第一個(gè)分支，根節(jié)點(diǎn)1到中間節(jié)點(diǎn)2，再?gòu)闹虚g節(jié)點(diǎn)2到中間節(jié)點(diǎn)3，最后從中間節(jié)點(diǎn)3到葉子節(jié)點(diǎn)4和葉子節(jié)點(diǎn)5；第二個(gè)分支，根節(jié)點(diǎn)1到中間節(jié)點(diǎn)6，再?gòu)闹虚g節(jié)點(diǎn)6到中間節(jié)點(diǎn)7，最后從中間節(jié)點(diǎn)7到葉子節(jié)點(diǎn)8；第三個(gè)分支，根節(jié)點(diǎn)1到中間節(jié)點(diǎn)12，再?gòu)闹虚g節(jié)點(diǎn)12到中間節(jié)點(diǎn)11，最后從中間節(jié)點(diǎn)11到葉子節(jié)點(diǎn)9和葉子節(jié)點(diǎn)10.

上述網(wǎng)絡(luò)連接結(jié)果的數(shù)學(xué)描述為

比較禁忌搜索法、傳統(tǒng)遺傳法、文中算法3種方法形成的優(yōu)化結(jié)果.3種方法優(yōu)化出的網(wǎng)絡(luò)最小代價(jià)排名前10位的結(jié)果,如表1所示.

從表1可知：禁忌搜索法獲得的網(wǎng)絡(luò)最小代價(jià)都比較高，其中排在第10位的最小代價(jià)為527.77，排在第1位的最小代價(jià)為333.85，從最小代價(jià)的絕對(duì)量上看，禁忌搜索法都劣于遺傳算法；傳統(tǒng)遺傳算法獲得的網(wǎng)絡(luò)最小代價(jià)，排在第10位的為411.36，排在第1位的為308.02，這種方法在最小代價(jià)為311.64之后，趨于收斂狀態(tài)，之后的最小代價(jià)與此值相差不大，存在過(guò)早收斂的問(wèn)題；文中算法排在第10位的最小代價(jià)為408.27，排在第1位的最小代價(jià)為280.29，同時(shí)，沒(méi)有出現(xiàn)過(guò)早收斂的問(wèn)題，可以獲得更小的網(wǎng)絡(luò)連接代價(jià).

進(jìn)一步對(duì)比禁忌搜索法、傳統(tǒng)遺傳法、文中算法3種方法的執(zhí)行時(shí)間[13]，如圖3所示.圖3中：t為時(shí)間；n為迭代次數(shù).由圖3可知：在迭代次數(shù)較低時(shí)，禁忌搜索法執(zhí)行時(shí)間較快，隨著迭代次數(shù)的增加，執(zhí)行時(shí)間增加非?？?文中算法和傳統(tǒng)遺傳算法相比，執(zhí)行時(shí)間相差不大，但文中算法的執(zhí)行時(shí)間增長(zhǎng)趨勢(shì)在放緩，這也體現(xiàn)出文中算法在執(zhí)行時(shí)間上的優(yōu)勢(shì)[14].

圖3 3種方法的執(zhí)行時(shí)間

表1 3種方法的優(yōu)化結(jié)果

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

以樹(shù)型網(wǎng)絡(luò)的優(yōu)化為切入點(diǎn)，對(duì)其拓?fù)浣Y(jié)構(gòu)和數(shù)學(xué)模型進(jìn)行研究.基于此，從個(gè)體編碼、種群初始化、種群進(jìn)化、適應(yīng)度函數(shù)計(jì)算等方面，構(gòu)建了一種可以優(yōu)化樹(shù)型網(wǎng)絡(luò)的遺傳算法.為了避免遺傳優(yōu)化過(guò)程的過(guò)早收斂，對(duì)適應(yīng)度函數(shù)進(jìn)行了改進(jìn)，可以增強(qiáng)弱勢(shì)個(gè)體在遺傳操作時(shí)被選擇的概率.實(shí)驗(yàn)結(jié)果表明：與禁忌搜索法和傳統(tǒng)遺傳法相比，文中算法可以獲得理想的網(wǎng)絡(luò)優(yōu)化結(jié)果，執(zhí)行時(shí)間隨著迭代次數(shù)的增加，增長(zhǎng)趨勢(shì)也在放緩.

[1] 鄧亮,趙進(jìn),王新.基于遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化[J].軟件學(xué)報(bào),2009,20(8):2269-2279.

[2] MICHAEL B,RICHARD M,SLYKE V.Backtracking algorithms for network reliability analysis[J].Annals of Discrete Mathematics,2012,1:221-235.

[3] 吳瓊,鄭士源,朱太球.基于列生成算法的集裝箱班輪運(yùn)輸網(wǎng)絡(luò)優(yōu)化[J].上海海事大學(xué)學(xué)報(bào),2014,35(1):29-35.

[4] GREINER D,WINTER G,EMPERADOR J M.Optimising frame structures by different strategies of genetic algorithms[J].Finite Elements in Analysis and Design,2001,37(5):381-442.

[5] AMORETTI M,GRAZIOLI A,ZANICHELLI F.Towards a formal approach to mobile cloud computing[C]∥Euromicro International Conference on Parallel, Distributed, and Network-Based Processing.Torino:IEEE Press,2014:743-750.

[6] BILGAIYAN S,SAGNIKA S,DAS M.A multi-objective cat swarm optimization algorithm for workflow scheduling in cloud computing environment[J].Advances in Intelligent Systems and Computing,2015,308(1):73-84.

[7] 趙云豐,付冬梅,尹怡欣,等.一種改進(jìn)的人工免疫網(wǎng)絡(luò)優(yōu)化算法及其性能分析[J].自然科學(xué)進(jìn)展,2009,19(4):434-445.

[8] 李柞泳,汪嘉楊,郭淳,等.基于蟻群算法的BP網(wǎng)絡(luò)優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,2010,30(6):1513-1517.

[9] 喬俊飛,逢澤芳,韓紅桂.基于改進(jìn)粒子群算法的污水處理過(guò)程神經(jīng)網(wǎng)絡(luò)優(yōu)化控制[J].智能系統(tǒng)學(xué)報(bào),2012,7(5):429-437.

[10] 樊富有,楊國(guó)武,樂(lè)千愷,等.基于量子遺傳算法的無(wú)線視頻傳感網(wǎng)絡(luò)優(yōu)化覆蓋算法[J].通信學(xué)報(bào),2015,36(6):22-27.

[11] 楊四海.TSP的等價(jià)解及其對(duì)免疫遺傳算法的干擾[J].華僑大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007,28(1):27-29.

[12] 莊健,楊清宇,杜海峰，等.一種高效的復(fù)雜系統(tǒng)遺傳算法[J].軟件學(xué)報(bào),2010,21(11):2790-2801.

[13] 都成娟,李和成.多下層分式雙層規(guī)劃問(wèn)題的改進(jìn)遺傳算法[J].計(jì)算機(jī)應(yīng)用,2012,32(11):2998-3001.

[14] 黃江波,付志紅.基于自適應(yīng)遺傳算法函數(shù)優(yōu)化與仿真[J].計(jì)算機(jī)仿真,2011,28(5):237-240.

(責(zé)任編輯： 黃曉楠 英文審校： 吳逢鐵)

Network Optimization Technique Using Genetic Algorithm

LI Guoqing， YIN Hongsheng

(School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou 221116, China)

Based on genetic algorithm， a network optimization method is proposed according to the topology and mathematical model of tree-shape network from the aspects of individual encoding, population initialization, population evolution, fitness function and so on. Experimental results show that the proposed method can further modify the fitness function， enhance the probability of the weak individuals′ being chosen， avoid the premature convergence of genetic algorithm， and reduce the execution time. The results show good networking optimization.

tree-shape network; network optimization; genetic algorithm; fitness function

1000-5013(2015)06-0663-04

10.11830/ISSN.1000-5013.2015.06.0663

2015-10-08

李國(guó)慶(1966-)，男，副教授，主要從事軟件工程、計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用技術(shù)的研究.E-mail:xzcxlgq@126.com.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61379100)

TP 312; TP 393

A