IDC资讯中心
perl用于实现遗传算法
[编者的话]
遗传算法在生物信息学尤其是蛋白结构预测与分析中有重要应用：perl是现在生物信息学界中很热门的一种编程语言（我们在以前专题中曾做过专门介绍）。perl的长处是文本分析，那么它在编写算法上是否能一样表现优异呢，它能不能做这方面的工作呢，别急，且看下文：）
创建您自己的达尔文式的繁殖基础
teodor zlatanov (tzz@iglou.com)
程序员，gold software systems
2001年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数组里把另外一个双亲也确定下来，但是，这样我们可以确保每个可以成为双亲的个体都有可能参与繁衍过程。
实际上实现繁殖的是一个随机的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”频繁出现）。
结束语
进化遗传算法是个非常吸引人的话题，在一篇文章中想把所有内容都讲清楚几乎是不可能的。我希望您能实践一下这些例子，并创建您自己的达尔文繁衍基础。试试第二个例子中的fitness函数，看着英文单词从原本无意义的字母和空格中出现，这真是一项非常有意思的娱乐。
上面的例子中用到的技巧涵盖了从初级到高级的范围，因此请尽量彻底理解这些内容。通常情况下仍有改进的空间。vec()函数尤为有趣。它非常适合于象dna或者其它的数值数据之类的长的位向量。
编写您自己的遗传算法的实现。与我的进行比较，从缺点中学习（并不一定是您的缺点）。实现算法是一件巧妙的事。您会遇到许多错误的方法，但正确的却只有为数不多的几种。
参考资料
感谢abigail，他的cpan样本模块可以演示我在两个例程中都用到的sample()函数。对于任何一个perl程序员，sample样本模块及其文档都是非常棒的工具。
访问cpan，那里有您想要的所有的perl模块。
在perl.com寻找perl信息和相关参考资料。
访问perldoc.com，那里有perldoc在线信息。
“perl 编程思想，第 3 版”，由larry wall、tom christiansen和jon orwant合著（oreilly & associates 2000）。这是目前最好的perl入门指导，更新到5.005和 5.6.0。
“用 perl 精通算法”，由jon orwant、jarkko hietaniemi和john macdonald合著（oreilly & associates 1999），是以perl表达算法的很棒的提纲。第14章的“概率”说明了如何用perl来计算加权和不加权的概率分布。
遗传算法常见问题解答有些过时，但是它指向的的确是一些有用的遗传算法的软件，有免费的也有商业化的。
teodor zlatanov在developerworks写的相关文章，包括：
one-liners，101
对大画面细节的观察
浏览developerworks上更多linux参考资料。
浏览developerworks上更多开放源代码的参考资料。
关于作者teodor zlatanov于1999年毕业于波士顿大学计算机工程专业，获硕士学位。自从1992年以来，他一直从事编程工作，使用的语言包括perl、java、c和c++。他的主要兴趣是在文本解析、3层客户机—服务器数据库体系结构、unix系统管理、corba以及项目管理方面的开放源代码工作。欢迎和teodor联络，发电子邮件到mailto:tzz@bu.edu提出建议或者纠正错误。
本文出自ibm网站linux专栏（www.ibm.com/developworks/cn）,转载请注明出处。
