如何用路径表示表示回路路径及其相关算子？

路径表示也许是一条回路的最自然的表示。例如一条回路

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

被表示为（5 1 7 8 9 4 6 2 3）。

关于路径表示的杂交算子主要有：部分映射杂交（Partially-Mapped Crossover，PMX）、次序杂交（Order Crossover，OX）、循环杂交（Cycle Crossover，CX）、基于位置杂交（Position-Based Crossover，PBX）等。关于路径表示的变异算子主要有：倒位、插入、移位、互换等。下面我们将分别介绍。

1.杂交算子

1）部分映射杂交

部分映射杂交算子通过从一个父体中选择一个子序列，然后尽可能多地保持另一个父体中城市的位置与次序的方式产生后代。其具体做法如下：对给定的两个父体p1、p2，首先随机地在父体上选择两个杂交点，然后交换父体p1、p2 上两个杂交点之间的中间段得到两个后代o1、o2，这时o1、o2 上除了两个杂交点中间段中的城市外，其他的城市尚未确定；然后对o1、o2 中尚未确定的城市，分别保留各自父体p1、p2 中与中间段无冲突的城市，对与中间段有冲突的城市，则执行部分映射，直到与中间段无冲突为止，再将该城市填入相应的位置即可。

例4-3 给定下列两个父体，随机地选择两个杂交点，用“|”表示。

p1=(2 6 4| 7 3 5 8| 9 1)

p2=(4 5 2| 1 8 7 6| 9 3)

将p1、p2 上两个杂交点之间的中间段交换得：

