自適應(yīng)蟻群差分進(jìn)化算法

拓守恒

（陜西理工學(xué)院 計(jì)算機(jī)系，陜西 漢中723000）

0 引 言

差分進(jìn)化算法（differential evolution，DE）具有全局探索和局部開發(fā)的能力，容易和其他優(yōu)化搜索混合等特性［1］，在大規(guī)模復(fù)雜應(yīng)用研究中取得了較好的效果［2］，但也存在求解精度低等缺點(diǎn)，研究者們?yōu)榱颂岣逥E算法的性能，做了大量研究和改進(jìn)。文獻(xiàn)［3］按照個(gè)體適應(yīng)度的差異將個(gè)體分成不同的子種群，并針對(duì)不同的個(gè)體適應(yīng)度值采用不同的變異算子，以保證在加快算法收斂速度的同時(shí)有效地跳出局部極值點(diǎn)。文獻(xiàn)［4］提出一種基于多進(jìn)化模式協(xié)作的差分進(jìn)化算法，在每次迭代時(shí)，總是依次從3種模式中選取一種用于不同個(gè)體的進(jìn)化，從而提高算法的通用性。文獻(xiàn)［5］提出一種帶有隨機(jī)變異的動(dòng)態(tài)差分進(jìn)化算法，在這個(gè)算法中，兩種不同的變異策略DE/rand/1和DE/best/1通過(guò)線性遞減加權(quán)組合策略產(chǎn)生新的變異策略，以便動(dòng)態(tài)利用DE/rand/1和DE/best/1的優(yōu)點(diǎn)。文獻(xiàn)［6］提出了中心變異差分進(jìn)化算法，算法在每代變異時(shí)，選擇種群的一個(gè)中心個(gè)體作為基向量，根據(jù)參加變異的3個(gè)隨機(jī)個(gè)體向量間的函數(shù)適應(yīng)值的大小關(guān)系，確定差向量的方向。上述幾種算法都是針對(duì)差分進(jìn)化算法的某一方面的缺點(diǎn)進(jìn)行了改進(jìn)，或者針對(duì)某一具體問(wèn)題的應(yīng)用性改進(jìn)，但是往往通用性較差，難以在各種復(fù)雜變化的問(wèn)題中得到好的優(yōu)化效果。

為了提高DE算法的通用能力，受蟻群算法的啟發(fā)，本文提出一種基于蟻群算法的自適應(yīng)差分進(jìn)化算法。算法將目前已經(jīng)取得較好效果的變異算子綜合應(yīng)用于優(yōu)化問(wèn)題中，采用一種改進(jìn)的多模式并行差分變異策略，不同于文獻(xiàn)［4］，本文采用蟻群算法對(duì)差分變異算子的選擇概率進(jìn)行動(dòng)態(tài)調(diào)整，從而提高算法的優(yōu)化速度、穩(wěn)定性和通用性。

1 差分進(jìn)化算法

差分進(jìn)化（differential evolution，DE）［7］是由Storn和Price于1996年為求解切比雪夫多項(xiàng)式而提出的一種演化算法。DE算法用浮點(diǎn)矢量編碼在連續(xù)空間中進(jìn)行隨機(jī)搜索。DE主要采用2種進(jìn)化算子：差分變異算子和交叉算法進(jìn)化種群。由于DE算法采用實(shí)屬編碼，算法簡(jiǎn)單易用，所以在連續(xù)域優(yōu)化問(wèn)題種得到了廣泛應(yīng)用［8］。

1.1 差分變異算法性能特征分析

DE算法的關(guān)鍵是差分變異算子（differential operator，DO），目前有多種變異進(jìn)化模式，其一般表示形式為DE/x/u/y/z［4，9］，其中，x表示在差分變異算法中與差異向量進(jìn)行重組的基準(zhǔn)個(gè)體，基準(zhǔn)個(gè)體可以是：當(dāng)前個(gè)體Xi、隨機(jī)選取的個(gè)體Xrand或者是當(dāng)前群體的最優(yōu)個(gè)體Xbest；u表示差異向量的生成方式（rand－to－rand，rand－to－best），y表示參與重組的差異向量個(gè)數(shù)；z表示重組所采用的方式，主要有指數(shù)重組方式和二項(xiàng)式重組方式。本文選取下面4個(gè)取得較好優(yōu)化效果的變異進(jìn)化模式，并對(duì)其進(jìn)行改進(jìn)：

