用python實現遺傳算法

Hello，大家好！最近事情比較多，一個月沒有寫公眾號了，但也積累了些不錯的內容可以分享，今天就給大家介紹的是遺傳算法，並用python加以實現。在遺傳算法的學習過程中，在CSDN上看到一篇已有人分享的python代碼，因此直接借鑑過來，並結合《數學建模與數學實驗》進行補充。（電子書和原博主連結見文末）遺傳算法介紹

遺傳算法（Genetic Algorithm），是由美國的J.Holland教授於1975年首先提出的，是受達爾文的進化論的啟發，借鑑生物進化過程而提出的一種啟發式搜索算法。

生存競爭，適者生存：對環境適應度高的個體參與繁殖的機會比較多，後代就會越來越多。適應度低的個體參與繁殖的機會比較少，後代就會越來越少。

簡單來說就是一個繁殖的過程，會發生基因交叉（Crossover），基因突變（Mutation），適應度（Fitness）低的個體會被逐步淘汰，而適應度高的個體會越來越多。

操作思路初始化

初始化進化代數計數器t←0，最大進化代數T（一般100~500），初始化變異概率α（一般0.0001~0.2）、交叉概率β（一般0.4~0.99），隨機生成M個（一般20~100）個體作為初始群體P(t)。

編碼

遺傳算法中，首要問題就是如何對解進行編碼（解的形式），編碼影響到交叉、變異等運算，很大程度上決定了遺傳算法的效率。

二進位編碼：每個基因值為符號0和1所組成的二進位數；

格雷編碼：與二進位編碼類似，連續兩個整數所對應編碼僅一碼之差；

實數編碼：每個基因值用某一範圍內的一個實數來表示；

符號編碼：染色體編碼串中的基因值取自一個無數值含義，而只有代碼含義的符號集。

個體評價

計算P(t)中各個個體的適應度值。適應度函數：也稱評價函數，是根據目標函數確定的用於區分群體中個體好壞的標準，適應度函數值的大小是對個體的優勝劣汰的依據。

選擇

選擇運算的作用是對個體進行優勝劣汰：從父代群體中選取一些適應度高個體遺傳到下一代群體中。

輪盤賭法：又稱比例選擇算子，個體i被選中的概率Pi與其適應度成正比：

兩兩競爭：從父代中隨機地選取兩個個體，比較適應度值，保存優秀個體，淘汰較差的個體

排序選擇：根據各個體的適應度大小進行排序，然後基於所排序號進行選擇。

交叉

是指對兩個相互配對的染色體，依據交叉概率按某種方式相互交換其部分基因，從而形成兩個新的個體。

變異

是對群體中的個體的某些基因座上的基因值作變動，模擬生物在繁殖過程，新產生的染色體中的基因會以一定的概率出錯。

Python實現初始化

DNA_SIZE = 24
POP_SIZE = 100
CROSSOVER_RATE = 0.8
MUTATION_RATE = 0.005
N_GENERATIONS = 100

編碼

在遺傳算法中，最常用的就是二進位編碼，我們可以利用np.random.randint()來實現：

pop = np.random.randint(2, size = (POP_SIZE, DNA_SIZE*2))

numpy.random.randint(low, high=None, size=None, dtype='l')1、low：生成的數值最低要大於等於low；當hign = None時，生成的數值要在[0, low)區間內；2、high：如果使用這個值，則生成的數值在[low, high)區間；3、size：輸出隨機數的尺寸。默認是None的，僅僅返回滿足要求的單一隨機數；4、dtype：想要輸出的格式。如int64、int等等。

一般來說DNA長度越長，所包含的信息越多，結果就越精確，當然還得具體問題具體分析。

雖然二進位編碼實現容易，便於操作，但是對於一些連續函數的優化問題，由於其隨機性使得其局部搜索能力較差，當解迫近於最優解後，由於其變異後表現型變化很大，不連續，所以會遠離最優解，達不到穩定。

格雷碼的好處就在於能夠提高遺傳算法的局部搜索能力，相比二進位精度更高。

因此，給大家介紹如何把二進位轉化為格雷碼（原理大家自行查閱）：

