一種求解連續(xù)空間約束優(yōu)化問題的蟻群算法

焦留成，邵創(chuàng)創(chuàng)，程志平

(鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州 450001)

一種求解連續(xù)空間約束優(yōu)化問題的蟻群算法

焦留成，邵創(chuàng)創(chuàng)，程志平

(鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州 450001)

借鑒蟻群算法和懲罰函數(shù)的思想提出了一種用于求解連續(xù)空間約束優(yōu)化問題的蟻群算法.應(yīng)用自適應(yīng)調(diào)整懲罰因子的懲罰函數(shù)法將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，再結(jié)合自適應(yīng)調(diào)整全局選擇因子和信息素?fù)]發(fā)系數(shù)的連續(xù)域蟻群算法，求解連續(xù)空間約束優(yōu)化問題.通過對基準(zhǔn)測試函數(shù)進(jìn)行編程求解，對比采用固定參數(shù)的蟻群算法求解結(jié)果，驗證了所提改進(jìn)算法的正確性和有效性.

連續(xù)空間;約束優(yōu)化;蟻群算法;懲罰函數(shù)

0 引言

蟻群算法是一種采用分布式控制，通過群體搜索策略和群體之間的信息交換尋找最優(yōu)路徑的優(yōu)化方法[1].并已在旅行商問題、二次分配問題和調(diào)度問題等一系列離散優(yōu)化問題上獲得了成功應(yīng)用[2].該算法的尋優(yōu)過程不依賴于優(yōu)化問題本身的嚴(yán)格數(shù)學(xué)性質(zhì)，對目標(biāo)函數(shù)無解析性要求[3].因此，可以將本質(zhì)上離散的蟻群算法應(yīng)用于求解連續(xù)空間的約束優(yōu)化問題，近年來也取得了一些成果[4].但這些研究大多是針對無約束或者約束條件僅為自變量取值范圍的優(yōu)化問題，而對約束條件一般的等式約束和不等式約束的研究很少.筆者借鑒蟻群算法和懲罰函數(shù)的思想設(shè)計了一種可以求解約束優(yōu)化問題的連續(xù)域蟻群算法.并通過對基準(zhǔn)測試函數(shù)的編程求解，驗證了算法能以很高的概率尋找到最優(yōu)解，誤差率很低.

1 約束優(yōu)化問題

約束優(yōu)化問題一般可以表達(dá)如下.

minf(X).

(1)

(2)

式中：X=(X1,X2,…,Xn)∈Rn為n維向量；f為待優(yōu)化函數(shù)；gi,hj為約束函數(shù).約束優(yōu)化問題的本質(zhì)是尋找到既滿足約束條件又能使目標(biāo)函數(shù)值達(dá)到最小的變量X*及其所對應(yīng)的函數(shù)值f(X*).

2 連續(xù)域蟻群算法

(3)

設(shè)定螞蟻i所處位置對應(yīng)的信息素強(qiáng)度為

T0(i)=exp(-f(Xi)).

(4)

(2)全局搜索.所有螞蟻在完成一次搜索后，將會有一只螞蟻搜索到本次循環(huán)的最優(yōu)解，然后其它螞蟻在各自的下一輪搜索中便會以一定的概率和步長轉(zhuǎn)向該處螞蟻.其轉(zhuǎn)移概率和步長分別為

(5)

(6)

(7)

式中：r=T(b)-T(i);λ=1/k為全局轉(zhuǎn)移步長參數(shù);k表示當(dāng)前迭代次數(shù);P0為全局選擇因子，將其設(shè)為迭代次數(shù)k的函數(shù)，迭代初期P0取較大值，那么非最優(yōu)解螞蟻X(i)(i=1,2,…,m,i≠b)向最優(yōu)解螞蟻X(b)轉(zhuǎn)移時，就會以較大概率選擇步長Xi+λ(Xb-Xi)，可加快算法尋優(yōu),迭代中期P0取較小值，螞蟻會以較大概率選擇步長Xi+rand(-1,1)·L(i)，會增強(qiáng)步長選擇的隨機(jī)性，進(jìn)而能擴(kuò)大搜索的解空間,迭代后期為加快搜索速度，P0還取較大值.

