從零開始實現遺傳演算法(用遺傳演算法求解函數的最大值)

04-28

知乎專欄： https://www.zhihu.com/people/feng-xue-ye-gui-zi

由於知乎不支持markdown格式，所以有公式的地方都使用了截圖，若影響閱讀效果，可移步我的Blog：風雪夜歸子 - CSDN博客，文章會同步更新！源碼可以去我的 Github fork！

進化演算法

進化演算法，也被成為是演化演算法（evolutionary algorithms，簡稱EAs），它不是一個具體的演算法，而是一個「演算法簇」。進化演算法產生的靈感借鑒了大自然中生物的進化操作，它一般包括基因編碼，種群初始化，交叉變異運算元，經營保留機制等基本操作。與傳統的基於微積分的方法和窮舉方法等優化演算法相比，進化計算是一種成熟的具有高魯棒性和廣泛適用性的全局優化方法，具有自組織、自適應、自學習的特性，能夠不受問題性質的限制，有效地處理傳統優化演算法難以解決的複雜問題（比如NP難優化問題）。

除了上述優點以外，進化演算法還經常被用到多目標問題的優化求解中來，我們一般稱這類進化演算法為進化多目標優化演算法（MOEAs）。目前進化計算的相關演算法已經被廣泛用於參數優化、工業調度、資源分配、複雜網路分析等領域。

遺傳演算法

遺傳演算法（Genetic Algorithm，簡稱GA）是一種最基本的進化演算法，它是模擬達爾文生物進化理論的一種優化模型，最早由J.Holland教授於1975年提出。遺傳演算法中種群每個個體都是解空間上的一個可行解，通過模擬生物的進化過程，從而在解空間內搜索最優解。

首先，讓我們刷新自己的記憶，試著理解一下達爾文提出的自然選擇。

這個理論很簡單：物種想要生生不息，就得持續自我提升，適者才能生存。種群中最優秀的特質應該傳遞給後代，而其他個體也不能被遺忘，這樣才能維持一定的多樣性，自然環境發生變化時才更容易適應。這是遺傳演算法的理論基礎。

優化問題

遺傳演算法在優化問題上特別管用。

我們來舉個例子：背包問題。

這個著名的數學問題是理查德·卡普在1972年提出的。問題是這樣的：

你有兩樣東西，一個設定了承重能力的背包、一些重量和價值各不相同的盒子，目標是把盒子裝到背包里，在不超過重量限制的情況下，裝進儘可能高的價值。

它是一個優化問題，有很多可能方案，因此非常適合用遺傳演算法來解決。

遺傳演算法的基本操作可以用下圖來描述：

個體的編碼方式確定以後，針對上圖操作的具體描述如下：

　　Step 1 種群初始化：根據問題特性設計合適的初始化操作（初始化操作應盡量簡單，時間複雜度不易過高），即對種群中的N個個體進行初始化操作；

　　Step 2 個體評價：根據優化的目標函數計算種群中所有個體的適應值（fitness value）；

　　Step 3 迭代設置：設置種群最大迭代次數n_iteration，並令當前迭代次數g=1；

　　Step 4 個體選擇：設計合適的選擇運算元來對種群P(g)個體進行選擇，被選擇的個體將進入交配池中組成父代種群FP(g)，用於交叉變換以產生新的個體。選擇策略要基於個體適應值來進行，假如要優化的問題為最小化問題，那麼具有較小適應值的個體被選擇的概率相應應該大一些。常用的選擇策略有輪盤賭選擇，錦標賽選擇等。

　　Step 5 交叉運算元：根據交叉概率pm（預先指定，一般為0.9）來判斷父代個體是否需要進行交叉操作。交叉運算元要根據被優化問題的特性來設計，它是整個遺傳演算法的核心，它被設計的好壞將直接決定整個演算法性能的優劣。

　　Step 6 變異運算元：根據變異概率pc（預先指定，一般為0.1）來判斷父代個體是否需要進行變異操作。變異運算元的主要作用是保持種群的多樣性，防止種群陷入局部最優，所以其一般被設計為一種隨機變換。

通過交叉變異操作以後父代種群FP(g)生成了新的子代種群P(g+1)，令種群迭代次數g=g+1，進行下一輪的迭代操作（跳轉到Step 4），直至迭代次數達到最大的迭代次數。

為了更形象說明交叉操作的作用，我們以下圖為例來深入理解一下交叉操作的作用：

動手教程：用遺傳演算法尋找函數的最大值

為了體驗這個演算法，我們用它來解決一個簡單的問題：求解函數 f(x)f(x) 在 x∈[a,b]x∈[a,b] 的最大值。

在求解之前，我們先解釋一下個體是什麼。在本問題中，個體其實就是 ∈[a,b]∈[a,b] 中的 xx ，我們的目的就是找到一個最佳的個體 x0x0，使得 f(x0)f(x0) 達到最大值。

第一步，我們初始化一個種群：

def init_population(self): population = np.random.randint(low=0, high=2, size=(self.n_population, self.DNA_size)).astype(np.int8) return population

第二步，計算種群中每個樣本的適應度值(fitness_score)，在計算種群中每個個體的fitness_score之前，我們先要提取出每個個體的DNA，在這裡，我們用二進位來表示每個個體的DNA：

def fitness(self, population): transform_population = self.transformDNA(population) fitness_score = f(transform_population) return fitness_score - fitness_score.min() # 在select函數中按照個體的適應度進行抽樣的的時候，抽樣概率值必須是非負的

第三步，進行自然選擇，選出基因好的個體作為父代：

