作者:bitsCN整理   來源:ChinaITLab 

        我的前兩篇關(guān)于使用 Perl 實現(xiàn)遺傳算法（GA）的文章（參閱 參考資料）講述的是個體細(xì)胞的變異與生命周期，它的適合度（fitness）完全依賴于它們自己的 DNA。本文將介紹如何仿真一個多細(xì)胞機(jī)體。具體的應(yīng)用程序?qū)捎善鋸?fù)雜性和正確性決定的字謎（letter puzzles）。要獲得 GA 的背景知識，您應(yīng)該去參考先前的兩篇文章。
　　
　　個體細(xì)胞是字謎中的字母塊（letter tiles）。它們的適合度將取決于它們與所有其他細(xì)胞的組合，所以，在應(yīng)用于上下文之前，細(xì)胞 DNA 本身沒有意義。而且， DNA 必須較長，但并不復(fù)雜。它只是要告訴我們?nèi)我庖粋€特定細(xì)胞可能會連接到哪些字母，當(dāng)然，它也會告訴我們這個特定細(xì)胞的字母（也可能是一個空塊）。
　　
　　那么，讓我們來開始設(shè)計!
　　
　　仿真設(shè)計
　　有兩方面基本設(shè)計。首先是個體細(xì)胞的設(shè)計，其次是細(xì)胞間交互的設(shè)計。我將從個體細(xì)胞開始講起。
　　
　　本質(zhì)上，每個細(xì)胞都是縱橫拼字謎（crossword puzzle）中的一個字母。那將是 DNA 的一個片段。而且， DNA 將決定一個細(xì)胞與其他字母的適合程度。這樣，對英文縱橫字謎來說，“an”和“he”將是合適的組合，而“xz”將不是。這并不是說“xz”不可能出現(xiàn)，而只是說使用它生成的縱橫字謎沒有多高的價值。我將使用一個詞典，這個詞典默認(rèn)位于 GNU/Linux 系統(tǒng)的 /usr/share/dict/words 中（至少在我的 Debian 系統(tǒng)中是這樣 —— 否則，可以使用 whereis 或 locate 命令來找到它，并相應(yīng)地修改 $words_file）。
　　
　　細(xì)胞之間的交互將發(fā)生在一個 N 乘 N 的字謎中，其中 N 在命令行中給定，默認(rèn)為 10。在任何時刻都會有 N^2 個細(xì)胞被選中，留下 N*2 個細(xì)胞（所以，在一個 10x10 字謎的循環(huán)周期中，總共有 120 個細(xì)胞）。這些數(shù)字是任意的，不太重要，只不過，一個大的“無限制”的池將使細(xì)胞選擇的值的適合度降低，而一個小的池將限制元素的機(jī)會。
　　
　　您應(yīng)該記住，這里的目標(biāo)不是生成“正確”的解決方案 —— 沒有這樣的解決方案。目標(biāo)是仿真細(xì)胞之間的交互，特別要注意平衡字母細(xì)胞所需要的空塊細(xì)胞。
　　
　　從初始細(xì)胞池中對細(xì)胞的選擇由字母關(guān)聯(lián)性來完成。如果在字謎板（puzzle board）上沒有其他細(xì)胞，那么任何細(xì)胞都是可以的。不過，如果程序正在為一個與“A”和“Q”相鄰的塊來選擇細(xì)胞，那么“A”和“Q”的細(xì)胞關(guān)聯(lián)性就有關(guān)系了。因此，細(xì)胞關(guān)聯(lián)性是 DNA 的一個基本部分，和細(xì)胞的字母一樣受到變異的影響。細(xì)胞關(guān)聯(lián)性的范圍是 0 到 255，所以可以方便地由 DNA 的一個字節(jié)來描述它。
　　
　　最后，我將緩存細(xì)胞所構(gòu)成的詞。我不會采用這種簡單的方法：選出每個塊并指出它構(gòu)成哪些詞。您想知道為什么嗎？因為我試過那種方法，為了得到正確的方法，浪費了好多個小時的時間，而且它并不快!
　　
　　我的方法是，從左到右，從上到下對謎板進(jìn)行掃描（兩遍，這是為了得到垂直方向和水平方向的詞）。當(dāng)找到一個詞后，我會記住構(gòu)成那個詞的細(xì)胞，然后將那個詞添加到所有那些細(xì)胞的詞緩存中。詞緩存是一個數(shù)組，不是散列表，反映出事實上同一個詞可以出現(xiàn)在水平方向上，也可以出現(xiàn)在垂直方向上，但細(xì)胞只能歸于一個這樣的詞。對于微不足道的細(xì)胞來說，那將是極其不公平的。
　　
　　對于謎板而言，它是一個簡單的散列表。我嘗試過使用嵌套數(shù)組來仿真一個矩陣，不過沒有必要那么麻煩。我只需要使用一個具有 x y 鍵的簡單散列表就可以完成仿真。唯一所需要的映射是 xy2index() 函數(shù)；我編寫了一個名為 index2xy() 的反向映射函數(shù)，但是沒必要使用它。
　　
　　與先前文章的不同之處
　　本文中的程序是我先前撰寫的兩篇遺傳算法文章中 GA 仿真程序的改進(jìn)版本。基于讀者 Matt Neuberg 的建議，以及我本人的經(jīng)驗，我做了一些修改。
　　
　　select_parents() 是不嚴(yán)格的，因為它將不適合的親本（parents）留在種群（population）中，即使它們的適合度為 0，不可能被選擇。為了糾正那一點，我添加了一個額外的 grep() 調(diào)用。
　　
　　recombine() 函數(shù)
　　我應(yīng)該提醒您，基于親本的適合度，親本種群包含有對親本的多個引用。親本越適合，在親本種群中出現(xiàn)的次數(shù)就會多，因而就會有更多機(jī)會繁殖下去。
　　
　　recombine() 使用 List::Util shuffle() 函數(shù)來隨機(jī)組合親本種群。這樣做的效果好于選擇隨機(jī)親本并保持對哪些已經(jīng)是親本的追蹤。另外，以前第二個親本是隨機(jī)選擇出來的，而且我認(rèn)為這樣是對演化的相當(dāng)準(zhǔn)確的描述，但是我改變了那種方法，通過將它們從親本種群中選擇出來然后再插入回去的方式，基于它們的適合度來選擇第二個親本。
　　
　　清單 1. recombine() 函數(shù)
　　
　　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;
　　}
　　
　　注意，如果最后一個親本恰好是自親本種群中獲得的，應(yīng)該如何去設(shè)置 $out_of_parents；那是跳出親本選擇循環(huán)的唯一途徑。
　　
　　構(gòu)建字謎
　　字謎網(wǎng)格由相應(yīng)的名為 build_puzzle() 的函數(shù)來構(gòu)建。種群中的每一個個體細(xì)胞都在內(nèi)部存儲了一個網(wǎng)格位置，所以，當(dāng)我想要找到某個細(xì)胞的網(wǎng)格位置時，不必搜索網(wǎng)格或者維持一個外部散列表。每一個個體還擁有一個“單詞”數(shù)組引用，在這個數(shù)組中保持有在衍生過程中那個個體生成的單詞。
　　
　　另外，我為每個細(xì)胞賦予了一個 ID 屬性，不過只是使用它來檢查算法的正確性。
　　
　　在 build_puzzle() 中，所有的個體都安置于 @puzzle_population。我做了一個 @puzzle_population 的拷貝，這樣我可以從它里面去刪除個體，以使得對個體的改變不會是永久的 —— 它是一個淺拷貝（shallow copy）。選擇塊的順序是隨機(jī)的，再次使用了 List::Util::shuffle()。注意，所有的位置都存儲在一個 [x,y] 數(shù)組中。那樣，數(shù)據(jù)可以像單一的參數(shù)一樣傳遞，而不是多個參數(shù)。
　　
　　清單 2. build_puzzle() 函數(shù)
　　
　　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 的計數(shù)器。由于 Perl 沒有內(nèi)存分配問題，所以對我來說缺陷的最主要來源就是追蹤計數(shù)器變量的錯誤（錯誤的初始化，錯誤的增量，或者錯誤的邊界）。這并不是說我在編寫 Perl 程序的時候出現(xiàn)了很多缺陷，只是我發(fā)現(xiàn)計數(shù)器變量會增加使用時出現(xiàn)缺陷的可能性。
　　
　　現(xiàn)在登場的是 choose_tile()。字謎中的每一個網(wǎng)格位置都會調(diào)用它來選擇一個將成為字謎塊的細(xì)胞。在為網(wǎng)格