基于TSP问题的仿生算法比较

文/刘云飞

1 引言

TSP问题自1759年被欧拉提出来后，一直成为一个困扰着数学界的难题。TSP问题是一个组合优化的问题，本身具有NPC计算复杂性，因为在计算机出现之前的数学计算比较复杂，人们可用于解决TSP问题的工具较为落后，TSP问题的精确结果仅仅局限于小规模数据。随着计算机计算的发展，计算量已经不再是困扰TSP问题求解难度的主要因素，可用于求解TSP问题的算法增速剧烈，但是每种算法的精确度都具有一定的差别。参考文献[1]中作者对现今求解TSP问题的算法进行分类，分为仿生算法和非仿生算法，并通过实验比较两种算法的求解精确度，最终发现对规模不大的TSP问题，仿生算法和非仿生算法的计算准确度相差不大，但是在问题规模很大时，非仿生算法求解准确度与仿生算法相去较大。本文将针对不同规模的TSP问题，对常见的仿生算法进行寻优对比，寻找对TSP问题求解较为敏感的仿生优化算法。

2 TSP问题简介

TSP问题可以这样描述：已知n 个城市各城市间的距离, 某一旅行商从某个城市出发访问每个城市一次且仅一次, 最后回到出发城市,怎样安排才使其所走路线最短。

其数学模型可以表示为：

对于T个城市问题，为每个城市进行编号，假设m、n为任意两个城市编号，0≤m≤T，0≤n≤T。kmn为城市m到城市n的距离，TSP问题的实质就是寻找一条最优路径，使得该路径中每个城市遍历一次，且路径长度最短。

目标函数：minS=∑m≠nkmnxmn

3 TSP问题求解算法简介-仿生算法

虽然仿生算法对求解TSP问题结果较好，但是不同的仿生算法之间也有差别。在用仿生算法解决TSP问题时，遗传算法、免疫算法和蚁群算法是经常被选用的，这三种智能算法在求解寻优过程中分别具备各自的特点：

3.1 遗传算法

遗传算法（genetic algorithm GA）是模拟生物在自然环境中的遗传和进化过程而形成的自适应全局优化搜索算法，它最早是由美国的J.H.Holland教授提出，该算法起始于20世纪60年代对自然和人工自适应系统方面的研究。遗传算法借鉴了达尔文的进化论和孟德尔的遗传学说，通过模拟自然界物种的进化机制，在算法运行过程中自动获取和积累有关搜索空间的数据，并自适应的控制搜索过程以求得最优解。

表1：burmal14（已知最优路径距离：30.8785）

表2：att48（已知最优路径距离：33522）

表3：kroA100（已知最优路径距离：21282）

遗传算法是一种常用的优化算法，编码技术简单，遗传操作易于理解，使用“适者生存”的原则，采用选择、交叉和变异等操作，通过模拟自然界物种进化原理，一代代的把“最优个体”遗传下去。该算法从种群中进行选择，搜索过程不受函数约束条件的限制，可以避免陷入局部次优解以及保证算法的简易性。但是当解决结构复杂和搜索空间较大的优化问题时，该算法搜索时间比较长，易出现早熟问题。而且对初始种群的选择很敏感，不同的初始种群的选取会直接影响解的质量和算法效率。

3.2 免疫算法

最早的免疫系统模型是由Jerne于1973年提出的，他依据Burnet的克隆选择学说，开创了独特型网络理论，给出了免疫系统的数学框架，并利用微分方程模型模拟了淋巴细胞的动态变化。现实的生物免疫系统是一种复杂的自适应系统，免疫系统能够在病原体入侵人体时识别出病原体，并且产生针对该病原体的抗体，抗体可以将病原体消灭，并在消灭病原体后依然残存在人体内，当同一种病原体再次入侵人体时，病原体会被体内存留的抗体消灭，免疫系统的这种学习、记忆和模式识别的能力可用于解决科学和工程问题。

与其它算法相比，免疫算法具有利用自身产生多样性和维持机制的能力，可以确保种群的多样性，这解决了一般寻优过程中经常出现的 “早熟”问题，利于获取全局最优解。

3.3 蚁群算法

蚁群算法(Ant Colony Optimization, ACO)是由意大利学者M.Dorigo.V.Maniezzo和A.Colorni于20世纪90年代初通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法，该算法在智能理论研究领域具有重要地位。

蚂蚁可以在没有任何参照的情况下找到从巢到食物的最短路径，并且可以在路径被阻挡时自适应地搜索到新的最短路径。根本原因是蚂蚁在寻找食物时可以在它们寻找的路径上释放一种特殊的分泌物——信息素。随着时间的推移，信息素蒸发导致浓度降低，而在最短路径上的蚂蚁可以比其它路径上的蚂蚁更快地返回，提升路径上的信息素浓度，从而形成一种正反馈机制。蚁群算法易于与其它算法相结合，具备求解复杂问题的能力，但是由于前期解过多，造成蚁群算法搜索算法较慢。

4 实验结果对比

为了比较不同的仿生算法对TSP问题求解的精确度，本文使用burmal14、att48和kroA100对不同的仿生算法进行了实验，这三组实验数据来源TSPLIB[7]。实验环境 为：pc机 -intel(R) Core(TM) i5-2450M CPU@2.50GHz，Windows7 64旗舰版。实验软件为：MATLAB R2014b。实验结果如表1所示。

通过表2、表3分析实验结果，我们得出如下结论：

（1）对于小规模TSP问题，如14个城市最短路径问题，遗传算法、免疫算法和蚁群算法的寻优能力都很强，几乎每一次运行都可寻找到最优路径。

（2）对于规模较大的TSP问题，三种仿生算法的寻优能力是有所差异的。由于遗传算法全局搜索能力较强，因此在解决48个和100个城市最短路径的问题时，同样10次的运行结果，遗传算法总是可以寻找到比其他两种算法距离更短的路径。但由于遗传算法的每次寻优具有一定的概率性，寻优稳定性的能力不如蚁群算法，这也导致它的平均路径长度与蚁群算法在相差不大情况下，标准误差却远远大于蚁群算法。

（3）通过实验数据对比，我们不难发现免疫算法在寻优的过程中具有记忆性，每代的最短路径会记录下来，与下一代随机生成的个体。

5 结语

通过本次实验，我们不难发现遗传算法、免疫算法和蚁群算法在TSP问题中各有优缺点，遗传算法的全局性保证了它寻优结果的准确性，蚁群算法的鲁棒性保证了它寻优结果的稳定性。因此在大规模TSP问题的寻优中，我们应该优先考虑采用遗传算法和蚁群算法的联合寻优，利用遗传算法的随机搜索、快速性和全局性产生TSP问题所需的初始种群，然后，充分利用蚁群算法的并行性和正反馈机制来修正寻优算法，提升寻优算法的求解效率和求解精度，这种联合寻优算法不仅适用于TSP问题，也可推广至求解其它NP问题。