管道铺设问题的改进蚁群算法

（） ３ 当完成了一次循环后， 根据整个路径长度来释放相应浓度的信息素， 并更新走过的路径 匕 的信息素浓度。 现用 （） ‘表示在 ‘ 时刻 ， （， 上 的信息浓度。经过 ｎ 时刻 ， 边 ） 个 当蚂蚁完成了一次循环之后 ， 相应边上 的信息素浓度必须进行更新处理 ， 模仿人类记忆的特点 ， 对旧的信息进行削弱 ， 同时 ， 必须将最新 的蚂蚁访 问 路径的信息加入到 丁 ， 这样得到 ： （ ＋ ） １ Ｐ 丁 （） △ 丁 ｔ 凡 ＝（ 一 ）。 ｔ ＋ 丁。 （） ４
中图分 类 号 ．２ １ ＂ ３ ０ 文 献标识 码 ： Ａ
工程 中经 常涉及 到管道 铺设 问题 ， 铺设一 些半 径 大小 不 等 的 圆形 管道 ， 求 所有 管 道 与底 边 相 切 ， 如 要 管 道之 间可 以相 切 ， 尽可 能使铺 好后 的总宽 度最 窄 。此 类 问题 通 常 也 称 为 圆排 列 问题 … 。此类 问题 要 求从 ｎ
２ 基本蚁群算法
给定 一个 有 ｎ个 城市 的 Ｔ Ｐ问题 ， Ｓ 人工 蚂蚁 的数量 为 ｍ。每个 人工蚂 蚁 的行为 符合 下列 规律 ： （ ） 据 路径上 的激素浓 度 ， １根 以相应 的概率来 选取 下一 步路 径 ； （） ２ 不再 选取 自己本次循 环 已经走 过 的路径 为下一 步 路径 。用 一个 数据 结构 （ａｕｉ ） ｔ ｌｔ来控 制 这一 点 ； ｂ ｓ
二
旅行商 问题 （ Ｓ ） 指有 ｎ个城市 ， ＴＰ是 城市 Ｊ之 间的距 离为 ｄ ， 一个 旅行 商从 城 市 １出发 到其他 每个 城市 去一次且 仅去 一次 ， 最后 回到城市 １旅行 商 问题要求 从 ２～ｎ 城市 的所有排 列 中找 出总路线 最短的排列 。 ， 个 假设把 １ １ 圆分别放 置在 １ ，个城 市 中 ， ～， 个 ～１ 城市 ｉ 间的距离 ｄ￣ ＝１２ … ， ＝１２ … ，） 义为 √之 ｏｉ ，， ， （ ｌ ，， ， 定 １
维普资讯
第 ２期
姜长元 ， ： 等 Ｐ完全问题 ， 目前求解旅行商 问题 的主要方 法有动态规划 方法 分枝 限界 ¨， 法 ， ¨ 模拟退火算法 － 遗传算法 一 启发式搜索法 神经 网络算法 蚁群算法 一 ， 引， 引， 引， 等。各种算法各 有千秋 。欧洲学者 Ｍ Ｄ ｒ ｏ ． ｏ ｇ 等人从生物进化论中得到启发 ， ｉ 通过模拟 自然界中蚂蚁集体寻找食物源的行为 （ 群集智 能 ） 出了蚁 群算 法 （ｎ ｏｏｙａ ｏｔｍ）该 算法 最 早 成功 地应 用 于 求解 Ｔ Ｐ问题 ， 又 用 于解 决 提 ａｔ ｌ ｌ ｒｈ ， ｃ ｎ ｇｉ Ｓ 后 其他组合优化问题 ， 并取得了较好的效果 。
管道铺设 问题 的改进蚁群 算法
姜长 元
（ 湖州师范学 院 理学 院 浙 江 湖州 ３ ３０ ） １０ ０
摘
要 ： 先把 管道铺 设 问题转 化 为旅 行 商 问题 ， 首 然后 利 用蚁群 算 法 来求解 此 问题 。算 法的分析 和
仿 真 实验表 明 ， 利用 了城 市 间距 离信 息 的改进蚁 群 算法是 一种 简单有 效的 算法 。 关键 词 ： 管道 铺设 问题 ； 旅行 商 问题 ； 蚁群 算 法
只去一次 ， 最后回到城市 ０ 旅行商问题要求从 １ ｎ ， ～ 个城市的所有排列中找出使总路线最短的排列 。所 以
解 圆排列 问题 就 变为 解旅行 商 问题 。
收 稿 日期 ：０ ６ １－２ ２ ０ —２２
基金项 目： 浙江省教育厅科研基金资助项 目（０ ６ ３ ５ ２０ ０ １ ） 作者简介 ： 长元 （９ ５）男 ， 姜 １７ 一 ， 安徽省桐城市人 ， 湖州师范学 院理学院讲师 ， 硕士 ， 主要从事智能优化系统研究 。
ｄ ＝ ／ｆ ２， ， ｒｆ 。
再增 加 一个 城市 ０ 它与 城市 的距离 ｃ， ｒ（＝１２ … ，） 义为 ， ｆ ＝ ，『 ， ， ｎ 定 ０ ＿ ｄ 。 ＝
（） ２
（） ３
在 如上定 义 之下 ， 圆排 列 问题 与旅行 商 问题等 价 。一个 旅行 商 从 城市 ０出发 到其 他 每个 城 市 去 一次 且
维普资讯
第 ｌ ７卷
第 ２期
长
春
大
学
学
报
Ｖ０． ７ Ｎｏ ２ １ １ ． Ａ ｒ ０７ ｐ ．２ ０
２０ ０ ７年 ４月
Ｊ ＯＵＲＮ Ｆ ＣＨＡ ＡＬ Ｏ ＮＧＣＨＵＮ ＵＮ ＥＲＳ ｒ Ⅳ ｒＹ
文章编号 ：０ ９—３０ （０ ７ ０ ０ １ ０ １０ ９ ７ ２ ０ ）２— ０ ０— ３
Ｄ ＝ｒ ＋ ｉ
，
＋２
＋ … ＋２
＋ｒ 。
图 １ 管 道铺 设 问 题
圆排 列 问题 要求 所有排 列 中使 总长度 达 到最小 。所 有 的排 列 共 有 ｎ ！个 ， 去掉 对 称 的排 列 ， １２ … ， 如 ，，
１
， １， ，， １…，，对称， ｌ ，与 ｌｌ ， ２ １ 一 ｌ ，一 共有÷， 种排列。 ｌ ！
个圆的所有排列 中找出有最小长度的那个排列。文献［ ］ １ 用回溯法解决此 问题 ， 其最坏情况接近于枚举法 ， 时间复杂性为 ０ （ １ ！ 。这类问题属于 Ｎ 一完全 问题 ， 前还没有有效的算法解决问题 。 （ ｎ＋ ） ） Ｐ 目 ’
１ 与 Ｔ Ｐ等价 问题 Ｓ
已知 圆 ｃ 的半径 ｒ ｉ １２ … ，）假 如排 列方 式 为 ｉ， ， ， 。 （ 图 １ 则总 长度 为 ＝ ，， ／ ， （ Ｚ 。ｉ … ｉ 见 ）
其中０ Ｐ １ ＜ ＜ 表示信息素的 挥发程度， 五△； △ ＝ 丁。 丁
（） ５
其中△ ： ｋ 丁 是第 个蚂蚁在时间ｔ ｔ 凡 到 ＋ 之间， ） 在边（ 上增加的信息素改变量。 它的 值由以下公式确定：