遗传算法详解附python代码实现
遗传算法
什么是遗传算法
遗传算法是⽤于解决最优化问题的⼀种搜索算法。从名字来看，遗传算法借⽤了⽣物学⾥达尔⽂的进化理论：“适者⽣存，不适者淘汰”，将该理论以算法的形式表现出来就是遗传算法的过程。
主要过程
1. 初始化⼀个种，种中的个体DNA表⽰
2. 种中的个体进⾏交叉变异产⽣后代
3. 根据后代中每个个体适应度进⾏⾃然选择、优胜劣汰
4. 不断迭代产⽣最优种
例⼦
以求解⼆元函数为例，体会遗传算法如何解决最优化问题
def F(x,y):
return3*(1-x)**p(-(x**2)-(y+1)**2)-10*(x/5- x**3- y**5)*np.exp(-x**2-y**2)-1/3**np.exp(-(x+1)**2- y**2)
在x ∈ [ − 3 , 3 ] , y ∈ [ − 3 , 3 ] 范围⾥求函数的最⼤值问题
种和个体的概念
遗传算法启发⾃进化理论，⽽进化是以种为单位的，⽽种是⼀定空间范围内同时⽣活着的同种⽣物的全部个体，显然种与个体是遗传算法⾥必不可少的概念；在遗传算法⾥，个体通常为某个问题的⼀个解，并且该解在计算机中被编码为⼀个向量表⽰！ 例如，求⼆元函数F(x, y)的最⼤值，该问题的解即为⼀组 (x,y) 取值，如（x=1.3，y=3.5）、(x=2.6，y=3.7)…这⾥的每⼀个（x，y）对即为⼀个个体，⽽⼀组⼀组可能解的集合就叫种，⽐如在这个问题中设置100个这样的x，y的可能的取值对，这100个个体就构成了种
编码、解码与DNA
在上述提到的个体（⼀组可能解）在程序中被表⽰成⼀组向量，将实数表⽰成向量的过程称为编码 ，于是问题就转化成了将两个实数表⽰成⼀组向量的问题（这⾥转化成向量表⽰是为了之后的交叉和变
异），这⾥可以类⽐⽣物的DNA，⽣物DNA有四种碱基对–ACGT 通过不同的组合构成不同的个体，⽽计算机只有0和1两种 通过不同的0和1组成的串构成不同的个体（例⼦中的函数解），⽽这个0和1组成的串可以映射成不同的⼗进制数
编码映射
y=f(x) x是实数，y是⼆进制数
这个映射可以不⽤关⼼，因为计算机本⾝操纵的就是⼆进制数，⼆进制串也可以随机产⽣
# pop表⽰种矩阵，⼀⾏代表⼀个个体（DNA），POP_SIZE为矩阵⾏数（个体个数），DNA_SIZE为编码长度
pop=np.random.randint(2,size=(POP_SIZE,DNA_SIZE*2))
没有必要将⼀个⼗进制数转化为⼀个⼆进制数，但是后⾯肯定要将编码的⼆进制转换成我们理解的⼗进制映射相应的实数值代⼊公式求函数值，因此必然要⽤到y=f(x)的逆映射，也就是将⼆进制转化为⼗进制，这个过程叫做解码
⾸先我们限制⼆进制串的长度为10（长度⾃⼰指定即可，越长精度越⾼），例如我们有⼀个⼆进制串（在程序中⽤数组存储即可）[0,1,0,1,1,1,0,1,0,1]
这个⼆进制串如何转化为实数呢？不要忘记我们的x , y ∈ [ − 3 , 3 ] 这个限制，我们⽬标是求⼀个逆映射将这个⼆进制串映射到x , y ∈ [− 3 , 3 ] 即可，为了更⼀般化我们将x , y 的取值范围⽤⼀个变量表⽰，在程序中可以⽤python语⾔写到：
X_BOUND =[-3,3]  # x 的取值范围
Y_BOUND =[-3,3]  # y 的取值范围
为将⼆进制串映射到指定范围，⾸先先将⼆进制串按权展开，将⼆进制数转化为⼗进制数，我们有
0 * 2 + 1 * 2 + 0 * 2 + 1 * 2 + 1 * 2 + 1 * 2+ 0 * 2 + 1 * 2 + 0 * 2 + 1 * 2 = 373，将转换后的实数压缩到[ 0 , 1 ]之间的⼀个⼩数，373/（2 −1）≈0.36461388074，通过以上这些步骤所有⼆进制串表⽰都可以转换为[ 0 , 1 ]之间的⼩数，现在只需要将
[ 0 , 1 ] 区间内的数映射到我们要的区间即可。假设区间[ 0 , 1 ]内的数称为num，转换在python语⾔中可以写成：
#X_BOUND,Y_BOUND 是x ，y 的取值范围 X_BOUND = [-3, 3], Y_BOUND = [-3, 3],
x_ = num * (X_BOUND [1] - X_BOUND [0]) + X_BOUND [0] #映射为x 范围内的数
y_ = num * (Y_BOUND [1] - Y_BOUND [0]) + Y_BOUND [0] #映射为y 范围内的数
通过上述步骤完成解码任务
解码过程python代码：
def  translateDNA (pop ):
'''
解码
:param pop: 种矩阵，⼀⾏表⽰⼀个⼆进制编码的个体（可能解），⾏数为种中个体数⽬
:return: 返回的x,y 是⼀个⾏ 为种⼤⼩ 列为 1 的矩阵 每⼀个值代表[-3,3]上x,y 的可能取值（⼗进制数）
'''
x_pop =pop [:,1::2]  # pop 中的奇数列表⽰x
y_pop =pop [:,0::2]  # pop 中的偶数列表⽰y
x =x_pop .dot (2**np .arange (DNA_SIZE )[::-1])/float (2**DNA_SIZE -1)*(X_BOUND [1]-X_BOUND [0])+X_BOUND [0]
y =y_pop .dot (2**np .arange (DNA_SIZE )[::-1])/float (2**DNA_SIZE -1)*(Y_BOUND [1]-Y_BOUND [0])+Y_BOUND [0]
return  x ,y
适应度和选择
我们已经得到了⼀个种，现在要根据适者⽣存规则把优秀的个体保存下来，同时淘汰掉那些不适应环境的个体。现在摆在我们⾯前的问题是如何评价⼀个个体对环境的适应度？在我们的求最⼤值的问题中可以直接⽤可能解（个体）对应的函数的函数值的⼤⼩来评估，这样可能解对应的函数值越⼤越有可能被保留下来，以求解上⾯定义的函数F的最⼤值为例，
# 得出每个个体的适应度
def  get_fitness (pop ):
x ,y =translateDNA (pop )
pred =F (x ,y )
return  (pred -np .min (pred ))+1e -3
def  select (pop ,fitness ):  # ⾃然选择，优胜劣汰
idx =np .random .choice (np .arange (POP_SIZE ),size =POP_SIZE ,replace =True ,p =(fitness )/fitness .sum ())
return  pop [idx ]
pred是将可能解带⼊函数F中得到的预测值，得到的也是⼀个矩阵，因为后⾯的选择过程需要根据个体适应度确定每个个体被保留下来的概率，⽽概率不能是负值，所以减去预测中的最⼩值把适应度值的最⼩区间提升到从0开始，但是如果适应度为0，其对应的概率也为0，表⽰该个体不可能在选择中保留下来，这不符合算法思想，遗传算法不绝对否定谁也不绝对肯定谁，所以最后加上了⼀个很⼩的正数。select()函数中主要是使⽤了choice⾥的最后⼀个参数p，参数p描述了从np.arange(POP_SIZE)⾥选择每⼀个元素的概率，概率越⾼约有可能被选中，最后返回被选中的个体即可。
交叉、变异
通过选择我们得到了当前看来“还不错的基因”，但是这并不是最好的基因，我们需要通过繁殖后代（包含有交叉+变异过程）来产⽣⽐当前更好的基因，但是繁殖后代并不能保证每个后代个体的基因都⽐上⼀代优秀，这时需要继续通过选择过程来让试应环境的个体保留下来，从⽽完成进化，不断迭代上⾯这个过程种中的个体就会⼀步⼀步地进化。
具体地繁殖后代过程包括交叉和变异两步。交叉是指每⼀个个体是由⽗亲和母亲两个个体繁殖产⽣，⼦代个体的DNA（⼆进制串）获得了⼀半⽗亲的DNA，⼀半母亲的DNA，但是这⾥的⼀半并不是真正的⼀半，这个位置叫做交配点，是随机产⽣的，可以是染⾊体的任意位置。通过交叉⼦代获得了⼀半来⾃⽗亲⼀半来⾃母亲的DNA，但是⼦代⾃⾝可能发⽣变异，使得其DNA即不来⾃⽗亲，也不来⾃母亲，在某个位置上发⽣随机改变，通常就是改变DNA的⼀个⼆进制位（0变到1，或者1变到0）。
987654321010
需要说明的是交叉和变异不是必然发⽣，⽽是有⼀定概率发⽣。先考虑交叉，最坏情况，交叉产⽣的⼦代的DNA都⽐⽗代要差（这样算法有可能朝着优化的反⽅向进⾏，不收敛），如果交叉是有⼀定概率不发⽣，那么就能保证⼦代有⼀部分基因和当前这⼀代基因⽔平⼀样；⽽变异本质上是让算法跳出局部最优解，如果变异时常发⽣，或发⽣概率太⼤，那么算法到了最优解时还会不稳定。交叉概率，范围⼀般是
0.6~1，突变常数（⼜称为变异概率），通常是0.1或者更⼩。
# 交叉、变异
def crossover_and_mutation(pop,CROSSVER_RATE=0.8):
python代码转换new_pop=[]
for father in pop:# 遍历种中的每⼀个个体，将该个体作为⽗亲
child=father      # 孩⼦先得到⽗亲的全部基因（代表⼀个个体的⼀个⼆进制0，1串）
if np.random.rand()<CROSSVER_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 mutation(child,MUTATION_RATE=0.1):
if np.random.rand()<MUTATION_RATE:
mutate_points=np.random.randint(0,DNA_SIZE*2)# 随机产⽣⼀个实数，代表要变异基因的位置
child[mutate_points]=child[mutate_points]^1# 将变异点位置的⼆进制反转
完整代码
# 遗传算法
import numpy as np
DNA_SIZE=8
POP_SIZE=200
CROSSVER_RATE=0.9
MUTATION_RATE=0.01
N_GENERATIONS=5000
X_BOUND=[-3,3]# x的取值范围
Y_BOUND=[-3,3]# y的取值范围
def F(x,y):
return3*(1-x)**p(-(x**2)-(y+1)**2)-10*(x/5- x**3- y**5)*np.exp(-x**2-y**2)-1/3**np.exp(-(x+1)**2- y**2)
# 得到最⼤适应度
def get_fitness(pop):
x,y=translateDNA(pop)
pred=F(x,y)
return(pred-np.min(pred))+1e-3
def translateDNA(pop):
'''
解码
:param pop: 种矩阵，⼀⾏表⽰⼀个⼆进制编码的个体（可能解），⾏数为种中个体数⽬
:return: 返回的x,y 是⼀个⾏为种⼤⼩列为 1 的矩阵每⼀个值代表[-3,3]上x,y的可能取值（⼗进制数）
'''
x_pop=pop[:,1::2]# pop中的奇数列表⽰x
y_pop=pop[:,0::2]# pop中的偶数列表⽰y
x=x_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(X_BOUND[1]-X_BOUND[0])+X_BOUND[0]
y=y_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(Y_BOUND[1]-Y_BOUND[0])+Y_BOUND[0]
return x,y
# population_matrix = np.random.randint(2, size=(POP_SIZE, DNA_SIZE * 2))
# print(len(translateDNA(population_matrix)[0]))
# 交叉、变异
def crossover_and_mutation(pop,CROSSVER_RATE=0.8):
new_pop=[]
for father in pop:# 遍历种中的每⼀个个体，将该个体作为⽗亲
child=father      # 孩⼦先得到⽗亲的全部基因（代表⼀个个体的⼀个⼆进制0，1串）
if np.random.rand()<CROSSVER_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 mutation(child,MUTATION_RATE=0.1):
if np.random.rand()<MUTATION_RATE:
mutate_points=np.random.randint(0,DNA_SIZE*2)# 随机产⽣⼀个实数，代表要变异基因的位置
child[mutate_points]=child[mutate_points]^1# 将变异点位置的⼆进制反转
def select(pop,fitness):# ⾃然选择，优胜劣汰
idx=np.random.choice(np.arange(POP_SIZE),size=POP_SIZE,replace=True,p=(fitness)/fitness.sum())
return pop[idx]
def print_info(pop):
fitness=get_fitness(pop)
max_fitness_index=np.argmax(fitness)
# print('此时种',pop)
# print('max_fitness:',fitness[max_fitness_index])
x,y=translateDNA(pop)
# print('最优基因型：',pop[max_fitness_index])
# print('(x,y):',x[max_fitness_index],y[max_fitness_index])
print('max_fitness:%s，函数最⼤值:%s'%(fitness[max_fitness_index],F(x[max_fitness_index],y[max_fitness_index])))
if __name__=='__main__':
pop=np.random.randint(2,size=(POP_SIZE,DNA_SIZE*2))
for i in range(N_GENERATIONS):
x,y=translateDNA(pop)
pop=np.array(crossover_and_mutation(pop))# 交叉变异
fitness=get_fitness(pop)# 得到适应度
pop=select(pop,fitness)# 优胜劣汰
# if(i%100==0):
#    print('第%s次迭代:'%i)
#    print_info(pop)
print_info(pop)
最后，这种算法得到的种是相对与之前的⽐较优秀，但对应的最⼤值却不⼀定⽐之前淘汰的种对应的函数最⼤值要⼤，现在的种只是相对于之前的更收敛罢了，附⼀张运⾏截图