《智能优化算法：TSP遗传算法求解方法》

1.编码方式与适应度函数

在求解TSP的各种遗传算法中，多采用以遍历城市的次序进行编码的方法，本章也采用这种最自然的编码方式。在可行解群体的初始化、交叉操作以及变异操作中均隐含了TSP的合法约束条件，即城市代码不重复出现。适应度函数取线性定标，即

其中，α为预先设定的常数，n为城市的数目，M为包含所有城市的最小正方形的边长，Td为根据式（2.22）计算得出的实际路径长度，即目标函数。

2.初始群体生成

在满足TSP的约束条件的前提下，对种群的初始化进行改进，将随机选取与贪心法结合应用于初始化操作，产生包含较优值的初始种群。贪心法实际上就是将每一步取局部最优的求解方法。本章在由贪心法找到的局部优化路径中，取最好的若干条包含进初始群体。这样初始群体中就包含了由贪心法得到的局部优化解和其余随机产生的个体。

3.选择操作

方式一　采用按比例选择的方式和最劣死亡方式使群体得到更新，即从父代中按比例选取两父本进行交叉，在得到的两个子代中，选择一个适应度高的替代父代群体中适应度最低的个体。若交叉后产生的子代的适应度比父代中适应度最差的还低时，则取消本次操作，重新选取父代进行交叉。

方式二　考虑到遗传算法初始群体中的个体一般是随机产生的，初始群体中的个体均匀地分布在整个串空间，在遗传迭代的早期，群体中个体适应度差别很大，在按比例选择时，适应度低的个体被选中的机会很小，低适应度值个体淘汰太快，容易使算法收敛于局部最优解；在遗传迭代的晚期，群体个体适应值差别不大，按比例选择时，“优胜劣汰”的作用不明显，算法收敛速度慢。于是针对方式一提出了一种改进的选择策略。在进化的初期仍然用式（2.26）确定的适应度差别不是特别大，沿用方式一的方法。在进化的晚期，由式（2.26）确定的适应度差别很小，先对群体中个体的适应值进行变换，再按个体适应值大小的比例进行选择，具体方法是：先将参与选择的N个个体按适应值从小到大的顺序编号，如果适应值相同，可以随意排列，然后以个体的序号作为其变换后的适应值，即N个个体的适应值分别变换为1，2，3，…，N，编号为m的个体被选中的概率为

在最终结果中为了统一适应度值的比较，在模拟实验中输出的适应值结果中仍采用变换前的适应度值，即由式（2.26）确定的值。

4.交叉操作

为了考察基因片段在求解TSP中的重要性，本章采用了7种交叉操作.

（1）PMX（partially matched crossover）法，该方法是由Goldberg和Lingle提出的部分匹配交叉操作。在两父代染色体中随机选取一段，利用两父代染色体在所选段内的元素定义一系列交换，这些交换可以在每条父代染色体上分别执行产生子代染色体。例如

A=10　8　6/4　5　7　9/3　1　2

则所选段内的元素所定义的一系列交换为

4↔6|5↔1|7↔4|9↔2

注意到4只是6，7之间的连接元素，所以合并后有关系6↔7|5↔1|9↔2，这样产生的子代为

A＇=10876142359

B＇=62845791103

（2）OX（order crossover）法，该方法是由Davis提出的一种交叉方法。在两个父串中随机选择一个匹配区域，如

A=1　2　3/4　5　6　7/8　9

B=4　5　2/1　8　7　6/9　3

首先将匹配区域复制到子代中

A＇=×××/4567/××

B＇=×××/1876/××

然后，将第二个交叉点后的码作为初始码，按原顺序重新排列有

9—3—4—5—2—1—8—7—6

8—9—1—2—3—4—5—6—7

删除匹配区域中已存在的码有9—3—2—1—8和9—2—3—4—5。将上述操作得到的子段从第二个交叉点后开始填充，最终得子代

（3）类OX法一（OX-type 1），现简介如下：在两个父串中随机选择一个匹配区域，如父串及匹配区域选定为

A=1　2/3　4　5　6/7　8　9

B=9　8/7　6　5　4/3　2　1

首先将B的匹配区域加到A的前面，A的匹配区域加到B的前面，得到

A＇=7654/123456789

B＇=3456/987654321

然后在A＇中自匹配区域后依次删除与匹配区域中相同的城市代码，得到最终的两个子串为

A″=7　6　5　4　1　2　3　8　9

B″=3　4　5　6　9　8　7　2　1

（4）类OX法二（OX-type 2），将匹配区域换成随机选取的几个随机位。先随机产生几个随机位，如两个父串为

A=1　2　3　4　5　6　7　8　9

B=9　8　7　6　5　4　3　2　1

