<font size=3>

遺傳算法Python實(shí)戰(zhàn) 002.翻硬幣

還是從游戲談起

現(xiàn)在有這樣一個(gè)游戲，準(zhǔn)備10枚（當(dāng)然，也可以更多）硬幣，正反兩面分別被涂上了黃色和綠色，然后把這些硬幣都扔在桌子上。

現(xiàn)在把你的眼睛蒙上，然后去翻硬幣，贏的條件是把所有硬幣都翻到綠色一面朝上。

當(dāng)你翻正確的時(shí)候，旁邊人會(huì)告訴你，你翻對(duì)了；而你翻錯(cuò)了的時(shí)候，他會(huì)告訴你錯(cuò)了，并且把這個(gè)硬幣翻回去……當(dāng)然，他還需要把這個(gè)硬幣移到另外的地方，防止你能夠馬上改正錯(cuò)誤。

然后兩個(gè)人輪流玩，以此比較，誰(shuí)的次數(shù)最少。

在這種規(guī)則下，區(qū)區(qū)十枚硬幣，極有可能要翻幾十次甚至幾百次（翻對(duì)了的有可能又會(huì)被翻回去）……實(shí)在是一場(chǎng)堅(jiān)苦卓絕的比賽。

這也是本節(jié)所要給大家介紹的算法和實(shí)現(xiàn)。
導(dǎo)入需要的包：

import numpy,datetime,random
import matplotlib.pyplot as plt

還是一樣，先定義遺傳算法的各種基礎(chǔ)組件，先是定義一個(gè)健壯性驗(yàn)證函數(shù)：

def get_fitness(genes):
    return genes.count(1)

定義一個(gè)類(lèi)，用來(lái)存儲(chǔ)當(dāng)前進(jìn)化到的這一代物種的染色體和健壯性：

class Chromosome:
    def __init__(self, genes, fitness):
        self.Genes = genes
        self.Fitness = fitness

繼續(xù)定義變異、進(jìn)化的方法：從父本里面隨機(jī)選擇一個(gè)基因進(jìn)行變化，生成下一代種群

def mutate(parent):
    childGenes = parent.Genes
    index = random.randrange(0, len(parent.Genes))
    newGene, alternate = random.sample([1,0], 2)
    childGenes[index] = alternate if newGene == childGenes[index] else newGene
    fitness = get_fitness(childGenes)
    return Chromosome(childGenes, fitness)

這是一個(gè)顯示的方法，用來(lái)顯示前15個(gè)元素和最后15個(gè)，不100個(gè)元素會(huì)顯示很長(zhǎng)：

def display(candidate, startTime):
    timeDiff = datetime.datetime.now() - startTime
    print("{}...{}\t{:3.2f}\t{}".format(
        ''.join(map(str, candidate.Genes[:15])),
        ''.join(map(str, candidate.Genes[-15:])),
        candidate.Fitness,
        timeDiff))

然后就是執(zhí)行方法了：
首先初始化一個(gè)祖先……用numpy的randint來(lái)生成一個(gè)100個(gè)元素的0和1的整數(shù)數(shù)組。如果這個(gè)祖先函數(shù)直接就全部是1，就不用玩了……之后進(jìn)入進(jìn)化，一直進(jìn)化到全部都是1為止，其中num是我添加在里面的計(jì)數(shù)器。

def get_best():
    random.seed()
    startTime = datetime.datetime.now()
    c1 = numpy.random.randint(0,2,(100)).tolist()
    bestParent = Chromosome(c1,get_fitness(c1))
    if bestParent.Fitness >= 100:
        return bestParent
    num = 0
    while True:
        num +=1
        child = mutate(bestParent)
        if bestParent.Fitness >= child.Fitness:
            continue
        display(bestParent,startTime)
        if child.Fitness >= 100:
            display(child,startTime)
            return (child,num)
        bestParent = child

執(zhí)行函數(shù)：

b = get_best()
print(b[0].Fitness,",",b[1])

執(zhí)行結(jié)果如下：

