近邻表示在路线问题中的应用

近邻表示将一条周游路线表示成n 个城市的一个排列，第i 个城市为j，当且仅当回路中从城市i到达的下一个城市为城市j。

例4-1 排列：

(2 4 8 3 9 7 1 5 6)

表示回路1-2-4-3-8-5-9-6-7-1。

显然，每一条回路都唯一地对应一个近邻表示，但任一近邻排列却不一定都对应于合法回路。这是因为n 个顶点的回路有（n-1）！ （不考虑对称性）条，而n 个顶点的近邻排列有n！ 个的缘故。例如，排列：

(2 4 8 1 9 3 5 7 6)

导致了不完全回路1-2-4-1。

传统的杂交算子不适用于近邻表示。下面介绍几种为近邻表示设计的杂交算子。

（1）交替边杂交：这种算子产生后代时，首先随机地从第一个父体中选取一条边，再从第二个父体中选取一条适当的边，如此交替进行，使得所选择的边扩展成一条合法的回路。若从某父体所选择的边导致当前路径构成一条子回路（即不包含所有顶点的回路），则从不构成子回路的剩余边中随机地选择一条边。(www.xing528.com)

例如，给定下列两个父体：

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

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

则一个可能的后代为：

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

该后代首先从p1 中选择边（1，2）开始，然后交替地从p2 中选择边（2，5），从p1 中选择边（5，9），从p2 中选择边（9，3），从p1 中选择边（3，8），从p2 中选择边（8，4），从p1 中选择边（4，7），这时若从p2 中选择边（7，8），则导致子回路8-4-7-8，故从与7关联且不构成子回路的边中随机地选择一条边（7，6），然后继续从p1 中选择边（6，1），这时所选择的边构成一合法回路，即得后代o1=（2 5 8 7 9 1 6 4 3）。

（2）子回路块杂交：该杂交算子与交替边杂交类似，所不同的是，不是每次交替地从一个父体中选择一条边，而是选择一条随机长度的子路径。同样地，若选择的某条边构成子回路，则从不构成子回路的剩余边中随机地选择一条边。

（3）启发式杂交：该杂交算子首先随机地选择一个城市作为起始点，再比较两父体中与该城市相连的几条边，选择其中最短的边，并将所选择边的另一端作为新的起始点。如此反复进行，直到产生一条合法的回路。如果选择的边导致一条子回路，则从不构成子回路的剩余边中随机地选择一条边。