基于蚁群算法的TSP问题求解
- 格式：pdf
- 大小：89.24 KB
- 文档页数：1
当前位置：文档之家 › 基于蚁群算法的TSP问题求解
合集下载
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
度 ： 表 示本 次循 环所 有 蚂 蚁在 路径 上 （，） 释放 的信 息 素浓 度 之和 。 △ ｉＪ 所 ３问题 求 解 ３ １设 定 ３ 城市 的坐 标位 置 ． Ｏ个
Ｃ＝ ３２ ｌ５ ５ ４ ： １ ： ： ９ ９ ６ １ ： ４ ０ １ ： ４ ６ １ ： ［ ： ： ：４ ７ ３ １ ０ ８ ７ ： ：０ ２ １ ：７ ３ １ ： ２ ９
在运 动过 程 中， 据各 条路 径上 的信 息素 的浓度 决定转 移方 ｒ， ） 根 Ｎ ｐ （ 表示在 ｔ ，
时刻 刻蚂蚁 ｋ从送 货 点 ｉ 移 到送 货点 Ｊ的概率 ， 转 其计 算公 式为
３ ２ 参数 设置 ： ． 最大 迭代 次数 ：Ｃ ｍ ｘ２ ０ Ｎ ａ＝ ０ ： 蚂蚁 个数 ：＝ ０ ｍ３ ： 信息 素重 要程 度 ：ｌｈ ＝ ： Ａｐ ａ ｌ 启发 式因子 重要 程度 ：ｅａ ５ Ｂ ｔ＝ ； 信 息 素蒸 发系 数 ：ｈ ＝ ． ： Ｒｏ Ｏ １ 信 息 素增加 强度 系数 ：＝ ０ ： Ｑ １０ Ｒ ｂ ｓ 代表 最佳路 线 ：－ ｅ ｔ 代 表最 佳路线 的 长度 。 ｅｔ Ｌ ｂｓ ３ ３ 编制 函数
１ １ １ ； １ ６ ８： １ ７ ｌ ２ ７ ４ ２ ０； ７ ９ ５ ９ １ ４： ０ ７： ０ ２ ９ ９ ２ ６ １ １ １ ： ５ １ １ １ ２ ｌ １ ５ １ ２ １
前 行 。与此 同时释 放 出与路线 长度 有关 的信 息素 。路径越 长 ， 放 的激素浓 释 度 越低 。当后 来的蚂 蚁再 次碰 到这个 路 口的时 候 ， 选择 激素 浓度 较高 路径 概 率 就会相 对较 大 。这样 形成 了一个 正反 馈 。最 优路 径上 的激 素浓度 越 来越 大 而 其它 的路 径上 激素 浓度 却会 随着 时 间的流 逝而 消减 。这样 ， 整个 蚁群 最 终 会 找 出最 优 路 径 。
科 学 论 坛
—■ Ｉ
基于 蚁群算 法的 Ｔ Ｐ问题求解 Ｓ
李洪 建 祝翰林 刘马隆
（． 国矿 业大 学化 工学 院 ： ２ 中 国矿 业大 学信 息与 电气 工程 学 院 江 苏 徐 州 ２ １ １） １中 型 的非确 定性 多项式 （ｏ ｅ ｅｍ ｎ ｓｉ ｏ ｙｏ ｉ ｌ缩写 Ｎ ） ｎ ｎ ｄｔ ｒ ｉ ｉｔ ｃ ｐ ｌｎ ｍ ａ ， Ｐ 问题 。Ｎ Ｐ困难 问题 即是 指不存 在 一 多项 式时 间 内的算法 即可 解 个 决 的复 杂 问题 。而蚁群 算法 是 一种用 于解决 此类 复杂 问题 的新 的 启发 式算 法， 它是通 过 信息 素 的积 累和 更新 收敛 于最 优 路径 上 。本文 通过 蚊群 算 法解 决 了 ３ Ｏ
用参数 １ 一Ｐ表 示信 息素 的挥 发 程度 。经 过 ｗ 个 时刻， 蚁 完成一 次循 环， 蚂 各 路径 上的信 息 素 的浓度 可根 据如 下 公式进 行 调整 ：
ｆ （ ：Ｐ （ △ Ｐｅ ０１ ｆ ＋ ‘ ＋ ｒ （，； ）
ｍ
Ａ Ｔ
△
式中： 表 △ ： 示第ｋ 蚂蚁 只 在本次 环中留 路径（ 循 在 ｆ ， 上的 息素的 信 浓
旅 行商 问题 （ｒ ｖ ｌｎ ａ ｅ ｍ ｎＰ ｏ ｌｍ 简称 Ｔ Ｐ ，Ｓ 是 。。 典 Ｔ ａ ｅ ｉｇ Ｓ ｌｓ ａ ｒｂ ｅ， Ｓ ）Ｔ Ｐ ＿个经 的组 合优化 问题 。它可 以描述 为 ： 个商 品推 销员要 去若 干个 城市 推销 商 品， 一 从一个 城市 出发 ， 需要经 过所有 城市 后 ， 回到 出发地 ， 如何选 择行 进 路线， 应 以使总行 程最 短 。现 实生活 中有 很 多 问题 可 以归 结为 旅 行商 问题 ， 比如 邮路 问题 、装 配 线上 的 螺帽 问题和 产 品 的生产 安 排 问题 等 。Ｔ Ｐ 问题 在 电 路板 Ｓ
个 城 市之 间的 最 短路 径 问题 。 ［ 关键 词 】 Ｓ Ｔ Ｐ问题 蚁群 算法 信 息素 最 短距 离 中图 分类号 ：Ｐ ８ Ｔ １ 文献标 识码 ： Ａ
文章编 号 ：０９ ９ ３ （００ １— ０４ ０ １０ — １Ｘ ２ １）９ ０ ３— １
１引言
的相对 重 要程度 。随着 时 间的推 移， 以前 留在各 条路 径上 的信 息素逐 渐 消失，
，
２１ ３： ４ ２ ２ １ ２ １ ２ ５ ： １ ２ ０：５ ６： ８ ８：２ ］
２ ２ 算 法求解 ．
设 ｍ 是蚁群 中蚂 蚁 的数量， ． ｄ． 表示 送货 点与 送货 点之 间 的距 离， Ｌ 表 ， Ｊ 示送 货 点表 示 ｔ时刻 在城 市 ｉ与城 市 Ｊ连线 上 的信息 素 的浓 度 。初 始时 刻， 各 条路径 上 的信息 素 的浓度 相 同， 设 （Ｊ ｃ， ｏ Ｃ为 常数 。蚂蚁膏 ＝，， １ …， ２
， ｖ ，ｈ ｒｅ ｏ ｔ ， ｈ ｒ ｅ ｔ ｅ ｇｈ ｆ ｎ ｉ ｎ ［ ｂ ｓ ， ｂｅｓｔ Ｌ ａ ｅ Ｓ ｏ ｔ ｓｔ Ｒ ｕ ｅ Ｓ ｏ ｔ ｓ Ｌ ｎ ｔ ］ ｕ ｃｔ ｏ Ｒ ｅ ｔ Ｌ
钻孔进 度 的安排 、基 因测序 和机 器人 控制 等方面 有着 重要 的应用 。因此， Ｓ ＴＰ 问题 具有 重要 的理 论意 义和 实 际意义 。 ２蚁群 算 法 ２ １ 蚁群 算法原 理 蚁群 算法 ａ ｔｃ ｌｎ ｌ ｏ ｉｈ， Ｃ 是一种 全新 的通 过模拟 自然 界蚂 ｎ ｏ ｏｙａ ｇｒ ｔｍ ＡＡ 蚁寻径 的行 为 的进化 算法 。蚂 蚁群 找到 食物 时 ， 它们 总能 找到一 条从 食物 到 巢 穴之 间 的最优路 径 。这是 因为蚂 蚁在 寻找路 径 时会在 路径 上释 放 出一种特 殊 的信 息素 当它们 碰 到一个 还没有 走 过的路 口时 ， 随机 地挑 选～ 条路 径 就
Ｃ＝ ３２ ｌ５ ５ ４ ： １ ： ： ９ ９ ６ １ ： ４ ０ １ ： ４ ６ １ ： ［ ： ： ：４ ７ ３ １ ０ ８ ７ ： ：０ ２ １ ：７ ３ １ ： ２ ９
在运 动过 程 中， 据各 条路 径上 的信 息素 的浓度 决定转 移方 ｒ， ） 根 Ｎ ｐ （ 表示在 ｔ ，
时刻 刻蚂蚁 ｋ从送 货 点 ｉ 移 到送 货点 Ｊ的概率 ， 转 其计 算公 式为
３ ２ 参数 设置 ： ． 最大 迭代 次数 ：Ｃ ｍ ｘ２ ０ Ｎ ａ＝ ０ ： 蚂蚁 个数 ：＝ ０ ｍ３ ： 信息 素重 要程 度 ：ｌｈ ＝ ： Ａｐ ａ ｌ 启发 式因子 重要 程度 ：ｅａ ５ Ｂ ｔ＝ ； 信 息 素蒸 发系 数 ：ｈ ＝ ． ： Ｒｏ Ｏ １ 信 息 素增加 强度 系数 ：＝ ０ ： Ｑ １０ Ｒ ｂ ｓ 代表 最佳路 线 ：－ ｅ ｔ 代 表最 佳路线 的 长度 。 ｅｔ Ｌ ｂｓ ３ ３ 编制 函数
１ １ １ ； １ ６ ８： １ ７ ｌ ２ ７ ４ ２ ０； ７ ９ ５ ９ １ ４： ０ ７： ０ ２ ９ ９ ２ ６ １ １ １ ： ５ １ １ １ ２ ｌ １ ５ １ ２ １
前 行 。与此 同时释 放 出与路线 长度 有关 的信 息素 。路径越 长 ， 放 的激素浓 释 度 越低 。当后 来的蚂 蚁再 次碰 到这个 路 口的时 候 ， 选择 激素 浓度 较高 路径 概 率 就会相 对较 大 。这样 形成 了一个 正反 馈 。最 优路 径上 的激 素浓度 越 来越 大 而 其它 的路 径上 激素 浓度 却会 随着 时 间的流 逝而 消减 。这样 ， 整个 蚁群 最 终 会 找 出最 优 路 径 。
科 学 论 坛
—■ Ｉ
基于 蚁群算 法的 Ｔ Ｐ问题求解 Ｓ
李洪 建 祝翰林 刘马隆
（． 国矿 业大 学化 工学 院 ： ２ 中 国矿 业大 学信 息与 电气 工程 学 院 江 苏 徐 州 ２ １ １） １中 型 的非确 定性 多项式 （ｏ ｅ ｅｍ ｎ ｓｉ ｏ ｙｏ ｉ ｌ缩写 Ｎ ） ｎ ｎ ｄｔ ｒ ｉ ｉｔ ｃ ｐ ｌｎ ｍ ａ ， Ｐ 问题 。Ｎ Ｐ困难 问题 即是 指不存 在 一 多项 式时 间 内的算法 即可 解 个 决 的复 杂 问题 。而蚁群 算法 是 一种用 于解决 此类 复杂 问题 的新 的 启发 式算 法， 它是通 过 信息 素 的积 累和 更新 收敛 于最 优 路径 上 。本文 通过 蚊群 算 法解 决 了 ３ Ｏ
用参数 １ 一Ｐ表 示信 息素 的挥 发 程度 。经 过 ｗ 个 时刻， 蚁 完成一 次循 环， 蚂 各 路径 上的信 息 素 的浓度 可根 据如 下 公式进 行 调整 ：
ｆ （ ：Ｐ （ △ Ｐｅ ０１ ｆ ＋ ‘ ＋ ｒ （，； ）
ｍ
Ａ Ｔ
△
式中： 表 △ ： 示第ｋ 蚂蚁 只 在本次 环中留 路径（ 循 在 ｆ ， 上的 息素的 信 浓
旅 行商 问题 （ｒ ｖ ｌｎ ａ ｅ ｍ ｎＰ ｏ ｌｍ 简称 Ｔ Ｐ ，Ｓ 是 。。 典 Ｔ ａ ｅ ｉｇ Ｓ ｌｓ ａ ｒｂ ｅ， Ｓ ）Ｔ Ｐ ＿个经 的组 合优化 问题 。它可 以描述 为 ： 个商 品推 销员要 去若 干个 城市 推销 商 品， 一 从一个 城市 出发 ， 需要经 过所有 城市 后 ， 回到 出发地 ， 如何选 择行 进 路线， 应 以使总行 程最 短 。现 实生活 中有 很 多 问题 可 以归 结为 旅 行商 问题 ， 比如 邮路 问题 、装 配 线上 的 螺帽 问题和 产 品 的生产 安 排 问题 等 。Ｔ Ｐ 问题 在 电 路板 Ｓ
个 城 市之 间的 最 短路 径 问题 。 ［ 关键 词 】 Ｓ Ｔ Ｐ问题 蚁群 算法 信 息素 最 短距 离 中图 分类号 ：Ｐ ８ Ｔ １ 文献标 识码 ： Ａ
文章编 号 ：０９ ９ ３ （００ １— ０４ ０ １０ — １Ｘ ２ １）９ ０ ３— １
１引言
的相对 重 要程度 。随着 时 间的推 移， 以前 留在各 条路 径上 的信 息素逐 渐 消失，
，
２１ ３： ４ ２ ２ １ ２ １ ２ ５ ： １ ２ ０：５ ６： ８ ８：２ ］
２ ２ 算 法求解 ．
设 ｍ 是蚁群 中蚂 蚁 的数量， ． ｄ． 表示 送货 点与 送货 点之 间 的距 离， Ｌ 表 ， Ｊ 示送 货 点表 示 ｔ时刻 在城 市 ｉ与城 市 Ｊ连线 上 的信息 素 的浓 度 。初 始时 刻， 各 条路径 上 的信息 素 的浓度 相 同， 设 （Ｊ ｃ， ｏ Ｃ为 常数 。蚂蚁膏 ＝，， １ …， ２
， ｖ ，ｈ ｒｅ ｏ ｔ ， ｈ ｒ ｅ ｔ ｅ ｇｈ ｆ ｎ ｉ ｎ ［ ｂ ｓ ， ｂｅｓｔ Ｌ ａ ｅ Ｓ ｏ ｔ ｓｔ Ｒ ｕ ｅ Ｓ ｏ ｔ ｓ Ｌ ｎ ｔ ］ ｕ ｃｔ ｏ Ｒ ｅ ｔ Ｌ
钻孔进 度 的安排 、基 因测序 和机 器人 控制 等方面 有着 重要 的应用 。因此， Ｓ ＴＰ 问题 具有 重要 的理 论意 义和 实 际意义 。 ２蚁群 算 法 ２ １ 蚁群 算法原 理 蚁群 算法 ａ ｔｃ ｌｎ ｌ ｏ ｉｈ， Ｃ 是一种 全新 的通 过模拟 自然 界蚂 ｎ ｏ ｏｙａ ｇｒ ｔｍ ＡＡ 蚁寻径 的行 为 的进化 算法 。蚂 蚁群 找到 食物 时 ， 它们 总能 找到一 条从 食物 到 巢 穴之 间 的最优路 径 。这是 因为蚂 蚁在 寻找路 径 时会在 路径 上释 放 出一种特 殊 的信 息素 当它们 碰 到一个 还没有 走 过的路 口时 ， 随机 地挑 选～ 条路 径 就