| 導購 | 订阅 | 在线投稿
分享
 
 
當前位置: 王朝網路 >> perl >> 功能豐富的Perl:遺傳算法仿真多細胞機體
 

功能豐富的Perl:遺傳算法仿真多細胞機體

2008-05-19 06:25:41  編輯來源:互聯網  简体版  手機版  評論  字體: ||
 
 
  我的前兩篇關于使用 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()

  }

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

  
 
 
 
上一篇《Perl的經典用法:讀入多個記錄》
下一篇《功能豐富的Perl:有趣的Ion窗口管理器》
 
 
 
 
 
 
日版寵物情人插曲《Winding Road》歌詞

日版寵物情人2017的插曲,很帶節奏感,日語的,女生唱的。 最後聽見是在第8集的時候女主手割傷了,然後男主用嘴幫她吸了一下,插曲就出來了。 歌手:Def...

兄弟共妻,我成了他們夜裏的美食

老鍾家的兩個兒子很特別,就是跟其他的人不太一樣,魔一般的執著。兄弟倆都到了要結婚的年齡了,不管自家老爹怎麽磨破嘴皮子,兄弟倆說不娶就不娶,老父母爲兄弟兩操碎了心...

如何磨出破洞牛仔褲?牛仔褲怎麽剪破洞?

把牛仔褲磨出有線的破洞 1、具體工具就是磨腳石,下面墊一個硬物,然後用磨腳石一直磨一直磨,到把那塊磨薄了,用手撕開就好了。出來的洞啊很自然的。需要貓須的話調幾...

我就是掃描下圖得到了敬業福和愛國福

先來看下敬業福和愛國福 今年春節,支付寶再次推出了“五福紅包”活動,表示要“把欠大家的敬業福都還給大家”。 今天該活動正式啓動,和去年一樣,需要收集“五福”...

冰箱異味産生的原因和臭味去除的方法

有時候我們打開冰箱就會聞到一股異味,冰箱裏的這種異味是因爲一些物質發出的氣味的混合體,聞起來讓人惡心。 産生這些異味的主要原因有以下幾點。 1、很多人有這種習...

《極品家丁》1-31集大結局分集劇情介紹

簡介 《極品家丁》講述了現代白領林晚榮無意回到古代金陵,並追隨蕭二小姐化名“林三”進入蕭府,不料卻陰差陽錯上演了一出低級家丁拼搏上位的“林三升職記”。...

李溪芮《極品家丁》片尾曲《你就是我最愛的寶寶》歌詞

你就是我最愛的寶寶 - 李溪芮 (電視劇《極品家丁》片尾曲) 作詞:常馨內 作曲:常馨內 你的眉 又鬼馬的挑 你的嘴 又壞壞的笑 上一秒吵鬧 下...

烏梅的功效與作用以及烏梅的食用禁忌有哪些?

烏梅,又稱春梅,中醫認爲,烏梅味酸,性溫,無毒,具有安心、除熱、下氣、祛痰、止渴調中、殺蟲的功效,治肢體痛、肺痨病。烏梅泡水喝能治傷寒煩熱、止吐瀉,與幹姜一起制...

什麽是脂肪粒?如何消除臉部脂肪粒?

什麽是脂肪粒 在我們的臉上總會長一個個像脂肪的小顆粒,弄也弄不掉,而且顔色還是白白的。它既不是粉刺也不是其他的任何痘痘,它就是脂肪粒。 脂肪粒雖然也是由油脂...

網絡安全治理:國家安全保障的主要方向是打擊犯罪,而不是處置和懲罰受害者

來源:中國青年報 新的攻擊方法不斷湧現,黑客幾乎永遠占據網絡攻擊的上風,我們不可能通過技術手段杜絕網絡攻擊。國家安全保障的主要方向是打擊犯罪,而不是處置和懲罰...

河南夫妻在溫嶺網絡直播“造人”內容涉黃被刑事拘留

夫妻網絡直播“造人”爆紅   1月9日,溫嶺城北派出所接到南京警方的協查通告,他們近期打掉了一個涉黃直播APP平台。而根據掌握的線索,其中有一對涉案的夫妻主播...

如何防止牆紙老化?牆紙變舊變黃怎麽辦?

如何防止牆紙老化? (1)選擇透氣性好的牆紙 市場上牆紙的材質分無紡布的、木纖維的、PVC的、玻璃纖維基材的、布面的等,相對而言,PVC材質的牆紙最不透氣...

鮮肌之謎非日本生産VS鮮肌之謎假日貨是謠言

觀點一:破日本銷售量的“鮮肌之謎” 非日本生産 近一段時間,淘寶上架了一款名爲“鮮肌之謎的” 鲑魚卵巢美容液,號稱是最近日本的一款推出的全新護膚品,産品本身所...

中國最美古詩詞精選摘抄

系腰裙(北宋詞人 張先) 惜霜蟾照夜雲天,朦胧影、畫勾闌。人情縱似長情月,算一年年。又能得、幾番圓。 欲寄西江題葉字,流不到、五亭前。東池始有荷新綠,尚小如...

關于女人的經典語句

關于女人的經典語句1、【做一個獨立的女人】 思想獨立:有主見、有自己的人生觀、價值觀。有上進心,永遠不放棄自己的理想,做一份自己喜愛的事業,擁有快樂和成就...

未來我們可以和性愛機器人結婚嗎?

你想體驗機器人性愛嗎?你想和性愛機器人結婚嗎?如果你想,機器人有拒絕你的權利嗎? 近日,第二屆“國際人類-機器人性愛研討會”大會在倫敦金史密斯大學落下帷幕。而...

全球最變態的十個地方

10.土耳其地下洞穴城市 變態指數:★★☆☆☆ 這是土耳其卡帕多西亞的一個著名景點,傳說是當年基督教徒們爲了躲避戰爭而在此修建。裏面曾住著20000人,...

科學家稱,人類死亡後意識將在另外一個宇宙中繼續存活

據英國《每日快報》報道,一位科學家兼理論家Robert Lanza博士宣稱,世界上並不存在人類死亡,死亡的只是身體。他認爲我們的意識借助我們體內的能量生存,而且...

《屏裏狐》片頭曲《我愛狐狸精》歌詞是什麽?

《我愛狐狸精》 - 劉馨棋   (電視劇《屏裏狐》主題曲)   作詞:金十三&李旦   作曲:劉嘉   狐狸精 狐狸仙   千年修...

 
 
 
  我的前兩篇關于使用 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()   }   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()。字謎中的每一個網格位置都會調用它來選擇一個將成爲字謎塊的細胞。在爲網格   
󰈣󰈤
 
 
 
  免責聲明:本文僅代表作者個人觀點,與王朝網路無關。王朝網路登載此文出於傳遞更多信息之目的,並不意味著贊同其觀點或證實其描述,其原創性以及文中陳述文字和內容未經本站證實,對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾,請讀者僅作參考,並請自行核實相關內容。
 
 
小龍女彤彤之情溢皇都
龔潔
智能手機形象美女
崔潔彤
回家的路上----
中國一站(哈爾濱)
清明植物園的花。
桃花堤印象之豎版
 
>>返回首頁<<
 
 熱帖排行
 
 
 
 
© 2005- 王朝網路 版權所有