《基于蚁群算法的TSP问题研究-毕业论文开题报告》由会员分享，可在线阅读，更多相关《基于蚁群算法的TSP问题研究-毕业论文开题报告（7页珍藏版）》请在金锄头文库上搜索。
1、南京航空航天大学金城学院毕 业 设 计 （ 论 文 ） 开 题 报 告题 目 基 于 蚁 群 算 法 的 TSP 问 题 研 究系 部 XXXX系专 业 XXXX学 生 姓 名 XXXX 学 号 XXXX指 导 教 师 XXXX 职 称 讲 师毕 设 地 点 XXXX年 月 日填 写 要 求1 开 题 报 告 只 需 填 写 “ 文 献 综 述 ”、 “ 研 究 或 解 决 的 问 题 和 拟采 用 的 方 法 ” 两 部 分 内 容 ， 其 他 信 息 由 系 统 自 动 生 成 ， 不 需 要 手工 填 写 。2 为 了 与 网 上 任 务 书 兼 容 及 最 终 打 印 格 式 一 致
2、， 开 题 报 告 采用 固 定 格 式 ， 如 有 不 适 请 调 整 内 容 以 适 应 表 格 大 小 并 保 持 整 体 美观 ， 切 勿 轻 易 改 变 格 式 。3 任 务 书 须 用 A4 纸 ， 小 4 号 字 ， 黑 色 宋 体 ， 行 距 1.5 倍 。4 使 用 此 开 题 报 告 模 板 填 写 完 毕 ， 可 直 接 粘 接 复 制 相 应 的 内容 到 毕 业 设 计 网 络 系 统 。1. 结 合 毕 业 设 计 （ 论 文 ） 课 题 任 务 情 况 ， 根 据 所 查 阅 的 文 献 资 料 ， 撰 写 1500 2000字 左 右 的 文 献 综 述 ：1.
3、1 蚁 群 算 法 的 发 展 和 应 用在 计 算 机 自 动 控 制 领 域 中 , 控 制 和 优 化 始 终 是 两 个 重 要 问 题 。 使 用 计 算 机 进 行控 制 和 优 化 本 质 上 都 表 现 为 对 信 息 的 某 种 处 理 。 随 着 问 题 规 模 的 日 益 庞 大 , 特 性 上的 非 线 性 及 不 确 定 性 等 使 得 难 以 建 立 精 确 的 “ 数 学 模 型 ” 。 人 们 从 生 命 科 学 和 仿 生 学中 受 到 启 发 , 提 出 了 许 多 智 能 优 化 方 法 , 为 解 决 复 杂 优 化 问 题 (NP- hard 问 题
4、) 提供 了 新 途 径 。蚁 群 算 法 (Ant Colony Algorithm, ACA) 是 Dorigo M 等 人 于 1991 年 提 出 的 。经 观 察 发 现 , 蚂 蚁 个 体 之 间 是 通 过 一 种 称 之 为 信 息 素 的 物 质 进 行 信 息 传 递 的 。 在 运动 过 程 中 , 蚂 蚁 能 够 在 它 所 经 过 的 路 径 上 留 下 该 种 信 息 素 , 而 且 能 够 感 知 信 息 素 的浓 度 , 并 以 此 指 导 自 己 的 运 动 方 向 。 蚁 群 的 集 体 行 为 表 现 出 一 种 信 息 正 反 馈 现 象 :某 一 路
5、径 上 走 过 的 蚂 蚁 越 多 , 则 后 来 者 选 择 该 路 径 的 概 率 就 越 大 。 蚂 蚁 个 体 之 间 就是 通 过 这 种 信 息 的 交 流 达 到 搜 索 食 物 的 目 的 。 它 充 分 利 用 了 生 物 蚁 群 通 过 个 体 间 简单 的 信 息 传 递 ， 搜 索 从 蚁 巢 至 食 物 间 最 短 路 径 的 集 体 寻 优 特 征 ， 以 及 该 过 程 与 旅 行商 问 题 求 解 之 间 的 相 似 性 。 同 时 ， 该 算 法 还 被 用 于 求 解 二 次 指 派 问 题 以 及 多 维 背 包问 题 等 ， 显 示 了 其 适 用 于
6、组 合 优 化 问 题 求 解 的 优 越 特 征 。蚁 群 算 法 应 用 于 静 态 组 合 优 化 问 题 , 其 典 型 代 表 有 旅 行 商 问 题 ( TSP) 、 二 次 分配 问 题 (QAP) 、 车 间 调 度 问 题 、 车 辆 路 径 问 题 等 。 在 动 态 优 化 问 题 中 的 应 用 主 要 集中 在 通 讯 网 络 方 面 。 这 主 要 是 由 于 网 络 优 化 问 题 的 特 殊 性 , 如 分 布 计 算 , 随 机 动 态性 , 以 及 异 步 的 网 络 状 态 更 新 等 。 例 如 将 蚁 群 算 法 应 用 于 QOS 组 播 路 由 问
7、 题 上 , 就得 到 了 优 于 模 拟 退 火 (SA)和 遗 传 算 法 (GA)的 效 果 。 蚁 群 优 化 算 法 最 初 用 于 解 决 TSP问 题 ， 经 过 多 年 的 发 展 ， 已 经 陆 续 渗 透 到 其 他 领 域 中 ， 如 图 着 色 问 题 、 大 规 模 集 成电 路 设 计 、 通 讯 网 络 中 的 路 由 问 题 以 及 负 载 平 衡 问 题 、 车 辆 调 度 问 题 等 。 蚁 群 算 法在 若 干 领 域 获 得 成 功 的 应 用 ， 其 中 最 成 功 的 是 在 组 合 优 化 问 题 中 的 应 用 。1.2 蚁 群 算 法 求 解
8、TSP 问 题（ 1） TSP问 题 的 描 述TSP问 题 的 简 单 形 象 描 述 是 :给 定 n个 城 市 ,有 一 个 旅 行 商 从 某 一 城 市 出 发 ,访 问各 城 市 一 次 且 仅 有 一 次 后 再 回 到 原 出 发 城 市 ,要 求 找 出 一 条 最 短 的 巡 回 路 径 。（ 2） TSP问 题 的 理 论 意 义该 问 题 是 作 为 所 有 组 合 优 化 问 题 的 范 例 而 存 在 的 。 它 已 经 成 为 并 将 继 续 成 为 测试 新 算 法 的 标 准 问 题 。 这 是 因 为 ， TSP问 题 展 示 了 组 合 优 化 的 所 有
9、 方 面 。 它 从 概 念 上来 讲 非 常 简 单 ， 但 是 其 求 解 的 难 度 是 很 大 的 。 如 果 针 对 TSP 问 题 提 出 的 某 种 算 法 能够 取 得 比 较 好 的 实 算 效 果 ， 那 么 对 其 进 行 修 改 ， 就 可 以 应 用 于 其 他 类 型 的 组 合 优 化问 题 并 取 得 良 好 的 效 果 。（ 3） 蚁 群 算 法 求 解 TSP的 算 法 流 程步 骤 1: nc=0(nc 为 迭 代 步 数 或 搜 索 次 数 ); 每 条 边 上 的 Tj(0)=c(常 数 ), 并 且 Tj=0; 放 置 m 个 蚂 蚁 到 n 个 城
10、 市 上 。步 骤 2: 将 各 蚂 蚁 的 初 始 出 发 点 置 于 当 前 解 集 TABUk(s)中 ; 对 每 个 蚂 蚁 k(k=1,m), 按 概 率 Pij(t)移 至 下 一 城 市 j; 将 城 市 j 置 于 TABUk(s)中 。步 骤 3: 经 过 n 个 时 刻 , 蚂 蚁 k 可 走 完 所 有 的 城 市 , 完 成 一 次 循 环 。 计 算 每 个蚂 蚁 走 过 的 总 路 径 长 度 Lk, 更 新 找 到 的 最 短 路 径 。步 骤 4: 更 新 每 条 边 上 的 信 息 量 Tij(t+n)步 骤 5: 对 每 一 条 边 置 Tij=0; nc=
11、nc+1步 骤 6: 若 nc预 定 的 迭 代 次 数 Ncmax, 则 转 步 骤 2; 否 则 , 打 印 出 最 短 路 径 ,终 止 整 个 程 序 。1.3 蚁 群 算 法 优 缺 点蚁 群 算 法 是 一 种 分 布 式 的 本 质 并 行 算 法 ， 蚁 群 算 法 是 一 种 正 反 馈 算 法 ， 蚁 群 算法 具 有 较 强 的 鲁 棒 性 ， 易 于 与 其 它 方 法 结 合 。 但 蚁 群 算 法 收 敛 速 度 慢 、 计 算 时 间 长 ，易 于 过 早 陷 入 局 部 最 优 ， 不 利 于 解 决 连 续 问 题 。1.4 蚁 群 算 法 的 展 望（ 1）
12、 目 前 大 部 分 改 进 的 蚁 群 算 法 都 是 针 对 于 特 定 问 题 , 普 适 性 不 强 , 同 时 蚁群 算 法 模 型 也 不 能 直 接 应 用 于 实 际 优 化 问 题 。 虽 然 正 反 馈 机 制 就 是 一 个 很 好 的 普 适性 模 型 , 但 还 远 远 不 够 。 因 此 , 急 需 设 计 一 种 通 用 的 蚁 群 算 法 普 适 性 模 型 。（ 2） 现 阶 段 的 蚁 群 算 法 只 是 模 拟 了 自 然 蚂 蚁 很 少 一 部 分 社 会 性 , 例 如 信 息 素机 制 。 仍 然 有 很 大 的 空 间 去 提 出 更 加 智 能
13、化 的 蚁 群 行 为 。（ 3） 蚁 群 算 法 目 前 还 带 有 明 显 的 经 验 性 , 很 多 结 果 只 是 建 立 在 实 验 的 基 础 之上 , 需 要 逐 步 奠 定 其 理 论 基 础 。因 此 ， 根 据 TSP 问 题 的 特 点 ， 建 立 蚁 群 算 法 的 模 型 ， 可 以 较 好 的 解 决 此 类 组 合优 化 问 题 （ NP问 题 ） 。参 考 文 献1 Dorigo M Ant algorithms and atigmergyJ Future Generation ComputerSystem.2000,16（ 8） ： 851-8712 Dori
14、go M Gambardella L M Ant colony system： a cooperative learningapproachtothetravelingsalesmanproblemJ IEEETrans onEvolutionaryComputation， 1997， 1（ 1） ： 53 663 Dorigo M Luca M The ant colony algorithm applied to the nuclear reloadproblem Annals of Nuclear Energy 2009， 29（ 12） ： 1455 14704 Dorigo M An
15、t colony system： optimization by a colony of cooperatingagents IEEE Trans on Systems, Man， and Cybernetics， Part B， 1996，26（ 1） ： 29 415 杨 海 ， 王 洪 国 ， 徐 卫 志 蚁 群 算 法 的 应 用 研 究 与 发 展 J 科 学 和 技 术 信 息 学 报 ，2007， （ 28） ： 13-146 张 宗 永 ， 孙 静 ， 谭 家 华 蚁 群 算 法 的 改 进 及 其 应 用 J 上 海 交 通 大 学 学 报 ， 2002，36（ 11） ：
16、1564-15677 尹 晓 峰 ， 刘 春 煌 基 于 MATLAB 的 混 合 型 蚁 群 算 法 求 解 旅 行 商 问 题 J 铁 路 计算 机 应 用 ， 2005， 14（ 9） ： 4-78 刘 志 硕 ， 申 金 升 ， 柴 跃 廷 一 种 求 解 车 辆 路 径 问 题 的 混 合 多 蚁 群 算 法 J 系 统仿 真 学 报 ， 2007， 19（ 15） ： 3513-35209 董 萍 基 于 蚁 群 算 法 求 解 TSPJ 无 锡 职 业 技 术 学 院 学 报 ， 2008， 7（ 5） ： 34-3610 王 果 ， 戴 冬 基 于 蚁 群 算 法 的 TSP问 题 求 解 J 河 南 机 电 高 等 专 科 学 校 学 报 ，2008， 16（ 5） ： 42-432. 毕 业 设 计 任 务 要 研 究 或 解 决 的 问 题 和 拟 采
