基于精确目标罚参数的遗传算法*

白云娇， 谷伟平

(重庆人文科技学院 机电与信息工程学院，重庆 401524)



基于精确目标罚参数的遗传算法*

白云娇， 谷伟平

(重庆人文科技学院 机电与信息工程学院，重庆 401524)

摘要：结合一种精确目标罚函数和遗传算法，提出新的算法；算法能将约束优化问题转化为无约束优化问题，同时具有遗传算法的全局搜索能力，避免陷入局部收敛；给出并讨论了精确罚定理，实验结果表明了算法的有效性.

关键词：目标罚参数；精确罚函数；遗传算法；扰动

0引言

研究下面不等式约束优化问题(P)：

(1)

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

罚函数法能将约束问题转化为无约束问题，通过求解罚问题得到原问题的最优解.但对每个约束优化问题都需求解一系列无约束优化问题(求解无约束优化问题的新方法如文献[5]等)，计算量十分庞大.因此，在求解约束优化问题时，精确罚函数具有重要作用.文献[1-4]中，讨论了一些精确罚函数的形式与性质.2012年，文献[6]中提出这样的目标罚函数法：

(2)

设Q:R1→R1∪{+∞}是连续函数并满足以下3个条件(P,Q函数定义相同)：

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

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

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

1基于精确目标罚参数的遗传算法

考虑下面的罚问题(P(ρ,M))：

(3)

其中,X⊂Y⊂Rn,X为原问题可行域，Y为扩大后的罚问题可行域.

新的罚函数定义：

(4)

设Q:R1→R1∪{+∞}是连续函数并满足以下3个条件(P,Q函数定义相同)：

(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)

现考虑下面问题(P)的扰动问题(P(ε))：

(10)

称xε是问题(P)的ε近似解.

(11)

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

(12)

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

(13)

3算法

4数值实验

例1考虑下面问题：

取罚函数：

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

取ρ1=ρ*=20，N=1，α=2初始点x(0)=(1,1)，M1=-10使用新算法得到结果如表1所示.

表1　新算法数值结果

取ρ=200，初始点x(0)=(1,1)，M1=-10使用文献[7]中的MQNFA算法得到结果如表2所示.

表2　MQNFA算法数值结果

5结语

已知例1问题的近似最优解为x*=(2.395 20,3.178 490)，目标值为f0*=-5.508 010.由表1和表2结果可知，算法在第4步就得到了比文献[7]的MQNFA算法迭代7步更精确的结果.同时在实验中发现新算法在陷入局部收敛时，保持原参数不变继续进行搜索最终能得到全局最优解.这是因为新算法中求解罚子问题时，通过遗传算法的变异算子引入了微小扰动使其跳出了局部收敛，因此新算法结合了遗传算法的优点具有全局搜索能力.

参考文献(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] 曾刘拴.解无约束优化的非单调自适应信赖域算法[J].重庆工商大学学报(自然科学版)，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] 刘树人,孟志青.基于双参数罚函数求解约束优化问题的一个新算法[J].应用数学，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

责任编辑：田静

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

中图分类号：O221.2

文献标志码：A

文章编号：1672-058X(2016)02-0030-04

作者简介：白云娇(1988-)，女，重庆人，硕士，从事最优化理论与算法研究.

*基金项目：重庆人文科技学院教改项目(15CRKXJ05).

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

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