遗传算法简介

假设有无约束优化问题：
$$z=f(x,y)$$
如何通过遗传算法求解？
在这里需要将该优化问题与遗传算法中的概念进行对比。

• $f$ 对应遗传算法的适应度函数。
• 自变量$x,y$ 对应遗传算法的个体，注意，这里的个体实际上就是染色体/基因，也就是说，我们的遗传算法与生物学中的遗传还是有一定区别的，即在我们的算法中，我们不区分个体、染色体、基因，而将此三者认为是同一个概念。
• 那么如何将自变量$x,y$ 转换成我们所需要的基因？这就来到了我要介绍的第一个概念——解码和编码。

解码与编码

先来说说编码。
编码实际上就是将自变量编码为基因，以方便后续的遗传模拟过程。本文以二进制编码为例进行讲解。
为了方便模拟染色体，我们将行向量$[x,y]$分开进行编码，如对$x,y=[13,27]$有：

• 13的二进制编码为1101
• 27的二进制编码为11011

可以发现其长度并不相等，但是不要着急，我们可以在其之前补上若干个0，使得二者最终的长度$n$相等。

那么问题来了，$n$取多少呢？8，16还是32？再或者其他的值？
当然不是随便取，因为：

1. $n$取得过大，会使得精度表示过高，增加无谓的计算量，导致算法效率低下等问题。
2. $n$ 取得过小，会导致此时所能表示的精度不够，甚至不能覆盖自变量的所有取值范围。这和32位浮点数、64位浮点数之间的区别是一样的。

所以，$n$的取值取决于我们自变量的范围与精度。
举个例子：
对于一个自变量$x\in [-2,2]$，需要精确到小数点后5位，那么该二进制编码的总长度应为多少？
显然，问题转化为：需要一个多长的二进制编码才能表示该区间内所有具有小数点后5的数字？
很显然，该区间内所有具有小数点后5的数字共有$4\times 10^5$个。
所以，需要找到一个最小的正整数$n$，使得$2^n\ge 4\times 10^5$。

for i in range(40):if 2**i>=4e5:print(i)break

解得n=19.

---

解码就是编码的逆过程，在二进制编码中，实际上就是由二进制转换为十进制的问题，但同时需要注意不能使得解码后的值超出我们规定的自变量的区间：

def decode(x,a,b):"""解码针对染色体的某个变量"""xt=0for i in range(len(x)):xt+=x[i]*np.power(2,i)return a+xt*(b-a)/(np.power(2,len(x))-1)  # a,b是自变量的取值范围

注意，通过上面的函数，我们只对某一条基因进行了解码，实际上我们在算法中，所有个体以及每个个体的基因都是在一个大的矩阵中，取$n=20$，自变量$x,y\in [-5,5]$为例，对于基因种群解码：

def decode_X(X:np.ndarray):"""对整个种群的基因解码"""X2=np.zeros((X.shape[0],2))for i in range(X.shape[0]):xi=decode(X[i,:20],-5,5)yi=decode(X[i,20:],-5,5)X2[i]=np.array([xi,yi])return X2

选择

物竞天择，适者生存。
不像之前介绍的粒子群算法，在遗传算法中，不合适的个体会被淘汰掉。因此我们要进行模拟选择的过程，我们选择当然要选择适应能力好的个体。（在最小化问题中适应度越小越好）

def select(X,fitness):"""根据轮盘赌法选择优秀个体"""fitness=1/fitness  # fitness越小的个体越优秀，其对应的概率越大，因此需要取一下倒数fitness=fitness/fitness.sum()    # 归一化idx=np.arange(X.shape[0])    # 每个个体的索引X2_idx=np.random.choice(idx,size=X.shape[0],p=fitness)X2=X[X2_idx,:]return X2

注意我们这里还是比较仁慈的，没有淘汰辣鸡个体，这是为了后面的程序好编写。

交叉

显然，这个是模拟自然界中个体与个体之间的交 配操作。

def mutation(X,m):for i in range(0,X.shape[0],2):xa=X[i,:]xb=X[i+1,:]for j in range(X.shape[1]):if np.random.rand()<m:xa[j],xb[j]=xb[j],xa[j]  # 交叉X[i,:]=xaX[i+1,:]=xbreturn X

代码也很简单。

变异

同样，模拟自然界中的变异，这通常会带来意想不到的结果：

def mutation(X,m):for i in range(X.shape[0]):for j in range(X.shape[1]):if np.random.rand()<m:X[i,j]=(X[i,j]+1)%2return X

代码也很简单。

主函数

来到主函数，只需在每次迭代中进行解码，选择，交叉，变异等操作即可，而这些操作我们上面已经定义完毕，所以主函数代码非常简单明了：

def ga(target_func,size,gene_num,p_cross=0.3,p_muta=0.05,iter_num=100):"""遗传算法主函数params:p_cross:交叉操作的概率阈值p_muta:变异操作的概率阈值iter_num:最大迭代次数size:种群中个体的个数gene_num:表示所有自变量所需要的基因位 数量"""c=p_cross  # 交叉概率m=p_muta  # 变异概率best_fitness=[]  # 记录每次迭代的效果best_xy=[]iter_num=100X0=np.random.randint(0,2,(size,gene_num))  # 初始化种群for i in range(iter_num):X1=decode_X(X0)fitness=target_func(X1)  # 初始化适应度X2=select(X0,fitness)  # 选择操作X3=crossover(X2,c)  # 交叉操作X4=mutation(X3,m)  # 变异X5=decode_X(X4)  # 解码fitness=target_func(X5)best_fitness.append(fitness.min())x,y=X5[fitness.argmin()]best_xy.append((x,y))X0=X4  # 最后别忘了更新种群# 多次迭代后的最新效果print("最优val是: ",best_fitness[-1])print("最优解是:\n x=%.5f, y=%.5f"%best_xy[-1])return best_fitness

最后来看一下迭代的过程：

import matplotlib.pyplot as pltfitnessList=ga(fitness_func,50,40)
plt.plot(fitnessList)

by——神采的二舅