当您初次登录到 developerWorks 时，将会为您创建一份概要信息。您在 developerWorks 概要信息中选择公开的信息将公开显示给其他人，但您可以随时修改这些信息的显示状态。您的姓名（除非选择隐藏）和昵称将和您在 developerWorks 发布的内容一同显示。

所有提交的信息确保安全。

当您初次登录到 developerWorks 时，将会为您创建一份概要信息，您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。

昵称长度在 3 至 31 个字符之间。您的昵称在 developerWorks 社区中必须是唯一的，并且出于隐私保护的原因，不能是您的电子邮件地址。

所有提交的信息确保安全。

My developerWorks:

我的通知：

退出

选择语言：

功能丰富的 Perl: 遗传算法仿真多细胞机体

创造生命或者类似于生命的东西

Teodor Zlatanov (tzz@bu.edu), 程序员, Gold Software Systems

Teodor Zlatanov 于 1999 年毕业于波士顿大学计算机工程专业，获硕士学位。自从 1992 年以来，他一直从事编程工作，使用的语言包括 Perl、Java™、C 和 C++。他的主要兴趣是在文本解析、3 层客户机—服务器数据库体系结构、UNIX 系统管理、CORBA 以及项目管理方面的开放源代码工作。欢迎提出建议或者纠正错误；可通过 tzz@bu.edu 与 Ted 联系。

简介： 遗传编程建立在达尔文适者生存的自然选择法则的基础之上，利用变异和复制来生成算法，该算法可创建不断改进的计算机程序。本文是关于遗传算法的第三部分，Ted 从他上一次结束的地方继续讲述，介绍了如何仿真一个多细胞机体。

标记本文！

发布日期： 2004 年 11 月 08 日
级别： 初级
访问情况： 1289 次浏览
评论：

我的前两篇关于使用 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()。字谜中的每一个网格位置都会调用它来选择一个将成为字谜块的细胞。在为网格位置计算候选细胞的关联性时，我考虑了相邻字母（记住，它们其中的一些可能还没有被初始化）。我还密切注意了未定义的种群元素，因为当我从 @puzzle_population 删除细胞时（在 choose_tile() 中传递一个名为 $population 的数组引用），它们可能会成为块。未定义的种群元素权重为 0，所以，为特定网格位置选择最可能细胞的 sample() 函数不会选择它。

清单 3. choose_tile() 函数

				
        
sub choose_tile
{
 my $population = shift @_;
 my $puzzle 	= shift @_;
 my $coords    	= shift @_;
 # uncomment this to get random population
 # return $population->[int(rand($size**2))];
 my $neighbors =
     puzzle_position_neighbors($puzzle, $coords);
 my @neighbor_letters;
 foreach my $n (@$neighbors)
 {
  next unless defined $n;
  push @neighbor_letters, dna_cell_letter($n);
 }
 my $offset;
  # now we have to use the affinity
  my @weights;
  foreach my $p (@$population)
  {
   my $weight = 0;
   if (scalar @neighbor_letters)
   {
    if (defined $p)
    {
     $weight +=
      dna_letter_affinity($p->{dna}, $_)
       foreach @neighbor_letters;
    }
    push @weights, $weight;
   }
   # no neighboring letters
   else
   {
    if (defined $p)
    {
     $weight = ord(dna_cell_letter($p));
    }
    push @weights, $weight;
   }
  }
  # we now have an array of weights we can sample
  $offset = sample(\@weights);
 # remove tile from the population and store it in $cell
 # (yes, this can be done in one step)
 my $cell = $population->[$offset];
 delete $population->[$offset];
 return $cell;
}

dna_letter_affinity() 函数是快速选择细胞的关键，所以它尽可能地依赖于 vec() 等 Perl 内置函数。如果 multicell.pl 需要进行速度方面的优化，这将是我首先考虑的一个地方。

既然已经构建了字谜，那么接下来我扫描它的单词，并根据细胞构成的单词计算所有细胞的适合度。

回页首

扫描并评价字谜

如前所述，我既扫描水平方向上的单词，也扫描垂直方向上的单词。 puzzle_scan_words() 函数有一个 $flip 参数，可以将扫描从水平方向转化为垂直方向。扫描会向一个单词进行累积，直到结束（或者是行或列的末尾，或者遇到非字母的块），然后将此单词添加到它寻找过程中遍历的所有字母细胞。

