白云嬌， 谷偉平

(重慶人文科技學(xué)院 機(jī)電與信息工程學(xué)院，重慶 401524)

?

基于精確目標(biāo)罰參數(shù)的遺傳算法*

白云嬌， 谷偉平

(重慶人文科技學(xué)院 機(jī)電與信息工程學(xué)院，重慶 401524)

摘要：結(jié)合一種精確目標(biāo)罰函數(shù)和遺傳算法，提出新的算法；算法能將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，同時(shí)具有遺傳算法的全局搜索能力，避免陷入局部收斂；給出并討論了精確罰定理，實(shí)驗(yàn)結(jié)果表明了算法的有效性.

關(guān)鍵詞：目標(biāo)罰參數(shù)；精確罰函數(shù)；遺傳算法；擾動(dòng)

0引言

研究下面不等式約束優(yōu)化問題(P)：

(1)

其中,fi:Rn→R1∪{+∞},i∈Ip={0,1,2,…,p}.

罰函數(shù)法能將約束問題轉(zhuǎn)化為無約束問題，通過求解罰問題得到原問題的最優(yōu)解.但對(duì)每個(gè)約束優(yōu)化問題都需求解一系列無約束優(yōu)化問題(求解無約束優(yōu)化問題的新方法如文獻(xiàn)[5]等)，計(jì)算量十分龐大.因此，在求解約束優(yōu)化問題時(shí)，精確罰函數(shù)具有重要作用.文獻(xiàn)[1-4]中，討論了一些精確罰函數(shù)的形式與性質(zhì).2012年，文獻(xiàn)[6]中提出這樣的目標(biāo)罰函數(shù)法：

(2)

設(shè)Q:R1→R1∪{+∞}是連續(xù)函數(shù)并滿足以下3個(gè)條件(P,Q函數(shù)定義相同)：

(1) 如果t≤0，則Q(t)=0;

(2) 如果t>0，則Q(t)>0；

(3) 如果t2>t1>0，則Q(t2)>Q(t1).

1基于精確目標(biāo)罰參數(shù)的遺傳算法

考慮下面的罰問題(P(ρ,M))：

(3)

其中,X?Y?Rn,X為原問題可行域，Y為擴(kuò)大后的罰問題可行域.

新的罰函數(shù)定義：

(4)

設(shè)Q:R1→R1∪{+∞}是連續(xù)函數(shù)并滿足以下3個(gè)條件(P,Q函數(shù)定義相同)：

(1) 如果t≤0，則Q(t)=0；

(2) 如果t>0，則Q(t)>0；

(3) 如果t2>t1>0，則Q(t2)>Q(t1).

2精確罰定理

(5)

(6)

(7)

(8)

(9)

現(xiàn)考慮下面問題(P)的擾動(dòng)問題(P(ε))：

(10)

稱xε是問題(P)的ε近似解.

(11)

其中εmax=max{ε1,ε2,…,εp}.

(12)

又因fi(x)≤εi,i=1,2,…,p.所以fi(x)≤εmax.因此，可以得到：

(13)

3算法

4數(shù)值實(shí)驗(yàn)

例1考慮下面問題：

取罰函數(shù)：

max(0,-x1)+max(0,x1-3)+

取ρ1=ρ*=20，N=1，α=2初始點(diǎn)x(0)=(1,1)，M1=-10使用新算法得到結(jié)果如表1所示.

表1　新算法數(shù)值結(jié)果

取ρ=200，初始點(diǎn)x(0)=(1,1)，M1=-10使用文獻(xiàn)[7]中的MQNFA算法得到結(jié)果如表2所示.

表2　MQNFA算法數(shù)值結(jié)果

5結(jié)語

已知例1問題的近似最優(yōu)解為x*=(2.395 20,3.178 490)，目標(biāo)值為f0*=-5.508 010.由表1和表2結(jié)果可知，算法在第4步就得到了比文獻(xiàn)[7]的MQNFA算法迭代7步更精確的結(jié)果.同時(shí)在實(shí)驗(yàn)中發(fā)現(xiàn)新算法在陷入局部收斂時(shí)，保持原參數(shù)不變繼續(xù)進(jìn)行搜索最終能得到全局最優(yōu)解.這是因?yàn)樾滤惴ㄖ星蠼饬P子問題時(shí)，通過遺傳算法的變異算子引入了微小擾動(dòng)使其跳出了局部收斂，因此新算法結(jié)合了遺傳算法的優(yōu)點(diǎn)具有全局搜索能力.

參考文獻(xiàn)(References)：

[1]MORRISON D D.Optimization by Least Aquares[J].SIAM J Numer,Anal,1968(5):83-88

[2] FLETCHER,R.Practical Method of Optimization.Wiley-Interscience[M].New York:1981

[3] FLETCHER R.Penalty functions[M].Berlin:Mathematical Programming,1983

[4] WILLARD I,ZANGWIL L.Nonlinear Programming Via Penalty Function[J].Management Science,1967(5):344-358

[5] 曾劉拴.解無約束優(yōu)化的非單調(diào)自適應(yīng)信賴域算法[J].重慶工商大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013，30(11):55-61

ZENG L S.Nonmonotone self-adaptive Trust-region Slgorithm for Solving Unconstrained Optimization[J].Journal of Chongqing Technology and Business University(Naturnal Science Edition),2013,30(11):55-61

[6] MENG Z Q,DANG C Y,JIANG M.Exactness and Algorithm of An Objective Penalty Function[J].Journal of Global Optimization,2012(11):1011-1015

[7] 劉樹人,孟志青.基于雙參數(shù)罰函數(shù)求解約束優(yōu)化問題的一個(gè)新算法[J].應(yīng)用數(shù)學(xué)，2009，22(2):346-351

LIU S R,MENG Z Q.A new Algorithm for Solving Constrained Optimization on Exact Penalty with Two Parameters[J].Mathematica Applicata,2009,22(2):346-351

責(zé)任編輯：田靜

Genetic Algorithm Based on Objective Parameter of Exact Penlty Function

BAI Yun-jiao，GU Wei-ping

(School of Mechanical Electronic and Information Engineering, Chongqing College of Humanities,Science and Technology, Chongqing 401524, China)

Abstract：In this paper,we proposed a new method which is based on the exact penalty function method and genetic algorithm. The method having the global search ability of genetic algorithm which avoids the local optimal solution can transform constrained optimization problems into unconstrained optimization problems. The exact penalty theorem is given and discussed. Numerical experiments show that the proposed method is effective.

Key words:objective penalty parameter; exact penalty function; genetic algorithm; disturbance

中圖分類號(hào)：O221.2

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-058X(2016)02-0030-04

作者簡介：白云嬌(1988-)，女，重慶人，碩士，從事最優(yōu)化理論與算法研究.

*基金項(xiàng)目：重慶人文科技學(xué)院教改項(xiàng)目(15CRKXJ05).

收稿日期：2015-09-11；修回日期：2015-11-13.

doi:10.16055/j.issn.1672-058X.2016.0002.007