(3)局部搜索.上一輪循環(huán)中找到最優(yōu)解的螞蟻繼續(xù)在一個小鄰域內(nèi)進(jìn)行局部搜索，以期望能找到更優(yōu)解.假設(shè)螞蟻新找到的解X(u)其信息素強(qiáng)度為T(u)，比較新解和原來解的信息素強(qiáng)度，若新解比原來解的信息素強(qiáng)度大，則用新解位置取代原來解位置；否則，仍保留原來最優(yōu)解.表達(dá)式如下.

(8)

(9)

(10)

式中：step為局部搜索的初始步長;w為局部搜索步長，將其取為迭代次數(shù)的函數(shù)，隨迭代次數(shù)增加而減小，這樣在迭代后期步長就會變小以便能搜索到更精確解.式中wmax和wmin分別為步長更新參數(shù)上下限，其值一般取范圍為(1,1.4)和(0.2,0.8)的常數(shù)[5].

(4)信息素更新.螞蟻完成一次全局搜索和局部搜索后，將對其信息素進(jìn)行更新，更新規(guī)則如下.

T(i)=(1-ρ)T(i)+ΔT(i).

(11)

ρ=0.1·exp((k/K)·ln(9)).

(12)

式中：ΔT(i)=exp(-f(Xi))；ρ為信息素?fù)]發(fā)系數(shù)，將ρ設(shè)定為迭代次數(shù)的函數(shù)，迭代早期，ρ取較小值可以提高搜索的隨機(jī)性和全局搜索能力，隨著搜素的進(jìn)行，蟻群會越來越向最優(yōu)解螞蟻聚集，這時需要減少搜索的隨機(jī)性，加快收斂速度，那么，增大ρ的取值，增強(qiáng)信息的正反饋作用可以達(dá)到此目的.

3 懲罰函數(shù)法處理約束條件

3.1 經(jīng)典懲罰函數(shù)法

常用的懲罰函數(shù)法表達(dá)形式如下.

(13)

gi(X)=(hi(X))2,i=1,2,…,p.

(14)

(15)

(16)

其中，式(14)、(15)分別為等式和不等式約束條件，式(16)表示新構(gòu)造的適應(yīng)度函數(shù)，l=p+m，Mk>0為懲罰因子.當(dāng)約束條件被破壞時，至少會有一個i(1≤i≤l)，使gi(X)>0，從而p(X)>0.且約束條件被破壞得越厲害，p(X)取值就會越大，在M取為一定值時，F(xiàn)(X,M)=f(X)+Mp(X)也就越大，懲罰也就越厲害，體現(xiàn)了對于約束條件被破壞時的懲罰.反之，當(dāng)x滿足約束條件時，則gi(X)=0 (i=1,2,…,l)，p(X)=0，這時不管M取值多大，都有F(X,M)=f(X)，即懲罰函數(shù)對原目標(biāo)函數(shù)的求解無影響.

3.2 自適應(yīng)懲罰函數(shù)法

懲罰函數(shù)法因其方法簡單，易于編程實現(xiàn)而得到廣泛應(yīng)用.但也存在著一個主要缺陷：懲罰因子對收斂速度影響較大[6].若選取過小，則對不可行解的懲罰力度不夠，算法不易進(jìn)入可行域甚至可能收斂到不可行解：若選取過大，則懲罰力度過大，會降低算法的搜索效率.為了解決該問題，這里將懲罰因子設(shè)置為自變量的函數(shù).構(gòu)造懲罰函數(shù)如下.

(17)

i=1,2,…,p.

(18)

j=1,2,…,m.

(19)

構(gòu)造適應(yīng)度函數(shù)如下.

G(X)=f(X)+C(X)p(X).

(20)

(21)

