用遗传算法求解TSP问题（IGT算法）

1.染色体编码

采用TSP问题的最自然、最直接的表示方式，即路径表示。它直接将一条路径中的城市按编号顺次记录，例如，环路4-2-3-1-4可直接表示为（4，2，3，1）或（2，3，1，4），一条染色体表示一条合法的路径^[1]。

2.适应度

衡量个体优良性的唯一标准。遗传算法的适应度采用路径长度的倒数表示，适应度越大，则路径越短，个体越优。算法中计算适应度的评价函数定义为：

3.映射算子

随机从种群P 中挑出两条染色体S1 和S2，不妨设f（S2）＞f（S1）（即S2 优于S1，其中f 为评价函数），从S1 中随机选择一段基因片段Δs1，判断S2 中是否存在这样一段基因Δs2：它与Δs1 长度相同且第一位和第二位城市编号相同，如果存在Δs2，则将染色体S1 中的基因片段Δs1 置换为Δs2，剩余基因按部分映射进行调整。

4.优化算子

假设当前获得的最优个体为S2，随机选择一条染色体S1，将S2 作为父体，随机选择S2中一段路径Δs2，然后判断S1 中是否存在这样一段路径Δs1，它与Δs2 中的基因长度相同且有相同的城市，只是基因城市的排列顺序不同，判断Δs1 和Δs2 的基因片段路径长度，如果Δs1 的路径较短，则用Δs1 置换掉当前最优个体S2 中的Δs2 片段。

5.选择策略

进行杂交或是变异以后，产生新的个体，为了保持样本总数一定，需要进行淘汰，即去掉不良个体，保留优良个体。

6.算法描述

begin

step 1：随机生成种群P={S0，S1，…，SN-1}，其每一条染色体是一条遍历所有城市的随机路径，计算每条染色体适应度Fi，初始化各演化参数。

step 2：初始化i：=0；

step 3：将种群P 中的染色体Si 赋值给空染色体S′，从S′中随机选择一基因城市C ；

step 4：变异算子，如果0～1之间的随机数小于变异概率P1，则从S′中任意选择一不同于C 的基因C′，并逆转C 和C′之间的基因片段，转至step 6；

step 5：反序-杂交算子，从种群P 中随机选择不同于Si 的另一条染色体S″，在S″中指定与C 相邻的下一个基因位C′，并执行以下操作：

①如果S′中C′的位置与C 相邻，转至step 7；(www.xing528.com)

②将S′中从C 到C′之间的基因片段进行倒位操作；

③计算逆转前后路径改变值d，若d＜0且演化速度小于临界速度，转至step 7。

step 6：将C′赋值给C，重复执行step 4～step 6，直到C 取过S′的每一个基因位；

step 7：计算S′的适应值，判断：如果f（S′）＞Fi，将S′替换Si，Fi 赋新值f（S′）[评价函数f（S）为个体的路径长度的倒数，长度短的适应值高]；

step 8：i增加1，重复执行step 3开始的操作直到i=N；

step 9：更新变异概率；

step 10：映射算子，如果演化速度小于临界速度且0～1之间的随机数小于映射概率P2，执行以下操作：

①随机从P 中挑出两条染色体S1 和S2，不妨设f（S1）＞f（S2）；

②从S1 中随机选择一段基因片段Δs1，判断S2 中是否存在这样一段基因Δs2：它与Δs1长度相同且第一位和第二位城市编号相同；

③如果存在Δs2，则将染色体S1 中的基因片段Δs1 置换为Δs2，剩余基因按部分映射进行调整。

step 11：优化算子：选择目前最优个体中的若干个基因片段，分别判断其余个体中是否有城市相同、基因长度相同、适应值更高的片段，如果有，则替换掉最优个体中相应的基因片段。

step 12：重复执行step 2～step 11，直到满足停机条件，最后输出最优染色体。

end

7.IGT 算法的特点

（1）保留了GT 算法中一个个体只与自己的后代竞争的选择机制，使得算法在运行中能够保持群体的多样性，以避免传统遗传算法中的早熟现象。

（2）以杂交算子为主，其他算子为辅，同时增加了一些控制机制使得算法能够更为快速地收敛。

（3）该算法的演化过程是一个并行爬山的过程，因此很容易得到问题的全局最优解，避免了过早陷入局部最优解。