基于約束處理和平滑技術(shù)的改進(jìn)的進(jìn)化算法

王曉萍，孟 坤

(1.西安文理學(xué)院軟件學(xué)院，陜西 西安 710068;2.西安電子科技大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710071)

0 引言

本文考慮以下的非線性約束優(yōu)化問(wèn)題:

其中 f(X)，gi(X)是非線性函數(shù)，［L，U］={X:lj≤xj≤uj，j=1，2，…，n}，L=(l1，...，ln)，U=(u1，...，un)和 X=(x1，...，xn)。這種問(wèn)題通常出現(xiàn)在工程、管理等領(lǐng)域中。當(dāng)f(X)，g(X)在［L，U］中是非凸、不可微的、甚至是不連續(xù)的時(shí)候，用一般傳統(tǒng)的優(yōu)化方法很難處理這類問(wèn)題，而進(jìn)化算法是處理這類問(wèn)題的非常有效的算法之一［1-3］。它們不易于陷入局部最小點(diǎn)［4-5］，但是通常要需大量的時(shí)間和計(jì)算量，并且不能有效地處理約束條件［6］。現(xiàn)在處理約束條件的最有效和最有用的方法之一是用懲罰函數(shù)或拉格朗日函數(shù)［2-4］，然而這些方法的缺點(diǎn)是:1)控制參數(shù)太多，如:拉格朗日乘子、罰參數(shù)等，這些參數(shù)在進(jìn)化過(guò)程中很難取適當(dāng)?shù)闹怠?)常引入不可微的懲罰項(xiàng)，從而可能引入額外的局部最優(yōu)解。這增加了進(jìn)化算法解決問(wèn)題的難度。為了克服這些缺點(diǎn)，首先，本文利用約束處理技術(shù)將約束最優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)題，使問(wèn)題求解難度降低。其次，為了減少局部最優(yōu)解的個(gè)數(shù)，利用了平滑技術(shù)，該技術(shù)可以消除比目前求出的最好解差的全部局部最優(yōu)解，從而使搜索全局最優(yōu)解更加快速和容易。此外還設(shè)計(jì)了新的進(jìn)化算子，并在此基礎(chǔ)上，提出了一種改進(jìn)的進(jìn)化算法。最后，進(jìn)行了計(jì)算機(jī)仿真實(shí)驗(yàn)，計(jì)算結(jié)果說(shuō)明了本算法的有效性。

1 模型的轉(zhuǎn)化

利用熵函數(shù)［7］:

來(lái)近似 max{gi(X):i=1，2，…，m}作為罰函數(shù)，將問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題:

此問(wèn)題的目標(biāo)函數(shù)是可微的，且只需一個(gè)懲罰參數(shù)p。并且罰函數(shù)有以下性質(zhì)［7］:

引理1 ?X∈Rn，p＞0，g(X，p)滿足下面的不等式:

g(X，p)-(ln m)/p≤ max

1≤i≤m{gi(X)}≤g(X，p)

證明:令g'(X)=1m≤ia≤xm{gi(X)}，注意到

因?yàn)?gi(X)-g'(X)≤0，i=1，2，…，m，所以至少存在一個(gè)不等式使它變成等式，故:

1≤∑exp［pgi(X)-pg'(X)］≤m

2 平滑技術(shù)

在目前的全局優(yōu)化算法中，有很多方法常常陷入局部極小點(diǎn)，為了使算法更易擺脫局部極小點(diǎn)，本文使用了一個(gè)平滑函數(shù)［8］，該函數(shù)可以消除比目前已找到的最好點(diǎn)差的局部極小點(diǎn)，保持比目前找到的最好點(diǎn)好的局部最優(yōu)點(diǎn)。若用此平滑函數(shù)作為適應(yīng)度函數(shù)，則局部極小點(diǎn)的數(shù)目會(huì)在迭代過(guò)程中不斷大量地減少，使算法更易找出全局極小點(diǎn)。此平滑函數(shù)如下:

3 一種改進(jìn)的進(jìn)化算法

3.1 新的交叉算子

均勻設(shè)計(jì)是一種在一個(gè)區(qū)域內(nèi)尋找一組均勻分布的點(diǎn)的方法。文獻(xiàn)［9-10］將其用于設(shè)計(jì)新的交叉算子，取得了很好的效果，本文利用類似的思想設(shè)計(jì)一個(gè)新的交叉算子。

按照均勻分布產(chǎn)生一個(gè)元素在［0，1］內(nèi)均勻分布的q行n列隨機(jī)矩陣Q，其第i行第j列元素記為Qij，再對(duì)其進(jìn)行運(yùn)算:aij=［q*Qij+0.5］，以 aij作為第i行第j列的元素做一個(gè)新的矩陣A。對(duì)一對(duì)父母點(diǎn) X=(x1，x2，...，xn)和 Y=(y1，y2，...，yn)，用矩陣A的每一行，可以定義X和Y的一個(gè)后代，具體定義如下:

令 W=(w1，w2，...，wn)，Z=(z1，z2，...，zn)其中，wi=min{xi，yi}，zi=max{xi，yi}，則第 i個(gè)后代 Oi可以被定義為:

