作者:bitsCN整理   來(lái)源:ChinaITLab 

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