基于改进蚁群算法的旅行售货员问题研究

基于改进蚁群算法的旅行售货员问题研究

1自催化行为的应用蚂蚁算法是近年来出版并引起人们注意的一种新的模拟算法。它在一些科学领域得到了广泛应用。作为通用型随机优化方法,它吸收了昆虫王国中蚂蚁的行为特性,有时也称作蚂蚁系统(AntSystem)。生物世界中的蚂蚁在搜索食物源时,能在其走过的路径上释放一种信息激素(Pheromone),使得一定范围内的其他蚂蚁能够察觉到并影响其行为。当某些路径上通过的蚂蚁越多时,留下的信息素轨迹(Trail)也越多,以致信息素强度增大,后来的蚂蚁选择该路径的概率也越高,从而可增加该路径的信息素强度,这种选择过程被称为蚂蚁的自催化行为(AutocatalyticBehavior)。旅行售货员问题(TravellingSalesmanProblem,TSP)是优化领域中一个著名的经典难题,迄今尚未彻底解决,现已被归入NP-完备的问题类。其一般提法为:有一货物推销员欲往若干个城市推销货物,从城市1出发,经其余各城市至少一次,然后回到城市1,问选择怎样的行走路线,才能使总行程最短(各城市间距离为已知)。由于该问题在许多实际领域中有着广泛的应用,因而寻找其有效的算法就显得颇为重要。然而,这种可能性到目前为止仍属未知。虽说也有一些指数级的算法可进行精确地求解,如分支定界法、割平面法等,但随着它们在大规模问题上的失效(组合爆炸),人们不得不转向近似算法或启发式算法。Dorigo等提出蚂蚁算法时,首先用TSP进行了测试。求解开始时,蚂蚁群各自随机行动,以后则按概率选择留有信息素轨迹的尚未走过的路径,直至完成一次搜索,即构成一个解。因此,蚂蚁群成功地搜索一轮所形成的是一组解,然后记录其中的最好解,各蚂蚁所遗下的信息素轨迹也将按持久程度保留到以后各轮搜索,从而产生特有的生物行为影响。2多目标tsp解的含义多目标旅行售货员问题是经典TSP的扩展和延伸,若给定图G的各边弧上有L个权值,则使得回路上相应的L个目标值都尽可能小的解就称为这个多目标TSP的(Pareto)有效解。如实际问题中常常需要考虑:路程最短、时间最少、费用最省、风险最小等多方面的因素。由于多目标意义下的解是一种“折衷解”、“非劣解”,因此,多目标TSP解的含义可定义如下:假定有一回路解H,若不存在任何其他回路解Q,使得Zr(Q)≤Zr(H),r=1,2,…,L,其中至少有一个不等式严格成立(Zr为相应的目标函数值),则H为一个非劣解或Pareto解。记G=(V,E)为赋权图,V={1,2,…,n}为顶点集,E为边集,各顶点间的权值为dirjrj(dirj>0,diri=+∞),i,j∈V,r=1,2,…,L),并设xij={1边(i,j)在解回路上0其他于是,多目标TSP的数学模型可写成:其中,|S|为集合S中所含图G的顶点个数。前两个约束意味着对每个顶点而言,仅有一条边进和一条边出。第三个约束则保证了没有任何子回路解的产生。当dij=dji(i,j∈V)时,被称为对称问题。当对所有i,j,k∈V,有不等式dij+djk≥dik成立时,问题被称为是满足三角形不等式的,简写成ΔTSP。三角形不等式在很多情况下是自动满足的,它是TSP中的一种主要类型。个别不满足的,也可进行等价转换。3检测多目标的描述在给出多目标TSP的蚂蚁算法之前,先对有关的变量和常数说明如下:m为蚂蚁个数;ηij为边弧(i,j)在多目标意义下的能见度(visibility),即1/dirj,r=1,2,…,L(按概率选取,可体现优先级);Pikj(t)为蚂蚁k的转移概率,定义为Ρkij(t)={[τij(t)]α[ηij]β∑k∈U[τik(t)]α⋅[ηik]βj∈U0其他其中:U为可行顶点集;τij(t)为边弧(i,j)在t时刻的轨迹强度(intensity);Δτikj为蚂蚁k在相邻时刻中于边弧(i,j)上留下的单位长度迹信息素量,按Δτikj的不同取法,可形成不同类型的蚂蚁算法:(1)Δτikj={∑rQ/Ζrk(i,j)在解路径上(Ζrk为目标函数值)0其他(2)Δτikj={Q(i,j)在解路径上0其他(3)Δτikj={∑rQ/dirj(i,j)在解路径上0其他上述三种情形可分别称为多目标的蚂蚁圈(Ant-Cycle)模型、蚂蚁密度(Ant-Density)模型和蚂蚁数量(Ant-Quantity)模型。算法中所用到的参数有:α为迹的相对重要性(α≥0);β为能见度的相对重要性(β≥0);p为迹的持久性(0≤p<1),可将1-p理解为迹衰减度(evaporation);Q为体现蚂蚁所留迹数量的一个常数。从而,可将多目标TSP的蚂蚁算法步骤按伪码形式叙述如下:其中:算法中的τmax取为1/(1-ρ)Zopt;τmin取为τmax/5。如果忽略目标个数L(一般不会很大),则算法的复杂度为O(nc·m·n2)。Dorigo等对经典的TSP求解所得到的经验结果表明,当m大致等于n时,效果最佳,此时的时间复杂度为O(nc·n3)。算法对距离的对称性以及目标函数无特殊要求,因此可用于各种非对称性问题和非线性问题。上述求解多目标TSP的蚂蚁算法用Delphi4.0实现,在PC系列机的Windows98环境下运行通过。4算法的三种形式下面用一个简单例子来说明算法的使用情况以及与其他算法的比较。例已知n=6,L=2,权矩阵分别为D1=[∞81725581381∞344940723∞877721554487∞67258197767∞93340212593∞]‚D2=[∞821414434782∞617629471461∞293151147629∞786743293178∞284747516728∞]对该算例,分别运行算法的三种形式,其中,Q=1～1000,最大迭代次数=100,运行于PENTIUMⅡ/350系列微机上,得到的非劣解以及与边交换法(2-opt)、模拟退火法(SA)的比较结果如表1所示(各运行10轮)。参数的不同组合,将对算法的效果产生一定的影响。由于对多目标TSP而言,α和β过大将可能产生不合理结果,因此,比较理想的区间是在0～3,不仅可保证结果的合理性,还可加快算法的运行速度。此外,对求多目标问题的非劣解而言,迭代次数也不用像解单目标问题那样定得很大。通过上述例子以及其他许多随机数值问题的求解(试验规模算到n=150),并与边交换法和模拟退火法进行比较,可以发现,本文的多目标TSP蚂蚁算法所得结果明显优于边交换法,与模拟退火法则不相伯仲,但随着问题规模的增大,在运行效率上要好于后者。5局部搜索机制蚂蚁算法是一种来自大自然的随机搜索寻优方法,是生物界的群体启发式行为,现已陆续应用到组合优化、人工智能、通讯等多个领域。蚂蚁算法的正反馈性和协同性使其可用于分布式系统,隐含的并行性更使之具有极强的发展潜力。从数值模拟结果来看,它比目前风行一时的遗传算法、模拟退火法等有更好的适应性。将