作者:bitsCN整理   来源:ChinaITLab 

        我的前两篇关于使用 Perl 实现遗传算法（GA）的文章（参阅 参考资料）讲述的是个体细胞的变异与生命周期，它的适合度（fitness）完全依赖于它们自己的 DNA。本文将介绍如何仿真一个多细胞机体。具体的应用程序将会生成由其复杂性和正确性决定的字谜（letter puzzles）。要获得 GA 的背景知识，您应该去参考先前的两篇文章。
　　
　　个体细胞是字谜中的字母块（letter tiles）。它们的适合度将取决于它们与所有其他细胞的组合，所以，在应用于上下文之前，细胞 DNA 本身没有意义。而且， DNA 必须较长，但并不复杂。它只是要告诉我们任意一个特定细胞可能会连接到哪些字母，当然，它也会告诉我们这个特定细胞的字母（也可能是一个空块）。
　　
　　那么，让我们来开始设计!
　　
　　仿真设计
　　有两方面基本设计。首先是个体细胞的设计，其次是细胞间交互的设计。我将从个体细胞开始讲起。
　　
　　本质上，每个细胞都是纵横拼字谜（crossword puzzle）中的一个字母。那将是 DNA 的一个片段。而且， DNA 将决定一个细胞与其他字母的适合程度。这样，对英文纵横字谜来说，“an”和“he”将是合适的组合，而“xz”将不是。这并不是说“xz”不可能出现，而只是说使用它生成的纵横字谜没有多高的价值。我将使用一个词典，这个词典默认位于 GNU/Linux 系统的 /usr/share/dict/words 中（至少在我的 Debian 系统中是这样 —— 否则，可以使用 whereis 或 locate 命令来找到它，并相应地修改 $words_file）。
　　
　　细胞之间的交互将发生在一个 N 乘 N 的字谜中，其中 N 在命令行中给定，默认为 10。在任何时刻都会有 N^2 个细胞被选中，留下 N*2 个细胞（所以，在一个 10x10 字谜的循环周期中，总共有 120 个细胞）。这些数字是任意的，不太重要，只不过，一个大的“无限制”的池将使细胞选择的值的适合度降低，而一个小的池将限制元素的机会。
　　
　　您应该记住，这里的目标不是生成“正确”的解决方案 —— 没有这样的解决方案。目标是仿真细胞之间的交互，特别要注意平衡字母细胞所需要的空块细胞。
　　
　　从初始细胞池中对细胞的选择由字母关联性来完成。如果在字谜板（puzzle board）上没有其他细胞，那么任何细胞都是可以的。不过，如果程序正在为一个与“A”和“Q”相邻的块来选择细胞，那么“A”和“Q”的细胞关联性就有关系了。因此，细胞关联性是 DNA 的一个基本部分，和细胞的字母一样受到变异的影响。细胞关联性的范围是 0 到 255，所以可以方便地由 DNA 的一个字节来描述它。
　　
　　最后，我将缓存细胞所构成的词。我不会采用这种简单的方法：选出每个块并指出它构成哪些词。您想知道为什么吗？因为我试过那种方法，为了得到正确的方法，浪费了好多个小时的时间，而且它并不快!
　　
　　我的方法是，从左到右，从上到下对谜板进行扫描（两遍，这是为了得到垂直方向和水平方向的词）。当找到一个词后，我会记住构成那个词的细胞，然后将那个词添加到所有那些细胞的词缓存中。词缓存是一个数组，不是散列表，反映出事实上同一个词可以出现在水平方向上，也可以出现在垂直方向上，但细胞只能归于一个这样的词。对于微不足道的细胞来说，那将是极其不公平的。
　　
　　对于谜板而言，它是一个简单的散列表。我尝试过使用嵌套数组来仿真一个矩阵，不过没有必要那么麻烦。我只需要使用一个具有 x y 键的简单散列表就可以完成仿真。唯一所需要的映射是 xy2index() 函数；我编写了一个名为 index2xy() 的反向映射函数，但是没必要使用它。
　　
　　与先前文章的不同之处
　　本文中的程序是我先前撰写的两篇遗传算法文章中 GA 仿真程序的改进版本。基于读者 Matt Neuberg 的建议，以及我本人的经验，我做了一些修改。
　　
　　select_parents() 是不严格的，因为它将不适合的亲本（parents）留在种群（population）中，即使它们的适合度为 0，不可能被选择。为了纠正那一点，我添加了一个额外的 grep() 调用。
　　
　　recombine() 函数
　　我应该提醒您，基于亲本的适合度，亲本种群包含有对亲本的多个引用。亲本越适合，在亲本种群中出现的次数就会多，因而就会有更多机会繁殖下去。
　　
　　recombine() 使用 List::Util shuffle() 函数来随机组合亲本种群。这样做的效果好于选择随机亲本并保持对哪些已经是亲本的追踪。另外，以前第二个亲本是随机选择出来的，而且我认为这样是对演化的相当准确的描述，但是我改变了那种方法，通过将它们从亲本种群中选择出来然后再插入回去的方式，基于它们的适合度来选择第二个亲本。
　　
　　清单 1. recombine() 函数
　　
　　sub recombine
　　{
　　my $population = shift @_;
　　my $pop_size = scalar @$population; # population size
　　my @parent_population;
　　my @new_population;
　　
　　my $total_parent_slots = 0;
　　
　　$total_parent_slots += $_->{parent}
　　foreach @$population;
　　
　　my $position = 0;
　　
　　foreach my $individual (@$population)
　　{
　　foreach my $parenting_opportunity (1 .. $individual->{parent})
　　{
　　push @parent_population, $individual;
　　}
　　$individual->{parent} = 0;
　　}
　　
　　@parent_population = shuffle @parent_population;
　　
　　while (1)
　　{
　　# this could result in a parent breeding with itself, which is not a big deal
　　my $parent = shift @parent_population;
　　my $parent2 = shift @parent_population;
　　my $out_of_parents = 0;
　　
　　# when we're out of parents...
　　unless (defined $parent2)
　　{
　　$parent2 = $parent;
　　$out_of_parents = 1;
　　}
　　
　　my $child = { survived => 1, parent => 0, fitness => 0, dna => 0 };
　　
　　# this is breeding!
　　my $dna1 = $parent->{dna};
　　my $dna2 = $parent2->{dna};
　　
　　# note we do operations on BYTES, not BITS.　This is because bytes
　　# are the unit of information (and preserving them is the faster
　　# breeding method)
　　foreach my $byte (1 .. $dna_byte_length)
　　{
　　# get one byte from either parent (the parent choice is random) and add it to the child
　　vec($child->{dna}, $byte-1, 8) = vec(((rand() < 0.5) ? $dna1 : $dna2), $byte-1, 8);
　　}
　　
　　push @new_population, $child; # the child is now a part of the new generation
　　push @parent_population, $parent2; # use the second parent again, but at the tail end
　　last if $out_of_parents;
　　}
　　
　　return \@new_population;
　　}
　　
　　注意，如果最后一个亲本恰好是自亲本种群中获得的，应该如何去设置 $out_of_parents；那是跳出亲本选择循环的唯一途径。
　　
　　构建字谜
　　字谜网格由相应的名为 build_puzzle() 的函数来构建。种群中的每一个个体细胞都在内部存储了一个网格位置，所以，当我想要找到某个细胞的网格位置时，不必搜索网格或者维持一个外部散列表。每一个个体还拥有一个“单词”数组引用，在这个数组中保持有在衍生过程中那个个体生成的单词。
　　
　　另外，我为每个细胞赋予了一个 ID 属性，不过只是使用它来检查算法的正确性。
　　
　　在 build_puzzle() 中，所有的个体都安置于 @puzzle_population。我做了一个 @puzzle_population 的拷贝，这样我可以从它里面去删除个体，以使得对个体的改变不会是永久的 —— 它是一个浅拷贝（shallow copy）。选择块的顺序是随机的，再次使用了 List::Util::shuffle()。注意，所有的位置都存储在一个 [x,y] 数组中。那样，数据可以像单一的参数一样传递，而不是多个参数。
　　
　　清单 2. build_puzzle() 函数
　　
　　sub build_puzzle
　　{
　　my $population = shift @_;
　　
　　my @puzzle_population = @$population; # make a local copy we can alter
　　
　　my $i = 0;
　　foreach (@puzzle_population)
　　{
　　$_->{id} = $i++;
　　$_->{position} = undef;
　　$_->{words} = [];
　　}
　　
　　my $puzzle = {};
　　
　　my @positions;
　　
　　foreach my $row (0 .. $size-1)
　　{
　　foreach my $column (0 .. $size-1)
　　{
　　push @positions, [$row, $column];
　　}
　　}
　　
　　foreach my $p (shuffle @positions)
　　{
　　my $row　　= $p->[0];
　　my $column = $p->[1];
　　
　　my $cell =　choose_tile(\@puzzle_population, $puzzle, $p);
　　$cell->{position} = $p;
　　$puzzle->{xy2index($p)} = $cell;
　　}
　　
　　return $puzzle;
　　}
　　
　　注意，上面的 recombine() 和 build_puzzle()中，以及程序所有其他位置，都没有类似于 $i 的计数器。由于 Perl 没有内存分配问题，所以对我来说缺陷的最主要来源就是追踪计数器变量的错误（错误的初始化，错误的增量，或者错误的边界）。这并不是说我在编写 Perl 程序的时候出现了很多缺陷，只是我发现计数器变量会增加使用时出现缺陷的可能性。
　　
　　现在登场的是 choose_tile()。字谜中的每一个网格位置都会调用它来选择一个将成为字谜块的细胞。在为网格