Ciyous Note: 遺傳演算法與進化策略

02-09

第一次寫比較嚴肅的文章，肯定還存在許多漏洞與不足，希望大佬不吝賜教。

0x00 遺傳演算法 Genetic Algorithm

我們都了解過達爾文的進化論，物競天擇，適者生存，正式這樣簡單且殘酷的自然法則最終在地球上造就了人類這一神奇的物種。我們會製造並使用工具來解決問題，會創作豐富多彩的文藝作品來抒發情感，也能相互合作提高解決問題的效率。而這一切都源於億萬年的時間和無休止的遺傳變異、自然選擇。

那麼如果我們把這樣簡單的規則應用到計算機程序中，是否同樣可以得出一些有意思的結果呢？遺傳演算法 就描述了這樣一種解決問題的思想——僅僅為程序提供隨機的初始基因（參數），任其在環境（問題空間）中作出行動（動作空間），並不斷選擇較為優秀的程序進行繁衍（選取雙親參數組成新程序），淘汰適應度不佳的程序，加以隨機的變異（略微改變子代參數），以求得到適應度最高的種群（收斂）。

遺傳演算法有許多種具體的實現方法，不同的方法存在一些差異，例如樸素遺傳演算法中基因為二進位編碼的0-1串，在進化策略（Evolution Strategy，簡稱ES）中基因則為實數向量。本文將主要介紹進化策略的一種最簡單實現並給出相應的Python程序示例。

*本文並不會涉及相關理論的數學推導，有興趣的同學可以自行查閱相關文獻

0x01 進化策略 Evolution Strategy

作為一種遺傳演算法思想的具體實現，進化策略（以下簡稱ES）主要有如下幾個概念：基因DNA，變異率DNA，產生種群，自然選擇。

兩條DNA

與樸素的遺傳演算法中定義全局變異率的做法不同，ES在變異率的設置上做了一些優化——除了一條用實數表達的基因DNA以外，額外增加一條與基因等長的、決定對應位置基因變異率的變異率DNA。這條新增的變異率DNA同基因DNA一起參與遺傳變異選擇，這樣做的好處是什麼呢？

可以使每個基因位點的變異率隨著該基因對適應的貢獻程度的增加而趨於0，相當於幫助種群在最優解處收斂。

在本文的實現中，我們的變異率DNA中的數值，將具體定義為對應基因以符合均值為0的正態分布為幅度變異時，該正態分布的標準差σ。

種群的產生與淘汰

演算法開始前，我們完全隨機地生成一定數量（Population） 的個體組成初始種群。在接下來的每個事件（Episode）內，我們根據保留率挑選一部分適應度（Fitness）較高的個體作為下一代的親本產生下一代，剩餘適應度不高的個體被淘汰。經過不斷的遺傳變異選擇，整個種群將逐漸靠近最優解並在其附近趨於收斂。

0x03 代碼實現 Talk is Cheap

在本文中我會將代碼逐段呈現，想一次性看到全部代碼的話請到我的Github。

訓練環境

為了簡化實驗流程並提供可視化的進化過程，我選用了OpenAI Gym作為訓練環境。Gym是一個為強化學習研究者編寫的基於Python的開源小遊戲/環境合集，提供了大量可供使用的訓練環境，強化學習研究者僅需關注自己的演算法，而不必在測試環境上浪費太多時間。雖然我們的目的是嘗試進化策略，但是也可以使用Gym提供的環境。

Gym有幾個重要概念，事件（Episode），環境（Environment），觀測值（Observation），行動（Action） 以及獎勵（Reward） 等，關於這些概念本篇文章不會做過多介紹，近期我會寫另一篇文章介紹OpenAI Gym。

在Gym中，每個不同的小遊戲可以看作一個環境，在環境中，Agent個體需要根據當前得到的觀測值選擇下一步的行動（Action），而環境則會在Agent做出行動之後輸出四個數據：新的觀測值（Observation）、上一步操作中Agent所獲得的獎勵（Reward）、當前事件（Episode，可以看作是遊戲的一局）是否結束（Done）及一些反饋給開發者的信息（Info）。訓練的最終目的是得到該環境下一輪事件內能夠獲得最多獎勵的Agent。

下面的代碼時Gym的標準使用方式：

import gymenv = gym.make(Your-Env-Name) #初始化訓練環境observation = env.reset #初始化一個事件（Eposide）for _ in range(MAX_STEP): # 根據observation制定下一步行動 ... # 執行行動獲取結果 observation, reward, done, info = env.step(YOUR_ACTION) # 根據reward修改個體適應度 ... # 如果事件結束則退出循環 if done: break

本文中，我們選取CartPole-v1作為訓練環境，在這個環境中，Agent將會學習控制一個能夠維持一根木杆平衡的小車。這一環境的觀測值包含四個實數（分別表示小車及木杆在上一個動作結束後的某些狀態，但是我們不需要知道他們是什麼意思），而小車的可選動作（Action Space）只有兩種：0、1，分別控制小車向左或向右移動。

編寫個體（Agent）

