遗传算法是一种本质上类似于进化过程的优化技术。这可能是一个粗略的类比，但如果你眯着眼睛看，达尔文的自然选择确实大致类似于生产完全适合在其环境中茁壮成长的生物体的优化任务。在这篇文章中，我将展示如何在Python中实现遗传算法，在几个小时内“进化”出一个垃圾收集机器人。背景我遇到的关于遗传算法原理的最佳教程来自MelanieMitchell《Complexity: A Guided Tour》的一本关于复杂系统的好书。在其中一章中，Mitchell介绍了一个名为Robby的机器人，其一生的唯一目的就是捡垃圾，并描述了如何使用GA来优化Robby的控制策略。下面我解释了我解决这个问题的方法，并展示了如何在Python中实现该算法。有一些很好的包可以构建这些类型的算法（例如DEAP），但在本教程中我将只使用基本的Python、Numpy和TQDM（可选）。虽然这只是一个玩具示例，但GA在许多实际应用中都有使用。作为一名数据科学家，我经常使用它们进行超参数优化和模型选择。尽管计算量很大，但GA允许我们并行探索搜索空间的多个区域，并且在计算梯度时是一个不错的选择。问题描述一个名叫Robby的机器人生活在一个充满垃圾的二维网格世界中，周围有4堵墙（如下图所示）。该项目的目标是开发一种最佳控制策略，使他能够有效地捡起垃圾而不是撞到墙上。罗比只能看到他周围的四个方块，上、下、左、右，以及他所在的方块。每个方块有3个选择，空的，有垃圾的，或者有一堵墙。因此，罗比有3?=243种不同的情况。罗比可以执行7种不同的动作：向上、向下、向左和向右移动（4种类型）、随机移动、捡起垃圾或静止不动。因此，罗比的控制策略可以编码为由0到6之间的243个数字组成的“DNA”字符串（对应罗比在243种可能情况下应该采取的行动）。方法任何GA的优化步骤如下：生成问题初始随机解的“种群”“遗传”材料被传递给下一代后代重复步骤2和3，直到我们有一组优化的解决方案。在我们的任务中，您创建了第一代初始化为随机DNA字符串的Robbys（对应于随机控制策略）。然后模拟在随机分配的网格世界中运行这些机器人并观察它们的性能。拟合优度机器人的拟合优度取决于它在n次移动中捡起多少垃圾，以及它撞墙的次数。在我们的示例中，机器人每捡起一块垃圾就会获得10分，每次撞到墙壁都会减去5分。然后这些机器人根据与其适应度相关的概率“交配”（即捡起大量垃圾的机器人更有可能繁殖），新一代机器人就诞生了。交配有几种不同的方法可以实现“交配”。在米切尔的版本中，她随机拼接了父母的两条DNA，然后将它们连接在一起，为下一代创造了一个孩子。在我的实现中，我随机分配每个父母的每个基因（即，对于243个基因中的每一个，我掷硬币来决定我继承谁的基因）。比如用我的方法，在前10个基因中，父母和孩子可能的基因如下：Parent1:1440623161Parent2:2430661132Child:2440621161Mutation我们用这个算法复制的自然选择的另一个概念是“突变”。虽然孩子的绝大部分基因都是从父母双方遗传的，但我也考虑到基因突变的可能性很小（即随机分配）。这种突变率使我们能够探索新的可能性。Python实现的第一步是导入所需的包并为此任务设置参数。我已选择这些参数作为起点，但可以对其进行调整，我鼓励您进行试验。"""导入包"""importnumpyasnpfromtqdm.notebookimporttqdm"""设置参数"""#模拟设置pop_size=200#每代机器人数量num_breeders=100#每代能够交配的机器人数量num_gen=400#Totalalgebraiter_per_sim=100#每个机器人的垃圾收集模拟次数moves_per_iter=200#机器人每次模拟可以做的移动次数#网格设置rubbish_prob=0.5#每个网格中出现垃圾的概率grid_size=10#0网格大小（墙壁除外）#进化设置wall_penalty=-5#撞墙扣除的适配点数no_rub_penalty=-1#空方块捡垃圾扣除rubbish_score=10#捡垃圾可得分mutation_rate=0.01#收到变异概率接下来，我们为网格世界环境定义一个类。我们用标签“o”、“x”和“w”表示每个单元格，分别对应于一个空单元格、一个有垃圾的单元格和一堵墙。classEnvironment:"""类，用来表示充满垃圾的网格环境。每个cell可以表示为：'o':empty'x':garbage'w':wall"""def__init__(self,p=rubbish_prob,g_size=grid_size):self.p=p#cell是垃圾的概率self。g_size=g_size#不包括墙#初始化网格并随机分布垃圾self.grid=np.random.choice(['o','x'],size=(self.g_size+2,self.g_size+2),p=(1-self.p,self.p))#设置外方为墙self.grid[:,[0,self.g_size+1]]='w'self.grid[[0,self.g_size+1],:]='w'defshow_grid(self):#打印当前状态的gridprint(self.grid)defremove_rubbish(self,i,j):#从指定的单元格(i,j)清除垃圾ifself.grid[i,j]=='o':#cell已经是空的returnFalseelse:self.grid[i,j]='o'returnTruedefget_pos_string(self,i,j):#returnaA表示单元格(i,j)中机器人“可见”的单元格的字符串returnsself.grid[i-1,j]+self.grid[i,j+1]+self.grid[i+1,j]+self.grid[i,j-1]+self.grid[i,j]接下来，我们创建一个类来表示我们的机器人。这个类包括执行动作、计算拟合和学习从一对父机器人那里学习一种生成新DNA的方法。classRobot:"""用来表示垃圾收集机器人"""def__init__(self,p1_dna=None,p2_dna=None,m_rate=mutation_rate,w_pen=wall_penalty,nr_pen=no_rub_penalty,r_score=rubbish_score):self.m_rate=m_rate#mutation评分self.wall_penalty=w_pen#撞墙的惩罚self.no_rub_penalty=nr_pen#在空方块捡垃圾的惩罚self.rubbish_score=r_score#捡垃圾的奖励self.p1_dna=p1_dna#父母2自己的DNA。p2_dna=p2_dna#parents2的DNA#生成字典从场景字符串中查找基因索引con=['w','o','x']#wall,empty,garbageself.situ_dict=dict()count=0forupincon:forrightincon:fordownincon:forleftincon:forposincon:self.situ_dict[up+right+down+left+pos]=countcount+=1#初始化DNAself.get_dna()defget_dna(self):#初始化机器人ifself的dna字符串。p1_dnaisNone:#没有父母时随机生成DNAself.dna=''.join([str(x)forxinnp.random.randint(7,size=243)])else:self.dna=self.mix_dna()defmix_dna(self):#生成DNamix_dna=''.join([np.random.choice([self.p1_dna,self.p2_dna])[i]foriinrange(243)])#addmutationforiinrange(243):ifnp.random.rand()>1-self.m_rate:mix_dna=mix_dna[:i]+str(np.random.randint(7))+mix_dna[i+1:]返回mix_dnadefsimulate(self,n_iterations,n_moves,debug=False):#模拟垃圾回收tot_score=0foritinrange(n_iterations):self.score=0#适应度得分self.envir=Environment()self.i,self.j=np.random.randint(1,self.envir.g_size+1,size=2)#随机分配初始位置ifdebug:print('before')print('startposition:',self.i,self.j)self.envir.show_grid()formoveinrange(n_moves):self.act()tot_score+=self.scoreifdebug:print('after')print('endposition:',self.i,self.j)self.envir.show_grid()print('score:',self.score)returntot_score/n_iterations#n次迭代的平均得分defact(self):#根据DNA和机器人位置执行动作post_str=self.envir.get_pos_string(self.i,self.j)#Robot当前位置gene_idx=self.situ_dict[post_str]#当前位置DNA相关索引act_key=self.dna[gene_idx]#从DNA读取动作ifact_key=='5':#随机移动act_key=np.random.choice(['0','1','2','3'])ifact_key=='0':self.mv_up()elifact_key=='1':self.mv_right()elifact_key=='2':self.mv_down()elifact_key=='3':self.mv_left()elifact_key=='6':self.pickup()defmv_up(self):#向上移动ifself.i==1:self.score+=self.wall_penaltyelse:self.i-=1defmv_right(self):#向右移动ifself.j==self.envir.g_size:self.score+=self.wall_penaltyelse:self.j+=1defmv_down(self):#向下移动ifself.i==self.envir.g_size:self.score+=self.wall_penaltyelse:self.i+=1defmv_left(self):#向左移动ifself.j==1:self.score+=self.wall_penaltyelse:self.j-=1defpickup(self):#捡垃圾success=self.envir.remove_rubbish(self.i,self.j)ifsuccess:#成功捡垃圾self.score+=self.rubbish_scoreelse:#当前区块没有捡垃圾self.score+=self.no_rub_penalty终于,运行算法的遗传时间在下面的代码中，我们生成了机器人的初始种群，并让自然选择顺其自然。我应该提一下，当然有更快的方法来实现这个算法（例如利用并行化），但为了本教程的目的，我为了清晰起见牺牲了速度。#初始种群pop=[Robot()forxinrange(pop_size)]results=[]#执行进化foriintqdm(range(num_gen)):scores=np.zeros(pop_size)#遍历所有机器人foridx,robinenumerate(pop):#Run垃圾收集模拟和拟合计算score=rob.simulate(iter_per_sim,moves_per_iter)scores[idx]=scoreresults.append([scores.mean(),scores.max()])#保存每一代的平均值和最大值best_robot=pop[scores.argmax()]#保存最好的机器人#限制可以交配的机器人数量inds=np.argpartition(scores,-num_breeders)[-num_breeders:]#根据契合度获取排名靠前的机器人索引subpop=[]foridxininds:subpop.append(pop[idx])scores=scores[inds]#平方并归一化norm_scores=(scores-scores.min())**2norm_scores=norm_scores/norm_scores.sum()#创建下一代机器人new_pop=[]forchildinrange(pop_size):#选择拟合优的父母p1,p2=np.random.choice(subpop,p=norm_scores,size=2,replace=False)new_pop.append(Robot(p1.dna,p2.dna))pop=new_popWh最初大多数机器人不会捡垃圾，总是会撞到墙上，几代之后，我们开始看到一些简单的策略（比如“如果有垃圾放在一起，就把它捡起来”和“如果它在旁边墙，不要进入它”）。经过数百次迭代，我们只剩下一代不可思议的垃圾收集天才！结果下方的图表显示，我们能够在400代机器人群体中“进化”出一个成功的垃圾收集策略。为了评估进化控制策略的质量，我手动创建了一个基线策略，其中包含一些直观合理的规则：然后墙壁朝相反的方向移动。否则，基准策略在随机移动平均上达到426.9的拟合，但我们最终“进化”的机器人的平均拟合为475.9。这种战略分析优化方法最酷的地方之一是你可以找到反直觉的解决方案。机器人不仅能够学习人类可能制定的明智规则，而且它们还能自发地想出人类可能永远不会考虑的策略。一种使用“标记”来克服近视和记忆缺陷的先进技术已经出现。例如，如果一个机器人当前在一个有垃圾的街区上，并且可以看到东西方块上的垃圾，一个天真的做法是立即捡起当前街区上的垃圾，然后移动到有垃圾的街区。这个策略的问题是，一旦机器人移动（比如向西），他就记不起东边还有1个垃圾。为了克服这个问题，我们观察了我们的进化机器人执行以下步骤：向西移动（将垃圾作为标记留在当前方格上）捡起垃圾向东走（它可以看到垃圾作为标记）捡起垃圾，向东移动并捡起垃圾lastpieceofjunk下面显示了从该优化中出现的反直觉策略的另一个示例。OpenAI使用强化学习（一种更复杂的优化方法）来教智能体玩捉迷藏。我们看到这些代理首先学习“人类”策略，但最终学习新的解决方案。结论遗传算法以独特的方式结合了生物学和计算机科学，虽然不一定是最快的算法，但在我看来，它们是最漂亮的算法之一。