其中，λ，c1，c2是變異因子，在（0，1）上取值，r是（0，1）上的隨機(jī)數(shù)。

模式（1）是標(biāo)準(zhǔn)的差分變異進(jìn)化算法，從種群中隨機(jī)選擇個(gè)體Xr1、Xr2和Xr3。讓基準(zhǔn)個(gè)體Xr1和差向量Xr2－Xr3進(jìn)行重組生成新個(gè)體Vi。該算法全局搜索能力強(qiáng)、不容易陷入局部搜索，但收斂速度慢，求解精度低。

模式（3）以當(dāng)前種群中最優(yōu)個(gè)體Xgbest作為基準(zhǔn)個(gè)體，從準(zhǔn)確中隨機(jī)選擇4個(gè)個(gè)體生成差向量：Xr1－Xr2和Xr3－Xr4，特點(diǎn)是收斂速度快、求解精度高，但對(duì)于多模態(tài)優(yōu)化問(wèn)題，容易陷入局部最優(yōu)。

模式（2）以隨機(jī)個(gè)體Xr1作為基準(zhǔn)個(gè)體，用Xgbest（當(dāng)前種群中最優(yōu)個(gè)體）和Xpbest（隨機(jī)選擇的3個(gè)體中最優(yōu)個(gè)體）分別和隨著個(gè)體Xr2，Xr3作差，生成差向量：Xgbest－Xr1和Xpbest－Xr2。模式（4）借鑒粒子群優(yōu)化算法思想，以局部最優(yōu)個(gè)體Xpbest和種群最優(yōu)個(gè)體Xgbest作為基準(zhǔn)個(gè)體，隨機(jī)選擇2個(gè)體作差向量。模式（2）、模式（4）結(jié)合模式（1）和模式（3）的優(yōu)缺點(diǎn)，在全局收斂性、局部收斂性和收斂速度等方面做了均衡，增強(qiáng)了算法的通用性，但算法的魯棒性和求解精度任然較低。

上述變異進(jìn)化模式（2）～模式（4）各自雖然針對(duì)差分進(jìn)化算法的某一方面的缺點(diǎn)進(jìn)行了改進(jìn)，但對(duì)一些具體問(wèn)題進(jìn)行優(yōu)化時(shí)性能表現(xiàn)各異，其一種算法并不能對(duì)所有問(wèn)題通用有效，甚至同一問(wèn)題在維度不同時(shí)（比如100維和200維），同一算法的有效性也有很多差異。為了使差分進(jìn)化算法具有更強(qiáng)的通用性和魯棒性，文獻(xiàn)［4］隨機(jī)從3種變異進(jìn)化模式中隨機(jī)選取一種用于不同個(gè)體的進(jìn)化，雖然使得算法具有更強(qiáng)的通用性，但隨機(jī)選取變異模式使得收斂速度明顯降低。文獻(xiàn)［5］中，兩種不同的變異策略DE/rand/1和DE/best/1通過(guò)線性遞減加權(quán)組合策略產(chǎn)生新的變異策略，算法也僅僅是在全局收斂和局部收斂做了一點(diǎn)平衡。

本文提出一種利用蟻群算法動(dòng)態(tài)選擇差分變異進(jìn)化模式，算法根據(jù)個(gè)體進(jìn)化中各模式對(duì)優(yōu)化問(wèn)題的有效性對(duì)權(quán)值進(jìn)行動(dòng)態(tài)調(diào)整，從而提高算法的收斂速度、穩(wěn)定性和通用性。

2 算法描述

2.1 蟻群算法

蟻群算法（ant colony optimization algorithm，ACO）［10－11］也是新型仿生智能優(yōu)化算法。ACO算法通過(guò)模仿螞蟻尋食過(guò)程，利用螞蟻群在尋找食物過(guò)程中留下的信息素，探索一條到食物源的最佳路徑［12－13］。

