作者博客：bot7.cc
关于遗传算法
遗传算法是仿照自然界中生物进化而产生的一类优化算法。个人感觉遗传算法简单粗暴，适应性广。关于遗传算法的介绍网上有很多了，这里按照我自己的理解简单概括一下。
- 编码解码，将待优化的参数编码为DNA序列，最简单直接的为二进制编码（即有两种碱基的DNA链）；
- 生成随机初代
- 选择，适应度（由待优化的模型得到）较好的个体有更大的概率被选择，应用比较多的方法有轮盘赌和锦标赛；
- 按照一定概率进行随机的交叉变异
- GOTO Step 2
经过多个世代的迭代之后，将会收敛到最优解。交叉和编译的作用是产生新个体，避免陷入局部最优解。
利用Python实现
前辈们常说一句话“避免重复造轮子”，其实最直接的还是搜一下别人写的包。这里之所以花时间自己搞一个主要是因为这个算法比较简单，逻辑性很明确，比较适合练手，因此才决定自己实现一下，算是敲开Python大门的第一个项目。
编码解码
这里选择使用二进制编码的方式来实现，根据用户输入的参数范围和精度计算出每个参数需要的位数，然后将参数空间均分映射为二进制编码。
# 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
这种方式实现的精度并不是确切的为用户输入的精度，而是要高于用户的输入精度。
选择
选择的策略使用了名为锦标赛的方式，同时添加了精英保留机制。锦标赛是指随机选择N个（通常N=2）候选个体，再从中选择最优的个体进入下一代，重复多次，直到子代规模达到要求。精英保留机制是是指保护已经产生的最优个体不被淘汰，不被交叉和变异破坏。
# 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
交叉和变异
交叉和编译比较简单，利用随机数的方式来控制发生的概率。这里值得一提的是，现实中可能会发生多点的变异或者交叉，只不过概率非常低，在遗传算法的实现中如果仅仅采用单点的交叉和变异也是可以的。
代码和例子
使用例程：
import GeneticAlgorithm as GA # 导入GeneticAlgorithm模块
import math
# 根据具体的优化目标设计适应度函数，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 # 发生交叉的概率
pMutation = 0.05 # 发生变异的概率
nGenes = 1 # 待优化的参数的个数
parametersRange = [[-1, 2, 0.01]] # 待优化参数的范围及要求的精度，多个参数写法：[[-1, 2, 0.01]，[-2, 3, 0.1]]
# 创建GA对象
ga = GA.GeneticAlgorithm(maxGen, popGeneration, pCross, pMutation, nGenes, parametersRange, fitness)
# 显示对象信息
ga.info()
# 执行优化
ga.run()
# 显示最优解
ga.result()
