殊 的 分 泌 物— —信 息 素 （ 着 时 间 的 推 移 该 物 随 质会 逐 渐 挥 发 ）， 来 的 蚂 蚁 选 择 该 路 径 的概 率 后 与 当 时这 条 路 径 上 该 物 质 的 强 度 成 正 比． 在 但 基 本蚁 群 算 法 中 ， 在 收 敛 速 度 较 慢 ， 出现 停 存 易
群算法 结 果与 基 因库 中 已有 基 因 中不 同基 因数 量
在一 次蚁 群算 法 循 环 后 得 到 局部 解 集 后 ， 将 局部 解集作 为 遗 传算 法 的初 始 种 群 基 因 库 ， 用 利 遗传算 法求 得 遗 传最 优 解 ． 从 蚁 群 算 法 的局 部 再 最 优 解 ， 传算 法 的局 部最 优解 与历 史 全 局 最 优 遗
△
下 ：
Ｊｅ 边 ） 生 的 时 短 径 ｓ （ 在 成 临 最 路 中 Ｌｔ ， ｂ若
Ｌ 否则 ０
其中， Ｑ为 的是 信息 素 的强度 ， 次循 环 中找 到 的最 短路 径 长度 ．
表示 蚂蚁 在本
即状 态 转移 规则 、 信息 素更 新 规 则． 面将 对 这 ２ 下
第 ２期
黄 明 ， ： 进 型 遗 传 蚁 群 混 合 算 法 求 解 旅 行 商 问题 等 改
下（＋ ）＝ （） ｔ 凡 Ｐ’ ｔ ＋∑ △
其中， Ｐ和 △ｒ 的计算 与 （ ） １ 中相 同．
１ ２ 遗传 算法 混合 原理 和模 型描 述 ．
（） ２
传 算法 初 始基 因库 设 置 一个 基 因数 量 下 限 ， 当蚁
更新．
算 法 结 合 ， 此 可 以 和 蚁 群 算 法 结 合 弥 补 蚁 群 因 算 法 的 不足 ， 传 算 法 和 蚁 群 算 法 具 有 互 补 性 ， 遗 它 们 有 可 能 有 机 地 融 合 在 一 起 ， 克 服 各 自缺 以 点 ， 挥 各 自优 点 ｕ 发 引．
息素 量 ；ｋ （ ）为 ｔ ｐ ｔ 时刻 ｋ由 ｉ 动 到 ＿的转 移概 移 『 率 ；ｌ ｗ ｄ ａｌ ｅ ＝ ［ ， ， ， ｏ １２ … ］一ｔｂ 示 ｋ 一步 ａｕ 表 下 允许 选 择 的 城 市 ， 忌 表 ｔｂ ｋ ： １２ … ， 禁 ａ ｕ（ ， ， ｍ）
寻找食 物源 时 ， 在其走 过 的路上 释放一 种特 能
ｒ（ ＋ ｔ Ｐ・ ｔ ＋ ｔ Ｔ ｆ ）＝ ｒ（） △ ：
示信 息挥 发 系数 ， ｒ △ 的计 算 ， 其表 达式 为 ：
（） １
其 中 ， （ ＜Ｐ ＜１ 表 示信 息残 留系数 ， Ｐ表 ｐＯ ） １一
１ 算法 改进
１ １ 遗 传蚁 群算 法求解 旅 行商 问题模 型和 原理 ． 蚁 群算 法 的求解 过 程 主 要 由 ２个 规 则控 制 ，
目前 国 内 外 启 发 式 算 法 研 究 的 热 点 和 前 沿 课
（ ） 态转 移规 则 １状
题 ， 已被 成 功地 应 用 于 求 解 Ｔ Ｐ问题 ． 蚁 在 它 Ｓ 蚂
｛ ’ｒ 攀 ｗ Ｊｓ ｏ ∈ ｔ ｈ ａ ｅ ｌ ｏ ｗ ｉ ｅ ｄ
其中， 和 ｉ ｉ （， Ｊ＝１２ …，）为两个不 同城 市； ，， 凡 ｋ 为蚂 蚁个 体 的编号 ； （）为 时刻 ｔ 径 上 的信 ｔ 路
改 进 型 遗 传 蚁 群 混 合 算 法 求 解 旅 行 商 问题
黄 明， 王聪 ， 旭 梁
（ 大连 交通大学 软件 学院 ， 辽宁 大连 １６ ２ ） １０ ８ 摘 要： 针对原有遗传蚁群混合算法的遗传算法特性不 突 出， 容易过 早收敛 的缺 陷， 出一种带有 基 因 提
数量控制 的遗传蚁群混合算 法 ， 有效地提高 了遗传算法部 分 的基 础基 因数量 ， 提高 了全局最 优解能 力．
解 中， 取最 优解 作 为全局 最优 解 ．
达不到基因库基因数量下限时 ， 不进行遗传计算 ， 只将这 些 蚁群计 算 结 果放 入 基 因库 ； 当蚁 群 算 法 结 果 与基 因库 中 已有基 因 中不 同基 因数量 达 到或
第３ ２卷 第 ２期 ２１ ０ １年 ４月
大 连
交
通
大
学 学
报
Ｖｏ ＿ ２ Ｎｏ ２ ｌ３ ．
Ｊ ＲＮＡＬ ＯＦ Ｄ Ｉ ＪＡＯＴ Ｇ ＵＮＩ ＲＳ Ｔ ＯＵ ＡＬ ＡＮ Ｉ ＯＮ ＶＥ Ｉ Ｙ
ＡＤ ． ０ １ ｒ２ １
文章编号 ：６ ３ ９ ９ ｆ０ １ ０ — ０ ６ ０ １７ ． ５０ ２ １ ）２ ０ ８ ．４
个 规则 进行说 明．
按式 （ ） 所有 完 成 一 次周 游 的蚂蚁 经 过 路 １对 径 的信 息素进 行更 新 ．
收 稿 日期 ：０ ０１ － ２ １ －０１ ４
作者简介 ： 明（９ １ ， ， 黄 １６ 一） 男 教授 ， 博士 ， 主要从事计算管理信息 系统 的研究
Ｅ － ａ ｌ ｄｈｍ ＠ ２ ｍ ｉ：ｌ ６３． ｅ． ｎｔ
通过动态分析基 因适应度 ， 生成动态变异概率 ， 提高 了最优解 的生成概 率． 精英交叉原理 的使用 ， 能保护 优秀基 因不受交叉变异 的影 响堕化． 关键词 ： 蚁群算 法 ； 遗传算法 ；Ｓ ； Ｔ Ｐ 动态变异概率 ； 英交叉 精
文献标识码 ： Ａ
０ 引 言
蚁群算法 是最近几 年 由意大利学 者 Ｄｒｏ ｏｉ ｇ 等人首先提 出的一 种新 的启发 式优 化算法 ， 是
滞， 以及 全 局搜 索 能 力 较 低 的缺 陷 ． 为 一 种 全 作
局 优 化算 法 ， 传 算 法 的 选 择 算 子 和 变 异 算 子 遗
具 有 局 部搜 索 的 能 力 ， 扩 展 性 好 ， 易 和 其 他 且 容
记录 ｋ 走过的城市； 分别表示信息素和启发 和 式 因子 的相对 重要 程度 ； 为路 径 ｉ能 见度 ． 叼 ｊ （ ） 息素 更新 规则 ２信 按 式 （ ） 最 短 路 径 的 边 上 的 信 息 素 进 行 １对