遗传算法原理及应用二（交叉算子、变异算子与运行参数选择）

声明：本文根据对遗传算法相关资料进行整理所得，所参考出处均在文末进行标注，如有侵权，请联系删除。

算法： 遗传算法 参照书籍： 遗传算法原理及应用（国防工业出版社） 应用问题： 寻优 遗传算法特点： （1）遗传算法以决策变量的编码作为运算对象。 （2）遗传算法直接以目标函数值作为搜索信息。 （3）遗传算法同时使用多个搜索点的搜索信息。 （4）遗传算法使用概率搜索技术。 遗传算法的构成要素： （1）编码方法。 （2）个体适应度评价。 （3）遗传算子：主要包括选择运算、交叉运算、变异运算。 （4）遗传算法运行参数：群体大小 M M M、遗传运算的终止进化代数 T T T、交叉概率 P c P_c Pc​、变异概率 P m P_m Pm​.

\qquad 交叉运算是遗传算法中产生新个体的主要操作过程，他以某一概率相互交换某两个个体之间的部分染色体。 \qquad 操作流程： \qquad （1）对群体进行随机配对。 \qquad （2）选择交叉方式进行交叉操作。 \qquad （3）产生新种群。 \qquad 交叉算子的设计包括以下两方面内容： \qquad （1）如何确定交叉点的位置？ \qquad （2）如何进行部分基因交换？ 单点交叉 \qquad 单点交叉又称简单交叉，指在编码个体中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。 \qquad 例： 1 0 1 0 ⋮ 1 1 → 1 0 1 0 ⋮ 0 1 1 1 1 0 ⋮ 0 1 → 1 1 1 0 ⋮ 1 1 1\quad0\quad1\quad0\quad\vdots\quad 1\quad1\quad\rightarrow1\quad0\quad1\quad0\quad\vdots\quad0\quad1\\ 1\quad1\quad1\quad0\quad\vdots \quad0\quad1\quad\rightarrow1\quad1\quad1\quad0\quad\vdots\quad1\quad1 1010⋮11→1010⋮011110⋮01→1110⋮11 \quad 虚线处为交叉点，单点交叉后，产生新个体。 \quad 单点交叉特点：若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度，则这种单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。 双点交叉与多点交叉 \quad 双点交叉是指在个体编码中随机设置了两个交叉点，然后在进行部分基因交换。 \quad 具体过程为： \quad （1）在相互配对的两个个体编码串中随机设置两个交叉点。 \quad （2）交换交叉点之间的部分染色体。 \quad 例： x x x ⋮ x x x ⋮ x x → x x x ⋮ y y y ⋮ x x y y y ⋮ y y y ⋮ y y → y y y ⋮ x x x ⋮ y y x\quad x\quad x\quad\vdots\quad x\quad x\quad x\quad\vdots\quad x\quad x\quad\rightarrow x\quad x\quad x\quad\vdots\quad y\quad y\quad y\quad\vdots\quad x\quad x\quad\\ y\quad y\quad y\quad\vdots\quad y\quad y\quad y\quad\vdots\quad y\quad y\quad\rightarrow y\quad y\quad y\quad\vdots\quad x\quad x\quad x\quad\vdots\quad y\quad y\quad xxx⋮xxx⋮xx→xxx⋮yyy⋮xxyyy⋮yyy⋮yy→yyy⋮xxx⋮yy \quad 虚线处为交叉点，交叉后产生新个体，多点交叉与之类似。 \quad 注：一般不太使用多点交叉算子，其可能破坏良好模式，随着交叉点数的增多，个体结构被破坏的可能性也逐渐增大，很难有效保存较好的模式，从而影响遗传算法的性能。 均匀交叉 \quad 均匀交叉是指两个配对个体的每一个基因都以相同的交叉概率进行交换，从而形成两个新的个体。（实际也属于多点交叉） 操作流程： \quad （1）随机产生一个与个体编码串长度等长的屏蔽字 W = w 1 w 2 w 3 . . . w l W=w_1w_2w_3...w_l W=w1​w2​w3​...wl​其中 l l lw为个体编码串长度。 \quad （2）由 w i w_i wi​的值确定是否进行交换， w i = 0 w_i=0 wi​=0不交换， w i = 1 w_i=1 wi​=1交换。 \quad 例： w = 01010101 x x x x x x x x → x y x y x y x y y y y y y y y y → y x y x y x y x w=01010101\\ x\quad x\quad x\quad x\quad x\quad x\quad x\quad x\quad\rightarrow x\quad y\quad x\quad y\quad x\quad y\quad x\quad y\quad\\ y\quad y\quad y\quad y\quad y\quad y\quad y\quad y\quad\rightarrow y\quad x\quad y\quad x\quad y\quad x\quad y\quad x\quad w=01010101xxxxxxxx→xyxyxyxyyyyyyyyy→yxyxyxyx 算数交叉 \quad 算术交叉是指两个个体的线性组合产生出两个新的个体，为了能够进行线性组合运算，算数交叉的操作对象一般是由浮点数编码所表示的个体。 \quad 设 X A t X_A^{t} XAt​、 X B t X_B^{t} XBt​之间进行算术交叉，则交叉后的两个新个体为： { X A t + 1 = α X B t + ( 1 − α ) X A t X B t + 1 = α X A t + ( 1 − α ) X B t \left\{\begin{array}{l}X_{A}^{t+1}=\alpha X_{B}^{t}+(1-\alpha) X_{A}^{t} \\ X_{B}^{t+1}=\alpha X_{A}^{t}+(1-\alpha) X_{B}^{t}\end{array}\right. {XAt+1​=αXBt​+(1−α)XAt​XBt+1​=αXAt​+(1−α)XBt​​ \quad 式中， α \alpha α为常数时，此时进行的交叉运算称为均匀算术交叉；当 α \alpha α为由进化代数所决定的变量时，此时称为非均匀算术交叉。 \quad 操作过程： （1）确定两个个体进行线性组合时的系数 α \alpha α。 （2）依据上式进行交叉操作产生新个体。

\quad 遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新个体。 \quad 变异算子主要有以下两个目的： \quad （1）改善遗传算法的局部搜索能力。 \quad （2）维持群体的多样性，防止出现早熟现象。 \quad 变异算子的设计包括如下两方面内容： \quad （1）如何确定变异点的位置？ \quad （2）如何进行基因值替换？ 基本位变异 \quad 基本位变异操作是指对个体编码串中以变异概率 P m P_m Pm​随机指定的一个或几个基因座上的基因值作变异运算。 \quad 操作过程： （1）对个体的每一个基因座，以概率 P m P_m Pm​指定其为变异点 （2）对指定变异点进行变异操作。 例： 1 0 1 0 1 1 → 1 0 1 0 0 1 1\quad0\quad1\quad0\quad 1\quad1\quad\rightarrow1\quad0\quad1\quad0\quad0\quad1 101011→101001 \quad 在第五个点进行变异。 均匀变异 \quad 均匀变异操作是指分别用符合某一范围内均匀分布的随机数，以一个较小的概率来替换个体编码串中各个基因座上原有的基因值。 操作过程： （1）依次指定个体编码串中的每个基因座为变异点。 （2）对每一个变异点，以变异概率 P m P_m Pm​从对应基因的取值范围内取一随机数来代替原有基因值。 \quad 设个体为 X = x 1 x 2 x 3 . . . x k . . . x l X=x_1x_2x_3...x_k...x_l X=x1​x2​x3​...xk​...xl​,若 x k x_k xk​为变异点，其取值范围为 [ U m i n k , U m a x k ] [U_{min}^k,U_{max}^k] [Umink​,Umaxk​],在该点对个体 X X X进行均匀变异操作后，可得到一个新的个体 X ′ = x 1 x 2 x 3 . . . x k ′ . . . x l X^{'}=x_1x_2x_3...x_{k}^{'}...x_l X′=x1​x2​x3​...xk′​...xl​,其中变异点的新基因值为： x ′ k = U min ⁡ k + r ⋅ ( U max ⁡ k − U min ⁡ k ) x^{\prime}{ }_{k}=U_{\min }^{k}+r \cdot\left(U_{\max }^{k}-U_{\min }^{k}\right) x′k​=Umink​+r⋅(Umaxk​−Umink​)，式中 r r r为 [ 0 , 1 ] [0,1] [0,1]范围内符合均匀概率分布的一个随机数。 \quad 均匀变异操作特别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内自由移动，从而可以增加群体的多样性，使算法处理更多的模式。

边界变异 \quad 设个体为 X = x 1 x 2 x 3 . . . x k . . . x l X=x_1x_2x_3...x_k...x_l X=x1​x2​x3​...xk​...xl​,在对个体 X X X进行边界变异操作后，可得到一个新的个体 X ′ = x 1 x 2 x 3 . . . x k ′ . . . x l X^{'}=x_1x_2x_3...x_{k}^{'}...x_l X′=x1​x2​x3​...xk′​...xl​,若 x k x_k xk​为变异点，其取值范围为 [ U m i n k , U m a x k ] [U_{min}^k,U_{max}^k] [Umink​,Umaxk​],则新的基因值 x k ′ x_k^{'} xk′​由下式确定： x k ′ = { U min ⁡ k ,  if  random ⁡ ( 0 , 1 ) = 0 U max ⁡ k ,  if   random  ( 0 , 1 ) = 1 x_{k}^{\prime}=\left\{\begin{array}{ll}U_{\min }^{k}, & \text { if } \operatorname {random}(0,1)=0 \\ U_{\max }^{k}, & \text { if } \quad \text { random }(0,1)=1\end{array}\right. xk′​={Umink​,Umaxk​,​ if random(0,1)=0 if  random (0,1)=1​ 当变量的取值范围特别宽，并且无其他约束条件时，边界变异会带来不好的影响，但它特别适用于最优点位于或接近于可行解的边界时的一类问题。 非均匀变异 \quad 均匀变异操作取某一范围内均匀分布的随机数来替换原有基因值，可使得个体在搜索空间内自由移动。但另一方面，他却不便对于某一重点区域进行局部搜索。 \quad 改进方式：采用对原有基因值作一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行运算后，相当于整个解向量在解空间中作了一个轻微的变动。 \quad 在进行由 X = x 1 x 2 x 3 . . . x k . . . x l X=x_1x_2x_3...x_k...x_l X=x1​x2​x3​...xk​...xl​向 X ′ = x 1 x 2 x 3 . . . x k ′ . . . x l X^{'}=x_1x_2x_3...x_{k}^{'}...x_l X′=x1​x2​x3​...xk′​...xl​的非均匀变异操作时，若变异点 x k x_k xk​的取值范围为 [ U m i n k , U m a x k ] [U_{min}^k,U_{max}^k] [Umink​,Umaxk​]，则新的基因值 x k ′ x_k^{'} xk′​由下式确定： x k ′ = { x k + Δ ( t , U max ⁡ k − ν k ) ,  if  random ⁡ ( 0 , 1 ) = 0 x k − Δ ( t , ν k − U min ⁡ k ) ,  if  random ⁡ ( 0 , 1 ) = 1 x_{k}^{\prime}=\left\{\begin{array}{l} x_{k}+\Delta\left(t, U_{\max }^{k}-\nu_{k}\right), \quad \text { if } \operatorname{random}(0,1)=0 \\ x_{k}-\Delta\left(t, \nu_{k}-U_{\min }^{k}\right), \quad \text { if } \quad \operatorname{random}(0,1)=1 \end{array}\right. xk′​={xk​+Δ(t,Umaxk​−νk​), if random(0,1)=0xk​−Δ(t,νk​−Umink​), if random(0,1)=1​ 高斯变异 \quad 高斯变异是改进遗传算法对重点搜索区域的局部搜索性能的另一种变异操作方法。所谓高斯变异操作是指进行变异操作时，用符合均值为 μ \mu μ、方差为 σ 2 \sigma^{2} σ2的正态分布的一个随机数来替换原有基因值。 \quad 由正态分布的特性可知，高斯变异也是重点搜索原个体附近的某个局部区域。高斯变异具体操作过程与均匀变异相类似。

（1）编码串长度 \quad 使用二进制编码来表示个体时，编码长度 l l l的选取与问题所要求的求解精度有关；使用浮点数编码来表示个体时，编码长度 l l l与决策变量的个数 n n n相等；使用符号编码来表示个体时，编码串长度 l l l由问题的编码方式来确定；另外可使用变长度的编码来表示个体。 （2）群体大小 M M M \quad 群体大小 M M M表示群体中所含个体数量。 M M M小，速度快，多样性差，易出现早熟。 M M M大，速度慢，多样性强。 （3）交叉概率 P c P_c Pc​ \quad 交叉概率一般取值 0.4 − 0.99 0.4-0.99 0.4−0.99，取值过大，易破坏种群优良模式，取值小产生新个体的速度较慢。可采用自适应思想来确定交叉概率 P c P_c Pc​。 （4）变异概率 P m P_m Pm​ \quad 变异概率 P m P_m Pm​取值较大，可产生较多新个体，同时可能会破坏掉很多良好模式，使得遗传算法的性能近似于随机搜索算法的性能。若取值较小，则产生新个体能力和抑制早熟现象的能力会较差。可采用自适应的策略来确定变异概率 （5）终止迭代数 T T T \quad 迭代终止条件 \quad 常用终止条件： \quad （1）连续几代个体平均适应度的差异小于某一个极小的阈值； \quad （2）群体中所有个体适应度的方差小于某一极小的阈值。 （6）代沟 G G G \quad 代沟 G G G是表示各代群体之间个体重叠程度的一个参数，它表示每一代群体中被替换掉的个体在全部个体中所占的百分率，即每一代群体中有 ( M ∗ G ) (M*G) (M∗G)个个体被替换掉。

\quad 在实际应用中，优化问题一般含有一定的约束条件，在遗传算法的应用中，必须对这些约束条件进行处理。 \quad 处理约束条件的常用的三种方法：搜索空间限定法、可行解变换法、惩罚函数法。 （1）搜索空间限定法 \quad 基本思想：对搜索空间的大小进行限制。 \quad 注意事项：要保证经过交叉、变异、等遗传算子的作用之后所产生的新个体在解空间中也要有确定的对应解。 \quad 处理约束条件方法： \quad 一、编码方式限制。 \quad 二、用程序保证直到产生解空间中有对应的可行解的染色体之前，一直进行交叉运算和变异运算。 （2）可行解变换法 \quad 基本思想：寻找基因型和个体表现型之间的多对一的变换关系。 通俗理解：当出现解空间外的个体时，通过一定的变换映射到解空间内。 （3）罚函数法 \quad 基本思想：对解空间中无对应可行解的个体，计算其适应度时，处以一个罚函数，从而降低该个体适应度，使该个体被遗传到下一代群体中的机会减少。

参考书籍：遗传算法原理及应用（国防工业出版社）