|
基于遺傳算法和神經(jīng)網(wǎng)絡(luò)的虛擬生物
丁哲航
2015年01月09日（第一版） PDF格式的本文、演示視頻、極其糟糕的源代碼可以從百度云下載 http://pan.baidu.com/s/1eQtOcsq (人人網(wǎng)的文章排版功能真令人惡心，建議看PDF版)
前言
本文將要介紹的是我自己編寫的一個虛擬生物程序。程序中，一個由人工神經(jīng)網(wǎng)絡(luò)控制的虛擬生物在一個存在障礙物的平面中運動，撿拾散落的物體。這確實是個聽起來很平淡的的場景，但是這里控制虛擬生物的神經(jīng)網(wǎng)絡(luò)不是特意設(shè)計出來的，而是通過遺傳算法從零開始進化得來的。也就是說，最開始這個神經(jīng)網(wǎng)絡(luò)完全是一團隨機數(shù)，隨著不同個體間的競爭——撿拾物體的能力——不斷淘汰能力弱小的個體，最終使得種群內(nèi)的個體越來越強。
我第一次接觸遺傳算法和神經(jīng)網(wǎng)絡(luò)是2013年年初，當時買了兩本書，一本是Mitchell T.M.的《機器學(xué)習(xí)》，另一本是Melanie Mitchell的《復(fù)雜》，這兩本書事后證明都非常有價值?！稒C器學(xué)習(xí)》中有關(guān)于神經(jīng)網(wǎng)絡(luò)章節(jié)（同樣有遺傳算法，但是當時還沒看到）。作為教科書，里面有很詳細的討論，我也試過自己用matlab和C寫過幾個框架，不過一直沒有真正用過。《復(fù)雜》是一本科普書，里面有作者給出的一個遺傳算法的應(yīng)用例子，本文的程序就是那個例子的升級版本。這個例子會在下一個章節(jié)做介紹。順便一提的是，當時購買《復(fù)雜》是因為自己對分形和混沌現(xiàn)象相當有興趣（意思就是學(xué)術(shù)水平其實是民科級），在讀完書后，我才明白自己的感興趣的這類奇奇怪怪的東西叫做復(fù)雜性科學(xué)（Complexity）。雖然現(xiàn)階段我對這類東西完全停留在“覺得有趣好玩”的階段，純粹用來自娛自樂，不過誰知道以后會發(fā)生什么呢。
背景知識 遺傳算法
遺傳算法是進化算法的一種。它模擬達爾文進化論的物競天擇原理，不斷從種群中篩選最優(yōu)個體，淘汰不良個體，使得系統(tǒng)不斷自我改進。在系統(tǒng)中，每個個體具有一串遺傳信息，這串信息代表了我們所要優(yōu)化對象的全部特征。算法維持一個由一定數(shù)量個體組成的種群，每一輪，算法需要計算每個個體的適應(yīng)度，然后根據(jù)適應(yīng)度選出一定數(shù)量存活的個體，同時淘汰掉剩余落后的個體。隨后，幸存的個體將進行“繁殖”，填補因為淘汰機制造成的空缺。所謂的繁殖，就是個體創(chuàng)造出和自己相同的副本。然而為了實現(xiàn)進化，必須要有模仿基因突變的機制。因此在復(fù)制副本的時候也應(yīng)當使得遺傳信息產(chǎn)生微小的改變。選擇-繁殖-進化這樣的過程反復(fù)進行，就能實現(xiàn)種群的進化。
數(shù)學(xué)上，這也可以被理解為在高維空間中尋找最優(yōu)解的問題。如果個體的“基因”用兩個數(shù)字（x，y）表示，而其輸出的“表現(xiàn)型”也用一個數(shù)字（z）表示的話，那么遺傳算法的過程就等同于在一個二維曲面（F (x，y，z) = 0）上尋找一個特定解——比如最大值。初始的時候，種群的各個個體隨機分布在曲面的各個地方。每一輪，篩選出這些個體中輸出值z較高的個體，然后拷貝出若干個副本，令其沿著曲面的不同方向隨機挪動一小段。這樣，向高處移動的個體將被保留，向低處移動的個體會被淘汰。并且總的趨勢是所有個體都在往高處移動。但是，這樣的機制完全有可能使得個體收斂到局部最優(yōu)，而不是全局最優(yōu)。克服這個問題的直接辦法就是使種群的規(guī)模盡可能大，提高初始個體出生在全局最優(yōu)附近的概率。在現(xiàn)實中，遺傳算法處理的問題通常是復(fù)雜的、無法用簡單算法優(yōu)化的非線性問題。
上一節(jié)中，我提到了《復(fù)雜》一書展示過一個虛擬生物的例子。那個例子同樣是一個撿拾物品的虛擬機器人，但是生物在一個離散的空間（棋盤格）上運動，同時也沒有障礙物阻攔。一個數(shù)字串被用來作為機器人的基因。機器人通過周身的九個格子的狀態(tài)編碼出一個序號，然后從數(shù)字串中找到對應(yīng)的“基因”，通過數(shù)字找到對應(yīng)的操作。我在讀完那一章節(jié)后也親自編程嘗試實現(xiàn)了這個實驗。經(jīng)過百代的進化，機器人成功進化出出色的撿拾罐子的能力（考慮到其只有一格的視野）。但是這還不夠令人滿意，因為對于在離散棋盤格上運動撿拾的機器人，靠手工設(shè)計的人工智能也能工作得非常好，沒法體現(xiàn)出遺傳算法的強大能力。我希望能夠看到一個更加復(fù)雜和絢麗的系統(tǒng)。
人工神經(jīng)網(wǎng)絡(luò)
人工神經(jīng)網(wǎng)絡(luò)，顧名思義是對大腦神經(jīng)系統(tǒng)的模擬。一個神經(jīng)網(wǎng)絡(luò)由大量互相連接的神經(jīng)元組成，一個神經(jīng)元可以向相連的神經(jīng)元傳遞信號。經(jīng)典的人工神經(jīng)網(wǎng)絡(luò)由三層神經(jīng)元組成，分別稱為輸入層、隱藏層和輸出層。每一層都包含了若干數(shù)量的神經(jīng)元，每一個神經(jīng)元都和下一次的所有神經(jīng)元相連。輸入層和輸出層的神經(jīng)元數(shù)量由系統(tǒng)需要的輸入和輸出值個數(shù)決定，隱藏層神經(jīng)元的數(shù)量則決定了神經(jīng)網(wǎng)絡(luò)運算能力。
神經(jīng)網(wǎng)絡(luò)進行運算時，首先輸出信號被加載的輸入層的各個神經(jīng)元。隨后，每個輸入層的神經(jīng)元將信號按一定權(quán)值傳遞給下一層（隱藏層），而隨后隱藏層在響應(yīng)了來自輸入層的信號后再以同樣的方式將信號傳遞給輸出層。輸出層響應(yīng)了來自隱藏層的信號后，得到最終的輸出。神經(jīng)網(wǎng)絡(luò)的輸出依賴于復(fù)雜網(wǎng)絡(luò)之間的信號傳遞。就如同人腦一樣，通常很難直接解釋神經(jīng)網(wǎng)絡(luò)內(nèi)在的邏輯。  
神經(jīng)元的連接是單向的，每一條連接都有一個權(quán)值，此外接收信號的神經(jīng)元自身也有固有的偏置值。當信號傳遞時，神經(jīng)元得到的信號是偏置值加上各個輸入神經(jīng)元信號和相應(yīng)連接的權(quán)值相乘的總和。但是這個和值依然不是最終的信號值，還需要通過一個函數(shù)變換，通常被稱為激活函數(shù)（activation function），不過我更喜歡稱為“響應(yīng)”。這個響應(yīng)函數(shù)是一個非線性函數(shù)，其中一個常用的選擇是反正切函數(shù)。非線性的響應(yīng)函數(shù)是人工神經(jīng)網(wǎng)絡(luò)工作的關(guān)鍵，否則這種三層式的經(jīng)典神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)就只能進行線性變換（可以直接等效成若干個矩陣的相加和相乘）。這種非線性的響應(yīng)使得整個神經(jīng)網(wǎng)絡(luò)可以擬合復(fù)雜的空間。需要注意的是，通常這些非線性函數(shù)會在正負兩個方向迅速收斂至兩個極值，這使得神經(jīng)網(wǎng)絡(luò)的每次響應(yīng)輸出其實都是布爾值（也就是代表“是”和“否”的二值，對反正切函數(shù)作為響應(yīng)函數(shù)的情形來說，可以用值的正負來判斷）。因此，盡管輸出的值是浮點數(shù)，但通常不把輸出作為模擬信號來理解，而視為二值數(shù)字信號。比如說，輸出值可以用來選擇自動駕駛的汽車向左或者向右轉(zhuǎn)彎，但是不宜用來控制速度的大小。量值的控制可以用編碼的方式實現(xiàn)。
實驗系統(tǒng)設(shè)計
環(huán)境和虛擬生物
本程序中，虛擬生物活動的空間是一塊平面區(qū)域。在這塊區(qū)域中，隨機分布著若干塊以線段形態(tài)存在的路障，以及若干質(zhì)點形態(tài)的物品。此外，平面的四周也被圍上了路障以防越界。虛擬生物出生在區(qū)域中的隨機位置，具有位置和朝向兩個屬性。生物可以在平面區(qū)域自由移動。生物具有一個以自身為中心的圓形區(qū)域，當這個區(qū)域和物品相接觸時，視為生物拾取到物品（分數(shù)獎勵），當生物和障礙、邊界相接觸時，生物的運動會被阻礙。
每一刻（運算周期）生物可以得知如下信息。第一個信息是離個體最近的物品的相對坐標，以個體當前朝向為縱坐標，其垂直方向為橫坐標。第二個信息是通過個體和最近物品間的線段是否和任何路障相交。第三個信息是生物上一次的行動是否撞到了路障。這三個信息的配置是合理的，沒有給出太多信息使得神經(jīng)網(wǎng)絡(luò)失去智能的意義，也不至于要求神經(jīng)網(wǎng)絡(luò)做出過于復(fù)雜而不切實際的計算。而且這樣的配置也很符合現(xiàn)實的生物特性。這三個信息可以類比為生物的聽覺、視覺和觸覺——聽覺可以感知物體相對自己朝向的位置、視覺可以判斷自身和目標間障礙、觸覺可以實際感知面前的路障。生物可以在每一刻選擇是否執(zhí)行下面兩項動作：前進一步和改變朝向。一步前進的距離是固定的，生物要么決定前進這個距離，要么決定不前進。生物的轉(zhuǎn)向可以是向左或者向右一定區(qū)間內(nèi)的任意值。
神經(jīng)網(wǎng)絡(luò)
采用的神經(jīng)網(wǎng)絡(luò)使用10個輸入神經(jīng)元、16個隱藏神經(jīng)元和9個輸出神經(jīng)元。其中有6個輸入和輸出神經(jīng)元相互連接。剩下的四個輸入和三個輸出則有固定意義。輸入內(nèi)容為前述的三個輸入信息，其中坐標需要用兩個神經(jīng)元。第一個輸出值用來控制是否前進，第二和第三個值同時決定生物的轉(zhuǎn)向程度。程序采用差分——兩個輸出值的差值來決定生物的轉(zhuǎn)向。采用這種方法的原因是，如果只用一個值來決定轉(zhuǎn)向角度的話，由于響應(yīng)函數(shù)的特性，結(jié)果幾乎必然是只能向左或者向右轉(zhuǎn)動固定的角度，而不能維持直線運動。如果采用差分的情況，則可以實現(xiàn)這樣的效果（當兩個值接近相同則不轉(zhuǎn)向）。將其中6個輸入輸出相連的目的是將反饋機制引入網(wǎng)絡(luò)，模擬了生物的記憶能力。
進化
實驗中，遺傳算法的種群規(guī)模被設(shè)定為40，即每代有40個互不相同的個體進行競爭。每個個體將單獨在虛擬環(huán)境中進行24輪游戲，在每輪8000步的限制中，個體被要求盡可能多的撿拾物體。每觸碰到一個物體可以獲得1分。最后每輪的平均得分作為生物的適應(yīng)度被記錄。進化時，篩選出其中最優(yōu)秀的10個幸存?zhèn)€體。每個幸存的個體可以繁衍三個后代。幸存的個體和繁衍的后代一起加入下一代的種群。繁衍包括復(fù)制和變異兩個環(huán)節(jié)。復(fù)制是將原有個體的神經(jīng)網(wǎng)絡(luò)原模原樣拷貝一份到新個體，隨后變異環(huán)節(jié)會隨機選擇神經(jīng)網(wǎng)絡(luò)中某個權(quán)值或偏置值，修改為一個隨機數(shù)。
實驗結(jié)果
行為
進化開始時，每個個體都是完全隨機產(chǎn)生的。然而此時已經(jīng)有了優(yōu)劣之分。絕大多數(shù)個體的平均分都接近零分。它們要么在原地打轉(zhuǎn)，要么沖向一個障礙物就此僵死。初代最好的個體能夠獲得鶴立雞群的11分平均分，相比之下，排名隨后的幾個個體分數(shù)都不到它的一半。這個個體能夠表現(xiàn)出向物品移動的傾向（盡量使得切向坐標減小、同時保持不斷移動），但基本的運動模式只是在平面上繞圈圈，偶爾會走走直線?；旧?，拾到物品是憑運氣。下一代種群的個體里，前一代一分不得的個體已經(jīng)被淘汰了，每個個體或多或少能夠拿到個位數(shù)的平均分，上一代的冠軍個體到這一代依然名列前茅，它的后代也基本能拿到和它差不多的分數(shù)。我在程序中給每個個體加入了特定的標記，使得能夠追尋不同“家族”的演化路線。但是這個功能只有前幾代有用，因為用不了多久整個種群就會被單一家族所統(tǒng)治。到了第四代，整個種群只剩下三個家系在互相競爭，其中最衰微的一家在下一代就被徹底淘汰。在初代鶴立雞群的個體的后代在第五代也差點被另一個家族的后起之秀驅(qū)逐殆盡，但因為第六代時的一個基因突變重新奪回了優(yōu)勢地位，而它的競爭對手在第九代被完全滅絕。
此時我們種群中的冠軍個體以及能拿到接近30分的成績了。我們的生物現(xiàn)在已經(jīng)懂得主動尋找食物了。它基本上表現(xiàn)出兩種運動策略。第一種是瞄準目標猛沖，但由于對神經(jīng)的控制依然沒有進化完全，路線總是歪歪扭扭的，有時還瞄不準目標。生物在吃到物體后往往會繼續(xù)前行，直到一頭扎進邊界障礙，然后才調(diào)整方向?qū)氏乱粋€目標。另一種策略有趣的多，在猛沖的過程中，生物有時候會突然往奇怪的方向轉(zhuǎn)彎，劃出一個圓圈然后吃到和轉(zhuǎn)彎方向相反位置的物體。在特定的情況下，它甚至能在畫弧線的過程中吃到好幾個排成線的目標。
進化的初期速度是飛快的，每隔幾代就會出現(xiàn)一個特別的個體。隨著它將基因散播給它的后代，那個特別的性狀就會迅速進化，使得種群的分數(shù)直線上升。第十代時就出現(xiàn)了這樣的情況，第九代的冠軍個體的一個后代產(chǎn)生了一個特別的突變，獲得了54分的高分。要知道在當時，前一代的得分普遍還在30分浮動，即使是那一代的冠軍個體——突變個體的父親，也只拿到了38分。這個54分的個體與它的后代迅速占領(lǐng)了種群。到第十三代時，那個突變體的孫子將分數(shù)改進到了63分，將其祖父輩的平均分翻了倍。這一代的個體已經(jīng)不會在像過去那樣橫沖直撞了，“反向旋轉(zhuǎn)”的奇怪撿拾策略成為了主導(dǎo)。這個奇怪的策略很可能是為了減小和環(huán)境中障礙的碰撞幾率而演化出的。到了這一代，個體已經(jīng)不太被障礙拌住而無法脫身了。因此，提升脫離障礙的技巧也成為了重要的進化驅(qū)動需求。
在這次突變之后，種群的冠軍得分基本上呈快速的線性增長。到第30代的時候，冠軍個體的分數(shù)已經(jīng)達到了120分。那種旋轉(zhuǎn)進食的奇怪策略到這一代已經(jīng)完全消失了，取而代之的是沿著連人類都會贊嘆不已的優(yōu)雅曲線在一個個物體間穿梭。生物對障礙的規(guī)避能力也大大提升，一旦觸碰到障礙，就會立即側(cè)向一邊，繞著圈離開。
到了這一步，物種的神經(jīng)網(wǎng)絡(luò)已經(jīng)接近于成熟，進化開始放緩，行為的變化也變得十分細微。種群在100代的時候觸碰到了180的分數(shù)線，隨后以非常非常緩慢而掙扎的方式慢慢做著細微的改善。它們在六七白代的演化后最終停留在了200分這樣的高分。從120分到200分具有很大的能力差距，但是他們的運動表現(xiàn)差異并不是那么明顯。我們只知道他的失誤概率小了，掙脫障礙更快了，然而基本的運行模式改變并不大。這也和現(xiàn)實是一樣的，一個表現(xiàn)型成熟之后，自然不會再有質(zhì)的改變。如果環(huán)境并不改變，那么剩下的工作就只是修修補補。，本質(zhì)上毫無智能、只能得到有限信息的虛擬生物，已經(jīng)運行得遠遠比開著上帝視角的人類玩家更加強大了。
進化
并不是每一次進化都能達到如此高的水準。每次運行進化的程序都會得到不同種群。這些不同的進化產(chǎn)物有著類似但又不同的生存策略，比如一些種群碰到障礙會沿著邊緣劃開，一些種群則選擇繞一個半圓離開。不同的進化實例產(chǎn)生不同的種群，最終也收斂到了不同的分數(shù)。前一節(jié)描述的進化軌跡是我同時進行的五次實驗中最好的一次結(jié)果。其余的四次進化收斂到了不到200的分數(shù)。最差的僅僅只有100分的成績。
進化系統(tǒng)的局部收斂問題的確是遺傳算法的一個難點所在。盡管很多時候局部最優(yōu)已經(jīng)十分出色，但是能收斂到全局最優(yōu)自然是最好。我應(yīng)對這個問題最簡單方法就是：多進化幾個版本，然后取最好的。 
分數(shù)估計
進化系統(tǒng)的成功與否，和能否有效精確地估計個體適應(yīng)度有很大關(guān)系。在本系統(tǒng)中，每個個體被放到虛擬空間中進行模擬計算，通過多次和長期測試力求獲得精確的結(jié)果。但是實驗的結(jié)果表明，即使如此每個個體多次進行適應(yīng)度估計得到的偏差依然很大。右圖是對一個初期個體進行500次測試后得到的分數(shù)分布?？梢钥吹?，得分分布在一個很大區(qū)間中?？傮w來說，得分大致呈正態(tài)分布，同時在低分段有較多的次數(shù)。這些結(jié)果很容易理解。生物因為不同場景會遇到不同的阻礙，突破這些阻礙的時間各不相同，同時有些阻礙是生物無法突破的。如此造就了圖中的分布形狀?？梢粤舷?，隨著個體進化的成熟，被障礙卡住致死的情形越來越少，這個分布將越來越接近于正態(tài)分布，并且方差會越來越小。但是每次測試的平均值總是會有一定浮動。由于后期所有個體的基因都相當接近，分數(shù)也大體相同。相對巨大的方差波動必然使得任何個體都會在若干輪后爆出冷門淘汰。因此，即使到了最后的收斂期，也往往沒有一個個體能夠在種群中存活超過四輪的——即使理論上他們是永生的。 
記憶
在編寫這個程序之前，我猜測有記憶的生物和無記憶的生物可能會表現(xiàn)出很大的區(qū)別。在早先一些小規(guī)模的測試中，無記憶的種群也確實沒有出現(xiàn)如有記憶個體那樣復(fù)雜的行為——通常是一圓弧的形式一段一段地撿拾物品，并且只有很少很簡陋的避障策略。然而，隨著程序的改進和運算規(guī)模的增加，無記憶個體的表現(xiàn)并不明顯比有記憶個體差。很多此前認為只有有記憶個體才能實現(xiàn)的策略，無記憶個體也實現(xiàn)了——如方向控制、避障等等。不過關(guān)于有無記憶的比較，現(xiàn)在還不充分，因此不適合得出很確定的結(jié)論。
展望
本系統(tǒng)實現(xiàn)的是幾年來一直想做的神經(jīng)網(wǎng)絡(luò)和遺傳算法的結(jié)合。虛擬生物當前運行在一個虛擬的（而且其實并不精確的）運動學(xué)模型中。事實上這些工作在幾十年前就已經(jīng)被研究過了，而且內(nèi)容要豐富的多。Youtube上有很多Virtual Creature的設(shè)計，其中大部分都采用了物理引擎來模擬力學(xué)相關(guān)的環(huán)境。比如要求虛擬生物穩(wěn)定站立、行走乃至跳高、游泳等。
當前的設(shè)計總的來說是很簡單的試驗品，不過已經(jīng)展現(xiàn)出遺傳算法和神經(jīng)網(wǎng)絡(luò)強大的智能行為。未來我想到的改進方向有這樣幾種。
更現(xiàn)實的輸入。本系統(tǒng)中，為了簡化系統(tǒng)，個體最重要的輸入是最近物品的坐標。這確實有些“作弊”的嫌疑。這之后我想改進這部分設(shè)計，引入更加真實的輸入。比如單純給出距離信號，需要生物移動來判斷位置（如無線電側(cè)向——事實上當前這個虛擬環(huán)境的設(shè)計就是受到無線電測向的啟發(fā)）；或者也可以生物提供雙目視覺，讓生物主動去尋找和判斷目標。
個體間的交互。復(fù)雜性科學(xué)研究的本質(zhì)是多個簡單元素交互產(chǎn)生的復(fù)雜現(xiàn)象，這不單單體現(xiàn)在神經(jīng)網(wǎng)絡(luò)通過神經(jīng)元互聯(lián)產(chǎn)生的復(fù)雜信號模式或者遺傳算法通過大量簡單變異累計出奇妙的基因，還體現(xiàn)在個體生物之間的交互上。我希望之后能建立起一些生物交互的系統(tǒng)，觀察不同獨立的虛擬生物個體能否進化出協(xié)作和對抗的機制。
更復(fù)雜的記憶機制。當前的記憶實現(xiàn)僅僅是將輸入和輸出連接。從數(shù)字電路的思想出發(fā)，這已經(jīng)是時序電路的全部了。但在實際操作過程中，這樣的反饋機制只能帶來瞬時的記憶，而無法形成長期記憶。我猜讓生物自行進化出如內(nèi)存這樣的機制需要很多很多神經(jīng)元以及很長很復(fù)雜的演化路線，但是回報可能也是巨大的。試想一個能偵查并記住一張地圖的生物是怎么樣的，一定比只能記住三步前撞到墻這種短期事件的生物更加有趣。
自更新的神經(jīng)網(wǎng)絡(luò)。當前的進化模式是隨機地修改神經(jīng)網(wǎng)絡(luò)，也就是達爾文的自然突變模式。但是如果我們把用進廢退也加入模型中會怎么樣，比如一個神經(jīng)網(wǎng)絡(luò)可以產(chǎn)生一些輸出來修改自身，會不會產(chǎn)生更有趣的結(jié)果？
未來還有很多路要走，盡管這些內(nèi)容可能幾十年前就已經(jīng)被人玩剩了。但不管怎么說，有趣的東西總是值得一玩的。
|
