畢曉君，張 磊

（哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱150001）

基于自適應(yīng)ε的約束優(yōu)化算法

畢曉君，張 磊

（哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱150001）

針對(duì)目前約束優(yōu)化算法易陷入局部最優(yōu)和魯棒性不好等缺點(diǎn)，提出基于自適應(yīng)ε的約束優(yōu)化算法。首先，通過(guò)改進(jìn)的個(gè)體比較準(zhǔn)則，充分利用優(yōu)秀不可行個(gè)體的有效信息，加大對(duì)搜索空間的探索力度，從而提高種群多樣性；其次，提出自適應(yīng)ε調(diào)整策略，平衡目標(biāo)函數(shù)和約束違反度之間的關(guān)系，進(jìn)而更加合理地進(jìn)行個(gè)體比較。對(duì)13個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的對(duì)比實(shí)驗(yàn)表明，本文算法不僅能夠以較高精度收斂到全局最優(yōu)解，而且魯棒性較好。

約束優(yōu)化算法；個(gè)體比較準(zhǔn)則；ε約束；自適應(yīng)

0 引 言

約束優(yōu)化問(wèn)題是一類(lèi)廣泛存在于現(xiàn)實(shí)世界中但又較難求解的問(wèn)題，涉及到函數(shù)優(yōu)化［1］、圖像處理［2］、網(wǎng)絡(luò)通信［3］等諸多領(lǐng)域，對(duì)其研究具有重要的理論和實(shí)際意義。目前，一般采用約束優(yōu)化算法處理約束優(yōu)化問(wèn)題，而有效的約束優(yōu)化算法必須在處理約束條件的同時(shí)能夠收斂到全局最優(yōu)解。

傳統(tǒng)的全局優(yōu)化算法如遺傳算法［4］、粒子群算法［5］、差分進(jìn)化算法［6－7］、免疫克隆算法［8］等必須結(jié)合約束處理技術(shù)才能處理約束優(yōu)化問(wèn)題。約束處理技術(shù)作為約束優(yōu)化算法中非常重要的組成部分，常用方法有懲罰函數(shù)法［9］、Deb準(zhǔn)則［10］、隨機(jī)排序法［11］、多目標(biāo)法［12］和ε約束［13］等。研究表明，基于ε約束的優(yōu)化算法在處理約束優(yōu)化問(wèn)題上取得良好的效果，但在收斂精度和魯棒性上仍需進(jìn)一步提高。文獻(xiàn)［14］提出一種基于分解的ε約束優(yōu)化算法，該算法通過(guò)帶權(quán)系數(shù)的切比雪夫計(jì)算適應(yīng)度值，利用ε約束選擇個(gè)體，但是該算法的魯棒性不好。文獻(xiàn)［15］提出一種基于偏好的ε約束優(yōu)化算法，該算法通過(guò)引入偏好信息減少計(jì)算量，但易陷入局部最優(yōu)。文獻(xiàn)［16］提出一種ε約束生物地理學(xué)優(yōu)化算法，該算法有效地提高了收斂速度和精度，但缺乏與ε約束優(yōu)化算法的實(shí)驗(yàn)對(duì)比。文獻(xiàn)［17］提出一種基于排序的ε約束差分進(jìn)化算法，該算法有效減少了適應(yīng)度評(píng)價(jià)次數(shù)，但是收斂精度較低。文獻(xiàn)［18］提出一種εDE算法，但是該算法的收斂精度不高，并且適應(yīng)度評(píng)價(jià)次數(shù)很多。由于約束優(yōu)化問(wèn)題存在各種復(fù)雜約束條件（線性、非線性、不等式、等式），可行域與不可行域的拓?fù)浣Y(jié)構(gòu)變得很復(fù)雜，使得算法兼顧多樣性和收斂性的難度很大，特別是對(duì)于等式約束條件較多和決策變量維數(shù)較高的約束優(yōu)化問(wèn)題，需要進(jìn)一步提高對(duì)搜索空間的探索和開(kāi)發(fā)能力，才能更好地協(xié)調(diào)種群的多樣性和收斂性。因此，急需研究開(kāi)發(fā)更為有效的方法進(jìn)行個(gè)體評(píng)價(jià)與比較，在保持多樣性的同時(shí)，能夠引導(dǎo)算法搜索滿(mǎn)足約束條件的全局最優(yōu)解。

