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

李國慶, 尹洪勝

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

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

李國慶, 尹洪勝

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

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

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

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

1 樹型網(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)、樹型拓?fù)浣Y(jié)構(gòu)等.樹型拓?fù)浣Y(jié)構(gòu)從總線型拓?fù)浣Y(jié)構(gòu)演變而來，不僅易于終端擴展，也有利于故障隔離.一般性的樹型網(wǎng)絡(luò)，如圖1所示.

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

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

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

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

如果用{li,j}表示一個樹型網(wǎng)絡(luò)的所有連接集合，用{ci，j}表示所有連接對應(yīng)的連接代價集合，則樹型網(wǎng)絡(luò)的優(yōu)化問題就變成是對{ci，j}集合的優(yōu)化問題，對應(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é)：個體編碼、種群初始化、種群進化(選擇、交叉、變異)、計算適應(yīng)度函數(shù).

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

[1] 鄧亮,趙進,王新.基于遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化[J].軟件學(xué)報,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] 吳瓊,鄭士源,朱太球.基于列生成算法的集裝箱班輪運輸網(wǎng)絡(luò)優(yōu)化[J].上海海事大學(xué)學(xué)報,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] 趙云豐,付冬梅,尹怡欣,等.一種改進的人工免疫網(wǎng)絡(luò)優(yōu)化算法及其性能分析[J].自然科學(xué)進展,2009,19(4):434-445.

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

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

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

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

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

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

[14] 黃江波,付志紅.基于自適應(yīng)遺傳算法函數(shù)優(yōu)化與仿真[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

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

國家自然科學(xué)基金資助項目(61379100)

TP 312; TP 393

A