周敏

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

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

1 意义和目标

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

2 国内外研究现状

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