市,构成一个完全图,任何两城市之间都有一个代价(例如路程、旅费等),现要构造遍历所有城市的环
路,每个城市恰好经过一次,求使总代价达到最小的一条环路。
遗传算法是求解该问题的一个很有效的近似算法。在该算法中,一个个体为一条环路,其编码方法
之一是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)输出两个新个体的编码。
程序:
#include <iostream.h> #include <stdlib.h> #define N 20 int a1[N], a2[N], kz1[N], kz2[N], n; int rand1(int k) { int t = 0; while (t < 2 || t > k) t = (int) ((double) rand( ) / RAND_MAX * k); return t; } void read1(int a[], int m) { 读入数组元素a[1] 至a[m],a[0] = 0,略。 } void wrt1(int a[], int m) { 输出数组元素a[1] 至a[m],略。 } void cross(int a1[], int a2[], int t1, int t2, int n) { int i, j, t, kj; for (i = t1; i <= t2; i++) { t = a1[i]; 1 ; } for (i = 1; i <= n; i++) if (i < t1 || i > t2) kz1[i] = kz2[i] = -1; else 2; for (i = t1; i <= t2; i++) for (j = t1; j <= t2; j++) if (a1[i] == a2[j]) { 3; break; } for (i = t1; i <= t2; i++) if (kz1[i] == 1) { for (j = t1; j <= t2; j++) if (kz2[j] == 1) { kj = j; break; } for (j = 1; j <= n; j++) if ( 4 ) { a1[j] = a2[kj]; break; } for (j = 1; j <= n; j++) if ( 5 ) { a2[j] = a1[i]; break; } kz1[i] = kz2[kj] = 0; } } void main( ) { int k, t1, t2; cout << "input (n>5):" << endl; cin >> n; cout << "input array 1 (" << n << " numbers):" << endl; read1(a1, n); cout << "input array 2 (" << n << " numbers):" << endl; read1(a2, n); t1 = rand1(n - 1); do { t2 = rand1(n - 1); } while (t1 == t2); if (t1 > t2) { k = t1; t1 = t2; t2 = k; } 6; wrt1(a1, n); wrt1(a2, n); }