基于现代超启发式搜索方法的计算机通信网络中路由选择优化的研究.pdf

第 3 7卷 第 2期 2 0 0 1年 4月 兰州大学学报(自 然科学版)J o u r n a l o f La nz h ou Uni v e r s i t y(Na t u r a l S c i e n c e s)V0 1 3 7No 2 Ap r 2 0 01 文章 缡号：0 4 5 5 2 0 5 9(2 0 0 1)0 2 0 0 6 3 0 8 基 于现 代 超 启 发 式搜 索方 法 的 计 算 机 通 信 网 络 中 路 由选 择 优 化 的 研 究 许 福永，梅 中磊(兰 州大 学 信 息 科 学与 工程 学 院，甘肃 兰 州 7 3 0 0 0 0)摘要：为了改进计 算机通信网络的性能 首次采用近年来才开始应用、且具有很强灵活性的现代 超 启 发 式搜 索 方法 Ta b u搜 索 方 法，对计 算 机 通 信 网络 中重 要 的路 由选 择 优 化 问 题 进 行 了 详 细 的 研 究 得 到 了 比经典 的 拉 格 朗 日松 弛及 子 梯 度 优化 方法 更 优 的 结 果，尤 其 在 网络 负荷 很 重 的 情 况下 与 其它 算法 相 比，更 显 示 出该 方 法 的优 越性 从 而 为计 算 机网 络 的优 化 理 论 提 供 了新 的 思 路和方法 大 量的计算机仿真实验 的结 果表 明 所得结论对于计算机通 信网络 以及电信 网、电力 网、交 通 运输 同 等 在 其 性能 优 化与 评 价、提 高 网络 性 能与 技益、降低 运 营 费 用等 方 面，具有 重 要 的 理 论价值 和广 阔 的应 用前 景 关 键词：计 算 机通 信 网络；路 由选 择 组 合最 优化；启 发式搜 索；Ta b u搜 索 中 国分 娄号：TP 3 9 3 文献 标 识 码：A 0引 言 随着 网络技术 的发展 和计算 机应用 水平 的提 高，计 算 机通 信 网络 广泛应 用 于科研、教 育、管理、生 产及 商业等 各个领域 在计 算机通 信网络的设计、建设 过程 中，路 由选择是 一个 十分 重 要但 又非 常复杂 的因素 理想 的路 由选择策 略，能够大大 降低 网络 的传 输 时延，即提 高其 实 时 性，在 一定程度 上 降低 网络 的运营 费用，从而提 高 网络的性 能价 格 比 同时，对 合理、有效 地 使 用 网络资源(如结点 缓冲器和链 路容量)也有很大 的影响 Ga r i s h等 _ 1 于 1 9 8 3年首先 对 S NA(S y s t e m Ne t wo r k Ar c h i t e c t u r e)网络 中的静态非 分 叉 路 由问题进 行 了研 究，并 采用经 典 的拉格 朗 日松弛 算法 和 子梯度 优化 方法，得到 了一 系列 令 人满 意的结果；Na r a r s i mh a n和 P i r k u l 等 r 对 Ga r i s h的算 法进行 了改 进，进 一步 提高 了解 的 质 量；近 年来，Ga r i s h和 Ami r i 等 州对计 算 机通 信 网络 中的路 由选择 及容 量分 配(C F A，C a p a c l t y a n d F l o w As s i g n me n t)问题进 行 了广泛 而又深 入 的研 究，这些 工 作可 以看 作是 路 由选 择 问题 的进一步深 化和拓展 计算机通信网络中的路 由选择 问题，是一个非常复杂的问题，它具有组合优化 问题 的性 质，且属 于其 中的 NP 完 全 一类 无 论在 数学理 论 还是 在工 程 实践 上，都 尚未 找 到切 实有 效 的解法 Gl o v e r 教授 6 于 2 O 世纪 9 O 年代初提出了具有很强灵活性的另一种启发式搜索算法，即 现代 超 启发式搜 索方 法 Ta b u搜索，用来 求解 路 由选择 问题 它 是 一种 限制性 的 局部搜 索 算法，能够在一定程度上模拟人脑的记忆和推理功能，其核心思想是引入了一个非常灵活的 收稿 日期：2 0 0 0 0 5 2 3 作者 简介：许 福 永(1 9 4 1 一)，男，教 授 维普资讯 http:/ 兰 州 大 学 学 报(自 然 科 学 版)第 3 7卷。禁 忌集 合”的概念，用 于指 导具体 的搜 索过程，既能够 保证搜 索 的集 中性，又可 以增 加搜 索 的 广 泛性；另 一方面，Ta b u搜 索方法，建立 了一套非 常完 善 的机 制，能 够或 在很大 程度 上避 免 陷 入 局部最优 解，为获 得全 局最优 解或次优 解提 供 了可 能；而且 Ta b u搜 索方 法本身 所 固有的灵 活性 和可 并行性，也 使得 它很 容 易与其 它搜索 方法 及特 定 问题结 合起来，组成 面 向对象 的实用 并行算法 正 因为如 此，在许 多组 合优化 问题 的解决 过程 中，Ta b u搜 索方法 已显示 出其强大 的 生 命 力 啪 通 过对计 算机通 信 网络 中路 由选 择 问题 求解 的初步 尝试，将会 拓 宽 Ta b u搜 索方 法 的应 用范 围，丰富现 有的计算 机网络优化理论，为计算机 通信 网络 及其它 网络的设计、建设、管 理及 其应用 中所涌现出来 的大量 非线性 最优化 问题，提供 了新 的思路 和方法 1 路 由选择 问题的数学描述 计算机 通信 网络 中的路 由选 择问题，是 网络设计和建 设过程 中的一个重要 因素 它可 以简 单 地描述 为：给 定一具 体拓扑 结构 的网络及其节 点集合()与链路 集合(L)，井 已知 网络 中的 所有通信节点对以及网络相应的传输需求和候选的路由集合，在所有链路容量均确定的情况 下，对 每一通 信节点对，从 相应 的候 选路 由集合 中选 取一 条路 由，使得 该 网络 平均端 到端 的时 延为最小 对该 问题 的 目标 函数所建立 的数学模 型为 f a，1 m i n 、1 圣(1)【Z d 舳 一 d，r rE R a r ，v L_(2)rE R 1，v P 1 I (3)面 0 0，1)，V r R (4)其 中：是所有通 信节点对(源 目的对)的集 合，P为其 中的一个元 素；L表 示链路 集合，z 为 其 中的一个元素；是对 应于节点对 P的候 选路 由集，若 P q，则 S N S 一(为空集)；R 为全 体候 选路 由的集合，r代表 其 中的 一条 路 由；a (或 a r)对 应于 节 点对 P或路 由 r的 报文 到 达速 率；为平均报 文长度 Q 为链路 的容量；4 为决 策变量，即 f 1，如果 路 由 r为某一通 信节点对 的路 由；。【0，其它 而“则 是一个指示 函数，即 f 1，如果路 由 r 经过链 路 “l 0，其 它 约束条件(2)应保证 链路 的数据传输速 率不超过 链路容量 约束条件(3)表 明任 一个通信 节点 对 都应有 且仅有 一条 路 由存在，以保证 其通 信需 求 式(4)则 规定 了决策 变量 的 取值 问题 的 核 心在于，在满足 上述条件 下，使得 目标 函数值 为最小 2现代超启发式 搜索方法 Ts方法 TS(Ta b u S e a r c h)方法 的基本 思想是：首先 利用随 机方法或 与 问题有关 的启发 式方 法产 维普资讯 http:/ 第 2期 许 福永 等：基于 现 代 超启 发式 搜 索方 法 的 计 算机 通信 同 路 中路 由选 择 优 化 的研 究 6 5 生一个 初始解，也即 当前 解 之 后，按照一定 的规则，对此 当前解进行 逐步改 进，也称 为“移 动”由当前 解经过 一次“移 动 所 能够 到达 的所 有解 的集 合，称为 当前解 的邻 域 TS方 法是 在 当前 解 的邻 域 中选 取对 目标 函数改进 最大 的“移动”作为 下一 次搜索 的方 向 当所 有 的“移动”对 目 标 函数均无改 善 时，可采 用对 目标 函数恶化 最小的 移 动”作 为下一步 的搜索 方 向(与贪婪 法不 同)为 防止 在搜索过 程 中陷 入局部最优 解，在 TS方法 中引入了 Ta b u表，即 当前被禁 止的“移 动”Ta b u“移动”的集合 它 可 以由那些 已经 实现 了的。移动”的 反方 向。移动”来构 成 Ta b u 表 中允 许存贮 的 Ta b u“移 动”的最 大数 目，称 为 Ta b u表 的规模，也 叫做 Ta b u保 留期 在搜 索 过 程 中，刚刚 实现的一 个新“移动”的反方 向 移动”被放 入 Ta b u表 中，而 Ta b u表 中 已达到 保 留期 的 移动”则 被移出此表 T a b u搜索 重复上述 步骤，直至满 足一定 的终止条 件，最终可 以得 到一 个全局 最优 或次 优解 2 1 路 由选择 问题解 的构成 形式 对于计 算 机通信 网络 中的任一个 通信节 点对 P E 7，共 有 l l 条候 选 路 由与之 相对 应，将这 些路 由分别 编号 为 0，l，2 ，l l l，并用 一路 由变 量 来表 示，则 由 r，的值 即可获得 该节 点对 的路 由 对所有 l 1 个 节 点对，采用 同样 的操 作，可得一个 l l 维 向量 r一(t o，r “，r 一 )，因此，用 向量 r即可表 示路 由选择 问题 的一个解 2 2初始 解的形 成 因 为初始 解 的质量优 劣对 于 Ta b u搜 索的 成 败有着 很大 的影响，故 采 用 了 以下几 种初 始 解 的形成方 式 随机路 由法是在 每次 Ta b u搜索之 前，由程 序 随机产 生 l 1 个 整 数值，分 别 赋于 r p，P E，且满 足条 件 0 l l l，由此产生初 始解 此外，根据路径 的长短 和跳数(从源节 点到 目的节 点所经过 的节点数)的多少，还有最短 路 由法、最长路 由法以及最少 跳数法等 2 3“移动”的定 义 由上述可 知，TS方法通过 对 当前解 r不断进 行修 正，也 即“移动 来 实现对 整个 解 空间的 搜索，从而 最终得 到 问题 的最优或次优 解 本 文定 义了两种 形式 的“移动”+和 一，它们分 别 产生 两种尝试 解：r 一 r+e i 及 一 一 r一 i=0，1，2 ，l l 一 1 其 中：一与 r 均 为 l l 维 向量，分别表 示尝试 解和当前 解 为一个 l l 维 的单 位矢量，除了第 i 个 元素为 1外，其余 元 素均为 0 很 明显，这些“移动 满足“完整性”的要 求，即任何一个 解，都可 以 由另外 一个解经过 一系列 的“移动”M+或 M 来实 现 2 4 Ta b u表的定 义及管理 如 前 所述，Ta b u表 在 T a b u搜 索 中起 着 非 常 重 要 的作 用 如 图 l所示，采 用一 个 长为 丁一 的环 形 队 列 来表 示 一 个 Ta b u表 队 列 中 的 每 一 个 单 元，存放着通信节点对的编号及相应的操作，其中：尾 维普资讯 http:/ 6 6 兰 州 大 学 学 报(自 然 科 学 版)第 3 7卷 一(为邻域 的规模)两种情况 之所 以取 7，是因为 Gl o v e r的许多 实验表 明，对很 多 组 合优 化问题，丁一 都 已取得 了较 好的结果；取”是 为了适应 不 同规模 的 问题 2 5 邻域搜索 繁略 合 理 的邻域搜索 策略，既 能保 证所 求解 的质量，又 可 以提 高 算 法 的效率 本文 采用 了如下 3种邻 域搜索 策略，并 研究 了它们对搜索结果 的 影响 最优 法：对当前解 的邻域 中的所有可行解 进行 评价，从中选 取 目标 函数 为最 小且 不被禁 止 的解，并移动到 此最优解 显然，该方法要对邻 域 中的所 有解进行 搜 索，因此，速 度较慢，但解 的 质量较 高 最 先法；对当前解 的邻域进 行搜索，当发现某 一可行解 所对 应的 目标函数值 小于 当前最优 解 所对 应 的值 时 立 即停止搜索，并将 当前 解 移动 到此解；如果 这样 的解不存在，则选 取邻域 中 不被禁 止 的最优解，作 为当 前的移动方 向 抽 样 法(采样 法)：在某些 情况下，当 邻域的规 模较 大 时，可对 整个 邻域 的某一 子集进 行搜 索，从中选 取不被禁止 的最优解，并 移动至此 一般 可采取 随机抽样 法 从当前解 的邻 域 中随机 抽取 一定数量 的解，并 对它 们分 别进行评 价 2 6释放水平 的定义 由上所述，T a b u表 中的“移动 一般不可作 为下一 步搜 索 的方 向 但这 也不 是绝对 的 事 实 上，TS方 法对 Ta b u“移 动 都 赋予一个释 放水平 如果 一个 Ta b u 移动 达到 了释放水平，则该“移 动”不被限制，于是 可以 实现 本 文所采用 的释放 水平 为：如果 一个 T a b u“移 动”作用于当 前 解 之后，可 以达到 比以前 所搜索到 的解都要好 的解，则该“移动 不被禁止，因而 可 以实现 2 7终 止 条 件 TS方 法的收敛判 据基本 上是启发式 的，并没 有严 格的收敛 条件 因此，采用 最为广瑟 的方 法，即规定最大 允许迭代 次数 一 在计算 机程序 的开 发测试 阶段，此 判据使用起 来 比较 方便，这 是 由于 TS方法所需要 的收敛 次数虽然与 问题 的规模 有关，但关 系并 不很大 3 计算机仿真实验 的结果及分析 本 文 所做 的大量计算 机 仿真 实验，其 目的是 为 了验 证 Ta b u搜 索 方法 的正确 性并 对 该方 法 的各 种参数 进行优选，确定 最优参数 集合，以指 导今 后 的实践 对 不 同规模 的典 型网络 在不 同 负 荷 下 进 行 了 路 由 选 择 优 化，其 中 包 括 Ga r i s h 和Ha n t l e r，Na r a r s i mh a n，Ga r i s h 和 Ne u ma n 等人用拉格朗 日松弛算法详细计算过 的 ARP A 网和 RI NG 网，分 别如 图 2，3所 示 在 ARP A 网中，共 有 2 1个节 点(4 2 0个 通 信节点对)，2 6 条链路，各通信节点对之间的通 信需 求均 为 4个 信 息包 s；在 RI NG网中，共 有 3 2个 节 点(9 6 2个 通 信 节 点 对)，6 0条 链 路，所 有的通信节点对之间的通信需求均为 1 个信息 包 s 在优化 过程 中，上 述两个 网络 中的任一个 50 k b i t s s 图 2 ARP A 网的拓 扑结 构 Fi g 2 Th e t o p ol o gy s t r u c t u r e 0 f ARP A n e t wo r k 维普资讯 http:/ 第 2期 许 福采 等：基干现 代 超 启发 式植 索方 法的 计 算机 通 信 同培 中路 由选 择 优化 的研 究 6 7 通 信 节点对 之 间的候选 路 由集 合的规 模均 为 5，由路 由 产 生程 序预 先 产生，并 按 照路 径 的长 短从 0到 4编 号，号 码 愈小，路 径越 短(对某个 节点对 其 候选 路 由有 可 能 小 于 5)-用 Ta b u搜索 方法对 上述两个 网络进行计 算的结 果 分别 见表 1，2 在这两 个表 中，“最优解”一栏 列出了在 信 息 包 的不 同分 组 长 度(平均 包 长)时 所得 到 的 网络 最短 平均 时延，此 值越 小 表 明网络 的实 时性 越 好；“链 路利 用 率(最 大 或 平均)”则 反 映 了在 一 定 的 网络 负荷 情 况 下，对 不 同平 均包 长 产 生的 解所 对应 的 链路 利用 程 度，或者 称 为占 网率，此值越 低 则所对 应 的路 由策略越 佳 由这 两个 表可 以看 出，与 P i r k u l 所采用 的经典拉 格朗 日 松弛 和子梯度优 化方法 相 比口 ，采用 Ta b u搜 索方法，在 绝大 多数情况下，都可以得到比前者更好的结果 在网 络 规模变 大、网络拓 扑结 构更趋 复杂 的情况 下，Ta b u搜 -3 5 k b i t s s 3 3 k b i t s s 一 3 0 k b i t s s 图 3 RI NG 网 的拓 扑 结 构 索方 法 更具 有优越 性，尤其对 ARP A 网与 RI NG 网，在 F i g-3 T h e t o p o l o g y s t r u c t u r e o f R I N G 平 均 包长(分组 长度)增加 到一定程 度(即网 络吞吐 量增。大 到 一 定 规模，网络 负荷 加重)时，采 用拉 格 朗 日松 弛 和 子梯 度 方法，找 不到 可 行 解，而采 用 Ta b u搜索方法，仍 旧能够得 到次优解，这 就进 一步验证 了 Ta b u搜 索方法 的 可行 性及 高效性 由这 些结 果 可知，Ta b u搜索方法 亦 可用来 求解 容量 分配 问题 6 事实 上，路 由选 择 问题 只是 容量分配问题在链路容量固定情况下的一个特例、在同等网络负荷的情况下，链路的低利用率 必然 意 味着更好 的容 量分配策略 由前 述可 知，诸 多 因 素制 约着 TS方法 的 搜 索效果，定 量研 究与分 析这 些 因 素 各 自的影 响，对 Ta b u搜索方法 的应 用将具 有重 要的意义、因此，有 必要 对 TS方法 的各种控制 参数进行 优选、为此 本文设计 了一系 列如表 3所示 的计算机仿真 实验、在 图 4中，对 不 同初始 解的 生成方 法进行 了 比较 从 图中 可 以看 出 不 同的初 始化方 法最 终导 致了不 同的最优值，而 且分组长 度越 大，即网络 负荷越重，这 种 差距 越 明显 但不管 网络负 裹 1 AR P A 阿 的计 算机 仿真 实 验 结果 Tab l e 1 The e xp er i men 柚 r e su I l s o f c0 m pat e r s i m ul a t l oa f or t he ARPA ac t wor k 维普资讯 http:/ 兰 州 大 学 学 拉(自 然 科 学 版)第 3 7卷 表 2 RI NG 网的 计 算机 仿真 实 验结 果 Ta bl e 2 The exp er i ment al r e s ul t s of c ompur si m ul at i on f or t he RI N G net wo rk 韧始 化方 法 郫蛾 擅索 策略 T a b u表的规模 有无 启发 式改 进 最 短 路 由法 最 步跳 数法 随 机路 由法，最长路 由法 最优 法，最先 法 抽 样法 7 有，无 平均包长 A R P A 5 1。0 】l 2 1 l 3 2 5 1 。l 5。Rl NG：5 0 1 6 0 1 6 1 1 6 2 2 00 2 50 3 00 3 25 3 50 37 5+40 0+4 25 荷 如何，“最 短路 由法 及“最少跳 数法”都 能够产生 更优 的结果，且 二者 差 别很 小 事实 上，“最 少 跳 数法 意 味 着最少 的链路数，也 意 味着在同等情 况 下，各节 点对 的路 由所 对应 的通信 需 求 被 累加 至各链 路(该 路 由必须 经 过此 链路)上 的次 数也 减 少，那 么从 全 阿 的角 度来考 虑，各 链 路 的实 际通 信量 也较少，由公 式(2)可 知，整个 网络 的 时延 减 少 在绝 大 多 数 情况 下，最少 的跳 数也 意 味 着最 短 的距 离，反之 亦 然 周此，在应用 Ts方法求解路由选 择问题时，初始化 方 法 应 采 用 差别 非常 小 的“最少 跳 数法 或“最 短 路 由 法”图 5，6给 出 了 3种邻域 搜索 策 略的 比较 正如在 前 面 所预 料的 那 样，“最优 法”获 得 了 最 好 的结 果；“采 样 法 的效 果接近 于“最优法”；“最先 法 的搜索效果 最差；网络 的负荷 越重，三 者之 间 的 差别越 明显 由图 6还 可 以看 出，在这 3种邻 域 搜索 方 法 中，“最 优 法”所 需 要 的 图 4 不 同 初始 化 方法 的 搜 索结 果 F i g 4 Th e s e a r c h r e s u l t s b y d i f f e r e n t n i t i a l i z e d me t h o d s 搜 索 时间也最 多 因此，在 实际应用 中，除 了当所求 问题 的实时性要 求 不高 时而 采用“最 优 法 之外，在一般情况 下，则 应采用“采 样法 维普资讯 http:/ 第 2期 许 福永 等：基 于现 代超 启 发式 搜 索 方 法的计 算机 通信 网路 中路 由选择 优 化 的研 究 6 9 E 图 5 3种 邻域 搜索 策略 的效 果 比较 Fi g 5 The e f f e c t c o mp a r i s o n f o r t hr e e n e i g hb o r h o o d s e a r c h s t r a t e g i e s 厘 营 脯 平 均包 长 b i t s 图 6 3种邻 域 搜索 策略 的搜 索 时 间 比较 Fi g 6 The c o m p a r i s o n o f s e a r c h t i me f o r t h r e e n e i g h b o r h o o d s e a r c h s t r a t e g i e s 图 7表 示不 同 Ta b u表 规模 的对 比结果 很 明显 在各 种 网络 负荷 的情 况 下，这 二者 的差 别 都 非常 小 尽 管增大 Ta b u表 的规 模能够 在 一定程度 上提高 搜 索的广 泛性，但 对 搜索 结果 的 改 进 不是 很大 因此，在 实际应用 中，Ta b u表 的规模，仍旧取 Gl o v e r所建议 的 7即可 E 、苔 露 平 均 包 长，b t ta 图 7 不 同 Ta b u表 规 模 对搜 索结 果 的影 响 Fi g 7 Th e e f f e c t s o n s e ar c h r e s ul t s o f d i f f e r e n t Ta b u l i s t s i z e s 目 、黜 曾 日 图 8启发 式搜 索 改进 的效 果 Fi g 8 Th e i m p r ov e d e f f e c t b y h e u r i s t i c s e a r c h 在一般 情况 下，Ta b u搜 索的输 出可 以直接 作 为最优或 次优 解 来使用，也可 以 用其 它 的启 发式 方法对 其改进，从而 进 一步 提高解 的质量 其具体 作法 是：对 于 Ta b u搜 索 的输 出结果 从 中找 出负荷最重 的 一条链 路，将 经过这 条链 路 的某些路 由进 行 调整，并 移出此 链 路，从 而使得 整个 网络 的负荷 比较均 匀，进而 获 得更 好 的解 图 8给 出 了这 种 改进 的计 算 机仿 真 的 实验结 果 从 图 中可 以看 出，随 着网络负荷 的加重，经过改 进可 以较 大幅度 地提高解 的质量 4结 束 语 采用一种新的超启发式搜索方法T s方法，对计算机通 信网络的路由选择问题进行了 计算和优化，得到了优于传统方法的一系列结果，为计算机通信网络的性能优化问题，提供了 一种 新的思路 和方法；本 文 的研 究结 果，对于计 算机通 信 网络 以及 电信 网、电力 网、交通 运输 网 等，在其性 能优化 与评价、提 高 网络性 能与效 益、降低其建设 和运营 费用等方 面 具 有重 要 的理 论意 义和广 阔的应用前 景 维普资讯 http:/ 7 0 兰 州 大 学 学 报(自 然 科 学 版)第 3 7卷 1 2 3 4 参考文献 Ga r i s h B Ha n t l e r S I An a l g o r i t h m f o r o p t i ma l r o u t e s e l e c t i o n i n S NA n e t wo r k s J I E EE Tr a n s a c t i o n s o n Co m mu n i c a t i o n s 1 9 8 3 3 1(1 0)：1 1 5 4 1 1 61 Na r a r s i mh a n S Ro u t e s e l e c t i o n i n b a c k b o n e d a t a c o mmu n i c a t i o n n e t wo r k s口 Co mp u t e r Ne t w o r k s a n d I S DN S y s t e mst 1 9 8 8，(1 5)：1 2 1 1 3 3 P i r k u l H，Ami r i A R o u t i n g i n p a c k e t s w i t c h e d c o mmu n i c a t i o n n e t wo r k s J Co mp u t e r C o mmu n i c a t i o n s，1 9 9 4，1 7(5)：3 O 7 3 1 6 G a v i s h B Ne u ma n I A s y s t e m f o r r o u t i n g a n d c a p a c i t y a s s i g n me n t i n c o m p u t e r c o mmun i c a t i o n n e t-wo r k s J I E E E Tr a n s a c t i o n s o n C o mmu n i c a t i o n s，1 9 8 9，3 7(4)：3 6 0 3 6 6 I s Ami r i A，P i r k u l H R o u t i n g a n d c a p a c i t y a s s i g n me n t i n b a c k b o n e e r$Op e r a t i o n s Re s e a r c h，1 9 97，2 4(3)1 2 7 5 2 8 7 n e t wo r k s J C omp u t 6 Gl o v e r F Ta b u s e a r c h par t I 口 OR S A J o u r n a l o n C o mp u t i n g，1 9 8 9，1(3)l 1 9 0 2 0 6 7 Gl o v e r F Ta b u s e arc h par t I口 OR S A J o u r n a l o x C o mp u t i n g，1 9 9 0，2(1)：4 3 2 8 L e e C Y，Ko h S J A d e s i g n o f t h e mi n i mu m c o s t r i n g c h a i n n e t wo r k wi t h d u a l h o mi n g s u r v i v a b i l i t y a t a b u s e a r c h J C o mp u t e r s Op e r a t i o n s R e s e a r c h。1 9 9 7 t 2 4(9)：8 8 3 8 9 7 S t udy on Ro ut e S e l e c t i o n Opt i m i z a t i on i n Co m put e r Co m m uni c a t i on Ne t wor ks Ba s e d o n M o de r n M e t ahe ur i s t i c Se ar c h M e t ho d Xu Fu y o n g，M e i Zh o n g l e i (S c ho o l o f I n f o r ma t i o n S c i e n c e a n d En g i n e e r i n g，La n z h o u Uni v e r s i t yLa a z ho ut 7 3 00 0 0，Ch i n a)Ab s t r a c t：I n o r d e r t o i mp r o v e p e r f o r ma n c e s o f c o mp ut e r c o mmu ni c a t i o n ne t wo r ks，t h e i m p o r t a nt r o u t e s e l e c t i o n op t i mi z a t i o n i n c o mp u t e r c o mmu n i c a t i o n n e t wo r k s i s f i r s t l y s t u di e d i n d e t a i l b y u s i n g t h e mo de r n me t a h e u r i s t i c s e a r c h m e t h od，i e，Ta b u s e a r c h，wh i c h i s o f g r e a t f l e xi b i l i t y a n d c a me i n t o u s e j u s t a f e w y e a r s a g o Be t t e r r e s u l t s a r e o b t a i n e d a n d c o rn-p a r e d wi t h t h e t r a d i t i o na l La g r a ng e a n r e l a x a t i o n a nd s u b g r a d i e n t o p t i mi z a t i o n me t h o dEs p e-c i a l l y，t h e s u p e r i o r i t y o f t h i s me t h od o v e r o t h e r a l g o r i t h ms i s f u r t h e r s ho wn i n t he c a s e o f v e r y h e a v i l y l o a d e d n e t wo r k Thu s，t h e n e w t h i nk i n g a nd me t h od ar e p r o v i de d f o r t h e o p t i-mi z a t i o n t h e o r y o f c o mp ut e r n e t wo r k s A g r e a t n u mb e r o f t h e e x p e r i me n t a l r e s u l t s s i m u l a t e d b y t h e c o mpu t e r s h o w t h a t t h e g i v e n c o n c l u s i o n s a r e o f i mp o r t a nt t h e o r e t i c a l v a l u e a n d h a v e b r o a d a p p l i c a t i o n p r o s p e c t s，n o t o nl y f o r t h e c omp ut e r c o mmu n i c a t i o n n e t wo r k s，b u t a l s o f o r t h e n e t wo r k s i n t e l e c o mmu n i c a t i o n，e l e c t r i c a l p owe r a n d t r a n s p o r t a t i o n f i e l ds，i n t h e i r p e r-f o r m a nc e o p t i mi z a t i o ns a n d e v a l u a t i o ns，a c h i e v i n g b e t t e r n e t wo r k p r o pe r t i e s a n d be ne f i c i a l r e s u l t s，a n d r e du c i n g t h e i r o p e r a t i o n c o s t s，e t c Ke y wo r d s：c o mp u t e r c o mmu n i c a t i o n n e t wo r k s；r o ut e s e l e c t i o nc o mbi n a t o r i a l o pt i mi z a t i o n h e u r i s t i c s e a r c hTa b u s e a r c h 维普资讯 http:/