清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.交叉 简单的交叉操作分两步实现。第一步是将新复制产生 的位串个体随机两两配对；第二步是随机选择交叉点，对 匹配的位串进行交叉繁殖，产生一对新的位串。具体过程 如下：设位串的字符长度为l,在1,1一1]的范围内，随机 地选取一个整数值k作为交叉点。将两个配对串从第k位右 边部分的所有字符进行交换，从而生成两个新的位串。例 如，在表6-2中，已知位串的字符长度1=5，随机选取=4， 对两个初始的位串个体A,和A,进行配对，交叉操作的位置 用分隔符“1”表示为： A,=0110|1 A,=1100|0 交叉操作后产生了两个新的字符串为： A1'=01100 A,=11001
2. 交叉 简单的交叉操作分两步实现。第一步是将新复制产生 的位串个体随机两两配对；第二步是随机选择交叉点，对 匹配的位串进行交叉繁殖，产生一对新的位串。具体过程 如下：设位串的字符长度为l，在[1，l－1]的范围内，随机 地选取一个整数值k作为交叉点。将两个配对串从第k位右 边部分的所有字符进行交换，从而生成两个新的位串。例 如，在表6-2中，已知位串的字符长度l=5，随机选取k=4， 对两个初始的位串个体A1和A2进行配对，交叉操作的位置 用分隔符“|”表示为： A1=0110 | 1 A2=1100 | 0 交叉操作后产生了两个新的字符串为： A1 ’=01100 A2 ’=11001
清华大学出版社 TSINGHUA UNIVERSITY PRESS 一般的交叉操作过程可用图6-2所示的方式进行。 交叉前 交叉后 串1： a2 ay uA a a2bb4b5新申1 图6-2交叉操作 串2： b b be as a445新申2 遗传算法的有效性主要来自于复制和交叉操作。复制操作虽然能 够从旧种群中选择出优秀者，但不能创造新的个体；交叉操作模拟生 物进化过程中的繁殖现象，通过两个个体的交换组合，来创造新的优 良个体。 表6-3列出了交叉操作之后的结果数据，从中可以看出交叉操作 的具体过程。首先，随机配对匹配集中的个体，将位串1、2配对，位 串3、4配对；然后，随机选取交叉点，设位串1、2的交叉点为仁4， 二者只交换最后一位，从而生成两个新的位串，即 01180-81089 新串1 新串2
一般的交叉操作过程可用图6-2所示的方式进行。 遗传算法的有效性主要来自于复制和交叉操作。复制操作虽然能 够从旧种群中选择出优秀者，但不能创造新的个体；交叉操作模拟生 物进化过程中的繁殖现象，通过两个个体的交换组合，来创造新的优 良个体。 表6-3列出了交叉操作之后的结果数据，从中可以看出交叉操作 的具体过程。首先，随机配对匹配集中的个体，将位串1、2配对，位 串3、4配对；然后，随机选取交叉点，设位串1、2的交叉点为k=4， 二者只交换最后一位，从而生成两个新的位串，即 图6-2 交叉操作 2 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 2 1 新串 新串 串 ： 串：
清华大学出版社 TSINGHUA UNIVERSITY PRESS 位串3、4的交叉点为k=2,二者交换后三位，结果生成两 个新的位串，即 00999-06860 表6-3交叉操作之后的各项数据 复制后的匹配池 配对对象 交叉点 新患号 (“|”为交叉点) (随机选择) (随机选择) 新种群 x值 I(x)=x' 1 0110|1 2 4 01100 12 144 2 110010 1 4 11001 25 625 3 11|000 2 11011 27 729 101011 2 10000 16 256 总计 1754 平均 439 最大值 729
位串3、4的交叉点为k=2，二者交换后三位，结果生成两 个新的位串，即 4 3 1 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0 1 0 1 1 4 3 新串 新串 串 ： 串 ：
清华大学出版社 TSINGHUA UNIVERSITY PRESS 单纯交叉与多点交叉 上述例子中交叉的位置是一个，称为单纯交叉，或称 单点交叉。即指个体切断点有一处，由于进行个体间的组 合替换生成两个新个体，位串个体长度为时，单点交叉 可能有1一1个不同的交叉。 多点交叉是允许个体的切断点有多个，每个切断点在 两个个体间进行个体的交叉，生成两个新个体，在2点交 叉时，可能有一2)×（一3）个不同的交叉。多点交叉又称 复点交叉
单纯交叉与多点交叉 上述例子中交叉的位置是一个，称为单纯交叉，或称 单点交叉。即指个体切断点有一处，由于进行个体间的组 合替换生成两个新个体，位串个体长度为l时，单点交叉 可能有l－1个不同的交叉。 多点交叉是允许个体的切断点有多个，每个切断点在 两个个体间进行个体的交叉，生成两个新个体，在2点交 叉时，可能有(l－2)×(l－3)个不同的交叉。多点交叉又称 复点交叉
清华大学出版社 TSINGHUA UNIVERSITY PRESS 3.变异 尽管复制和交叉操作很重要，在遗传算法中是第一位的，但不能保证 不会遗漏一些重要的遗传信息。在人工遗传系统中，变异用来防止这 种不可弥补的遗漏。在简单遗传算法中，变异就是在某个字符串当中 把某一位的值偶然的（概率很小的）随机的改变，即在某些特定位置 上简单地把1变为0，或反之。当它有节制地和交叉一起使用时，它就 是一种防止过度成熟而丢失重要 表6-4随机种群 概念的保险策略。例如，随 机产生一个种群，如表6-4所示。在 编号 位串 适值 该表所列种群中，无论怎样交叉， 1 01101 169 在第4位上都不可能得到有1的位串。 2 11001 625 若优化的结果要求该位串中该位是1， 3 00101 25 显然仅靠交叉是不够的，还需要有变 异，即特定位置上的0和1之间的转变。 11100 784
3. 变异 尽管复制和交叉操作很重要，在遗传算法中是第一位的，但不能保证 不会遗漏一些重要的遗传信息。在人工遗传系统中，变异用来防止这 种不可弥补的遗漏。在简单遗传算法中，变异就是在某个字符串当中 把某一位的值偶然的（概率很小的）随机的改变，即在某些特定位置 上简单地把1变为0，或反之。当它有节制地和交叉一起使用时，它就 是一种防止过度成熟而丢失重要 概念的保险策略。例如，随 机产生一个种群，如表6-4所示。在 该表所列种群中，无论怎样交叉， 在第4位上都不可能得到有1的位串。 若优化的结果要求该位串中该位是1， 显然仅靠交叉是不够的，还需要有变 异，即特定位置上的0和1之间的转变