随机选取第2，4位，其对应的城市标号为2，4，8，6，在父串中保持这些城市的位置不变，其余的位按顺序对换位置。

其余的位分别按9—7—5—3—1和1—3—5—7—9填入，最终得两个子串为

A″=9　2　7　4　5　6　3　8　1

B″=1　8　3　6　5　4　7　2　9

（5）单点交叉映射法，举例说明如下：记两父串为A、B，随机选取交叉点，设两父串及交叉点选定为(www.xing528.com)

A=9　1　4　5　6/7　8　3　2

B=6　8　1　2　3/9　5　4　7

执行简单的交叉后得到

A＇=9　1　4　5　6/9　5　4　7

B＇=6　8　1　2　3/7　8　3　2

对于交叉点前的码，检查其出现的遍历重复，依据交叉点后的位置映射关系，逐一进行交换，对于A＇有9→2|5→8|4→3，对于B＇有8→5|3→4|2→9，于是有

A″=2　1　3　8　6　9　5　4　7

B″=6　5　1　9　4　7　8　3　2

（6）单点顺序交叉法，举例说明如下：设两父串为A，B。随机选取交叉点，定义交叉点后面为匹配区域。首先将A和B的匹配区域分别加到B和A的前面，得到A＇和B＇，然后分别在匹配区域后依次删除与匹配区域相同的码得最终子串A″和B″。假如，设

A=9　1　4　5　6/7　8　3　2

B=6　8　1　2　3/9　5　4　7

则依上述操作可得

A＇=9　5　4　7/9　1　4　5　6　7　8　3　2

B＇=7　8　3　2/6　8　1　2　3　9　5　4　7

A″=9　5　4　7　1　6　8　3　2

B＇=7　8　3　2　6　1　9　5　4

（7）位置信息法，即将一个父串中的城市编号作为另一个父串中的城市位置号，互相替换，例如，若父串分别为

A=3　5　4　6　2　1　7　8　9

B=6　7　5　3　4　2　1　9　8

位置编号为index=1，2，3，4，5，6，7，8，9，则最终子串为

A＇=7　1　6　2　4　3　5　9　8

B＇=2　4　6　5　7　3　1　9　8

5.变异操作

本节在不同的遗传操作组合中，采用了4种变异操作。

（1）对换变异，即随机选择串中的两点，交换其值。例如，对于串

若对换点为4，7，则经过对换后为

（2）插入变异，即从串中随机选择一个码，将此码插入随机选择的插入点之间。例如，对于上述A而言，若选择插入码为5，选择插入点为2，3之间，则

A＇=1　2　5　3　4　6　7　8　9

（3）移位变异，即对串中的每一位，都进行是否发生变异的判断，对没有发生变异的位保持不变，发生变异的位依次进行移位循环操作。例如，仍对于

A=1　2　3　4　5　6　7　8　9

若第3，6，7位通过变异率，即对应这些位通过伯努利试验，则其余位不变，只有这些位上的码发生移位变换，按上述规则产生的子串为

A＇=1　2　7　4　5　3　6　8　9

（4）目标导向变异，这是一种基于贪心法思想的启发式变异操作，贪心法的思想是每步取局部最优；反之，在一个串中相邻的某两个码之间的距离是整个串中相邻码距离最大的，那么这两个码相邻的不合理性要大一些。随机地将这两个码中的一个与随机产生的另一个码进行对换。这里的目标导向是指如果变异后的适应值没有变大，则重新进行这次操作，如果仍然得不到更高的适应值，则取两个码中的另一个码，重复上面的操作，如果适应值依然没有变大，姑且认为这两个码是较合理的，就随机选取两位进行对换操作；否则，用变异后的串替代原串。

6.进化逆转操作

进化逆转操作是在串中随机选择两点（两点间称为逆转区域），再将逆转区域内的子串按反序插入到原位置。例如，设串A为

A=1　2　3/4　5　6/7　8　9

若选择逆转点为3，6，则进化逆转后串A变为

A＇=1　2　3/6　5　4/7　8　9

对于一个给定串的两位码间是否要执行进化逆转操作，需经判断决定。例如，设串A为

现对ci，cj进行判断，若

则定义

其中，由“/”之间的部分为逆转区域，然后执行进化逆转操作。

对于上述进化逆转判断的执行，首先要根据问题的要求和不同的遗传操作组合来决定逆转判断长度l，然后在父串中随机选取长度为l的子串，对该子串中的每一位码与其他所有位码进行形如式（2.29）的判断。本章采用的进化逆转是一种单向（朝着进化的方向）和连续多次的逆转操作，即对于给定的串，若进化逆转使串的适应度提高，则执行进化逆转操作，如此反复，直至不存在这样的进化逆转操作为止。