遺傳算法Python實(shí)戰(zhàn) 001.hello world

遺傳算法Python實(shí)戰(zhàn) 001.hello world

前言

本系列文章，來自Clinton Sheppard的著作：Genetic Algorithms with Python
本書可可以在亞馬遜官方網(wǎng)站上獲取：
https://www.amazon.com/Genetic-Algorithms-Python-Clinton-Sheppard/dp/1540324001

Genetic Algorithms with Python

文中的所有代碼，可以在github上獲取到源碼：
https://github.com/handcraftsman/GeneticAlgorithmsWithPython

另外，系列文章在蝦神的gitee上進(jìn)行同步直播：
https://gitee.com/godxia/python_genetic_algorithm

關(guān)于蝦神與本系列

看蝦神的文章的同學(xué)，肯定已經(jīng)習(xí)慣了蝦神那無所不在的表情包，但是這個(gè)系列為什么沒有一個(gè)表情包，甚至圖片都很少呢？因?yàn)檫@是蝦神首次試用markdown的方式寫文章，所有的圖片都要先上傳到gitee，才能引用，比較麻煩，所以能少用圖片就少用圖片了。

另外，蝦神的主要吃飯的活是GIS，但是作為一個(gè)計(jì)算機(jī)專業(yè)出身的老碼農(nóng)，算法一直是蝦神的基礎(chǔ)愛好，從以前的文章中，教大家手算插值就可以看出來，蝦神最喜歡的做的事情就是把各種復(fù)雜的算法，掰扯碎了為止。而且正好遇上了這段時(shí)間需要用遺傳算法去解決一部分參數(shù)優(yōu)化的問題，所以干脆就整出了這一系列的文章。

為什么要寫這個(gè)系列？

都已經(jīng)有書了，而且都有源碼了，為什么還多此一舉的寫這個(gè)系列呢？答案是本書目前還沒有中文版，一部大部頭的英文版著作，雖然說里面的英文都挺簡單的（計(jì)算機(jī)英語就沒有復(fù)雜的），但是說算法本來就是比較復(fù)雜的東西……哪怕是中文的算法書，能讀到融會(huì)貫通的人也不多，更別說英文版的了，所以蝦神準(zhǔn)備發(fā)揮自己科普小能手的功力，先自己從英文版這個(gè)地雷陣?yán)锩鏉L過去，給大家開一條路，然后大家踩著這條小路過來就好了。

當(dāng)然，原書中還有不少代碼寫得比較晦澀（作者用了大量Python特有的語法編寫模式，閱讀起來會(huì)比較痛苦），那么蝦神也會(huì)用最簡單的小白方式重寫一部分代碼，主要是方便閱讀理解（當(dāng)然這樣一改，效率可能就會(huì)降低了）。

當(dāng)然，鼓勵(lì)有興趣的同學(xué)去閱讀原書，跑原書提供的代碼。

關(guān)于遺傳算法

本系列文章完全沒有涉及任何算法的原理，沒有說教，也沒有流程圖，更沒有高大上的數(shù)學(xué)公式和推導(dǎo)，完全就是用實(shí)戰(zhàn)的方式，通過可以直接運(yùn)行和看到結(jié)果的十幾個(gè)小項(xiàng)目，用實(shí)戰(zhàn)的方式來解答遺傳算法：

  • 是這樣用的

  • 居然還可以這樣用？

  • 我去這樣用也行？

所以，遺傳算法的原理就大家可以直接自己去找，互聯(lián)網(wǎng)上大把的多。而遺傳算法的各種細(xì)節(jié)、核心、實(shí)現(xiàn)在本系列文中會(huì)逐步給大家揭曉。

關(guān)于實(shí)戰(zhàn)

什么叫做實(shí)戰(zhàn)？李云龍面對日本鬼子的時(shí)候，不會(huì)糾結(jié)對方是軍事院校的高材生，而自己大字不識幾個(gè)；也不會(huì)糾結(jié)對方是日本軍界的名將之花，而自己只是大別山區(qū)十里八鄉(xiāng)有名的篾匠……

實(shí)戰(zhàn)就是用最快最有效的方式，擊倒敵人，所以本系列文章中，出來就直接上代碼，而且保證每一份代碼都是可直接運(yùn)行的——甚至不用去安裝各種依賴包，用最基礎(chǔ)的Python環(huán)境就可以直接運(yùn)行所有的功能并且能夠直觀看見最終的結(jié)果。

練武的核心目的并不是修身養(yǎng)性，也不是強(qiáng)身健體——而是給你在走投無路的時(shí)候，一個(gè)暴起一擊，血濺五步的機(jī)會(huì)。

