解旅行商问题的蚁群分布估计混合算法

潘 澔, 孙 俐, 高 尚*

(1.苏州建设交通高等职业技术学校，苏州 215104) (2.江苏科技大学 计算机学院，镇江 212100)

旅行商问题(traveling salesman problem,TSP)可以描述为有一个推销员从某城市出发走遍所有的城市，且每个城市只能走一次，最后返回原处，如何选择路线使所走路程最短.TSP问题是一个NP完全问题，对于一个N个城市的TSP问题，可能的路径数是一个组合数(N-1)!/2, 随着城市数目N的增大，问题的规模呈指数式增大.TSP问题是组合优化领域中的一个典型的问题，解决此问题有较大的现实意义，如印刷电路板的钻空路线方案，连锁店送货路线问题等都可简化为TSP问题.并且此问题也可作为测试新的算法的标准问题，因此一直是研究的热点.目前求解TSP问题的主要方法有模拟退火算法[1]，遗传算法[1-2]，启发式搜索法，Hopfield神经网络算法[1]，蚁群算法[3]，演化算法[4],近似多项式方法[5]等.文中依据分布估计算法的思想，提出一种蚁群分布估计混合算法来解决旅行商问题.

1 基本蚁群算法

蚂蚁个体之间是通过一种称之为外激素的物质进行信息传递，从而能相互协作，完成复杂的任务.蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动.因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大.蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的.蚁群算法首先成功应用于旅行商问题，目前在车辆路径寻优[6]、装配序列规划[7]等方面均有应用.

设有m个蚂蚁，每个简单蚂蚁有以下特征：它根据以城市距离和连接边上外激素的数量为变量的概率函数选择下一个城(设τij(t)为t时刻边e(i,j)上外激素的强度).规定蚂蚁走合法路线，除非周游完成，不允许转到已访问城市，有禁忌表控制(设tabuk表示第k个蚂蚁的禁忌表，tabuk(s)表示禁忌表中第s个元素).它完成周游后，蚂蚁在它每一条访问的边上留下外激素.

(1)

τij(t+n)=ρ·τij(t)+Δτij

(2)

(3)

(4)

式中：Lk为第k只蚂蚁环游一周的路径长度；Q为常数.

解旅行商问题的蚁群算法的基本步骤:

步骤1nc←0；(nc为迭代步数或搜索次数)各τij和Δτij的初始化；将m个蚂蚁置于n个顶点.

步骤3 计算各蚂蚁的路径长度Lk(k=1,2,…,m)；记录当前的最好解.

步骤4 按更新方程修改轨迹强度.

步骤5 对各边弧(i,j)，置Δτij←0，nc←nc+1.

步骤6 若nc<预定的迭代次数且无退化行为(即找到的都是相同解)则转步骤2.

步骤7 输出目前最好解.

2 基本分布估计算法

分布估计算法[8-10]提出了一种全新的进化模式.在传统的遗传算法中，用种群表示优化问题的一组候选解，种群中的每个个体都有相应的适应值，然后进行选择、交叉和变异等模拟自然进化的操作，反复进行，分布估计算法中，没有传统的交叉、变异等遗传操作，而是概率模型的学习和采样分布估计算法通过一个概率模型描述候选解在空间的分布, 采用统计学习手段从群体宏观的角度建立一个描述解分布的概率模型,然后对概率模型随机采样产生新的种群，如此反复进行, 实现种群的进化，直到终止条件.根据概率模型的复杂程度以及不同的采样方法，分布估计算法发展了很多不同的具体实现方法，但是都可以归纳为两个主要步骤[8]：首先构建描述解空间的概率模型，通过对种群的评估，选择优秀的个体集合，从而采用统计学习等手段构造一个描述当前解集的概率模型;然后由概率模型随机采样产生新的种群，一般的，采用蒙特卡罗方法，对概率模型采样得到新的种群.

