用遺傳算法優化垃圾收集策略

遺傳算法是一個優化技術，在本質上類似於進化過程。這可能是一個粗略的類比，但如果你眯著眼睛看，達爾文的自然選擇確實大致上類似於一個優化任務，其目的是製造出完全適合在其環境中繁衍生息的有機體。

在本文中，我將展示如何在Python中實現一個遺傳算法，在幾個小時內“進化”一個收集垃圾的機器人。

背景

我所遇到的遺傳算法原理最好的教程來自Melanie Mitchell寫的一本關於複雜系統的好書《Complexity: A Guided Tour》。

在其中一個章節中，Mitchell介紹了一個名叫Robby的機器人，他在生活中的唯一目的是撿垃圾，並描述瞭如何使用GA優化Robby的控制策略。下面我將解釋我解決這個問題的方法，並展示如何在Python中實現該算法。有一些很好的包可以用來構造這類算法（比如DEAP），但是在本教程中，我將只使用基本Python、Numpy和TQDM（可選）。

雖然這只是一個玩具的例子，但GAs在許多實際應用中都有使用。作為一個數據科學家，我經常用它們來進行超參數優化和模型選擇。雖然GAs的計算成本很高，但GAs允許我們並行地探索搜索空間的多個區域，並且在計算梯度時是一個很好的選擇。

問題描述

一個名為Robby的機器人生活在一個充滿垃圾的二維網格世界中，周圍有4堵牆（如下圖所示）。這個項目的目標是發展一個最佳的控制策略，使他能夠有效地撿垃圾，而不是撞牆。

Robby只能看到他周圍上下左右四個方塊以及他所在的方塊，每個方塊有3個選擇，空的，有垃圾，或者是一面牆。因此，Robby有3⁵=243種不同的情況。Robby可以執行7種不同的動作：上下左右的移動（4種）、隨機移動、撿拾垃圾或靜止不動。

因此，Robby的控制策略可以編碼為一個“DNA”字符串，由0到6之間的243位數字組成（對應於Robby在243種可能的情況下應該採取的行動）。

方法

任何GA的優化步驟如下：

1. 生成問題初始隨機解的“種群”
2. 個體的“擬合度”是根據它解決問題的程度來評估的
3. 最合適的解決方案進行“繁殖”並將“遺傳”物質傳遞給下一代的後代
4. 重複第2步和第3步，直到我們得到一組優化的解決方案

在我們的任務中，你創建了第一代Robbys初始化為隨機DNA字符串（對應於隨機控制策略）。然後模擬讓這些機器人在隨機分配的網格世界中運行，並觀察它們的性能。

擬合度

機器人的擬合度取決於它在n次移動中撿到多少垃圾，以及它撞到牆上多少次。在我們的例子中，機器人每撿到一塊垃圾就給它10分，每次它撞到牆上就減去5分。然後，這些機器人以它們的擬合度相關的概率進行“交配”（即，撿起大量垃圾的機器人更有可能繁衍後代），新一代機器人誕生了。

交配

有幾種不同的方法可以實現“交配”。在Mitchell的版本中，她將父母的兩條DNA鏈隨機拼接，然後將它們連接在一起，為下一代創造一個孩子。在我的實現中，我從每一個親本中隨機分配每個基因（即，對於243個基因中的每一個，我擲硬幣決定遺傳誰的基因）。

例如使用我的方法，在前10個基因裡，父母和孩子可能的基因如下：

<code>
Parent 1:
 
1440623161
Parent 2:
 
2430661132
Child:
    
2440621161 

/<code>

突變

我們用這個算法複製的另一個自然選擇的概念是“變異”。雖然一個孩子的絕大多數基因都是從父母那裡遺傳下來的，但我也建立了基因突變的小可能性（即隨機分配）。這種突變率使我們能夠探索新的可能。

Python實現

第一步是導入所需的包併為此任務設置參數。我已經選擇了這些參數作為起點，但是它們可以調整，我鼓勵你可以嘗試調整。

<code>
"""
導入包
"""
import
 numpy 
as
 np
from
 tqdm.notebook 
import
 tqdm

"""
設置參數
"""
 
pop_size = 
200
  
num_breeders = 
100
  
num_gen = 
400
  
iter_per_sim = 
100
  
moves_per_iter = 
200
  

 
rubbish_prob = 
0.5
  
grid_size =  
10
  

 
wall_penalty = 
-5
  
no_rub_penalty = 
-1
  
rubbish_score = 
10
  
mutation_rate = 
0.01
  
/<code>

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

<code>
class
 
Environment
:

    
""
"
    類，用於表示充滿垃圾的網格環境。每個單元格可以表示為:
    'o': 空
    'x': 垃圾
    'w': 牆
    "
""
    
def
 
__init__
(
self
, p=rubbish_prob, g_size=grid_size)
:
        
self
.p = p  
        
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'

    
def
 
show_grid
(
self 
)
:
         
        print(
self
.grid)

    
def
 
remove_rubbish
(
self
,i,j)
:
         
        
if
 
self
.grid[i,j] == 
'o'
:  
            
return
 False
        
else:
            
self
.grid[i,j] = 
'o'
            
return
 True

    
def
 
get_pos_string
(
self
,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]
/<code>

接下來，我們創建一個類來表示我們的機器人。這個類包括執行動作、計算擬合度和從一對父機器人生成新DNA的方法。

<code>
class
 
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  
        
self
.wall_penalty = w_pen  
        
self
.no_rub_penalty = nr_pen  
        
