粒子群优化的多群蚂蚁算法

喻学才，张田文

(1.哈尔滨工业大学计算机科学与技术学院，哈尔滨 150001，yuxuecai@zjnu.cn;2.浙江师范大学交通学院，浙江金华 321004)

粒子群优化的多群蚂蚁算法

喻学才1，2，张田文1

(1.哈尔滨工业大学计算机科学与技术学院，哈尔滨 150001，yuxuecai@zjnu.cn;2.浙江师范大学交通学院，浙江金华 321004)

设计多蚁群算法的关键是群间的信息交换规则.利用粒子群优化中粒子移动的基本思想研究了蚁群间信息交换的新规则，定义了新的多蚁群优化算法.新算法的信息交换所占用的数据通信量要远低于现有的信息交换方法.将新算法用于求解带时间窗的车辆路由问题并和以前的最好的多蚁群算法做比较，计算结果表明:新算法的性能超过了已有的方法.采用群体智能中个体的移动思想来设计群间信息交换规则能改进多蚁群算法的求解性能.

蚁群优化;粒子群优化;带时间窗的车辆路由问题

蚁群优化(Ant Colony Optimization，ACO)是一种广泛应用于各种困难组合优化问题求解的元启发式方法［1］.将蚁群分成若干组能改进ACO的求解能力，且更易于实现并行化［2－4］.多群 ACO算法的分组关键技术是蚁群组间的信息交换规则的设计.本文将粒子群优化(Particle swarm optimization，PSO)［5］中的粒子移动的基本思想引入多群蚁群算法中群之间的信息交换，从而开发出新的多群蚁群算法.

1 带时间窗约束的车辆路由问题

2 VRPTW的单群ACO算法

蚁群的每只蚂蚁k构造VRPTW的一个可行解.首先，蚂蚁k从中心仓库0出发，选择满足问题所有约束的客户作为下一个服务的对象.如此反复进行，直到一辆车h没有可服务的客户为止.如果还有客户没有被任何一辆车服务，则蚂蚁k新增加一辆车，重复上述的构造过程，直到所有的客户都恰好被一辆车提供了一次运输服务为止.设蚂蚁k当前服务的客服为i，则根据规则概率地选择从未被任何一辆车服务的客户j作为下一个服务对象.

式中:pkij(t)为蚂蚁k在迭代步t服务完客户i之后选择客户j为下一个服务对象的概率.Tk(t)为蚂蚁k在迭代步t正在构建的部分解，J(Tk(t))为该部分解仍未提供服务的客户的集合.τij∈τ为顶点i与顶点j的连接边eij对应的信息素值.由于蚂蚁经过边eij时，会对其对应的信息素值进行局部更新，所以蚂蚁k在迭代步t时边eij对应的信息素值τij会变化.ηij为顶点i与顶点j的连接边eij的启发式信息.设Wij=Ckj－(Cki+si)为到达客户j与服务完客户i之间的时间差，Uij=lj－(Cki+si)为客户j要求服务的紧迫性，则信息素值ηij定义为ηij=1/(WijUij)注意到Cki是一个与蚂蚁k正构造的部分解相关的变量.这个定义实际上是说时间差越小，紧迫性越高的客户应该被优先服务.q~为一个［ 0，1］区间上均匀分布的随机数，q~0为式(1)中平衡使用与探索的选择阈值.

蚂蚁k选择顶点j加入到其当前构造的部分解Tk(t)后，对信息素值τkij(t)进行局部更新.

式中:ρ为信息素值的减少率，τ0为信息素的初始值.信息素的初始值与VRPTW实例的最近邻算法(Nearest-Neighbor Algorithm)最优解的代价相关即τ0=1/(n×fc(TNN)).

一个解的代价:

式中:L为所有车辆行程之和，Cf为一个大到足以偏置两个目标函数值的数.

当所有的蚂蚁构造了一个可行解后，利用从算法开始搜索到的最优解Tg对信息素矩阵进行全局更新.更新规则为

式中:Δτ=1/fc(Tg).注意到fc(Tg)≤fc(TNN)，所以Δτ＞τ0.

一个蚁群求解VRPTW的算法描述为:

算法1 求解VRPTW的单ACO算法(Vrptw-sAco).

输入 实例:位置，时间窗，服务时间，需求量，车辆容量，最大迭代步Nt，蚂蚁数Na，q0

输出 搜索到的实例的最优解Tg

S1计算顶点间距离;

S2根据ηij用最近邻(Near-Neighbor)算法求TNN;

3 VRPTW的多群ACO算法

多群ACO求解VRPTW实例是在单群算法的基础上直接构建的.具体地说，每个蚁群仍像单群一样求解VRPTW，然后每隔一定的迭代步数之后，群间交换积累的搜索信息.不同的多群ACO算法的区别在于群之间交换信息的差别.本文构造的多群ACO算法即将PSO中位置点移动的思想应用于群间信息的交换.

算法2 求解VRPTW的多群ACO算法(Vrptw－DAco).

输入 实例:位置，时间窗，服务时间，需求量，车辆容量，最大迭代步Nt，蚂蚁数Na，q0，群数Nc.

输出 搜索到的实例的最优解Tg

最优解更新信息素矩阵的规则为

