0 引言

目前, 旅行已经越来越受到人们的青睐, 而旅游路线的选择也成为人们出发前研究的一个重要问题, 优化旅游路线可以为人们的出行降低成本和提高效率.蚁群算法是解决线路优化问题的有力工具, 它是由意大利学者Dorigo M等在20世纪90年代初提出的一种新型的模拟进化算法^[1-2].它的基本原理是基于蚁群相互协作找到一条从蚁穴到食物源的最短路径, 是一种群优化算法^[3], 但蚁群算法易陷入局部最优解, 因此对蚁群算法的改进也就成为当前研究的热点之一.学者们从蚁群算法的路径选择^[4]、信息素更新准则^[5-6]、局部搜索与全局搜索^[7-9]、收敛速度^[10-11]等方面做了大量的工作.德国学者Thomas sttzle与Jolger Hoos提出了“最大最小蚁群系统”的改进算法^[12], 避免了某条路径的信息量远大于其他路径; 郑松等^[13]提出一种动态调整的选择策略以强化其全局搜索能力; 侯文静等^[14]通过缩小算法的搜索范围、改善解空间的质量而提高了蚁群算法的搜索速度; 柳长安等^[15]借鉴狼群分配原则对信息素进行更新, 避免了蚁群算法在搜索中陷入局部最优; 针对基本蚁群算法收敛速度慢的问题, 文献[16-17]对其进行改进, 改进后的算法加快了收敛速度.然而对于蚁群算法路径选择方面改进的文章目前还比较少, 由于基本蚁群算法以邻近节点最短路径选取下一个节点, 这样选择会使得全局的路径长度总和不一定最小, 针对这一缺陷, 文章考虑用两步节点最短路径策略来选取下一个节点的思想对基本蚁群算法改进, 并对禁忌表中节点顺序进行调整, 然后将改进后的算法应用于Benchmark31、Att48、kroA100、Pr136、tsp225问题, 对旅游路线进行优化和仿真, 得到改进蚁群算法比基本蚁群算法能搜寻到更优结果.

1 蚁群算法(ACO) 原理

引入旅行商优化问题说明蚁群系统模型^[18].旅行商问题的实质是在N个城市中, 旅行商有且只有一次经过每一个城市, 使其总路程最短.设城市数目为N个, 蚂蚁有M只, 蚂蚁通过转移概率选择下一个要访问的城市.在蚁群算法中人为地设置禁忌表tabu (k), 用来存储蚂蚁已经访问过的城市.蚂蚁根据记忆, 按照转移概率选择下一个没有在禁忌表中的城市, 转移概率表达式为

