Genetic Algorithms are a family of optimisation techniques that loosely resemble evolutionary processes in nature. It may be a crude analogy, but if you squint your eyes, Darwin’s Natural Selection does roughly resemble an optimisation task where the aim is to craft organisms perfectly suited to thrive in their environments. While it may have taken many millennia for humans to develop opposable thumbs and eagles to develop 20/4 vision, in this article I will show how to implement a Genetic Algorithm in Python for “evolving” a rubbish collecting robot in a couple of hours.

遺傳算法是一系列優化技術，與自然界的進化過程大致相似。 這可能是一個粗略的類比，但是如果您起眼睛，達爾文的《自然選擇》確實類似于優化任務，其目的是制造出非常適合在其環境中繁衍生息的生物。 雖然人類可能需要花費數千年的時間才能開發出相對的拇指和鷹來開發20/4視覺，但在本文中，我將展示如何在Python中實現遺傳算法，以在幾小時內“進化”垃圾收集機器人。

背景 (Background)

The best example I’ve come across to demonstrate how Genetic Algorithms work comes from a fantastic book on complex systems by Melanie Mitchell called “Complexity: A Guided Tour” (highly recommended). In one chapter, Mitchell introduces a robot named Robby whose sole purpose in life is to pick up rubbish and describes how to optimise a control strategy for Robby using a GA. Below I will explain my approach to solving this problem and show how to implement the algorithm in Python. There are some great packages for constructing these kinds of algorithms (such as DEAP) but in this tutorial, I will only be using base Python, Numpy and TQDM (optional).

我碰到的最好的例子演示了遺傳算法的工作原理，這是梅拉妮·米切爾(Melanie Mitchell)撰寫的一本關于復雜系統的出色著作，名為“復雜性：導覽”(強烈推薦)。 在一個章節中，米切爾介紹了一個名為Robby的機器人，該機器人的唯一目的是撿拾垃圾，并描述了如何使用GA優化Robby的控制策略。 下面，我將解釋解決此問題的方法，并展示如何在Python中實現該算法。 有一些很棒的軟件包可用于構建這類算法(例如DEAP )，但是在本教程中，我將僅使用基本的Python，Numpy和TQDM(可選)。

While this is only a toy example, GAs are used in a number of real-world applications. As a data scientist, I most often use them for hyper-parameter optimisation and model choice. While they can be computationally expensive, GAs allow us to explore multiple areas of a search space in parallel and are a good option when computing a gradient is difficult.

盡管這只是一個玩具示例，但GA已在許多實際應用中使用。 作為數據科學家，我經常將它們用于超參數優化和模型選擇。 盡管它們的計算成本可能很高，但GA允許我們并行探索搜索空間的多個區域，當難以計算梯度時，它們是一個不錯的選擇。

問題描述 (Problem Description)

A robot named Robby lives in a two-dimensional grid world full of rubbish and surrounded by 4 walls (shown below). The aim of this project is to evolve an optimal control strategy for Robby that will allow him to pick up rubbish efficiently and not crash into walls.

名為Robby的機器人生活在一個充滿垃圾的二維網格世界中，周圍環繞著4面墻(如下所示)。 該項目的目的是為Robby制定最佳的控制策略，使他能夠有效地撿拾垃圾而不撞墻。

Robby can only see the four squares NESW of himself as well as the square he is in and there are 3 options for each square; it can be empty, have rubbish in it or be a wall. Therefore there are 3? = 243 different scenarios Robby can be in. Robby can perform 7 different actions; move NESW, move randomly, pickup rubbish or stay still. Robby’s control strategy can therefore be encoded as a “DNA” string of 243 digits between 0 and 6 (corresponding to the action Robby should take in each of the 243 possible situations).

羅比只能看到他自己的四個NESW以及他所在的正方形，每個正方形有3個選項； 它可以是空的，里面有垃圾或可以是墻壁。 因此，Robby可能有3種= 243種不同的場景。Robby可以執行7種不同的動作； 移動NESW，隨機移動，撿垃圾或保持靜止。 因此，Robby的控制策略可以被編碼為0到6之間的243位數的“ DNA”字符串(對應于Robby在243種可能的情況下應采取的措施)。