針對(duì)上述問(wèn)題，本文提出一種個(gè)體比較準(zhǔn)則和自適應(yīng)ε參數(shù)調(diào)整策略，構(gòu)成基于自適應(yīng)ε的約束優(yōu)化算法（selfadaptiveεconstrained optimization algorithm，εCOA）。改進(jìn)的個(gè)體比較準(zhǔn)則能夠充分利用優(yōu)秀不可行個(gè)體信息，加大對(duì)搜索區(qū)域的探索能力，避免陷入局部最優(yōu)；同時(shí)，采用自適應(yīng)ε參數(shù)調(diào)整策略，更好地平衡可行個(gè)體和不可行個(gè)體的關(guān)系，進(jìn)一步提高算法的搜索效率和魯棒性。

1 約束優(yōu)化問(wèn)題描述及相關(guān)定義

不失一般性，以最小化問(wèn)題為例，約束優(yōu)化問(wèn)題如式（1）所示。

式中，X＝（x1，x2，…，xn）∈Rn是n維決策變量，每一維xi∈［li，ui］，i＝1，2，…，n；f（X）是目標(biāo)函數(shù)；gi（X）是第i個(gè)不等式約束條件；p是不等式約束條件個(gè)數(shù)；hj（X）是第j個(gè)等式約束條件；q是等式約束條件個(gè)數(shù)。與其他文獻(xiàn)一樣，本文將等式約束條件轉(zhuǎn)化為不等式約束條件［19］，具體如式（2）所示。

式中，δ是很小的實(shí)數(shù)，本文參考文獻(xiàn)［19］取值為0.000 1。

將滿(mǎn)足所有約束條件的個(gè)體空間S稱(chēng)為式（1）的可行域，否則稱(chēng)為不可行域，S?Rn。包括在S中的個(gè)體X稱(chēng)為可行個(gè)體，否則稱(chēng)為不可行個(gè)體。

約束違反函數(shù)如式（3）所示，其大小稱(chēng)為約束違反度。

2 相關(guān)文獻(xiàn)回顧

Deb準(zhǔn)則［10］是一種有效的個(gè)體比較機(jī)制，因其操作簡(jiǎn)單和無(wú)需設(shè)置參數(shù)受到很大的關(guān)注，它由3條準(zhǔn)則構(gòu)成：

（1）兩個(gè)都是可行個(gè)體，目標(biāo)函數(shù)小的獲勝；

（2）兩個(gè)都是不可行個(gè)體，約束違反度小的獲勝；

（3）一個(gè)是可行個(gè)體，另一個(gè)是不可行個(gè)體，可行個(gè)體獲勝。

但是，Deb準(zhǔn)則存在一個(gè)明顯缺陷，它強(qiáng)調(diào)可行個(gè)體一定優(yōu)于不可行個(gè)體，導(dǎo)致種群容易陷入早熟收斂。

文獻(xiàn)［18］在Deb準(zhǔn)則基礎(chǔ)上提出一種改進(jìn)的個(gè)體比較準(zhǔn)則，在一定程度上利用了不可行個(gè)體，主要由3條準(zhǔn)則組成：

（1）兩個(gè)都是可行個(gè)體，目標(biāo)函數(shù)小的獲勝；

（2）兩個(gè)都是不可行個(gè)體，約束違反度小的獲勝；

（3）一個(gè)是可行個(gè)體，另一個(gè)是不可行個(gè)體：如果不可行個(gè)體的約束違反度小于等于ε，目標(biāo)函數(shù)小的獲勝；如果不可行個(gè)體的約束違反度大于ε，可行個(gè)體獲勝。

其中，對(duì)于ε設(shè)置如下：

式中，gen為進(jìn)化代數(shù)；ε（0）＝1。

但是，該方法對(duì)于一些復(fù)雜的約束優(yōu)化問(wèn)題仍存在收斂精度不高的問(wèn)題，歸其原因還是由于對(duì)搜索空間的探索利用能力不足和參數(shù)調(diào)整的缺陷，導(dǎo)致種群多樣性下降。

3 基于自適應(yīng)ε的約束差分進(jìn)化算法

