1.选择操作
构成新一代群体有许多方法，可以全更新（称为N方式）、保留一个最好的父串（称为E方式）、按一定比例部分更新（称为G方式）、从子代和父代中挑选若干个体组成新群体（称为B方式）等。一般而言，N方式的全局搜索性能最好，但收敛速度最慢；B方式收敛速度最快，但全局搜索性能最差；E方式和G方式的性能介于N方式和B方式之间，在求TSP问题的应用中，多选用E方式。
2.交换操作
采取顺序编码法后，若用简单的一点交换或多点交换，必然会导致未能完全遍历所有城市的非法路径。如8城市的TSP问题的父路径为
1234|5678
8765|4321
若采取一点交换，交换点随机选为4，则交换后产生的两个后代为
87655678
12344321
显然，这两个子路径均未能遍历所有8个城市，都违反了TSP问题的约束条件。解决这一问题，可以采取上述构造惩罚函数的方法，但试验效果不佳。
既要进行交换操作，又要满足约束条件，就必须对交换操作进行修正。常用的几种修正的交换操作方法介绍如下。
1）部分匹配交换（PMX，partially matched crossover）法
PMX操作是由Goldberg和Lingle于1985年提出的。在PMX操作中，先随机地产生两个交换点，定义两交换点之间的区域为一匹配区，进行两个父串的匹配区的交换操作。考虑下面的实例，两个父串A、B为
A=984|567|1320
B=871|230|9546
首先交换A和B的两个匹配区的码，得到
A＇=984|230|1320
B＇=871|567|9546
可见A＇、B＇出现了匹配区外的遍历重复。如果能对匹配区外的重复通过修改使其不重复，则非法路径问题便得到解决。易知，只要把原来在匹配区内的映射关系，即5↔2，6↔3，7↔0再按反映射关系施行到重复的编码上，就能消除非法路径现象。例如A＇匹配区以外的2，3，0分别以5，6，7替换，则得
A″=984|230|1657
同理可得
B″=801|567|9243
这样，子串仍是遍历的，但每个子串的次序部分地由其父串确定。
2）顺序交换（OX，order crossover）法
与PMX法相似，Davis（1985）等人提出了一种OX。此法开始也是选择一个匹配区域：
A=984|567|1320
B=871|230|9546
根据匹配区域的映射关系，在其区域外的重复位置标记H，得到
A＇=984|567|1H HH
B＇=8H1|230|9H4H
移动匹配区到起点位置，且在其后预留相等于匹配区域的空间（H数目），然后将其余的码按其相对次序排列在预留区后面，得到
A″=567HHH1984
B″=230HHH9481
最后将父串A、B的匹配区域相互交换，并放置到A″、B″的预留区内，即可得到两个子代：
A‴=567|230|1984
B‴=230|567|9481
虽然，PMX法与OX法非常相似，但它们处理相似特性的手段却不同。PMX法趋向于所期望的绝对城市位置，而OX法却趋向于期望的相对城市位置。
3）循环交换（CX，cycle crossover）法
Smith等人提出的CX方法与PMX法和OX法不同。循环交换执行的是以父串的特征作为参考，使每个城市在约束条件下进行重组。设两个父串为(www.xing528.com)
C=9821745063
D=1234567890
不同于选择交换位置，我们从左边开始选择一个城市
C＇=9--------
D＇=1--------
再从另一父串中的相应位置，寻找下一个城市
C＇=9--1-----
D＇=1------9-
再轮流选择下去，最后可得
C＇=9231547860
D＇=1824765093
关于PMX、OX、CX方法更进一步的分析，可参见Oliver等人的论文。
4）基于知识的交换方法
这种方法是一种启发式的交换方法，它按一些知识来规划构造后代。
（1）随机地选取一个城市作为子代圈的开始城市。
（2）比较父串中与开始城市邻接的边，选取最小的边添加到圈的路径中。
（3）重复第（2）步，如果发现按最小边选取的规划产生非法路径（重复经过同一城市），则按随机法产生一合法的边，如此反复，直至形成一完整的TSP圈。
使用这一方法，可以获得较好的结果。实践表明，在200个城市的TSP优化方面，此法已产生了接近由模拟退火算法所计算出的优化结果。
关于TSP问题，还有各种各样的修改的交换操作方法，一般而言，交换方法应能使父串的特征遗传给子串，子串应能部分或全部地继承父串的结构特征或有效基因。
3.变异操作
在遗传算法中，变异操作不是主要的操作，它只是一种补充的操作，用以防止在选择、交换中可能丢失某些遗传基因，在TSP问题中主要的变异操作如下。
1）位点变异
以小概率对串的某些位作值的变异。
2）逆转变异
对两点内的码进行逆转操作，如
A=123|456|7890
逆转操作后变为
A＇=123|654|7890
所以这种操作对TSP问题而言，属于一种细微调节，因而局部精度较高，对全局优化的作用不大。
3）对换变异
随机选择两个交换点，使交换点处的码值交换。如对于串A
在4、7交换点处交换，得到
A＇=123756489
这种变异操作在TSP问题中常被采用。
4）插入变异
从串中随机选择一个码，将此码随机插入各码中间。例如在上述A中，随机选择插入码5，插入2～3之间，则有
A＇=125346789
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
