­

如何用遺傳演算法進化出一隻聰明的小鸚鵡

  • 2019 年 10 月 6 日
  • 筆記

問題

現在有一些樣本數據,如下表所示。你是否能找到其中的規律,然後計算出新樣本的output是多少?

input

output

樣本1

5, 8, 7

9

樣本2

2, 8, 4

6

樣本3

3, 0, 5

3

樣本4

9, 12, 13

15

新樣本

10, 6, 8

?

乍一看,規律似乎並不明顯。

仔細看,可能會發現其中的規律:output=input1+input2/2+input3*0,因此問號處的值應該是13。

現在,我們想讓一隻小鸚鵡來做這個事情。這當然不是現實中的小鸚鵡,而是我們用程式碼寫的小鸚鵡。

小鸚鵡

小鸚鵡要想解出上面的題目,必須會「思考」。這裡的思考,我們可以理解為:具有將input轉換成output的能力。我們選擇神經網路作為鸚鵡的大腦。

神經網路

我們知道,人腦中有無數個神經元,神經元之間通過軸突連接。當某個神經元接收到足夠多的訊號後,就會被「觸發」。而被「觸發」的神經元會發送訊號到臨近的神經元,臨近的神經元接收到足夠的訊號後,又會被「觸發」。這樣的過程被稱之為「思考」。

我們可以用程式模擬這個過程。為了簡化,這裡只使用一層網路。我們給每個軸突(連接神經元的線)設置一個權重,每一個input乘以相應的軸突權重會得出一個值,然後對這些值再求和,得出output。即output=input1*w1+input2*w2+input3*w3

這就是一個簡單的「大腦」。大腦是否聰明,取決於[w1,w2,w3]的值的組合。如果這三個權重值能夠滿足提出的問題,那它就是「聰明」的,否則就是「笨」的。於是,剛才的問題就轉換成:如何找到一組「聰明」的權重組合。

對於文章開頭的問題,我們已經知道,[w1=1,w2=0.5,w3=0]這種組合是最好的。那,如何生成這樣的「大腦」呢?

上帝之手

現在,我們可以扮演上帝的角色,隨性的創造物種。假設我們創造了一隻鸚鵡,它的腦子就是一個有3個權重的神經網路。這隻鸚鵡只會做上面的題(但不一定能做好)。它的大腦是隨機生成的,假設他的權重組合為[0.5,0.3,1.2]。

此時,這隻鸚鵡就可以用大腦去「思考」上面的問題了。它會先看樣本數據,從樣本1開始看。這隻鸚鵡根據input算出來的output是:0.5*5+0.3*8+1.2*7=13.3,而樣本給出的output是9。於是它的誤差(error1)是13.3-9=4.3。同樣,還可以知道這隻鸚鵡計算其它樣本時的誤差,它們分別是:

error2=2.2    error3=4.5    error4=8.7

我們知道,鸚鵡計算得越准(誤差越小),就越聰明。因此,我們可以給鸚鵡的智商設定一個計算方法:

根據這個公式,可以算出這隻鸚鵡的智商(intelligence)為9.15

我們再隨機創建第二隻鸚鵡。假設它的大腦的神經網路權重組合為[0.8,0.7,0.1]。

根據同樣的方法,可以算出它的智商為35.65。它比第一支鸚鵡「聰明」!

進化

種群

我們可以創建一個鸚鵡種群,這個種群里有若干只鸚鵡,比如有100隻。每個鸚鵡的智商也各不相同。下一步就是讓這個種群進行自我進化。

進化

物競天擇、適者生存!大自然的這個法則,讓地球上的物種不斷進化,誕生了越來越高級的物種,乃至出現了我們人類。我們的這個鸚鵡種群也可以通過進化變得越來越聰明。

種群中的鸚鵡比拼的是智商。每一次比拼,我們把低智商的鸚鵡淘汰掉,把高智商鸚鵡留下來。然後,讓留下來的鸚鵡繁衍下一代,這樣它們和下一代的個體會組成一個新群體。然後再來一次全員智商比拼,再把低智商鸚鵡淘汰掉,高智商留下。留下的鸚鵡再次繁殖。這樣不斷迭代,經過若干代的篩選後,最後留下的就是特別聰明的鸚鵡。

在最後留下來的鸚鵡中,找到最聰明的那個。讓它去「思考」文章開頭提到的問題,它會給出一個不錯的答案!

繁衍

現實中的鸚鵡是雙性繁殖,那是長期進化的結果。我們的鸚鵡還很原始,只能單性繁殖:)

