《基于禁忌搜索算法的改进有向赋权网络最短路径算法.doc》由会员分享,可在线阅读,更多相关《基于禁忌搜索算法的改进有向赋权网络最短路径算法.doc(10页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第 卷第 期 交 通 科 技 与 经 济 , 年 月 , : , , , (): 引用 著录 罗亦俊 : 刘小亮基于禁忌搜索算法的改进有向赋权网络最 短路径算法 交通科技与经济 基 于禁 忌 搜 索 算 法 的 改 进 有 向 赋 权 网 络 最 短 路 径 算 法 , 罗亦俊 刘小亮 ( 兰州交通大学 交通运输学院 , 甘肃 兰州 ; 西安科技大学 通信与信息工程学院 , 陕西 西安 ) 摘 要 :在网络优化中,路由器的网络计算能力提升可以很大程度地减 少网络请 求 的响应时 间。在传统的 有向赋权 最短路径求解过程中, 算法仍存在 慢收敛问题。建 立一个 具体的 网络拓 扑结构 问题模型
2、,并 利用禁 忌搜索 ( 算法框架 ,对禁忌搜索算法的常用参数进行设置,对多个实例拓扑网络结 构编程求解 ,经 多组数据测 试和分析,证明 该方法能适应多条路径选择,算法可行并有效。 , , , ; , , , ) : , , , 作 为 网 络 优 化 设 计 中 的 关 键 问 题 ,最 短 路 径 的最 优解 可以 包揽 这 个 多 目标 条 件 的 最 优 解,因 而 ( , )问题 在求 解通 信网 、交 通 网、电 针对 某一 目标 取得 较优 解 。 网 以及 项 目 运 筹 网 等 网 络 规 划 和 路 径 决 策 中 有 着 基于 上述 几点 ,本 文 提 出 一 种 基于
3、 禁 忌 搜 索 算 重 要意 义 。通 常情 况 下 ,经 典 的 最 短 路 径问 题 仅 法的 改进 有向 赋权 网 络 最 短路 径 的 计 算 方 法,此 方 : ; ; ; : : : ( ) : ; ; ; 。 有向赋权网络最短路径问题模型描述 仅 考虑 路 径 的 距 离 最 短 、时 间 最 短 或 者 费 用 最 少 , 法的 目的 是 缩 减 计 算 有 向 赋 权 网 络 最 短 路 径 模 型 属 于单 目标 优化 ,这 就 很 难 准确 描 述 实 际 网 络 环境 问题 的时 间和 次数 ,提高 计算 效率 。 题 经常 会和 多目 标或 多约 束条 件关 联到
4、一起 。如 通 信网 络中 的时 延、分 组 掉 包、带 宽、抖 动 等 约 束条 本文 基于 现实 通 信 和 交 通网 络 基 础 ,构 建 一 个 件 ,在 多条 件 最 短 路 径 问 题 中,往 往 并 非 某 一 条 件 有向 赋权 网络 的最 短 路 径 问题 模 型 ,该模 型 可 以 被 收稿日期 : 理与信息系统,智能算法等 交 通 科 技 与 经 济 第卷 图 ( , )中, 是 图 中 的一 条 边 , 是 加入 到禁 忌表 中。 当 整 个 运 算达 到 了 某 一 规 则后 , 到 的 一条 道 路 或 者 一 条链 路 。 每 条 边都 赋 有 停止 搜索 ,根
5、据禁忌 表原 则获 取其 最短 路径 。 一 个实 数 ,表示 实 际网 路 中 的 距 离,用 邻 接 矩阵 该算 法 求 解 的 设 计 思 路 主 要 包 括 以 下 个 存 放 图 各 结点 对 之 间 的 特 性,当 一 个结 , 部分 。 ) : 点 不能 直接 到达 另一 个结 点时 。 将其 设定为 一个 , 领 域 变 换 初 始 路 径 中 随 机 选 取 点 的 优 先 , 无 穷大 的 数 从 起 点 出 发 到 达 终 点 距 离 最 短 的 那 权 通过 解码 原 则 获 取 下 一 个 点 的 位 置 产 生 新 的 条 路径 就为 图 )邻点 ( ) 的最 短路
6、 径。 路径 集合 称 为 初 始 路 径 领 域 。 为 更 好 地 获 取 有 效 领域 路径 ,本 文 采 用 了 递 归 法 ,通 过 多 次 递 归 获 取 。 ( ) 指 的是 所有 达到 点 的集 合 领域 路径 ) : 。 所 有从 点 出发 的点 的集 合 候 选解 集 初 始路 径的 邻域 子集 )解的 表 示 :给 每 一 个 顶 点 一 个 优 先 权 (不 同 的 顶点 权不 同)。 顶 点的 优先 权。 先 权最 大 的 点 ,令 ,如 此 下 去,直 到 (终点)。 (, )。而 该 模 型 问 题 的 最 短 路 径 可 以 转 化 型 不同 处是 有向 以 及
7、 带权 值 ,其 中 权 值 的 用 法 主要 是 对领 域解 的确 定。 应用 算法求解设计思路 禁 忌搜 索 ( )模 拟 人 脑 短 期 记 忆 功 能,全局 逐 步 寻 找 最 优 解,为 避 免 无 效 的 循 环 计 算 ,它 使用 禁忌 准 则来 实 现 。同 时 使 用 藐 视 准 则来 接 受较 差解 ,用 来确 保 对 于 不同 范 围 内 有 效 路 径的 探 测,在这 方面 禁忌搜 索的 局部 搜索 能力 较强 。 本 文设 计的 有 向 赋权 网 络 问 题 的 禁忌 算 法 ,首 先 设计 一个 合理 的 邻 接矩 阵 方 法 ,根 据 起 点 获 取下 一 个可
8、能到 达的 点 的 集合 ,然后 在 该 集 合 中 随机 取 出 其中 一个 有效 点 作 为路 径 达 到 的 第 二个 点 ,依次 循 环获 取,直 至 达 到 终 点 位 置 结 束 ,获 取 的 所 有 点 的 集合 称为 初 始 解,然 后 计 算 其 长 度 ,再 根 据 领 域 搜 索原 则,获取领 域 解 ,据 此 获 取 局 部 最优 解 ,最后 ) : , , , 。 )优 先 权: ( ) ,是 指 优 先 权 的 值为 。 令 ( ) , , ( ) 。 ) : , 其 中,从 到 节 点 的 路 径 由 路 径 经 过的 节点 序列 构成 : 。 ( (,) ( (
9、, ) ( , ( ) ( )。 在该 过 程 中,针 对 该 模 型 与 其 他 模 )禁 忌表 :用 来 存 放 禁忌 对 象 的 数 据 结构 。 通 常情 况下 ,禁 忌表 中的 对 象 是 不 能 被选 作 产 生 邻 域 的新 解,这也是 为 了防 止 出 现 陷 入 局部 最 优 解 和 循 环搜 索的 情况 。 )藐 视准 则:如果 候 选 解 集 中 的最 优 对 象 比 以 前历 史最 优 解 更 优 时 ,就 算 该 对 象 已 经 被 禁 忌 ,但 仍可 以替 代之 前的 最 优 解,在 下 一 次 迭代 过 程 作 为 初始 解,也就 是特 赦 该 禁忌 对 象。 还
10、有 一 种特 赦 情 况是 :如 果 候 选 解 集 中 的 全 部 对 象 都 已 经 被 禁 忌, 那么 特赦 最优 候选 解。 )终 止条 件:如果 算 法 已 经 达 到之 前 预 设 的 迭 代次 数,或者在 设 置好 的 固 定 周 期 内连 续 获 得 的 最 优解 不发 生变 化,这两 种 情 况 满 足 其中 一 个 就 可 以 终止 计算 过程 ,将 固定 周 期 设 置 成 算法 总 迭 代 次 数 的倍 。 算法的实现过程 本文 提出 的 关 于 有 向 赋 权 网 络 最 短 路 径 问 题 模型 的解 决方 法,其 具体 实现 流程 如图 所 示。 在搜 索过 程中
11、 ,由 于 有 向 赋 权 网络 路 径 是 路 径 固定 的不 可 随 机 抽 点 ,在 本 文 中 ,主 要 采 用 多 次 递 归函 数方 法结 合邻 接 矩 阵 的 特性 获 取 迭 代 初 始解 。 通过 计算 迭代 初始 解 的 长 度,并 将 迭 代初 始 解 的 路 径编 码放 入禁 忌表 中 ,然 后 根 据 权 限值 的 大 小 选 取 该初 始解 的路 径领 域 解,选 取 出 符 合 条件 的 领 域 解 集后 ,对 其领 域 解 集 进 行 路 径 长 度 计 算,通 过 比 较 该领 域解 集与 迭代 初 始 解 之间 的 路 径 长 度,确 定 下 一轮 迭代 初
12、 始 解 和 禁 忌 表 是 否 添 加 和 解 禁 。 一 次 轮询 比较 ,直 到终 止 条 件得 到 满 足 ,结 束 此 次 计 算。 以上 是本 文设 计实 现思 路。 初始 解的 确定 设 计:根 据 模 型 要 求得 到 源 节 点 和目 标节 点的 编码 ,根 据 源 点 及 上 面的 邻 接 矩 阵 判 断与 该源 点连 通的 其 他 节 点编 码 ,从 中取 出 权 值 最 大的 点,依次类 推获 取最 后的 目标 节点 。 第期 罗亦俊 等, :基于禁忌搜索算法的改进有向赋权网络最短路径算法 : 图 算法实现流程 : , 评 价函 数的 设 计 分 别 计算 每 一 次
13、领 域 搜索 后 , 终止 条件 的 设 计 。 算 法 达 到 预 设 的 迭 代 次 数 获 取的 最短 路径 编 码 长度 , 判断 该 路 径 是 否 加入 到 , 即可 终止 计算 过程 禁 忌表 中 等 待 预 设 的 迭 代 次 数 结 束 后 计 算 禁 忌 试验与结论 表 中距 离 最 短 的 路 径 作 为 该 有 向 拓 扑 网 络 的 最 短 路 径。 本文 给定 一个 具体 模型 ,其 中 包含 的 点 数为 在 本文 设 计 中 增 加 了 一 个 条 件 函 数 用 于 处 理 个 ,其有 向赋权 如图 所 示 。 同 一禁 忌长 度和 同 一 迭代 次 数 ,在
14、 不 同 领 域 路 径搜 在上 述的 有向 赋 权 图 中,圆 圈 中 的标 号 代 表 路 径编 码,同时也 表 示上 一 个 节 点 到 下 一 个 节 点 的 权 索 数目 下,计算 出 最短 路 径 编 码 的 出 现率 关 系 。每 个 领域 路 径 搜 索 数 目 的 最 短 路 径 编 码 出 现 率 计 算 值 ,而带 箭头的 线上 的标 号表 示两 点间 的长 度 。 方 法如 式()所 示 为解 决该 模型 的问 题,本 文 利 用 语言 在 () 软件 工 具 中 编 程 ,完 成 的 最 短 路 径 式 中 : 为最 短路 径 出现 率 , 为 运 行次 数 , 查找
15、 。 整个 程 序 中 采 用 的 路 径 编 码 策 略 :采 用 可 变 为 最短 路径 出现 次数 。 长,将节 点序 号 作 为 路 径 的 编 码 方 式,每 条 路 径 都 交 通 科 技 与 经 济 第卷 由起 始节 点 编码 均采 用 到目 的 节 点 号 编码 串 表 示 ,其 中 所 有 (链表 结构 )实 现。 编码 串所代 表 的 图 有向赋权拓扑结构网络 路径 不能 有重 复节 点 ,同 时 不 允 许 出现 无 连 接 节 点 间的 编码 关系 。 数;通 过编 写运 行程 序后 发 现其 最 短路 径 为 况如 图 所示 。 图 运行结果 郝 光,张 殿 业,冯
16、勋 省 多目 标 最 短路 径 模 型 及算 法 由 图 可以 得 知 :上 述 模 型 所 得 的编 码 路 径 西南交通大学 学报, , (): 为 , , , 最 短路 径的 编码 串,其最短 距离 为 。 朱涛 张水平 郭戎萧 等改进的加权复杂网 络节点重 , , 本 文另 外设 计一 个 个 点 的 模 型,根 据 以 上算 要度评估的收缩方法 系 统工程与 电子技术 法的设 计、实 现 以 及 运 行 的 结 果,可 充 分 证 明 本 文 提 出的 关 于 有 向 赋 权 网 络 最 短 路 径 问 题 的 解 决 方 张帆,李 军,王钧,等 多 目标 最短 路 径进 化求 解
17、方法 系统工程, , (): 法 是有 效的 ,同 时 ,确 定 了 一 种 对 领 域 搜 索 数 目 的 , 设 置确 定方 法 。 康晓 军 王茂 才 基于 遗传 算法 的最 短路 径问 题 求解 , , ( ): 在 后续 的工 作 中 , ,需 要 进一 步 研 究 算 法 的时 间 , 计算机工程与 应用 冶晓隆,兰巨龙,郭通基于 主成分 分析禁 忌搜索 和决 复 杂度 并 对 算 法 进 行 改 进 引 入 其 他 优 秀 的 算 法 策树分类的异常流量检测方法计 算机应用, , (比如 遗传 算法 )来减 少其 时间 复杂 度 。 (): , , , : , , 、 、 , ;
18、 , (): 参 考文 献 : 李进 傅培华 李修琳 等低碳环境下的车辆 路径问题 , , 阎啸天,武穆清 基于 的网络最短路径多目标 优化 及禁忌 搜 索 算 法 研 究 中 国 管 理 科 学 算法研究控制与决策, , (): 黄艺 坤 算 法在 室内 移动 导航 最短 路径 寻址 ( ): 第期 的改进 罗亦俊 等, :基于禁忌搜索算法的改进有向赋权网络最短路径算法 福建师范大学学报(自然科 学版), , (): 於世为,郭海湘,诸克军 基于 的开放式车辆路 胡天寒,叶明全,张浩,等 基于禁忌搜索算法的特 征选 径 优 化 算 法 及 应 用 系 统 管 理 学 报 , , , ():
19、择方法研究 梅海涛 王毅, ,华继 学 直 觉模糊 小生境 的自 适应遗 传 李茂军 ,童调 生 单亲遗 传算 法及其 全局 收敛性 分析 算法求解旅行商问题 计算机 科学, , ( ): 自动化学报, , (): , 李惠,蒋大奎基于单亲遗传禁忌搜索算法的 手术排程 , , 张毅 梁艳春基于选路优化的改进蚁群 算法 计算 机工程与应用, , (): 问题研究 计算 机应用研究 责 任编 辑 : 王 欣 钟石泉,杜纲,贺国 光 有 时间窗 的开放 式车 辆路径 问 题及其 遗 传算 法 计 算机 工 程 与 应 用, , : ( 上接 第 页 ) 张王 乐元,张荠 丰,孙 增林,等 基于灰 色
20、理论 的公路 止 ,从 而 使 模 型 达 到 很 好 的 预 测 精 度 ,利 用 残 差 修 正 ( ,)模 型 对 包神 铁 路 北线 的 货 运 量进 , , 工程施 工 造价 动 态 控 制研 究 交 通 科 技 与 经 济, , (): 行 预测 是可 行 的 模 型 的 精 度 达 到 了 一 级 , 预 测 值 李梦婉,沙秀艳 基于 (, )灰色 预测 模型的 改进 与 实际 拟合 度很 好 预 测 结 果可 以 为 铁 路 企 业 在制 与应用计算机 工程与应用, , (): 定 发展 策略 和 资 源 配 置,以 及 投 资 结 构 、运 输 组 织 和 经营 管理 方面
21、有很 好的 借鉴 作用 。 , (): ,适 用 于近 ( ,) : 期 的预 测,随 着 新 数 据 的 出 现,要 及 时 对 原 始 数 据 进 行更 新,重 新 建 立 新 的 预 测 模 型 ,才 能 达 到 最 好 的 预测 效果 和最 高的 预测 精度 。 , , 参 考文 献 : , 邓聚龙 灰色 系统理论 教程 武 汉 :华中 理工大 学 焦永兰 ,孙秉珍基于灰色理论的铁路客货运 量预测研 究 兰州交通大 学学报 , (): 出版社, , , 王 慧 晶 基 于灰 色 预测 模 型的 铁 路 客运 量 预测 研 究 , ,( ): 铁道运输与经济 用交通科技与经济, , (): ) , (): , (): (, ) : , , (,) 秦天轶公路 工程招 投标阶 段的造 价管 理工作 江 西 建材 , (): 故预测数学的实践与认识, , ( ): 伍雄斌残差 灰色预 测模型 在交通事 故预测 中的应 用 杨阳基于残差修正的 (,)模型 的我国人均 粮食 产量预测统计与决策,( ): 马彪 ( )模 型 在 春运 铁 路客 流 预测 中 的 应用 交通科技与经 济, (): , 尹晖,周晓庆,张晓鸣非等间距 (,)建 模方法对 责 任编 辑 : 王晓 琳 , (, ) , , (): , ,( ): , , ():
限制150内