self 
.rubbish_score = r_score  
        
self
.p1_dna = p1_dna  
        
self
.p2_dna = p2_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

         
        
self 
.get_dna()

    
def
 
get_dna
(
self
)
:
         
        
if
 
self
.p1_dna is 
None:
             
            
self
.dna = 
''
.join([str(x) 
for
 x 
in
 np.random.randint(
7
,size=
243
)])
        
else:
            
self
.dna = 
self
.mix_dna()

    
def
 
mix_dna
(
self
)
:
         
        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 
  
            
self
.envir = Environment()
            
self
.i, 
self
.j = np.random.randint(
1
,
self
.envir.g_size+
1
, size=
2
)  
            
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  

    
def
 
act
(
self
)
:
         
        post_str = 
self
.envir.get_pos_string(
self
.i, 
self
.j)  
        gene_idx = 
self
.situ_dict[post_str]  
        act_key = 
self
.dna[gene_idx]  
        
if
 act_key == 
'5'
:
             
            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
)
:
         
        
if
 
self
.i == 
1
:
            
self
.score += 
self
.wall_penalty
        
else:
            
self
.i -= 
1

    
def
 
mv_right
(
self
)
:
         
        
if
 
self 
.j == 
self
.envir.
g_size:
            
self
.score += 
self
.wall_penalty
        
else:
            
self
.j += 
1

    
def
 
mv_down
(
self
)
:
         
        
if
 
self
.i == 
self
.envir.
g_size:
            
self
.score += 
self
.wall_penalty
        
else:
            
self
.i += 
1

    
def
 
mv_left
(
self 
)
:
         
        
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:
             
            
self
.score += 
self
.no_rub_penalty
/<code>

最後是運行遺傳算法的時候了。在下面的代碼中，我們生成一個初始的機器人種群，讓自然選擇來運行它的過程。我應該提到的是，當然有更快的方法來實現這個算法（例如利用並行化），但是為了本教程的目的，我犧牲了速度來實現清晰。

<code> 
pop
 = 
[Robot() for x in range(pop_size)]
results
 = 
[]
 
for
 
i in tqdm(range(num_gen)):
    
scores
 = 
np.zeros(pop_size)
 
    
for
 
idx, rob in enumerate(pop):
 
        
score
 = 
rob.simulate(iter_per_sim, moves_per_iter)
          = 
score

      
# 保存每一代的平均值和最大值

    
best_robot
 = 
pop[scores.argmax()] # 保存最好的機器人
 
    
inds
 = 
np.argpartition(scores, -num_breeders)[-num_breeders:] # 基於擬合度得到頂級機器人的索引 

    
subpop
 = 
[]
    
for
 
idx in inds:
        
subpop.append(pop[idx])
    
scores
 = 
scores[inds]
 
    
norm_scores
 = 
(scores - scores.min()) ** 2 
    
norm_scores
 = 
norm_scores / norm_scores.sum()
 
    
new_pop
 = 
[]
    
for
 
child in range(pop_size):
 
          
p2 = np.random.choice(subpop, p=norm_scores, size=2, replace=False)
          
p2.dna))

    
pop
 = 
new_pop
/<code>

雖然最初大多數機器人不撿垃圾，總是撞到牆上，但幾代人之後，我們開始看到一些簡單的策略（例如“如果與垃圾在一起，就撿起來”和“如果挨著牆，就不要移到牆裡”）。經過幾百次的反覆，我們只剩下一代不可思議的垃圾收集天才！

結果

下面的圖表表明，我們能夠在400代機器人種群中“進化”出一種成功的垃圾收集策略。

為了評估進化控制策略的質量，我手動創建了一個基準策略，其中包含一些直觀合理的規則：

• 如果垃圾在當前方塊，撿起來
• 如果在相鄰的方塊上可以看到垃圾，移到那個方塊
• 如果靠近牆，則向相反方向移動
• 否則，隨意移動

平均而言，這一基準策略達到了426.9的擬合度，但我們最終的“進化”機器人的平均擬合度為475.9。

戰略分析

這種優化方法最酷的一點是，你可以找到反直覺的解決方案。機器人不僅能夠學習人類可能設計的合理規則，而且還自發地想出了人類可能永遠不會考慮的策略。一種先進的技術出現了，就是使用“標記物”來克服近視和記憶不足。

例如，如果一個機器人現在在一個有垃圾的方塊上，並且可以看到東西方方塊上的垃圾，那麼一個天真的方法就是立即撿起當前方塊上的垃圾，然後移動到那個有垃圾的方塊。這種策略的問題是，一旦機器人移動（比如向西），他就無法記住東邊還有1個垃圾。為了克服這個問題，我們觀察了我們的進化機器人執行以下步驟：

1. 向西移動（在當前方塊留下垃圾作為標記）
2. 撿起垃圾往東走（它可以看到垃圾作為標記）
3. 把垃圾撿起來，搬到東邊去
4. 撿起最後一塊垃圾

從這種優化中產生的另一個反直覺策略的例子如下所示。OpenAI使用強化學習（一種更復雜的優化方法）教代理玩捉迷藏。我們看到，這些代理一開始學習“人類”策略，但最終學會了新的解決方案。

結論

遺傳算法以一種獨特的方式將生物學和計算機科學結合在一起，雖然不一定是最快的算法，但在我看來，它們是最美麗的算法之一。

本文中介紹的所有代碼都可以在我的Github上找到，還有一個演示
Notebook:https://github.com/andrewjkuo/robby-robot-genetic-algorithm。