2.2 基于蟻群算法的多模式差分變異

本文提出一種基于蟻群算法的多模式差分變異算法，使群體在進(jìn)化過(guò)程中根據(jù)各變異進(jìn)化算法的有效性動(dòng)態(tài)調(diào)整其選擇權(quán)值，個(gè)體在每代進(jìn)化中根據(jù)變異進(jìn)化模式（DO1，DO2，DO3，DO4）上的信息素（τ1，τ2，τ3，τ4）的大小采用輪盤賭選擇算法選擇變異算子，如圖1所示。

（1）信息素的更新

設(shè)置初始信息素τ1（t0）＝τ2（t0）＝τ3（t0）＝τ4（t0）＝0.25，這樣在進(jìn)化開始時(shí)，各變異算子（DO1，DO2，DO3，DO4）被選中的概率相同。

為了提高進(jìn)化效率，在個(gè)體的進(jìn)化過(guò)程中根據(jù)各變異算子對(duì)進(jìn)化所做的貢獻(xiàn)更新信息素。更新規(guī)則如下

圖1 基于蚊君算法的多模式差分進(jìn)化過(guò)程

式中：M——種群中個(gè)體的數(shù)量（螞蟻的數(shù)量），i＝1，2，…，M，ρ——信息素的蒸發(fā)率。max f、min f——當(dāng)前種群中個(gè)體的最大、最小適應(yīng)值。

（2）改進(jìn)的自適應(yīng)差分變異

本文提出一種自適應(yīng)的并行變異策略，改進(jìn)后變異算子可表示為：

其中，λ＝rand（1，D），rnd＝rand（1，D），rand（1，D）表示在（0，1）上產(chǎn)生一個(gè)D維的隨機(jī)向量。

br＝｛s1s2，…，sD｝＝round（rand（1，D）＊ex），，（u∈［0.8，1.5］，σ∈［0.7，2］），t是當(dāng)前進(jìn)化代數(shù)。maxT是最大進(jìn)化次數(shù)。D是維數(shù)，round（a）表示對(duì)a進(jìn)行4舍5入取整。“.×”表示向量對(duì)應(yīng)位的乘積，比如：（0.5，0.4，0.7，0.2）.×（1，0，1，0）＝（0.5，0，0.7，0）。

2.3 基于蟻群算法的自適應(yīng)差分進(jìn)化算法

算法步驟如下：

（1）參數(shù)初始化：設(shè)置種群大小 M，交叉概率p，信息素的蒸發(fā)率ρ＝0.2，變異參數(shù)（u，σ），最大迭代次數(shù)maxT，維數(shù)D，種群擁擠裁剪最小距離minL，進(jìn)化終止條件等參數(shù)。

（2）在可行解空間內(nèi)隨機(jī)初始化種群。

（3）計(jì)算個(gè)體的適應(yīng)度。

（4）利用本文提出的基于蟻群算法的差分變異算法對(duì)種群進(jìn)行一次變異進(jìn)化。

（5）利用交叉算子和選擇算子對(duì)種群進(jìn)行交叉和選擇。

（6）混沌搜索：選擇種群中最優(yōu)個(gè)體Xgbest進(jìn)行混沌迭代［14］，最大迭代次數(shù)設(shè)置為20。

（7）為了避免種群陷入局部搜索，采用種群擁擠距離裁剪策略［15］將種群中擁擠距離＜minL的部分個(gè)體剔除。

（8）產(chǎn)生新個(gè)體補(bǔ)充到種群，使得種群大小為保持為M。

（9）終止條件判斷。如果迭代次數(shù)達(dá)到規(guī)定最大值或獲得到理想的結(jié)果，則結(jié)束并輸出結(jié)果，否則轉(zhuǎn)到第（4）步繼續(xù)下一代進(jìn)化。

3 算法仿真分析