通過(guò)深入研究分析，本文算法從個(gè)體比較準(zhǔn)則、ε設(shè)置兩個(gè)方面進(jìn)行改進(jìn)，綜合提高全局搜索能力。首先，改進(jìn)的個(gè)體比較準(zhǔn)則不只是基于約束違反度來(lái)比較不可行個(gè)體，而是較好地兼顧目標(biāo)函數(shù)和約束違反度，使得進(jìn)化朝著全局最優(yōu)方向進(jìn)行。其次，為了進(jìn)一步提高算法魯棒性，設(shè)計(jì)新的自適應(yīng)ε參數(shù)調(diào)整策略，進(jìn)而有效合理地比較個(gè)體。

3.1 改進(jìn)的個(gè)體比較準(zhǔn)則

對(duì)于約束優(yōu)化問(wèn)題，其中最為關(guān)鍵的就是要通過(guò)有效的方法在可行個(gè)體之間、不可行個(gè)體之間以及可行個(gè)體與不可行個(gè)體之間進(jìn)行評(píng)價(jià)與比較，從而引導(dǎo)算法搜索滿(mǎn)足約束條件的全局最優(yōu)解。不可行個(gè)體在進(jìn)化中對(duì)維持種群多樣性起著非常重要的作用，但目前的方法對(duì)于不可行個(gè)體利用不足，導(dǎo)致算法容易陷入局部最優(yōu)。為了充分利用優(yōu)秀不可行個(gè)體的有效信息，加強(qiáng)對(duì)搜索區(qū)域的探索能力，保持進(jìn)化種群的多樣性，本文提出一種改進(jìn)的個(gè)體比較準(zhǔn)則，具體形式為：

準(zhǔn)則1 兩個(gè)都是可行個(gè)體，目標(biāo)函數(shù)值小的個(gè)體獲勝。

準(zhǔn)則2 一個(gè)是可行個(gè)體，另一個(gè)是不可行個(gè)體，分兩種情形進(jìn)行討論：（情形1）不可行個(gè)體的約束違反度小于等于ε，基于目標(biāo)函數(shù)值比較，目標(biāo)函數(shù)值小的個(gè)體獲勝；（情形2）不可行個(gè)體的約束違反度大于ε，可行個(gè)體獲勝。

準(zhǔn)則3 兩個(gè)都是不可行個(gè)體時(shí)，分3種情形進(jìn)行討論：（情形1）兩個(gè)個(gè)體的約束違反度都小于等于ε，目標(biāo)函數(shù)值小的個(gè)體獲勝；（情形2）一個(gè)個(gè)體的約束違反度小于等于ε，另一個(gè)體的約束違反度大于ε，約束違反度小的個(gè)體獲勝；（情形3）兩個(gè)個(gè)體的約束違反度都大于ε，以較大概率Ps基于約束違反度比較，約束違反度小的個(gè)體獲勝，以較小概率1－Ps基于目標(biāo)函數(shù)值比較，目標(biāo)函數(shù)值小的個(gè)體獲勝。

上述個(gè)體比較準(zhǔn)則可以轉(zhuǎn)化為如式（5）所示形式。

對(duì)于準(zhǔn)則1：目標(biāo)函數(shù)較優(yōu)個(gè)體進(jìn)入下一代種群，有利于保證種群向更優(yōu)可行方向進(jìn)化。對(duì)于準(zhǔn)則2：保留約束違反度小、目標(biāo)函數(shù)值小的優(yōu)秀不可行個(gè)體，有利于加大對(duì)搜索空間的探索范圍，從而提高種群多樣性。對(duì)于準(zhǔn)則3：實(shí)際中有很多復(fù)雜約束優(yōu)化問(wèn)題，其可行域十分狹小，種群進(jìn)化中會(huì)產(chǎn)生很多不可行個(gè)體，所以大多數(shù)情況都是不可行個(gè)體之間的比較。情形1、情形2能夠保留約束違反度和目標(biāo)函數(shù)同時(shí)較優(yōu)的不可行個(gè)體，更大程度地保留了不可行個(gè)體的有效信息，進(jìn)而能夠更好地向全局最優(yōu)方向收斂。情形3以較小概率1－Ps基于目標(biāo)函數(shù)比較個(gè)體，從而保留極少數(shù)約束違反度較大的個(gè)體，這樣可以進(jìn)一步加強(qiáng)對(duì)搜索空間的探索。同時(shí)這些不可行個(gè)體只會(huì)存在于極少數(shù)的進(jìn)化代數(shù)中，而不會(huì)影響整體的進(jìn)化過(guò)程。

