旅行商问题推广及其混合智能算法

陈冬华

（华东交通大学基础科学学院，江西南昌 330013）

1TSP与CTSP

从上个世纪50年代起，学术界出版了大量关于旅行商问题[1]的文献。旅行商问题（traveling salesman problem，TSP）是指这样一个组合优化问题：某个商人欲到n座城市A=（a1，a2，…，an）去推销商品，希望选择一条路线使得商人走遍每座城市后（仅能访问一次）回到起点且所走路程最短。用图论术语来说[2]，假设有一个图g=（v，e），其中v是顶点集（顶点对应于某个城市），e是边集（城市之间的连接状态，每边赋予权重表示城市间距离），设D是由顶点i与顶点j之间的距离所组成的距离矩阵，如果任意两个城市的距离都是对称的，它所对应的是图论中的无向图，若两个城市间的距离是非对称的，它所对应于图论中的有向图。旅行商问题就是求出一条经过所有顶点且每个顶点只经过一次的具有最短路径的回路。

如果令城市ai与aj的距离为dij，用xij表示商人是否以顺序i访问城市ai后接着访问城市aj（即，xij=1表示商人以顺序i访问城市ai后接着访问城市aj，否则xij=0），则TSP问题可以描述成如下优化问题

式中：s.t.为约束条件。

TSP是典型的NP-hard问题，是组合优化领域研究中研究最多的问题之一，也是目前解决旅行优化领域里的研究热点。也有不少研究者对TSP进行了推广，如多旅行商问题[3-6]，广义旅行商问题[7-14]，中国旅行商问题[15]，有向黑白旅行商问题[16]。

下面将TSP变形推广成全体旅行商问题（caboodle traveling salesman problem，CTSP）。CTSP定义如下：某个商人拥有s种货物B=（b1，b2，…，bs），其中bj（j=1，2，…，s）表示第j种货物的数量，欲到n座城市A=（A1，A2，…，An）去推销这些商品，Ai=（a1i，a2i，…，asi），其中aji（i=1，2，…，n；j=1，2，…，s）表示第i座城市Ai对这s种货物各自的需求数量，商人事先不知道各座城市需求情况但希望找到一座城市一次性销售掉所有的商品（沿途不卖），销售完商品后随即返回不再访问其它剩余城市，需要选择一条路线使得商人推销完商品后（每座城市仅能访问一次，走过所有的城市后没有销售完商品即生意失败也返回起点城市）回到起点且所花时间最短（假设商人在途中速度始终不变）。

显然，CTSP具有现实实用价值与意义，也有些其它领域的问题可以转化为CTSP，比如信息检索等，但目前为止，CTSP少有人进行研究。

2GA、ACS算法与CTSP描述

遗传算法[17]（genetic algorithm，GA）是一类仿生优化算法，具有快速随机的大范围全局搜索能力，很容易与其它算法结合，但对于系统中的反馈信息利用不够，当求解到一定范围时往往做大量无为的冗余迭代，求精确解效率低。因为GA不受函数连续性、可导性等条件的约束，并以其固有的并行性，使GA广泛应用于组合优化、图像处理、人工智能、机器学习、专家系统等很多领域。

蚁群系统（ant colony system，ACS）算法[18]是意大利学者M.Dorigo等人于1991年首先提出的。1996年，M.Dorigo等又应用该算法求解非对称TSP以及车间作业调度问题（job-shop scheduling problem，JSP），且对蚁群算法中初始化参数对其性能的影响作了初步探讨，该算法可以使得蚂蚁在行进过程中不再局限于按照已积累的信息浓度信息选择路径，而是可以做到利用已有信息与搜索新路径并重，通过适当提高解的随机性和多样性，从而大大增强了基本蚁群算法的鲁棒性。ACS算法具有分布式并行全局搜索能力，能较大程度避免候选解陷入局部极小并导致系统收敛到伪最优解从而停止进化，但存在初期信息匮乏求解速度慢的缺点。我国在蚁群算法领域的研究起步较晚，从公开发表的论文来看，国内最早研究蚁群算法的是东北大学控制仿真研究中心的张纪会博士与徐心和教授，以投稿日期为标准，时间是1997年10月。

为了使用智能算法对CTSP进行路径规划，CTSP定义重新描述为：某地区共有n座城市，其编号分别为1，2，…，n，旅行商从城市1出发去执行销售任务，旅行商在城市i完成其销售任务的概率为pi，pi与pj（i≠j）相互独立（i=1，2，…，n；j=1，2，…，n）。不论旅行商在城市i是否能完成其销售任务，其在城市i因尝试执行任务而造成的时延均为ti。对城市1而言，p1=0，t1=0。旅行商从城市i旅行到城市j所需的时间为tij（从城市i旅行到城市j距离dij=vtij，假设v为常数。所以tij也可以用dij来代替）。若旅行商在某城市完成任务，则可由该城市直接返回出发城市1，而无需继续访问其余城市；若未能完成任务，则旅行商需要继续旅行到另一座城市直至其任务完成或遍历所有城市均不能完成其任务即任务失败为止（途中每座城市至多访问一次）。要求制定一个旅行商路径计划，使得旅行商完成任务所需时间的期望值最小。