清单 4. puzzle_scan_words() 函数

				
        
sub puzzle_scan_words
{
 my $puzzle = shift @_;
 my $flip   = shift @_;
 my @words;
 my @trail;
 foreach my $row (0 .. $size-1)
 {
  my $word = '';
  foreach my $column (0 .. $size-1)
  {
   my $p = ($flip) ? [$column, $row] : [$row, $column];
   my $cell = puzzle_cell_at($puzzle, $p);
   croak "Unexpected undefined tile at $row, $column"
    unless defined $cell;
   if (is_cell_letter($cell))
   {
    push @trail, $cell;
    $word .= dna_cell_letter($cell);
   }
   else
   {
    puzzle_add_word($puzzle, $word,
                    @trail);
    @trail = ();
    $word = '';
   }
  }
  puzzle_add_word($puzzle, $word,
                  @trail);
  @trail = ();
 }
}

注意，虚词（empty words）也可以被添加。 puzzle_add_word() 将拒绝虚词 —— 那样逻辑会更简单，即使在那个过程中会有对 puzzle_add_word() 的额外调用。

@trail 列表是 puzzle_scan_words() 的最重要部分。它存储在生成那个单词时所遍历的所有细胞。

扫描完字谜后，我可以根据它生成的单词来评价每个细胞的适合度。首先，所有未入选的细胞被赋予的适合度为 10。然后，分配给字母和非字母细胞的 $factor 分别为 5 和 2，非字母的情况还要加上初始适合度 1。

对于块生成的每一个单词，它都会将 $factor 添加到适合度的分数。而且，如果那个单词是一个长度为 2 或者更长的字典单词，那么 $factor 将增加为单词长度的乘方。这样就使得构成长单词的细胞非常有可能再次被选中。非字母细胞是一种特殊情况：对它们来说，所有与它们相邻的单词都会被返回。这样，没有字母与之相邻的空块的适合度为 1，而由八个单词所环绕的空块（最多 —— 每边四个）会有高得多的适合度。这样，我就得到了那些与字母（尤其是可能构成有用的英文单词的字母）相关的空块。

清单 5. fitness() 函数

				
        
# calculate the fitness of a cell's DNA
# by looking at what it's done in the puzzle
sub fitness
{
 my $puzzle = shift @_;
 my $cell   = shift @_;
 return 10 unless exists $cell->{position}; # exclude all non-puzzle cells
 my @words = cell_words($puzzle, $cell); # what words use this cell?
 # print "Cell ", $cell->{id}, " uses words @words\n";
 # start with 0 fitness
 my $fitness = 0;
 my $factor;
 if (is_cell_letter($cell))
 {
  $factor = 5; # reward longer words significantly more
 }
 else
 {
  # reward blanks with a small score, but they
  # get all neighboring words and start well
  $factor = 2;
  $fitness = 1;
 }
 foreach my $word (@words)
 {
  # some minimal fitness for all cells
  $fitness+=$factor;
  next unless exists $dictionary{$word};
  next unless length $word > 1;
  # remember this generated word!
  $generated_words{$word} = 1;
  $fitness += $factor ** length $word;
 }
 return $fitness;
}					# end of fitness()

我将生成的单词存储在一个单独的表中，这样我就可以在每一次衍生中获取并显示它们。这是 multicell.pl 所实现的 GA 算法有效性的一个表现。

清单 6. 演化

				
        
