在Python中用遺傳算法優(yōu)化垃圾收集策略
遺傳算法是一個(gè)優(yōu)化技術(shù)，在本質(zhì)上類似于進(jìn)化過程。這可能是一個(gè)粗略的類比，但如果你瞇著眼睛看，達(dá)爾文的自然選擇確實(shí)大致上類似于一個(gè)優(yōu)化任務(wù)，其目的是制造出完全適合在其環(huán)境中繁衍生息的有機(jī)體。
在本文中，我將展示如何在Python中實(shí)現(xiàn)一個(gè)遺傳算法，在幾個(gè)小時(shí)內(nèi)“進(jìn)化”一個(gè)收集垃圾的機(jī)器人。
背景
我所遇到的遺傳算法原理最好的教程來自Melanie Mitchell寫的一本關(guān)于復(fù)雜系統(tǒng)的好書《Complexity: A Guided Tour》。
在其中一個(gè)章節(jié)中，Mitchell介紹了一個(gè)名叫Robby的機(jī)器人，他在生活中的唯一目的是撿垃圾，并描述了如何使用GA優(yōu)化Robby的控制策略。下面我將解釋我解決這個(gè)問題的方法，并展示如何在Python中實(shí)現(xiàn)該算法。有一些很好的包可以用來構(gòu)造這類算法(比如DEAP)，但是在本教程中，我將只使用基本Python、Numpy和TQDM(可選)。
雖然這只是一個(gè)玩具的例子，但GAs在許多實(shí)際應(yīng)用中都有使用。作為一個(gè)數(shù)據(jù)科學(xué)家，我經(jīng)常用它們來進(jìn)行超參數(shù)優(yōu)化和模型選擇。雖然GAs的計(jì)算成本很高，但GAs允許我們并行地探索搜索空間的多個(gè)區(qū)域，并且在計(jì)算梯度時(shí)是一個(gè)很好的選擇。
問題描述
一個(gè)名為Robby的機(jī)器人生活在一個(gè)充滿垃圾的二維網(wǎng)格世界中，周圍有4堵墻(如下圖所示)。這個(gè)項(xiàng)目的目標(biāo)是發(fā)展一個(gè)最佳的控制策略，使他能夠有效地?fù)炖?，而不是撞墻?/p>
Robby只能看到他周圍上下左右四個(gè)方塊以及他所在的方塊，每個(gè)方塊有3個(gè)選擇，空的，有垃圾，或者是一面墻。因此，Robby有3⁵=243種不同的情況。Robby可以執(zhí)行7種不同的動(dòng)作：上下左右的移動(dòng)(4種)、隨機(jī)移動(dòng)、撿拾垃圾或靜止不動(dòng)。
因此，Robby的控制策略可以編碼為一個(gè)“DNA”字符串，由0到6之間的243位數(shù)字組成(對(duì)應(yīng)于Robby在243種可能的情況下應(yīng)該采取的行動(dòng))。
方法
任何GA的優(yōu)化步驟如下：
- 生成問題初始隨機(jī)解的“種群”
- 個(gè)體的“擬合度”是根據(jù)它解決問題的程度來評(píng)估的
- 最合適的解決方案進(jìn)行“繁殖”并將“遺傳”物質(zhì)傳遞給下一代的后代
- 重復(fù)第2步和第3步，直到我們得到一組優(yōu)化的解決方案
在我們的任務(wù)中，你創(chuàng)建了第一代Robbys初始化為隨機(jī)DNA字符串(對(duì)應(yīng)于隨機(jī)控制策略)。然后模擬讓這些機(jī)器人在隨機(jī)分配的網(wǎng)格世界中運(yùn)行，并觀察它們的性能。
擬合度
機(jī)器人的擬合度取決于它在n次移動(dòng)中撿到多少垃圾，以及它撞到墻上多少次。在我們的例子中，機(jī)器人每撿到一塊垃圾就給它10分，每次它撞到墻上就減去5分。然后，這些機(jī)器人以它們的擬合度相關(guān)的概率進(jìn)行“交配”(即，撿起大量垃圾的機(jī)器人更有可能繁衍后代)，新一代機(jī)器人誕生了。
交配
有幾種不同的方法可以實(shí)現(xiàn)“交配”。在Mitchell的版本中，她將父母的兩條DNA鏈隨機(jī)拼接，然后將它們連接在一起，為下一代創(chuàng)造一個(gè)孩子。在我的實(shí)現(xiàn)中，我從每一個(gè)親本中隨機(jī)分配每個(gè)基因(即，對(duì)于243個(gè)基因中的每一個(gè)，我擲硬幣決定遺傳誰的基因)。
例如使用我的方法，在前10個(gè)基因里，父母和孩子可能的基因如下：
- Parent 1: 1440623161
- Parent 2: 2430661132
- Child: 2440621161
突變
我們用這個(gè)算法復(fù)制的另一個(gè)自然選擇的概念是“變異”。雖然一個(gè)孩子的絕大多數(shù)基因都是從父母那里遺傳下來的，但我也建立了基因突變的小可能性(即隨機(jī)分配)。這種突變率使我們能夠探索新的可能。
Python實(shí)現(xiàn)
第一步是導(dǎo)入所需的包并為此任務(wù)設(shè)置參數(shù)。我已經(jīng)選擇了這些參數(shù)作為起點(diǎn)，但是它們可以調(diào)整，我鼓勵(lì)你可以嘗試調(diào)整。
- """
- 導(dǎo)入包
- """
- import numpy as np
- from tqdm.notebook import tqdm
- """
- 設(shè)置參數(shù)
- """
- # 仿真設(shè)置
- pop_size = 200 # 每一代機(jī)器人的數(shù)量
- num_breeders = 100 # 每一代能夠交配的機(jī)器人數(shù)量
- num_gen = 400 # 總代數(shù)
- iter_per_sim = 100 # 每個(gè)機(jī)器人垃圾收集模擬次數(shù)
- moves_per_iter = 200 # 機(jī)器人每次模擬可以做的移動(dòng)數(shù)
- # 網(wǎng)格設(shè)置
- rubbish_prob = 0.5 # 每個(gè)格子中垃圾的概率
- grid_size = 10 # 0網(wǎng)格大小(墻除外)
- # 進(jìn)化設(shè)置
- wall_penalty = -5 # 因撞到墻上而被扣除的擬合點(diǎn)
- no_rub_penalty = -1 # 在空方塊撿垃圾被扣分
- rubbish_score = 10 # 撿垃圾可獲得積分
- mutation_rate = 0.01 # 變異的概率
接下來，我們?yōu)榫W(wǎng)格世界環(huán)境定義一個(gè)類。我們用標(biāo)記“o”、“x”和“w”來表示每個(gè)單元，分別對(duì)應(yīng)一個(gè)空單元、一個(gè)帶有垃圾的單元和一個(gè)墻。
- class Environment:
- """
- 類，用于表示充滿垃圾的網(wǎng)格環(huán)境。每個(gè)單元格可以表示為:
- 'o': 空
- 'x': 垃圾
- 'w': 墻
- """
- def __init__(self, p=rubbish_prob, g_size=grid_size):
- self.p = p # 單元格是垃圾的概率
- self.g_size = g_size # 不包括墻
- # 初始化網(wǎng)格并隨機(jī)分配垃圾
- self.grid = np.random.choice(['o','x'], size=(self.g_size+2,self.g_size+2), p=(1 - self.p, self.p))
- # 設(shè)置外部正方形為墻壁
- self.grid[:,[0,self.g_size+1]] = 'w'
- self.grid[[0,self.g_size+1], :] = 'w'
- def show_grid(self):
- # 以當(dāng)前狀態(tài)打印網(wǎng)格
- print(self.grid)
- def remove_rubbish(self,i,j):
- # 從指定的單元格(i,j)清除垃圾
- if self.grid[i,j] == 'o': # 單元格已經(jīng)是空
- return False
- else:
- self.grid[i,j] = 'o'
- return True
- def get_pos_string(self,i,j):
- # 返回一個(gè)字符串，表示單元格(i,j)中機(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]
接下來，我們創(chuàng)建一個(gè)類來表示我們的機(jī)器人。這個(gè)類包括執(zhí)行動(dòng)作、計(jì)算擬合度和從一對(duì)父機(jī)器人生成新DNA的方法。
- class Robot:
- """
- 用于表示垃圾收集機(jī)器人
- """
- 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 # 突變率
- self.wall_penalty = w_pen # 因撞到墻上而受罰
- self.no_rub_penalty = nr_pen # 在空方塊撿垃圾的處罰
- self.rubbish_score = r_score # 撿垃圾的獎(jiǎng)勵(lì)
- self.p1_dna = p1_dna # 父母2的DNA
- self.p2_dna = p2_dna # 父母2的DNA
- # 生成字典來從場景字符串中查找基因索引
- con = ['w','o','x'] # 墻，空，垃圾
- self.situ_dict = dict()
- count = 0
- for 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] = count
- count += 1
- # 初始化DNA
- self.get_dna()
- def get_dna(self):
- # 初始化機(jī)器人的dna字符串
- if self.p1_dna is None:
- # 沒有父母的時(shí)候隨機(jī)生成DNA
- self.dna = ''.join([str(x) for x in np.random.randint(7,size=243)])
- else:
- self.dna = self.mix_dna()
- def mix_dna(self):
- # 從父母的DNA生成機(jī)器人的DNA
- mix_dna = ''.join([np.random.choice([self.p1_dna,self.p2_dna])[i] for i in range(243)])
- #添加變異
- for 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_dna
- def simulate(self, n_iterations, n_moves, debug=False):
- # 仿真垃圾收集
- tot_score = 0
- for it in range(n_iterations):
- self.score = 0 # 擬合度分?jǐn)?shù)
- self.envir = Environment()
- self.i, self.j = np.random.randint(1,self.envir.g_size+1, size=2) # 隨機(jī)分配初始位置
- if 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.score
- if debug:
- print('after')
- print('end position:',self.i, self.j)
- self.envir.show_grid()
- print('score:',self.score)
- return tot_score / n_iterations # n次迭代的平均得分
- def act(self):
- # 根據(jù)DNA和機(jī)器人位置執(zhí)行動(dòng)作
- post_str = self.envir.get_pos_string(self.i, self.j) # 機(jī)器人當(dāng)前位置
- gene_idx = self.situ_dict[post_str] # 當(dāng)前位置DNA的相關(guān)索引
- act_key = self.dna[gene_idx] # 從DNA中讀取行動(dòng)
- if act_key == '5':
- # 隨機(jī)移動(dòng)
- act_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):
- # 向上移動(dòng)
- if self.i == 1:
- self.score += self.wall_penalty
- else:
- self.i -= 1
- def mv_right(self):
- # 向右移動(dòng)
- if self.j == self.envir.g_size:
- self.score += self.wall_penalty
- else:
- self.j += 1
- def mv_down(self):
- # 向下移動(dòng)
- if self.i == self.envir.g_size:
- self.score += self.wall_penalty
- else:
- self.i += 1
- def mv_left(self):
- # 向左移動(dòng)
- if self.j == 1:
- self.score += self.wall_penalty
- else:
- self.j -= 1
- def pickup(self):
- # 撿垃圾
- success = self.envir.remove_rubbish(self.i, self.j)
- if success:
- # 成功撿到垃圾
- self.score += self.rubbish_score
- else:
- # 當(dāng)前方塊沒有撿到垃圾
- self.score += self.no_rub_penalty
最后是運(yùn)行遺傳算法的時(shí)候了。在下面的代碼中，我們生成一個(gè)初始的機(jī)器人種群，讓自然選擇來運(yùn)行它的過程。我應(yīng)該提到的是，當(dāng)然有更快的方法來實(shí)現(xiàn)這個(gè)算法(例如利用并行化)，但是為了本教程的目的，我犧牲了速度來實(shí)現(xiàn)清晰。
- # 初始種群
- pop = [Robot() for x in range(pop_size)]
- results = []
- # 執(zhí)行進(jìn)化
- for i in tqdm(range(num_gen)):
- scores = np.zeros(pop_size)
- # 遍歷所有機(jī)器人
- for idx, rob in enumerate(pop):
- # 運(yùn)行垃圾收集模擬并計(jì)算擬合度
- score = rob.simulate(iter_per_sim, moves_per_iter)
- scores[idx] = score
- results.append([scores.mean(),scores.max()]) # 保存每一代的平均值和最大值
- best_robot = pop[scores.argmax()] # 保存最好的機(jī)器人
- # 限制那些能夠交配的機(jī)器人的數(shù)量
- inds = np.argpartition(scores, -num_breeders)[-num_breeders:] # 基于擬合度得到頂級(jí)機(jī)器人的索引
- subpop = []
- for idx in inds:
- subpop.append(pop[idx])
- scores = scores[inds]
- # 平方并標(biāo)準(zhǔn)化
- norm_scores = (scores - scores.min()) ** 2
- norm_scores = norm_scores / norm_scores.sum()
- # 創(chuàng)造下一代機(jī)器人
- new_pop = []
- for child in range(pop_size):
- # 選擇擬合度優(yōu)秀的父母
- p1, p2 = np.random.choice(subpop, p=norm_scores, size=2, replace=False)
- new_pop.append(Robot(p1.dna, p2.dna))
- pop = new_pop
雖然最初大多數(shù)機(jī)器人不撿垃圾，總是撞到墻上，但幾代人之后，我們開始看到一些簡單的策略(例如“如果與垃圾在一起，就撿起來”和“如果挨著墻，就不要移到墻里”)。經(jīng)過幾百次的反復(fù)，我們只剩下一代不可思議的垃圾收集天才!
結(jié)果
下面的圖表表明，我們能夠在400代機(jī)器人種群中“進(jìn)化”出一種成功的垃圾收集策略。
為了評(píng)估進(jìn)化控制策略的質(zhì)量，我手動(dòng)創(chuàng)建了一個(gè)基準(zhǔn)策略，其中包含一些直觀合理的規(guī)則：
- 如果垃圾在當(dāng)前方塊，撿起來
- 如果在相鄰的方塊上可以看到垃圾，移到那個(gè)方塊
- 如果靠近墻，則向相反方向移動(dòng)
- 否則，隨意移動(dòng)
平均而言，這一基準(zhǔn)策略達(dá)到了426.9的擬合度，但我們最終的“進(jìn)化”機(jī)器人的平均擬合度為475.9。
戰(zhàn)略分析
這種優(yōu)化方法最酷的一點(diǎn)是，你可以找到反直覺的解決方案。機(jī)器人不僅能夠?qū)W習(xí)人類可能設(shè)計(jì)的合理規(guī)則，而且還自發(fā)地想出了人類可能永遠(yuǎn)不會(huì)考慮的策略。一種先進(jìn)的技術(shù)出現(xiàn)了，就是使用“標(biāo)記物”來克服近視和記憶不足。
例如，如果一個(gè)機(jī)器人現(xiàn)在在一個(gè)有垃圾的方塊上，并且可以看到東西方方塊上的垃圾，那么一個(gè)天真的方法就是立即撿起當(dāng)前方塊上的垃圾，然后移動(dòng)到那個(gè)有垃圾的方塊。這種策略的問題是，一旦機(jī)器人移動(dòng)(比如向西)，他就無法記住東邊還有1個(gè)垃圾。為了克服這個(gè)問題，我們觀察了我們的進(jìn)化機(jī)器人執(zhí)行以下步驟：
- 向西移動(dòng)(在當(dāng)前方塊留下垃圾作為標(biāo)記)
- 撿起垃圾往東走(它可以看到垃圾作為標(biāo)記)
- 把垃圾撿起來，搬到東邊去
- 撿起最后一塊垃圾
從這種優(yōu)化中產(chǎn)生的另一個(gè)反直覺策略的例子如下所示。OpenAI使用強(qiáng)化學(xué)習(xí)(一種更復(fù)雜的優(yōu)化方法)教代理玩捉迷藏。我們看到，這些代理一開始學(xué)習(xí)“人類”策略，但最終學(xué)會(huì)了新的解決方案。
結(jié)論
遺傳算法以一種獨(dú)特的方式將生物學(xué)和計(jì)算機(jī)科學(xué)結(jié)合在一起，雖然不一定是最快的算法，但在我看來，它們是最美麗的算法之一。
