程序代码里的优选实验

陈凯

算法对世界的巨大改变无可否认，然而对于知识技术水平有限的初学者来说，某些算法具体实现的复杂性确实令人望而生畏，即便大致了解了某个著名的算法的基本原理，或者在工作、生活中使用到了该算法的成果，也很难从代码实现的角度去体验、实证算法的作用，更遑论要结合实际问题做需求分析并编写出有实用价值的程序了。以遗传算法为例，它涉及到情境创设、基因编码、适应度函数评分、选择函数设置、基因重组、基因变异等诸多步骤，且每个步骤都对应着相当多的程序代码量，教学者的任务一方面是尽量尝试设计简单有趣的任务情境，另一方面是将复杂的算法自顶向下分解成小任务，通过每个小任务的编码实证，让学习者体会这一段代码所体现出来的思想方法。上一期文章《程序代码里的遗传》所介绍的内容重点在于如何将情境创设和基因编码过程变得有趣形象，本期文章所介绍的活动内容，是在人工干预的条件下，让随机图形变得越来越像某种图形，重点在于如何将基因重组变异的过程直观显现出来。

为了简单起见，笔者在本文的例子中，用8×8的点阵组成简单的图形，希望借助人工选择，使得初始的随机生成图形一代代产生变化，并越来越像某个数字。例如，一开始的时候，图形可能是如图1所示的样子。

然后，下一代图形会在上一代图形的基础上发生变化，在逐代人工优选操作下，图形变得越来越像数字“2”（如图2）。

代码作用概述

实验中被栽培的“物种”个体就是这个由8行8列星号组成的图形（注意并不是每个星号都代表一个个体），该物种个体生长的模样和它的基因有关，为了简化问题，笔者直接用一个64位由空格和星号组成的字符串代表基因，图形生成也很简单，只要将作为基因的每8个字符换行打印即可。

从上页图3代码中可以看出，物种个体基因的64个字符完全是随机生成的。seed函数的作用是生成不同的随机种子，实验时，也可以改变seed函数的参数来得到不同的随机序列；randint函数的作用是生成具体的随机整数，括号里的参数是0和1，于是得到的随机数不是0就是1；arr数组的作用是存放10个不同个体的基因。最后，用print语句将字符串以数组的形式，分8行打印出来，打印出的图案如上页图4所示。

这10个图案的形状完全是随机的，可以借助人工选择操作来有倾向性地改变它们后代的模样。虽然说真正的遗传算法需要进行适应度评分，但本文例子的重点是观察遗传变异中物种的演化，所以就以人工选择的方式来大幅度简化问题。假如生成图形的最终目标是“3”，那么可以优选两个看上去已经具备有发展成“3”潜质的图形，如图4中的2号个体图形和9號个体图形，选择完成后，程序代码会将这两个个体的基因进行混合。

从图5代码中可以看出，两个基因混合的方法也很简单，如果两个基因的同一位字符是相同的，那就继续继承这个字符，如果两个基因的同一位字符不同，那就以各百分之五十的概率，随机生成一个字符。通过这个方法得到0号个体并打印出来（如图6）。

新一代的0号个体是2号个体和9号个体的后代，这个0号个体看上去有点像数字“5”而不是数字“3”，不过没有关系，我们还能以这个个体为蓝本，生成另外9个变异的个体，变异方式也是随机。

为了能够在教学中将基因重组和变异两个概念分别讲述，案例中重组和变异的代码明显分成两段，实际上，变异也可以直接在基因重组时发生，那样就更接近现实中的遗传变异现象。从图7代码中可以看出，大部分的基因会按原样继承下去，但小部分基因，存在一定概率发生变异。想象一下，如果没有变异现象，那么每个个体都会被固化在初始的形状中，这样也就失去了进化的可能。

另外，下一代个体的变异最好要具有一定差异，从而能呈现出多样性的发展。为了能够体现变异的差异性，此处做了一个十分简单的设定：从1号个体到9号个体，编号小的个体基因中空格多，而编号大的个体基因中星号多（如下页图8）。

接下来，就可以反复人工选出两个最优个体，让它们繁殖生成下一代。

用以体验遗传算法的代码就此完成，笔者用它来生成了四个不同的数字（如下页图9）。

实践、思考与讨论

围绕实现算法的代码，可以安排一些有趣的实验，考虑到凭空编写代码难度太高，可以引导学习者修改部分代码并验证效果。例如，可以将点阵扩大，或者一次繁殖生成更多的个体，让实验者能够选出多个优秀个体来进行基因重组和变异。

下面几个问题，就值得投入更多时间去思考，相关实验也涉及到更多的代码改编量，可以作为研究性、探究性学习的内容。

首先，实验者可能发现，一个问题是用这段代码生成直线图案（如数字1或者7）非常困难，由于随机变异的作用，图案的边缘很难做到平滑齐整，不是这里多一块，就是那里少一块，本文的案例中，图案本质上是由一维字符串直接对应生成的，若要让遗传变异生成平滑齐整的边缘，就不得不考虑每一点与上下左右其他点的关系；另一个问题是每次变异都是以一个点为单位取随机值，而不是以一块区域为单位取随机值，但一维的数据很难对应图形中的某一块区域。以上两个问题，都需要引入二维数组来解决。

其次，对于某些图案，如数字或字母图案，空白区域和涂黑区域的分界是很明显的，图案中的点最好是要么聚集在一起，要么不要出现，然而案例中的代码却无法实现这样的需求。例如，图10中的数字“5”，就因为右上侧多了一点而不完美。

尽管它的下一代还会变异，然而即便这个多余的点消失了，其他空白处仍然有一定概率冒出不合适的点来。所以有必要改变代码，让点的生成和消失与周边点存在一定依赖，从而使得某些区域的图案保持更多稳定性；然而，为了在变异中获得一定的多样性，又要允许某些个体的区域变化有比较大的随意性。两者如何平衡，是个很大的研究课题。

最后一个问题大概是最重要的：如果没有人工选择，计算机怎样才能知道哪些图案更像数字？这其实是在问，怎么编写一个适应度函数，让那些看上去像数字的图案评分更高？对于这个问题，最简单的处理方法是，预先建立一个数字图案的点阵，借助代码逐个比对各个像素是否相同，由此给出适应度评分。但仔细一想，却发现这样做除了可以作为算法设计及代码编写训练的实例外，没有什么现实价值，因为既然图案已经被规定好了，又为什么要让遗传算法再费时费力地去生成相同的图案？人们的真实需求，大致是希望代码能自动识别出图形中的数字吧。然而，这个问题不是单纯的遗传算法能够解决的，它和图像识别、大数据等领域的知识产生了关联，等待着怀有好奇心的学习者去深入探索研究。endprint