求解旅行商问题的混合蚂蚁算法.doc

求解旅行商问题的混合蚂蚁算法11,2陈文兰,戴树贵(,安徽滁州239000;),上海200062摘要:旅行商问题是一个经典的NP问题,文中给出了一个有效的求解旅行商问题的混合蚂蚁算法。算法设计了初始信息素量设置方案和信息素的更新方法,限制了蚂蚁转移的目标城市数,并使用2-Opt方法对路径进行优化。数据实验表明,该算法是有效的。关键词:旅行商问题;蚂蚁算法;2-Opt;局部优化()文章编号:1673-629X200707-0110-04中图分类号:TP18;:AAHybridAntColonyAlgorithmforSolvingTravelingSalesmanProblem11,2CHENWen2lan,DAIShu2gui(,ChuzhouUniversity,Chuzhou239000,China;),EastChinaUniversity,Shanghai200062,China()Abstract:AnefficienthybridantcolonyalgorithmisproposedfortheclassicalNP-hardproblem—’stransfer,andtheroutesareoptimizedby2-:travelingsalesmanproblem;antcolonyalgorithm;2-Optmethod;localoptimization1TSP的数学模型0引言()Travelin旅行商问题gSalesmanProblem,TSP是经典TSP可以描述为:有N个城市,一个旅行商一个经典的组合优化问题,在交通运输、电路板线路设从某个城市出发,遍历所有城市后回到出发点,求一条计以及物流配送等领域有着广泛的应用。由于该问题经过所有城市仅一次的最短遍历路径。从图论的角度的可行解是所有顶点的全排列,随着顶点数的增加,会来看,该问题实质是在一个带权完全无向图中,找一个产生组合爆炸,它是一个NP完全问题。早期的研究(权值最小的Hamilton回路。其精确描述为:G=V,者使用精确算法求解该问题,常用的方法包括:分枝定)E为一个带权图,V={1,2,,N}为顶点集,E=123界法、线性规划法和动态规划法等。但是,随着()({e=i,j|i,j?V,i?j}为边集。di,j?V,ijij问题规模的增大,精确算法将变得无能为力,因此,在)i?j为顶点i到顶点j的距离,其中d>0且d?ijij后来的研究中,国内外学者重点使用近似算法或启发(()?,同时=di,j?V,则经典TSPClassicaldijji式算法,主要有遗传算法、蚁群算法、模拟退火算法和)TSP的数学模型为:4,6禁忌搜索算法等。文中首先介绍TSP的模型,然)(minF=1d×xijij6i?j后构造了一个求解TSP的蚂蚁算法,最后通过数据实1,边e在最优路径上ij验讨论了算法的有效性和参数设置对算法性能的影)(=ij0,边e不在最优路径上响。ij=1,i?V()x3ij6i?j收稿日期:2006-10-14)(=1,j?V4xij()基金项目:安徽高校省级自然科学基金2006KJ253B,2006KJ085B6i?j()作者简介:陈文兰1972-,女,浙江绍兴人,硕士,讲师,研究方向()=|S|,S为G的子图x5ij6为软件与算法;戴树贵,博士研究生,副教授,研究方向为软件与算i,j?S()法、高级物流。其中|S|为图S的顶点数。式1为目标函数,求经过()()()所有顶点的回路的最小距离。式2,4限定回路上2在所有蚂蚁完成一次遍历后,更新路径上的()每个顶点仅有一条入边和一条出边。式5限定在回信息素时,通常采用以下三种方式:?蚂蚁所经过路(路中不出现子回路。径的每条边上的信息素加上信息素总量Q/L路径k)长度;?蚂蚁所经过路径上的每条边上的信息素加()上Q/d边的长度;?每条边上信息素均加上Q。其ij求解TSP蚂蚁算法2中:?只考虑了路径长度,没考虑到每条边在路径中蚂蚁算法是根据蚂蚁