為了驗(yàn)證本文算法的性能，所使用的硬件環(huán)境為：方正Pentium 4CPU1.8GHz處理器，512MB內(nèi)存，算法編碼在MATLAB 2009（a）進(jìn)行編程實(shí)現(xiàn)。測(cè)試選取了5個(gè)標(biāo)準(zhǔn)benchmark高維多模態(tài)測(cè)試函數(shù)（f1－f5）作為測(cè)試用例，將算法測(cè)試結(jié)果與 MEDE［4］進(jìn)行比較。在所有測(cè)試函數(shù)中，設(shè)置參數(shù)u＝1.0，σ＝1.2。分別測(cè)試在維數(shù)D＝100和D＝200是的運(yùn)行結(jié)果，讓每個(gè)測(cè)試各自獨(dú)立運(yùn)行20次，并記錄下平均進(jìn)化次數(shù)（Gens），20次結(jié)果的最優(yōu)值（Best），20次測(cè)試的平均值（Mean）及標(biāo)準(zhǔn)方差（Std），見表1。

表1 本文算法與MEDE算法在函數(shù)f1－f5上的測(cè)試結(jié)果比較

在測(cè)試中，實(shí)驗(yàn)同時(shí)記錄了不同階段4種變異進(jìn)化模式上的信息素的變化過(guò)程，如圖2、圖3所示。通過(guò)圖2和圖3可以看出，對(duì)100維的函數(shù)f1，進(jìn)化初期，DO3獲得很高的信息素，DO1一直保持低水平的信息素，DO4在進(jìn)化后期效果明顯，信息素增加較快。而對(duì)函數(shù)f3和f1相比，變異進(jìn)化模式DO1和DO3出現(xiàn)了相反的變化過(guò)程。這說(shuō)明對(duì)于不同的問(wèn)題往往解決方式有差異，本文通過(guò)基于蟻群算法的自適應(yīng)多模式差分變異策略，使得算法面對(duì)具體問(wèn)題時(shí)，能夠根據(jù)進(jìn)化的需要自適應(yīng)的選擇變異模式，從而提高收斂速度和解的精度。

圖2 函數(shù)f1（100維）在進(jìn)化過(guò)程中信息素變化曲線

從表1中可以看出，除了測(cè)試函數(shù)f3之外，其余函數(shù)在100和200維都能夠在3000次以內(nèi)獲得高精度全局近似最優(yōu)解。觀察20次獨(dú)立運(yùn)行的結(jié)果發(fā)現(xiàn)，Best、Mean和Std在測(cè)試函數(shù)f1和f2上與MEDE算法比較接近，而測(cè)試函數(shù)f3－f5結(jié)果具有明顯優(yōu)勢(shì)，并且進(jìn)化代數(shù)和函數(shù)的評(píng)價(jià)次數(shù)也遠(yuǎn)低于MEDE。圖4是函數(shù)f3在200維時(shí)的進(jìn)化收斂曲線，由圖可以明顯看出，本文算法不論是收斂速度還是解的精度都明顯優(yōu)于MEDE算法。

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

傳統(tǒng)差分進(jìn)化算法存在收斂速度慢、魯棒性低和通用性差等特點(diǎn)，并且同一變異算子對(duì)不同問(wèn)題時(shí)，性能存在較大差異，甚至對(duì)同一函數(shù)在維度不同時(shí)也存在差異。為了提高算法的通用性，本文在傳統(tǒng)的差分進(jìn)化算法基礎(chǔ)上提出了一種基于蟻群算法的自適應(yīng)多模式差分進(jìn)化算法，算法根據(jù)各變異算子對(duì)當(dāng)前種群的進(jìn)化效果進(jìn)行動(dòng)態(tài)調(diào)整各變異模式上的信息素，使得各變異算子發(fā)揮其最大性能。

［1］CHI Yuan－cheng，F(xiàn)ANG Jie，CAI Guo－biao.Hybrid optimization algorithm based on differential evolution and particle swarm optimization［J］.Computer Engineering and Design，2009，30（12）：2963－2965（in Chinese）.［池元成，方杰，蔡國(guó)飆.基于差分進(jìn)化和粒子群優(yōu)化算法的混合優(yōu)化算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（12）：2963－2965.］