遗传算法中的交叉和变异会破坏已经优化好的个体，分布估计算法用建立概率模型和采样两大操作取代了遗传算法中的交叉算子和变异算子，以一种带有“全局操控”性的操作模式解决了遗传算法存在的这一问题.遗传算法和分布估计算法的流程对比如图1，并且分布估计算法不需要太多的参数设置，编程比遗传算法简单.

图1 分布估计算法与遗传算法的流程异同点

3 解旅行商问题的蚁群分布估计混合算法

蚁群算法各侯选解根据积累的信息不断调整自身结构，以期望产生性能更好的解.蚁群算法根据对所有的候选解的信息进行更新信息素，没有对优解、劣解进行区分，而分布估计算法通过对种群的评估，选择优秀的个体集合，淘汰劣性解.文中给出2个改进策略，优选初始值策略，首先初始化时，随机产生一些解，选择较优的路径留下信息素，其他不改变；优选路径策略，蚂蚁每次周游结束后，只有比较好的解才留下信息素，按路径长度排序，并从中选出最优的s个个体才留下信息素.

解旅行商问题的蚁群分布混合算法步骤如下:

步骤1nc←0；(nc为迭代步数或搜索次数)各τij和Δτij的初始化；将m个蚂蚁置于n个顶点上；优选初始值策略，随机产生100个解，选择较优的个路径留下信息素(文中取30个)，其他不变.

步骤3 计算各蚂蚁的路径长度Lk(k=1,2,…,m)，记录当前的最好解.

步骤4优选路径策略，按路径长度排序，并从中选出最优的s个个体，对最优的s个个体按更新方程修改轨迹强度(种群个数s占m的比例取30%～90%).

步骤5 对各边弧(i,j)，置Δτij←0，nc←nc+1.

步骤6 若nc<预定的迭代次数且无退化行为(即找到的都是相同解)则转步骤2.

步骤7 输出目前最好解.

4 算法测试

选用Oliver30和att48作为实验例子，由于各种参考文献提供Oliver30数据不一致，文中采用http://stevedower.id.au/other/oliver30中的数据.图2是Oliver30的最好的解(横轴和纵轴是城市的相对坐标)，总路程为423.740 6(假设城市间的距离用最接近的整数近似，总路程为420).图3是解att48的最好的解，总路程为33 522.

固定资产投资减去折旧等于当年的固定资产增量。如果假定技术不发生变化，用非工业部门当年的增加值相对于上一年的增量除以固定资产增量，就等于非工业产业单位增加值所需的直接固定资产含量。

图2 Oliver30的TSP最好的解

图3 att48的最好的解

将与模拟退火算法、遗传算法作对比.模拟退火算法参考文献[1]，起始温度T=100 000 ℃，终止温度T0=1 ℃，退火速度α=0.99；遗传算法程序的参数如下：染色体个数N=30，交叉概率Pc=0.2，变异概率Pm=0.5，迭代次数100；蚁群算法：α=1.5，β=2，ρ=0.9，nmax=50，C=100，Q=1 000 000，比例为60%.算法各测试100次，统计数据如表1.从表1可以看出，蚁群算法+优选初始值策略+优选路径策略的混合算法的效果比较有效.

表1 几种算法测试结果

影响算法的性能的主要参数是种群的个数m和选出的种群个数s.采用蚁群算法+优选初始值策略+优选路径策略，选出的种群个数s占m的比例不同，结果也不一样.不同的比例，算法各测试20次，统计数据如表2.

表2 s/m取不同值结果比较果

从表2可以看出，s/m比例越大，不能体现出选优的优势，效果越不好；当然s/m比例太小，也容易陷入局部极值.因此s/m比值取60%～70%，效果比较好.

5 结论

(1) 提出利用蚁群分布估计混合算法来解决旅行商问题，得到满意效果.如果与其他方法结合，如加上2-Opt局部搜寻的方式，解决旅行商问题的效果可能会更好.