Facebook加入
LINE加入
2021/12/25
李林 編譯自 SICARA blog
量子位 出品 | 公眾號 QbitAI
量子位今天編譯整理的這篇文章，全面地介紹了遺傳演算法（genetic algorithm），從它的起源和目標，到如何用python實現它。
本文作者是Louis Nicolle，發在法國大數據創業公司SICARA的博客上。
我們先來思考一個問題：
如何創造一個好的人工智慧？
最樸素的方法，是創造一個「經驗主義的演算法」，由一堆規則構成，比如說「如果遇到西瓜，買一個」。有了足夠多的規則，我們就能複製自然智能。
但是，這樣做工作量巨大，而最終造出的智能也不可能超過它的創作者。花了好多時間，造的東西又不理想，是不是很傷心？
於是出現了一種新方法：我們不要寫規則了，乾脆重現一下進化過程，先造出一條史前魚類，放在合適的環境中讓它進化，等著它變成人，甚至更高級的生命。這種方法叫做「遺傳演算法」。
首先，讓我們刷新自己的記憶，試著理解一下達爾文提出的自然選擇。
這個理論很簡單：物種想要生生不息，就得持續自我提升，適者才能生存。種群中最優秀的特質應該傳遞給後代，而其他個體也不能被遺忘，這樣才能維持一定的多樣性，自然環境發生變化時才更容易適應。
這是遺傳演算法的理論基礎。
優化問題
遺傳演算法在優化問題上特別管用。
我們來舉個例子：背包問題。
這個著名的數學問題是理查德·卡普在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 random def generateAWord (length): i = 0 result = "" while i < length: letter = chr(97 + int(26 * random.random)) result += letter i +=1 return result def 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 operator import random def 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 random def createChild(individual1, individual2): child = "" for i in range(len(individual1)): if (int(100 * random.random) < 50): child += individual1[i] else: child += individual2[i] return child def 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 random def 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 word def 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。
上面，我們講了遺傳演算法的理論基礎和適用問題，還講了如何創建自己的遺傳演算法。
上文涉及的所有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
— 完 —
加入社群
量子位AI社群8群開始招募啦，歡迎對AI感興趣的同學，加小助手微信qbitbot2入群；
此外，量子位專業細分群(自動駕駛、CV、NLP、機器學習等)正在招募，面向正在從事相關領域的工程師及研究人員。
誠摯招聘
量子位正在招募編輯/記者，工作地點在北京中關村。期待有才氣、有熱情的同學加入我們！相關細節，)對話界面，回復「招聘」兩個字。
量子位 QbitAI
վ'ᴗ' ի 追蹤AI技術和產品新動態
熱門推薦
留言回覆