设城市i所需求的货物需求向量Ai=（a1i，a2i，…，asi），其中aji（i=1，2，…，n；j=1，2，…，s）均为非负值，表示城市i需求某种货物j的数量。完成销售任务必需满足旅行商具有货物资源（供应向量）B=（b1，b2，…，bs），其中bj（j=1，2，…，s）表示该销售任务的第j种货物的数量。那些需求向量的每一维分量均大于供应量的城市完成销售任务的概率较大，即城市的需求模式和旅行商销售任务的供给模式越匹配，其完成任务的概率也就越大。可以按照如下公式对旅行商在i城市完成任务的概率pi进行预测

式中：T表示向量转置。

解决了CTSP，可以给出旅行商在不同城市的最优旅行路线，保证旅行商可以在最短时间内销售完商品，这在实际生活中具有指导意义，并且在其它领域应用中发挥作用，如在网络信息库中进行某种信息检索时，对检索系统规划出检索路径等等。

3 混合智能算法（combined intelligent algorithm，CIA）

ACS算法在求解TSP问题时，只需考虑城市之间的距离。CTSP除了需要考虑城市间距离上路径延时之外，还需要考虑在各城市完成任务概率和销售时间。旅行商蚂蚁除了会倾向于以较高的概率选择花费时间短、外激素浓度高的城市间路径之外，还会优先考虑那些完成任务概率高、销售时间短的城市，这是因为旅行商蚂蚁在访问过若干完成任务概率高、销售时间短的城市之后很可能就已经完成了预定任务，由此即可直接返回出发点城市而无须继续访问其余城市。按照这一基本思想，旅行商蚂蚁选择下一城市的概率为

在系统尚未收敛到全局最优解前，当前最优解很可能对应着局部极小值，这很有可能使得整个蚁群系统陷入局部极小而停止进化，为了避免此种情况发生，可对全局更新规则进行推广：在蚁群系统中只有当前循环中最优的那一只蚂蚁能够进行全局更新，令最优的k只蚂蚁同时更新所经路径上的信息素浓度，则将公式（2）修改为

式中：m为所对应的蚂蚁；Tm为第m最优解对应的蚂蚁完成任务的时间。

这样全局更新规则的推广使得解的多样性得到了适当提高，在很大程度上避免了候选解陷入局部极小并导致系统收敛到伪最优解而停止进化。并在此ACS算法基础上引入GA，基本思想是汲取两种算法的优点，克服各自缺点，起到优势互补作用，本文针对CTSP提出一种新的混合智能算法（combined intelligent algorithm，CIA）。CIA在求解速度效率上优于ACS算法，在求解精确度上效率优于GA，是收敛速度快与求解效率高的比较好的一种启发式算法。

4 CIA描述与实例

CIA基本思路是首先采用GA，充分利用GA的快速性、随机性、全局收敛性，并把GA产生的结果作为有关问题的初始信息素分布，然后再采用ACS算法，在有一定初始信息素分布的情况下，利用ACS算法的并行性、正反馈性、求解精度效率高等特点。CIA运算如下：

步骤一：定义目标函数和适应度函数；初始化GA中相关参数；随机生成一组实数编码；置GC：=0，GC为GA算法运行次数。

步骤二：设置控制遗传代数t：=0。

步骤三：根据适应度函数选择X，Y；对X，Y进行OX交叉；对X，Y进行逆转变异。

步骤四：设置控制遗传代数标准T；若t＜T，则置t：=t+1，转入步骤三，否则继续。

步骤五：设置GA控制运行次数GCmax；若GC＜GCmax（其中GCmax为GA最大运行次数），则转入步骤二，否则继续。

步骤六：生成若干组GA优化解；初始化ACS算法中相关参数；根据GA的优化解生成信息素初始分布，将m只旅行商蚂蚁置于n座城市；置NC：=0，NC为ACS算法运行次数。

步骤七：每只蚂蚁根据公式（1）状态转换规则旅行到下一座城市，并按公式（3）进行信息素局部更新；m只蚂蚁遍历n座城市后，按公式（4）进行信息素强度范围进行控制；将m只蚂蚁随机置于n座城市，对禁忌表和路径序列进行初始化。

步骤八：设置ACS算法控制运行次数NCmax；若NC＜NCmax（其中NCmax为ACS最大运行次数），则转入步骤七，否则继续。

