如何将进化计算的过程可视化？

进化算法和遗传程序本质上是不断寻找和优化问题的答案。为了看清这个过程中发生了什么，想象由某个问题的所有可能解答组成的一个抽象多维空间，每个可能的解答都是这个空间中的一个点。这种空间通常都大得难以想象，但是可以通过所谓的适应性地形来大致地可视化，适应性地形用3维地貌来显示问题的大量可能答案的值或某个性质。1932年休厄尔·赖特首次提出用这种图形帮助阐释生物系统的进化。它对进化算法尤为适用。图6.9给出了一个简单的数学函数的3维图，这个函数因为显而易见的原因有时候被称为“山峰函数”。这幅图通过显示与x和y值对应的z值，让我们可以看见方程的解空间。

图6.9 z=1/（x2+y2+1），“山峰函数”的3维图像。感谢丹·阿什洛克提供图片

无论代入的x和y值是多少，z的最大可能值是1。这可以用微积分或进化算法证明。进化算法并不知道解微积分问题，但有把握找到这个方程的最大值在哪里。这个算法创建一个猜测的“群体”，分别进行评估，选择最好的（最大的值），然后在最好的猜测“附近”创建一个可能答案的新群体。我们用算法的一次运行输出来说明这个过程，这个算法维持20个猜测值组成的群体。每个猜测值都是一对x和y值。为了简明只给出了每一轮生成的20个猜测值中的5个，并且只保留了两位有效数字（小数点后第1个非0值的后两位）。表6.3给出了运行过程。只显示了第1、第3、第4、第5和第7回合。每轮最好的猜测（最高的z值）用粗体显示。初始猜测介于1000和-1000之间，随后的猜测限制在4倍于最好猜测大小的区间内。例如，如果某回合y的最好猜测是3，则下一回合猜测的y在-3到+9之间随机选取。z值越大，答案越好。可以注意到每回合的z值都比前一回合更接近1.0。这次运行到第8回合时（没有显示），z的值到了0.998，舍入为1.0。如果不舍入，要达到正确的1，需要100多回合。

表6.3 搜索山峰函数最大值过程中进化算法生成的一些值

再看图6.9，可能的答案就好像散布在区域地形上，最好的答案位于山顶。最初的猜测没有哪个特别靠近山顶，但有一个比其他的更好。下一回合就在第一轮的最佳答案附近进行猜测。这回又会有一个比其他猜测更接近理想答案。只用了5个回合，就找到了“答案”0.94，到第7回合，就找到了0.990。这个算法要很久才能找到正确答案，但一定能找到。

无论是哪种进化算法，都要在（解空间中）目前已知的最佳猜测的附近进行猜测；如果不这样就没有什么机会获得稳定的改善。如果不限制在最佳猜测的临近区域，算法就变成了纯粹的随机猜测，而大部分问题都基本不可能通过随机猜测找到好的答案，因为这些问题的解空间都很大。对于山峰函数，需要上百万次随机猜测才能找到最佳答案，而进化算法只需不到200回合，而且从上面的例子可以看到，算法只用了5个回合就找到了一个相当不错的答案（0.94），虽然找到最佳答案的回合数要多得多。

山峰函数与很多问题都有一个共同的特点，大部分可能的答案都离峰顶很远，但在任意特定答案的邻域中，几乎有一半答案比当前答案更接近峰顶。因此，只要将猜测限制在上次猜测的邻域，就几乎总是有新的猜测会有所改进，搜索也就可以推进到越来越好的答案。而如果不对搜索进行约束，绝大部分猜测都不会比当前的猜测好。只有当可能的答案数量或搜索空间足够小，全局搜索才有可能成功。要让进化算法能顺利工作，每个回合或多个回合中至少要有一个答案在山坡上爬得更高。通过不断往更好的答案推进，才能最终发现峰顶的最佳答案。

山峰函数很容易用遗传算法解决，因为其形状很光滑。许多问题都没有这么简单。解空间经常会有许多峰和谷。图6.10给出了一个假想的例子。这种情况下进化算法很容易陷入一个低矮山峰，永远也找不到最高峰。前面说过，几乎所有解空间都是多维的。图6.9和6.10显示的是2维解空间（x-y平面）。10位的最大1问题的字串解有10维解空间。1000比特位的串则需搜索1000维空间。高于3维的空间没法画出来，因此图6.10只是对高维解空间的一个有用但并不完美的想象。

图6.10 由许多峰谷组成的2维适应地形。每个峰都是一个局部最优的答案，谷则代表了糟糕的答案。对于进化算法来说找到一个山峰很容易，而要找到最高峰则通常很难