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

李林 編譯自 SICARA blog

量子位 出品 | 公眾號 QbitAI

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

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

blog.sicara.com/was-dar

***

我們先來思考一個問題:

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

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

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

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

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

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

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

優化問題

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

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

這個著名的數學問題是理查德·卡普在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

地址:sciencedirect.com/scien

小結

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

上文涉及的所有Python 3代碼都在GitHub上,地址:gist.github.com/Nicolle

blog.sicara.com/was-dar

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

1. 網頁應用

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

rednuht.org/genetic_car

2. 移動應用

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

play.google.com/store/a

3. DIY

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

codingame.com/home

— 完 —

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

誠摯招聘

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

量子位 QbitAI

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

推薦閱讀:

拋棄移動業務,全面轉戰 AI,微軟將與谷歌、Facebook 開啟三足鼎立時代?
AI在閱讀理解領域開始「跑分」,這個「人類好幫手」還能去哪炫技
在人機關係中採用「機本位」視角
為什麼霍金說真正的人工智慧將是人類最偉大的發明?

TAG:遗传算法 | 人工智能 |