步骤九：输出CIA的最优解。

应用CIA求解CTSP时，在求解初始阶段采用GA，充分利用GA的全局优化机制在较短时间内取得一组优化解，然后将这组优化解转化为对应路径上信息素的初始浓度，从而引导蚂蚁的寻找路径过程，减少了单独使用ACS算法时初始计算过程的盲目性与随机性。在构造解的过程中按照ACS算法的局部更新规则在所经过的路径上分泌信息素，并且每一代的前k个优胜解都会按照ACS算法的全局更新规则对所经过的路径进行信息浓度更新。经过若干代之后，那些延时短且沿途城市销售完成任务概率高、总时间费时短的路径上信息浓度会逐渐高于其它路径，后继蚂蚁在信息素指引下，会以更高的概率选择那些比较优化的路径，如此反复就构成了一个正反馈过程，这样会使得绝大多数蚂蚁首选优化路径，从而快速给出最优解。

为了验证CIA与GA及ACS算法的寻优效率，下面研究一个实例，如：求旅行商去16座城市销售的最佳路线。16座城市（城市编号为1至16）地理位置横坐标与纵坐标（x，y）分别为：1（38.24，20.42），2（39.57，26.15），3（40.56，25.32），4（36.26，23.12），5（33.48，10.54），6（37.56，12.19），7（38.42，13.11），8（37.52，20.44），9（41.23，9.10），10（41.17，13.05）11（36.08，-5.21），12（38.47，15.13），13（38.15，15.35），14（37.51，15.17），15（35.49，14.32），16（39.36，19.56）。采用Matlab2008a仿真平台，在Pentium4，2.8 GHz，512 MB内存的微机上进行仿真实验。求出的最优解（用城市编号顺序表示路线）为：1，14，13，12，7，6，15，5，11，9，10，16，3，2，4，8。3种算法的效果见表1。

表1 三种算法效果表Tab.1 Effect of three algorithms

实验表明，CIA比GA及ACS算法寻优效率更高、更好。

[1]王有为.基于禁忌表的捕鱼搜索算法及其在旅行商问题中的实验研究[J].系统工程理论与实践，2008，2（2）：230-631.

[2]刘新，刘任任，侯经川.求解旅行商问题的整体优先算法[J].计算机应用，2007，5（5）：1204-1207.

[3]李天龙，吕勇哉.基于自组织优化算法的一类多旅行商问题[J].计算机应用，2010，2（2）：458-460.

[4] 党建武，靳蕃.神经网络求解MTSP的应用研究[J].铁道学报，1997，19（2）：63-69.

[5]WAC E，HAN J，MANN R C.Aneural network algorithm for the multiple traveling salesmen problem[J].Biological Cybernetics，1989，61（1）：11-19.

[6]代坤，鲁士文，蒋祥刚.基于遗传算法的多人旅行商问题求解[J].计算机工程，2004，30（16）：139-141.

[7]黄可为，汪定伟.热轧计划中的多旅行商问题及其计算方法[J].计算机应用研究，2007，7（24）：43-57.

[8]HAYKIN S，LABORDERE A L.The record balancing problem：A dynamic programming solution of a generalized traveling salesman problem[J].Real WorldApplications，1969（2）：43-49.

[9]SAKSENA J P.Mathematical mode of scheduling clients through welfare agencies[J].Computers&Structures，1970（8）：185-200.

[10]SRIVASTAVA S S，KUMAR S，GARG R C，et al.Generalized traveling salesman problem through n sets of nodes[J].Computers&Structures，1969（7）：97-101.

[11]赵曦，叶和平.广义旅行商问题及其求解[J].东莞理工学院学报，2007，5（14）：75-80.

[12]LIEN Y N，MA E.Transformation of the generalized traveling salesman problem into the standard traveling salesman problem[J].Information Sciences，1993（74）：177-189.

[13]VLADIMIR D，ZORAN S.An efficient transformation of the generalized traveling salesman problem into the traveling salesman on digraphs[J].Informatics and Computer Science，1997（192）：105-110.

[14]余国兴，丁玉成，李涤尘.平面多轮廓加工路径优化模型及其近似算法[J].西安交通大学学报，2004，1（38）：39-42.

[15]王怡雯，丛爽.用随机神经网络优化求解C-TSP[J].吉林大学学报：信息科学版，2004，4（22）：359-363.

[16]江贺，张宪超，陈国良.有向黑白旅行商问题[J].计算机学报，2007，3（3）：431-439.

[17]吴微，周春光，梁艳春.智能计算[M].北京：高等教育出版社.2009：119-146.

[18]徐宗本.计算智能[M].北京：高等教育出版社.2006：111-114.