|
功能丰富的 Perl： Perl 用于实现遗传算法 |
|
![]() |
|
|
|
您查看的文章来源于http://www.oklinux.cn
如果您的机器上已经安装了 Perl 5.005 或者更高的版本，您可以运行一下文章中的例子。您的系统最好应该是安装了最近的（2000 年或者更迟些）主流的 UNIX（Linux，Solaris，BSD），但其它种类的操作系统可能也可以。文中的例子可能可以在更老的版本的 Perl、UNIX 以及其它操作系统下运行，但是如果不行的话，读者应当把它看作是一次练习来解决。
历史
进入 20 世纪以来，在速度和影响范围方面遗传学的发展只有电子学和计算机科学能与之相比。遗传算法是 20 世纪出现的最令人感兴趣的算法之一，这一说法是恰当的。
遗传算法（以及普遍意义上的进化算法）出现在 20 世纪 60 年代早期，并在计算机科学的确定性和非确定性算法之间占据了一席之位。本质上，遗传算法具有如同您所希望的那样的确定性，意味着用户可以决定重复次数和结束条件。它模拟达尔文的自然选择，还有变异，把“适应性”（正如适用于个体的公式所决定的那样）作为主要因素选择生存繁衍和变异的个体。
其它的进化算法试图模拟拉马克的进化论，在他看来，行为是一种生存的机制，可以在两代之间传递，甚至有一些进化程序是出于某种目的而自然出现的。以上这些都不在本文的论述范围之内。
Perl 用于实现遗传算法的主要缺点在于速度慢。由于遗传算法的计算需要，用 C 语言或其它低级的预编译语言来实现效率会更高。本文展示的 Perl 例程不如其 C 语言的等价程序快，但是可以使您明白遗传算法是如何工作的，况且，对于一些问题来说，已经够快了。
那么什么是遗传算法呢？
遗传算法是如此简单，任何人只要用高中时学过的生物术语就可以理解。以一群个体为例，它们都有自己的 DNA。然后衡量每一个个体的适应性（把它看作是适用于个体的 DNA 的官能来衡量），并且使那些更适应的个体更有可能繁衍。而最不适应的个体将会被灭绝。每个幸存者都会有机会繁衍（重要的是任何幸存者都可能会繁衍，如果不太适应的话，仅仅是降低了可能性）。合并双亲的 DNA，对合并后的 DNA 应用随机变异以模拟繁衍。理论上说来，新的个体是和双亲一样适应的，由于变异或增或减会有些微小的变化。然后循环会周而复始。
显然，有许多变化的因素在影响遗传算法，包括人群大小、代（算法的迭代）、合并方法、适应性函数，适应性将如何影响繁衍的可能性，以及发生了多少变异。
该算法也存在一些缺陷。如果把应用于 DNA 的适应性官能看成是一系列的二进制位，效果最好。换句话说，如果 DNA 是一系列二进制的选项，是还是不是。蓝眼睛？黑眼睛？红头发？黑头发？合并双亲的 DNA 和随后的变异应当不允许特定的一些位组合出现，因为得出的 DNA 可能不再是最初的问题的有效解答。请记住，所谓“DNA”仅仅是适应性公式纯数学的一种解答。该公式中用到的一些值可能是无效的 — 例如，除数为零。
另外，遗传算法不受时间限制。由您来挑选代的数目。您可以确定某个目标 — 比方说，“找一个适应性为 0.99999 的个体”，找到后停止。但是，结果是算法永远也不会结束，因为它没找到那个个体。如果您制定了不切实际的目标，或者代的数目太小，就会出现问题。尝试、出错，以及深入的思考是解决这个问题的最佳途径。
适应性公式返回的是介于 0 和 1 之间的一个浮点数。您也可以使用其它的范围的数，但是我的经验告诉我，浮点数是最有效的。比如，如果出于优选的考虑，您希望适应性是一个 7 位的整型数，您想要的范围就是 0 到 32767 之间。
当然，把优选推迟到您认为有需要的时候，这是一个好主意，那么您在开始的时候，最起码得有一个简单的适应性公式。适应性公式是遗传算法中最常用的函数，（它将要被调用的次数是（人群大小）x（代的数目）次），所以您应当尽可能的使它简单、快速。
有三种“好”的可以退出遗传算法的方式！首先，当 DNA 池里不再有变化时，您就可以决定退出。事实上，这是个棘手的测试，只要您能够把 DNA 表示为字符串，就可以利用一个确定串之间的差异的 CPAN 模块。第二，如果达到了适应性的目标，您也可以退出。除非对适应性公式非常了解（在这种情形下，无论如何，您都可能不再需要遗传算法了），设定适应性目标的结果，或者是导致无穷循环，或者是得到一个仅仅是“足够好”的个体。第三，在迭代了一定的次数或者说经历了一定数目的“代”后，您也可以退出。
在实践中，这三种方式（或者至少是第二种和第三种）都会被用于控制遗传算法。只要经过为数不多的测试，可能是 10 次，也可能是 20 次，您就会清楚的知道算法汇集需要多长时间，以及您想要的适应性是什么样子的。
一个简单的例子
清单 1 里的代码把一个字节看作是 DNA（它的值介于 0 和 255 之间，8 位）。对每个新个体应用适应性公式一次，用表示 DNA 的字节所具有的数值，去除以 256。这样适应性公式总是会返回一个介于 0 和 255/256 之间的数值，因此，它永远也不会等于 1。那么，您认为最适应的 DNA 应当是多少呢？
清单 1. 繁殖字节以测试其适应性
numbers.pl source
清单 1 里有几件非常有趣的事情。它的主循环位于程序的开始部分，您应当弄懂所有的程序片，以及它们是如何共同作用于人群的（既然这些部分是相互独立的，因此我们还可以在下面的例子中重复使用）。您可以运行清单 1，程序文件为 numbers.pl。
通过把 map() 堆栈到 grep() 的上部，我们在 select_parents() 函数里建立了 weights 数组。虽然我们本来可以把它写成循环，但是长度只有一行的解决方案要清楚得多，并且不会显著降低程序运行的速度。
清单 2. map 和 grep 堆栈
my @weights = map { $_->{fitness} } grep { $_->{survived} } @$population;
$population 数组引用是间接引用。那么，只有带“survived”域的数组元素（在前面由 survive() 函数设定的）通过 grep。然后这些幸存者被蒸馏成代表其适应性的数字，并存入 weights 数组里该幸存者所对应的位置。
取大小为 256 的人群，原因是这样便于把个体都初始化成一个与其序号相等的数字。您可以自由选择不同的人群大小开始。
大于 1% 的变异率使得适应性的最大值和最小值剧烈波动。人群绝不可能稳定在高适应性。变异率低导致了需要更多的时间人群才能整体上达到高适应性。最后，对于我们讨论的人群大小而言，1% 恰好合适。
繁衍选择算法会查找 weights 数组，选择第一个双亲 — 其实，每个个体都有可能成为双亲，但是双亲位置的数目是确定的。另一个双亲是随机地从双亲人群中挑选的。为什么呢？噢，本来我们可以在 weights 数组里把另外一个双亲也确定下来，但是，这样我们可以确保每个可以成为双亲的个体都有可能参与繁衍过程。
实际上实现繁殖的是一个随机的 8 位位掩码。我们只把这个位掩码和第一个双亲的 DNA（请记住，它只是一个字节）作 AND 运算，并且把位掩码取反后和第二个双亲的 DNA 作 AND 运算。结果，我们可以从一个双亲上随机选择某些位，其余的来自另外一个双亲。
变异是通过对个体的 DNA 和随机生成的 8 位位掩码作 AND 和 OR 运算实现的。
对了，顺便说一下，最适应的 DNA 当然是 255。您并不需要等待 100,000 代。当您只是在欣赏状态行时，请按 Ctrl-C 结束。
繁殖单词
在这个例子里，我们用的 DNA 是 32 位（5 个字节）的。每个字节代表一个字母或者一个空格。我们本来可以在一个字节中包含更多的信息，但是这样可能会使这个例子的本意变得模糊。每一字节的值（介于 0-255 之间的数值）可能对应 A 到 Z 之间的一个字母（如果它的值在 65 到 90 之间，便于选择同 ASCII 码集相匹配），或者也可能是一个空格（如果数值介于 0 到 64 之间，或 91 到 255 之间的话）。
请关注一下下面的这个例子和清单 1 的例子的相似之处。dictionary 的单词跟在程序的后面。
清单 3. 繁殖单词
words.pl source
这个例子的主要问题在于长度超过 32 位的 DNA 不好处理。开始我尝试着自己做位操作，结果不仅仅是难处理，而且速度极慢。然后，我试了一下 Math::BigInt 包，用在这里还是非常慢。 您可以运行清单 3，程序文件为 words.pl。
最后，我决定使用 vec() 函数 — 它的速度相当快，对于处理 DNA 而言，它无疑是正确的选择（本质上，DNA 是个位向量，一个内建的 Perl 数据结构）。用“perldoc -f vec”查找更多有关 vec() 函数的信息。
1024 个个体的适应性为 0 的结果也是有可能出现的。这个例子比第一个例子能更有效的预防这样的“意外”的原因正在于此。
修改 init_population()、recombine() 和 mutate() 函数以处理位向量而非字节。
dna_to_words() 函数的效率不高，但并不经常调用它，所以问题不是很严重。速度慢的最主要的因素是 fitness() 函数试图匹配 dictionary 里的所有单词，以及字母表里的所有字母。
适应性是这样计算的：DNA 里的每一个字母是一个 2，加上那个字母在 dictionary 里出现的频率， 再为 DNA 里长度为 N 的每个 dictionary 单词加上 2^N。dictionary 数组以及字母频率的散列只得到一次（使用 closure）。您可以任意修改适应性函数和 dictionary 来繁殖您自己的英语单词。如上所示的适应性公式很大程度上偏向字母，要汇集成英语单词还需要一定的时间（尽管“on”和“in”频繁出现）。
结束语
进化遗传算法是个非常吸引人的话题，在一篇文章中想把所有内容都讲清楚几乎是
|
上一篇：功能丰富的 Perl: Perl自动化系统管理 下一篇：功能丰富的 Perl：编写说英语的 Perl 程序
 |
相关文档 |
|
|
|
发表评论 |
|
|
|
|