将PSO中粒子移动的基本思想引入群之间的信息交换可以设计一种新颖的交换信息模块，即称之为EXHGPSO.将多蚁群中的群对应为PSO中的粒子，根据文献［2］，EXHGPSO的目的就是使群搜索向自算法开始的最好解Tg和群自己的最好解Tbh移动.为此需要使用两个最好解Tg和Tbh更新群h的信息素.给每个最优解向信息素矩阵更新的增加值加以权衡→—εbh，其维数等于对应解Tbh的长度，每个分量ωj～U( 0，1).更新规则为

从数据通信量的角度看，两种信息交换模块中，一般情况下，EXHGPSO占用的通信资源较少.蚁群之间要交换信息:1)需要将各个群的最好解的代价发送到某个群;2)比较其大小;3)根据交换规则，由某些群向另一些群发送最好解的信息.就EXHGIB而言，注意到在相同的迭代步，各个蚁群构造的解的代价不会相差太远，可以假设最好解代价低于平均代价的解为蚁群数的一半.这样，平均而言，有Nc/2的蚁群会向除自身外的每个群发送其最好解的信息.整体看，解信息的发送次数为Nc(Nc－1)/2.除了解信息外，EXHGIB还需要发送每个群最好解相应的更新信息素权重，但与发送解相比，通信量则小了许多，可以忽略不计.再看EXHGPSO，在知道拥有最低代价的最好解的群之后，只需该群向其它每个群发送最好解的信息即可.整体看，发送次数为Nc－1.所以EXHGPSO在并行运行时具有很大的优势，特别是在问题规模很大，解长度很长的情况下更适用.

从信息素更新的复杂性来看，EXHGPSO交换模块下的每个群需要两个解更新;而EXHGIB平均需要Nc/2个.所以EXHGPSO交换模块下的每个群更新信息素模块的计算量最低.

4 试验

为了比较两种交换模块下的多蚁群算法求解VRPTW问题的性能，用C++语言实现了这些算法并在Solomon标准测试算例上执行.

表1报告每个小组的平均车辆数、平均路由长度和群间信息交换耗用的时间.试验参数设置为:β = 2，ρ=0. 1，~q0=0.9.每群蚂蚁数为 10，群数为8.最大迭代步数为1 500.这些参数是根据大量试验结果进行设置，也有可能存在更好的设置.每个单群算法在局域网的一个节点上运行，局域网的实际平均带宽为83.6 Mbps.

表1显示，两种信息交换模块EXHGIB和EXHGPSO下的多蚁群算法求解主目标函数的能力在大多数算例组上相同，仅在组R上基于EXHGPSO模块的多蚁群算法稍有优势.另一方面，基于模块EXHGIB的多蚁群算法求解次目标函数的优化能力所有算例组上比新算法有较为明显的优势.但是，当与局部优化结合时，新算法求解次目标函数能力比较弱的问题能得到充分的解决.再考虑到EXHGPSO比EXHGIB少得多的信息交换量(从表1中的时间上可知，EXHGIB用于信息交换耗用的时间比EXHGPSO要大一个数量级)，基于EXHGPSO设计多群蚁群优化应该是一个好的选择.

表1 两种多群ACO求解VRPTW的性能比较

5 结论

1)引入粒子群优化(PSO)中粒子移动的思想到多蚁群算法的群间信息交换设计中，得到了新的多蚁群算法.

2)新算法的交换数据量远低于目前的方法.而且在带时间窗约束的车辆路由问题上的计算结果显示，新方法的求解性能优于原来的方法.

［1］DORIGO M，MANIEZZO V，COLORNI A.Ant system:Optimization by a colony of cooperating agents［J］.IEEE Transactions on Systems，Man and Cybernetics，Part B， 1996，26(1):29－41.

［2］ELLABIB I，CALAMAI P，BASIR O.Exchange strategies for multiple ant colony system［J］.Information Sciences， 2007，177(5):1248 －1264.

［3］MIDDENDORF M，REISCHLE F，SCHMECK H.Multi colony ant algorithms［J］.Journal of Heuristics， 2002，8(3):305－320.

［4］CHU S C，RODDICK J F，PAN J S.Ant colony system with communication strategies［J］.Information Sciences， 2004，167(1/4):63 －76.

［5］KENNEDY J，EBERHART R.Particle swarm optimization［C］//In:Neural Networks.Nagoya:IEEE International Conference on Proceedings，1995:1942－1948.

［6］GAMBARDELLA L M，TAILLARD E，AGAZZI G.MACS-VRPTW:A multiple ant colony system for vehicle routing problems with time windows［C］//In:New Ideas in Optimization.London:Advanced Topics In Computer Science Series，1999:63－76.

Multiple colony ant algorithm based on particle swarm optimization

YU Xue-Cai1，2，ZHANG Tian-wen1

(1.School of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China，yuxuecai@zjnu.cn;2.Transportation College，Zhejiang Normal University，Jinhua 321004，China)

This work suggested a new multi-ACO algorithm by introducing the basic idea in the particle swarm optimization(PSO)into solution information exchange between ant colonies.The new algorithm takes much less cost for exchanging solution information than those existing methods.The new algorithm was used to solve the VRPTW benchmark instances and was compared with one existing algorithm.The results show that the new algorithm out performs the existing methods.Exploiting the idea of individual moving in the swarm intelligence to design the rule of information exchange between ant colonies can improve the performance of multi-ACO algorithm.

ant colony optimization;particle swarm optimization;vehicle routing problem with time windows

TP18

A

0367－6234(2010)05－0766－04

2009－01－10.

喻学才(1975—)，男，博士，讲师;

张田文(1940—)，男，教授，博士生导师.

(编辑 张 红)