资源描述：
《基于遗传算法的退火精确罚函数非线性约束优化方法new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、控制与决策1998年3月Vol.13No.2CONTROLANDDECISIONMar.1998X基于遗传算法的退火精确罚函数非线性约束优化方法吴志远邵惠鹤吴新余(上海交通大学自动化所,200030)(南京邮电学院)摘要提出一种新的基于遗传算法求解非线性约束优化的方法,通过自适应的退火罚因子和不可微精确罚函数来处理约束条件,可以使算法逐渐收敛于可行的极值点。仿真结果表明该方法有较高的求解精度。关键词遗传算法,模拟退火,精确罚函数,非线性约束优化分类号O2241引言在最优化问题中,无约束优化问题的求解已有
2、许多成熟的方法,但对于约束优化问题,尤其是非线性约束优化的求解,仍在不断发展完善中。早期的非线性约束优化问题求解是通过罚函数法将其化为无约束问题来求解。近期发展的逐次二次规划法(SQP)、逐次线性规划法(SLP)以及广义简约梯度法(GRG),已经脱离了对无约束优化方法的依赖,是目前求解非线性约束最优化问题较为有效的方法。尽管如此,这些方法都是基于梯度寻优的方法,它们要求目标函数和约束连续、可微,且这些方法仅能求得局部极值点。[1]遗传算法(GA)是由美国Holland教授及其学生和同事发展起来的,目前已
3、得到了广泛的研究和应用。GA是一种通用的求解优化问题的方法,它吸取了自然界的自然选择,适者生存等思想,在每次迭代中都保留一组候选解,并按某种指标从解群中选取较优的个体,利用一些遗传算子(如交叉和变异等)对其进行运算,产生新一代的候选解群,重复此过程,直到满足某种收敛指标为止。由于遗传算法无需优化问题有连续性和可微性的限制,只要求被优化的问题是可计算的,同时遗传算法是基于群体进化的算法,且能收敛到全局最优解,这样就克服了传统的基于梯度优化方法的一些缺点。GA已被广泛应用于各种优化问题中,如神经网络训练算法
4、,调度问题,机器学习中的分类系统,组合优化等问题。但这些大多是无约束优化问题。对基于遗传算法的有约束非线性优化问题,是近期才逐渐研究和应用的。2基于遗传算法的非线性约束优化方法实际工程中的各种优化问题,最终都可化为非线性约束优化问题的求解,通常可描述为下列形式minimizef(x)(1)subjecttoCi(x)=0,i=1,2,⋯,meCi(x)≥0,i=me,me+1,⋯,mX国家“九·五”攻关课题1997-05-27收稿,1997-09-14修回第13卷第2期第13卷第2期吴志远等:基于遗传算
5、法的退火精确罚函数非线性约束优化方法137n其中x∈R,f(x)是被优化的目标函数,me是等式约束的个数,m是整个约束的个数。用遗传算法求解约束优化问题的难点在于:1)不可行解可能产生偏离可行域的解;2)遗[2]传因子作用于可行解后,可能产生不可行解。目前,在遗传算法中,已有几种常用处理约束的方法:抛弃不可行解法(rejectionofinfeasibleoffspring),修复不可行解法(repairofinfeasible[3]offspring),改变遗传因子法(modifiedgenetico
6、perators),惩罚函数法(penaltyfunctions)。抛弃不可行解法是将产生的不可行后代完全丢掉。这种方法虽然消除了不可行解,维持了解群的可行性,但其搜索效率较低,尤其当解群中含有较多的不可行解时。修复不可行解法是通过特殊的修复算法将产生的不可行解修复成可行解。该算法的最大缺点是依赖于所要解决的问题。对于不同的问题需要设计不同的修复算法,对于某些复杂的优化问题,设计相应的修复算法是较为困难的。改变遗传因子法是通过特殊的遗传因子,在这些遗传因子作用之后产生的后代均为可行[4,5]解。但是该方
7、法仅能处理线性约束的优化问题。对于非线性的约束问题则无能为力。以上方法或多或少都与所要解决的问题有关。惩罚函数法则克服了这种缺陷,它通过对不可行解施加某种惩罚,经过不断迭代后,使解群逐渐收敛于可行的极值点。目前该方法是遗传算法中求解约束优化问题的一种常用的方法。惩罚函数法的关键问题是对不可行解的罚函数的选取。如果罚函数取得过大,有可能使算法过早地收敛于非极值点;而罚函数取得过小,又可能使算法的收敛性能很差。3基于遗传算法的退火精确罚函数算法311惩罚函数法惩罚函数法最早是在最优化问题中用来处理非线性约束
8、优化的一种方法,它通过对约束条件施加惩罚函数而使有约束问题变为无约束优化问题,从而利用成熟的无约束优化方法求解。对于式(1)的求解可以化为下列无约束问题的求解minimizeF(x,Rk)=f(x)+P(Rk,x)(2)其中P(Rk,x)是惩罚函数,Rk是惩罚因子。针对不同的惩罚函数,形成了不同的方法,主要有外[6]罚函数法,内罚函数法,乘子法和精确罚函数法。外罚函数法和内罚函数法容易引起求解问题的病态问题,这是由于它们需要罚因子无限增大而