方法 (Approach)

At a high level, the steps for optimisation with any GA are:

從總體上講，使用任何GA進行優化的步驟如下：

1. An initial “population” of random solutions to a problem are generated
   生成問題的隨機解決方案的初始“填充”
2. The “fitness” of each individual is assessed based on how well it solves the problem
   根據每個人解決問題的能力來評估每個人的“適應性”
3. The fittest solutions “reproduce” and pass on “genetic” material to offspring in the next generation
   最合適的解決方案“繁殖”并“遺傳”材料傳給下一代
4. Repeat steps 2 and 3 until we are left with a population of optimised solutions
   重復步驟2和3，直到剩下優化解決方案為止

For our task, you create a first generation of Robbys initialised to random DNA strings (corresponding to random control strategies). You then simulate letting these robots run around in randomly assigned grid worlds and see how they perform.

對于我們的任務，您將創建初始化為隨機DNA字符串(對應于隨機控制策略)的第一代Robby。 然后，您可以模擬這些機器人在隨機分配的網格世界中運行，并觀察它們的性能。

適合度 (Fitness)

A robot’s fitness is a function of how many pieces of rubbish it picked up in n moves and how many times it crashed into a wall. In our example, we award 10 points to a robot for every piece of rubbish picked up and subtract 5 points every time it crashes into a wall. The robots then “mate” with probabilities linked to their fitness score (i.e. robots that picked up lots of rubbish are more likely to reproduce) and a new generation is created.

機器人的適應性取決于它在n步中撿起多少垃圾以及撞到墻壁的次數。 在我們的示例中，對于每撿起的垃圾，我們會為機器人獎勵10分，每次撞到墻壁時，機器人都會減去5分。 然后，機器人將與其適應度得分相關聯的概率“配對”(即，撿拾大量垃圾的機器人更有可能繁殖)，并創造了新一代。

交配 (Mating)

There are a few different ways that “mating” can be implemented. In Mitchell’s version she took the 2 parent DNA strings, randomly spliced them and then joined them together to create a child for the next generation. In my implementation, I assigned each gene probabilistically from each parent (i.e. for each of the 243 genes, I flip a coin to decide which parent will pass on their gene). For example, here are the first 10 genes of 2 parents and a possible child using my method:

有幾種不同的方法可以實現“匹配”。 在米切爾(Mitchell)的版本中，她采用了2個父DNA字符串，隨機拼接它們，然后將它們結合在一起，為下一代創造了一個孩子。 在我的實現中，我按概率從每個親本中分配了每個基因(即，對于243個基因中的每個基因，我擲硬幣決定哪一個親本將通過其基因)。 例如，以下是使用我的方法的2個父母和一個可能的孩子的前10個基因：

Parent 1: 1440623161
Parent 2: 2430661132
Child:    2440621161

突變 (Mutation)

Another concept from natural selection that we replicate with this algorithm is that of “mutation”. While the vast majority of genes in a child will be passed down from a parent, I have also built in a small possibility that the gene will mutate (i.e. will be assigned at random). This mutation rate gives us the ability to control the trade-off between exploration and exploitation.

我們使用該算法復制的自然選擇的另一個概念是“變異”。 雖然孩子中的絕大多數基因會從父母那里遺傳下來，但我也認為基因突變的可能性很小(即隨機分配)。 這種突變率使我們能夠控制勘探與開發之間的權衡。

Python實現 (Python Implementation)

The first step is to import the required packages and set our parameters for this task. I have chosen these parameters as a starting point, but they can be adjusted and I encourage you to experiment with them.

第一步是導入所需的程序包并為此任務設置參數。 我選擇了這些參數作為起點，但是可以對其進行調整，建議您嘗試一下。

