性的“测度”。设计惩罚函数没有一般规则,这仍要依赖于待解的问题。
图 4-3 解空间:可行域与不可行域
惩罚技术通过惩罚不可行解将约束问题转化为无约束问题。构造带有惩罚项的评估函数的方法一般有两种。一种采用加法形式:
其中, 代表染色体; 是问题的目标函数; 是惩罚项。对于极大化问题,取
令 和 分别为现行种群中的 的最大值和 的最小值。并要求
以免出现负的适应值。对于极小化问题,则取
另一种方法是采用乘法形式:
这时,极大化问题可以取为
对于极小化问题则取
注意,对于极小值问题,较好的染色体具有较低的 值。对于某些选择方法,需要将目标值转化为适值,使得较好的染色体有较大的适值。
遗传算法领域里提到了若干种控制不可行性的方法。一般可以分为两类:
(1) 定量惩罚
(2) 变量惩罚
定量惩罚法对于复杂问题不太有效,最近的工作集中在变量惩罚上。
一般,变量惩罚法包含两部分:
(1) 可变惩罚率
(2) 违反约束的惩罚量
可变惩罚率可以按一下因素调节:
(1) 违反约束的程度
(2) 遗传算法的迭代次数
Michalewicz指出,前者随约束违反变得严重而增加惩罚压力,属于静态
惩罚;后者随进化过程的进展而增加惩罚压力,属于动态惩罚。
基本上,惩罚是距可行域的距离的函数。这个距离可按以下三种方式测量:
(1) 单一不可行解的绝对距离的函数
(2) 现行种群中所有不可行解的相对距离的函数
(3) 自适应惩罚项的函数
多数算法采用第一种方法。对于约束严的问题,每代中不可行解与可行解的比较高。这时,第二种和第三种有可能在保留信息和增加对不可行性的压力之间寻求折衷。
惩罚法可进一步分为
(1) 问题依赖的
(2) 问题独立的
多数惩罚技术属于前者
(1) 带参数的
(2) 不带参数的
多数惩罚技术属于带参数的。参数惩罚函数似乎都是问题依赖的。
按照惩罚函数的分类,我们介绍几种求解非线性规划问题的遗传算法狗早惩罚函数的方法。
(1) Homaifar,Qi和Lai方法
Homaifar等考虑如下非线性规划问题:
取加法形式的惩罚函数
惩罚函数由两部分组成:①可变乘法因子和②违反约束惩罚。其表达式如下:
其中 是约束 的可变惩罚函数系数。对于每个约束,又可以分为几个违反级, 相应变化。然而,对每个约束确定违反级和适合的 的值也不是一件容易的事,这要依赖于要解的问题。
Homaifar,Qi和Lai方法对应的函数为:
float HomaifarPunish(SensorPosition SensorPositionArray[],SensorRectangle SensorRectangleArray[],float HomaifarPunishParameter[])
这里只需将相应的问题转化为求目标函数最大值的问题。将边界条件转化为不等式条件即可。
(2)Smith,Tate和Coit方法
自适应惩罚函数是有Smith和Tate首先提出的,该惩罚函数能根据获得的最好解的适应值动态地标定惩罚的量级。随着较好的可行解和不可行解被找到,加给某些给定的可行解上的惩罚可以改变。Coit和Smith进一步扩展了以上的工作,并提出近可行性阈的概念,简称NFT。外部惩罚函数为了给定解可行域的“距离”的非减函数。NFT是一个与可行域距离有关的阈值,距离小于NFT后认为搜索“变热”。给惩罚函数将鼓励在可行域和NFT的邻域内搜索,而限制在阈值界定的邻域外的搜索。
- 上一篇:关于s-凸函数的性质及其不等式的研究
- 下一篇:配煤槽水分分布模型的有限元解法模拟仿真
-
-
-
-
-
-
-
乳业同业并购式全产业链...
电站锅炉暖风器设计任务书
java+mysql车辆管理系统的设计+源代码
当代大学生慈善意识研究+文献综述
杂拟谷盗体内共生菌沃尔...
十二层带中心支撑钢结构...
中考体育项目与体育教学合理结合的研究
河岸冲刷和泥沙淤积的监测国内外研究现状
大众媒体对公共政策制定的影响
酸性水汽提装置总汽提塔设计+CAD图纸