第37卷第3期广西大学学报：自然科学版Vo1．37No．32012年6月JournalofGuangxiUniversity：NatSciEdJune2012文章编号：1001_7445(2012)03-0588-06遗传算法在动态权值路径寻优中的应用马超，郭军(1．西北大学软件学院，陕西西安710100；2．西北大学信息科学与技术学院，陕西西安710100)摘要：为了克服传统算法在求解动态权值下最短路径问题时权值设定不合理，所得结果往往不是最优路径这一问题，提出了一种基于遗传算法的复杂路径寻优算法。遗传算法本身的随机性可以很好的避免权值设定这一步骤。为了使路径寻优算法更加可靠，该算法通过优化变异过程使得收敛速度更快，可靠性更高。将其应用在一个实际游戏模型中，实验结果表明其有效性。关键词：遗传算法；最短路径；动态权值中图分类号：TP301．6文献标识码：AApplicationofgeneticalgorithminoptimalroutingindynamicweightsystemMAChao，GUOJun(1．CollegeofSoftware，No~hwestUniversity，Xi’an710100，China；2．SchoolofInformationandTechnology，NorthwestUniversity，Xi’an710100，China)Abstract：Thetraditionalalgorithmscannotmakesuretogettheoptimalroutingindynamicweightsystemsbecauseoftheunreasonableweightsetting．Randomnessofthegeneticalgorithmiscapableofsolvingthisproblem．Anewalgorithmbasedongeneticalgorithmisproposedinthispaper．In0r．dertomaketheshortestpathsolutionmorereliable，theproposednewalgorithmgetsawaytoopti—mizetheprocessofmutationtomakethespeedofthegeneticalgorithmfasterandthereliabilitybet-ter．Theproposedalgorithmwasappliedtoanactualgamemodelandthevalidityofthealgorithmwasconfirmed．Keywords：geneticalgorithm；shortestpath；dynamicweight随着网络技术的飞速发展，最短路径(ShoaestPath，SP)¨问题已经越来越多的被应用在了各项技术中，例如：城市交通规划，网络路由，项目进度规划，游戏人工智能等。最短路径问题是图论研究中的一个经典算法，旨在寻找图中两节点之间的最短路径。传统解决最短路径问题的算法有：Dijsktra，A，SPFA，Bellman．Ford，Floyd．Warshall等。但是，人们面临的实际问题越来越复杂，传统算法求的最短路径往往并不是最优路径。例如：对于出行者选择出行线路来说，道路的质量，流量和容量等诸多因素同样影响着他们的决策，如果只是距离上微弱的优势，并不能成为路线选择的关键。近年来，在最短路径的求解中，蚁群算法J，模拟退火算法，遗传算法，神经网络等一系列新型改进算法脱颖而出，并取得了显著的成果。这些算法在解决最短路径问题时与传统算法相比，表现出了收稿日期：2012-03—19；修订日期：2012-04-21基金项目：陕西省科技攻关项目(2009k01-53)通讯联系人：郭军(1968一)，男，湖北房县人，西北大学副教授；E—mail：Masxp@163．corn。第3期马超等：遗传算法在动态权值路径寻优中的应用589更高的智能性和稳定性。在动态权值系统中，这种智能性和稳定性尤为突出。基于以上研究成果，本文提出了一种基于遗传算法的复杂路径寻优算法】。1算法设计1．1算法流程根据遗传算法的思想，将算法应用在动态权值系统的流程归纳如下：①进行初始化工作。扫描整张图，标记出图中的动态节点。所谓动态节点，是那些会对系统产生动态影响，权值不固定的节点。求出任意两个动态节点之间的绝对最短路径。这里的绝对最短路径即物理长度上的最短路径，即路径中不包括其他动态节点。②产生初始种群。算法采用随机原理在动态节点中任意挑选若干节点进行组合(允许有重