6H,V$$#一圈中只有最短路径的蚂蚁才进行信息素 修 改 增 加 !这 与 蚁 周 系 统 %,+879781H!Q;#模 型 调 整 方 法 相 似 $##为 了 避 免 算 法 过 早 收 敛 于 非 全 局 最 优 解 !
将各路径的信息素轨迹强度限制 在&6H3+!6H,V’之 间! 超出这个范围的被强制设为6H3+或 者6H,V!从 实 验 结 果看!@@Q;算法在防止算法过早停滞及 有效性 方
处 !要 么 进 行 邻 域 搜 索 9
可 见 一 旦 蚂 蚁 个 数 足 够 多 !搜 索 半 径 足 够 小 !这
种搜寻方式相当于一 群 蚂 蚁 对 区 间 %.!A#做 穷 尽 的
面对 Q;算法有较大的改进>
$!基于 ‘Q 与 QQ 的混合算法的设计
;>:!函数优化问题的 QQ 模型 在函 数 优 化 问 题 中!由 于 最 初 的 蚂 蚁 算 法 思 想
源于离散型的网络 路 径 问 题!因 此 必 须 对 模 型 中 的 实 施 细 节 加 以 修 正&A’>本 文 主 要 研 究 的 是 一 维 函 数 的优化问题>
65-*)(,*%Q3H1D,8801W*(I-1H7(.-(B7(-)83(+W*1<373(+I941+183<,-4(*380H,+D7-(B*17(-63+47W11DI9 ,+8,-4(*380H$,09I*3D,-4(*380HI,71D(+41+183<,-4(*380H,+D,+8,-4(*380H B,7W*171+81D>J01H1*38 (.,Y)3<[,+D*,+D(H4-(I,-71,*<03+43+41+183<,-4(*380H B,7)71D3+8(801W*(W(71D09I*3D,-4(*380H> J01<(D3+4,+D.38+177.)+<83(+ B,7D1734+1D$,+DW(W)-,83(+W*(D)<3+4,+D<0*(H(7(H171-1<83(+ B1*1 W1*.(*H1D>J01D1734+(.<*(77(61*(W1*,8(*,+D H)8,83(+(W1*,8(*B,7D181*H3+1D$,+D801+W01*(H(+1 D378*3I)83(+B,7,<03161D>J01 H1*387(.W(738361.11DI,<[3+,+8,-4(*380H$801W,*,--1-W*(<1773+4,+D 4-(I,-71,*<03+4B1*1)83-3C1D3+801W*(W(71D09I*3D,-4(*380H$,+D8013+383,-6,-)1(.,88*,<83(+3+81+7389 B,7<(+.3*H1D>J01H(D1-(.3+81+7389)WD,83+4B,7718)W$,+D801+8011V,<87(-)83(+B,7(I8,3+1D>J01 ,-4(*380H B,7,WW-31D8(7(-61.)+<83(+(W83H3C,83(+W*(I-1H7>J01*17)-8770(B80,8<(HW,*1DB38041G +183<,-4(*380H ,+D ,+8,-4(*380H$801 W*(W(71D ,-4(*380H <(+61*417.,781*,+D 0,7 I1881*71,*<03+4 ,I3-389> 7&8.")9-%41+183<,-4(*380H&,+8,-4(*380H&.)+<83(+(W83H3C,83(+
摘!要#针对遗传算法求解精度低以及蚂蚁算法求解速度慢的 问 题$提 出 一 种 基 于 遗 传 算 法 和 蚂 蚁 算 法 的 混 合 算 法>该混合算法利用了遗传算法快速随机的全局搜索能力的优点$设计了编码与 适 应 度 函 数$进 行 了 种 群 生 成 与 染 色 体 的 选 择 $并 通 过 设 定 交 叉 算 子 和 变 异 算 子 $生 成 了 信 息 素 分 布 >该 混 合 算 法 利 用 了 蚂 蚁 算 法 正 反 馈 以 及 具 有 分 布式并行全局搜索能力的优点$通过确定吸引强度 的 初 始 值$建 立 了 强 度 更 新 的 模 型$从 而 求 得 精 确 解>并 将 该 算 法 应 用 于 求 解 函 数 优 化 问 题 >结 果 表 明 $该 混 合 算 法 与 遗 传 算 法 和 蚂 蚁 算 法 相 比 $收 敛 速 度 快 $寻 优 性 能 好 > 关 键 词 #遗 传 算 法 &蚂 蚁 算 法 &函 数 优 化 中图分类号#JK"#!!!!!文献标识码#Q!!!!!文章编号#"%%P E&#R"$%%&#%# %!$& %!
第 !" 卷 第 # 期 $%%& 年 # 月
浙! 江 ! 大 ! 学 ! 学 ! 报 !工 学 版 "
’()*+,-(./0123,+4 5+361*7389!:+43+11*3+4;<31+<1"
=(->!" ?(># @,*>$%%&
基于遗传算法和蚂蚁算法求解函数优化问题
杨剑峰
"浙江大学 电气工程学院$浙江 杭州 #"%%$&#
!! 函数优化 问 题 是 在 工 程’控 制’决 策 中 普 遍 存 在的一类优化问题$其 优 化 目 标 函 数 可 能 包 含 多 个 在一定范围内的连 续 变 量$传 统 的 优 化 手 段 对 目 标 函 数 要 求 苛 刻 $如 需 要 满 足 可 导 或 者 可 微 等 >导 致 有 些函数难以优化$容 易 陷 入 局 部 解 而 难 以 得 到 全 局 最优解$收敛速度 较 慢>近 年 来$人 们 从 仿 生 学 的 机
理中受到启发$提出 了 许 多 用 于 求 解 函 数 优 化 问 题 的 新 方 法 $如 模 拟 退 火 算 法 ’遗 传 算 法 ’蚁 群 算 法 等 > 然而对于函数优化 问 题 的 复 杂 性$每 种 算 法 都 表 现 出各自的优势和缺陷>
遗传 算 法 "41+183<,-4(*380H$‘Q#是 T(--,+D 教授首 先 提 出 来 的 一 类 仿 生 型 优 化 算 法>在 使 用
因此本 文 算 法 吸 取 了 ‘Q 和 QQ 的 优 点!采 用 ‘Q 生成信息素分布!利用 QQ 求 精 确 解!力 求 将 两 种算法优势互补!期 望 同 时 获 得 较 好 的 优 化 性 能 和 时间性能>
. &6%2%$#’!&’%2’& $2 "3!
0 C%2!= I - *"3 &6%*%$#’!&’%*’&
!$P
ห้องสมุดไป่ตู้
浙!江!大!学!学!报!工学版"!!!!!!!!!! !第!"卷!
‘Q 算法求解 函 数 优 化 问 题 时!一 般 先 将 实 际 问 题 进行数学建模!将其 抽 象 为 一 个 数 值 函 数 的 优 化 问 题>‘Q 提供了一种求解这种优 化 问 题 的 通 用 框 架> ‘Q 通过对群 体 所 施 加 的 迭 代 优 化 过 程!不 断 将 当 前群体中具有较高适应度的个体遗传到下一代群体
循环中)%E#的 变 化 量!定 义 为 )%E_,#F)%E#!
%&(&"!于 是 函 数 优 化 就 借 助 - 个 蚂 蚁 的 不 断 移
动来进行9当’%2$% 时!蚂蚁%按概率C%2 从其邻 域% 移至 蚂 蚁2 的 邻 域$当’%2 &% 时!蚂 蚁% 做 邻 域 搜
索!搜索半径为,!即每个 蚂 蚁 要 么 转 移 至 其 他 蚂 蚁
中 !并 且 不 断 地 淘 汰 适 应 度 低 的 个 体 !从 而 最 终 寻 找 出适应度最大的 个 体>其 优 点 是""#具 有 大 范 围 全 局搜索的能力!与 问 题 领 域 无 关$$#搜 索 从 群 体 出 发 !具 有 潜 在 的 并 行 性 $可 进 行 多 值 比 较 !鲁 棒 性 强 $ 搜索使用评价函 数 启 发!过 程 简 单$##使 用 概 率 机 制进行迭代!具有 随 机 性$具 有 可 扩 展 性!容 易 与 其 他算法结合>但是缺点是 ‘Q 算 法对 于 系统 中 的 反 馈信息利用不够!当 求 解 到 一 定 范 围 时 往 往 做 大 量 无 为 的 冗 余 迭 代 !求 解 效 率 低 >
如路径%%!2#在$时 刻 信 息 素 轨 迹 强 度 为6%2!蚂 蚁= 在路径%%!2#上 留 下 的 单 位 长 度 轨 迹 信 息 素 轨 迹 强 度 $6%2!=!轨迹的持久 性(%%&(&"#!则 轨 迹 强 度 的 更新方程为
0 6%2%$L"#I((6%2%$#L $6%2!=%$#9 %"#