遺傳演算法能幫你破解同事的密碼？| 入門教程，附代碼

李林 編譯自 SICARA blog

量子位 出品 | 公眾號 QbitAI

量子位今天編譯整理的這篇文章，全面地介紹了遺傳演算法（genetic algorithm），從它的起源和目標，到如何用python實現它。

本文作者是Louis Nicolle，發在法國大數據創業公司SICARA的博客上。

https://blog.sicara.com/was-darwin-a-great-computer-scientist-81ffa1dd72f9

***

我們先來思考一個問題：

如何創造一個好的人工智慧？

最樸素的方法，是創造一個「經驗主義的演算法」，由一堆規則構成，比如說「如果遇到西瓜，買一個」。有了足夠多的規則，我們就能複製自然智能。

但是，這樣做工作量巨大，而最終造出的智能也不可能超過它的創作者。花了好多時間，造的東西又不理想，是不是很傷心？

於是出現了一種新方法：我們不要寫規則了，乾脆重現一下進化過程，先造出一條史前魚類，放在合適的環境中讓它進化，等著它變成人，甚至更高級的生命。這種方法叫做「遺傳演算法」。

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

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

這是遺傳演算法的理論基礎。

優化問題

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

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

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

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

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

動手教程：用遺傳演算法破解密碼

為了體驗這個演算法，我們用它來解決一個簡單的問題：破解同事的密碼。

選擇適應度函數

創建遺傳演算法的時候，第一件事是建立一個評價函數，用來衡量樣本的成功與否。

它能幫我們分清醜小鴨和白天鵝，區分開之後，我們才能給成功的樣本更多「機會」，讓它參與生成下一代。

這一步看起來很簡單，其實……嘿嘿嘿……

我們的目標是什麼來著？破解密碼。因此，函數的目標應該是將「成功/失敗」的二元結果從0（一直失敗）轉換成100（完美）。

最簡單的方法是：

fitness score = (number of char correct) / (total number of char)

這樣，fitness得分更高的樣本，就比其他個體更接近成功，我們這個fitness函數就能精確地為演算法種群分類。

def fitness (password, test_word): if (len(test_word) != len(password)): print("taille incompatible") return else: score = 0 i = 0 while (i < len(password)): if (password[i] == test_word[i]): score+=1 i+=1 return score * 100 / len(password)

創建個體

我們知道了該怎樣評價這些個體，但如何定義它們呢？這部分很難，目標是要知道哪些特徵要保持不變，哪些是可變的。

為了理清思路，我們來和基因比較一下。DNA是由基因組成的，而每個基因都來自不同的等位基因，也就是說，DNA中的每一個基因，都是從一組等位基因中選出的。你需要為演算法種群創建DNA。

在我們這個案例中，個體是詞，每個詞和密碼的長度差不多；每個字母是一個基因，這個字母的賦值是它的等位基因。比如說banana這個詞，b是第一個字母的等位基因。

這種創造有什麼意義？現在我們知道每個個體都是長度合格的詞，但是我們的種群覆蓋了這個長度下所有可能的詞。

創建第一個種群

上面我們知道了個體的特徵，以及如何評估它們，接下來，該開始嚴格意義上的「進化」了。

在創建第一個種群時，要時刻記住這一點：我們不能將種群指向一個明顯很好的方案。我們需要讓種群儘可能廣、覆蓋儘可能多的可能性，完美的第一代種群應該覆蓋現存所有等位基因。

所以，我們就要創建由隨機字母構成的單詞。

import randomdef generateAWord (length): i = 0 result = "" while i < length: letter = chr(97 + int(26 * random.random())) result += letter i +=1 return resultdef generateFirstPopulation(sizePopulation, password): population = [] i = 0 while i < sizePopulation: population.append(generateAWord(len(password))) i+=1 return population

下一代

有了第一代，想創造下一代，我們需要做兩件事：1）從現有的這一代中選擇一部分；2）讓它們結合在一起創造下一代。

首先，要從第一代中選擇用來繁殖的「親本」。

選擇有很多方法，但是你必須牢記：我們的目標是從第一代中選擇最好的方案，但不能將其他的都去掉。如果在演算法開始創建時，就只選擇了那些最好的方案，你會迅速收斂到局部最小值，沒有機會找到最佳方案。

