前言
遗传算法，顾名思义和遗传相关，是模拟自然界物竞天择，适者生存的搜索算法。
由于此算法与遗传紧密联系，包含种群（population),个体,基因,交叉（crossover）,遗传（mutation),适应度（fitness)等概念。初学者刚学遗传算法，可能会混淆概念。本文尽量以初学者的角度出发，希望写一篇通俗易懂，快速入门遗传算法，并能上手python代码的文章。
原理
1.什么是遗传算法？
遗传算法是用于解决最优化问题的搜索算法。
通俗来说是解决最大值，最小值的问题。同时可以结合其他方法，解决一些线性，非线性的问题。
举个例子：(我们以求最大值为例）
已知:\(m=f(x)+f(y)+f(z)...\)和 x,y,z...的定义域, 求\(m_{max}\)以及此时的x,y,z...?
遗传算法解决问题的思路？
（继续上面的例子）在x,y,z的定义域内随机取几组值，每一组带入方程就有一个m的解。m越大的越靠近最大值，符合我们的要求，就比较好。然后对这几组值，不好的我们就摒弃它，较好的我们就留下它（并且复制一份较好的，代替摒弃了的），这样我们就得到新的几组值更靠近我们的最大值。
这样第一轮就已经结束，我们不断一轮一轮地进行摒弃、留下的选择，代代更替，我们最终将得到最好的，也就是最大值的最优解。
但是，以上忽略了一个问题，我们只从最开始的几组值中选出最好的，就算摒弃了所有不好的，它也只是这几组中得到的最大值的解，很可能不是是全局的最优解。所以我们的解决方法是每轮将其中的某组数据，或者某几组数据进行随机改变，让他产生新的解，这就突破了只有最初几组数据的局部最大值的壁垒。随机产生的可能更大或者更小，更小的被丢弃，更大的留下。逐步逼近全局最大值。
而实际上，我们的初始数据不只几组，可能比较多，每一轮进行迭代，迭代的次数也会非常多。这样，通过大量的迭代轮回最终就会逐渐达到我们的最优解。
引入遗传背景知识
有了上面的大致思路，就可以引入我们的遗传学概念。
- 基因(DNA)：对于单个自变量x或y,z...,是一个基因。同时，我们这里基因就是DNA。
- 1个体=1染色体=1种表现型=1组解：虽然人体有23对染色体，但是这里始终是1对1的关系。染色体的提出只是因为染色体上有n组基因（这个我们熟知），而通过1对1的关系可知，个体上就有n组染色体。
- 种群（population）：一个种群包含m个个体，即m组解。
- 交叉（crossover)：交叉和变异的目的都是为了突破局部，向全局最优解奔去。
交叉就是父母之间的交配，对于父亲\(x_1,y_1,z_1...和母亲x_2,y_2,z_2...\)两组解，将每个基因转换为二进制（转换为二进制对编程操作比较方便，同时对突破局域更有帮助，这里不过多阐述）如：
01001|0011001|0001
+11010|1110110|1101
--------------------------> (哭了，sf不支持<u></u>的下划线）此句可忽略。
01001|1110110|0001 (中间的交叉互换）
然后通过设置一个交叉率，控制交叉的频率。取值范围一般0.4~0.99
- 变异（mutation):同样使用每个基因的二进制，变异是随机突变。
如：
01001|00110010001
01001|11001101110
从|后面的每一位，0变为1，1变为0.
同时我们会设置较小的变异率，控制变异的发生频率。取值范围一般0.0001~0.1
我们这里再次复述一遍遗传思路：
$$
随机n组解\longrightarrow(交叉，变异）\longrightarrow儿女n组解\longrightarrow(选择优良)\longrightarrow新一代n组解
$$
变异和交叉我们了解了，那么是如何实现“选择优良”的呢？这里我们引入适应度。
- 适应度(fitness)：儿女n组解中每一组解，带入方程都有一个m值，这个m值就是我们的适应度。
-
适应度百分比：\(儿女每一组解的适应度/儿女所有解的适应度总和\)
适应度百分比就是我们进行选择的概率，越大，我们选择的概率也就越大。不好的选择的概率就越小，从而实现优良选择，得出新的一代。（ps:这种占比越大概率越大的选择方法也叫做轮盘赌选择法）python实现
下面直接上代码，作者写了大量注释，读者从main函数和初始变量开始看，相信非常容易理解。同时运行结果，点击图片可以看到，每轮迭代的模拟过程。
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm
from mpl_toolkits.mplot3d import Axes3D
CROSSOVER_RATE=0.8
MUTATION_RATE=0.03
POP_SIZE=200#pop是population
DNA_SIZE=24
N_GENERATIONS=50
X_BOUND=[-3,3]
Y_BOUND=[-3,3]
def F(x, y):
return 3*(1-x)**2*np.exp(-(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 plot_3d(ax):
X=np.linspace(*X_BOUND,100)
Y=np.linspace(*Y_BOUND,100)
X,Y=np.meshgrid(X,Y)
Z=F(X,Y)
ax.plot_surface(X,Y,Z,rstride=1,cstride=1,cmap=cm.coolwarm)
ax.set_zlim(-10,10)
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('z')
plt.pause(3)
plt.show()
def translateDNA(pop):#pop表示种群矩阵，一行表示一个二进制编码的DNA，矩阵的行数表示种群数目
x_pop=pop[:,1::2]#x表示奇数列，即::即从第一列开始，每跳两下，都取一个
y_pop=pop[:,::2]#y表示偶数列
#现在x_pop,y_pop都变成了matrix(popsize,DNAsize)
# pop:(POP_SIZE,DNA_SIZE)*(DNA_SIZE,1) --> (POP_SIZE,1)
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
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)#x算一个基因，y算一个基因，所以是DNAsize*2
child[cross_points:]=mother[cross_points:]#每个位点都要改变
mutation(child)
new_pop.append(child)
return new_pop
def mutation(child,MUTATION_RATE=0.03):
if np.random.rand()<MUTATION_RATE:
mutate_point=np.random.randint(0,DNA_SIZE)#这里基因只变了前面，但2*dnasize也是可以的
child[mutate_point]=child[mutate_point]^1
def get_fitness(pop):
x,y=translateDNA(pop)
pred=F(x,y)
return (pred - np.min(pred)) + 1e-3 # 减去最小的适应度是为了防止适应度出现负数，通过这一步fitness的范围为[0, np.max(pred)-np.min(pred)],最后在加上一个很小的数防止出现为0的适应度
def select(pop, fitness): # nature selection wrt pop's fitness
idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
p=(fitness)/(fitness.sum()) )#如果最小1-p即可
return pop[idx]
def print_info(pop):
fitness = get_fitness(pop)
max_fitness_index = np.argmax(fitness)
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]))
if __name__ == "__main__":
fig = plt.figure()
ax = Axes3D(fig)
plt.ion()#将画图模式改为交互模式，程序遇到plt.show不会暂停，而是继续执行
plot_3d(ax)
pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE * 2))
#随便取0-2范围的数据，满足x，y定义域即可
#matrix (POP_SIZE, DNA_SIZE)种群初始化，这个时候注意，要满足可行域x还是y
for _ in range(N_GENERATIONS):#迭代N代
x,y=translateDNA(pop)#表现型转化为基因，再在图中画出来
if 'sca' in locals():
sca.remove()
sca=ax.scatter(x,y,F(x,y),c='black',marker='o')#三维就x,y,z 二维就x,y就可以了
plt.show();plt.pause(0.1)
pop=np.array(crossover_and_mutation(pop,CROSSOVER_RATE))
#F_values = F(translateDNA(pop)[0], translateDNA(pop)[1])#x, y --> Z matrix
fitness=get_fitness(pop)
pop = select(pop, fitness) #选择生成新的种群
print_info(pop)
plt.ioff()
plot_3d(ax)下面展示，从最开始随机选的200个解，逐渐逼近最优解的过程。
练习
这里放上2022mathcup D题，第一问遗传算法，请读者进行思考，并自行寻找答案。
结语
相信读者已经入门遗传算法，并掌握python代码。
这里补充几点遗传算法的优点：
- 启发式搜索 ：逐渐向最优解靠近，不盲目搜索。
- 群体搜索 ：多个解并发处理，同时向最优解靠近。
- 适用范围广 ：不受连续，可微等条件限制。
以及遗传算法的应用：
遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。
另一方面，遗传算法与模糊技术，神经网络的结合已经取得了不少成果~
好了，完结撒花~本次分享到此结束，创作不易，你的点赞是我继续创作的动力~
相关文章
