如何用遗传算法进化出一只聪明的小鹦鹉

• 2019 年 10 月 6 日
• 笔记

问题

现在有一些样本数据，如下表所示。你是否能找到其中的规律，然后计算出新样本的output是多少？

乍一看，规律似乎并不明显。

仔细看，可能会发现其中的规律：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]非常接近!

这就是自然选择的力量！

让我们向大自然的规则致敬！