模拟退火算法求解tsp问题 朱健炽

模拟退火算法解决 TSP 问题班级：信息 10-4 姓名：朱健炽 学号：10124010440指导老师：王世华 成绩： 问题：通过模拟退火算法解决 TSP 问题一 、 问 题 描 述旅 行 商 问 题 ， 即 TSP 问 题 （ Travelling Salesman Problem） 是 数学 领 域 中 著 名 问 题 之 一 。 假 设 有 一 个 旅 行 商 人 要 拜 访 n 个 城 市 ， 他 必 须选 择 所 要 走 的 路 径 ， 路 经 的 限 制 是 每 个 城 市 只 能 拜 访 一 次 ， 而 且 最 后 要 回到 原 来 出 发 的 城 市 。 路 径 的 选 择 目 标 是 要 求 得 的 路 径 路 程 为 所 有 路 径 之 中的 最 小 值 。 图 1 TSP 问 题 的 示 意 图 二 、 遍 历 算 法一 个 最 容 易 想 到 的 方 法 是 利 用 排 列 组 合 的 方 法 把 所 有 的 路 径 都 计 算 出来 ， 并 逐 一 比 较 ， 选 出 最 小 的 路 径 。 虽 然 该 方 法 在 理 论 上 是 可 行 的 ， 但 路径 的 个 数 与 城 市 的 个 数 成 指 数 增 长 ， 当 城 市 个 数 较 大 时 ， 该 方 法 的 求 解 时间 是 难 以 忍 受 的 ， 甚 至 是 不 可 能 完 成 的 。 以 每 秒 1 亿 次 的 计 算 速 度 来 估算 ， 如 果 TSP 问 题 包 含 20 个 城 市 时 ， 求 解 时 间 长 达 350 年 ； 如 果 要 处理 30 个 城 市 ， 则 求 解 时 间 更 长 达 1+10e16 年 。 如 此 长 的 时 间 ， 在 实 际中 完 成 是 难 以 想 象 的 。 三 、 模 拟 退 火 算 法模 拟 退 火 算 法 是 解 决 TSP 问 题 的 有 效 方 法 之 一 ， 其 最 初 的 思 想 由Metropolis 在 1953 年 提 出 ， Kirkpatrick 在 1983 年 成 功 地 将 其 应 用 在组 合 最 优 化 问 题 中 。模 拟 退 火 算 法 来 源 于 固 体 退 火 原 理 ， 将 固 体 加 温 至 充 分 高 ， 再 让 其 徐徐 冷 却 ， 加 温 时 ， 固 体 内 部 粒 子 随 温 升 变 为 无 序 状 ， 内 能 增 大 ， 而 徐 徐 冷却 时 粒 子 渐 趋 有 序 ， 在 每 个 温 度 都 达 到 平 衡 态 ， 最 后 在 常 温 时 达 到 基 态 ，内 能 减 为 最 小 。 用 固 体 退 火 模 拟 组 合 优 化 问 题 ， 将 内 能 E 模 拟 为 目 标 函数 值 f， 温 度 T 演 化 成 控 制 参 数 t， 即 得 到 解 组 合 优 化 问 题 的 模 拟 退 火 算法 ： 由 初 始 解 i 和 控 制 参 数 初 值 t 开 始 ， 对 当 前 解 重 复 “产 生 新 解 计 算 目 标 函 数 差 接 受 或 舍 弃 ”的 迭 代 ， 并 逐 步 衰 减 t 值 ， 算 法 终 止 时的 当 前 解 即 为 所 得 近 似 最 优 解 ， 这 是 基 于 蒙 特 卡 罗 迭 代 求 解 法 的 一 种 启 发式 随 机 搜 索 过 程 。 求 解 TSP 的 模 拟 退 火 算 法 模 型 可 描 述 如 下 :解 空 间 ： 解 空 间 S 是 遍 访 每 个 城 市 恰 好 一 次 的 所 有 路 经 ， 解 可 以 表 示为 w1,w2 , wn， w1, , wn 是 1,2,n 的 一 个 排 列 ， 表 明w1 城 市 出 发 ， 依 次 经 过 w2, , wn 城 市 ， 再 返 回 w1 城 市 。 初 始 解 可选 为 (1, n) ; 目 标 函 数 ： 目 标 函 数 为 访 问 所 有 城 市 的 路 径 总 长 度 ; 我 们 要 求 的 最 优 路 径 为 目 标 函 数 为 最 小 值 时 对 应 的 路 径 。 新 路 径 的 产 生 ： 随 机 产 生 1 和 n 之 间 的 两 相 异 数 k 和 m， 不 妨 假 设k random )ResultRouter = SelRouter;/如 果 新 路 径 长 于 当 前 路 径 ， 但 exp(- f/t) random(0,1)， 则 仍 然 替 换 当 前 路 径if( JudgeOverInnerLoop(0) )break; /判 断 内 循 环 是 否 结 束 ， 结 束 则跳 出 当 前 温 度 的 内 循 环elseNowInnerIterNumber+; /判 断内 循 环 是 否 结 束 ， 不 结 束 则 继 续 内 循 环if( JudgeOverExternalLoop(0) )break; /判 断 外 循 环 是 否 结 束 ， 结 束 则 结 束 模 拟退 火 计 算elseNowTemperature = CountDownTemperature( NowTemperature, 0 );NowExternalIterNumber+;NowInnerIterNumber = 0;/判 断 外 循 环 是 否 结 束 ， 不 结 束 则 计 算 出 下 降 后的 温 度 ， 并 继 续 循 环 五 、 算 例 测 试 程 序 对 48 个 城 市 的 TSP 问 题 进 行 计 算 ， 求 解 得 到 的 最 优 路 径 图 如 下 。图 3 模 拟 退 火 算 法 获 得 的 最 优 路 径 图 48 个 城 市 的 计 算 结 果