作者博客：bot7.cc

關于遺傳算法

遺傳算法是仿照自然界中生物進化而產生的一類優(yōu)化算法。個人感覺遺傳算法簡單粗暴，適應性廣。關于遺傳算法的介紹網上有很多了，這里按照我自己的理解簡單概括一下。

1. 編碼解碼，將待優(yōu)化的參數編碼為DNA序列，最簡單直接的為二進制編碼（即有兩種堿基的DNA鏈）；
2. 生成隨機初代
3. 選擇，適應度（由待優(yōu)化的模型得到）較好的個體有更大的概率被選擇，應用比較多的方法有輪盤賭和錦標賽；
4. 按照一定概率進行隨機的交叉變異
5. GOTO Step 2

經過多個世代的迭代之后，將會收斂到最優(yōu)解。交叉和編譯的作用是產生新個體，避免陷入局部最優(yōu)解。

利用Python實現(xiàn)

前輩們常說一句話“避免重復造輪子”，其實最直接的還是搜一下別人寫的包。這里之所以花時間自己搞一個主要是因為這個算法比較簡單，邏輯性很明確，比較適合練手，因此才決定自己實現(xiàn)一下，算是敲開Python大門的第一個項目。

編碼解碼

這里選擇使用二進制編碼的方式來實現(xiàn)，根據用戶輸入的參數范圍和精度計算出每個參數需要的位數，然后將參數空間均分映射為二進制編碼。

# Encode parameters into DNA    
def encode(self, parameters):
    dna = ''
    for i in range(self.nGenes):
        geneSequenceDigit = (parameters[i]-self.parametersRange[i,0])/(self.parametersRange[i,1]-self.parametersRange[i,0])*(2**self.geneLength[i]-1)
        geneSequenceDigit = int(round(geneSequenceDigit))
        geneSequenceBin   = self.int2bin(geneSequenceDigit, self.geneLength[i])
        dna = dna + geneSequenceBin 
    dna = list(dna)  # Trun string to list
    return dna

# Decode DNA to parameters
def decode(self, dna):
    dna = ''.join(dna)  # Trun list to string
    parameters = []
    for i in range(self.nGenes):
        geneSequenceBin   = dna[self.dnaIdx[i,0]:self.dnaIdx[i,1]+1]
        geneSequenceDigit = self.bin2int(geneSequenceBin)
        parameterI = geneSequenceDigit/(2**self.geneLength[i]-1)*(self.parametersRange[i,1]-self.parametersRange[i,0])+self.parametersRange[i,0]
        parameters.append(parameterI)
    return parameters

# Returns the binary string of integer n, using count number of digits
def int2bin(self, n, count=32):
    binStr = "".join([str((n >> y) & 1) for y in range(count-1, -1, -1)])
    return binStr

# Returns digit integer of binary string
def bin2int(self, n):
    ret = int(n,2)
    return ret

這種方式實現(xiàn)的精度并不是確切的為用戶輸入的精度，而是要高于用戶的輸入精度。

選擇

選擇的策略使用了名為錦標賽的方式，同時添加了精英保留機制。錦標賽是指隨機選擇N個（通常N=2）候選個體，再從中選擇最優(yōu)的個體進入下一代，重復多次，直到子代規(guī)模達到要求。精英保留機制是是指保護已經產生的最優(yōu)個體不被淘汰，不被交叉和變異破壞。

# Select individuals
def select(self):
    nCandidates = 2
    generation  = []
    for i in range(self.popGeneration):
        candidates = random.choices(self.generation, k=nCandidates)
        fitnessList = self.fitness(candidates=candidates)
        bestFitness = max(fitnessList)
        idx = fitnessList.index(bestFitness)
        generation.append(candidates[idx].copy())
    self.generation = generation
    return

# Elitist preservation
def elitistPreservation(self):
    bestFitness = max(self.fitnessList)
    if bestFitness > self.bestFitness:
        idx = self.fitnessList.index(bestFitness)
        self.bestFitness    = bestFitness
        self.bestIndividual = self.generation[idx].copy()
    else:
        worstIndividual = min(self.fitnessList)
        idx = self.fitnessList.index(worstIndividual)
        self.generation[idx]  = self.bestIndividual.copy()
        self.fitnessList[idx] = self.bestFitness
    return

交叉和變異

交叉和編譯比較簡單，利用隨機數的方式來控制發(fā)生的概率。這里值得一提的是，現(xiàn)實中可能會發(fā)生多點的變異或者交叉，只不過概率非常低，在遺傳算法的實現(xiàn)中如果僅僅采用單點的交叉和變異也是可以的。

代碼和例子

GeneticAlgorithm.py

使用例程：

import GeneticAlgorithm as GA # 導入GeneticAlgorithm模塊
import math

# 根據具體的優(yōu)化目標設計適應度函數，par為輸入參數的列表，ret為適應度
def fitness(par):
    x = par[0]
    ret = x*math.sin(10*math.pi*x)+2
    return ret

maxGen = 500 # 迭代次數
popGeneration = 50 # 每個世代的個體數目
pCross = 0.1 # 發(fā)生交叉的概率
pMutation = 0.05 # 發(fā)生變異的概率
nGenes = 1 # 待優(yōu)化的參數的個數
parametersRange = [[-1, 2, 0.01]] # 待優(yōu)化參數的范圍及要求的精度，多個參數寫法：[[-1, 2, 0.01]，[-2, 3, 0.1]]

# 創(chuàng)建GA對象
ga = GA.GeneticAlgorithm(maxGen, popGeneration, pCross, pMutation, nGenes, parametersRange, fitness)
# 顯示對象信息
ga.info()
# 執(zhí)行優(yōu)化
ga.run()
# 顯示最優(yōu)解
ga.result()