懲罰因子Si(X)和Mj(X)隨著約束函數(shù)hi(X)和gj(X)的變化而變化，即懲罰因子會隨著算法迭代的進(jìn)行做自適應(yīng)調(diào)整.這能實現(xiàn)在違反約束程度大的段給予較大的懲罰，對違反程度小的段給予較小的懲罰，進(jìn)而能提高算法的求解效率.

4 算法求解步驟

結(jié)合上文連續(xù)域蟻群算法和自適應(yīng)懲罰函數(shù)法，求解連續(xù)空間約束優(yōu)化問題的具體步驟如下.

(1)根據(jù)具體問題確定最大循環(huán)次數(shù)K、螞蟻數(shù)目m、收斂精度ε、步長更新參數(shù)上下限wmax和wmin、局部搜索時的初始步長step、各變量取值范圍，按式(3)初始化蟻群位置.

(2)根據(jù)式(17)～(21)將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，并構(gòu)造適應(yīng)度函數(shù).

(3)根據(jù)式(4)計算各螞蟻所在位置對應(yīng)的信息素強(qiáng)度、適應(yīng)度值，找出信息素強(qiáng)度最大的螞蟻X(b).

(4)根據(jù)式(5)～(7)各螞蟻進(jìn)行全局搜索，更新各個螞蟻位置.

(5)最優(yōu)解螞蟻按式(8)～(10)進(jìn)行局部搜索，更新當(dāng)前最優(yōu)解螞蟻位置.

(6)所有螞蟻在完成本次循環(huán)后按式(11)、(12)進(jìn)行信息素更新，并保存當(dāng)前最優(yōu)解.

(7)如果所求的最優(yōu)解滿足要求或已經(jīng)達(dá)到最大迭代次數(shù)，則算法迭代結(jié)束，否則轉(zhuǎn)向步驟2繼續(xù)迭代運算.

5 仿真實驗及數(shù)據(jù)結(jié)果分析

筆者選取如下標(biāo)準(zhǔn)測試函數(shù)利用MATLAB軟件進(jìn)行算法的仿真實驗.

(22)

由于該函數(shù)為開口向上的曲面，如果直接求解該函數(shù)的最小值，則螞蟻都會分布在曲面底部，被曲面遮蓋，故筆者采用求解-f(x1,x2)最大值的方式，這樣螞蟻的最初和最終位置分布都會覆蓋在曲面上，對比更明晰.將采用固定參數(shù)蟻群算法對比改進(jìn)后自適應(yīng)調(diào)整參數(shù)值的蟻群算法用MATLAB軟件分別編程求解.采用同樣的螞蟻個數(shù)m=100，最大迭代次數(shù)K=1 000.改進(jìn)前固定參數(shù)p0=0.2，ρ=0.8，m=100,改進(jìn)后自適應(yīng)調(diào)整參數(shù)的步長更新參數(shù)上下限分別取wmax=1.2和wmin=0.6，局部搜索的初始步長step=0.1·rand(1).分別運行該算法程序30次，求得螞蟻最初分布位置、最終分布位置、最優(yōu)函數(shù)值隨迭代次數(shù)的變化趨勢如圖1～3所示.分別記錄每次迭代時間和求得的解，取其中最優(yōu)解、獲得最優(yōu)解次數(shù)、最差解、獲得最差解次數(shù)和計算的平均解、平均時間以及誤差率制作表1.

圖1 螞蟻的最初分布位置Fig.1 Initial location of ants

圖2 螞蟻的最終分布位置Fig.2 Final location of ants

圖3 最優(yōu)函數(shù)值隨迭代次數(shù)變化趨勢Fig.3 The optimal function values of chang trends with the iteration 表1 蟻群算法優(yōu)化結(jié)果Tab.1 Ant colony algorithm results

項目改進(jìn)前改進(jìn)后最優(yōu)解-f(0.5,0.25)=-0.2500-f(0.5,0.25)=-0.2500最優(yōu)解的個數(shù)1025最差解-f(0.4858,0.2692)=-0.3746-f(0.4986,0.2512)=-0.2514最差解的個數(shù)11平均解-f=-0.2896-f=-0.2506平均時間7.36725.0961平均誤差率3.27%0.24%

