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

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

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

3、世纪60年代末期到70年代初期，由美国michigan大学的john holland与其同事、学生们研究形成的一套较完整的理论和方法，是试图解释自然系统中的生物复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。随后经过近几十年的发展，遗产算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即

4、基因型）是某种基因组合，它决定了个体的形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解5。2

5、.2 tsp问题巡回旅行商问题（traveling salesman problem，tsp），也称货郎问题，它属于np完全问题，给定一组n个城市和它们两两之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。用图论术语描述巡回旅行商问题：在有向图，表示顶点集，表示边集合，每条边上有非负权值，寻找的hamilton圈，使得的总权最小5。3. 已经存在的tsp问题编码方法3.1 编码已经存在的tsp问题的编码方式有很多种，其中最常用的三种分别是：序号排列编码法、随机数编码法和剩余序号编码法。（1）序号排列编码方法 将n个城市分别用进行序号标识，并将的个整数的一个排列作为

6、一个旅行方案。例如共有8个城市，整数的一个排序就是tsp问题的一个可行解，它可以作为遗传算法求解tsp问题的一个染色体1。（2）随机数编码法1 一种能够避免出现不可行解的编码方案是利用随机数编码。假设有8个城市，它们分别对应序号，编码方法是在（0，1）内产生8个不相同的随机数作为编码分类键例如随机产生一个染色体 按照随机数大小升序排列为 将的下标表示为城市序号，则得到一个旅行路线：6，1，3，7，8，4，2，5。（3）剩余序号编码法1 设n个城市的序号分别为，我们称其为固有标识序号，如果在n个城市中删除几个城市后，需要对剩余城市重新赋予序号，新的序号应遵循原固有标识序号的排列次序，称其为剩余序

7、号。例如8个城市删除城市，则剩余的5个城市的序号分别为，城市d的固有序号为4，在删除后，它的剩余序号为3。剩余序号的编码方法为设n个城市的一个访问路线次序为，对于这个访问路线，产生一个染色体，其中，它是在n个城市中删除后的剩余序号。例如有8个城市的固有序号为，给出一个旅行路线，按照剩余序号定义，该旅行线路的编码为3.2 编码的不足对于序号排列编码方法的最大不足是交换和突变的过程中容易产生不可行解；随机数编码的不足之处是产生随机数的过程中或者在交换突变过程中可能会使随机数某些值相等，导致不能进行排序。剩余序号发编码法解决了以上几个不足之处，但是剩余序号编码在从编码到实际路程顺序转换中稍显繁琐，而

8、且没有转换成较为简单的二进制编码。4. 空隙编码法求解tsp问题4.1 空隙编码法设n个城市，对于任意城市，定义之间的空隙为叫做的前向空隙；定义之间的空隙为叫做的后向空隙；特殊的，的前向空隙为，的后向空隙为。例如有三个城市，它的空隙集为，城市与空隙的表现形式如下： 空隙编码法首先确定一个编码顺序，然后放置第一个城市，因为放置第一个城市的时候还没有空隙，所以第一个城市不用编码。但产生两个空隙，分别为和，之后按照之前已经确定的编码顺序将第二个城市放入上步产生的两个空隙之一，如放入，记空隙的标号0为第二个城市的编码，定义其编码为0，然后依次把城市插入空隙，直至完成。所得到的编码序列即为一个利用空隙编

9、码法所得。例如有7个城市，分别为，设定编码顺序为，即先放置a，不需要编码；之后放置b，假设b放置在a的前向空隙中，记编码为0；c放置在a的后向空隙中，编码为2；d放置在a的前向空隙中，编码为1；e放置在c的后向空隙中，编码为4；f放置在a的前向空隙中，编码为2；g放置在c的后向空隙中，编码为5，编码结束。所以，当顺序为时，编码为。过程如下所示：空隙0 空隙1a第一步： 放置a，不需要编码 产生新空隙0，1第二步：b a 空隙0 空隙1 空隙2 看上图，b放置在a的前向空隙 0上，产生新空隙0，1，2 b a c 空隙0 空隙1 空隙2 空隙3第三步： 看上图，c放置在a的后向空 隙2上，产生新

