程序代码里的“遗传”

陈凯

遗传算法是一种计算模型，它模拟了达尔文的生物进化理论：针对特定问题构造一个环境及一组“基因”不同的个体，根据优胜劣汰原则，对符合繁衍条件的个体，借助组合交叉、随机变异等方法，产生出拥有和前辈有相似之处，但又略有变化的“基因”新个体，一代代遗传变异后，生存下来的个体的“基因”，其实就是问题较优的解答。

● 有趣的遗传算法演示案例

笔者在网络上找到了一些有趣的遗传算法实施案例，有一些还提供了源代码下载。

1.Flappy Bird（https：//github.com/ssusnic/Machine-Learning-Flappy-Bird）

Flappy Bird的玩法可能大家都不陌生，在这个程序中（如图1），十只鸟一起以波浪状飞行试着穿过树丛缝隙，在Game Over时，表现最好的四只鸟将包含有自己的行为模式的基因略加变异或者交叉组合后传到下一代。最终，程序生成的鸟的飞行精确性远超人类。

2.牧场（http：//math.hws.edu/eck/js/genetic-algorithm/GA.html）

牧场上的绿色植物（小方块）不完全是随机生长的（如图2），而是依赖某个群体逐渐往外扩展，刚开始的时候，牧场上的动物（T形）几乎是随机行走的，因此要花费很长时间才能遇见食物，随着这些动物的一代代进化，它们开始变“聪明”了，能越来越快地找到食物。

3.迷宫（https：//code.msdn.microsoft.com/Genetic-algorithm-for-2D-74dd9e10）

从迷宫的某处通往另一处有很多条路（如图3），哪条路最短呢？这个程序在走廊里设置多处“假墙”来限定行走路径，那么如何设置假墙才最有效呢？这就要靠一代代的遗传进化了。

● 简易遗传算法流程的实证

虽然上述程序代码的演示有趣、直观，但问题是这些遗传算法实施项目的代码实在太长，学习者没有办法在短时间里读懂，也就难以体会到遗传算法的设计要点。笔者希望能有这样一个例子：①任务情境要简单，尽量少涉及其他学科的知识；②代码要尽可能简单；③项目要有趣直观；④问题的解答必须是借助算法实现的，而不是靠人力能推演出来；⑤要能给学习者一定的参与性。因为无法在网络上找到符合以上要求的例子，所以笔者决定自己设计一个项目。该项目是让某“生物”在迷宫中行动，目标是让某生物个体尽可能长时间地留在迷宫中（这个目标比快速离开迷宫更有趣）。最后，笔者用Python编写了半个遗传算法程序，用来描述遗传算法的大致实施过程。

1.项目情境设置

该项目名为“一维生物的迷宫”，把二维迷宫变成一维迷宫，是为了简化环境的构造。迷宫由五种符号构成，分别是“[”“]”“#”“|”“_”，分别表示左边界、右边界、一型栅栏、二型栅栏、石板路。当迷宫中的生物从左往右行走时用“c”表示，从右往左行走时用“@”表示。开始时，生物位于迷宫正中，周围放置若干栅栏，整个迷宫环境可用一个字符串表示：[____#_#_________c_______|_|__ _________]。

可见，生物左侧有两个一型栅栏，右侧有两个二型栅栏、生物碰见栅栏后的行为预设了若干种，大致是跨越并摧毁栅栏、跨越并修好栅栏、被栅栏撞向反方向等。生物的行为可用简单的字符串替换来实现。例如，可以把“c#”替换成“_c”，表示朝右跨越并摧毁栅栏（栅栏变成了石板路）。又如，可以把“c|”替换成“@|”，表示碰撞栅栏被迫改变方向。大家应该能发现，简单的行为模式组合在一起，也能有各种复杂的效果。至于生物个体究竟擅长怎样的行动，这是随机决定的。

至于生物的行走，也可以用两个简单的替换来进行，把“c_”替换成“_c”，它就能向右走，将“_@”替换成“@_”，它就向左走。

2.初始个体的生成

首先生成十个个体，每个个体都由随机函数得到一串有十位数字的“基因”，每一位数字代表一种行为，生物行动前（被替换字符串）的状态存放在be数组中，行动后的状态（替换字符串）存放在af数组中，代码只是看上去比较长，其实相当简单，其功能就是按随机数设置字符串替换规则，走石板路的两条规则，即把“c_”替换成“_c”，把“_@”替换成“@_”为必选规则，因此不受随机函数影响（如上页图4）。