所以，本系列文章講究的就是兩個(gè)字：實(shí)戰(zhàn)，行不行，用代碼說話。

本系列文章的約定

  1. 本系列文章以markdown方式編寫，所以就不做各種復(fù)雜的排版了
  2. 代碼以Jupyter notebook方式提供，使用Python 3.6 及以上版本運(yùn)行。
  3. 里面如果有提供的數(shù)據(jù)，真實(shí)性和有效性均不做承諾，僅可用于學(xué)習(xí)和演示，不能用于論文寫作、出版、研究等用途。

進(jìn)入正題

猜數(shù)字小游戲

小時(shí)候我們都玩過一個(gè)游戲，就是一個(gè)人在1-10之間指定一個(gè)數(shù)字，然后另外一個(gè)人猜，看幾次可以猜中。一般來說，怎么猜也不會(huì)超過10次……

游戲過程通常如下：
A: 1
B: 錯(cuò)
A：2
B：錯(cuò)
……

A只要從1到10，依次說一遍，肯定能找到……當(dāng)然，你要是用上各種復(fù)雜的博弈論思維來思考的話，當(dāng)我沒說（最簡單的博弈，就是選擇從1開始遞增，還是選擇從10開始遞減）……

但是如果游戲的規(guī)則，從1-10,拉伸到1-1000，甚至1-10000呢……好吧，就變成了一個(gè)無聊的折磨人的問題了。因?yàn)椴还芪覀冊趺床聹y，結(jié)果就對或者錯(cuò)，沒有辦法從反饋中得到的信息來提高我們的猜測能力。

所以游戲稍微修改一下——比如A猜過之后，B會(huì)告訴他，你猜測的這個(gè)數(shù)字比他指定是數(shù)字是過大還是過小，比如這樣：

A：150
B：太小了
A：300
B：太大了
……

那么這種玩法，自然就多了很多意思了……一方可以根據(jù)另外一方的反饋，動(dòng)態(tài)調(diào)整自己的答案，以更快的接近答案。

而等我們學(xué)習(xí)了二分查找之后，發(fā)現(xiàn)，實(shí)際上會(huì)很快就能找到：

#在1-10000之間，生成一個(gè)隨機(jī)數(shù)，然后用折半查找法來進(jìn)行查詢
import random
mi,mx = 1,10000
r = random.randint(mi,mx)
x,y = mi,mx
i = 0
while(True):
    v = int((x+y)/2)
    i+=1
    print(i,v)
    if v == r:
        print("------------",r)
        break
    if v < r :
        x,y = v,y
    else:
        x,y = x,v

這個(gè)代碼執(zhí)行1000次，發(fā)現(xiàn)不管生成的數(shù)字是哪個(gè)，最少5次，最多14次，就一定能夠?qū)⑵洳檎页鰜?，?zhí)行分布如下：

分布

為什么二分查找法會(huì)比依次迭代強(qiáng)上這么多呢？答案是我們會(huì)記憶上一次分析的結(jié)果，以對本次的分析進(jìn)行參考和修正。

這就是遺傳算法的一個(gè)基本原理：

可以利用以往分析的結(jié)果，來對目前的分析進(jìn)行修正——只是遺傳算法更加復(fù)雜，它通過對問題空間的隨機(jī)探索和以進(jìn)化過程為主要手段，模擬基因的遺傳、雜交、（隨機(jī)）變異，來對一些復(fù)雜問題進(jìn)行求解，以提高我們解決問題的能力。

但是遺傳算法相對于算法界那些各種驚才絕艷天才設(shè)計(jì)不同，它非常的傻——他沒有智能，也不會(huì)學(xué)習(xí)，而且它會(huì)重復(fù)的試錯(cuò)——但是也恰恰因?yàn)樗麤]有經(jīng)驗(yàn)限制和邊界，所以往往會(huì)通過嘗試一些看似不可能的可能，從而得到一些更有啟發(fā)性的結(jié)果。

遺傳算法的核心：

遺傳算法會(huì)進(jìn)行知情猜測——即每一次嘗試都需要給出明確的更好或者更壞的評價(jià)。

猜密碼小游戲

我們把猜數(shù)字這個(gè)游戲，修改成一個(gè)更加復(fù)雜點(diǎn)的游戲，比如猜密碼，我設(shè)定這一個(gè)密碼，比如就叫做“Hello World!",這樣一共是12個(gè)字符（10個(gè)字母加兩個(gè)標(biāo)點(diǎn)符號）組成，現(xiàn)在我給你問題空間，共計(jì)26個(gè)小寫字母+26個(gè)大寫字母+空格+感嘆號+逗號+句號，一共是56個(gè)字符，要在里面找到我設(shè)定的密碼。

