作者: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()。字謎中的每一個網格位置都會調用它來選擇一個將成為字謎塊的細胞。在為網格