遗传算法求解TSP的研究

    周敏

    摘 要：遗传算法通常被认为是自适应的随机搜索算法，与传统的优化方法（枚举，启发式等）相比较，以生物进化为原型，具有很好的收敛性。文章用遗传算法求解经典的旅行商问题，最后使用实验对算法进行了测试，能够在短时间内找到理想的解。

    关键词：遗传算法；旅行商问题；遗传；变异

    1 意义和目标

    文章提出用遗传算法求解TSP这个古老而有挑战性的NP问题，利用遗传算法的原理对个城市进行编码，从一组随机产生的初始解开始搜索，种群中的每个染色体是问题的一个解的编码串，这些染色体在后续迭代中不断进化，运算过程中计算每个个体的适应度来衡量染色体的好坏。遗传和变异过程中，根据选择规则选择部分后代，同时淘汰部分后代，最后算法收敛于最好的染色体，可能是TSP的最优解。

    2 国内外研究现状

    目前对遗传算法的研究大部分是从算子出发，提出各种杂交算子，但这些算子一般在实际使用中需要花费较大的工作量，比如已有的OX，PMX，SSX，ERX，CSEX和DPX等。还有其他一种变异算子，这种变异算子以颠倒作为基石，它的工作效率比较高，但也有自身的缺点，就是具有一定的随机性，从而实现不了对团体中的个别的消息进行再次构建。所以，由Michalewicz和郭涛根据以上两类算子的优缺点进行了结合，得到了一种比较适合的算子，这种算子叫做Inver-Over，这种算子能够容易获取，查找领域宽，它的基本思路是：旅行商问题的核心参数是城市之间的边，却不是这些城市的具地理位置。

    另外一些研究者为了提高群体的质量，发明了疫苗，通常称之为疫苗算法，而这种是一种基因库的观念，这种观念是录制好基因的集合，通过路径抓举、灌输疫苗来实现的。量子遗传算法（Q GA）在求解数值和组合优化问题时效率明显优于传统进化算法，但目前较多被用于求解组合优化的背包问题，为了充分发挥Q GA的优点，文中用其求解TSP这一经典的NP难问题。首先，文中设计了一种利用几率幅值编码的新的编码方式，即利用几率幅值编码的量子个体与一组向量对应，而此向量又与一条可行路径一一对应。这样的编码方式不仅缩小了种群规模，占用较少内存，所得的解均可行，而且有效地增强了种群的多样性；其次，为了继承比较优秀的基因集，通过对量子进行杂交，并且是在量子的个体上的操作来实现的；最后，通过加上两步的查找，并且是局部查找，从而降低了算法的收敛时间，第一阶段主要针对实例中排列稀疏处的城市进行优化，第二阶段在第一阶段的基础上着重对排列密集处的城市优化。据此，设计了解TSP的一个新的高效的QGA，并证明了其以概率1收敛到全局最优解；测定算法性能的数值。

    3 算法理论分析

    达尔文著名的自然选择学说，是遗传算法的来源理论，该算法是一种迭代搜索算法。达尔文的自然选择学说认为：生物的变异一般不是定向的，而自然选择是定向的，只有那些能适应环境的变异类型才能生存下来，产生后代，而那些与环境不相适应的变异类型将可能被淘汰。在自然环境中，每种生物都有自己的适应能力，适应能力的不同揭示了不同生物的繁衍能力。

    最原始的遗传算法中，仅仅包含三种最基本的遗传算子，也就是选择算子、交叉算子和变异算子，这种最原始的遗传算法工作的过程是非常简单的，并且较为人们学习，它也是其他的后来发展的遗传算法的祖辈。

    ⑴最原始的遗传算法的组成部分。遗传算法中最基本的就是染色体了，它是利用二进制编码的0和1组成的符号串来表示的，也就是说它的等位基因是由零和一构成的。而最初的状态下，0和1的符号串是可以随机的来生成染色体的。

    ⑵群体中的个体对环境的适应性的得分。决定是否遗传的概率的大小，这个值是由个体的自适应性的大小决定的，可以说，自适应行越高，那么遗传的概率也就越高。这里，要得到这个遗传的概率，那么初始状态下，必须让每个个体的适应性的得分为0或者是大于0的数。所以，我们必须确定自适应性与遗传的概率的之间的正确规则。

    ⑶遗传算子：这里我们只谈到了三个最基本的遗传算子：使用比例选择算子的是选择算子；使用单点交叉算子的是交叉算子；使用基本位变异算子或均匀位变异算子是变异算子。

    ⑷每一种算法都有自己的参数，那么遗传算法的参数包括以下：M：群体中的个体的总数是多少，也就是说，群体的多少问题；S：作为遗传算法，它在进化过程中，什么时候停止的问题；Pc：这是指交叉的概率；Pm：这是指变异的概率。

    4 算法的技术路线

    （1）编写代码，用代码来回答问题。（2）模拟一个原始的群体，这个群体的规模是固定的。（3）这一步需要计算每个个体的适应性程度，前面已经讲到了，适应度大，那么个体就好，适应度小，那么个体就差。（4）若终止条件T（a：最优个体保持20代不变；b：t>500；c：平均适应度与最优个体适应度之差小于e，e是任意小的正实数；只要满足其中一条就终止）满足，则算法终止；否则，计算概率

    并以概率pi从P（t）中随机选取一些个体构成一个种群RP（t）。（5）为了得到一个新的交叉后的种群，应该由交叉概率获取。最后再以概率pm，再进行变异，从而生成一个新的种群P（t+1）。（6）t=t+1，如不满足终止条件转（3）。

    5 数据实验及结果

    本实验的硬件环境：Intel（R） Core（TM）2 Duo CPU T5800 @2。00GHz 1。99GHz，2。00GB的内存。本实验的软件环境：Dev-C++编译器对程序进行编译执行。实验对标准的TSPLIB 20个城市进行了计算，程序输入的初值为20个城市的坐标（城市数，城市的横坐标，城市的纵坐标）。通过读取文件input。txt中的20个城市的坐标进行计算，计算结果保存在文件out。txt中。程序运行时需在相同目录下新建文件input。txt和out。txt，将20个城市的坐标放在input。txt中。程序经过10次运算，计算结果最优值为：25。800371507 ，具体的路径为： 8 4 2 17 6 20 13 5 16 18 7 19 10 15 9 12 3 1 14 11。

    6 结语

    该算法对求解大型的TSP性能不优，后续工作主要是研究优化的遗传算法求解大型的TSP。遗传算法具备自身很多的优点，尤其是同传统的一些优化方法进行比较的时候，因为遗传算法具有非常优秀的收敛性，并且工作的时间上花费较少，在工作的精准度上也比较优秀。具体的优点在实践中的应用可以看出来，特别是在文章中的旅行商问题的解决上可以看出来。但就像前述讲过的，在解决大规模的问题上，可能遗传算法就会逊色很多了。

    实验过程中对于如何确定GA有关参数最佳范围是一个难题，如迭代次数的选择和运行时间两方面的权衡问题，以及遗传概率和变异概率的选择等。后续的工作是寻求优化的遗传算法对TSP进行求解。

    [参考文献]

    [1]Grover L K.A fast quant um mechanical algorithm for database search/ /Proceedings of the 28th ACM Sympium Theory Computing.Philadelphia，Pennsylvania，USA，1996：212-219.

    [2]Deut sch D，Jozsa R.Rapid solution of problems by quantum computation/ / Proceedings of t he Royal Society London A.London，UK，1992，439：553-558.

    [3]吴斌，史忠植.一种基于蚁群算法的TSP问题分段求解算法.计算机学报[J].2001，24（12）：1329-1333.

    [4]杨辉，康立山，陈毓屏.一种基于构建基因库求解TSP问题的遗传算法[J].计算机学报，2003，26（12）：1753-1758.

    [5]周智，万颖瑜，陈国良，等.基于局部最优解的归约算法：一般方法和在TSP问题上的应用[R].合肥：国家高性能计算中心，1999.

    [6]康立山，谢云，尤矢勇，等.非数值并行算法（第一册）：模拟退火算法[M].北京：科学出版社，1997.

    [7]赵春英，张铃.求解货郎担问题（TSP）的佳点集遗传算法[J].计算机工程与应用，2001，37（3）：83-84.

    [8]朱文兴，傅清祥.一个基于填充函数变换的对称TSP问题的局部搜索算法[J].计算机学报，2002，25（7）：701-707.

    [9]王伟.人工神经网络原理与应用[M].北京：北京航空航天大学出版社，1995.