资源描述：
《基于ga的网络最短路径多目标优化算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第24卷第7期控制与决策2009年7月Vol.24No.7ControlandDecisionJul.2009文章编号:1001-0920(2009)07-1104-06基于GA的网络最短路径多目标优化算法研究阎啸天,武穆清(北京邮电大学信息与通信工程学院,北京100876)摘要:针对现有基于遗传算法(GA)优化的网络最短路径算法存在优化目标单一、遗传编码质量低、搜索策略间平衡性差、适应度分配效率与灵活性较低等问题,建立一种多目标优化最短路径自适应GA模型.提出了优先级编码和优先级索引交叉算子,引入了遗传算子参数的模糊
2、控制机制和基于自适应加权的适应度分配方法.实验结果表明,该算法的准确性和稳定性高、复杂度合理,实现了对网络设计优化中多目标最短路径问题的高质量求解.关键词:最短路径;多目标遗传算法;优先级编码;模糊控制;优先级索引交叉中图分类号:TN967.2;TN929.5文献标识码:AResearchonmult-iobjectiveoptimizationforshortestpathalgorithmbasedonGAYANXiao-tian,WUMu-qing(SchoolofInformationandCommunicat
3、ionEngineering,BeijingUniversityofPostsandTelecommunications,Beijing100876,China.Correspondent:YANXiao-tian,E-mail:xiaotian.yan@gmail.com)Abstract:Thesinglenessoftheoptimizationobjective,poorperformanceofgeneticrepresentation,unbalancebetweensearchingstrategies,
4、andlowefficiencyoffitnessassignmentaremainproblemsoftheconventionalshortestpath(SP)geneticalgorithms(GA).Therefore,anadaptiveSPmult-iobjective(MO)GAisproposed.Priority-basedgeneticencodingandpriority-indexedcrossoverareintroduced.Fuzzylogicbasedgeneticoperatorad
5、aptationandadaptiveweightfitnessassignmentmethodsaredesigned.SimulationsofthemodelbasedonvariousscaleofnetworkseffectivelyshowthatthehighrequirementofSPproblemiswellfulfilledwithhighaccuracyandstabilityoftheproposedMOGA.Keywords:Shortestpath;Mult-iobjectiveGA;Pr
6、iorityencoding;Fuzzycontrol;Priorityindexedcrossover1引言分配机制的效率与灵活性较低等缺点,使得该算法[2,3,5]最短路径问题模型是网络设计优化中最基础及的多目标优化性能受到较大影响.[1]本文基于最小费用和最小时延等优化目标,建核心的模型之一,被广泛应用于通信网路由、智能交通规划、配电网重构、项目运筹管理等领域,是影立了网络多目标最短路径的自适应遗传算法模型.[1-4]响网络设计优化性能的关键技术.满足各种路径以优先级编码替代传统定长、变长表达方式,并相应权重约束
7、条件的网络最短路径问题可以归结为多目设计了优先级索引交叉算子,有效提高了遗传编码[1,2]标组合优化NP-Hard问题.针对这类问题,传统与交叉算子的质量;应用模糊系统理论,依据父子两基于图搜索策略的算法通常无法在多项式时间内完代种群间平均适应度的变化量,引入对遗传算子参[4-6]成求解;当前较为常用的是基于软计算理论的方数进行模糊逻辑控制的自适应机制,有效改善了搜法.其中,遗传算法相比神经网络具有更高的灵活索策略间的平衡;综合与改进了基于Pareto等级与[1,2]性,更适用于多目标优化问题的求解.现有基于加权和的传
8、统方法,通过引入自适应加权机制有效遗传算法的网络多目标最短路径算法模型存在优化改善了适应度分配的性能.仿真实验结果表明,该模目标单一,染色体编码的可行性、继承性与位置相关型不仅精度较高,而且性能稳定、计算复杂度合理,性不足,搜索范围与搜索强度间的平衡性差,适应度实现了网络多目标最短路径的可靠求解.收稿日期:2008-08-28;修