根據ES的基本步驟，每一個個體應該具有兩條DNA，能夠與其他個體產生子代且能根據外部環境輸出相應的行動。由於每次我們可以獲得4個觀測值，並且只需要控制小車左右移動，我們可以將整個問題看成是一個一次線性函數的擬合（想想為什麼），我選擇生成包含四個實數的DNA，根據這四個數與觀測值對應相乘的和選擇小車的兩種操作，若大於0則執行操作1，否則執行操作0。

import numpy as npimport random as randclass Agent: def __init__(self): # 隨機生成一個個體，包含由兩個四維向量組成的矩陣，分別代表ES的兩種DNA self.gene = np.random.rand(2, 4) * 10 # 初始化個體適應度為0 self.fitness = 0 def __mul__(self, other): # 重載乘法運算使其成為兩個個體產生子代的運算 kid = Agent() # 下面的代碼是隨機遺傳變異的過程，我的實現不是很好 gene_T = kid.gene.T tup_DNA = (self.gene[0], other.gene[0]) DNA_P = np.vstack(tup_DNA) tup_MUT = (self.gene[1], other.gene[1]) MUT_P = np.vstack(tup_MUT) for col in range(4): rnd = rand.randint(0, 1) gene_T[col] = np.array([DNA_P.T[col][rnd], MUT_P.T[col][rnd]]) # 這裡對生成的新基因和變異率加以符合正態分布N(0，σ^2 )的變異，其中σ為對應基因的變異率 gene_T[col][0] += np.random.randn() * gene_T[col][1] gene_T[col][1] += np.random.randn() * gene_T[col][1] kid.gene = gene_T.T return kid def calc(self, observation): # 根據觀測值決定行動 res = np.sum(self.gene[0] * observation) if res > 0: return 1 if res < 0: return 0 return 0

進化策略

編寫好個體之後，我們就可以開始寫進化策略本體了。根據我們之前的描述，程序本體應該包含兩個部分：產生種群、自然選擇。

我們先來梳理一下ES的整個流程：

人為規定種群中個體總數Population以及每次自然選擇中要保留的好個體數目Keep
產生一個數量為Population的初始種群
重複以下過程直到找到最優解：

對種群中的每個個體求適應度Fitness
根據Fitness從大到小將種群中的個體排序
根據Keep保留Fitness排在前面的一部分個體，淘汰其餘個體
以保留下來的個體作為親本，產生新的個體填補淘汰出的空位
將新的種群投入訓練

產生初始種群：

agents = [Agent() for _ in range(population)]

獲取適應度並淘汰落後個體：

import gymdef get_fittness(agents): # 在Gym中訓練並獲得個體適應度 fitness = [] for agent in agents: agent.fitness = 0 for agent in agents: observation = env.reset() for _ in range(50000): observation, reward, done, info = env.step(agent.calc(observation)) if done: break # 根據獲得的獎勵調整個體適應度 agent.fitness += reward fitness.append(agent.fitness) return np.array(fitness)def choose_agent(agents): # 獲取每個個體的適應度 fitness = get_fittness(agents) # 將是適應度從大到小排序 fitness_sort = np.argsort(-fitness) # 選取好的個體加入新種群，淘汰不好的個體 new_agents = [] for i in range(keep): new_agents.append(agents[fitness_sort[i]]) # 我這裡順便返回了表現最好的個體以供展示 return new_agents, fitness, agents[fitness_sort[0]]

產生新種群：

def make_agent(agents): # 從選擇好的個體中隨機選出兩個產生新的個體，直到種群再次達到規定數目 for _ in range(population - len(agents)): agents.append(agents[rand.randint(0, keep - 1)] * agents[rand.randint(0, keep - 1)]) return agents

有了這些函數，接下來我們就可以開始進化策略的主程序編寫了。

繪製圖像

我們希望能有一個直觀的方式來展示訓練的過程，這裡可以使用matplotlib來繪製每一代種群中適應度的最大值、最小值和平均值。

我們可以在進化策略的主程序中記錄下每代個體的適應度最大、最小和均值，在訓練結束後將他們繪製成折線圖：

import matplotlib.pyplot as plt# 制定訓練環境env = gym.make(CartPole-v1)# 規定參數並生成初始種群keep = 60population = 100agents = [Agent() for _ in range(population)]# 創建用於保存繪圖數據的列表fitness_avg = []fitness_max = []fitness_min = []# 訓練主循環for i in range(100): agents = make_agent(agents) # 生成種群 agents, fitness, best = choose_agent(agents) # 自然選擇 fitness_avg.append(np.mean(fitness)) # 保存這一代適應度數據 fitness_max.append(np.max(fitness)) fitness_min.append(np.min(fitness)) print("%d Done! Avg: %d Max: %d" % (i, np.mean(fitness), np.max(fitness))) # 每訓練10代，挑選出最好的個體展示其行為 if i % 10 == 0: observation = env.reset() for _ in range(10000): # 將上一動作渲染到窗口 env.render() observation, reward, done, info = env.step( best.calc(observation)) if done: breakplt.figure()plt.plot(fitness_avg)plt.plot(fitness_max)plt.plot(fitness_min)plt.show()

0x04 訓練結果

在經過僅僅40代訓練後，種群的平均適應度就幾乎可以達到滿分。

留個贊再走唄，也可以來我的博客看看呀：Ciyous Notebook