我的方法是一方面選擇表現好的樣本，就是下面代碼中的best_sample；另一方面選擇隨機選擇一組個體，也就是下面代碼中的lucky_few。

import operatorimport randomdef computePerfPopulation(population, password): populationPerf = {} for individual in population: populationPerf[individual] = fitness(password, individual) return sorted(populationPerf.items(), key = operator.itemgetter(1), reverse=True)def selectFromPopulation(populationSorted, best_sample, lucky_few): nextGeneration = [] for i in range(best_sample): nextGeneration.append(populationSorted[i][0]) for i in range(lucky_few): nextGeneration.append(random.choice(populationSorted)[0]) random.shuffle(nextGeneration) return nextGeneration

下一步，育種。

我們依然和生物學來進行類比。有性生殖的目的是將兩個個體的DNA結合起來，我們這裡要做的事情也差不多。

我們有兩個個體，Tom和Jerry，它們的DNA是由自己的等位基因（每個字母的賦值）決定的，為了將它們的DNA結合起來，我們需要將它們的字幕混合一下。在諸多方法中，我們選擇最簡單的一個：子代的每一個字母，都隨機取自親代的Tom或Jerry。

顯然，Tom和Jerry這對親本能生成不止一個後代，我們需要控制後代的數量，來保持種群規模的穩定。也就是說，第一代的個體數要和第二代的個體數相同。

import randomdef createChild(individual1, individual2): child = "" for i in range(len(individual1)): if (int(100 * random.random()) < 50): child += individual1[i] else: child += individual2[i] return childdef createChildren(breeders, number_of_child): nextPopulation = [] for i in range(len(breeders)/2): for j in range(number_of_child): nextPopulation.append(createChild(breeders[i], breeders[len(breeders) -1 -i])) return nextPopulation

接下來，我們要談一談遺傳帶來的變化。

上一步的育種過程會導致個體的自然變異。育種之後，每個個體都必須有一定可能性會看到自己的DNA發生變異。這樣做的目標是防止演算法收斂到局部最小化。

以下是控制變異的代碼：

import randomdef mutateWord(word): index_modification = int(random.random() * len(word)) if (index_modification == 0): word = chr(97 + int(26 * random.random())) + word[1:] else: word = word[:index_modification] + chr(97 + int(26 * random.random())) + word[index_modification+1:] return worddef mutatePopulation(population, chance_of_mutation): for i in range(len(population)): if random.random() * 100 < chance_of_mutation: population[i] = mutateWord(population[i]) return population

關於如何選擇變異率，可以參考R.N.Greenwell、J.E.Angus、M.Finck 1995年的論文Optimal mutation probability for genetic algorithms。

地址：http://www.sciencedirect.com/science/article/pii/089571779500035Z

小結

上面，我們講了遺傳演算法的理論基礎和適用問題，還講了如何創建自己的遺傳演算法。

上文涉及的所有Python 3代碼都在GitHub上，地址：https://gist.github.com/NicolleLouis/d4f88d5bd566298d4279bcb69934f51d

https://blog.sicara.com/was-darwin-a-great-computer-scientist-81ffa1dd72f9

如果你想進一步探索AI和遺傳演算法，可以看看以下資源：

1. 網頁應用

BoxCar是這類演算法的一個網頁應用，這個演算法的目標是創造最有效的兩輪車輛。

http://rednuht.org/genetic_cars_2/

2. 移動應用

在Evolution這個App里，你需要創建一個有關節、骨骼和肌肉的「生物」，然後演算法會優化它的運動方式來完成特定任務，比如跳、跑、爬台階等等。

https://play.google.com/store/apps/details?id=com.keiwando.Evolution

3. DIY

最後再推薦一個編程遊戲網站。每個月，這個網站都會舉辦為期一周的比賽，讓參賽者創造最好的人工智慧，獲勝者用的幾乎一直是遺傳演算法。

https://www.codingame.com/home

— 完 —

歡迎大家關注我們的專欄：量子位 - 知乎專欄

誠摯招聘

量子位正在招募編輯/記者，工作地點在北京中關村。期待有才氣、有熱情的同學加入我們！相關細節，請在量子位公眾號(QbitAI)對話界面，回復「招聘」兩個字。

量子位 QbitAI

?"?" ? 追蹤AI技術和產品新動態

推薦閱讀：