3.2 變異算子

假定 O=(o1，...，on)由 Gaussian 變異進(jìn)行變異，經(jīng)變異后，它變成=O+ΔO，其中ΔO～(N(0，σ1)，...，n(0，σn))，N(0，σi)表示均值為 0 和方差為的 Gaussian分布，在 ΔO 中，n個(gè)分量 ΔO1，...，ΔOn相互獨(dú)立。

3.3 改進(jìn)的進(jìn)化算法

算法框架:

步驟1 (Initialization)給定雜交概率pc和種群維數(shù) N。記 k=1，產(chǎn)生初始種群 POP(k)={X1，...，XN}。

步驟3 (Mutation)對(duì)集合OFF(k)中每個(gè)中間后代Oi由3.2節(jié)中的變異算子變異為一個(gè)最終的后代，用替換OFF(k)中的Oi形成一個(gè)新的集合OFF(k)，這個(gè)集合就是第k代所有的后代。

步驟4 (Selection)從集合POP(k)∪OFF(k)中選擇最好的N個(gè)點(diǎn)組成(k+1)代的種群POP(k+1)，定義模型(2)中新的函數(shù)。

步驟5 若終止條件成立，則停;否則，令k=k+1，轉(zhuǎn)步驟2。

4 仿真實(shí)驗(yàn)結(jié)果及分析

4.1 測(cè)試問(wèn)題

本文對(duì)下面5個(gè)廣泛使用的測(cè)試問(wèn)題［11］進(jìn)行了計(jì)算機(jī)仿真實(shí)驗(yàn)，其中下列各式中→x*，f(→x*)分別為問(wèn)題的真正最優(yōu)點(diǎn)和真正最優(yōu)值。測(cè)試問(wèn)題如下:

Problem 1:

Problem 2:

Problem 3:

Problem 4:

Problem 5:

4.2 實(shí)驗(yàn)結(jié)果及比較

上一節(jié)針對(duì)5個(gè)測(cè)試問(wèn)題采用本文算法分別獨(dú)立運(yùn)行50次，記錄所求出的最好、最差、平均的目標(biāo)函數(shù)值及方差，并和其它方法作了比較。New Algorithm代表本文的方法，Best是本文算法50次運(yùn)行中得到的最好值，Median是對(duì)50次運(yùn)行中所得出解的平均值，而Worst是其中得到的最壞值，Sd是50次運(yùn)行中得到的值的方差。本文中N取10×n，Gen為最大控制代數(shù)。

參數(shù)設(shè)定如下:q=5，p=1000;N和Gen與所比較的方法取相同的值。其中，“-”表示表中相應(yīng)的方法沒(méi)有記錄此結(jié)果。

表1 是對(duì) Problem1、Problem2、Problem4 分別在50次運(yùn)行中，得到的最優(yōu)值和真正的最優(yōu)值的相對(duì)誤差不超過(guò)ε%的次數(shù)統(tǒng)計(jì)，并同時(shí)將本文方法的計(jì)算結(jié)果與方法 TS-B［12］、TS-R［12］和 PS［13］已有的結(jié)果作了比較。對(duì)Problem1，各方法的種群規(guī)模取為N=20(10×2)，最大控制代數(shù)取Gen=50。對(duì)Problem2，N和 Gen分別取80和1000，而對(duì) Problem4，取 N=100，Gen=1000。(結(jié)果見(jiàn)表 1)。

表1 Problem1、Problem2、Problem4 的結(jié)果比較

表2分別是本文方法對(duì)Problems 3、Problem5在50次運(yùn)行中得到的結(jié)果，及與文獻(xiàn)［14-17］方法已有結(jié)果的比較。對(duì)Problem3，取N=50，Gen=1000。對(duì)Problem5，取 N=20，Gen=1000。

從表1可看出，對(duì)Problem1，本文方法在50次循環(huán)中，有31次得到的最優(yōu)值距真正的最優(yōu)值(f(→x*)=13.59085)的相對(duì)誤差不超過(guò)1%，而TS-R方法只有29次，PS(R=1)方法只有17次。本文有42次得到的最優(yōu)值距真正的最優(yōu)值的相對(duì)誤差不超過(guò)50%，而TS-R和PS(R=1)方法分別只有39和32次。本文中方法在50次運(yùn)行中得到的最好點(diǎn)為→x=(2.246826，2.381865)，其函數(shù)值為f(→x)=13.59085。比TS-B，PS(R=1)得到的結(jié)果都好，和TS-R的最優(yōu)值是一樣的，但是平均值和最差的結(jié)果均比TS-R得到的好，因此本文方法比TS-R法穩(wěn)定。

