基于改进蚁群算法的计算机网络路由优化研究
- 格式：pdf
- 大小：104.64 KB
- 文档页数：1
算法分析
基于改进蚁群算法的计算机网络路由优化研究
孟建 东
（ 山东医学高等专科学校计算机教研 室 山东临沂 ２ ７ ６ ０ ０ ０ ）
摘要 ： 路 由作 为计算机 网络 的重要 组成部分， 对 于提 高计 算机 网络服务 质量具 有重要作 用， 备 受社会 关注。 论文 简单提 出计算机 网络路 由优化 问 题， 为 了进一 步解决计算机 Ｎ￣ － － ｇ 息传输过程 中 出现的延 时、 延 时抖 动、 宽带限制与路径 消耗４ 大问题， 提 出了改进 蚁群算 法的途径 。 对蚁 群算法的定 义、 特点、 原理 与 改 进 、 结果做 了分 析 ， 取 得 一 定 的成 功 。 关键 词： 蚂 蚁算 法 网络 路 由 优 化 中图分类 号： Ｔ Ｐ ３ ９ ３ ． ０ ２ 文献 标识码 ： Ａ 文章编 号 ： １ ０ ０ ７ － ９ ４ １ ６ （ ２ ０ ｌ ５ ） ０ ８ — ０ １ ５ ０ — ０ １
Ｉ根据式 （ １ ） 选择ｊ ｏ ｔ ｈ ｅ ｒ ｗ ｉ ｓ ｅ
在这里的 ｑ 是０ －１ 间的均匀分布 随机 数 ， 而ｑ 。 则 是０ － １ 之间的 常数 ， （ ｔ ） 表示蚁群算法改进 的网络路 由延时与延时抖动 、 倒数 的
函数， 也就是 ＝１ ／ （ ｄ ＋ａ ｊ ｆ ） 。 通过这样的蚁群算法改进， 利于蚁
， ｒ 、
一
Ｊ ｎ ｌ ａ ｘ 口
） 。 町 （ ｆ ） 妇
， ’ 、
，
２ 蚁ห้องสมุดไป่ตู้ 算法的定义 、 特点、 原 理及 改进分析
２ ． １ 蚁 群 算 法 的定 义及 特 点
蚁群算法最 早出现在２ ０ 世纪９ ０ 年代 ， 由意大利学者Ｍ・ Ｄ ｏ ｒ ｉ ｇ ｏ 等人共 同提 出， 是根据蚁群行为而提 出的用于求解组合优化 问题 的 种新型模拟进化算法 ， 又被乘坐蚁群系统［ ２ １ 。 它对于解决Ｑ Ａ Ｐ 分配 问题、 Ｔ Ｓ Ｐ 旅行商问题 以及Ｊ Ｓ Ｐ Ｎ ］ 度问题都具有较好的应用效果 ， 并 呈现出正反馈 、 分布式计算等特点 。 由此可见 ， 蚁群算法在解决复杂 优化 问题上具有一定的优势 ， 适用于计算机 网络路 由优化 问题 。
一
巍
～ ㈤
由优化 ， 就是指在网络 中满足一个或多个约束条件下 ， 寻找从路 由 Ａ ｒ ｊ ， （ ｔ ） ＝ △ （ ｆ ） （ ２ ） 个节点到另一节 点的最佳路径 的过程 。 当然也是为了有效 的解决 ＝１ 计算机 网络数据 传输过程 中， 出现的延时、 丢包 、 宽带限制等 问题 ， 计算机 网络路 由优化主要是为 了解决节点 间数据信息传输过 尽量减少路径能量 消耗 。 延时、 延时抖动 、 宽带 限制与路径消耗是影 程 中出现 的延时 、 延时抖动 、 宽带 限制 、 路径能量消耗等问题 。 在进 响计算机 网络数 据信 息传递的４ 大主要 因素 ， 改进蚁群算法就是为 行节点状态转移改进过程 中， 分别用ｄ 、 ｄ ｊ 、 ｂ 、 ｃ 表示上述网路 路 由需 了更快速有效的解决计算机网络路由存在 的这些问题 ， 保证计算机 解决 的问题 ， 形成 的计算公 式如 下所示 ： 网络 的 正 常 运 行 ｕ 。
群在行进状态转移 时， 选择 信息 素最 浓的路径 前进 ， 很好的避免 了 出现局部最 优值 的情 况。
一
４结 语
随着计算机 网络逐步的深入人们的 日常生活工作 ， 计算机 网络 服务质量就是关注的焦点 ， 计算机 网络路 由作为必不可少的组成部 蚂蚁在 觅食 的过程 中 ， 会在经过 的路上 留下信息素 ， 并能感知 通过对路 由的优化来提高计算机 网络服务质量成为人们研 究的 到其他信息素的存在 ， 以此来确定 自己的运动方 向准 确与否 ， 因此 分 ， 新方 向。 通过对蚁群算法 的改进 ， 将其应用于计算机 网络路 由的优 使得大量的蚂蚁都 向着信息素强度较高的方 向移动［ ３ １ 。 当路上 出现 取得 巨大成功 ， 值得继续深入 研究。 障碍物时 ， 蚂蚁在短 路径上 留下的信 息素更 多 ， 使得选择短 路径 的 化上 ， 参考文献 蚂蚁越来越多 ， 就是所谓 的正反馈现象 。 当然蚂蚁在运动过程 中， 在短路径上留下的信息素远远大于长 ［ １ ］ 贾云富， 秦 勇， 段富， 等． 蚁群算法及其在路 由优化 中的应用 综述 路径 ， 主要 是因为路径较短 ， 蚂蚁所耗 时间较短 ， 加大 了信息素 。 这 ［ Ｊ ］ ． 计算机工程 与设计， ２ ０ ０ ９ （ １ ９ ） ： ４ ４ ８ ７ — ４ ４ ９ １ ． 也使得后面 蚂蚁选择该路径的概率大大提升 ， 都沿着最短路径前进 ［ ２ ］ 张凌． 蚁群算法的研究及其在网络路由优化上 的应用［ Ｄ ］ ． 江南大 觅食 ， 形成著名 的信息正反馈现象 。 学， ２ ０ １ ４ （ ９ ） ： ８ ６ － ８ ７ ． ［ ３ ］ 史士财， 等． 基于改进蚁群算法的装配序列规戈 ０ ［ Ｊ ］ ． 计算机集成制 ３ 蚁群 算 法 的改 进及 实 现 造 系统， ２ ０ １ Ｏ （ ６ ） ： １ １ ８ ９ —１ １ ９ ４ ． 从蚂蚁算法 的原理可知 ， 它 的实质就 是分布 式并行算法 ， 使得
随着互 联网规模 的逐渐增大 ， 网络技术 也在 不断 的完善 与成 熟， 尤其是多媒体服 务应用的增加 ， 使得提高计算机网络服务质量 成为重要课题 。 当然 在享 受计 算机 网络 带来的诸多便利时 ， 更多的 专家讲 关注 焦点转移 到网络路 由优 化问题上 ， 蚁群 算法被广泛应 用， 并取得一定效果 。
１计 算机 网络 路 由优 化 的提 出
（ ｆ ） ＝ 在 网络规模 日益扩大的今天 ， 利用计算机 网络传输数据常 出现 丢包、 延时 以及宽带 限制等 问题 ， 都会对网络正常运行 产生影响 。 路 当然随着蚂蚁在前进过程 中留下的信息 素越来越多， 启发信息 由算法 作为计算机 网络的重要组成 部分 ， 更是对 网络具有直接 影 为 了不断更新信息素 ， 传统 的蚁群算法也需要进行 响， 同时路 由包含多种约束条件 ， 是一个复 杂的ＮＰ － Ｃ问题 ， 很难通 就会受到影响 ， 表现为 ： 过简单 的路 由算法解 决。 因此众多学者打算利用不 同算法 的结合 ， 更新 ， Ｔ ｊ ￣ （ ｔ ＋ ｎ ） ：（ １ 一 ｐ ） ‘ ） ＋ △ （ ｆ ） 或是优化算法 来解决计算机网络 路由问题 。 而所谓 的计算机 网络路
路径 规划呈现正反馈校正机制， 鲁棒性较 好。 然而该计算方法过程 较为复杂 ， 对于高维规划所需 时间较长 ， 收敛速度缓慢， 极易 陷入局 部最优值 中， 因此需要改进 。 在传统 的蚁群 算法 中， 引入状态转移规
制， 蚂蚁ｋ 在ｔ 时刻从ｉ 处转移到ｊ 处的概率为 （ ｆ ） ， 算 式如 下所示 ：
基于改进蚁群算法的计算机网络路由优化研究
孟建 东
（ 山东医学高等专科学校计算机教研 室 山东临沂 ２ ７ ６ ０ ０ ０ ）
摘要 ： 路 由作 为计算机 网络 的重要 组成部分， 对 于提 高计 算机 网络服务 质量具 有重要作 用， 备 受社会 关注。 论文 简单提 出计算机 网络路 由优化 问 题， 为 了进一 步解决计算机 Ｎ￣ － － ｇ 息传输过程 中 出现的延 时、 延 时抖 动、 宽带限制与路径 消耗４ 大问题， 提 出了改进 蚁群算 法的途径 。 对蚁 群算法的定 义、 特点、 原理 与 改 进 、 结果做 了分 析 ， 取 得 一 定 的成 功 。 关键 词： 蚂 蚁算 法 网络 路 由 优 化 中图分类 号： Ｔ Ｐ ３ ９ ３ ． ０ ２ 文献 标识码 ： Ａ 文章编 号 ： １ ０ ０ ７ － ９ ４ １ ６ （ ２ ０ ｌ ５ ） ０ ８ — ０ １ ５ ０ — ０ １
Ｉ根据式 （ １ ） 选择ｊ ｏ ｔ ｈ ｅ ｒ ｗ ｉ ｓ ｅ
在这里的 ｑ 是０ －１ 间的均匀分布 随机 数 ， 而ｑ 。 则 是０ － １ 之间的 常数 ， （ ｔ ） 表示蚁群算法改进 的网络路 由延时与延时抖动 、 倒数 的
函数， 也就是 ＝１ ／ （ ｄ ＋ａ ｊ ｆ ） 。 通过这样的蚁群算法改进， 利于蚁
， ｒ 、
一
Ｊ ｎ ｌ ａ ｘ 口
） 。 町 （ ｆ ） 妇
， ’ 、
，
２ 蚁ห้องสมุดไป่ตู้ 算法的定义 、 特点、 原 理及 改进分析
２ ． １ 蚁 群 算 法 的定 义及 特 点
蚁群算法最 早出现在２ ０ 世纪９ ０ 年代 ， 由意大利学者Ｍ・ Ｄ ｏ ｒ ｉ ｇ ｏ 等人共 同提 出， 是根据蚁群行为而提 出的用于求解组合优化 问题 的 种新型模拟进化算法 ， 又被乘坐蚁群系统［ ２ １ 。 它对于解决Ｑ Ａ Ｐ 分配 问题、 Ｔ Ｓ Ｐ 旅行商问题 以及Ｊ Ｓ Ｐ Ｎ ］ 度问题都具有较好的应用效果 ， 并 呈现出正反馈 、 分布式计算等特点 。 由此可见 ， 蚁群算法在解决复杂 优化 问题上具有一定的优势 ， 适用于计算机 网络路 由优化 问题 。
一
巍
～ ㈤
由优化 ， 就是指在网络 中满足一个或多个约束条件下 ， 寻找从路 由 Ａ ｒ ｊ ， （ ｔ ） ＝ △ （ ｆ ） （ ２ ） 个节点到另一节 点的最佳路径 的过程 。 当然也是为了有效 的解决 ＝１ 计算机 网络数据 传输过程 中， 出现的延时、 丢包 、 宽带限制等 问题 ， 计算机 网络路 由优化主要是为 了解决节点 间数据信息传输过 尽量减少路径能量 消耗 。 延时、 延时抖动 、 宽带 限制与路径消耗是影 程 中出现 的延时 、 延时抖动 、 宽带 限制 、 路径能量消耗等问题 。 在进 响计算机 网络数 据信 息传递的４ 大主要 因素 ， 改进蚁群算法就是为 行节点状态转移改进过程 中， 分别用ｄ 、 ｄ ｊ 、 ｂ 、 ｃ 表示上述网路 路 由需 了更快速有效的解决计算机网络路由存在 的这些问题 ， 保证计算机 解决 的问题 ， 形成 的计算公 式如 下所示 ： 网络 的 正 常 运 行 ｕ 。
群在行进状态转移 时， 选择 信息 素最 浓的路径 前进 ， 很好的避免 了 出现局部最 优值 的情 况。
一
４结 语
随着计算机 网络逐步的深入人们的 日常生活工作 ， 计算机 网络 服务质量就是关注的焦点 ， 计算机 网络路 由作为必不可少的组成部 蚂蚁在 觅食 的过程 中 ， 会在经过 的路上 留下信息素 ， 并能感知 通过对路 由的优化来提高计算机 网络服务质量成为人们研 究的 到其他信息素的存在 ， 以此来确定 自己的运动方 向准 确与否 ， 因此 分 ， 新方 向。 通过对蚁群算法 的改进 ， 将其应用于计算机 网络路 由的优 使得大量的蚂蚁都 向着信息素强度较高的方 向移动［ ３ １ 。 当路上 出现 取得 巨大成功 ， 值得继续深入 研究。 障碍物时 ， 蚂蚁在短 路径上 留下的信 息素更 多 ， 使得选择短 路径 的 化上 ， 参考文献 蚂蚁越来越多 ， 就是所谓 的正反馈现象 。 当然蚂蚁在运动过程 中， 在短路径上留下的信息素远远大于长 ［ １ ］ 贾云富， 秦 勇， 段富， 等． 蚁群算法及其在路 由优化 中的应用 综述 路径 ， 主要 是因为路径较短 ， 蚂蚁所耗 时间较短 ， 加大 了信息素 。 这 ［ Ｊ ］ ． 计算机工程 与设计， ２ ０ ０ ９ （ １ ９ ） ： ４ ４ ８ ７ — ４ ４ ９ １ ． 也使得后面 蚂蚁选择该路径的概率大大提升 ， 都沿着最短路径前进 ［ ２ ］ 张凌． 蚁群算法的研究及其在网络路由优化上 的应用［ Ｄ ］ ． 江南大 觅食 ， 形成著名 的信息正反馈现象 。 学， ２ ０ １ ４ （ ９ ） ： ８ ６ － ８ ７ ． ［ ３ ］ 史士财， 等． 基于改进蚁群算法的装配序列规戈 ０ ［ Ｊ ］ ． 计算机集成制 ３ 蚁群 算 法 的改 进及 实 现 造 系统， ２ ０ １ Ｏ （ ６ ） ： １ １ ８ ９ —１ １ ９ ４ ． 从蚂蚁算法 的原理可知 ， 它 的实质就 是分布 式并行算法 ， 使得
随着互 联网规模 的逐渐增大 ， 网络技术 也在 不断 的完善 与成 熟， 尤其是多媒体服 务应用的增加 ， 使得提高计算机网络服务质量 成为重要课题 。 当然 在享 受计 算机 网络 带来的诸多便利时 ， 更多的 专家讲 关注 焦点转移 到网络路 由优 化问题上 ， 蚁群 算法被广泛应 用， 并取得一定效果 。
１计 算机 网络 路 由优 化 的提 出
（ ｆ ） ＝ 在 网络规模 日益扩大的今天 ， 利用计算机 网络传输数据常 出现 丢包、 延时 以及宽带 限制等 问题 ， 都会对网络正常运行 产生影响 。 路 当然随着蚂蚁在前进过程 中留下的信息 素越来越多， 启发信息 由算法 作为计算机 网络的重要组成 部分 ， 更是对 网络具有直接 影 为 了不断更新信息素 ， 传统 的蚁群算法也需要进行 响， 同时路 由包含多种约束条件 ， 是一个复 杂的ＮＰ － Ｃ问题 ， 很难通 就会受到影响 ， 表现为 ： 过简单 的路 由算法解 决。 因此众多学者打算利用不 同算法 的结合 ， 更新 ， Ｔ ｊ ￣ （ ｔ ＋ ｎ ） ：（ １ 一 ｐ ） ‘ ） ＋ △ （ ｆ ） 或是优化算法 来解决计算机网络 路由问题 。 而所谓 的计算机 网络路
路径 规划呈现正反馈校正机制， 鲁棒性较 好。 然而该计算方法过程 较为复杂 ， 对于高维规划所需 时间较长 ， 收敛速度缓慢， 极易 陷入局 部最优值 中， 因此需要改进 。 在传统 的蚁群 算法 中， 引入状态转移规
制， 蚂蚁ｋ 在ｔ 时刻从ｉ 处转移到ｊ 处的概率为 （ ｆ ） ， 算 式如 下所示 ：