def BToG(pop):
    pop_g = []
    for i in pop:
        new = [i[0]]
        for j in range(1,len(i)):
            new.append(new[j-1]^i[j])
        pop_g.append(new)
    return np.array(pop_g)

「^」是按位異或運算符：當兩對應的二進位相異時，結果為1，相同結果為0。

當然，對其進行編碼後還需要再將其解碼回二進位：

def jiema(pop_g):

    pop = []
    for i in pop_g:
       new = [i[0]]
       for j in range(1,len(i)):
         if i[j] == 0:
           new.append(new[j-1])
         else:
           if new[j-1] == 0:
             new.append(1)
           else:
             new.append(0)
      pop.append(new)
    return np.array(pop)

不同的編碼，後續所對應的變換和突變也會有所不同，因為格雷碼和二進位碼比較相似，因此在這就先介紹這兩種，其它編碼歡迎加好友一起探討學習。

個體評價

通常評價函數可以由目標函數直接或間接改造得到。比如，目標函數或目標函數的倒數/相反數經常被直接用作適應度函數。一般情況下，適應度是非負的，並且總是希望適應度越大越好。比較好的適應度函數應單值、連續、非負、最大化。

def get_fitness(pop): 

  x1, x2 = translateDNA(pop)

  pred = F(x1, x2)

  return (pred - np.min(pred))

註：

translateDNA()是自定義的函數，用於將二進位碼轉換為數值，在測試部分會提到；F()是目標函數。

該評價函數是為了評價最大值的適應度，減去最小的結果是為了避免出現負數的情況；同理，如果我們想要最小值的適應度，就可以改成np.max (pred)-pred即可。

選擇

兩兩競爭和排序選擇都容易產生局部最優解的情況，因此遺傳算法中更多使用的是輪盤賭法：

def select(pop, fitness):
    idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
                           p=(fitness)/(fitness.sum()))
    return pop[idx]

參數說明：

numpy.random.choice(a, size=None, replace=True, p=None)

1、從a(只要是ndarray都可以，但必須是一維的)中隨機抽取數字，並組成指定大小(size)的數組；

2、replace:True表示可以取相同數字，False表示不可以取相同數字；

3、數組p：與數組a相對應，表示取數組a中每個元素的概率，默認為選取每個元素的概率相同。

變異

def mutation(child, MUTATION_RATE=0.003):
    if np.random.rand() < MUTATION_RATE:
        mutate_point = np.random.randint(0, DNA_SIZE)
        child[mutate_point] = child[mutate_point]^1

交叉：單點交叉&兩點交叉

單點交叉：

def crossover_and_mutation(pop, CROSSOVER_RATE = 0.8):
    new_pop = []
    for father in pop: 
        child = father
        if np.random.rand() < CROSSOVER_RATE:
            mother = pop[np.random.randint(POP_SIZE)]
            cross_points = np.random.randint(low=0, high=DNA_SIZE*2)
            child[cross_points:] = mother[cross_points:] 
            mutation(child) 
            new_pop.append(child)
    return new_pop

兩點交叉：

def crossover_and_mutation(pop, CROSSOVER_RATE = 0.8):
    new_pop = []
    for father in pop: 
        child = father
        if np.random.rand() < CROSSOVER_RATE: 
            mother = pop[np.random.randint(POP_SIZE)]
            cross_points_1 = np.random.randint(low=0, high=DNA_SIZE*2)
            cross_points_2 = np.random.randint(low= cross_points_1, high=DNA_SIZE*2)
            child[cross_points_1: cross_points_2] = mother[cross_points_1:cross_points_2]
            mutation(child)
            new_pop.append(child)
    return new_pop

到此，遺傳算法中所有的步驟我們均已實現，後面我們就以原博主所用的例子將所有步驟串起來，來進行測試。（此次測試與原博主不同的是採用格雷編碼以及兩點交叉遺傳）

我們再拿原博主的代碼跑一次做個對比。

從結果中可以看出，雖然我們用了新的編碼和遺傳形式進行計算，但結果並沒有原博主的好，所以具體問題具體分析，用算法前得多加思考，多加嘗試。

參考資料

1、https://blog.csdn.net/u014484715/article/details/40046307

2、《數學建模與數學實驗》