10、空隙0，1，2，3 第四步： . . . . . .第五步： . . . . . .b d f a c e 空隙0 空隙1 空隙2 空隙3 空隙4 空隙5 空隙6第六步： f放在a的前向空隙2上， 产生新空隙0，1，2，3，4，5，6 b d f a c g e第七步： 如上图，g放在c的后向空隙 5上，编码结束4.2 空隙编码法的二进制表现形式二进制编码方式对于初始群体的产生和交换突变运算比较方便，结合空隙编码法的编码特点，导出基于空隙编码法编码的二进制表示形式。针对上述例子，当放置第一个城市a的时候，产生两个空隙，当放置第二个城市b的时候，产生三个空隙，所以，当放置第n个城市的时候，产生个

11、空隙。针对上述问题，可以得到如下表格。表1 空隙编码法二进制表现形式依据放置城市vi后abcdef产生的空隙数234567空隙标号范围010120123012340123450123456二进制位数122333 即当放置城市d后，一共可以得到5个空隙，每个空隙从前到后的依次标号为0，1，2，3，4，用二进制数表示04四个数需要用3位二进制数。所以针对此问题，可以用一个14位的二进制数对一个方案进行编码，第一位二进制数表示b的空隙编码法编码，第23位二进制数表示c的空隙编码法编码，第45位二进制数表示d的空隙编码法编码，第68位二进制数表示e的空隙编码法编码，第911位二进制数表示f的空隙编码法

12、编码，第1214位二进制数表示g的空隙编码法编码。当放置城市b后，空隙标号为0，1，2，而两位二进制数表示的范围为03，所以编码的时候c的空隙编码法编码范围为02，当大于2的时候，人为的调整为2。即城市的空隙编码法编码范围为，当二进制数转换为十进制数时大于，令此数等于或等于0。4.3 空隙编码法及其二进制表现形式的初始群体产生方法（1） 空隙编码法由表1可知，当放置城市之后，产生的空隙标号范围为，对于一个空隙编码法编码,的范围为。所以可以按照此种规格产生任意符合条件的初始群体。（2） 空隙编码法的二进制表现形式 因为空隙编码法的二进制表现形式产生的二进制数可能超过空隙标号范围，所以用空隙编码法

13、的二进制表现形式产生初始群体的时候按照以下几个步骤： a.产生符合实际问题位数的二进制数 b.按实际问题对二进制数进行位数划分，看每个划分区间是否满足该区间的空隙标号的最大标号范围，如果不满足，丢弃此染色体。4.4 空隙编码法及其二进制表现形式的交换方法（1） 空隙编码法 对于空隙编码法编码，其交换方式可以采用节段交换，单点或者多点都可以，但是要保证只有对应位的空隙编码法编码可以交换。如取交换点在第三位，则从第四位可以开始交换，得到 （2） 空隙编码法的二进制表现形式 对于空隙编码法的二进制表现形式，交换的方法可以使用任何二进制编码的交换方式，但是空隙编码法的二进制表现形式可能产生某个区间的最

14、大数超过该区间空隙标号的最大范围，对于这种情况，使超过空隙标号范围的区间重置为该区间空隙标号的最大数或最小数。4.5 空隙编码法及其二进制表现形式的突变方法（1）空隙编码法空隙编码法编码的突变方式可以单点突变和多点突变，只要保证空隙编码法编码突变点的突变范围在该点允许的范围即可。（2）空隙编码法的二进制表现形式 空隙编码法的二进制表现形式的突变方法可以采用二进制编码的任何突变方法，只是突变之后检查每个区间的范围是否满足该区间的范围条件，如果不满足，重置该区间为该区间允许的最大范围或最小范围。5. 算例分析假设有a，b，c，d，e五个城市，每个城市之间的距离如下表所示：表2 各个城市之间距离表城

15、市/距离abcdea03435b306510c46086d35809e510690用基于空隙编码法和空隙编码法的二进制表现形式编码法的遗传算法解决此问题。5.1 基于空隙编码法编码方式的遗传算法初始群体的选择，交换概率和突变概率的选择对于实际问题会产生很大的影响，本题为tsp问题中的一个很小规模的路径选举，所以本题中选取交换概率，突变概率，交换方法选为节段交换，突变方法选为单点突变。（1）产生初始群体 默认编码顺序为a，b，c，d，e随机产生四个初始个体 （2）定义适应度为经过此路径的权重和的倒数。 （3）复制适应度高的个体，淘汰适应度低的个体，即为复制淘汰，新群体为（4）交换操作，因为交换概

