问题［ 、 ２ 大规 模集 成 电路设 计 、 讯 网络 中的路 由 ］ 通 问题 、 载 平衡 、 负 车辆 调 度 问题 等 ， 明该 算 法具 表
个 还 没有 走 过 的 路 口时 ， 随 机 地 挑选 一条 路 就
径前 行 ， 同时释 放 出与 路径 长度 有关 的信息 素． 蚂 蚁走 的路 径 越 长 ， 释 放 的信息 量 越小． 则 当后来 的 蚂蚁 再 次碰 到这 条 路 口的时 候 ， 择信 息 量 较 大 选
文 章编 号 ：１７ ・９ Ｘ（０ ０ ０ —０ １０ ６ ２６ １ ２ １ 】４０ ６—３
浅谈 用蚁群 算法求解 ＴＳ Ｐ
李 云
（ 迁 高等师范学校 计算机系 ， 苏 宿迁 ２３０） 宿 江 ２８ ０
摘 要 ： 群 算 法 是 优 化 领 域 中 新 出现 的 一 种 启 发 式 仿 生 类 智 能 进 化 算 法 ． 述 了 该 算 法 的 基 本 原 理 、 法 模 蚁 阐 算 型 和 在 旅 行 商 问题 中 的 具 体 实 现 过 程 ． 究 表 明该 算 法 具 有 并 行 性 ， 棒 性 等 优 良性 质 ． 研 鲁 关 键 词 ： 群算 法 ； 行 商 问 题 蚁 旅
中 图分 类 号 ： ３ ３０ ＴＰ ９ ． １ 文献标识 码 ： Ａ
０ 引 言
自仿 生 学创 立 以来 ， 学 家 们 就 根 据 生 物 进 科 化 的机理 先 后提 出 了多种 适合 于现 实世 界 中复杂
问题 优 化 的模 拟 进 化 算 法 ， 群 算 法 （ ｔ ｏｏ － 蚁 Ａｎ Ｃ ｌｎ
旅 行 商 问 题 （ ａ ｅｉｇ Ｓ ｌｓ ｎ Ｐ ｏ ｌｍ） Ｔｒｖ ｌ ａｅ ｍａ ｒｂｅ ｎ
是 一个 著名 的 ＮＰ ｈ ｒ － ａｄ问题 ． 即给 定 ，个 城 市 的 ｚ 集 合 （ ， ， ， 及 城 市之 间 的环 游 花 费 （ ≤ １ ２ … ） １
ｉ ≤ ， ≤ ≤ ， ≠ ） 找 到一 条 经过 每个 城市 １ ｉ ，
一
应环 境 的变化 ， 蚁 群 的运 动路 径 上 突然 出现 障 当
碍物 时 ， 蚁 也 能 很 快 地 重 新 找 到 最 优 路 径 ． 蚂 可
见， 在整个 寻 优 过程 中 ， 虽然 单 只蚂 蚁的选 择能力 有限， 但是 通 过信 息 素 的作 用 使 整 个 蚁 群 行 为具
有非 常高 的 自组 织性 ， 蚁之 间交 换 路径 信息 ， 蚂 最
今 尚未 找到 有效 的求 解 方 法 ， 理 论上 枚 举 法 可 在
以解 决 这一 问题 ， 是 当 较 大时 ， 但 解题 的时 间消
耗会 使枚 举法 显 得 没 有 任 何 实 际 价 值． 因此 寻 求
一
种 求解 时 间短 ， 满足 实 际问题 精 度要求 的解 ， 能 ‘
第２ ４卷 第 ４期 ２１ ０ ０年 ７月
甘 肃 联 合 大 学 学报 （ 自然科 学 版 ）
Ｊ ｕ ｎ ｌｆ ｎ ｕ ａ ｈ Ｕｎｖ ｒｉｙ Ｎａ ｕ ａＳ ｉｎ ｅ ） ｏ ｒ ａｏＧａ ｓ Ｌｉｎ ｅ ｉｅｓｔ （ ｔ ｒ ｌｅｅ ｃ ｓ

Ｖｏ ． ４ ． １ ２ ＮＯ ４
Ｊ １ ２ １ ｕ． ０ ０
Ｔ Ｐ问题 ， Ｓ 其可 能 的路径 数 目为 （ ］ 一 １ ！２ 至 ）／ ，
收 稿 日期 ：０ ００ ・８ ２ １—２２ ．’
成为 解决 该 问题 的 主要 途径 ．
ｙ ｇ ｒ ｈ 简 称 ＡＣ 是 由 意 大 利 学 者 Ｄｏｉｏ Ａｌｏｉ ｍ， ｔ Ａ） ｒ ｇ
等人 于 ２ ０世 纪 ９ ０年代 初 首先 提 出来 的一 种 基于 种群 的启 发式 仿生 类并 行 智能 进 化算 法 的新 型 的
模拟进 化 算法 ［ ． 主要 特点 就 是 ： １其 ］ 通过 正反 馈 分 布式 并行 计算 机 制 来 寻 找 最 优 路 径． 它充 分 利 用
１ ２ 基本 蚁 群算 法解 决 旅行 商 问题 的数 学模 型 ．
旅 行 商 问 题 （ ａ ｅｉｇ Ｓ ｌｓ ｎ Ｐ ｏ ｌｍ， Ｔｒｖ ｌ ａｅｍａ ｒ ｂｅ ｎ Ｔ Ｐ 是 一个 典 型 的组合 优化 问题 ［ ． 然陈 述起 Ｓ） ３虽 ］ 来很 简单 ， 求解 却很 困难 ， 于具有 个城 市 的 但 对
路径 的概率 相对 较 大 ， 样 便 形 成 了 一个 正 反 馈 这
机制 ． 优路 径 上 的信息 量越 来越 大 ， 最 而其 他路 径 上 的信息 量却 会 随 着 时 间 的流 逝 而 逐 渐 消 减 ， 最 终整 个蚁 群会 找 到最 优 路 径 ． 时 蚁群 还 能 够适 同
有 良好 的 解决复 杂 问题 的能 力 ．
次且 回 到起点 的 最 小 花 费 的环 游． 将 每个 顶 若
点 看成是 图上 的节点 ， 费 Ｃ 为 连 接点 Ｖ 边 花 ，
上 的权 ， ＴＳ 则 Ｐ问题 就是 在一 个具 有 个 节点 的 完 全 图上 找 一条 花 费最小 的 哈密 顿 回路 ．
终通 过蚁 群 的集 体 自催化 行 为找 出最 优路 径．
１ 基 本 蚁 群 算 法
Ｉ 基 本 蚁群 算法 的 原理 ． Ｉ 根 据仿 生 学 家 的 长期 研 究 发 现 ： 蚂蚁 虽然 没 有 视 觉 ， 运动 时会 通 过 在 路 径 上 释 放 出 一 种特 但 殊 的分 泌物 —— 信 息 素来 寻 找 路 径 ． 当它 们 碰 到
一
了 自然界 蚁群 能 通 过 个 体 间 简单 的 信 息 传递 ， 从 而能 相互 协作 ， 索 从 蚁 穴 至 食 物 间 最 短 路 径 的 搜 集体 寻优 特征 ， 以及 该 过 程 与 旅 行 商 问题 求 解 之 间 的相似 性 ， 到 了具 有 ＮＰ难 度 的旅 行 商 问题 得 的最优 解 答． 同时 ， 该算 法还 被 成功 应用 在 图着 色