资源描述：
《必经点最短路径模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第31卷第2期系统工程与电子技术Vol.31No.22009年2月SystemsEngineeringandElectronicsFeb.2009文章编号:10012506X(2009)0220459204必经点最短路径问题模型及相应遗传算法研究1,21徐庆征,柯熙政(1.西安理工大学自动化与信息工程学院,陕西西安710048;2.西安通信学院,陕西西安710106)摘要:根据军事运输在路径寻优方面的特殊需求,将必经点最短路径问题分为三类,建立各类问题的数学模型。以分类保序最短路径为例,设计相应的改进遗传算法。该
2、遗传算法构造了独特的适应度函数,使包含较多必经点的染色体能够优先被选择进入下一代种群。通过节点保序算子的引入,保证相关节点之间存在特定的先后次序,并提出一种新的引入必经点变异算子,提高算法的全局搜索能力,加快收敛速度。仿真结果验证了算法的有效性。关键词:遗传算法;最短路径;分类必经点;保序节点;军事运输中图分类号:TP301.6文献标志码:AModelsandgeneticalgorithmfordesignated2pointsshortestpathproblem1,21XUQing2zheng,KEXi2z
3、heng(1.FacultyofAutomationandInformationEngineering,Xi’anUniv.ofTechnology,Xi’an710048,China;2.Xi’anCommunicationInst.,Xi’an710106,China)Abstract:Onthebasisofthespecialrequirementsofmilitarytransportationinrouting,thedesignated2pointsshortestpathsproblemisdiv
4、idedintothreecategoriesandtheirmathematicsmodelsareestablished.Theimprovedgeneticalgorithmforthegroupedandorder2preservingdesignated2pointsshortestpathsproblemispresented.Thealgorithmconstructsauniquefitnessfunction,whichmakesthatachromosomewithshorterdistanc
5、eandmoredesignated2pointswouldbeselectedtorebirthintonextgenerationmoreeasily.Anorder2pre2servingoperationisproposedtoensurethatsomeparticularpointsareconnectedbasedonthedeterminedorder.Byusingnovelmutation,theglobalsearchcapabilityandconvergencespeedareimpro
6、ved.Theexperimentalre2sultsshowtheeffectivenessoftheproposedalgorithm.Keywords:geneticalgorithm;shortestpath;groupeddesignated2point;order2preservingpoint;militarytrans2portation中,必须通过的节点,比如一些重要的城市、桥梁、加油站、0引言弹药库、中转站等地点或设施。避开点是指部队在执行军最短路径问题(shortestpathproblem
7、)是一类受到普事运输任务的过程中,必须避开的节点和路段,对于避开遍重视和研究的网络优化问题,广泛应用于计算机科学、交点,可将和需要避开的节点相连接的所有路段以及需要避通工程、通信工程、系统工程、运筹学、信息论、控制理论等开的路段从网络结构图中删除掉。节点保序问题是指要求众多领域。它为研究更复杂的网络流问题提供了基础,是运输路线中的某些节点之间存在特定的先后次序,比如部解决其它许多复杂网络优化问题的子问题之一。求解最短队在通过某个指挥所节点之前,必须先到其它某个地点接[1]路径问题的经典方法是Dijkstra算法。
8、受作战命令或补充弹药。在实际应用中,为了方便指挥员军事人员及物资的运输和一般民用运输在路径寻优方的部署和决策,有时候还需要提供多条路线供指挥员选择。面的最大不同在于,军事运输必须考虑必经点、避开点和节我们称此类问题为必经点最短路径(designated2points点保序问题。必经点是指部队在执行军事运输任务的过程shortestpaths,DPSP)问题。收稿日期:20