$p_{ij}^k\left( t \right) = \left\{ \begin{array}{l} \frac{{\tau _{ij}^\alpha \left( t \right)\eta _{ij}^\beta }}{{\sum\limits_{j \in N_j^k} {\tau _{ij}^\alpha \left( t \right)\eta _{ij}^\beta } }}, j \notin {\rm{ta}}\;{\rm{bu}}\left( k \right), \\ 0, {\rm{otherwise}}{\rm{.}} \end{array} \right.$

(1)

其中τ_ij表示蚂蚁经过城市i到城市j, 在路径ij上留下的信息素大小, α表示的是信息素的重要程度; η_ij等于城市i与城市j之间路径ij长度的倒数, 即η_ij=1/d_ij(d_ij表示城市i与城市j之间的距离长度), 表示路径ij上的启发因子, β表示的是启发因子的重要程度; N_j^k为没有访问过的城市, p_ij^k (t) 表示在时刻t第k只蚂蚁在城市i选择城市j的概率.

信息素τ_ij会以一定的方式更新, 其表达式为

${\tau _{ij}}\left( {t + n} \right) = \rho \cdot {\tau _{ij}}\left( t \right) + \sum\limits_{k = 1}^m {\Delta \tau _{ij}^k} .$

(2)

其中ρ表示信息素残留因子, 0 < ρ < 1, 初始时刻Δτ_ij^k=C, 随后Δτ_ij^k变化为

$\Delta \tau _{ij}^k = \left\{ \begin{array}{l} Q/{L_K}, j \notin {\rm{ta}}\;{\rm{bu}}\left( k \right), \\ 0, {\rm{otherwise}}{\rm{.}} \end{array} \right.$

(3)

其中L_K表示一次旅游结束后蚂蚁k目前访问的总路径长度, Q是常量.

2 蚁群算法的改进 2.1 启发式因子的改进

基本蚁群算法以邻近节点路径最短的原理选取下一个节点, 即为一个城市离蚂蚁所在地越近, 则蚂蚁就会以较大的概率选择该城市.然而, 在这个过程中, 蚂蚁以该原理选择的两步路径之间的距离长度不一定是最小的, 并通过正反馈使得该误差值进一步放大, 从而导致蚂蚁向错误的方向寻找, 对整个算法性能造成影响.也就是说蚂蚁从上一个城市以最短路径选择下一个城市, 步步如此, 最后选择的路径不一定是最优路径, 这样最终的路径长度总和不一定最小.如图 1所示, 假定从A点出发, 要求到达D点.ACD为最短路径, 然而, 蚂蚁按照邻近节点路径最短的选择规则, 以较大的概率选择下一节点B, 所以蚂蚁所走路径为ABD, 而路径ABD的路径长度6大于路径ACD的路径长度4.5.

通过上面的例子可以看出, 蚁群算法以相邻的两个节点(即一步) 路径最短的原理选取下一个节点, 得到的结果不一定是最优的, 因此考虑三个节点(即两步) 之间的路径距离, 且利用这一策略对启发式因子进行改进, 按照式(1) 中距离越大, 启发式因子越小, 转移概率越小的原则, 改进如下:

${\eta _{ij}} = 1/\left( {{d_{i, j}} + {d_{j, j + 1}}} \right).$

(4)

其中η_ij为启发式因子, d_i，j表示节点i与节点j之间的距离长度.节点j按照式(5) 选取:

$j = \left\{ \begin{array}{l} j, D\left( {i, j} \right) + D\left( {j, j + 1} \right) < D\left( {i, k} \right) + D\left( {k, j + 1} \right)\;{\rm{and}}\;j, k, j + 1 \notin R, \\ k, {\rm{otherwise}}{\rm{.}} \end{array} \right.$

(5)

其中节点j是从节点i要选取的下一个节点, 节点j+1是从节点j要选取的下一个节点, k是任意节点, D表示完全图的赋权邻接矩阵, 则D(i, j) 表示节点i与节点j之间的距离, R=tabu.

基本蚁群算法的启发式因子是由一步节点之间的距离界定的, 一步距离越小, 启发式因子越大, 则选择该一步路径概率越大; 改进后的启发式因子是由两步节点之间的距离决定的, 两步之间距离越小则启发式因子越大, 则选择该路径的概率就越大.基本蚁群算法完成一步之后, 再搜寻第二步, 而且这种分离式的两步距离之和不一定是最短的, 如图 1所示.蚂蚁在搜索初期, 各条路径上的信息素量是一样的, 对蚂蚁诱导作用不是很大, 而主要以启发式因子值为导向进行搜索, 与基本蚁群算法相比, 改进后的算法采用两步距离策略更有全局性, 因此在搜索初期进行比较, 改进蚁群算法将会得到比基本蚁群算法较优的路径.在图 2中, 迭代初期, 改进蚁群算法得到的路径长度小于基本蚁群算法得到的路径长度, 从而可以从启发式因子的角度有效避免分离式两步距离不是最短的缺点.

2.2 禁忌表中节点顺序调整

在蚁群算法中, 蚂蚁按照概率选择公式去选择下一个节点, 并将选择的这个节点添加到禁忌表tabu中, 在此过程中选择概率是按邻近节点路径最短的原理选取下一个节点的, 文中通过2.1的改进, 采用两步节点最短路径策略选取下一个节点的方法来影响转移概率.当蚂蚁遍历所有节点之后, 将所有节点全部添加到禁忌表tabu中, 然后按照禁忌表tabu中的顺序来计算最短距离, 然而按此时禁忌表tabu中节点的顺序计算出的距离不一定是全局最短距离, 因为选择概率是由启发式因子和信息素共同决定的, 在蚂蚁搜寻后期路径上的信息素量会越来越大, 从而降低了启发式因子对选择概率的影响, 如果在之前有蚂蚁搜寻到非最优路径, 则后来蚂蚁也会按照这条路径搜寻, 导致搜寻得到的结果不是全局最优值.所以文中考虑用(6) 式进行调整禁忌表tabu中节点的顺序.

$L\left( i \right) = \left\{ \begin{array}{l} L\left( i \right) + D\left( {R\left( j \right), R\left( {j + 1} \right)} \right), D\left( {R\left( i \right), R\left( j \right)} \right) + D\left( {R\left( j \right), R\left( {j + 1} \right)} \right) < \\ \;\;\;\;\;D\left( {R\left( i \right), R\left( {j + 1} \right)} \right) + D\left( {R\left( {j + 1} \right), R\left( {j + 2} \right)} \right), \\ L\left( i \right) + D\left( {R\left( {j + 1} \right), R\left( {j + 2} \right)} \right), {\rm{otherwise}}{\rm{.}} \end{array} \right.$

(6)

其中R=tabu, L记录本次迭代最佳路线, L(i) 表示从起点到节点i的路线长度, D(R(i), R(j)) 表示禁忌表中节点i和节点j之间的距离.

2.3 改进的蚁群算法步骤

根据以上的改进思路, 改进后的算法实现步骤如下：

Step 1  初始化蚁群算法中的参数α, β, ρ, Q, NC_max, m, 设置迭代计数器初始值NC=1;

Step 2  随机选择每只蚂蚁的初始位置, 初始化禁忌表tabu, 按式(4) 计算启发因子;

Step 3  m只蚂蚁按概率函数式(1) 选择下一座城市, 将所选城市节点添加到tabu中;

Step 4  若禁忌表tabu未满转至Step 3, 若已满, 得出蚂蚁此次的最优路径长度L_NC, 并且更新L_best的值;

Step 5按照式(6) 调整节点之间的顺序, 记录本次迭代最佳路线;

Step 6按式(2) 更新信息素, 禁忌表tabu清零;

Step 7判断迭代次数是否满足条件NC < NC_max.若满足, 则迭代次数NC=NC+1, 并转至Step 2, 开始新一轮的迭代; 若不满足, 转至Step 8;

Step 8算法结束, 输出最优路径长度L_best.

3 改进蚁群算法在旅游路线优化中的应用

在Windows 7环境下, 运用Matlab7.0语言进行编程, 采用TSPLIB中的Benchmark31、Att48、kroA100、Pr136、tsp225问题, 对旅游路线进行优化和仿真.首先将基本蚁群算法和改进后的蚁群算法对其进行求解, 各运行10次, 结果如表 1所示, 迭代图如图 2所示.然后将Benchmark31单独运行10次, 结果如表 2、图 3~4所示; 最后将Att48、Eil51问题运行结果与其他算法进行比较, 结果如表 3~4, 图 5~6所示.算法参数选择如下:α=1, β=5, ρ=0.1, Q=100, 取迭代次数200为终止条件, 蚂蚁个数为31.

通过比较表 1中最优值和平均值发现, 改进蚁群算法对于Benchmark31、Att48、kroA100、Pr136、tsp225问题的运行结果都优于基本蚁群算法的结果.

观察图 2，在每个图中改进蚁群算法迭代曲线的最低位置总是低于基本蚁群算法迭代曲线的最低位置, 表明改进蚁群算法总是可以收敛到比基本蚁群算法更优的结果.

在图 3中, 用基本蚁群算法求得该旅游线路的最短距离为15 602, 最优解路径为14→12→13→11→23→16→5→6→7→2→
4→8→9→10→3→18→17→19→24→25→20→21→22→26→28→27→30→31→29→1→15.

在图 4中, 用改进的蚁群算法求得该旅游线路问题的最短距离为15 398, 最优解路径为6→5→16→4→2→8→9→10→3→18
→17→19→24→25→20→21→22→26→28→27→30→31→29→11→23→13→12→14→1→15→7.

由表 2可以看出, 基本蚁群算法最优路径长度为15 602, 平均路径长度为15 798;改进蚁群算法最优路径长度为15 398, 平均路径长度为15 590.改进蚁群算法比基本蚁群算法能够找到更短的路径.

如图 5所示, 改进蚁群算法优化Att48 TSP问题得到的最优路径为37→6→30→28→36→18→7→44→31→38→9→1→8→
22→16→3→23→11→12→15→ 40→33→46→20→47→21→13→25→14→34→41→29→2→42→10→24→45→35→
26→4→5→48→39→32→17→27→43→19.

如图 6所示, 改进蚁群算法优化Eil51 TSP问题得到的最优路径为19→41→13→25→14→18→47→12→46→51→27→48
→6→23→24→43→7→26→8→31→28→3→20→35→36→22→1→32→11→38→5→49→9→50→16→2→29→21→34
→30→10→39→33→45→15→44→37→17→4→42→40.

4 结束语

路径优化问题是实际生活中一个重要的现实问题, 文中采用两步节点最短路径策略选取下一个节点的方法, 对蚁群算法路径选择进行改进, 并对禁忌表中节点顺序进行调整, 然后采用TSPLIB中的Benchmark31、Att48、kroA100、Pr136、tsp225问题进行仿真, 并将改进蚁群算法运行Att48、Eil51的结果与其他算法运行结果进行比较.结果表明, 在迭代次数小于100时得到Att48的最优路径长度为32 112, 在迭代次数小于150时得到Eil51的最优路径长度为442.76, 比其他算法的运行结果更优.因此改进蚁群算法可用于解决旅游路线优化问题.