上述準(zhǔn)則為什么能夠收斂到全局最優(yōu)解？首先，準(zhǔn)則1中可行個(gè)體利用目標(biāo)函數(shù)比較，可以讓進(jìn)化在可行域內(nèi)朝著更優(yōu)可行方向進(jìn)行；其次，準(zhǔn)則2、準(zhǔn)則3保證種群中存在一定的優(yōu)秀不可行個(gè)體，不僅有利于加強(qiáng)種群多樣性，而且進(jìn)化從不可行域向可行域進(jìn)行。所以改進(jìn)的個(gè)體比較準(zhǔn)則可以讓種群在可行域和不可行域同時(shí)向全局最優(yōu)方向進(jìn)化，從而保證收斂性。

3.2 ε水平設(shè)置

從式（4）給出的ε參數(shù)設(shè)置方法可以看出，ε隨著進(jìn)化代數(shù)的增加呈等比例減少，并且只單純地依賴(lài)進(jìn)化代數(shù)，忽略了種群的整體信息，這樣將直接導(dǎo)致ε對(duì)個(gè)體選擇的壓力不準(zhǔn)確，不能很好地平衡目標(biāo)函數(shù)和約束違反度的關(guān)系。當(dāng)進(jìn)化初期不可行個(gè)體較多時(shí)，ε過(guò)大使得往往只是基于目標(biāo)函數(shù)比較個(gè)體，導(dǎo)致較多進(jìn)化代數(shù)后種群很難到達(dá)可行域，甚至可能停滯在不可行域；而ε過(guò)小將導(dǎo)致不能很好利用優(yōu)秀不可行個(gè)體，目標(biāo)函數(shù)較優(yōu)而約束違反度較小的不可行個(gè)體無(wú)法得到保留，勢(shì)必會(huì)影響種群的多樣性。同時(shí)，ε的初始設(shè)置取常數(shù)1將直接影響不能有效處理不同問(wèn)題，并對(duì)進(jìn)化過(guò)程產(chǎn)生不利影響。因此，單純依據(jù)進(jìn)化代數(shù)來(lái)調(diào)整ε還存在較大的缺陷，每一代的ε應(yīng)當(dāng)根據(jù)種群的整體約束違反度，針對(duì)不同問(wèn)題可行域的變化，進(jìn)行自適應(yīng)調(diào)整。在可行域較小時(shí)產(chǎn)生相對(duì)較大的ε，從而擴(kuò)大搜索區(qū)域，增大跳出局部最優(yōu)的可能；反之，產(chǎn)生較小ε，增強(qiáng)種群開(kāi)發(fā)能力，加快種群收斂速度。基于上述思想，本文提出如式（6）、式（7）所示的ε自適應(yīng)調(diào)整策略。

式中，Te為截?cái)噙M(jìn)化迭代次數(shù)，用于控制ε（t）的大小。Te不宜過(guò)大也不宜過(guò)小，過(guò)大時(shí)將會(huì)使得在進(jìn)化后期種群中還存在很多不可行個(gè)體，這勢(shì)必會(huì)影響種群最終收斂到全局可行解；而過(guò)小時(shí)，第3.1節(jié)中的個(gè)體比較準(zhǔn)則將會(huì)非常近似于Deb準(zhǔn)則，從而使得在進(jìn)化前期就排除了大量不可行個(gè)體，出現(xiàn)類(lèi)似Deb準(zhǔn)則容易陷入局部最優(yōu)的缺點(diǎn)。α＝αmin＋λ×（αmax－αmin）；N為種群大??；λ＝Num（feasible）／N，λ表示種群中可行個(gè)體在整個(gè)種群中的比例。在進(jìn)化過(guò)程中不再單純依靠進(jìn)化代數(shù)，而是利用整個(gè)種群的約束違反度設(shè)置初始ε。同時(shí)根據(jù)可行個(gè)體所占比例，對(duì)ε進(jìn)行自適應(yīng)調(diào)整，有效平衡個(gè)體的目標(biāo)函數(shù)和約束違反度，提高算法搜索效率。

3.3 本文算法流程

εCOA采用差分進(jìn)化算法［17］作為進(jìn)化機(jī)制，主要流程如下：

步驟1 初始化。設(shè)置初始參數(shù)包括種群規(guī)模N、縮放因子F、交叉因子CR、最大迭代次數(shù)Gmax。利用隨機(jī)方法初始化種群，每個(gè)個(gè)體Xi＝（x1，x2，…，xn）的第j維分量xj＝lj＋rand（）×uj（j＝1，2，…，n；i＝1，2，…，N）。其中，rand為［0，1］的隨機(jī)數(shù)；xj∈［lj，uj］。