繁殖的方式是把自己複製一份,再做一次「基因突變」。所謂「基因突變」就是對神經網路的權重進行微調。比如有一隻鸚鵡,它的大腦神經網路是[2, 3, 3.5],它繁衍的某一個後代可能是[2, 3.01, 3.5]或[1.98, 3, 3.5]等。

這樣,後代基本保留了父代智商,又做了微調。這種微調可能是正向的(更聰明),也可能是負向的(更笨)。

程式碼

import random  import copy  import numpy as np    class Parrot():      brain = 2 * np.random.random((3, 1)) - 1      intelligence = 0        def think(self,inputs):          return np.dot(inputs,self.brain)        '''      基因變異      '''      def mutation(self,max=0.05):          #隨機選中一個神經網路權重,進行微調          index = np.random.randint(0,len(self.brain))          adjustment = np.random.uniform(-max,max)          self.brain[index] +=adjustment        def copy(self):          child = Parrot()          child.brain = copy.copy(self.brain)          child.intelligence = self.intelligence          return child      class GA():      def __init__(self, count):          #進化的代數          self.gen_num = 0          # 種群中個體數量          self.count = count          # 種群個體要儘可能得去滿足input和output關係          self.inputs,self.outputs=self.load_data()          # 隨機生成初始種群          self.population = self.gen_population(count)        def load_data(self):          inputs = np.array([[5, 8, 7], [2, 8, 4], [3, 0, 5], [9, 12, 13]])          outputs = np.array([[9, 6, 3, 15]]).T          return inputs,outputs        def create_parrot(self):          parrot = Parrot()          parrot.brain = 2 * np.random.random((3, 1)) - 1          parrot.intelligence = self.calc_intelligence(parrot)          return parrot        """      獲取初始種群      """      def gen_population(self,count):          return [self.create_parrot() for i in range(count)]        #計算適應度      def calc_intelligence(self, parrot):          errors = self.outputs - parrot.think(self.inputs)          intelligence = 1/np.sum(np.sqrt(np.square(errors)))          return intelligence        '''      繁殖      '''      def reproduction(self, mothers):          # 新出生的孩子,最終會被加入存活下來的父母之中,形成新一代的種群。          children = []          # 需要繁殖的孩子的量          target_count = len(self.population) - len(mothers)          # 開始根據需要的量進行繁殖          while len(children) < target_count:              mother = mothers[np.random.randint(0,len(mothers))]              child = mother.copy()              child.mutation()              children.append(child)          self.population = mothers + children        '''      選擇      '''      def selection(self, retain_rate, random_select_rate):          # 計算每一個鸚鵡的智商          graded = [(self.calc_intelligence(parrot), parrot) for parrot in self.population]          # 智商從大到小進行排序          graded = [x[1] for x in sorted(graded, key = lambda graded: graded[0], reverse=True)]          # 選出智商最高的一部分鸚鵡          retain_length = int(len(graded) * retain_rate)          retain_parrots = graded[:retain_length]          # 選出智商不高,但是倖存的鸚鵡          for parrot in graded[retain_length:]:              if random.random() < random_select_rate:                  retain_parrots.append(parrot)          return retain_parrots        '''      進化      retain_rate:保留最聰明個體的比例      random_select_rate:不夠聰明的個體中,也要保留一定比例的個體,以保持物種的多樣性。      '''      def evolve(self,retain_rate=0.2, random_select_rate=0.2):          self.gen_num += 1          mothers = self.selection(retain_rate, random_select_rate)          self.reproduction(mothers)        def smartest_parrot(self):          graded = [(self.calc_intelligence(parrot), parrot) for parrot in self.population]          graded = [x[1] for x in sorted(graded, key = lambda graded: graded[0], reverse=True)]          return graded[0]    if __name__ == '__main__':      #種群數量為100      ga = GA(100)      for x in range(300):          ga.evolve()      winner = ga.smartest_parrot()      print("brain=",winner.brain.T)      print("output=",winner.think(np.array([10, 6, 8])))

運行

python3 ga.py 

運行結果

brain= [[0.99293629 0.498883   0.00599333]]  output= [12.97060759]

新樣本中的output應該是13,進化出來的鸚鵡給出的答案是12.97060759,已經相當接近!

它的大腦[0.99293629, 0.498883, 0.00599333]與最優解[1,0.5,0]非常接近!

這就是自然選擇的力量!

讓我們向大自然的規則致敬!