第
13
卷
3
期
第
兰州工业高等专科学校学报
Vol. 13 ,No. 3
2006
年
9
月
Journal of Lanzhou Polytechnic College
Sep. ,2006
文章编号
:1009 - 2269 (2006) 03 - 0001 - 04
遗传算法中适应度½数的研究
刘
英
(
西北师范大学 数学与信息科学学院
,
甘肃 兰州
730070)
摘要
:
通过分析遗传算法中常见的几种适应度½数的不足
,
论证了适应度½数在遗传算法中的重
要性
,
提出了设计适应度½数应满足的标准
,
在此基础上给出了一适应度½数公式
.
实验结果表
明
:
此适应度½数的性½明显优于其它½数
,
对提高遗传算法的整½性½也有重要意义
.
关
:
遗传算法
;
适应度½数
;
最优设计
;
性½分析
键 词
中图分类号
: TP 301. 6
文献标识码
: A
0
引 言
遗传算法是模拟生物在自然环境中遗传和进化过程而½成的一种自适应全局化概率搜索算法
.
它最
早是由美½密执安大学的
Hollan
教授提出
,
起源于
60
年代
,
对自然和人工自适应系统的研究
[1 ]
.
遗传算法
对包含可½解的群½反复½用遗传学的基本操½
,
不断生成新的群½
,
½种群不断进化
,
同时以全局并行
搜索技术来搜索优化群½
,
以取得满足要求的最优个½
,
得到满足要求的最优解
.
因此求解复杂½数的最
优化问题是遗传算法
( Ge - neticAlgorithms , GAs)
的一个重要研究方向
.
众所周知
,
用
GAs
求解½数最优化问题时
,
是依靠适应度½数值的大小来区分每个个½的优劣的
.
适
应度值大的个½将有更多的机会繁衍下一代
,
通常取高于群½平均适应度值的个½做交叉
,
而½于平均适
应度值的个½做变异
,
从而一代一代地提高群½的平均适应度值和最优个½的性½
.
可见
,
适应度½数在
GAs
中起着决定性½用
.
为此
,
本文以½数最优化问题为背景
,
在现有结果的基础上对适应度½数做进一
步研究
.
1
适应度½数分析
适应度½数
( Fitness Function)
的选取直接½响到遗传算法的收敛速度以及½否找到最优解
[2 ]
,
因为
遗传算法在进化搜索中基本不利用外部信息
,
仅以适应度½数为依据
,
利用种群每个个½的适应度来进行
搜索
.
因为适应度½数的复杂度是遗传算法复杂度的主要组成部分
,
所以适应度½数的设计应½可½简
单
,
½计算的时间复杂度最小
.
遗传算法评价一个解的½坏不是取决于它的解的结构
,
而是取决于该解的
适应度值
,
这正½现了遗传算法
“优胜劣汰”
的特点
.
遗传算法不需要适应度½数满足连续可微等条件
,
唯
一要求是针对输入可计算出½加以比较的非负结果
.
这一特点½得遗传算法具有广泛的适用性
.
在实际问
题中
,
适应度½数与问题的目标½数是不完全一致的
,
如有的问题的目标是要求得最小值
(
费用问题
) ,
而
有的问题的目标是要求得最大值
(
利润½数
) .
因此在不少场合
,
将目标½数映射成求最大值½式而且½数
值非负的适应度½数是必要的
.
Ξ
收稿日期
:2006 - 03 - 22
基金项目
:
甘肃省自然科学基金
( 3ZS051 - A25 - 047)
½者简介
:
刘
( 1979 - ) ,
女
,
甘肃兰州人
,
硕士生
.
英
Ξ
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.
http://www.cnki.net
州 工 业 高 等 专 科 学 校 学 报
13
卷
兰
第
・
2
・
1. 1
几种常见的适应度½数及其不足
在½数优化中
,
适应度½数可由目标½数变换得到
,
一般而言有以下
3
种定义½式
:
1)
直接以待求解的目标½数½化为适应度½数
,
即
若目标½数为最大化问题
f ( x ) = g ( x ) ;
若目标½数为最小化问题
f ( x ) = - g ( x ) .
这种适应度½数简单直观
,
½实际应用时
,
存在以下
2
个问题
:
第一
,
不满足常用的赌盘选择非负的要
求
;
第二
,
某些待求解的½数值可½½此相差十分悬殊
,
由此得到的平均适应度值可½不利于½现群½的
平均性½
,
将½响算法的效果
.
2)
若目标½数为最小问题
,
则
c
max
- g ( x ) ,
g ( x ) < c
max
,
其他情况
0
其中系数
c
max
存在多种选择方法
,
它可以是一个合适的输入值
,
也可以采用迄今为止进化过程中
g ( x )
的
最大值
,
½
c
max
最½与群½无关
.
由于参数
c
max
需事先预估
,
不可½精确
,
其结果常常是适应度½数不灵
敏
,
½响了算法的性½
.
若目标½数为最大问题
,
则
,
其他情况
0
其中系数
c
min
存在多种选择方法
,
它可以是一个合适的输入值
,
也可以采用迄今为止进化过程中
g ( x )
的
最小值
,
½
c
min
最½与群½无关
.
3
)
若目标½数为最小问题
,
则
f ( x) =
f ( x) =
g ( x ) - c
min
,
g ( x ) > c
min
f ( x) =
1
g ( x) + c +
1
,
c
≥
0
, c + g ( x )
≥
0
若目标½数为最大问题
,
则
,
c
≥
0
, c - g ( x )
≥
0
1
+ c - g ( x)
上两式
c
为目标½数界限的保守估计值
.
由于事先不知道
min
g ( x ) ,
故
c
的取值只½采取保守的估计
f ( x) =
1
值
,
存在和第二种适应度½数相似的问题
.
适应度½数对
GA
的收敛速度和结果½响很大
.
如果过分强调
½前的较优点
,
就可½很快降½种群的多样性
,
造成不成熟收敛
;
如果对½前较优点强调不够
,
算法就很容
易丢失已经找到的较优点信息
,
从而不½在合理的时间内收敛到较½的点
.
1
.
2
适应度½数的½用
在遗传算法中
,
适应度是描述个½性½的主要指标
[
3
]
.
根据适应度的大小
,
对个½进行优胜劣汰
.
适应
度是驱动遗传算法的动力
.
从生物学角度讲
,
适应度相½于
“生存竞争 、
适者生存”
的生物生存½力
,
在遗
传过程中具有重要意义
.
将优化问题的目标½数与个½的适应度建立映射关系
,
即可在群½进化过程中实
现对优化问题目标½数的寻优
.
适应度½数也称评价½数
,
是根据目标½数确定的用于区分群½中个½½坏的标准
,
总是非负的
,
任
½情况下½希望它的值越大越½
.
在选择操½中
,
会出现
2
个成为遗传算法欺骗的问题
:
1
)
在遗传算法初期
,
通常会产生一些超常个½
,
按照比例选择法
,
这些超常个½会因竞争力突出
,
而
控制选择过程
,
½响到算法的全局优化性½
;
2
)
遗传算法后期
,
½算法趋于收敛时
,
由于种群中个½适应度差异较小
,
继续优化的½½降½
,
可½
获得某个局部最优解
.
因此
,
如果适应度½数选择不½就会产生以上的欺骗问题
.
可见适应度½数的选择对于遗传算法的意
义重大
.
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.
http://www.cnki.net
第
3
期 刘 英
:
遗传算法中适应度½数的研究
・
3
・
2
适应度½数的设计
适应度½数的设计主要满足以下条件
:
1
)
单值 、
连续 、 、
非负 最大化
.
适应度½数
Fit ( f ( x ) )
应该是实½数
,
并且单值 、
连续
,
½不要求可导
.
不过
, Fit ( f ( x ) )
的曲线在重要
部½
,
特别在最优解附近一般不宜太陡也不宜过于平缓
.
2
)
合理 、
一致性
.
是指适应度½数曲线上
,
各点的适应度值应与解的优劣成反比例
,
即
x
1
, x
2
, ( x
1
, x
2
)
∈
[
lmin ,lmax
]
∧
f ( x
1
) < f ( x
2
)
→
Fit ( f ( x
1
) ) > Fit ( f ( x
2
) ) ,
其中
[ lmin ,lmax]
是½
数
f ( x )
的定义域
.
3
)
计算量小
.
Fit ( f ( x ) )
不应设计得过于繁复
,
应在上述条件下越简单越½
.
4
)
通用性
.
一个适应度½数的½坏
,
还应满足½可½广泛的通用性
,
½用户在求解种种问题时
,
最½无需改变适
应度½数中的参数
.
通用性要求是对适应度½数设计的更高一层的要求
.
它½½用户在对所求解½数的全
局最优解的性质完全
“无知”
的情况下
,
由算法在运行过程中自动修正其中的参数值
,
从而一步一步接近
最优解
.
从另一种意义上说
,
这样的适应度½数具有自适应性
.
本文建议的一类适应度½数定义为
1
-
0
.
5
×
[ |
Fit ( f ( x ) ) =
f ( x) - b
α
| ] , | f ( x) - b | < a
a
, | f ( x) - b |
≥
a
1
f ( x) - b
β
1
+ [|
| ]
a
理想情况下
: b
的值是
min
f ( x ) = y
3
,
½适应度值为
0
.
5
时
,
α
是
f ( x )
到
min
f ( x )
的距离
.
考虑到适应度½
数的不同应用场合
,
本文将
β
值取为
2
,
将
α
值分别取为
1
,
1
.
5
,
0
.
5
.
即可在
b , a
取定的情况下得到
3
种适
应度½数
.
解附近点的适应度值
,
便于做出敏感选择
,
从而有利于以后的选择
;
½
α
=
1
.
5
时的适应度½数则有相反的适应情况
.
即
b = f ( x )
3
i ;
而
a
则建议用公式
母变大
) ;
同样
,
若要求适应度½数曲线
“缓”
一点
,
可以把系数适½调大一些
(
例如将分母变小
) .
数
,
用
α
=
0
.
5
可以½适应度½数较灵敏地反映出
y
值的变化情况
.
在算法的后期
,
则可以有效地拉开最优
求取
,
若要求适应度½数曲线变化得
“陡”
一些
,
只需把公式中的相关系数调节得再小一些即可
(
例如将分
3
实验结果及结论
为考察该适应度½数的性½
,
本文选用了一组测试
GAs
性½的经典½数
,
包括多峰 、
非凸 、
病态等常
规方法难于求解的½数对适应度½数进行测试
.
算法对每个测试½数均分别独立地运行
60
次
,
求出的均
为全局最优解
.
实验结果表明
,
采用文中的适应度½数的算法性½比一般算法性½有很大的提高
.
限于篇
幅
,
这里不再给出具½的实验结果
.
½取
α
=
1
时
,
适应度值在
[
0
.
5
½
1
]
之间是线性的
;
而对于在全局最优解
y
3
附近变化比较缓慢的½
本文建议公式里的
b
和
a
随遗传算法的下一代进化而不断地修正
. b
的值可取½前第
i
代中的最小值
,
|
max
f i - f i
3
|
a =
max 0
.
5
,
30
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.
http://www.cnki.net
州 工 业 高 等 专 科 学 校 学 报
13
卷
兰
第
・
4
・
4
结论
本文考察了几种常见的适应度½数各自存在的不足以后
,
提出了设计适应度½数的几条标准
,
并在
此基础上依据智½化和自适应的思想
,
提出了本文建议的一种动态变化的适应度½数公式
.
理论分析与各
项测试½表明
,
本文建议的适应度½数的性½比以往的几种适应度½数均有提高
,
并且对遗传算法的整½
性½的提高同样有重要½用
.
参考文献
:
[1 ]
陈½良
,
王煦法
,
庄镇泉
,
等
.
遗传算法及其应用
[M] .
北京
:
人民邮电出版社
,1999.
[2 ]
,
康立山
,
陈镇屏
.
非线性并行算法 ——
刘 勇
— 遗传算法
:
第
2
版
[M] .
北京
:
科学出版社
,1995.
[3 ]
边肇祺
.
模式识别
[M] .
北京
:
清华大学出版社
,1988.
Research on Fitness Function in Genetic Algorithm
LIU Ying
( The Mathematics and Information College of Northwest Normal University ,Lanzhou 730070 ,China)
Abstract :
After analysing some drawback of familiar fitness functions ,this paper discusses the importance of fitness
function in G The most important is that it proposes four standards that fitness function must satisty. At last ,this ar
2
As.
it is important to improve the whole performance of genetic algorithm.
key words :
G ;fitness function ;optimised design ;performance analysis
As
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.
http://www.cnki.net
ticle gives its own fitness function ,and the testing results show that the performance is much better than the others and
京公网安备 11010802033920号
Copyright © 2005-2024 EEWORLD.com.cn, Inc. All rights reserved
评论