求解动态最优路径的混合优化算法.doc

·· 通信学报 第29卷
第7期 王江晴等：求解动态最优路径的混合优化算法 ··

第29卷第7期 通信学报 Vol.29No.7
2008年7月 JournalonCommunications July2008

求解动态最优路径的混合优化算法
王江晴,覃俊,李子茂
(中南民族大学计算机科学学院，湖北武汉430074)
摘要：对动态网络环境下动态需求的最优路径搜索问题进行了研究，首次提出了一个能同时利用演化算法的全局优化能力和蚁群算法的局部探索能力的混合智能优化算法Evo-Ant，并将其应用于DVRP。为了验证算法的有效性，给出了DVRP的混合整数规划模型，建立了DVRP的动态性能测试类，并进行了大量的仿真实验和比较。结果表明，Evo-Ant算法能够根据实时接收到的信息对当前规划路径进行及时调整，具有明显改善的性能优势。
关键词：动态网络；路由问题；演化算法；蚁群算法
中图分类号：TP301.6文献标识码：A文章编号：1000-436X(2008)07-0135-06
Hybridoptimizationalgorithmforroutingproblemindynamicnetworks
WANGJiang-qing,QINJun,LIZi-mao
(CollegeofComputerScience,South-CentralUniversityforNationalities,Wuhan430074,China)
Abstract:Aroutingproblemwasinvestigatedwherebothdynamicnetworkenvironmentandreal-timecustomerrequestswereconsidered,ahybridoptimizationalgorithmcalledEvo-Antwasproposed.Theadvantageofthealgorithmisthatitincorporatesantcolonyalgorithmforexplorationandevolutionaryalgorithmforexploitation,andusesreal-timeinformationduringtheoptimizationprocess.Inordertodiscusstheperformanceoftheproposedalgorithm,amixedintegralprogrammingmodelfordynamicvehicleroutingproblemwasformulated,andbenchmarkfunctionswereconstructed.Theperformanceofthealgorithmisevaluatedbycomparingitsresultswithsomeexactalgorithmsandheuristicalgorithmsforrandomlygeneratedtestproblems.Theresultsshowthattheproposedalgorithmcanachieveahigherperformancegain,andiswellsuitedtoproblemscontainingdynamicnetworkenvironmentandreal-timecustomerrequests.
Keywords:dynamicnetwork;routingproblem;evolutionaryalgorithm;antcolonyalgorithm

1引言
收稿日期：2008-01-07；修回日期：2008-06-02
基金项目：国家自然科学基金资助项目（60603008）
FoundationItem:TheNationalNaturalScienceFoundationofChina(60603008)
最优路径搜索主要研究如何在网络中寻找能够同时满足多个约束条件，且具有最小代价的路径。这类问题在QoS路由、车辆调度等领域中有着广泛的应用。在实际的网络中，最优路径搜索问题分为2种：基于静态信息的路径搜索和基于动态信息的路径搜索[1]。由于更加贴近实际应用的需求，近年来对动态问题的研究引起了计算机等领域专家学者的广泛关注[2~4]。动态最优路径问题属于NP完全问题，目前一般采用现代启发式算法求解，如演化算法[5~7]和蚁群算法[8~10]等。
演化算法从模拟自然界的生物演化过程入手，以解决智能系统如何从环境中进行学习的问题。演化算法的特点是具有隐含并行性，擅长求解全局最优问题，但算法的局部搜索能力较差，求解精确度较低。蚁群算法也是一种源于自然界的仿生类算法，它模拟昆虫王国中蚂蚁的行为机制，是一种依照蚂蚁觅食原理