[机器学习]Perl-遗传算法（一）

dskongenius 发表于 2007/11/6 11:38:12

[编者的话] 遗传算法在生物信息学尤其是蛋白结构预测与分析中有重要应用：Perl是现在生物信息学界中很热门的一种编程语言（我们在以前专题中曾做过专门介绍）。Perl的长处是文本分析，那么它在编写算法上是否能一样表现优异呢，它能不能做这方面的工作呢，别急，且看下文：） 　 创建您自己的达尔文式的繁殖基础 Teodor Zlatanov (tzz@iglou.com)程序员，Gold Software Systems2001年8月 遗传编程建立在达尔文适者生存的自然选择法则的基础之上，利用变异和复制来生成算法，该算法可创建不断改进的计算机程序。在本专栏里，您将开始了解用浅显的术语表述的遗传算法。Ted 给出了几种特定的任务的 Perl 实现，您可以用于广泛的用途。为了示范遗传算法，Ted 繁殖了一些数字和字母，应用于公式以测试这些数字的适应性，而繁殖的字母则形成了英语单词。 如果您的机器上已经安装了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数组里把另外一个双亲也确定下来，但是，这样我们可以确保每个可以成为双亲的个体都有可能参与繁衍过程。