王 萍

(鐵嶺師范高等?？茖W(xué)校，遼寧 鐵嶺 112000)

?

基于非線性規(guī)劃全局優(yōu)化問題的兩種優(yōu)化算法

王 萍

(鐵嶺師范高等?？茖W(xué)校，遼寧 鐵嶺 112000)

提出針對全局優(yōu)化問題的非線性規(guī)劃的隨機算法進行探討，給出適用于全局優(yōu)化問題中的帶有非線性約束的兩種算法——模擬退火算法和進化規(guī)劃算法。算法通過構(gòu)造子問題來尋找優(yōu)于當前局部最優(yōu)解的可行解。該子問題可通過給出的兩種隨機算法——模擬退火算法和進化規(guī)劃算法求解。求解子問題后，當前最優(yōu)解被不斷地更新，最終求得全局最優(yōu)解。本算法應(yīng)用于幾個典型例題，并與基于模擬退火的罰函數(shù)法相比較，數(shù)值結(jié)果表明該算法是可行的、有效的。

非線性規(guī)劃；模擬退火算法；進化規(guī)劃算法

0 引言

模擬退火思想最早在1953年時由Metropolis[1]提出，之后Kirkpatrick和Aart等分別于1983年[2]和1987年提出將模擬退火算法應(yīng)用于組合優(yōu)化問題和模擬退火算法的理論和應(yīng)用。王卓鵬等[3]研究出一種快速模擬退火算法，用來加快模擬退火算法的速度：先對樣本點進行局部搜索之后再隨機搜索。在關(guān)于退火策略研究方面，部分專家提出了對數(shù)下降、快速下降、直線下降和指數(shù)退溫策略[4]，例如顧基發(fā)、楊若黎，給出了與迭代次數(shù)有關(guān)的退火策略，同時給出一個退火準則[5]。

Fogel在20世紀60年代提出進化規(guī)劃。他給出的方法和遺傳算法有不少共同之處，但又不同于遺傳算法，他強調(diào)父代與子代的表現(xiàn)行為聯(lián)系上[6]。Fogel在1966年編著了《基于模擬進化的人工智能》，詳細敘述了進化規(guī)劃思想。到了90年代，學(xué)術(shù)界開始對進化規(guī)劃加以重視。

1 目標函數(shù)是線性的非線性規(guī)劃問題

本文給出了帶有線性目標函數(shù)的非線性規(guī)劃問題的模擬退火和進化規(guī)劃算法，該方法將帶有約束問題轉(zhuǎn)變?yōu)闊o約束，數(shù)值結(jié)果證實方法計算精度高，顯示了很好的收斂效果，考慮如下優(yōu)化問題(其中c是向量)：

mincTx

s.t.gi(x)≤0i=1,…,r

(1)

Ax≤b

為了尋找到滿足約束的可行解，我們首先來解決子問題：

minf=max{0,gi(x)i=1,…,r}

(2)

Ax≤b

Bx≤d可寫成：

(3)

2 非線性規(guī)劃全局優(yōu)化問題的模擬退火算法

基于分量x(li)的上下界我們提出了一類求解子問題(3)的模擬退火算法，算法的具體步驟如下：

算法1：Step 0:初始化：給定最高和最低溫度分別為Tmax，Tmin，迭代次數(shù)Lmax以及參數(shù)ε>0。

Step1:利用隨機過程，得到可行解的初始值x0=(x0(1),…,x0(n))，設(shè)T=Tmax,t=0,I=0。若f(x0)≤0，則I=1，y*=x0。否則轉(zhuǎn)step2。

Step2: While (T>Tmin) do

(a) whilet≤Lmaxdo

(1)隨機地選取lt∈{1,2,…,n}，給出均勻分布的隨機數(shù)λ∈[-1,1]。Forj=1,…,n，ifλ>0，

其中alt和blt為下界和上界xt(lt)來自于不等式(3)，α的初值為1，若α<10-4，則α=1。

(2)令z=(z(1),…,z(n))，如果f(z)≤0，則I=1,y*=z。算法1則停。否則轉(zhuǎn)(3)。

(3)取η∈[0,1],如果η≤min{1,exp{[f(xt)-f(z)]/T}}，設(shè)xt+1=z，否則xt+1=xt。t=t+1。