步驟2 判斷終止條件。如果達(dá)到最大迭代次數(shù)Gmax，算法結(jié)束；否則，轉(zhuǎn)到步驟3。

步驟3 變異操作。按式Vi（t＋1）＝Xr1（t）＋F×（Xr2（t）－Xr3（t））進(jìn)行變異操作。其中，t為進(jìn)化代數(shù)；i，r1，r2，r3為1～N上互不相等的正整數(shù)。

步驟4 交叉操作。按

進(jìn)行交叉操作。其中，t為進(jìn)化代數(shù)；vij為個(gè)體Vi的第j維分量；xij為個(gè)體Xi的第j維分量；rand（j）為［0，1］的隨機(jī)數(shù)。

步驟5 選擇操作。按第3.1節(jié)方法比較個(gè)體。

步驟6 按式（6）、式（7）更新ε（t）。

步驟7 t＝t＋1，返回到步驟2。

4 實(shí)驗(yàn)及分析

本文所有實(shí)驗(yàn)在硬件配置為Intel Pentium，CPU：G620、4GB內(nèi)存、主頻2.6GHz的計(jì)算機(jī)上進(jìn)行，程序采用Matlab R2010編寫(xiě)。

為了驗(yàn)證本文算法的有效性和先進(jìn)性，采用文獻(xiàn)［19］中的13個(gè)國(guó)際通用測(cè)試函數(shù)（g01～g13）進(jìn)行測(cè)試。在有效性方面與文獻(xiàn)［18］進(jìn)行了對(duì)比實(shí)驗(yàn)，在先進(jìn)性方面，與目前先進(jìn)的ISR算法［11］、εRDE算法［17］、SMES算法［20］進(jìn)行了對(duì)比實(shí)驗(yàn)。

本文算法的參數(shù)均通過(guò)大量實(shí)驗(yàn)和一定的經(jīng)驗(yàn)得出。其中對(duì)于取值N＝50、F＝0.7、CR＝0.8（參考文獻(xiàn)［13］），取值Gmax＝10 000（參考文獻(xiàn)［18］），Ps為（0.9 1.0）上的隨機(jī)數(shù)，αmin＝3.5，αmax＝9.5。而對(duì)于關(guān)鍵參數(shù)取值Te＝1 000則是通過(guò)實(shí)驗(yàn)得出，具體討論見(jiàn)第4.3節(jié)。

4.1 有效性驗(yàn)證

為了驗(yàn)證εCOA的有效性，與文獻(xiàn)［18］進(jìn)行了對(duì)比實(shí)驗(yàn)，測(cè)試項(xiàng)目包括最優(yōu)值、最差值、平均值及標(biāo)準(zhǔn)差。對(duì)于每個(gè)測(cè)試函數(shù)在相同條件下算法均獨(dú)立運(yùn)行50次，仿真實(shí)驗(yàn)結(jié)果如表1所示。εCOA的最大評(píng)價(jià)次數(shù)為500 000，εDE的最大評(píng)價(jià)次數(shù)為2 000 000。

表1 εCOA與εDE對(duì)比實(shí)驗(yàn)結(jié)果

由表1可以看出，εCOA較εDE具有明顯的優(yōu)勢(shì)。εCOA和εDE在11個(gè)測(cè)試函數(shù)（g02、g13除外）都一致達(dá)到全局最優(yōu)解，但εCOA的標(biāo)準(zhǔn)差幾乎均優(yōu)于εDE，說(shuō)明εCOA的收斂精度更高；同時(shí)，在函數(shù)g02上，εCOA較εDE的平均值和標(biāo)準(zhǔn)差都更小，說(shuō)明εCOA收斂精度更高，魯棒性也更好；在函數(shù)g13上，εCOA較εDE平均值更小，標(biāo)準(zhǔn)差相當(dāng)；并且εCOA最大評(píng)價(jià)次數(shù)只有εDE的25%，說(shuō)明εCOA在運(yùn)行時(shí)間具有很大的優(yōu)勢(shì)。從以上分析可以得出，εCOA較εDE具有更好的約束優(yōu)化性能。

4.2 先進(jìn)性驗(yàn)證

