（TSP 问题的交叉算子） TSP 问题 (Traveling Salesman Problem) 描述如下： 给定 n 个城市， 构成一个完全图，任何两城市之间都有一个代价（例如路程、旅费等） ，现要构造遍历所有 城市的环路，每个城市恰好经过一次，求使总代价达到最小的一条环路。 遗传算法是求解该问题的一个很有效的近似算法。 在该算法中， 一个个体为一条环路， 其编 码方法之一是 1 到 n 这 n 个数字的一个排列， 每个数字为一个城市的编号。 例如当 n=5 时， “ 3 4 2 1 5 表示该方案实施的路线为 ” 3->4->2->1->5->3 。遗传算法的核心是通过两个个体的 交叉操作，产生两个新的个体。下面的程序给出了最简单的一种交叉算法。

具体过程如下：

 (1)选定中间一段作为互换段，该段的起止下标为 t1，t2，随机生成 t1，t2 后，互换两段。

 (2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两 步处理： 

(2.1) 将两个互换段中，共同的数字标记为 0，表示已处理完。 

(2.2) 将两个互换段中其余数字标记为 1，按顺序将互换段外重复的数字进行替换。

 例如： n=12，两个个体分别是： 

a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11 

a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9 t1=5，t2=8。

上述每一行中，两个星号间的部分为互换段。假定数组的下标从 1 开始，互换 后有： 

a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11 

a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9 

然后，将数字 6,7 对应的项标记为 0，星号内数字 2,9,10,11 对应的项标记为 1，并且按顺序 对应关系为 : 10<->2 ，11<->9。于是，将 a1[9]=10 替换为 a1[9]=2 ，将 a2[2]=2 替换为 a2[2]=10 ， 类似再做第 2 组替换。这样处理后，就得到了两个新个体： 

a1: 1 3 5 4 6 7 10 11 2 12 8 9 

a2: 3 10 1 12 2 6 7 9 8 5 4 11 

（3）输出两个新个体的编码。 

程序：