除了走石板路的两条规则，其他行动规则按随机值分成三个档次，0号到2号行动规则出现机会最少，3号到5号出现较多，6号到9号出现最多。上页图5的循环结构，目的就是借助替换规则，让迷宫中的生物动起来。

代码运行时，可以看到生物体在迷宫中乱窜（如上页图6）。

至于包含有生物个体行动特征的基因，被保存在gene.txt文档中，该个体行动的效果，则被保存在result.txt文本中，实现方法很简单，在程序开头用代码设置需要读写的文件：

input=open（d：/gene.txt）

output=open（d：/result.txt，a）

在每个个体行动结束后，将结果保存到文件中：

output.write（actstr+ +str（steep）+ +str（i））

output.write（＼n）

为了让学习者有充分的参与感，同时也为了项目实施的代码足够简单，调整基因这一环节，是由人而不是由程序代码实施的，所以程序自身并不向gene.txt文件输出内容。

3.遗传和变异

打开result.txt文件，可以看到數据分为三栏，第一栏是随机生成的十条基因，第二栏是生物个体在迷宫中行走的步数，第三栏是生物个体到达迷宫边缘时的时间值，但若时间值达到最大点200，则说明该个体有可能“僵死”在迷宫中。所以优秀的基因是第三栏数字未达到200，而第二栏数字比较大的基因。实际上，真正优秀的基因在迷宫中行动时间可以很长，200这个数值的设置，只是为了程序调试和演示上的方便（如图7）。endprint

然后，就可以自己制订遗传规则了。例如，先手工选出前三条优秀基因，即1959027339、0034334533和2115520901，这三条基因保持原样继承到下一代；接着将最优秀的基因首位数字放到末尾，得到基因9590273391继承到下一代；然后将三条基因每条前两位数字放到末位后，得到5902733919、3433453300和1552090121，继承到下一代；最后杂交三条优秀基因，生成三条新的基因继承到下一代，杂交方法是将第一条基因的末两位数给第二个基因，第二条基因的末两位数给第三个基因，第三条基因的末两位数给第一条基因，然后再取一个字符串中出现最少的数字，替换掉这三条基因的倒数第三位数，得到1959027601、0034334639和2115520633。把新得到的十条基因保存到gene.txt文件中。

这里只是用了比较机械的方法来调整基因。在实际操作时，调整方法可以有很多种。例如，考虑以下基因变化策略：首先选出当前表现最优秀的基因，然后找出在这些基因里出现最多的两种数字，将某个数置换掉当前基因的前半部分的某一位，将另一个数置换掉当前基因的后半部分的某一位，反复操作后，基因中的数字种类会逐渐变少。这样的基因变化策略就要比先前的机械方法有效，原因是，为使得后代生存时间更长，某些低效的数字（对应跨越并破坏栅栏的行为）要尽量被剔除掉，但有些数字又是必须存在的（若完全不破坏栅栏，生物个体会僵死在迷宫中）；与此同时，还要想办法尽可能把对生物个体行走起到阻碍作用的替换规则放到高概率区域。当然，对遗传算法来说，它并不会真正去想办法，而只是把表现不佳的基因给踢出局了。

接下来，只要对先前的程序稍做修改，把随机生成基因的部分，改成從gene.txt文件中读取基因，就可以再一次运行程序，验证第二代个体乃至更多代个体的行动效果了（如第34页图8）。

可以看出，4376041569这条基因在迷宫中走了197步。为什么这条基因的效果那么好？如何才能得到更好的基因呢？若只看程序运行过程与结果，而不看程序代码，一时半会儿是无法推断出来的。所以，对代码运行后数据的分析，仿佛真的变成了科学研究（如第34页图9）。

● 更多探索

以下几个问题值得深入探索：①本案例所构建的替换规则还是很简单的，由于几个替换事件之间不存在因果关系，因而就无法体现出遗传算法在执行效率上的优势来，为了使得迷宫环境充分体现出遗传算法的效率，就要让不同的替换事件之间呈现树状关联的结构。②本文采用的手动基因编辑方法虽然简单，但无法处理稍微复杂一些的数据，若要使本项目成为真正有用的遗传算法，终究还是需要编写与杂交和变异有关的代码。③由于替换规则受随机作用影响，某些优秀基因无法传到下一代，如能回溯一代或几代查看基因记录，就更有利于优秀基因片段的传承，这就涉及遗传算法中的精英保留策略。④只要能识别出基因片段的作用，人工干预的基因编辑就必然强过随机编辑，那么，怎样将人工的干预和识别，也变得自动化呢？希望有兴趣的读者能将研究继续下去。endprint