1. 研究背景

旅行商问题(TSP)是物流领域中的典型问题,它的求解具有十分重要的理论和现实意义.采用一定的物流配送方式,可以大大节省人力物力,完善整个物流系统.

已被广泛采用的遗产算法是旅行商问题的传统求解方法,但遗传算法收敛速度慢,具有一定的缺陷.

本文采用蚁群算法,充分利用蚁群算法的智能性,求解旅行商问题,并进行实例仿真.进行仿真计算的目标是,该算法能够获得旅行商问题的优化结果,平均距离和最短距离.

求解TSP的蚂蚁算法中,每只蚂蚁是一个独立的用于构造线路的过程,若干蚂蚁过程之间通过自适应的信息素值来交换信息,合作求解,并不断优化.这里的信息素值分布存储在图中,与各弧相关联.

2. 算法流程

蚂蚁算法求解TSP算法的过程如下:

1. 首先初始化,设迭代的次数为NC.初始化NC=0.

2. 将m个蚂蚁置于n个顶点上.

3. m只蚂蚁按概率函数选择下一个城市,完成各自的周游.

每个蚂蚁按照状态变化规则逐步地构造一个解,即生成一条回路.蚂蚁的任务是访问所有城市后返回到起点,生成一条回路.设蚂蚁k当前所在的顶点为i,那么,蚂蚁k由点i向j移动要遵循规则而不断迁移,按不同概率来选择下一点.

4. 记录本次迭代最佳路线.

5. 全局更新信息素值.

应用全局信息素更新规则来改变信息素值.当所有m个蚂蚁生成了m个解,其中有一条最短路径是本代最优解,将属于这条路线上的所有弧相关联的信息素值进行更新.

全局信息素更新的目的是在最短路线上注入额外的信息素,即只有属于最短路线的弧上的信息素才能得到加强,这是一个正反馈的过程,也是一个强化学习的过程.在图中各弧上,伴随着信息素的挥发,全局最短路线上各弧的信息素值得到增加.

6. 终止.若终止条件满足,则结束;否则NC=NV+1,转入步骤(2)进行下一代进化.终止条件可指定进化的代数,也可限定运行时间,或设定最短路长的下限.

7. 输出结果.

3. 算法仿真与分析

程序仿真结果如下图1和2所示：

图1

图2

仿真结果输出截图：

 部分代码截图：

 4. 展望和改进

1. 第一种是蚁群算法系统的改进，内容可以参考【智能算法第一期】蚁群算法原理和多种改进方法

2. 第二种是蚁群算法中参数的改进，标准蚁群算法中的4个参数Alpha、Beta、Rho和Q都是设定的经验值，而其数值往往会影响蚁群算法求解的速度和求解精度，如何通过其他算法对它们进行优化，也会作为重要的研究内容

*文章部分内容取自书籍，如有侵权请联系作者删除。