而你每次猜測之后，我都會(huì)告訴你，你這次猜測對了幾個(gè)字符(對的意思是字符和位置都得是正確的），但是不會(huì)告訴你對的是哪幾個(gè)，如下：

A：h
B：0個(gè)字符
A：hel
B: 2個(gè)字符（el對了)
A：Heloo
B：4個(gè)字符（Hel o對了）
A：Hello World.(11字符)
……

括號里面的內(nèi)容是不會(huì)告訴A的，只是為了告訴讀者們這個(gè)游戲規(guī)范

可以看見，最高就是12，等于12就表示你答對了所有的密碼。

那么你來玩這個(gè)游戲，大約需要多少次呢？

從理論上來看，是一個(gè)標(biāo)準(zhǔn)的排列組合問題，從56個(gè)字符里面，挑選12個(gè)進(jìn)行組合可以重復(fù)的話，一共會(huì)有—10E22這么多種組合……

如果傳統(tǒng)方式進(jìn)行迭代查找的話，大家可以試試……

而下面我們來看看怎么通過遺傳算法來進(jìn)行求解：

遺傳算法需要先定義我們的原始基因，比如我們把最終結(jié)果"Hello world!"這個(gè)字符串看成是我們的要進(jìn)化的終極目的，那么組成這個(gè)目的的基礎(chǔ)，也就是我們的基因就是26個(gè)小寫字母+26個(gè)大寫字母+4個(gè)標(biāo)點(diǎn)符號：

target = "Hello World!"
geneset = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!.,"

接下去，定義第一個(gè)方法，這個(gè)方法用于以上基因中，隨機(jī)抽取一些基因組合成一個(gè)個(gè)體。

def generate_parent(length):
    genes = []
    while len(genes) < length:
        sampleSize = min(length - len(genes), len(geneSet))
        genes.extend(random.sample(geneSet, sampleSize))
    return ''.join(genes)

然后，定義一個(gè)驗(yàn)證函數(shù)，返回你生成的這個(gè)個(gè)體，有多少個(gè)基因與最終個(gè)體相同

def get_fitness(guess, target):
    return sum(1 for expected, actual in zip(target, guess)
               if expected == actual)

這是一個(gè)變異函數(shù)，模擬在進(jìn)化的過程中，基因會(huì)發(fā)生突變。
主要邏輯是從基因庫里面隨機(jī)選擇一個(gè)基因，然后在父本基因里面進(jìn)行替換，生成一個(gè)新的字符串

def mutate(parent):
    index = random.randrange(0, len(parent))
    childGenes = list(parent)
    newGene, alternate = random.sample(geneSet, 2)
    childGenes[index] = alternate if newGene == childGenes[index] else newGene
    return ''.join(childGenes)

打印出隨機(jī)生成的字符串以及有多少個(gè)字符猜對了，以及所用的時(shí)間

import datetime
def display(guess):
    timeDiff = datetime.datetime.now() - startTime
    fitness = get_fitness(target,guess)
    print("{0}\t{1}\t{2}".format(guess, fitness, str(timeDiff)))

第一次運(yùn)行，先隨機(jī)生成一個(gè)字符串，作為起始值

random.seed()
startTime = datetime.datetime.now()
bestParent = generate_parent(len(target))
bestFitness = get_fitness(target,bestParent)
display(bestParent)

開始迭代，迭代邏輯如下：
1、對父本字符串進(jìn)行進(jìn)化變異
2、對每次進(jìn)化的字符串進(jìn)行驗(yàn)證，保留驗(yàn)證結(jié)果更好的字符串進(jìn)行進(jìn)化
3、重復(fù)迭代，直到最后找到結(jié)果

while True:
    child = mutate(bestParent)
    childFitness = get_fitness(target,child)
    if bestFitness >= childFitness:
        continue
    display(child)
    if childFitness >= len(bestParent):
        break
    bestFitness = childFitness
    bestParent = child

執(zhí)行結(jié)果如下：（隨機(jī)生成的，所以每次執(zhí)行過程可能都不同）

YOcUCHXSejh     0   0:00:00
YOclCHXSejh     1   0:00:00
YeclCHXSejh     2   0:00:00.001023
YeclCHWSejh     3   0:00:00.001023
YeclC WSejh     4   0:00:00.001023
YeclC WSrjh     5   0:00:00.001993
YeclC WSrjh!    6   0:00:00.001993
YeclC WSrlh!    7   0:00:00.003029
Yeclo WSrlh!    8   0:00:00.003029
Yeclo Worlh!    9   0:00:00.003029
Heclo Worlh!    10  0:00:00.008974
Heclo World!    11  0:00:00.009972
Hello World!    12  0:00:00.025929