"""
Import Packages
"""
import numpy as np
from tqdm.notebook import tqdm"""
Set Parameters
"""
# Simulation Settings
pop_size = 200 # number of robots per generation
num_breeders = 100 # number of robots who can mate in each generation
num_gen = 400 # total number of generations
iter_per_sim = 100 # number of rubbish-collection simulations per robot
moves_per_iter = 200 # number of moves robot can make per simulation# Grid Settings
rubbish_prob = 0.5 # probability of rubbish in each grid square
grid_size = 10 # size of grid (excluding walls)# Evolution Settings
wall_penalty = -5 # fitness points deducted for crashing into wall
no_rub_penalty = -1 # fitness points deducted for trying to pickup rubbish in empty square
rubbish_score = 10 # fitness points awarded for picking up rubbish
mutation_rate = 0.01 # probability of a gene mutating

Next, we define a class for the grid-world environment. We represent each cell by the tokens ‘o’, ‘x’ and ‘w’ corresponding to an empty cell, a cell with rubbish and a wall respectively.

接下來，我們為網格世界環境定義一個類。 我們用標記“ o”，“ x”和“ w”表示每個單元，分別對應一個空單元，一個帶有垃圾的單元和一個壁。

class Environment:"""Class for representing a grid environment full of rubbish. Each cell can be:'o': empty'x': rubbish'w': wall"""def __init__(self, p=rubbish_prob, g_size=grid_size):self.p = p # probability of a cell being rubbishself.g_size = g_size # excluding walls# initialise grid and randomly allocate rubbishself.grid = np.random.choice(['o','x'], size=(self.g_size+2,self.g_size+2), p=(1 - self.p, self.p))# set exterior squares to be wallsself.grid[:,[0,self.g_size+1]] = 'w'self.grid[[0,self.g_size+1], :] = 'w'def show_grid(self):# print the grid in current stateprint(self.grid)def remove_rubbish(self,i,j):# remove rubbish from specified cell (i,j)if self.grid[i,j] == 'o': # cell already emptyreturn Falseelse:self.grid[i,j] = 'o'return Truedef get_pos_string(self,i,j):# return a string representing the cells "visible" to a robot in cell (i,j)return self.grid[i-1,j] + self.grid[i,j+1] + self.grid[i+1,j] + self.grid[i,j-1] + self.grid[i,j]

Next, we create a class to represent our robots. This class includes methods for performing actions, calculating fitness and generating new DNA from a pair of parent robots.

接下來，我們創建一個代表機器人的類。 該課程包括執行動作，計算適應性以及從一對父機器人生成新DNA的方法。

class Robot:"""Class for representing a rubbish-collecting robot"""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 rateself.wall_penalty = w_pen # penalty for crashing into a wallself.no_rub_penalty = nr_pen # penalty for picking up rubbish in empty cellself.rubbish_score = r_score # reward for picking up rubbishself.p1_dna = p1_dna # parent 1 DNAself.p2_dna = p2_dna # parent 2 DNA# generate dict to lookup gene index from situation stringcon = ['w','o','x'] # wall, empty, rubbishself.situ_dict = dict()count = 0for up in con:for right in con:for down in con:for left in con:for pos in con:self.situ_dict[up+right+down+left+pos] = countcount += 1# initialise dnaself.get_dna()def get_dna(self):# initialise dna string for robotif self.p1_dna is None:# when no parents (first gen) initialise to random stringself.dna = ''.join([str(x) for x in np.random.randint(7,size=243)])else:self.dna = self.mix_dna()def mix_dna(self):# generate robot dna from parentsmix_dna = ''.join([np.random.choice([self.p1_dna,self.p2_dna])[i] for i in range(243)])#add mutationsfor i in range(243):if np.random.rand() > 1 - self.m_rate:mix_dna = mix_dna[:i] + str(np.random.randint(7)) + mix_dna[i+1:]return mix_dnadef simulate(self, n_iterations, n_moves, debug=False):# simulate rubbish collectiontot_score = 0for it in range(n_iterations):self.score = 0 # fitness scoreself.envir = Environment()self.i, self.j = np.random.randint(1,self.envir.g_size+1, size=2) # randomly allocate starting positionif debug:print('before')print('start position:',self.i, self.j)self.envir.show_grid()for move in range(n_moves):self.act()tot_score += self.scoreif debug:print('after')print('end position:',self.i, self.j)self.envir.show_grid()print('score:',self.score)return tot_score / n_iterations # average fitness score across n iterationsdef act(self):# perform action based on DNA and robot situationpost_str = self.envir.get_pos_string(self.i, self.j) # robot's current situationgene_idx = self.situ_dict[post_str] # relevant idx of DNA for current situationact_key = self.dna[gene_idx] # read action from idx of DNAif act_key == '5':# move randomlyact_key = np.random.choice(['0','1','2','3'])if act_key == '0':self.mv_up()elif act_key == '1':self.mv_right()elif act_key == '2':self.mv_down()elif act_key == '3':self.mv_left()elif act_key == '6':self.pickup()def mv_up(self):# move up one squareif self.i == 1:self.score += self.wall_penaltyelse:self.i -= 1def mv_right(self):# move right one squareif self.j == self.envir.g_size:self.score += self.wall_penaltyelse:self.j += 1def mv_down(self):# move down one squareif self.i == self.envir.g_size:self.score += self.wall_penaltyelse:self.i += 1def mv_left(self):# move left one squareif self.j == 1:self.score += self.wall_penaltyelse:self.j -= 1def pickup(self):# pickup rubbishsuccess = self.envir.remove_rubbish(self.i, self.j)if success:# rubbish successfully picked upself.score += self.rubbish_scoreelse:# no rubbish in current squareself.score += self.no_rub_penalty

