前言遗传算法，顾名思义，与遗传学有关。它是一种模拟自然界自然选择和适者生存的搜索算法。由于该算法与遗传学密切相关，包括种群、个体、基因、交叉、变异、适应度等概念。刚刚学习遗传算法的初学者可能会混淆这个概念。本文尝试从初学者的角度出发，希望能写出一篇通俗易懂，快速介绍遗传算法，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对染色体，但始终是一对一的关系。染色体之所以被提出，只是因为染色体上有n组基因（这个我们很熟悉），通过一对一的关系，可以知道个体上有n组染色体。种群：一个种群包含m个个体，即m个群解。交叉：交叉和变异的目的是突破局部区域，向全局最优解运行。交叉是父母之间的交配。对于父亲\(x_1,y_1,z_1...和母亲x_2,y_2,z_2...\)两组解，将每个基因转换为二进制（转换为二进制对编程操作更方便，并且对突破局部更有帮助，这里就不细说了）比如：01001|0011001|0001+11010|1110110|1101------------------------>（哭，sf不支持的下划线）这句话可以忽略。01001|1110110|0001（中间交叉交换）然后通过设置交叉率来控制交叉频率。取值范围一般为0.4~0.99Mutation（突变）：也使用各个基因的二进制，突变为随机突变。如：01001|0011001000101001|11001101110来自|对每一位，0变1，1变0。同时我们会设置一个小的变异率来控制变异的频率。取值范围一般为0.0001~0.1。这里再重复一遍遗传思路：$$随机n组解\longrightarrow(交叉,变异)\longrightarrow后代n组解\longrightarrow(优选)\longrightarrow新生代n组解$$mutation我们理解了交叉，那么如何实现“优选”？下面我们介绍一下健身。Fitness（适应度）：孩子的n组解中的每组解都有一个m值带入方程，这个m值就是我们的适应度。适应度百分比：\（每组儿童解的适应度/所有儿童解的适应度之和\）适应度百分比就是我们选择的概率。概率越大，我们选择的概率就越大。错误选择的概率较小，从而实现良好的选择并获得新一代。（ps：这种比重更大，概率更高的选择方式也叫轮盘赌选择方式）下面直接用Python实现代码，作者写了很多注释。读者从main函数和初始变量入手，相信是非常容易理解的。同时运行结果，点击图片可以看到每次迭代的仿真过程。importnumpyasnpimportmatplotlib.pyplotaspltfrommatplotlibimportcmfrommpl_toolkits.mplot3dimportAxes3DCROSSOVER_RATE=0.8MUTATION_RATE=0.03POP_SIZE=200#pop是populationDNA_SIZE=24N_GENERATIONS=50X_BOUND,3_[Y_BOUND=[Y-3,3]defF(x,y):返回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)defplot_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')轴.set_zlabel('z')plt.pause(3)plt.show()deftranslateDNA(pop):#pop代表种群矩阵，一行代表一个二进制编码的DNA，矩阵的行数代表populationnumberx_pop=pop[:,1::2]#x表示奇数列，即::从第一列开始，每跳两步，取一个y_pop=pop[:,::2]#y表示偶数列#nowx_pop,y_pop已成为矩阵（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]returnx,ydefcrossover_and_mutation(pop,CROSSOVER_RATE=0.8):new_pop=[]forfatherinpop:#traverseeachofthepopulation个体,把这个个体当成父亲child=father#孩子先得到父亲的所有基因ifnp.random.rand()