為了進(jìn)一步驗(yàn)證εCOA的先進(jìn)性，將εCOA與ISR算法［11］、εRDE［17］算法以及SMES算法［20］進(jìn)行了對(duì)比實(shí)驗(yàn)，對(duì)每個(gè)測(cè)試函數(shù)在相同條件下獨(dú)立運(yùn)行50次，仿真實(shí)驗(yàn)結(jié)果如表2所示。

從表2可以看出，εCOA在11個(gè)測(cè)試函數(shù)（g02、g13除外）50次獨(dú)立運(yùn)行時(shí)一致達(dá)到全局最優(yōu)解；ISR只在9個(gè)測(cè)試函數(shù)（g02、g07、g10、g13除外）上一致達(dá)到全局最優(yōu)解，ISR在g13上的均值和標(biāo)準(zhǔn)差略?xún)?yōu)于εCOA，由于相差較小并且獨(dú)立運(yùn)行次數(shù)只有30次，所以ISR和εCOA在處理g13時(shí)能力相當(dāng)，而在g02、g07、g10上，εCOA的最差值、平均值和標(biāo)準(zhǔn)差均優(yōu)于ISR，說(shuō)明εCOA具有更高的收斂精度和更好的魯棒性；SMES只在7個(gè)測(cè)試函數(shù)上一致達(dá)到全局最優(yōu)解（g02、g05、g06、g07、g09、g13除外），εCOA幾乎在所有測(cè)試函數(shù)上的性能均優(yōu)于SMES；εRDE在11個(gè)測(cè)試函數(shù)上一致達(dá)到了全局最優(yōu)解（g02、g07除外），εRDE在g13上的均值和標(biāo)準(zhǔn)差優(yōu)于εCOA，也是4種算法中唯一一致達(dá)到全局最優(yōu)解的，但是獨(dú)立運(yùn)行次數(shù)只有30次，而在g03、g07、g10上εCOA的最差值和標(biāo)準(zhǔn)差都更優(yōu)，說(shuō)明εCOA具有更好的魯棒性。從以上分析可以得出，εCOA在處理13個(gè)基本測(cè)試函數(shù)時(shí)具有一定的優(yōu)勢(shì)。

g02決策變量的維數(shù)較高，搜索空間的拓?fù)浣Y(jié)構(gòu)十分復(fù)雜，使得對(duì)其求解難度很大，5種算法都未一致達(dá)到全局最優(yōu)解。g13等式約束條件較多，從而可行域空間十分狹小，大多數(shù)算法未一致達(dá)到全局最優(yōu)解。可以看出對(duì)于決策變量維數(shù)較高、等式約束條件較多的問(wèn)題，大多數(shù)算法都存在一定的缺陷，需要進(jìn)一步改善算法的探索和開(kāi)發(fā)能力，更好兼顧種群的多樣性和收斂性。

表2 εCOA與其他3種算法的比較結(jié)果

4.3 參數(shù)Te的分析

在εCOA中，最重要的參數(shù)是截?cái)噙M(jìn)化迭代次數(shù)Te。為了分析不同的Te取值對(duì)εCOA收斂性能的影響，通過(guò)對(duì)不含等式約束條件的函數(shù)g01和含有復(fù)雜等式約束條件的函數(shù)g03、g11和g13進(jìn)行實(shí)驗(yàn)，獨(dú)立運(yùn)行次數(shù)為5次，實(shí)驗(yàn)結(jié)果如圖1～圖4所示。

圖1 在g01上不同Te取值下的最優(yōu)值均值

圖2 在g03上不同Te取值下的最優(yōu)值均值

圖3 在g11上不同Te取值下的最優(yōu)值均值

圖4 在g13上不同Te取值下的最優(yōu)值均值