def select(self, population, fitness_score): fitness_score = fitness_score + 1e-4 # 下一步抽樣的過程中用到了除法，出現除法就要考慮到分母為0的特殊情況 idx = np.random.choice(np.arange(self.n_population), size=self.n_population, replace=True, p=fitness_score/fitness_score.sum()) return population[idx]

第四步，有了父代之後，就要產生後代了：

def create_child(self, parent, pop): if np.random.rand() < self.cross_rate: index = np.random.randint(0, self.n_population, size=1) cross_points = np.random.randint(0, 2, self.DNA_size).astype(np.bool) parent[cross_points] = pop[index, cross_points] return parent

第五步，產生的後代我們還需要對該後代進行一些基因突變，目的是保證種群的多樣性：

def mutate_child(self, child): for i in range(self.DNA_size): if np.random.rand() < self.mutate_rate: child[i] = 1 else: child[i] = 0 return child

最後一步就是開始進化了：

def evolution(self): population = self.init_population() for i in range(self.n_iterations): fitness_score = self.fitness(population) best_person = population[np.argmax(fitness_score)] if i%100 == 0: print(u第%-4d次進化後, 基因(fitness_score)最好的個體是: %s, 其適應度(找到的函數最大值)是: %f % (i, best_person, f(self.transformDNA(best_person)) ) ) population = self.select(population, fitness_score) population_copy = population.copy() for parent in population: child = self.create_child(parent, population_copy) child = self.mutate_child(child) parent[:] = child population = population self.best_person = best_person

詳細代碼如下：

from __future__ import divisionimport numpy as npimport matplotlib.pyplot as plt%matplotlib inline# 找到函數f(x)在區間self.x_bounder上的最大值def f(x): return np.sin(x) + np.cos(x)class GeneticAlgorithm(object): """遺傳演算法. Parameters: ----------- cross_rate: float 交配的可能性大小. mutate_rate: float 基因突變的可能性大小. n_population: int 種群的大小. n_iterations: int 迭代次數. DNA_size: int DNA的長度. x_bounder: list x 軸的區間, 用遺傳演算法尋找x在該區間中的最大值. """ def __init__(self, cross_rate, mutation_rate, n_population, n_iterations, DNA_size): self.cross_rate = cross_rate self.mutate_rate = mutation_rate self.n_population = n_population self.n_iterations = n_iterations self.DNA_size = 8 # DNA的長度 self.x_bounder = [-3, 4] # 初始化一個種群 def init_population(self): population = np.random.randint(low=0, high=2, size=(self.n_population, self.DNA_size)).astype(np.int8) return population # 將種群中的每個個體的DNA由二進位轉換成十進位 def transformDNA(self, population): population_decimal = ( (population.dot(np.power(2, np.arange(self.DNA_size)[::-1])) / np.power(2, self.DNA_size) - 0.5) * (self.x_bounder[1] - self.x_bounder[0]) + 0.5 * (self.x_bounder[0] + self.x_bounder[1]) ) return population_decimal # 計算種群中每個個體的適應度，適應度越高，說明該個體的基因越好 def fitness(self, population): transform_population = self.transformDNA(population) fitness_score = f(transform_population) return fitness_score - fitness_score.min() # 在select函數中按照個體的適應度進行抽樣的的時候，抽樣概率值必須是非負的 # 對種群按照其適應度進行採樣，這樣適應度高的個體就會以更高的概率被選擇 def select(self, population, fitness_score): fitness_score = fitness_score + 1e-4 # 下一步抽樣的過程中用到了除法，出現除法就要考慮到分母為0的特殊情況 idx = np.random.choice(np.arange(self.n_population), size=self.n_population, replace=True, p=fitness_score/fitness_score.sum()) return population[idx] # 進行交配 def create_child(self, parent, pop): if np.random.rand() < self.cross_rate: index = np.random.randint(0, self.n_population, size=1) cross_points = np.random.randint(0, 2, self.DNA_size).astype(np.bool) parent[cross_points] = pop[index, cross_points] return parent # 基因突變 def mutate_child(self, child): for i in range(self.DNA_size): if np.random.rand() < self.mutate_rate: child[i] = 1 else: child[i] = 0 return child # 進化 def evolution(self): population = self.init_population() for i in range(self.n_iterations): fitness_score = self.fitness(population) best_person = population[np.argmax(fitness_score)] if i%100 == 0: print(u第%-4d次進化後, 基因(fitness_score)最好的個體是: %s, 其適應度(找到的函數最大值)是: %f % (i, best_person, f(self.transformDNA(best_person)) ) ) population = self.select(population, fitness_score) population_copy = population.copy() for parent in population: child = self.create_child(parent, population_copy) child = self.mutate_child(child) parent[:] = child population = population self.best_person = best_person def main(): ga = GeneticAlgorithm(cross_rate=0.9, mutation_rate=0.1, n_population=300, n_iterations=2000, DNA_size=8) ga.evolution() # 繪圖 x = np.linspace(start=ga.x_bounder[0], stop=ga.x_bounder[1], num=200) plt.plot(x, f(x)) plt.scatter(ga.transformDNA(ga.best_person), f(ga.transformDNA(ga.best_person)), s=200, lw=0, c=red, alpha=0.5) ax = plt.gca() ax.spines[right].set_color(none) # 去掉右側的軸 ax.spines[top].set_color(none) # 去掉上方的軸 ax.xaxis.set_ticks_position(bottom) # 設置x軸的刻度僅在下方顯示 ax.yaxis.set_ticks_position(left) # 設置y軸的刻度僅在左邊顯示 plt.show()if __name__ == __main__: main()

參考文獻： https://www.cnblogs.com/maybe2030/p/4665837.html