# The Saga Begins (random initialization)
Generated: HG
YYYYV@ZOBJ
YTGX@P@GU@
HMNQMTTIXP
PEZQJA@FPP
YX@E@XPHLH
EBZVGM@@XG
VL@Y@ZUBCL
FYFHEFTVYV
TDNLGOXHZG
@@QZJTYFPQ
# Invasion of the Ottos
Generated: BOY BY FE GO LO LT MB MY OTTO OW PA TB TL TO TOO TOOT TOT TOW TOY TY
YB YE
OOOOTTOTOO
OOOOOOTOOO
OTOOTOOOOO
OTTOTOTOTT
OOTOOOTOOT
OOTOOOOOTO
TOTOOOOOOO
TTOOTTOOOT
OOTTTOOOOT
OOOOTOOTOT
# After 1000 Generations, a Moment of Peace
Generated: AN ANA ANN ANNA ANY AR ARA AS AT ATS AU AY BI CS DR GS HI
ID IN IT KR LU NA NAN NAT NB ND NI NU NUN OAT OR OS OTTO PB PI PIP PIT
PT PU RA RAN RB RD RH RN RS RU SN SO SOOT SOT SOTO SOTS SR ST TA TC TI
TO TOO TOOT TOSS TOST TOT TOTO TOTS TS UR US WU YA ZN
TTTTTTTTTT
TTTTTTTTTT
TTTVTTTTTT
VTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT
TTTTTTTTTT

回页首

结束语

GA 的这个实现是有效的吗？我做了随机字母选择相对于 GA-辅助字母选择的测试， GA 字母选择总是会生成更长的单词。随机选择会给出两个和三个字母的单词，而 GA 方法在一个 20x20 的网格中经过几百次衍生后会得到六个字母的单词。

运行 multicell.pl 并观察字谜变种。您可能会看到空块充斥于谜板之上，然后出现“I” 和“S”字母（当然，ISIS 是最先衍生的单词之一）。然后是“U”和“T”字母，然后衍生出一个引入“L”和“LULL”的小的变异。这令人着迷。字母的适应和选择取决它们对英文的适宜程度；很少会出现字母“Q”或“Z”。

最后，我将介绍在 Slashdot 上关于前两篇 GA 文章的讨论引发的一些评论（请参阅参考资料以获得关于那些讨论的链接）。很多人感觉 Perl 用于 GA 仿真太慢了。我认为 Perl 非常适于进行 GA 仿真，通常速度问题应归因于拙劣的 Perl 程序编制，而不是语言的内在限制。诚然，Perl 比原始的 C 慢一些，但是另一方面，我要看看与 multicell.pl 相当的 C 源程序 —— 我怀疑它能不能满足 1）长度不超过 700 行，2）没有缺陷，3）编写起来有趣。此三点要求 multicell.pl 都可以达到。

当您可以定义适合度时，GA 本身是实用的，但是您不容易优化它。例如，汽车贷款不容易被优化。适合度就是您在 30 年的汽车贷款中可以赚到多少钱（一个很好的，单一的数字），但是，每一年的利润还取决于计划的汽车销售和税率，与前几年相关连 —— 本质上这是一个数字难题。 GA 可以很好地完成那种具体仿真。

作为一个教学工具，Perl 中的 GA 可以用来实现复杂 GA 仿真的原型，也可以运行小型的 GA 仿真。在很多其他 Perl 项目的帮助下，毫无疑问它会比在 C 中更快 —— 问题在于，为了获得那样的加速而付出开发时间与精力（包括调试!）是否值得。答案通常有利于 Perl。

参考资料

您可以参阅本文在 developerWorks 全球站点上的英文原文。
本系列的前两篇 GA 文章是
- Perl 用于实现遗传算法
- 遗传算法，下一代
在 2002 年最初发表时，本系列的第二篇文章就在 Slashdot 上得到了讨论并被其链接。
下载本文中使用的 multicell.pl 程序。您还可以从 Ted 的早期文章中下载 words.txt 和 numbers.txt。
Wikipedia 通过引用和历史对 GA 进行了全面的评论，既包括了许多附加参考资料，也包括了 GA 的发展历史。
在 developerWorks 上阅读“功能丰富的 Perl”系列中 Ted 的所有 Perl 文章。
在 developerWorks Linux 专区可以找到更多为 Linux 开发者准备的参考资料。
从 developerWorks 的 Speed-start your Linux app 专区下载能够运行于 Linux 之上的 IBM 中间件产品的免费测试版本，包括 WebSphere® Studio Application Developer、WebSphere Application Server、DB2® Universal Database、Tivoli® Access Manager 和 Tivoli Directory Server，并可查找 how-to 文章和技术支持。
通过参与 developerWorks blogs 加入到 developerWorks 社区。
在 Developer Bookstore Linux 区中定购打折出售的 Linux 书籍。