解非线性方程自适应变搜索区间的遗传算法

!% $
上式中 1% %1! 为常数 % , &!,&, %,&!)& . %!, %!) 均 可以在算法执 行 过 程 中 动 态 调 节 & ’() %*+,- %./0,- 分 别 为 群 体 中个体的平均 % 最好和最差的适应值 &
作者简介 ! 成媛媛 !!"#!$ $% 女 % 硕士研究生 % 主要研究方向为智能计算 % 演化算法 % 偏微分方程数值解等 & 全惠云 ’!"%&$ $% 男 % 教授 % 主要研究方向 为智能计算 % 演化算法 % 偏微分方程数值解等 &
"#!
杂交概率和变异概率的动态确定
杂交概率 012
$! ’*3*/%,4.35/%36 ! % % # " 789:; <.<+4=*
$
$
% " 789:; 其 中 @%#@! 为 常 数 # 由 实 验 动 态 确 定 $ ’()(*+,-.) 为 进 化 代数 #/0123 为染色体的长度 #4.45-6( 为每代群体的规模 $ 这样确定的 01 #0> 值随着进化代数 而 随 机 进 行 自 适 应 的 更新 $ 总体来说 #01#0> 在进化初期较大 # 随着进化的发展 #01# 0> 值逐渐变小 $ 从而完全符合进化发展规律 $ ’*3*/%,4.35/%36 !
其中 3 为常数 # 一般为染色体长度的 ! 到 ! $ ! !43;, #-./+, 为群体中最大和最小的适应值 $ 可 以 看 出 #适 应 值 大 的 个 体 发 生 变 异 的 位 数 少 #从 而 保 证 了 其 稳 定 性 %适 应 值 差 的 个 体 发 生 变 异 位 数 多 #在 一 定 程 度 上 增 加 了 群体个体的多样性 $
文章编号 %""!=’&&%= !!""# $!%=&&/0$&1
文献标识码 8
中图分类号 CD,0
! "#$%&’(’)#( *#(+,-./ 0.1#23’$ 4#.#1-, !$/52-167 %52 85.$-.#’2 9:+’1-5. "5$+1-5.
;6#./ <+’.=+’. >+’. ?+-=+. !E>*1(2>*+,F >)G H/2I@*(0 J,+(),( H/--(.(%K@)>) 9/02>- L)+M(0F+*? %H1>).F1> <%""’% $
基金项目 ! 国家自然科学基金项目 ! 编号 "%"""%"&"’ # 资助
!
多种参数的动态自适应确定
一般遗传算法有三个关键的进化参数 "!%$适应度函数 ! !"$
! 通过线性定标 %! 截断或是 乘幂标等方法确定 $()!$ 选择概率
$% (!& $ 杂交概率 $&! 完全由算法设计者根据其经验设定 $& 即
以上关键的进化参数都是算法使用者在算法运行之前确定 % 在 算法进行过程中无法对其进行动态修改 & 因此 % 算法缺乏动态 的生命力 % 导致算法的在线性能与离线性能 ;&6降低 & 本文在遗传 算法执行过程中 % 三个关键参数都动态地根据染色体个体当时 的 情 况 确 定 %因 此 算 法 具 有 自 适 应 性 %从 而 能 够 以 概 率 为 % 搜 索到全局最优解 &
/0
!""#$!% 计算机工程与应用
从 !%" 式 可 以 看 出 # 群 体 在 进 化 过 程 中 # 当 ! !" " #$%&%&’ 时 # 算 法 将 动 态 地 将 其 适 应 值 降 低 !!! 越 小 # 适 应 值 降 低 的 程 度就越大 "# 从而很好地抑制了局部最优解的出现 $ 但 ! !" "( $!&%&’ 时 # 算法将动态地将即将死亡的个 体 的 适 应 值 相 对 提 高 !!" 越大 # 适应值提高的程度就越大 "# 从而在一定程度上延 缓了这些个体的死亡 # 保证了群体个体的多样性 $
)*%
适应度函数 ! ""# 的动态确定
" $ $ $ $ # $ $ $ $ %
! !" $5
!"#$%+ !!,-&’(%)!"*$% $+, !( $)!"*$% , !( $01,+234 -.$%)!/*$% !/#$%+ !!)-&.(%)!/#$% $+, !( $)!/#$% , !( $51)+234 &.$%)!/#$% ) )
!!$! ( "
"
*+,-./0 !$#% "
#1 %&’#!(
*+2-.
#其 中 0
!$ #% " %&3 #$3 !%3#! "3 "*+2-.( 表 示 的 是 个 体 $ 和 % 之 间 的
7+88-)’ 距离 #"456"6789$:"$ ;( !$ #% " 表示由种群 <" 到种群 ="
!@A12’,1" N) *1+F I>I(0 %>) +2I0/M(G .()(*+, >-./0+*12 @F(G +) F/-M+). *1( )/)-+)(>0 (O@>*+/) +F I0/I/F(G$N) *1+F +2I0/M(G .()(*+, >-./0+*12 %*1( 2/F* ,0@,+>- I>0>2(*(0F >)G *1( F(>0,1 +)*(0M>- >0( I0(F()*(G */ ,/I( P+*1 I0/Q-(2F$R@0 (SI(0+2()*F F1/P *1>* *1+F +2I0/M(G .()(*+, >-./0+*12 +F I0>,*+,>- >)G (TT+,+()* ,/2I>0(G P+*1 *1( )/02>- .()(*+, >-./0+*12$N) F/-M+). *1( )/)-+)(>0 (O@>*+/)%+* G/(F)U* *>V( *1( +)+*+>- M>-@( >)G *1( +)+*+>- +)*(0M>- +)*/ ,/)F+G(0>*+/) >)G (M() *1/@.1 +) /)( +)*(0M>- *1>* 1>F )/* /)-? /)( 0//*%+* >-F/ ,>) (TT+,+()*-? T+.@0( /@* (M(0? 0//*F %F/ +* ,/)O@(0 *1( *0>G+*+/)>- 2(*1/GUF -+2+*>*+/)$ B#=C52(A " ’()(*+, ( -./0+*12 % T+*)(FF M>-@( % I0/Q>Q+-+*? /T 2@*>*+/) % I0/Q>Q+-+*? /T ,0/FF/M(0 % F(>0,1 +)*(0M>- % )/)-+)(>0 (O@>*+/)
$% #$! 两常数需根据具体函数 # 具体情况动态确定 $ 根据
!% " 式 # 若某个染色体的适应 值 大 于 平 均 适 应 值 的 $% 倍 # 算 法 则自动地调节将其适应值减少 % 若某个染色体的适应值小于平 均适应值的 $! 倍 # 则算法自动调节将其适应值增大 $ 因此 # 当 )*+, #-./+, #%&’ 均 为 正 值 时 #$% #$! 越 小 则 动 态 确 定 的 适 应 度 函数使群体中各个个体的适应度差距变小 # 增加了多个个体进 入下一代的概率 # 保证群体的多样性 $ $%#$! 越大则动态确定 的适应度函数将拉大群体中各个个体的适应度 # 是适应度高的 个体很快占绝对优势 # 迅速收敛到全局最优解 $ 因此 # 我们提出在进化初期采用较小的 $% #$! 值 # 较小 的 值 !! # 较 大 的 !" 值 % 在 进 化 后 期 采 用 较 大 的 $% #$! 值 # 较 大 的 !! 值 # 较小的 !" 值 $
%
引言
遗传算法 !’()(*+, (-./0+*12 $ 是一种模拟达尔文的遗传选
区间内非线性方程 ! 组 $ 的各个根 &
择和自然淘汰生物进化机制的计算模型 % 是一种全局并行优化 搜索工具 % 具有简单 % 通用 % 适于并行分布的特点以及广泛的应 用前景 & 遗传算法是一个迭代的过程 % 每次迭代过程都保留一 组 候 选 解 ! 染 色 体 $% 然 后 按 其 好 坏 进 行 排 序 % 并 按 某 个 指 标 从 中选出一些解 % 进行杂交 % 变异等遗传操作 % 产生新一代的一组 候选解 % 重复此操作 % 直到满足某种收敛条件为止 3%4& 遗传算法 在 搜 索 过 程 中 不 易 陷 入 局 部 最 优 %而 且 不 要 求 适 应 度 函 数 !通 常是问题的目标函数 $ 可微 % 应用范围十分广泛 % 尤其是对非线 性 % 多极值问题更显其优越性 & 对于非线性方程 ! !" $5" 求解 % 传统的数值方法 如 二 分 法 % 试位法 % 牛顿法 % 割线法等 % 均存在着严重的局限性 & 如牛顿法 % 必须已知根的存在区间且不能区分根与奇点 % 即使在较小的求 根 区 间 内 % 当 !# !" $ 5" 或 !# !" $ !" 时 % 方 法 失 效 % 另 一 方 面 % 计 算 过 程 中 !# !" $ 的 计 算 花 费 大 量 时 间 % 方 法 对 初 始 值 的 选 取 十 分敏感 % 选取不当将会导致迭代解不收敛或收敛到一个毫无关 系的解 3!6& 本文结合传统非线性方程求解的数值方法提出了一种自 适 应 变 搜 索 区 间 的 遗 传 算 法 !789: $% 保 证 了 在 任 意 大 小 的 含 根 区 间 内 !允 许 含 有 多 个 根 $以 概 率 为 % 在 有 限 步 内 收 敛 到 该