(b)Lmax=Lmax+d,t=0.

(c)由T=δ×T降低溫度T。其中，參數(shù)d,β和δ為事先輸入的已知常數(shù)。

在算法1的基礎(chǔ)上，給出隨機的可行解初始值x0，令k=0。如果I=1,令xk+1*=y*，Tmax=T，Lmax=Lmax，k=k+1。如果I=0,則xk*就是問題(1)的全局最優(yōu)解。

3 非線性規(guī)劃全局優(yōu)化問題的進化規(guī)劃算法

本節(jié)針對問題(2)給出一個改進的進化規(guī)劃算法，適應(yīng)值即取目標函數(shù)值，具體步驟如下：

算法2:Step1：給出μ個初始值，設(shè)k=1，I=0。設(shè)個體為實值向量對(xi,ηi),?i∈{1,…,μ}。

Step2：計算個體適應(yīng)值。如果?i∈{i,…,μ}，f(xi)≤0，則I=1，y*=xi′否則轉(zhuǎn)Step3。

Step3：每個父代(xi,ηi)，?i=1,…,μ，根據(jù)如下步驟產(chǎn)生一個子代(xi′,ηi′)：從集合{1,2,…,n}中隨機的選取li，產(chǎn)生介于[-1,1]區(qū)間的均勻分布隨機參數(shù)λ。對于j=1,…,n，如果λ>0

η的初始值為1，如果ηi<10-4，那么ηi=1。

Step4：若適應(yīng)值≤0個數(shù)為0，令k=k+1，轉(zhuǎn)Step3。若適應(yīng)值≤0的個數(shù)>0，算法2則停。

基于算法2，我們提出求解問題(1)的算法，給出隨機的μ個可行解初始值xi，?i∈{1,…,μ},令t=1。如果I=1，令xi′*=y*，t=t+1。如果I=0，則xi*就是問題(1)的全局最優(yōu)解。

4 數(shù)值結(jié)果

下面我們給出求解的數(shù)值例子：

s.t.x1+2x2+8x3+x4+3x5+5x6≤16 and -8x1-4x2-2x3+2x4+4x5-x6≤-1,

2x1+0.5x2+0.2x3-3x4-x5-4x6≤24 and 0.2x1+2x2+0.1x3-4x4+2x5+2x6≤12，

-0.1x1-0.5x2+2x3+5x4-5x5+3x6≤3 andx4≤1,x5≤1 andx6≤2 andxi≥0,(i=1,…,6)

該函數(shù)的全局最優(yōu)解為(0，6，0，1，1，0)，最優(yōu)值為-11。

表1示出了進行數(shù)值計算的參數(shù)設(shè)定值，表2和表3是數(shù)值計算結(jié)果。

表1 模擬退火算法的參數(shù)設(shè)定值

表2 基于文中提出的模擬退火算法和罰函數(shù)法計算結(jié)果

表3 基于本文進化規(guī)劃算法和罰函數(shù)法計算結(jié)果

[1]Metropolis N, Rosenbluth A. Rosenbluth M. et al.. Equation of State Calculations by Fast Computing Machines[J].Journal of Chemical Physics,1953，(21)：1 087—1 092.

[2]Kirkpatrick S., Gelatt Jr C,D. and Vecchi M P.. Optimization by Simulated Annealing[J].Science,1983，(220)：671—680.

[3]王卓鵬,高國成,楊衛(wèi)平.一種改進的快速模擬退火組合優(yōu)化法[J].系統(tǒng)工程理論與實踐,1999，(2)：73—76.

[4]高尚.模擬退火算法中的退火策略研究[J].航空計算技術(shù),2002，32(4)：20—23.

[5]楊若黎,顧其發(fā).一種高效的退火全局優(yōu)化算法[J].系統(tǒng)工程理論與實踐,1997，(5)：29—35.

[6]Heitkotter, J. and Beasley, D.. The hitch-hiker’s guide to evolutionary computation[J].FAQ in Comp Ai Genetic,1995.

責任編輯：柴造坡

10.3969/j.issn.1674-6341.2015.06.047

2015-09-11

王萍(1981—)，女，遼寧鐵嶺人，碩士研究生，講師。研究方向：數(shù)學(xué)教育與教學(xué)。

G642.4

A

1674-6341(2015)06-0101-02