Egyptian Informatics Journal（2010）11，75开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com原创文章求网络中k条最短路的艾哈迈德·尤尼斯·哈米德埃及Sohag大学理学院计算机科学系收稿日期：2010年4月27日;接受日期：2010年2010年10月28日在线提供摘要在多媒体应用中，大多数应用都要求在单个源和多个目的地之间的通信中有k条最短路径。这个问题被称为多媒体多播路由，并已被证明是NP完全的。本文提出了一种遗传算法来确定从单个源节点到多个目的节点的具有带宽约束的k条最短路径。该算法利用给定网络的连接矩阵和链路的带宽来获得k条最短路径。最后通过实例说明了该算法的有效性.©2010计算机和信息学院，开罗大学。由爱思唯尔公司制作和主持All rights reserved.1. 介绍k条最短路问题在其它网络优化问题中有着广泛的应用。其中之一是受限最短路径，其中搜索验证指定条件的最短路径。本研究将尝试应用遗传演算法来解决这个问题的基础上，一个真实的世界系统这是基于找到最短路径的类比（即，最短的可能带宽）（假设网络中的每个边具有带宽值）。因此，应用遗传算法是一个有趣的想法。这显然不同于传统算法，传统算法试图比较每种可能性以找到最佳解决方案，这可能非常耗时包含大量节点的网络的算法电子邮件地址：a_y_hamed@yahoo.com1110-8665© 2010 开 罗 大 学 计 算 机 和 信 息 学 院 。 制 作 和 主 办Elsevier B.V.保留所有权利。开罗大学计算机和信息系负责同行审查。doi：10.1016/j.eij.2010.10.004制作和主办：Elsevier和边缘。许多文献研究k条最短路径的算法[1Yen[20]引用了几篇关于这个主题的论文，可以追溯到1957年。我们必须区分这个问题的几种常见的变体。在上面引用的许多论文中，路径被限制为简单的，即，没有顶点可以被重复。几篇论文[5，18]考虑了允许重复顶点的k最短路径问题的版本，我们也研究了这个版本。本文将尝试应用遗传算法来解决基于网络链路带宽的k条本文件的结构如下关键词计算机网络;最短路径;遗传算法;多媒体76A.Y. Hamedn0的niNJnk........nmD图1染色体形式（其中n i，n j，n k，.. . ..切割点父母1n0的niNJ nk........nmD亲本2n0的niNJ nk........nmD图2交叉操作。图5结果见表1。n0的niNJnk........nmDn0的niNJnl........nmD图3突变操作。图4示例网络。第2节：第2节介绍了问题描述以及如何解决问题。第三节介绍了遗传算法及其算子.所提出的算法在第4节中给出。第5节介绍了实验结果，并显示所获得的结果。2. 问题描述网 络 通 常 表 示 为 加 权 有 向 图 ， G= （ N， E） ， 其 中N={1，. ，n}表示节点的集合，并且E ={e1，. 表示连接节点的通信链路的集合。设M={n0，u1，u2，.. . ，um}N是从源节点到目的节点的集合，其中n0是源节点，节点和U={u1，u2，. .， um}表示目的地节点的集合。P（n0，u i）是从源节点n0到目的节点u i∈ U的路径。路径P是最短路径，如果该路径的带宽path等于常数值B（该值由用户确定或者是带宽的所需值）。P的带宽（Band（P））是P中链路带宽（Band（e））的最小值. 也就是说，带P的最小值带E的最小值e2 EP因此，带宽受限k最短路径的问题是找到从源节点到每个目的地节点的所有路径，这些路径满足：带P-P-P-B：3. 提出的遗传算法遗传算法作为一种功能强大、应用广泛的随机搜索和优化技术，115213101215531284121067109912孩子...n0的 niNJ nk........nmD表1用遗传算法求出k条最短路径k Band（P）41287645101341015641012413156782410515413124651012876510134651071342876101346710124671012871215671015642871081564286101 3 4 2 81013467810156781012815124678108求网络中k条最短路的遗传算法7700111000001100111111010011000010110011100000100011110001001001100010100000110110001100110001011110010001110111100111011010101100010000101100000110100110110010101000001110010111011101100000100001110000110001110100111010001011001010010101000100100111111111110000001000011100100110100101110101101010101011100101100100010000110110100100000000111100100010000111010001000110010011000100图6网络的连接矩阵（20个节点）。00000000013008139000000800790000013000151316100097000301200091500814000001338010131100016014100090001012013004130000011940031000006092000157601113091001406000130092125004001620602013012930502129100050151103616201100838002000910200073001309130001232004139109130010001001200000169001509235071420000601265156065001101101220000110120001117050110301401130000107000511201405070500170000000000012780006100003306821006002200071103000090811300000000601210070080000056500600图7给定网络的带宽值。表2N代时的k条每个目的节点的N代k条最短路径91112141617192010003211311110,00013818519153920,000181524122920101330,0002418281731227980,000312738293932141990,0003334343045341818120,0003528363445321624140,0003830403350322019180,0003934413653352021200,0004038453754352326今天广为人知的进化计算方法。一般来说，遗传算法有以下五个基本组成部分：（1）编码方法，它是程序解的遗传表示（基因型）。(2)一种创建染色体初始种群的方法。(3)目标函数。(4)在繁殖过程中改变后代遗传组成的遗传算子（交叉和变异）。3.1. 编码方法给定一个有N个节点的网络G（N，E），E是连接节点的通信链路的集合。此外，我们考虑源节点n0和目的地节点集合U={u1，u2. ，um}。染色体可以由长度为N的整数串表示。染色体的基因是源节点n0和目的节点ui之间的节点。每个0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 078A.Y. Hamed算法：遗传算法寻找k条最短路径输入：pop_size，maxgen，Pm，Pc，n0，目的节点U，B。输出量：1. 按照第3.2节生成初始种群2. gen< $1.3. While（gen<= maxgen）do4. P<$15. While（p<=pop_size）do6. 获得新群体的染色体，根据Pc值从亲本群体中选出两条染色体.应用交叉，然后根据Pm参数对新的子节点进行变异.7. 根据等式（1）计算新孩子的带宽（Band（P））。（一）.8. 如果B（P）PB，则将此子项保存为候选解。9.P<$p+1。10. End if11.端12.打印所有获得的溶液。13.端图8N代的k条显然，染色体表示k最短路径问题的候选解，因为它保证源节点和任何目的地节点之间3.2. 初始种群根据以下步骤生成初始种群：1. 初始群体中的染色体x可以以如图1所示的形式产生。1.一、2. 如果步骤1中生成的染色体不满足2-连通性条件，则丢弃它并转到步骤1。3. 重复步骤1至2以生成染色体的pop_size数量。3.3. 目标函数目标函数是找到从源节点到目的节点的最短路径，带P的最小值带E的最小值e2 EPP B3.4. 交叉操作交叉操作由一个切割点执行。在所提出的方法中，交叉操作将执行，如果验证了交叉比（PcPc的值为0.9。切割点是随机选择的。通过交叉操作产生的后代如图所示. 二、3.5. 变异操作变异操作是在逐位的基础上执行的。在所提出的方法中，如果变异率（Pm）被验证，则执行变异操作。该方法中的突变率Pm随机选择突变位。突变产生的后代如图所示。3.第三章。4. 该算法本节介绍了建议的遗传算法解决k最短路径问题。该算法的步骤如下：5. 实验结果在本节中，我们通过将上述算法应用于如下两个示例来5.1. 第一示例我们考虑一个有8个节点的网络，如图4所示。每条链路都有相应的带宽。该算法中的参数设置为：pop_size= 20，Pm=0.2，Pc=0.9，maxgen= 600。源节点n0是节点No.1，目的节点是U= 0。{4，5，7，8}，B的目标值等于10（图）。 5）。表3变异对k条最短路径的影响。每个目的节点的变异率Pm k9111214161719200.9221930182923490.7141523152317490.5981651510160.3789101011110.143614714求网络中k条最短路的遗传算法79图9研究突变概率的影响表1中示出了由所提出的遗传算法获得的k条最短路径。这些结果表明，所提出的算法是寻找从一个单一的源节点到多个目的地节点的任何给定的网络拓扑结构的带宽约束的k条下图表示表1中给出的结果。5.2. 二示例我们考虑另一个具有20个节点的示例。该示例的连接矩阵如图6所示。每个链路的相应带宽如图所示。第七章该算法的参数设置为：pop_size = 25， PmP0.1，Pc=0.9，maxgen= 2000000.源节点n0是节点No.1，目的节点是U= 0。{9，11，12，14，16，17，19，20}，B的目标值为等于10。表2中示出了N代处的每个目的地节点的k条最短路径。图 8表示表2中给出的结果。表3和图9显示了改变突变概率的效果。从上表可以清楚地看出，在所提出的算法中，当变异率降低时，k条最短路径减少6. 结论本文提出了一种遗传算法来确定从单个源节点到多个目的节点的具有带宽约束的k条最短路径。该算法使用给定网络的连接矩阵，以获得k条最短路径。 所提出的遗传算法已被应用于两个例子的网络拓扑结构和所产生的结果是由较少的代数。该算法被认为是第一个使用遗传算法来获得从单个源节点到多个目的地节点的k条引用[1] 用矩阵方法确定第k条最短路径. Szigma 1977;10：61[2] Brander AW，Sinclair MC. k-最短路径算法的比较研究。在：Proc.11th UK Performance Engineering Workshop for Computerand Telecommunications Systems; Sep-oln 1995。[3] Carraresi P，Sodini C.一个二叉枚举树，找到K条最短路径 。 In ： Proc. 第 七 届 研 讨 会 运 筹 学 p. 177 比 88Athenéaum/Hain/Ha nstein，MethodsOper. Res. 第四十五章.[4] Consiglio A，Pecorella A.利用模拟退火算法求解K-最短路问题。见：Proc. conf. Italian assoc.运筹学; 1995年9月。[5] 福 克 斯 湾 K 次 最 短 路 及 其 在 概 率 网 络 中 的 应 用 . 载 于 ：ORSA/TIMS联合全国会议，第23卷; 1975年。p. B263[6] 霍恩GJ。在无环活动网络中寻找K条最小成本路径。J OperRes Soc 1980;31：443[7] Katoh N，Ibaraki T，Mine H.求非负弧长无向图中K条最短简单路的一个O.Kn2/算法电子通信工程学报1978;E61：971[8] Katoh N，Ibaraki T，Mine H.一个求K条最短简单路径的有效算法网络1982;12（4）：411[9] Kumar N，Ghosh RK. 求第一个K的最短路径。Comput Sci Inform 1994;24（3）：21[10] 雷扎扎德·劳在非负权重下计算K-最短路径.在：Proc.22ndManitobaConf.NumericalMathematicsandComputing ，Congr.Numer.，第92卷; 1993年。第277- 280页。[11] 劳勒图中k条最短路的计算Commun Asphalt Comput Mach1977;20：603[12] 米涅卡湖第K个最短路径问题.载于：ORSA/TIMS联合国家会议，第二卷。23; 1975年。p. B/116。[13] 佩尔科河K条最短无环路径算法的实现。网络1986;16：149[14] 鲁珀特E.并行计算k条最短路径。In：Proc. 14th symp. 计算机科学的理论方面;1997年2月[15] 涩谷湾通过人工智能搜索技术寻找k条最短路径。合作研究模型算法1995;7（77）：212[16] Shier DR. 在网 络中寻找k 条 最短 路径的算 法。 参加：ORSA/TIMS联合全国会议; 1976年。p. 一百一十五[17] 施尔博士确定网络中k条最短路径的迭代方法Networks1976;6（3）：205[18] Shier 博 士 ， 《 关 于 网 络 中 k 条 最 短 路 径 的 算 法 》 （ OnAlgorithms for Finding thek Shortest Pathways in a Network）。网络1979;9（3）：195[19] Weigand MM.一种求解第k条最佳路径问题的新算法.计算机1976;16：139[20] 颜智英另一种寻找K条最短环路较少的网络路径的算法。In：Proc. 41st mtg.美国运筹学学会，第20卷; 1972年。p. B/185。
我的内容管理
展开