16、率为，即与交换，与交换。采用节段交换，可以随机产生一个位置，比如产生的数为2，即从第三位开始进行节段交换。 至此产生四个新个体，分别为。（5）突变操作，群体个数为4，个体长度为4，突变概率为，采用单点突变，即系统随机选取三个个体，每个个体突变一位。得到突变后的新个体为 （6）重复上述步骤，直到找到最优解。在实际问题中，也可以规定算法的代数为终止条件。5.2 基于空隙编码法二进制表现方法的遗传算法对于此方法，选取交换概率为，突变概率为，初始群体为4。采用默认编码顺序a，b，c，d，e，根据此问题，可由8个二进制数表示一个染色体的编码，其中第1位表示b的编码，第23位表示c的编码，第45位表示d的

17、编码，第68位表示e的编码。（1）产生初始群体产生四个初始群体，分别为计算个体每个区间是否超过最大空隙标号的允许范围，可知=（1，1，1，1，0，1，0，0）在c的空隙编码法编码（1，1）超过该区间空隙标号的允许范围（该区间空隙标号范围为0，1，2），删除染色体，重新生成一个染色体=（1，0，1，1，0，1，0，0），所以产生的初始群体为（2）定义适应度为经过此路径的权重和的倒数。 （3）复制适应度高的个体，淘汰适应度低的个体，即为复制淘汰，新群体为 （4）交换操作，因为交换概率为，即与交换，与交换。采用节段交换，可以随机产生一个位置，比如产生的数为3，即从第四位开始进行节段交换。 （5）突变

18、操作，群体个数为4，个体长度为8，突变概率，采用单点突变，即系统随机选取三个个体。若每个个体突变的位置相同，则使突变后产生的个体在某个区域超出该区域允许范围的概率增大，所以突变采用每个个体不同位置的突变。 =（0，1，1，1，1，1，0，0） =（0，0，1，1，0，0，1，0） =（0，1，0，1，1，1，0，0） =（1，0，1，1，0，0，1，1）检查每个区域的允许范围，可以发现=（0，1，1，1，1，1，0，0）在c的空隙编码法区域编码（1，1）超出该区域空隙标号的允许范围（该区间空隙标号范围为0，1，2），将其超出允许范围的部分重置为（0，0），即=（0，0，0，1，1，1，0，0）

19、。所以突变后的新个体为 =（0，0，0，1，1，1，0，0） =（0，0，1，1，0，0，1，0） =（0，1，0，1，1，1，0，0） =（1，0，1，1，0，0，1，1）（6）重复上述步骤，直到找到最优解。在实际问题中，也可以规定算法的代数为终止条件。6. 总结 本文通过采用空隙编码法对tsp问题进行编码，成功的解决了其他一些tsp问题编码方法所产生的不足，并通过空隙编码法的特点成功的给出了tsp的问题的二进制编码方式，通过重新定义二进制编码的交换和突变方法，使tsp问题的解决方法更加完善。同时对于二进制编码的交换和突变方法还应该有更加优于本文的方法，在实际的应用中，读者可以加入自己的方法

20、，使问题的解法更加完善。参考文献1 郭嗣琮.信息科学中的软计算方法m，沈阳：东北大学出版社，2001。 2 田景文，高美娟.人工神经网络算法研究与应用m，北京：北京理工大学出版社，2006。 3 周培德.算法设计与分析m，北京：清华大学出版社，2005。4 张文修，梁怡.遗传算法的数学基础m，西安：西安交通大学出版社，2006。5 李敏强,寇纪淞,林丹,李书全.遗传算法的基本理论与应用m，北京：科学出版社，2004。gap-coded genetic algorithms based on tsp problemzhang qian，liu hongxing，xu lingdepartment of basic science, liaoning technical university, fuxin 123000abstractthis paper presents a genetic algorithm to solve the tsp problem gap coding method, and through the use