罚函数
2011年04月14日
它将有约束最优化问题转化为求解无约束最优化问题:
[/b]
[b] 其中M为足够大的正数, 起"惩罚"作用, 称之为罚因子, F(x, M )称为罚函数.
[/b]
[b] 定理 对于某个确定的正数M, 若罚函数F(x, M )的最优解x* 满足有约束最优化问题的约束条件, 则x* 是该问题的最优解.
[/b]
[b] 序列无约束最小化方法
[/b]
[b] 罚函数法在理论上是可行的, 在实际计算中的缺点是罚因子M的取值难于把握, 太小起不到惩罚作用;太大则由于误差的影响会导致错误.
[/b]
[b] 这些缺点, 可根据上述定理加以改进, 先取较小的正数M, 求出F(x, M )的最优解x* .
[/b]
[b] 当x*不满足有约束最优化问题的约束条件时, 放大M (例如乘以10)重复进行, 直到x* 满足有约束最优化问题的约束条件时为止.
传统的罚函数法一般分为外部罚函数法和内部罚函数法。外部罚函数法是从非可行解出发逐渐移动到可行区域的方法。内部罚函数法也称为障碍罚函数法,这种方法是在可行域内部进行搜索,约束边界起到类似围墙的作用,如果当前解远离约束边界时,则罚函数值是非常小的,否则罚函数值接近无穷大的方法。
由于进化计算中通常采用外部罚函数法,因此本文主要介绍外部罚函数法。在进化计算中,研究者选择外部罚函数法的原因主要是该方法不需要提供初始可行解。需要提供初始可行解则是内部罚函数法的主要缺点。由于进化算法应用到实际问题中可能存在搜索可行解就是NP难问题,因此这个缺点是非常致命的。
外部罚函数的一般形式为
B(x)=f(x)+[∑ riGi+∑ cjHj]
其中B(x)是优化过程中新的目标函数,Gi和Hj分别是约束条件gi(x)和hj(x)的函数,ri和cj是常数,称为罚因子。
Gi和Hj最常见的形式是
Gi=max[0, gi(x)]a
Hj=| hj(x)|b
其中a和b一般是1或者2。
理想的情况下,罚因子应该尽量小,但是如果罚因子低于最小值时可能会产生非可行解是最优解的情况(称为最小罚因子规则)。这是由于如果罚因子过大或者过小都会对进化算法求解问题产生困难。
如果罚因子很大并且最优解在可行域边界,进化算法将很快被推进到可行域以内,这将不能返回到非可行域的边界。在搜索过程开始的时候,一个较大的罚因子将会阻碍非可行域的搜索。如果在搜索空间中可行域是几个非连通的区域,则进化算法可能会仅移动在其中一个区域搜索,这样将很难搜索到其他区域,除非这些区域非常接近。另一方面,如果罚因子太小,这样相对于目标函数罚函数项是可以忽略的,则大量的搜索时间将花费在非可行域。由于很多问题的最优解都在可行域的边界,大量时间在非可行域进行搜索对找到最优解是没有多大作用的,这对于进化算法来说非常致命的。
最小罚因子规则概念是很简单的,但是实现起来却是非常的困难。对于一个确定的进化算法,很多问题的可行域和非可行域的边界是未知的,因此很难确定它的精确位置。
非可行个体和搜索空间可行区域之间的关系对于个体的惩罚时具有非常重要的作用。但是,怎样利用这种关系指导搜索方向并将它引导到期望区域的原理并不清楚。
在现有方法中,主要存在三种定义可行域和非可行域之间关系的方法。
(1) 个体惩罚值仅与它的非可行性有关,与约束违反量无关(即不使用个体与可行域之间距离的信息)。
(2) 违反约束条件的个数作为衡量标准,并且用于确定相应的惩罚值。
(3) 非可行个体的修复代价(即需要修复个体可行性需要的成本)。
很多研究者研究了设计罚函数的启发式方法。其中最著名的是Richardson等人提出的一种方法,它的具体的内容如下:
(1) 采用到可行域距离的罚函数方法比采用约束违反个数的罚函数方法性能优越。
(2) 如果问题仅有几个约束条件并且可行解非常少,则单独使用约束违反个数的罚函数的方法可能找不到任何解。
(3) 罚函数的性能可以通过以下两个标准进行评价:最大完成成本和期望完成成本。完成成本与可行性的距离有关。
(4) 罚函数应该接近期望完成成本,但是并不需要在期望完成成本之下。越精确的罚函数越能够找到更好的解。当罚函数低估完成成本时,搜索可能会找不到解。
罚函数法既可以处理不等式约束也可以处理等式约束,并且一般情况下是将等式约束转化为不等式约束形式
| hj(x)|-e<=0
[/b]
[b] 罚因子:penalty
[/b]
[b] 罚常数:penalty constant
[/b]
[b] 罚函数法:penalty function method
发表评论
-
is-is提高篇2
2012-01-09 09:44 728is-is提高篇2 2009年09月03 ... -
转 考研 二 续
2012-01-09 09:44 693转 考研 二 续 2010年07 ... -
OSPF(Open Shortest Path First)
2012-01-09 09:43 849OSPF(Open Shortest Path First) ... -
具象艺术
2012-01-06 10:03 897具象艺术 2011年12月14日 2011-06-2 ... -
2012年在职攻读艺术硕士(MFA)招生简章【公告类别:艺术硕士】
2012-01-06 10:03 6552012年在职攻读艺术硕士 ... -
《 中国当代艺术“价值观” 》 高岭 (六) 完
2012-01-06 10:03 428《 中国当代艺术“价值 ... -
首都师范大学科德学院2012年艺术类招生简章
2012-01-06 10:03 596首都师范大学科德学院2 ... -
严格落实专武干部和民兵干部政治和生活待遇,建立了民兵干部奖惩制度
2012-01-06 09:58 1824严格落实专武干部和民 ... -
高洁的品格,隐逸的情怀
2012-01-05 13:25 1159高洁的品格,隐逸的情怀 ... -
[转载]古诗词里的雨
2012-01-05 13:25 563[转载]古诗词里的雨 2011年01月07日 描写雨的诗 ... -
读书札记:音律的基本类型
2012-01-05 13:25 945读书札记:音律的基本类型 2010年08月22日 音律 ... -
这盏智慧之灯――我的秘密
2012-01-05 13:25 603这盏智慧之灯――我的 ... -
陶渊明复杂感情世界探微 (转)
2012-01-05 13:25 522陶渊明复杂感情世界探 ... -
感谢之雨 赞美之泉
2012-01-04 15:39 516感谢之雨 赞美之泉 2011年11月08日 早晨送 ... -
学会赞美(2011-11-11 09:57:35)
2012-01-04 15:39 674学会赞美 (2011-11-11 09:57:35) 201 ... -
赞美女性气质形容词
2012-01-04 15:39 1321赞美女性气质形容词 2011年05月12日 女性气质形容 ... -
对女人的赞美之词
2012-01-04 15:39 781对女人的赞美之词 2011年04月22日 对女人的赞美之 ...
相关推荐
基于罚函数法的粒子群算法,处理优化调度问题
MATLAB中解决约束问题的算法,罚函数的粒子群算法的精度高,速度快
通过外点罚函数法求解约束问题中目标函数的最优解
外点罚函数的matlab源码,罚函数之外点罚函数求解约束优化问题,构造惩罚函数,能求解教程例题,跟教材完全对应。
外点罚函数实现代码,罚函数是指在求解最优化问题(无线性约束优化及非线性约束优化)时,在原有目标函数中加上一个障碍函数,而得到一个增广目标函数,罚函数的功能是对非可行点或企图穿越边界而逃离可行域的点赋予一...
通过外罚函数法求解约束优化问题目标函数的最优值
最优化方法中的罚函数法求解方程的根,自己编写的MATLAB程序
最优化 外点罚函数 实例 程序 matlab 经典推荐,希望对大家有所帮助。
基于matlab的带罚函数的自适应粒子群算法+含代码操作演示视频
MATLAB的梯度法,内点法,外点法,罚函数,惩罚函数,线性梯度法,源程序,按照提示输入,可直接运行
MATLAB的梯度法,内点法,外点法,罚函数,惩罚函数,线性梯度法,源程序,按照提示输入,可直接运行-MATLAB' s gradient method, interior point method, outside the point of law, penalty function, penalty ...
利用罚函数求最优值,求解非线性问题的,不等式约束的最优值。
含有约束方程 求最值所用的罚函数+粒子群优化算法
matlab罚函数乘子法.rar
外罚函数程序,采用visual c++编程,优化算法,搜索法
利用增广Lagrange罚函数处理问题的约束条件, 提出了一种新的约束优化差分进化算法。基于增广Lagrange惩罚函数, 将原约束优化问题转换为界约束优化问题。 在进化过程中, 根据个体的适应度值将种群分为精英种群和普通...
为分析圆环链与链轮在启动工况下的瞬间接触动态特性,采用对称罚函数法建立链环与链轮接触理论分析模型;采用有限元法模拟该工况下圆环链传动过程的接触动态特性,得到随时间变化的位移、速度、加速度曲线,以及啮合接触...
外点罚函数优化实例,详细的代码,截图,还有分析
M代码的罚函数程序,包括DFP法以及进退法确定搜索区间。
用matlab实现的牛顿外点罚函数法,求解n个未知变量