遗传算法在求解TSP问题上的应用

摘? 要 TSP (Traveling Salesman Problem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP 问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。 关键词：TSP ?遗传算法 ?遗传算子?? 编码 在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码。 编码是应用遗传算法时要解决的主要问题，也是设计遗传算法的一个关键步骤。编码方法除了决定个体染色体排列形式之外，还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法，编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。 针对一个具体问题，如何设计一个完美的编码方案一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向。目前还没有一套既严密有完整的指导理论及评价准则能够指导我们设计编码方案。De Jong曾提出了两条操作性较强的实用编码原则： 编码原则一(有意义积木块编码原则):应使用能易于产生与所求问题相关的且具有低阶，短定义长度的编码方案。 编码原则二(最小字符集编码原则):应使用能使问题得到自然表示或描述的具有最小字符集的编码方案。 迄今为止人们已经提出了许多的编码方法，总的来说，可以分为三类：二进制编码方法，浮点数编码方法，符号编码方法。