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

dskongenius 发表于 2007/11/6 10:33:57

实际上实现繁殖的是一个随机的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合著（O'Reilly & Associates 2000）。这是目前最好的Perl入门指导，更新到5.005和 5.6.0。 “用 Perl 精通算法”，由Jon Orwant、Jarkko Hietaniemi和John Macdonald合著（O'Reilly & 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提出建议或者纠正错误。