一种改进的自适应遗传算法

(’( 中，交叉率和变异率随着个体的适应度 在 种 群 平 均 适 应 、 （! ） 所示， 图% 度和最大适应度之间进行线性调整。如公式 （% ）
（, ） 是交叉率自适应调整曲线， 图% （- ） 是变异率自适应调整曲 线。 ） % %.,/ &% ’ " $（ ， % ’!%()*
#
!" #$ %.,/ &%()* %$ !
12/3 函数设计出的求解最大优化 问 题 时 的 交 叉 率 及 变 异 率 的 及公式 （# ） 所示， 其中， 自适应调整公式分别如公式 （5 ） #’ 。图 （ ） 是 求解最大优化问题时的自适应交叉 4$4"-5-& 5 8 9:;:
作者简介： 金晶 （%V&!H ） ， 女， 硕士生， 主要研究方向为声音信号处理、 掩蔽效应、 遗传优化算法。苏勇 （%V&"H ） ， 男， 硕士生， 主要研究方向为通信与 信息系统、 遗传优化算法。
FB
!""#$%& 计算机工程与应用
叉率的大小决定新个体产生速度的快慢， 交叉率越大， 旧个体 的模式越容易被破坏， 新个体产生的速度就越快。过高的交叉 率可能使较优良的个体的模式遭到破坏， 过小的交叉率又会延 缓新个体的产生， 导致算法早熟， 停滞不前。 变异率是决定算法 跳出局部最优解的一个关键因素。变异率过小， 不易生成新的 模式结构， 而变异率过大， 会 使 ’( 成 为 纯 粹 的 随 机 搜 索 算 交叉和变异 法 )%"*。是否收敛到全局最优解将不再取决于选择、 操作， 而主要取决于种群规模和演化代数。 如果使用 +’( ， 针对 不同程度的优化问题就必须通过反复地试验调整好交叉率和 变异率， 这是极不方便的， 且难以保证获得最佳的参数值。在
%
引言
4%5 遗传算法 （’()(*+, -./01+*23， 以 下 简 称 ’- ） 是一种模仿
4B5 称 -’- ） 以来， 自 适 应 调 整 交 叉 率 和 变 异 率 被 应 用 到 ’- 中 ，
从而较好地提高了 ’- 的收敛速度 4#CD5。然而， -’- 在演化初期 存在停滞现象，故将自适应调整交叉率和变异率的方法用于
（!""# ） 文章编号 %""!H&@@%H %&H""FBH"F
!" #$%&’()* !*+%,-() .)"),-/ !01’&-,2$
3-" 3-"14 56 7’"18 % （ N(:81*3()* 0? -::.+(9 M2O=+,=， P0..(/( 0? A,+(),( ， A0;*2 P2+)8 Q)+<(1=+*O 0? L(,2)0.0/O ， ’;8)/R20; #%"FB"） ! （ A,200. 0? G.(,*10)+, S E)?0138*+0) G)/+)((1+)/ ， A0;*2 P2+)8 Q)+<(1=+*O 0? ’;8)/R20; #%"FB"） L(,2)0.0/O ，
图-
./012/3 函数
’ % 18* (’ % 1/= ,’ % 1/= ， ) *&)"!+ （)"!+ () ） # ! （ （ ） ） %()*+ # %, $% &$ )"!+ ()1/= # ) */)"!+ %’ %1/=
"
（> ）
如图 - 所示， 当 "! ! ./012/3 函数拥有平滑的顶部和底部。 （! ） 当 "! 6,4$4"-5-& 时 ， （! ） 4$4"-5-& 时 ， ! ’% ； ! ’" 。 利 用 ./07
)%"*
7(’( 的优化机理
为避免 (’( 在上述情况下停滞不前， 首先， 应使交叉率和 变异率的自适应调整曲线 %()* 在处缓慢改变，从而大面积地提 高适应度接近平均适应度的个体的交叉率和变异率。其次， 保 证当代种群中较优个体仍具有一定的交叉率和变异率。 为了能 在算法演化后期尽可能地保留较优个体的模式，应平滑 %.,/ 处 的自适应调整曲线。 在神经网络中，构造神经元激活函数 最 常 用 的 是 638.93: 函数， 如公式 （0 ） 所示。 该函数在线性和非线性行为之间显现出 较好的平衡 );*。 计算机工程与应用 !""#$%&
#
局部收敛。
（, ） 自适应交叉率调整曲线 （$#$ %#$ !） （, ） 个体在 (’( 中的自适应交叉变异调整
（- ） 自适应变异率调整曲线 （$’#$ 0#$ 1） 图%
(’( 自适应调整曲线
（- ） 个体在 7(’( 中的自适应交叉变异调整 图!
根 据 +2345,6 等 提 出 的 (’( ， 当个体的适应度低于当代种 群的平均适应度时， 认为该个体性能不佳， 若该个体在选择机 制下被选中， 将对其采用较大的交叉率和变异率。当个体适应 度接近当代种群中的最大适应度时，认为该个体性能较好， 应 尽可能保留其优良模式，即使该个体在选择机制中被选中， 也 会对其采用较低的交叉率和变异率。 (’( 在 进 化 初 期 并 不 理 想， 因为在进化初期的群体中， 较优个体几乎处于一种不发生 变化的状态， 而此时的优良个体不一定是全局最优解， 这容易 由于初 使进化走向局部收敛的可能性增加 。 (’( 进化后期，
（’-=） !9:,&+/,： ’()(*+, 8./01+*23= 81( =*0,28=*+, 0:*+3+R8*+0) 3(*209= ;=+)/ *2( ,0),(:* 0? )8*;18. (<0.;*+0) 8)9 )8*;>
18. /()(*+,=$L2( =*8)9819 ’- 28= =;,2 9+=89<8)*8/(= 8= :1(38*;1( ,0)<(1/(),(， .0T ,0)<(1/(),( =:((9 8)9 .0T 10> U;=*)(==$-98:*8*+0) 0? :8183(*(1= 8)9 0:(18*01= += 0)( 0? *2( 30=* +3:01*8)* 8)9 :103+=+)/ 81(8= 0? 1(=(81,2 +) ’-$ L2+= :8:(1 :1(=()*= 8 3(*209 ?01 0:*+38. 9(=+/) 0? 8) +3:10<(9 898:*+<( ’()(*+, 8./01+*23$L2( ,8=( =*;9O 0? 9(=+/)> +)/ 8)9 =+3;.8*+0) =20T= 0;1 )(T 3(*209 28= ?8=*(1 ,0)<(1/(),( =:((9 8)9 2+/2(1 10U;=*)(==$ ;)<=’&*:： ’()(*+, -./01+*23=， 10U;=*)(==， 898:*8*+0) ， ,0)<(1/(),(
一种改进的自适应遗传算法
金
!
晶%
苏
勇!
% （华南理工大学应用物理系， 广州 #%"FB"） （华南理工大学电子与通信工程系， 广州 #%"FB" ）
GH38+.： I(8)*+3(JK%F@$,03
摘 要 遗传算法作为一种模仿生物自然进化过程的随机优化算法，对求解一般的全局最优问题具有较好的鲁棒性，
生 物 群 体 进 化 的 随 机 优 化 算 法 ， 它 是 由 美 国 密 歇 根 大 学 6$7$
70..8)9 教授创立的。 ’- 拥有一个代表了问题可能潜在解集的 ， 种群中的个体 （+)9+<+9;8.=） 在选择 （=(.(,> 种群 （:0:;.8*+0) ） 、 交叉 （,10==0<(1） 以及变异 （3;*8*+0) ） 算子的作用下向更高 *+0) ） 进化以达到寻求问题最优解的目标 4!5。 交叉和 的适应度 （?+*)(==） 变异是影响 ’- 行为和性能的关键。
期难以跳出局部最优解， 导致算法最终陷入局部收敛。
!$!
改进的自适应遗传算法
’( 的自适应能力应该体现在种群中的个体能根据周围环
<#
（! ） ! ’
% （,"! ） %()*+
（- ）
算法力求跳出局部收敛。 给出 9:;: 求解最小优化问题时的自适应 调 整 公 公式 （> ） 给 出 9:;: 求 解 最 小 优 化 问 题 时 的 自 适 应 变 异 调 式， 公式 （? ） 整公式， 其中， 图# （8 ） 是 9:;: 求解最小优化问题 :’4$4"-5-& 。 （< ） 是 9:;: 求解最小优化问 时的自适应交叉率调整曲线， 图# 题时的自适应变异率调整曲线。
境的变化自动发现环境的特性和规律， 最明显的环境特征就是 种群中个体的适应度， 最明显的演化规律就是种群中个体适应 度与平均适应度、 最小适应度以及最大适应度的关系。生物在 进化过程中， 并不记忆当前演化到哪一代， 它所关心的是自身 适应环境的能力是否得到了提高， 如果没有， 那么它被自然界 淘汰的几率就增大， 如果有提高， 表明它拥有较良好的模式， 在 个体的 算法设计中， 尽可能地把这种模式保留下来 。 (’( 中 ， 交叉率及变异率根据个体的适应度在平均适应度与最大适应 度之间进行线性变换， 并且最低交叉率和最低 变 异 率 为 " 。 当 种群中出现较多适应度接近平均适应度的个体时， 这些个体的 模式相当， 且占据了种群的大部分， 如图 ! （, ） 中较密集部分所 示。若平均适应度与当代种群中的最大适应度接近， (’( 的自 适应交叉、 变异调整曲线会变得更陡峭， 这些个体的交叉率和 变异率也因此产生较大差异， 导致大部分个体只能拥有较低的 交叉率和变异率， 使演化停滞不前。另外， 在算法演化初期， 种