一种多路径并行搜索蚁群算法求解多播路由问题

《一种多路径并行搜索蚁群算法求解多播路由问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、种多路径弗干=

2、：搜索的蚁群算法求解多播路由问题论文题目：专业：硕士生：指导老师：一种多路径并行搜索的蚁群算法求解多播路由问题计算机软件与理论谭旋张军教授摘要随着多媒体在高速网络的广泛应用，多播路由问题(MultipleDestinationRouting)已成为越来越重要的研究课题。多播路由问题可以数学上形式化成Steiner树问题，该问题的求解是需要在满足一定限制条件情况下，找出包含源节点和目标节点且开销最小的一颗多播树。在本文中，我们提出的多路径并行搜索蚁群算法MPS．ACS(MultiplePathSearchAntColonySystem)，基于

3、蚂蚁具有找到蚁巢与食物之间的最短路径的能力，在求解多播路由问题上取得了很好的效果。该算法的基本思想是：首先将多播路由问题中的网络转换成完全连通图，然后通过多条路径在连通图上并行搜索获得构成多播树所需要的节点集合，最后通过构造最小生成树将选中的节点连接起来。与其他算法相比，本文的算法具有以下优点：首先，多条路径从源节点和日标节点出发保证了每一只蚂蚁都能找到可行解；第二，引入局部搜索机制使得求解的精度大大提高；第三，大量的数值试验的结果表明，算法具有很好的求解性能，对于OR．1ibrary中给出的标准问题进行测试发现，本文提出的多路径并行搜索蚁群算法在大部分情

4、况下都能找到近似最优解，求解质量上要优于文章给出的其它一些算法。另外，多路径并行搜索蚁群算法还具有较低的计算复杂性，随着问题规模的扩大，算法仍能在可以接受的时间内找到比较好的解。文章最后给出的算法性能分析也表明，多路径并行搜索蚁群算法具有较强的鲁棒性。关键词：蚁群算法(ACS)，多播路由问题(MDR)，最小牛成树(MSl)，多路径并行搜索蚁群算法(MPS—ACS)Title：AMultiplePa仇SearchAntColonySystemfortheMultipleDestinationRoutingProblemsMajor：ComputerSoftw

5、areandTheoriesName：XuanTanSupervisor：ProfessorJunZhangABSTRACTWiththeadventofmanynewmultimediaapplicationsinhighspeednetwo咄researchonthemultipledestinationmuting(MDR)problemsbfAT,omesoneofthemostsignificantareas．MDRproblems伽bemathematicallyformulatedasfindingaminimalcosttreewhichc

6、ontainscertainnc∞鹞arypoints．IthasprovedthatMDRproblemisaNP-hardproblem，thereforeheuristicalgorithmsaxeoftenofpracticalvalue．TheproposedMultiplePathSearchAntColonySystem(MPS-ACS)inthispaper,whichisinspiredfromrealants’capabilityoffindingtheshortestpathbetweenfoodsourc圮andtheirnest,

7、bringsanewapplicationofACSinthesolvingofMDRproblems．Thebasicideaofthisalgorithmis：aftertransformingtheunderlyingnetworkofallMDRproblemintoitsdistancecompleteform,multiplepathssetoutfromthesourceanddestinationnodessothattheycansearchinparalleltoconstructasetofn优髑sarypointsforthefin

8、alsolution．Thenthepri】咀algorithmisappliedtogenerateaminimalspanningtreosoastoconnectalltheselectedpointswithminimalcosts．Theproposedalgorithmhasseveraladvantages．First,itguaranteesthatallants啪findfeasiblesolutions．Second．withthelocalsearchmethod,MPS-ACSisabletofindsolutionswithhig

9、hprecision．Experimentsonstandardp