综述
旅 行 商 问 题 （ ＴＳ Ｐ ） 算 法 的 比 较
苗卉
杨韬
澳大利亚昆士兰大学信息技术与电气工程学院 西南交通大学 电气工程学院 成都 ６１００３１
摘要： 旅行商问题是一种典型的求解多局部最优的最优化问题： 有ｎ个城市， 一个旅行者从其中的一个城市出发， 经过所有的城市一次并返回出发的城市， 求最短的路线。本文 运用Ｍａｔｌａｂ７．０实现三种能解决ＴＳＰ问题的算法（ 贪心算法， 模拟退火算法和遗传算法） ， 并在ＴＳＰ测试文件 ｂｅｒｌｉｎ５２．ｔｓｐ和ｋｒｏｂ１００．ｔｓｐ上运行三种算法。从而比较和归纳每个算法的优 缺点。
在ＴＳＰ测试文件ｂｅｒｌｉｎ５２．ｔｓｐ和ｋｒｏｂ１００．ｔｓｐ上运行三种算法。从而 内能， Ｅ为其改变量， ｋ为Ｂｏｌｔｚｍａｎ常数。
比较和归纳每个算法的优缺点。
用固体退火模拟组合优化问题， 将内能Ｅ模拟为目标函数
１． 旅行商问题简介
值ｆ， 温度Ｔ演 化 成 控 制 参 数ｔ， 即 得 到 解 组 合 优 化 问 题 的 模 拟 退
化问题中又有着广泛的应用，故长期以来一直吸引着国内外许
２） 对ｋ＝１至ｋ＝Ｌ做第（３）至第６步；
多研究人员进行研究，他 们 尝 试 着 用 各 种 算 法 来 求 解ＴＳＰ问 题，
３） 产生新解ｓ′（ 一般利用２－ ｏｐｔ算法来产生新的路径） ；
归纳起来有：近似解法、局部搜索法、神经网络、遗传算 法、克隆
平均路径长度为７９１７．９， 与最优值的平均差： ３７５．９， 与最优解的 平均方差：４７５．６。在遗传序列算法中， 平 均 路 径 长 度 为８５１５．６， 与最优值的平均差： ９７３．６， 与最优解的平均方差： １０４３．０。从以 上数据可以看出， 模拟退火算法的效率最高， 在有限的迭带次 数下求得的结果离最优解最近 （ 与最优解的平均方差为 ４７５．６） 。
技 术 ０与 市 场 ８１
２００７ ／ ２
综述
生更适应环境的新一代“ 染色体”群。这样， 一代一代地进化， 最 后就会收敛到最适应环境的一个“ 染色体”上， 它就是问题的最 优 解 。 下 列 是 实 现 遗 传 算 法 解 决 ＴＳＰ问 题 的 步 骤 ：
１） 产 生 一 群 染 色 体（ 不 同 的 游 历 路 径） 然 后 计 算 评 估 每 个 染色体的健壮度（ 总路径长度） 。
５． 总结 本文运用Ｍａｔｌａｂ７．０实现三种能解决ＴＳＰ问题的算法 （ 贪心 算 法 ， 模 拟 退 火 算 法 和 遗 传 算 法） ， 并 在ＴＳＰ测 试 文 件ｂｅｒｌｉｎ５２． ｔｓｐ和 ｋｒｏｂ１００．ｔｓｐ上 运 行 三 种 算 法 。从 而 比 较 和 归 纳 每 个 算 法 的 优缺点。实验结果表明， 每个算法都有各自的优缺点。另外， 在 模 拟 退 火 算 法 和 遗 传 序 列 算 法 中 ， 初 始 温 度 、衰 减 因 子 和 马 尔 可夫链长度等参数的控制， 还需要做进一步研究。今后应在更 先进的硬件平台 的 基 础 上 尝 试 较 大 的ＴＳＰ地 图（ 上 千 城 市 规 模 的地图） 来进 一 步 测 试 算 法 的 性 能 。 解 决ＴＳＰ问 题 的 算 法 在 对 钻孔路线方案、连锁店的货物配送、网络布线， 铁路网优化等问 题中有着广泛的 应 用 ， 所 以 改 进 和 研 究 解 决ＴＳＰ问 题 算 法 对 实 际的工业生产是有重要意义的。 参考文献： ［１］ 王 忠 业，房 丽 娜． 基 于 遗 传 算 法 的 项 目 投 资 决 策 分 析［Ｊ］． 科 技 进步与对策， ２００６， （ ５） ： １１０－ １１１． ［２］ 魏 延，谢 开 贵． 模 拟 退 火 算 法［Ｊ］． 蒙 自 师 范 高 等 专 科 学 校 学 报， １９９９， （ ８） ： ７－ １１． ［３］ 芦金婵，王伟东． 模拟退火算法的改进［Ｊ］． 淮北煤师院学报， ２００３， （ １２） ： １６－ １９． ［４］ 万军洲． 基于模拟退火技术的旅行商问题求解算法［Ｊ］． 软件 导刊， ２００６， （ ８） ： ８８－ ８９． ［５］ Ｓｃｏｔｔ Ｍ． Ｔｈｅｄｅ Ａｎ ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ Ｏｃｔｏｂｅｒ ２００４ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｉｎｇ Ｓｃｉｅｎｃｅｓ ｉｎ Ｃｏｌｌｅｇｅｓ， Ｖｏｌｕｍｅ ２０ Ｉｓｓｕｅ １．
是最短的路径。如此然后去Ｃ， 再到Ｄ。所以， 此算法则总是选择 传算法之前， 给出一群“ 染色体”， 也即是假设解。然后， 把这些
最短的路径。
假设 解 置 于 问 题 的“ 环 境 ”中 ， 并 按 适 者 生 存 的 原 则 ， 从 中 选 择
２．２ 模拟退火算法
出较 适 应 环 境 的“ 染 色 体 ”进 行 复 制 ， 再 通 过 交 叉 ， 变 异 过 程 产
的路径。城市越多， 可能的路径也越多。而且路径的增加速度非 体退火 原 理 ， 将 固 体 加 温 至 充 分 高 ， 再 让 其 缓 慢 降 温（即 退 火），
常快且是非线形的。当ｎ很大时， 去尝试每一种可能的路径是不 使之达到能量最低点。反之， 如果急速降温（即淬火）则不能达到
可能的， 所以需要设计一个有效的算法去寻找最短的路径。现 最低点。加温时， 固体内部粒子随温升变为无序状， 内能增大，
今可以解决ＴＳＰ问题的算法 有 很 多 ， 如 ： 模 拟 退 火 算 法 ， 蚁 群 算 而缓慢降温时粒子渐趋有序， 在每个温度上都达到平衡态， 最
法， 遗传算法， 克隆算法等等。本文运用Ｍａｔｌａｂ７．０实现三种能解 后在常温时达到基态， 内能减为最小。根据Ｍｅｔｒｏｐｏｌｉｓ准则， 粒子
决ＴＳＰ问 题 的 算 法（ 贪 心 算 法 ， 模 拟 退 火 算 法 和 遗 传 算 法） ， 并 在 温 度Ｔ时 趋 于 平 衡 的 概 率 为ｅｘｐ（－ Ｅ／（ｋＴ））， 其 中Ｅ为 温 度Ｔ时 的
２） 选留健壮度较好的染色体（ 总路径较短的路径） ， 剩下的 作为父染色体；
３） 父 染 色 体 交 换 ， 倒 转 或 移 位 产 生 下 一 代 染 色 体（ 其 中 有 ５％的染色体变异的概率） ；
４） 在下一代染色体的基础上回到第 １ 步骤； ５） 循环整个程序多次， 记录下每代的最好的染色体； ６） 选择其中最优秀的染色体作为最优解。 ３． ＴＳ Ｐ 算法的比较 ３．１ 实验器材与数据 用 来 测 试 算 法 性 能 的ＴＳＰ文 件ｂｅｒｌｉｎ５２．ｔｓｐ和ｋｂｒｏ１００．ｔｓｐ是 两张具有５２个城市和１００个城市 的ＴＳＰ地 图 ， 它 们 可 以 从ＴＳＰ问 题 的 数 据 库 中 下 载 得 到 。 下 载 ＴＳＰ 测 试 文 件 的 地 址 为 ： ｈｔｔｐ： ／／ｗｗｗ．ｉｗｒ．ｕｎｉ－ ｈｅｉｄｅｌｂｅｒｇ．ｄｅ／ｇｒｏｕｐｓ／ｃｏｍｏｐｔ／ｓｏｆｔｗａｒｅ／ＴＳＰＬＩＢ９５／ｔｓｐ／ 测试的硬 件 平 台 主 要 配 置 为Ｐｅｎｔｉｕｍ Ｍ １．６ Ｇｈｚ处 理 器， ３３３Ｍｈｚ ＤＤＲ ２５６Ｍ 内存， 测试算法的软件选用Ｍａｔｌａｂ７．０。 ３．２ 实验结果 贪心算法： 运行贪心算法 计 算ｂｅｒｌｉｎ５２．ｔｓｐ和ｋｂｒｏ１００．ｔｓｐ各 １０ 次 ， 记 录 路 径 总 长 度 和 程 序 运 行 时 间 ， 在 贪 心 算 法 中 ： Ｂｅｒｌｉｎ５２．ｔｓｐ： 平均路径长度为９１９７．４； 程 序 平 均 执 行 时 间 ： ０．０３２ 秒； 与最优值的平均差： １６５５．４； 与最优解的平均方差：１７８５．７。 Ｋｂｒｏ１００．ｔｓｐ： 平 均 路 径 长 度 为２８３０３； 程 序 平 均 执 行 时 间 ： ０．０３８ 秒； 与最优值的平均差： ６１６２；与最优解的平均方差： ６４３５．４。 模 拟 退 火 算 法 ： Ｂｅｒｌｉｎ５２．ｔｓｐ： 平 均 路 径 长 度 为７９１７．９； 程 序 平均执行时间： ９．３秒； 与最优值的平均差： ３７５．９；与 最 优 解 的 平 均 方 差： ４７５．６。Ｋｂｒｏ１００．ｔｓｐ： 平 均 路 径 长 度 为２３４５４； 程 序 平 均 执 行 时 间 ： １５６．８秒 ； 与 最 优 值 的 平 均 差 ： １３１３；与 最 优 解 的 平 均 方差： １４１３．５。 遗 传 序 列 算 法 ： 运 行 遗 传 序 列 算 法 计 算 ｂｅｒｌｉｎ５２．ｔｓｐ 和 ｋｂｒｏ１００．ｔｓｐ各１０次 ， 记 录 路 径 总 长 度 和 程 序 运 行 时 间 ， 在 遗 传 序 列 算 法 中 ： Ｂｅｒｌｉｎ５２．ｔｓｐ： 平 均 路 径 长 度 为８５１５．６； 程 序 平 均 执 行 时 间 ： ２９．６秒 ； 与 最 优 值 的 平 均 差 ： ９７３．６；与 最 优 解 的 平 均 方 差： １０４３．０。 Ｋｂｒｏ１００．ｔｓｐ： 平 均 路 径 长 度 为２７１８４； 程 序 平 均 执 行 时 间 ： １４８．１秒； 与最优值的平均差： ５０４３；与最优解的平均方差： ５２８３。 ４． 算法的结果分析 首先我们比较三个算法的运行时间 ， 拿Ｂｅｒｌｉｎ５２．ｔｓｐ为 例 ： 在 贪 心 算 法 中 ， 程 序 平 均 执 行 时 间 ： ０．０３２秒 ； 在 模 拟 退 火 算 法 中， 程序平均执行时间： ９．３秒； 在遗传序列算法中， 程序 平 均 执 行时间： ２９．６秒。由上数 据看出， 由于贪心算法不需要迭 代 ， 所 以运行速度最快， 而遗传序列算法是计算最慢的算法。 然 后 我 们 比 较 三 个 算 法 的 准 确 度 ， 还 是 以Ｂｅｒｌｉｎ５２．ｔｓｐ为 例 ： 在 贪 心 算 法 中 ， 平 均 路 径 长 度 为 ９１９７．４， 与 最 优 值 的 平 均 差： １６５５．４， 与最优解的平均方差：１７８５．７。 在 模 拟 退 火 算 法 中 ，
４） 计算增量Ｃｏｓｔ＝Ｃｏｓｔ（ｓ′）－ Ｃｏｓｔ（ｓ）， 其中Ｃｏｓｔ（ｓ）为评价函数；
算 法 、模 拟 退 火 算 法 、混 合 遗 传 算 法 等 。
５） 若 ｔ′＜０ 则 接 受 ｓ′ 作 为 新 的 当 前 解 ， 否 则 以 概 率 ｅｘｐ