CHINESE INSTITUTE OF COMMAND AND CONTROL
CICC科普栏目｜优化算法——遗传算法发表时间：2024-08-02 15:35 与遗传算法的第一次接触遗传算法是我进入研究生阶段接触的第一个智能算法，从刚开始接触，到后来具体去研究，再到后来利用遗传算法完成了水利水电的程序设计比赛，整个过程中对遗传算法有了更深刻的理解，在此基础上，便去学习和研究了粒子群算法，人工蜂群算法等等的群体智能算法。想利用这个时间，总结下我对于遗传算法的理解，主要还是些基本的知识点的理解。 遗传算法的基本概念遗传算法(Genetic Algorithm, GA)是由Holland提出来的，是受遗传学中的自然选择和遗传机制启发发展起来的一种优化算法，它的基本思想是模拟生物和人类进化的方法求解复杂的优化问题。 基本定义
遗传算法的基本流程遗传算法的过程中主要包括这样几个要素：1、参数的编码。2、初始群体的设定。3、适应度函数的设计。4、遗传操作设计。5、控制参数的设定。基本遗传算法的具体过程如下：
这里写图片描述 遗传算法过程中的具体操作参数的编码遗传算法中的参数编码的方式主要有：1、二进制编码。2、Gray编码。3、实数编码。4、有序编码。 二进制编码二进制编码是最原始的编码方式，遗传算法最初是在二进制编码的方式下进行运算的。二进制编码也是遗传算法中使用最为直接的运算编码方式。二进制编码是指利用00和11对问题的解向量进行编码。例如，对于如下的优化问题： maxf(x1,x2)=21.5+x1sin(4πx1)+x2sin(20πx2) max\; f\left ( x_1,x_2 \right )=21.5+x_1sin\left ( 4\pi x_1 \right )+x_2sin\left ( 20\pi x_2 \right ) −3.0≤x1≤12.1;4.1≤x2≤5.8 -3.0\leq x_1\leq 12.1;4.1\leq x_2\leq 5.8 其三维图像如下图所示：
这里写图片描述 在对这样的优化问题进行二进制编码的过程中，是将问题的可能解编码为二进制位串，例如问题的可能解为实数对(x1,x2)\left ( x_1,x_2 \right )，首先必须将x1x_1和x2x_2分别使用二进制位串表示，然后将他们的二进制位串组合在一起。对于每一个变量的二进制位串的长度取决于变量的定义域所要求的精度。 二进制位串的长度的计算方法如下：假设aj≤xj≤bja_j\leq x_j\leq b_j，所要求的精度是小数点后tt位。这要求将区间划分为至少(bj−aj)10t\left ( b_j-a_j \right )10^t份。假设表示变量xjx_j的位串的长度用ljl_j表示，则ljl_j可取为满足下列不等式的最小数mm： (bj−aj)10t≤2m−1 \left ( b_j-a_j \right )10^t\leq 2^m-1 即有： 2lj−1−1<(bj−aj)10t≤2lj−1 2^{l_j-1}-1<\left ( b_j-a_j \right )10^t\leq 2^{l_j}-1 对于上述的优化问题，假设精度为小数点后44位，则： (12.1−(−3.0))×10000=151000 \left ( 12.1-\left ( -3.0 \right ) \right )\times 10000=151000 217−1<151000≤218−1 2^{17}-1<151000\leq 2^{18}-1 那么表示变量x1x_1的二进制位串的长度为l1=18l_1=18。同理，对于变量x2x_2： (5.8−4.1)×10000=17000 \left ( 5.8-4.1 \right )\times 10000= 17000 214−1<17000≤215−1 2^{14}-1<17000\leq 2^{15}-1 表示变量x2x_2的二进制位串的长度为l2−15l_2-15。此时，个体可以表示为：
这里写图片描述 其中，前1818位表示的是x1x_1，后1515位表示的是x2x_2。 Gray编码这种编码方式在求解优化问题时，本人基本上没做过任何研究。 实数编码在二进制编码的过程中存在这样的一个问题，即在计算适应值的时候需要将二进制编码转换成十进制的编码进行运算，这样，很显然会想到能否直接使用十进制编码直接进行运算，如上例中的(x1,x2)\left ( x_1,x_2 \right )这样的编码方式。 有序编码有序编码主要使用在TSP问题中， 初始群体的设定在解决了个体的编码问题后，需要解决的问题是如何利用个体表示群体。在上述中，我们知道，群体是个体的集合。假设初始群体的大小为N=20N=20。对于二进制编码方式与实数编码方式产生2020个初始解。如： v1=(010001001011010000111110010100010) v_1=\left ( 010001001011010000111110010100010 \right ) 对应的实数编码的方式则为： v1=(1.052426,5.755330) v_1=\left ( 1.052426,5.755330 \right ) 对于二进制编码则是随机初始化2020组这样的初始解，每组初始解随机初始化3333位的0−10-1编码。而对于实数编码方式，则是在区间上随机初始化2020组初始解。 适应度函数的计算适应度函数的目的是评价个体的好坏，如上面的优化问题中，即为最终的优化目标函数。对于二进制编码，则需要先将二进制编码转换成实数编码，再进行适应值函数的计算，对于实数编码方式，则直接进行适应值函数的计算。 遗传操作设计遗传操作主要包括：选择(selection)、交叉(crossover)、变异(mutation)，遗传操作的主要目的是从当前的群体中产生新的群体，这样便能使得产生新的更优的个体。 选择(selection)选择操作的目的是选择出父体，用于参加交叉(crossover)和变异(mutation)操作。一般使用较多的方式是轮盘赌的选择策略(Roulette Wheel Selection)。根据每个个体的适应值，计算出相对适应值大小，即： pi=fi∑fi p_i=\frac{f_i}{\sum f_i} 相对适应值又称为选择概率，将一个圆盘划分成NN份，即群体的大小。每个扇面的面积与其选择概率成正比。轮盘如下图所示：
这里写图片描述 现在在[0,1]\left [ 0,1 \right ]上产生一个随机数rr，若： p1+p2+⋯+pi−1<r≤p1+p2+⋯+pi p_1+p_2+\cdots+p_{i-1}<r\leq p_1+p_2+\cdots+p_i 则选择第ii个个体。重复此操作NN次，选择出NN个父体。轮盘赌的算法过程如下所示：
这里写图片描述 交叉(crossover)交叉操作也称为杂交，其目的是产生新的个体。对于二进制编码方式，主要有单点杂交和多点杂交。单点杂交是指在二进制串中随机选择一位，交换两个父体中该位以后的二进制串，用以产生新的个体，操作如下图所示：
这里写图片描述 多点杂交是指在二进制串中选择某几位进行杂交，其中以两点杂交最为常见，其过程如下图所示：
这里写图片描述 具体的操作过程为：设定一个杂交的概率pcp_c，对选择操作中产生的NN个父体，每个父体产生一个[0,1]\left [ 0,1 \right ]区间上的随机数rkr_k，若rk<pcr_k< p_c，则将第kk个个体用于杂交，若选择出来的个体数目是奇数，则在父体集合中再随机挑选一个，以保证挑选出的是偶数个，之后进行两两杂交操作。对于实数编码形式，可以将实数转换成二进制编码的形式进行杂交运算，但是这样同样存在效率的问题，在实数编码中，主要采用的是算术杂交方式，算术杂交分为：部分算术杂交和整体算术杂交。部分算术杂交是指在父体向量中选择一部分分量进行算术运算，而整体算术杂交是指全部的分量都进行算术运算。我们以整体算术杂交为例：先在[0,1]\left [ 0,1 \right ]生成nn个随机数a1,a2,⋯,ana_1,a_2,\cdots ,a_n，经杂交算子后，所得到的两个后代为： x′=(a1x1+(1−a1)y1,a2x2+(1−a2)y2,⋯,anxn+(1−an)yn) {x}'=\left ( a_1x_1+\left ( 1-a_1 \right )y_1,a_2x_2+\left ( 1-a_2 \right )y_2,\cdots ,a_nx_n+\left ( 1-a_n \right )y_n \right ) y′=(a1y1+(1−a1)x1,a2y2+(1−a2)x2,⋯,anyn+(1−an)xn) {y}'=\left ( a_1y_1+\left ( 1-a_1 \right )x_1,a_2y_2+\left ( 1-a_2 \right )x_2,\cdots ,a_ny_n+\left ( 1-a_n \right )x_n \right ) 变异(mutation)变异操作的目的是使得基因突变，在优化算法中，可以防止算法陷入局部最优，从而跳出局部最优，帮助算法找到全局最优解。二进制编码时的变异算子非常简单，只是依一定的概率(称为变异概率)将所选个体的位取反。即若是11，则取00；若是00，则取11。具体的操作为：设定一个变异概率pmp_m，对杂交操作后的NN个父体，对父体中的每一个位产生一个[0,1]\left [ 0,1 \right ]区间上的随机数rk,jr_{k,j}，若rk,j<pmr_{k,j}< p_m，则该位变异。对于实数编码方式，可以采用均匀变异和非均匀变异方式，在均匀变异中，假设x=(x1,x2,⋯,xn)x=\left ( x_1,x_2,\cdots ,x_n \right )是要变异的个体，随机产生一个随机整数k∈[1,n]k\in \left [ 1,n \right ]，产生新的后代x=(x1,x2,⋯,x′k,⋯,xn)x=\left ( x_1,x_2,\cdots ,{x}'_k,\cdots, x_n \right )，其中x′k{x}'_k是[lk,uk]\left [ l_k, u_k \right ]中服从均匀分布的一个随机数。另一种是非均匀变异，，假设x=(x1,x2,⋯,xn)x=\left ( x_1,x_2,\cdots ,x_n \right )是要变异的个体，随机产生一个随机整数k∈[1,n]k\in \left [ 1,n \right ]，产生新的后代x=(x1,x2,⋯,x′k,⋯,xn)x=\left ( x_1,x_2,\cdots ,{x}'_k,\cdots, x_n \right )，其中： x′k={xk+Δ(t,uk−xk)xk−Δ(t,xk−lk) if Random(2)=0 if Random(2)=1 {x}'_k=\begin{cases} x_k+\Delta \left ( t,u_k-x_k \right ) & \text{ if } Random(2)=0 \\ x_k-\Delta \left ( t,x_k-l_k \right ) & \text{ if } Random(2)=1 \end{cases} 这里tt是当前演化代数，函数Δ(t,y)\Delta \left ( t,y \right )返回[0,y]\left [ 0,y \right ]中的一个值，并且Δ(t,y)\Delta \left ( t,y \right )随tt的增加而趋于00的概率增大。函数Δ(t,y)\Delta \left ( t,y \right )具体形式为： Δ(t,y)=y⋅(1−r(1−t/T)b) \Delta \left ( t,y \right )=y\cdot \left ( 1-r^{\left ( 1-t/T \right )^b} \right ) 或者 Δ(t,y)=y⋅r⋅(1−tT)b \Delta \left ( t,y \right )=y\cdot r\cdot \left ( 1-\frac{t}{T} \right )^b 其中，rr是[0,1]\left [ 0,1 \right ]上的一个随机数，TT表示最大演化代数。bb是确定非均匀度的一个参数，通常取2∼52\sim 5。 控制参数的设定控制参数主要包括种群的规模NN，演化代数TT，杂交概率pcp_c，变异概率pmp_m等等。 在实现遗传算法时，一个常用的方法是将到当前代为止演化的最好个体单独存放起来，在遗传算法结束后，将演化过程中发现的最好个体作为问题的最优解或近似最优解。 求解优化问题的实例问题描述minf(x1,x2,⋯,xn)=−20⋅exp⎛⎝−0.21n∑i=1nx2i−−−−−−−√⎞⎠−exp(1n∑i=1ncos(2π⋅xi))+20+e min\; f\left ( x_1,x_2,\cdots ,x_n \right )=-20\cdot exp\left ( -0.2\sqrt{\frac{1}{n}\sum_{i=1}^{n}x^2_i} \right )-exp\left ( \frac{1}{n}\sum_{i=1}^{n}cos\left ( 2\pi \cdot x_i \right ) \right )+20+e 其中， −30≤xi≤30,i=1,2,⋯,n;e=2.71828 -30\leq x_i\leq 30,i=1,2,\cdots ,n;e=2.71828 问题分析这是一道不带约束条件的函数优化的问题，既可以采用二进制编码方式，也可以采用十进制的编码方式，在本题的解决过程中，采用十进制的编码方式。首先通过Matlab得到的函数图像大致如下，从图像中可以观察到当n=2n=2时，我们可以在(0,0)(0,0)附近取得函数的最小值。
这里写图片描述 算法设计基于以上的分析，当n=2n=2时，以下分别从个体的编码、适应值函数、选择策略、杂交算子、变异算子、参数设置、初始化以及终止条件这八个方面对程序的设计作简要的描述： 个体编码采用实数向量编码，每一个个体是一实数对(x1,x2)\left ( x_1,x_2 \right )。 适应值函数该优化问题是一个极小化问题，可对目标函数作简单变换，同时考虑到在选择策略时选择的是轮盘赌的选择策略，轮盘赌的选择策略有一个要求就是个体的适应值要为正数，因此，可以作如下的变换：F=30−f(x1,x2)F=30-f\left ( x_1,x_2 \right )，这里的3030是取的一个上界。这样，既保证了变换后的适应值函数式中为正，而且我们可以将极小化问题转换成一个极大值问题考虑。 选择策略采用轮盘赌的选择策略，因为在计算适应值时已经作了处理，即适应值始终为正，这样就可以使用轮盘赌的选择策略。轮盘赌的选择策略是一种基于适应值比例的选择策略，适应值越大被选择到下一代的概率也会越大。 杂交算子采用整体算术杂交，即给定两个父体，产生一个随机数，经杂交后得到两个后代个体，v1=(x1,x2)v_1=\left ( x_1,x_2 \right )，v2=(y1,y2)v_2=\left ( y_1,y_2 \right )，产生一个随机数α∈[0,1]\alpha \in \left [ 0,1 \right ]，经杂交后得到两个后代个体：v′1=(αx1+(1−α)y1,αx2+(1−α)y2){v}'_1=\left ( \alpha x_1+\left ( 1-\alpha \right )y_1,\alpha x_2+\left ( 1-\alpha \right )y_2 \right )，v′2=(αy1+(1−α)x1,αy2+(1−α)x2){v}'_2=\left ( \alpha y_1+\left ( 1-\alpha \right )x_1,\alpha y_2+\left ( 1-\alpha \right )x_2 \right )。 变异算子采用非均匀变异，即对于要变异的个体x=(x1,x2)x=\left ( x_1,x_2 \right )，随机产生整数k∈{1,2}k\in \left \{ 1,2 \right \}，例如k=1k=1，然后产生后代x′=(x′1,x2){x}'=\left ( {x}'_1,x_2 \right )，其中 x′1={x1+Δ(t,u1−x1)x1−Δ(t,x1−l1) if Random(2)=0 if Random(2)=1 {x}'_1=\begin{cases} x_1+\Delta \left ( t,u_1-x_1 \right ) & \text{ if } Random(2)= 0\\ x_1-\Delta \left ( t,x_1-l_1 \right ) & \text{ if } Random(2)= 1 \end{cases} 参数设置
初始化在区间内随机初始化种群的个体，并置个体的适应值，适应值之和以及相对适应值比例为00。 终止条件采用代数作为终止条件，当算法运行到指定的最大代数时，程序停止。 实验代码代码语言：javascript 复制 最终结果本文来源：数学中国 |