從圖1可以看出，對(duì)于只含有不等式約束條件的函數(shù)g01，當(dāng)Te的取值范圍從200代到4 000代左右時(shí)，εCOA在5次獨(dú)立運(yùn)行實(shí)驗(yàn)中都能達(dá)到全局最優(yōu)解，而從4 000代之后，εCOA不能一致收斂到全局最優(yōu)解；從圖2可以看出，當(dāng)Te的取值范圍從800到3 000代左右時(shí)，εCOA在5次獨(dú)立運(yùn)行實(shí)驗(yàn)中都能一致收斂到全局最優(yōu)解，而在3 000代之后不能一致收斂；從圖3可以看出，在Te取值4 600代左右后出現(xiàn)不能一致收斂的情況；從圖4可以看出，當(dāng)Te的取值范圍從800代到4 600代左右時(shí)，εCOA在5次獨(dú)立實(shí)驗(yàn)中達(dá)到一致收斂；而在5 000代之后，出現(xiàn)了種群中甚至沒(méi)有可行個(gè)體的情況，所以在圖4中沒(méi)有最優(yōu)值均值。以上實(shí)驗(yàn)結(jié)果表明，當(dāng)Te的取值過(guò)小時(shí)（小于800代），由于對(duì)不可行個(gè)體的有效信息利用不足，對(duì)于等式約束條件較多進(jìn)而可行域很小的函數(shù)，算法不能一致收斂到全局最優(yōu)解；而當(dāng)Te的取值過(guò)大時(shí)（大于4 600代），由于過(guò)多的利用不可行個(gè)體，使得算法對(duì)可行域搜索力度不夠，從而不能充分收斂到全局最優(yōu)解，甚至不能進(jìn)入可行域?；谏鲜鰧?shí)驗(yàn)結(jié)果和分析，Te取值800～3 000較為合適，而在所有測(cè)試函數(shù)上統(tǒng)一取值1 000。

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

本文在深入研究約束優(yōu)化問(wèn)題的基礎(chǔ)上，提出一種自適應(yīng)ε約束優(yōu)化算法。首先通過(guò)改進(jìn)約束處理技術(shù)，充分利用不可行個(gè)體的有效信息，加強(qiáng)算法的探索能力，增強(qiáng)多樣性，避免陷入局部最優(yōu)；其次通過(guò)自適應(yīng)設(shè)置ε，平衡可行個(gè)體與不可行個(gè)體的關(guān)系，提高算法的魯棒性和搜索效率。仿真實(shí)驗(yàn)結(jié)果表明，εCOA不僅能夠收斂到全局最優(yōu)解，而且魯棒性較好。但是對(duì)于決策變量維數(shù)較高、等式約束條件較多的復(fù)雜約束優(yōu)化問(wèn)題，仍需要進(jìn)一步提高種群的多樣性和收斂性，使之一致收斂到全局最優(yōu)解。

［1］Bi X J，Wang Y J.Artificial bee colony algorithm with fast convergence［J］.Systems Engineering and Electronics，2011，33（12）：2755－2761.（畢曉君，王艷嬌.加速收斂的人工蜂群算法［J］.系統(tǒng)工程與電子技術(shù)，2011，33（12）：2755－2761.）

［2］Kang L，Wu L，Chen X，et al.Practical structure and motion recovery from two uncalibrated images usingεconstrained adaptive differential evolution［J］.Pattern Recognition，2013，46（5）：1466－1484.

［3］Du X Y，Sun L J，Guo J，et al.Coverage optimization algorithm for heterogeneous WSNs［J］.Journal of Electronics ＆Information Technology，2014，36（3）：697－701.（杜曉玉，孫力娟，郭劍，等.異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法［J］.電子與信息學(xué)報(bào)，2014，36（3）：697－701.）

［4］Wu T Y，Xu J H，Liu J Y，et al.Improved genetic algorithm for vehicle routing problem with hard time windows［J］.Systems Engineering and Electronics，2014，36（4）：708－713.（吳天羿，許繼恒，劉建永，等.求解有硬時(shí)間窗車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法［J］.系統(tǒng)工程與電子技術(shù)，2014，36（4）：708－713.）

［5］Yan Z C，Luo Y S.A particle swarm optimization algorithm based on simulated annealing［C］∥Proc.of the Conference on Advanced Materials Research，2014：2301－2305.

［6］Elsayed S M，Sarker R A，Essam D L.An improved self-adaptive differential evolution algorithm for optimization problems［J］.IEEE Trans.on Industrial Informatics，2013，9（1）：89－99.

［7］Wisittipanich W，Kachitvichyanukul V.Mutation strategies toward Pareto front for multi-objective differential evolution algorithm［J］.International Journal of Operational Research，2014，19（3）：315－337.

［8］Gou S，Zhuang X，Li Y，et al.Multi-elitist immune clonal quantum clustering algorithm［J］.Neurocomputing，2013，101（2）：275－289.

［9］Datta R，Deb K.Individual penalty based constraint handling using a hybrid bi-objective and penalty function approach［C］∥Proc.of the IEEE Congress on Evolutionary Computation，2013：2720－2727.

