基于空隙编码遗传算法的tsp 问题研究

《基于空隙编码遗传算法的tsp 问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于空隙编码遗传算法的TSP问题研究张倩，刘红星，徐玲辽宁工程技术大学理学院，辽宁阜新（123000）摘要：本文提出了遗传算法解决TSP问题的空隙编码法，并通过采用空隙编码法对TSP问题进行编码，解决了其他编码方式在交换和突变过程中容易产生不可行解的问题，同时给出了基于空隙编码法的遗传算子的交换和突变方法，简化了问题的求解过程。并根据空隙编码法的特点，提出了空隙编码法的二进制表现形式，解决了TSP问题应用遗传算法的二进制编码，同时也定义了适合TSP问题的二进制算子的交换和突变的方式，使算法更加简化合理。关键词：遗传算法；空隙编

2、码法；二进制表现；TSP问题1.引言TSP问题是运筹学中的一类组合爆炸问题，由于其各种组成数量巨大，给问题的求解带来很大的不便。通过遗传算法解决TSP问题是近几十年发展的很好的方法，但是传统的应用遗传算法的TSP问题的编码方法还存在一些不足的地方，比如序号排列编码方法在交换和突变的过程中容易产生不可行解，随机数编码法在产生过程和交换突变过程中容易产生相等的随机数，使问题求解困难。本文通过采用空隙编码法对TSP问题进行编码，解决了算子在交换和突变过程中产生不可行解的问题，同时根据空隙编码法的特点给出了TSP问题的二进制编码，使得

3、TSP问题在编码和求解过程中更加简单。2.问题概述2.1遗传算法遗传算法（GeneticAlgorithms，GA）是20世纪60年代末期到70年代初期，由美国Michigan大学的JohnHolland与其同事、学生们研究形成的一套较完整的理论和方法，是试图解释自然系统中的生物复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。随后经过近几十年的发展，遗产算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基

4、因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneti

5、coperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解[5]。2.2TSP问题巡回旅行商问题（TravelingSalesmanProblem，TSP），也称货郎问题，它属于NP完全问题，给定一组n个城市和它们两两之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。用图论术语描述巡回旅行商问题：在有向图，表示

6、顶点集，，表示边集合，，每条边上有非负权值，寻找的Hamilton圈，使得的总权最小[5]。1.已经存在的TSP问题编码方法3.1编码已经存在的TSP问题的编码方式有很多种，其中最常用的三种分别是：序号排列编码法、随机数编码法和剩余序号编码法。（1）序号排列编码方法将n个城市分别用进行序号标识，并将的个整数的一个排列作为一个旅行方案。例如共有8个城市，整数的一个排序就是TSP问题的一个可行解，它可以作为遗传算法求解TSP问题的一个染色体[1]。（2）随机数编码法[1]一种能够避免出现不可行解的编码方案是利用随机数编码。假设有8

7、个城市，它们分别对应序号，编码方法是在（0，1）内产生8个不相同的随机数作为编码分类键例如随机产生一个染色体按照随机数大小升序排列为将的下标表示为城市序号，则得到一个旅行路线：6，1，3，7，8，4，2，5。（3）剩余序号编码法[1]设n个城市的序号分别为，我们称其为固有标识序号，如果在n个城市中删除几个城市后，需要对剩余城市重新赋予序号，新的序号应遵循原固有标识序号的排列次序，称其为剩余序号。例如8个城市删除城市，则剩余的5个城市的序号分别为，城市D的固有序号为4，在删除后，它的剩余序号为3。剩余序号的编码方法为设n个城市的

8、一个访问路线次序为，对于这个访问路线，产生一个染色体，其中，它是在n个城市中删除后的剩余序号。例如有8个城市的固有序号为，给出一个旅行路线，按照剩余序号定义，该旅行线路的编码为3.2编码的不足对于序号排列编码方法的最大不足是交换和突变的过程中容易产生不可行解；随机数编码的不足