由上表可知，筆者設(shè)計的蟻群算法在求解基準(zhǔn)測試函數(shù)所求各結(jié)果明顯優(yōu)于改進(jìn)前采用固定參數(shù)的蟻群算法.螞蟻最初比較分散地分布在解空間內(nèi)，程序運行結(jié)束后會比較明顯地聚集在最優(yōu)點附近，對比明晰.改進(jìn)后算法求得的平均解-f=-0.250 6，即求得的滿足約束條件的函數(shù)最小值為f=0.250 6，平均誤差率很低.

6 結(jié)論

在借鑒前人研究蟻群算法求解優(yōu)化問題的基礎(chǔ)上，設(shè)計了一種用于求解連續(xù)空間約束優(yōu)化問題的蟻群算法，并給出了算法的較詳細(xì)步驟.在MATLAB軟件上分別編程采用固定參數(shù)的蟻群算法和采用自適應(yīng)調(diào)整參數(shù)的蟻群算法求解一個基準(zhǔn)測試函數(shù)，對比求得的結(jié)果，驗證了改進(jìn)后的算法具有更強(qiáng)的尋優(yōu)能力.

[1] 原思聰，劉道華，江祥奎，等.基于蟻群算法的多維有約束函數(shù)優(yōu)化研究[J].計算機(jī)應(yīng)用研究，2008,25(6)：1682-1684.

[2] 劉喜恩.用于連續(xù)空間尋優(yōu)的一種蟻群算法[J].計算機(jī)應(yīng)用，2009,29(10)：2744-2747.

[3] 李朝輝，梁昔明.連續(xù)域蟻群算法的改進(jìn)研究及在參數(shù)估計中的應(yīng)用[D].長沙：中南大學(xué)信息科學(xué)與工程學(xué)院，2011.

[4] SOCHA K, DORIGO M. Ant colony optimization for continuous domains [J]. European Journal of Operational Research (S0377-2217), 2008, 185(3): 1155-1173.

[5] 賈延臣，劉長良.基于連續(xù)空間優(yōu)化問題的蟻群算法及其應(yīng)用研究[D].保定：華北電力大學(xué)控制與計算機(jī)工程學(xué)院，2008.

[6] 雷韻平，成良玉.一種改進(jìn)的蟻群算法及其在電機(jī)優(yōu)化設(shè)計中的應(yīng)用研究[D].廣州：中山大學(xué)信息科學(xué)與技術(shù)學(xué)院，2010.

Ant Colony Algorithm for Solving Continuous Space Constrained Optimization Problems

JIAO Liu-cheng, SHAO Chuang-chuang, CHENG Zhi-ping

(School of Electrical Engineering, Zhengzhou University, Zhengzhou 450001, China)

With ideas of ant colony algorithm and penalty function, an ant colony algorithm, which can solve continuous space constrained optimization problems, was proposed. We adopted the penalty function method of adjusting its value of adaptively to transform the constrained optimization problems into unconstrained optimization problems, and then combined with the continuous domain ant colony algorithm of adjusting its global selection factor and the value of the pheromone evaporation factor adaptively to solve the continuous space constrained optimization problems. And through programming solution of one benchmarking function, we compared the results with those of using fixed parameters ant colony algorithm, it was verified with correctness and effectiveness.

continuous space; constrained optimization; ant colony algorithm; penalty function method

2014-09-18；

2014-11-20

國家自然科學(xué)基金資助項目(61075071); 河南省教育廳自然科學(xué)基金資助項目(14A413008);鄭州市科技局資助項目(131PPTGG409-5)

程志平(1974-)，男，河南商水人，鄭州大學(xué)副教授，博士，主要從事直線電機(jī)建模與控制研究，E-mail:zpcheng@zzu.edu.cn.

1671-6833(2015)01-0020-04

TP18

A

10.3969/j.issn.1671-6833.2015.01.005