從零開始實現遺傳演算法(用遺傳演算法破解密碼)

05-11

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

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

上一篇文章我們動手實驗了用遺傳演算法求解函數在給定區間的最大值。本篇文章再來看一個實驗：用遺傳演算法破解密碼。

在這個問題中，我們的個體就是一串字元串了，其目的就是找到一個與密碼完全相同的字元串。基本步驟與前一篇文章基本類似，不過在本問題中，我們用字元的ASCII值來表示個體(字元串)的DNA。其它的就不多說了，還是看詳細代碼吧：

import numpy as npclass GeneticAlgorithm(object): """遺傳演算法. Parameters: ----------- cross_rate: float 交配的可能性大小. mutate_rate: float 基因突變的可能性大小. n_population: int 種群的大小. n_iterations: int 迭代次數. password: str 欲破解的密碼. """ def __init__(self, cross_rate, mutation_rate, n_population, n_iterations, password): self.cross_rate = cross_rate self.mutate_rate = mutation_rate self.n_population = n_population self.n_iterations = n_iterations self.password = password # 要破解的密碼 self.password_size = len(self.password) # 要破解密碼的長度 self.password_ascii = np.fromstring(self.password, dtype=np.uint8) # 將password轉換成ASCII self.ascii_bounder = [32, 126+1] # 初始化一個種群 def init_population(self): population = np.random.randint(low=self.ascii_bounder[0], high=self.ascii_bounder[1], size=(self.n_population, self.password_size)).astype(np.int8) return population # 將個體的DNA轉換成ASCII def translateDNA(self, DNA): # convert to readable string return DNA.tostring().decode(ascii) # 計算種群中每個個體的適應度，適應度越高，說明該個體的基因越好 def fitness(self, population): match_num = (population == self.password_ascii).sum(axis=1) return match_num # 對種群按照其適應度進行採樣，這樣適應度高的個體就會以更高的概率被選擇 def select(self, population): fitness = self.fitness(population) + 1e-4 # add a small amount to avoid all zero fitness idx = np.random.choice(np.arange(self.n_population), size=self.n_population, replace=True, p=fitness/fitness.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) # select another individual from pop cross_points = np.random.randint(0, 2, self.password_size).astype(np.bool) # choose crossover points parent[cross_points] = pop[index, cross_points] # mating and produce one child #child = parent return parent # 基因突變 def mutate_child(self, child): for point in range(self.password_size): if np.random.rand() < self.mutate_rate: child[point] = np.random.randint(*self.ascii_bounder) # choose a random ASCII index return child # 進化 def evolution(self): population = self.init_population() for i in range(self.n_iterations): fitness = self.fitness(population) best_person = population[np.argmax(fitness)] best_person_ascii = self.translateDNA(best_person) if i % 10 == 0: print(u第%-4d次進化後, 基因最好的個體(與欲破解的密碼最接近)是: %s% (i, best_person_ascii)) if best_person_ascii == self.password: print(u第%-4d次進化後, 找到了密碼: %s% (i, best_person_ascii)) break population = self.select(population) population_copy = population.copy() for parent in population: child = self.create_child(parent, population_copy) child = self.mutate_child(child) parent[:] = child population = population def main(): password = I love you! # 要破解的密碼 ga = GeneticAlgorithm(cross_rate=0.8, mutation_rate=0.01, n_population=300, n_iterations=500, password=password) ga.evolution()if __name__ == __main__: main()