［2］TUO Shou－h(huán)eng，WANG Wen－yong.Self－adaptive differential evolution algorithm based on orthogonal and niche elite for highdimensional multi－modal optimization［J］，Journal of Computer Applications，2011，31（4）：1094－1098（in Chinese）.［拓守恒，汪文勇.求解高維多模優(yōu)化問(wèn)題的正交小生境自適應(yīng)差分演化算法［J］.計(jì)算機(jī)應(yīng)用，2011，31（4）：1094－1098.］

［3］LU Feng，GAO Li－qun.Adaptive differential evolution algorithm based on multiple subpopulation with parallel policy［J］.Journal of Northeastern University（Natural Science），2010，31（11）：1538－1541（in Chinese）.［盧峰，高立群.基于多種群的自適應(yīng)差分進(jìn)化算法［J］.東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，31（11）：1538－1541.］

［4］HE Yi－chao，WANG Xi－zhao.Convergent analysis and algorithmic improvement of differential evolution［J］.Journal of Software，2010，21（5）：875－885（in Chinese）.［賀毅朝，王熙照.差分進(jìn)化的收斂性分析與算法改進(jìn)［J］.軟件學(xué)報(bào)，2010，21（5）：875－885.］

［5］GAO Yue－lin，LIU Jun－mei.Dynamic differential evolution algorithm with random mutation［J］.Journal of Computer Applications，2009，29（10）：2719－2722（in Chinese）.［高岳林，劉俊梅.一種帶有隨機(jī)變異的動(dòng)態(tài)差分進(jìn)化算法［J］.計(jì)算機(jī)應(yīng)用，2009，29（10）：2719－2722.］

［6］CHI Yuan－cheng，F(xiàn)ANG Jie，CAI Guo－biao.Center mutation based differential evolution［J］.Systems Engineering and Electronics，2010，32（5）：1105－1108（in Chinese）.［池元成，方杰，蔡國(guó)飆.中心變異差分進(jìn)化算法［J］.系統(tǒng)工程與電子技術(shù)，2010，32（5）：1105－1108.］

［7］Storn R，Price K.Differential evolution－a simple and efficient heuristic for global optimization over continuous spaces［J］.Journal of Global Optimization，1997，11（4）：341－359.

［8］YANG Qi－wen，CAI Liang，XUE Yuancan.A survey of differential evolution algorithms［J］.Pattern Recognition and Artificial Intelligence，2008，21（4）：506－513（in Chinese）.［楊啟文，蔡亮，薛云燦.差分進(jìn)化算法綜述［J］.模式識(shí)別與人工智能，2008，21（4）：506－513.］

［9］Noman N，Iba H.Enhancing differential evolution performance with local search for high dimensional function optimization［C］.Beyer HG，et al.Proc of the Conf on Genetic and Evolutionary Computation.New York：ACM Press，2005：967－974.

［10］Zhang Jun，Hu Xiaomin，Tan X.Implementation of an ant colony optimization technique for job shop scheduling problem［J］.Transactions of the Institute of Measurement and Control，2006，28（1）：93－108.

［11］Cai Zhaoquan，Huang Han.Ant colony optimization algorithm based on adaptive weight and volatility parameters［C］.Shanghai：IEEE Press，2008：75－79.

［12］Li Yancang，Li Wanqing.Adaptive ant colony optimization algorithm based on Information entropy［J］.Foundation and Application，F(xiàn)undamental Informaticae，2007，77（3）：229－242.

［13］XIAO Jing，LI Liang－ping.Adaptive ant colony algorithm based on information entropy［J］.Computer Engineering and Design，2010，31（22）：4873－4876（in Chinese）.［肖菁，李亮平.基于信息熵調(diào)整的自適應(yīng)蟻群算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（22）：4873－4876.］

［14］DENG Ze－xi，LIU Xiao－Ji.Chaotic mutation differential evolution algorithm combined with niche［J］.Computer Engineering and Applications，2010，46（25）：31－33（in Chinese）.［鄧澤喜，劉曉冀.基于小生境的混沌變異差分進(jìn)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（25）：31－33.］

［15］Tseng Lin－Yu，Chen Chun.Multiple trajectory search for large scale global optimization［C］.IEEE Congress on Evolutionary Computation，2008：3052－3059.