［10］Mezura-Montes E，Coello C A.Constraint handling in nature-inspired numerical optimization：past，present and future［J］.Swarm and Evolutionary Computation，2011，1（4）：173－194.

［11］Runarsson T P，Yao X.Search biases in constrained evolutionary optimization［J］.IEEE Trans.on Systems Man and Cybernetics-Part C：Applications and Reviews，2005，35（2）：233－243.

［12］Long Q.A constraint handling technique for constrained multiobjective genetic algorithm［J］.Swarm and Evolutionary Computation，2014，15（4）：66－79.

［13］Takahama T，Sakai S.Constrained optimization by theεconstrained differential evolution with gradient-based mutation and feasible elites［C］∥Proc.of the IEEE Congress on Evolutionary Computation，2006：1－8.

［14］Asafuddoula M，Ray T，Sarker R.An adaptive constraint handling approach embedded MOEA／D［C］∥Proc.of the IEEE Congress on Evolutionary Computation，2012：1－8.

［15］Landa R，Coello C A C，Toscano-Pulido G.Goal-constraint：incorporating preference through an evolutionaryε-constraint based method［C］∥Proc.of the IEEE Congress on Evolutionary Computation，2013：741－747.

［16］Bi X J，Wang J，Li B，et al.Anεconstrained biogeographybased optimization with dynamic migration［J］.Journal of Computer Research and Development，2014，51（3）：580－589.（畢曉君，王玨，李博，等.基于動(dòng)態(tài)遷移的ε約束生物地理學(xué)優(yōu)化算法［J］.計(jì)算機(jī)研究與發(fā)展，2014，51（3）：580－589.）

［17］Tetsuyuki T，Setsuko S.Efficient constrained optimization by theεconstrained rank-based differential evolution［C］∥Proc.of the IEEE Congress on Evolutionary Computation，2012：10－15.

［18］Zheng J G，Wang X，Liu R H.ε-Differential evolution algorithm for constrained optimization problems［J］.Journal of Software，2012，23（9）：2374－2387.（鄭建國(guó)，王翔，劉榮輝.求解約束優(yōu)化問(wèn)題εDE算法［J］.軟件學(xué)報(bào)，2012，23（9）：2374－2387.）

［19］Wang Y，Cai Z X.Combining multi-objective optimization with differential evolution to solve constrained optimization problems［J］.Evolutionary Computation，2012，16（1）：117－134.

［20］Mezura-Montes E，Coello C A.A simple multi-membered evolution strategy to solve constrained optimization problems［J］.IEEE Trans.on Evolutionary Computation，2005，9（1）：1－17.

Self-adaptiveεconstrained optimization algorithm

BI Xiao-jun，ZHANG Lei
（Institute of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China）

Since current constrained optimization algorithms are easy to fall into the local optimum and their robustness are weak，a self-adaptiveεconstrained optimization algorithm is proposed.By improving the individual comparison criterion，it can make full use of effective information carried by the infeasible solution，then enhance the exploration in the search space and improve the population diversity.Simultaneously，a self-adaptive adjustment strategy is presented to produce a suitableεfor balancing the relationship between the objective function and the constraint violation degree according to different problems，which can make more reasonable comparisons between individuals.Finally，comparative experiments on thirteen benchmark functions show that the proposed algorithm is not only able to converge the global optimal solution with higher accuracy but also has better robustness.

constrained optimization algorithm；individual comparison criteria；εconstrained；self-adaptive

TP 18

A

10.3969／j.issn.1001-506X.2015.08.29

畢曉君（1964－），女，教授，博士，主要研究方向?yàn)樾畔⒅悄芴幚砑夹g(shù)、智能優(yōu)化算法、數(shù)字圖像處理。

E-mail：bixiaojun＠hrbeu.edu.cn

張 磊（1987－），男，博士研究生，主要研究方向?yàn)樾畔⒅悄芴幚砑夹g(shù)、約束多目標(biāo)優(yōu)化。

E-mail：zl12306124＠163.com

1001－506X201508－1909－07

網(wǎng)址：www.sys－ele.com

2014－07－11；

2014－11－14；網(wǎng)絡(luò)優(yōu)先出版日期：2015－03－23。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150323.1706.004.html

國(guó)家自然科學(xué)基金（61175126）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金（HEUCFZ1209）；教育部博士點(diǎn)基金（20112304110009）資助課題