111110111000110...110111100101100   47.00   0:00:00
111110111000110...110111100101100   55.00   0:00:00
111110111000110...110111100101100   56.00   0:00:00
111110111000110...110111100101100   57.00   0:00:00.000997
111110111000110...110111100101100   58.00   0:00:00.000997
111110111000110...110111110101100   59.00   0:00:00.000997
……
111111111011111...111111111111111   96.00   0:00:00.012965
111111111111111...111111111111111   97.00   0:00:00.013963
111111111111111...111111111111111   98.00   0:00:00.014960
111111111111111...111111111111111   99.00   0:00:00.016993
111111111111111...111111111111111   100.00  0:00:00.016993
100 , 414

一次執(zhí)行，用了0.16秒,總共翻了414次硬幣，才全部翻正確（因?yàn)殡S機(jī)的關(guān)系，每次執(zhí)行，結(jié)果會(huì)不一樣）

現(xiàn)在我們來(lái)迭代1000次，看看統(tǒng)計(jì)信息：

n = []
for i in range(1000):
    n.append(get_best()[1])
plt.hist(n)

結(jié)果如下：

頻率

可以看見(jiàn)，一般說(shuō)，最少需要200次，而最多需要1000多次，才能全部翻對(duì)，平均也得451次才能完成，可見(jiàn)真是一個(gè)艱難的游戲。

但是，我們要是修改一下游戲規(guī)則：

比如，再你翻對(duì)一枚硬幣的時(shí)候，就把這枚硬幣從桌子上拿下來(lái)。這時(shí)候桌子上剩下的就是你翻錯(cuò)的，或者還沒(méi)有翻的硬幣了，這樣看起來(lái)是不是就容易很多了啊。因?yàn)槟悴挥弥貜?fù)去翻你已經(jīng)翻對(duì)過(guò)的硬幣了。

具體的轉(zhuǎn)換到算法上，就是要記錄你翻對(duì)過(guò)的硬幣在哪里——翻對(duì)過(guò)，從桌上已經(jīng)拿掉了，就等于你不用再去翻一次了，下面來(lái)看看這種規(guī)則下的游戲：

修改基因進(jìn)化變異函數(shù)，傳入一個(gè)記錄數(shù)組，如果你隨機(jī)的索引已經(jīng)是翻過(guò)且正確的（拿掉的硬幣，則重新選擇一個(gè)索引）

def mutate(parent,idxlist):
    childGenes = parent.Genes[:]
    while True:
        index = random.randrange(0, len(parent.Genes),1)
        if index in idxlist:
            pass
        else:
            break
    newGene, alternate = random.sample([0,1], 2)
    childGenes[index] = alternate if newGene == childGenes[index] else newGene
    fitness = get_fitness(childGenes)
    return (Chromosome(childGenes, fitness),index)

開(kāi)始運(yùn)行之前，設(shè)定一個(gè)list，用來(lái)存儲(chǔ)拿掉的那些硬幣

def get_best():
    oneIndex = []
    random.seed()
    startTime = datetime.datetime.now()
    c1 = numpy.random.randint(0,2,(100)).tolist()
    bestParent = Chromosome(c1,get_fitness(c1))
    if bestParent.Fitness >= 100:
        return bestParent
    num = 0
    while True:
        num +=1
        child,idx = mutate(bestParent,oneIndex)
        if bestParent.Fitness >= child.Fitness:
            continue
        oneIndex.append(idx)
        #display(bestParent,startTime)
        if child.Fitness >= 100:
            display(child,startTime)
            return (child,num)
        bestParent = child
    display(bestParent,startTime)

執(zhí)行1000次之后，結(jié)果如下：

頻率

可以看見(jiàn)，效果顯著——平均僅需要274次，就能夠完成全部硬幣的翻面。

這種算法，在游戲中經(jīng)常用到，你不用管開(kāi)局是什么樣子的，只需要知道你這樣做是更好還是更壞，就可以最終達(dá)到最佳效果。

</font>