當(dāng)然，你可以把密碼修改得更復(fù)雜，比如蝦神最喜歡的指環(huán)王電影第一部的開場詩：

The world is changed.

I feel it in the water.

I feel it in the earth.

I smell it in the air.

Much that once was.

is lost.

For none now live who remember it.

,U!OlRmdhfaqS YAcIbZwHykvKVtsBTWjinFrJgXM.ueoNGCQEzLxDPpsAVGwrKLT ZQPRiNHfqtelD!domJXS.bWxgahBcpUyznMCIFYjvkEO,ukbBXWRICoJpTAw,FzqPlegfMKdj!sQc NynaDhuUGrSi    1   0:00:00
,U!OlRmdhfaqS YAcIbZwHykvKVtsBTWjinFrJgXM.ueoNGCQEzLxDPpsA GwrKLT ZQPRiNHfqtelD!domJXS.bWxgahBcpUyznMCIFYjvkEO,ukbBXWRICoJpTAw,FzqPlegfMKdj!sQc NynaDhuUGrSi    2   0:00:00.001005
,U!OlRmdhfaqS YAcIbZwHykvKVtsBTWjinFrJgXM.ueoNGCQEzLxDPpsA GwrKLT ZQPRiNHfqtelD!domJXS.bWxgahBcpUyznMCIFYjvkEO,ukbBXWRICoJpTAw,FzqPlegfMKdj!sQc NynaDbuUGrSi    3   0:00:00.001994
,U!OlRmdhfaqS YAcIbZwHykvKVtsBTWjinFrJgXM.ueoNGCQEzLxDPpsA Gwr LT ZQPRiNHfqtelD!domJXS.bWxgahBcpUyznMCIFYjvkEO,ukbBXWRICoJpTAw,FzqPlegfMKdj!sQc NynaDbuUGrSi    4   0:00:00.002991
,U!OlRmdhfaqS YAcIbZwHykvKVtsBTWjinFrJgXM.ueoNGCQEzLxDPpsA Gwr LT ZQPRiNHfqtelD!domJXS.bWxgahBcpUyzhMCIFYjvkEO,ukbBXWRICoJpTAw,FzqPlegfMKdj!sQc NynaDbuUGrSi    5   0:00:00.003989
……
The world is changed. I feel it in the water. G feel it in Ghe earth. I smell it in the air. Much that once was. is lost. For none now live who rememberGiS.    152 0:00:00.801853
The world is changed. I feel it in the water. G feel it in the earth. I smell it in the air. Much that once was. is lost. For none now live who rememberGiS.    153 0:00:00.820839
The world is changed. I feel it in the water. G feel it in the earth. I smell it in the air. Much that once was. is lost. For none now live who remember iS.    154 0:00:00.825819
The world is changed. I feel it in the water. G feel it in the earth. I smell it in the air. Much that once was. is lost. For none now live who remember it.    155 0:00:00.870705
The world is changed. I feel it in the water. I feel it in the earth. I smell it in the air. Much that once was. is lost. For none now live who remember it.    156 0:00:00.898627

從最早的隨機(jī)字符串開始，總共經(jīng)過5200多次進(jìn)化，最終生成了指環(huán)王的開場詩

所以，按照隨機(jī)宇宙理論，只要猴子足夠多，是否能夠打出莎士比亞全集來呢？

無限猴子理論

(不過真實(shí)情況下，猴子只會(huì)按住一個(gè)按鍵不放，然后在屏幕上打出一連串的jjjjjjjj……)

還有的話，按照遺傳算法，你得對猴子進(jìn)行獎(jiǎng)勵(lì)，如果他答對了一個(gè)字符或者一個(gè)詞，你得獎(jiǎng)勵(lì)它們一根香蕉，這樣才符合遺傳算法的核心——必須具備進(jìn)化驗(yàn)證功能。

待續(xù)未完

作者的github上的源代碼，把上面的算法給抽象封裝成了可供通用的類，而且進(jìn)行了多次重復(fù)驗(yàn)證統(tǒng)計(jì)，我這里就不展開源碼講了，有興趣的同學(xué)自行去訪問作者的github。

因?yàn)槟承┣闆rgithub網(wǎng)絡(luò)不好，所以同學(xué)們可以訪問蝦神的gitee：
https://gitee.com/godxia/python_genetic_algorithm

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容