遗传算法/格雷码

在遗传算法中, 算法不直接对物种的表现型(即实际的决策变量)做操作, 而是对决策变量的个体编码施加选择, 交叉和变异等遗传算子, 通过这种操作来达到优化的目的. 我们将实际的决策变量转换为遗传算法所能处理的搜索空间的转换方法就成为编码. 例如, 在前一篇文章中, 为了求得 f(x)=sin(10x) * x + cos(2x) * x 在 [0, 5] 区间内的最大值, 将决策变量 x 转换为从 0000000000 到 1111111111 的 10 位二进制编码的步骤就是一种编码.

编码的反向算法就是解码, 它将基因型重新转换为表现型, 以此才能进行适应度计算. 编码/解码是设计遗传算法的第一个步骤, 它很大程度上决定了算法的有效性和效率. 目前来说, 最通用的编解码方式是二进制编解码, 也就是将决策变量编码为 01 字串. 它的优点如下:

编解码操作简单易行.
包含最大的模式数, 遗传算法在确定规模的种群中能够处理最多的模式.
极易为其设计各种不同的选择, 交叉和变异算子.
容易对算法进行理论分析.

二进制编码由符号 0 和 1 组成, 它所构成的个体基因型是一个二进制编码字符串. 二进制编码符号串的长度和求解的精密度有关, 例如决策变量 x 范围为 0 到 5, 我们若用长度为 l 的二进制编码符号来表示该参数, 则它总共能产生 2^l 种不同的编码, 它将决策空间平均分成了 2^l 份. 举个栗子, 当 l 等于 10 时:

基因型	表现型
0000000000	0.000000000000000000
0000000001	0.004887585532746823
0000000010	0.009775171065493646
...	...
1111111110	4.995112414467253000
1111111111	5.000000000000000000

在生物学中, 基因型相似的生物也拥有相似的表现型. 但是观察二进制编码, 却容易发现一个问题: 连续的基因型可以拥有差别很大的表现型. 例如, 上题中, 基因型 0000000000 对应的表现型是 0.00, 基因型 1000000000 对应的表现型却是 2.49, 它们之间整整跨越了半个搜索空间, 而基因却仅仅只相差一位! 正是这种特性导致二进制编码的局部搜索能力较差. 为改进这个特性, 贝尔实验室的弗兰克·格雷人们提出了使用格雷码. 格雷码是由在 20 世纪 40 年代提出, 并在 1953 年取得美国专利 pulse code communication. 最初目的是在使用 pcm 方法传输数字信号的过程中降低错误可能. 格雷码还有许多其它不同的名字, 例如循环码或反射码.

格雷码最大的特征是任意两个相邻数的编码只有一位不同. 十进制数 0~15 之间的二进制编码与格雷码分别如表所示.

十进制数	二进制码	格雷码
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

格雷码与二进制码之间的转换极其简单, 公式可以用如下代码表示:

// 二进制到格雷码
func GraycodeEncode(x uint64) uint64 {
    return x ^ (x >> 1)
}

// 格雷码到二进制
func GraycodeDecode(x uint64) uint64 {
    x ^= x >> 32
    x ^= x >> 16
    x ^= x >> 8
    x ^= x >> 4
    x ^= x >> 2
    x ^= x >> 1
    return x
}

作为二进制编码的一种变形, 它在拥有二进制编码的全部优点的同时, 还额外有更优的局部搜索能力. 大多数情况下, 在可以使用格雷码的前提下我们总是应该使用格雷码.