Finally it’s time to run the Genetic Algorithm. In the code below we generate an initial population of robots and let Natural Selection run its course. I should mention that there are certainly much faster ways to implement this algorithm (e.g. utilising parallelisation) but for the purpose of this tutorial I have sacrificed speed for clarity.

最后是時候運行遺傳算法了。 在下面的代碼中，我們生成了機器人的初始填充，然后讓Natural Selection運行其過程。 我應該提到，當然有更快的方法來實現該算法(例如，利用并行化)，但是出于本教程的目的，我為了清晰起見而犧牲了速度。

# initial population
pop = [Robot() for x in range(pop_size)]
results = []# run evolution
for i in tqdm(range(num_gen)):scores = np.zeros(pop_size)# iterate through all robotsfor idx, rob in enumerate(pop):# run rubbish collection simulation and calculate fitnessscore = rob.simulate(iter_per_sim, moves_per_iter)scores[idx] = scoreresults.append([scores.mean(),scores.max()]) # save mean and max scores for each generationbest_robot = pop[scores.argmax()] # save the best robot# limit robots who are able to mate to top num_breedersinds = np.argpartition(scores, -num_breeders)[-num_breeders:] # get indices of top robots based on fitnesssubpop = []for idx in inds:subpop.append(pop[idx])scores = scores[inds]# square and normalise fitness scoresnorm_scores = (scores - scores.min()) ** 2 norm_scores = norm_scores / norm_scores.sum()# create next generation of robotsnew_pop = []for child in range(pop_size):# choose parents with probability proportionate to squared fitness scoresp1, p2 = np.random.choice(subpop, p=norm_scores, size=2, replace=False)new_pop.append(Robot(p1.dna, p2.dna))pop = new_pop

While initially most of the robots pick up no rubbish and consistently crash into walls, within a few generations we start to see simple strategies (such as “if in square with rubbish, pick it up” and “if next to wall, don’t move into wall”) propagate through the population. After a few hundred iterations, we are left with a generation of incredible rubbish-collecting geniuses!

最初，大多數機器人沒有撿拾垃圾，并且始終撞到墻壁上，但在幾代人之后，我們開始看到簡單的策略(例如“如果與垃圾成一直線，撿拾垃圾”和“如果靠近墻壁，不要撿垃圾”)。進入墻壁”)在人群中傳播。 經過幾百次迭代，我們剩下了一代令人難以置信的垃圾收集天才！

結果 (Results)