o1=(# # #|1 8 7 6| # #)

o2=(# # #|7 3 5 8| # #)

这里#表示待定城市。

由两个中间段确定的部分映射为：

1↔7,8↔3,7↔5,6↔7

然后，对后代o1、o2 中的#部分，分别保留与各自父体p1、p2 交换后的中间段无冲突的城市得：

o1=(2 # 4|1 8 7 6| 9 #)o2=(4 # 2|7 3 5 8| 9 #)

对o1、o2 中与交换后的中间段有冲突的#部分，执行部分映射，直到无冲突为止。例如o1 中的第一个#初始为6，但6与中间段中的城市冲突，部分映射将6映射到7，但7仍与中间段冲突，部分映射将7映射到5，5与中间段不冲突，这时第一个#填入5。类似地可确定其他的#部分，最后所得到的o1、o2 如下：

o1=(2 5 4|1 8 7 6| 9 5)

o2=(4 1 2|7 3 5 8| 9 6)

2）次序杂交

次序杂交算子通过从一个父体中选择一个子序列，保持另一个父体中城市的相对次序的方式产生后代。其具体做法如下：对给定的两个父体p1、p2，首先随机地在父体上选择两个杂交点，保留父体p1、p2 上两个杂交点之间的中间段得到两个后代o1、o2，这时o1、o2 上除了两个杂交点中间段中的城市外，其他的城市尚未确定；对o1 中尚未确定的城市，首先p2中的城市从第二个杂交点开始按其相对次序列出，然后将该序列中在o1 中间段中的城市删除，再将剩余子序列从第二个杂交点填入o1 的相应位置即得o1。用同样的方式可得o2。

例4-4 给定下列两个父体，随机地选择两个杂交点，用“|”表示。

p1=(2 6 4| 7 3 5 8| 9 1)

p2=(4 5 2| 1 8 7 6| 9 3)

保留p1、p2 上两个杂交点之间的中间段得：

o1=(# # #|7 3 5 8| # #)

o2=(# # #|1 8 7 6| # #)

这里#表示待定城市。

然后从第二个杂交点开始，将p2 中的城市按原次序列出得：

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

从中删除o1 中间段中的城市的得：

9-4-2-1-6

将该子序列从第二个杂交点开始依次填入到o1 中得：

o1=(2 1 6|7 3 5 8| 9 4)

类似地可得：

o2=(4 3 5|1 8 7 6| 9 2)

3）循环杂交

循环杂交算子产生的后代中的每一个城市是某个父体相应位置的城市。具体做法如下：对给定的两个父体p1=（c1，c2，…，cn），p1=（u1，u2，…，un），先确定后代o1 中来自于父体p1 中的城市，首先假定p1 中的第一个城市c1 在o1 中，即将o1 中的第一个城市置为c1，那么p2 中的第一个城市u1 必不在o1 中，由此知p1 中的城市u1 在o1 中，若u1 还没有填入o1 中，则将u1 填入o1 中与其在p1 相应的位置，p2 中与p1 中u1 相应位置的城市u2 必不在o1 中，若u2 还没有填入o1 中，则将u2 填入o1 中与其在p1 中相应的位置，这样继续下去，直到将某个uk 填入o1 后，p2 中与p1 中uk 相应位置的城市已经填入到o1 为止，这时将p2 中尚未在o1 中出现的城市直接填入到o1 中与其在p2 中相应的位置即可。类似地可得后代o2。

例4-5 给定下列两个父体：

p1=(2 6 4| 7 3 5 8| 9 1)

p2=(4 5 2| 1 8 7 6| 9 3)

先从p1 中取第一个城市2作为o1 的第一个城市得：

o1=(2 # # # # # # # #)

p1 中城市2对应p2 中城市4，而4还没有填入到o1 中，将4填入到o1 中与其在p1 中相应的位置得：

o1=(2 # 4 # # # # # #)

p1 中城市4对应p2 中城市2，但2已经填入到o1 中了，这完成了一个循环。将p2 中尚未在o1 中出现的城市直接填入到o1 中与其在p2 中相应的位置得：(www.xing528.com)

o1=(2 5 4 1 8 7 6 9 3)

类似地可得：

o2=(4 6 2 7 3 5 8 9 1)

4）基于位置杂交

基于位置杂交类似于次序杂交，唯一的区别在于：在基于位置杂交中，不是选取父体的一个连续的子序列，而是随机地选取一些位置，再按次序杂交的方式产生后代。

例4-6 给定下列两个父体：

p1=(2 6 4| 7 3 5 8| 9 1)

p2=(4 5 2| 1 8 7 6| 9 3)

假定随机选取的位置为2、3、6、8。保留p1，p2 中在这些位置上的城市得：

o1=(# 6 4 # # 5 # 9 #)

o2=(# 5 2 # # 7 # 9 #)

然后从最后一个选取的位置开始，将p2 中的城市按原次序列出得：

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

从中删除o1 中间段中的城市得：

3-2-1-8-7

将该子序列从最后一个位置之后开始依次填入到o1 中得：

o1=(2 6 4 1 8 5 7 9 3)

类似地可得：

o2=(6 5 2 4 3 7 8 9 1)

除了上述杂交算子外，文献中出现了许多其他的杂交算子，在此不一一叙述。

2.变异算子

1）倒位变异

对一个个体进行倒位变异的过程如下：首先个体上随机地选择两个城市，然后将这两个城市之间的城市子序列反转。

例4-7 设有个体：

(1 2 3 4 5 6 7 8 9)

假定随机选择的两个城市为3、7，则对该个体进行倒位变异后得：

(1 2 7 6 5 4 3 8 9)

2）插入变异

对一个个体进行插入变异的过程如下：首先在个体中随机地选择一个城市，然后将该城市插入到某个随机的位置上。

例4-8 设有个体：

(1 2 3 4 5 6 7 8 9)

假定随机选择的城市为2，随机地选择位置为6，那么将城市2插入到第6个位置上得：

(1 3 4 5 6 2 7 8 9)

要注意的是，当将所选择的城市插入到所选择的位置上时，有两种城市移动方式。若所选择的城市在要插入的位置的左边，则所选择城市到插入位置之间的城市（包括插入位置上的城市）向左移动1个位置，否则向右移动1个位置。

3）移位变异

对一个个体进行移位变异的过程如下：首先在个体中随机地选择一个连续子序列，然后将该子序列插入到某个随机的位置上。将子序列插入到所选择的位置上时，有两种插入方式，一种是将子序列的第一个元素插入到所选择的位置上，另一种是将子序列的最后一个元素插入到所选择的位置上。

例4-9 设有个体：

(1 2 3 4 5 6 7 8 9)

假定随机选择的子序列为4 5 6，随机选择的位置是7，那么经移位变异后，得：

将4插入到所选择的位置→（1 2 3 7 8 9 4 5 6）

将6插入到所选择的位置→（1 2 3 7 4 5 6 8 9）

4）互换变异

互换变异是指随机地选择两个城市，并将这两个城市互换。

例4-10 设有个体：

(1 2 3 4 5 6 7 8 9)

随机选择的两个城市为3、7，那么经互换变异后得：

(1 2 7 4 5 6 3 8 9)