對(duì)Problem2，真正最優(yōu)值是f(→x*)=7049.331，本文求得的最優(yōu)值是f(→x)=7049.331，最優(yōu)點(diǎn)為→x=(579.31，1360，5110.1，182.07，295.53，217.91，286.44，395.59)，而方法TS-R得到的最優(yōu)值是f(→x)=7065.742，顯然比本文的要差。Problem4的真正最優(yōu)值是f(→x)=24.306，本文方法得到的最優(yōu)點(diǎn)和最優(yōu)值分別為→x=(2.337，8.7854，5.0331，0.95669，1.4442，1.3617，9.8975，8.2953，8.3974)和f(→x)=24.358，它們與真正的最優(yōu)值很接近，也比方法TS-R得到的結(jié)果好。

表2給出對(duì)Problem3、Problem5的計(jì)算結(jié)果。對(duì)Problem3，本文算法所求得最優(yōu)值為f(→x)=-30693.1，最優(yōu)點(diǎn)為→x=(78.007，33.014，29.905，45.051，36.798)。本文中算法得到的解比Deb、Homaifar及Gen得到的結(jié)果都好，比Coello稍差，但是本文方法得到的平均值和最差的結(jié)果與最優(yōu)值相差不大，說(shuō)明本文方法很穩(wěn)定。從表2也看出本文中得到的結(jié)果比文獻(xiàn)［11］中的方法得到的結(jié)果要好。

表2 Problem3、Problem5的結(jié)果比較

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

進(jìn)化算法是一種處理非線性規(guī)劃問(wèn)題的有效方法之一，它們可以避開(kāi)局部最小點(diǎn)，但是要花費(fèi)大量的時(shí)間和計(jì)算量。本文首先利用約束處理技術(shù)將約束最優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)題，使問(wèn)題求解難度降低。其次利用平滑技術(shù)消除不優(yōu)于當(dāng)前最優(yōu)解的全部局部最優(yōu)解，減少了局部最優(yōu)解的個(gè)數(shù)，從而使搜索全局最優(yōu)解更加快速和容易?；诖?，提出了一種改進(jìn)的進(jìn)化算法。實(shí)驗(yàn)表明本文的新算法用較少的計(jì)算量、較快的速度求出了高質(zhì)量的最優(yōu)值，且新算法的表現(xiàn)優(yōu)于所比較的算法。

［1］Michalewicz Z.Genetic Algorithms+Data Structures=E-volution Programs［M］.3rd Edition.Berlin:Springer-Verlag，1999.

［2］Tahk Min-jea，Sun Byung-chan.Coevolutionary augmented Lagrangian methods for constrained optimization［J］.IEEE Trans.on Evolutionary Computation，2000，4(1):114-124.

［3］Kim J H，Myung H.Evolutionary programming techniquesfor constrained optimization［J］.IEEE Trans.on Evolutionary Computation，1997，1(1):129-140.

［4］Deb K，Agrawal S.A niched-penalty approach for constrained handling in genetic algorithms［C］//Proceedings of the ICANNGA.1999:235-243.

［5］Yao Xin，Liu Yong.Fast evolution strategies［M］//Evolutionary Programming VI.Berlin:Springer-Verlag，1997:149-161.

［6］Back T，Schwefel H P.An overview of evolutionary algorithms for parameter optimization［J］.Evolutionary Computation，1993，1(1):1-23.

［7］左利云，曹志波，董守斌.云計(jì)算虛擬資源的熵優(yōu)化和動(dòng)態(tài)加權(quán)評(píng)估模型［J］.軟件學(xué)報(bào)，2013，24(8):1937-1946.

［8］王宇平，劉大蓮.基于平滑技術(shù)和一維搜索的全局優(yōu)化進(jìn)化算法及其收斂性［J］.計(jì)算機(jī)學(xué)報(bào)，2006，29(4):670-675.

［9］Wang Yuping，Dang Chuangyin.An evolutionary algorithm for global optimization based on level-set evolution and Latin squares［J］.IEEE Trans.on Evolutionary Computation，2007，11(5):579-595.

［10］Leung Y W，Wang Yuping.An orthogonal genetic algorithm with quantization for global numerical optimization［J］.IEEE Trans.on Evolutionary Computation，2001，5(1):41-53.

［11］Chew Soo Hong，Zheng Quan.Integral Global Optimization:Theory，Implementation and Applications［M］.Berlin Heidelberg:Springer-Verlag，1988.

［12］Deb K，Agrawal R.Simulated binary crossover for continuous search space［J］.Complex Systems，1995，9(2):115-148.

［13］Powell D，Skolnick M M.Using genetic algorithms in engineering design optimization with nonlinearconstraints［C］//Proc.of the Fifth International Conference on Genetic Algorithms.1993:424-430.

［14］Carlos A Clello Coello.Constraint-handling using an evolutionary multiobjective optimization technique［J］.Civil Engineering and Environmental Systems，2000，17(4):319-346.

［15］Deb K.A robust optimal design technique for mechanical component design［M］//Evolutionary Algorithms in Engineering Applications.Berlin:Springer-Verlag.1997:497-514.

［16］Homaifar A，Chlarelene X Qi，Steven H Lai.Constrained optimization via genetic algorithms［J］.Simulation，1994，62(4):242-253.

［17］Gen M，Chang R.Genetic Algorithms＆ Engineering Design［M］.New York:John Wiley＆ Sons Inc.，1997.