The plot below shows that we were able to “evolve” a successful rubbish collection strategy in 400 generations.

下圖顯示了我們能夠在400代內“演變”成功的垃圾收集策略。

To assess the quality of the evolved control strategy, I manually created a benchmark strategy with some intuitively sensible rules:

為了評估改進的控制策略的質量，我手動創建了一些具有直觀意義的規則的基準策略：

1. If rubbish is in current square, pick it up
   如果垃圾在當前方塊中，請撿起
2. If rubbish is visible in an adjacent square, move to that square
   如果在相鄰的正方形中可見垃圾，請移至該正方形
3. If next to a wall, move in the opposite direction
   如果靠近墻壁，請朝相反方向移動
4. Else, move in a random direction
   否則，朝隨機方向移動

On average, this benchmark strategy achieved a fitness score of 426.9 but this was no match for our final “evolved” robot which had an average fitness score of 475.9.

平均而言，該基準策略的適應度得分為426.9，但這與我們最終的“進化”機器人的平均適應度得分為475.9并不匹配。

策略分析 (Strategy Analysis)

One of the coolest things about this approach to optimisation is that you can find counter-intuitive solutions. Not only were the robots able to learn sensible rules that a human might design, they also spontaneously came up with strategies that humans might never consider. One sophisticated technique that emerged was the use of “markers” to overcome short-sightedness and a lack of memory. For example, if a robot is currently in a square with rubbish in it and can see rubbish in the squares to the east and west, a naive approach would be to immediately pickup the rubbish in the current square and then move to one of the adjacent squares. The problem with this strategy is that once the robot has moved (say to the west), he has no way of remembering that there is rubbish 2 squares to the east. To overcome this problem, we observed our evolved robots performing the following steps:

關于這種優化方法的最酷的事情之一是，您可以找到違反直覺的解決方案。 機器人不僅能夠學習人類可能設計的明智規則，而且還自發提出了人類可能永遠不會考慮的策略。 一種新興的先進技術是使用“標記”來克服近視和缺乏記憶。 例如，如果一個機器人當前在一個有垃圾的正方形中并且可以看到東西方的正方形中的垃圾，那么幼稚的方法是立即在當前正方形中拾取垃圾，然后移到相鄰的一個正方形中。方塊。 這種策略的問題在于，一旦機器人移動(例如向西移動)，他就無法記住東邊有2個正方形的垃圾。 為了克服這個問題，我們觀察了我們進化的機器人執行以下步驟：

1. move to the west (leave the rubbish in the current square as a marker)
   向西移動(將垃圾放在當前廣場中作為標記)
2. pick up the rubbish and move back to the east (it can see the rubbish left as a marker)
   撿起垃圾并向東移動(可以看到垃圾作為標記)
3. pick up the rubbish and move to the east
   撿起垃圾，然后移到東方
4. pick up the final piece of rubbish
   撿起最后一塊垃圾

Another example of counter-intuitive strategies emerging from this kind of optimisation is shown below. OpenAI taught agents to play hide and seek using reinforcement learning (a more sophisticated optimisation approach). We see that the agents learn “human” strategies at first but eventually learn novel solutions such as “Box Surfing” that exploit the physics of OpenAI’s simulated environment.

這種優化產生的反直覺策略的另一個示例如下所示。 OpenAI教給代理商使用強化學習(一種更復雜的優化方法)玩捉迷藏的游戲。 我們看到代理首先學習“人性化”策略，但最終學習了新穎的解決方案，例如“盒式沖浪”，它們利用了OpenAI模擬環境的物理特性。

結論 (Conclusion)

Genetic Algorithms combine biology and computer science in a unique way and while not necessarily the fastest algorithms, in my opinion they are among the most beautiful. All of the code featured in this article is available on my Github along with a demo notebook. Thanks for reading!

遺傳算法以獨特的方式結合了生物學和計算機科學，雖然不一定是最快的算法，但我認為它們是最漂亮的算法之一。 我的Github和演示筆記本都提供了本文中介紹的所有代碼。 謝謝閱讀！