优化算法——遗传算法

与遗传算法的第一次接触

基本定义

1. 个体(individual)：在遗传学中表示的是基因编码，在优化问题中指的是每一个解。
2. 适应值(fitness)：评价个体好坏的标准，在优化问题中指的是优化函数。
3. 群体(population)： 由个体组成的集合
4. 遗传操作：遗传操作的主要目的是用于在当前的群体中产生新的群体，主要的操作包括：选择(selection)、交叉(crossover)、变异(mutation)。

遗传算法的基本流程

遗传算法过程中的具体操作

参数的编码

遗传算法中的参数编码的方式主要有：1、二进制编码。2、Gray编码。3、实数编码。4、有序编码。

二进制编码

二进制编码是最原始的编码方式，遗传算法最初是在二进制编码的方式下进行运算的。二进制编码也是遗传算法中使用最为直接的运算编码方式。二进制编码是指利用$0$和$1$对问题的解向量进行编码。例如，对于如下的优化问题：
$$maxf\left(x_1,x_2\right)=21.5+x_{1}sin\left(4\pi x_1\right)+x_{2}sin\left(20\pi x_2\right)$$
$$-3.0\le x_1\le 12.1;4.1\le x_2\le 5.8$$
其三维图像如下图所示：

在对这样的优化问题进行二进制编码的过程中，是将问题的可能解编码为二进制位串，例如问题的可能解为实数对$\left(x_1,x_2\right)$，首先必须将$x_1$和$x_2$分别使用二进制位串表示，然后将他们的二进制位串组合在一起。对于每一个变量的二进制位串的长度取决于变量的定义域所要求的精度。

对于上述的优化问题，假设精度为小数点后$4$位，则：
$$\left(12.1-\left(-3.0\right)\right)\times 10000=151000$$
$$2^{17}-1<151000\le 2^{18}-1$$
那么表示变量$x_1$的二进制位串的长度为$l_1=18$。
同理，对于变量$x_2$：
$$\left(5.8-4.1\right)\times 10000=17000$$
$$2^{14}-1<17000\le 2^{15}-1$$
表示变量$x_2$的二进制位串的长度为$l_2-15$。
此时，个体可以表示为：

其中，前$18$位表示的是$x_1$，后$15$位表示的是$x_2$。

Gray编码

这种编码方式在求解优化问题时，本人基本上没做过任何研究。

实数编码

在二进制编码的过程中存在这样的一个问题，即在计算适应值的时候需要将二进制编码转换成十进制的编码进行运算，这样，很显然会想到能否直接使用十进制编码直接进行运算，如上例中的$\left(x_1,x_2\right)$这样的编码方式。

有序编码

有序编码主要使用在TSP问题中，在本文中主要涉及二进制编码和实数编码。

初始群体的设定

在解决了个体的编码问题后，需要解决的问题是如何利用个体表示群体。在上述中，我们知道，群体是个体的集合。假设初始群体的大小为$N=20$。对于二进制编码方式与实数编码方式产生$20$个初始解。如：
$$v_1=\left(010001001011010000111110010100010\right)$$
对应的实数编码的方式则为：
$$v_1=\left(1.052426,5.755330\right)$$
对于二进制编码则是随机初始化$20$组这样的初始解，每组初始解随机初始化$33$位的$0-1$编码。而对于实数编码方式，则是在区间上随机初始化$20$组初始解。

适应度函数的计算

适应度函数的目的是评价个体的好坏，如上面的优化问题中，即为最终的优化目标函数。对于二进制编码，则需要先将二进制编码转换成实数编码，再进行适应值函数的计算，对于实数编码方式，则直接进行适应值函数的计算。

遗传操作设计

遗传操作主要包括：选择(selection)、交叉(crossover)、变异(mutation)，遗传操作的主要目的是从当前的群体中产生新的群体，这样便能使得产生新的更优的个体。

选择(selection)

交叉(crossover)

变异(mutation)

控制参数的设定

控制参数主要包括种群的规模$N$，演化代数$T$，杂交概率$p_c$，变异概率$p_m$等等。

在实现遗传算法时，一个常用的方法是将到当前代为止演化的最好个体单独存放起来，在遗传算法结束后，将演化过程中发现的最好个体作为问题的最优解或近似最优解。

求解优化问题的实例

问题描述

$$minf\left(x_1,x_2,\cdots ,x_n\right)=-20\cdot exp\left(-0.2\sqrt{\frac{1}{n}\sum _{i=1}^n{x}_i^2}\right)-exp\left(\frac{1}{n}\sum _{i=1}^{n}cos\left(2\pi \cdot x_i\right)\right)+20+e$$
其中，$$-30\le x_i\le 30,i=1,2,\cdots ,n;e=2.71828$$

问题分析

这是一道不带约束条件的函数优化的问题，既可以采用二进制编码方式，也可以采用十进制的编码方式，在本题的解决过程中，采用十进制的编码方式。首先通过Matlab得到的函数图像大致如下，从图像中可以观察到当$n=2$时，我们可以在$(0,0)$附近取得函数的最小值。

算法设计

基于以上的分析，当$n=2$时，以下分别从个体的编码、适应值函数、选择策略、杂交算子、变异算子、参数设置、初始化以及终止条件这八个方面对程序的设计作简要的描述：

个体编码

采用实数向量编码，每一个个体是一实数对$\left(x_1,x_2\right)$。

适应值函数

该优化问题是一个极小化问题，可对目标函数作简单变换，同时考虑到在选择策略时选择的是轮盘赌的选择策略，轮盘赌的选择策略有一个要求就是个体的适应值要为正数，因此，可以作如下的变换：$F=30-f\left(x_1,x_2\right)$，这里的$30$是取的一个上界。这样，既保证了变换后的适应值函数式中为正，而且我们可以将极小化问题转换成一个极大值问题考虑。

选择策略

采用轮盘赌的选择策略，因为在计算适应值时已经作了处理，即适应值始终为正，这样就可以使用轮盘赌的选择策略。轮盘赌的选择策略是一种基于适应值比例的选择策略，适应值越大被选择到下一代的概率也会越大。

杂交算子

采用整体算术杂交，即给定两个父体，产生一个随机数，经杂交后得到两个后代个体，$v_1=\left(x_1,x_2\right)$，$v_2=\left(y_1,y_2\right)$，产生一个随机数$\alpha \in \left[0,1\right]$，经杂交后得到两个后代个体：$v_1^{\prime }=\left(\alpha x_1+\left(1-\alpha \right)y_1,\alpha x_2+\left(1-\alpha \right)y_2\right)$，$v_2^{\prime }=\left(\alpha y_1+\left(1-\alpha \right)x_1,\alpha y_2+\left(1-\alpha \right)x_2\right)$。

变异算子

采用非均匀变异，即对于要变异的个体$x=\left(x_1,x_2\right)$，随机产生整数 k ∈ { 1 , 2 } k\in \left \{ 1,2 \right \} k∈{
1,2}，例如$k=1$，然后产生后代$x^{\prime }=\left(x_1^{\prime },x_2\right)$，其中
$$x_1^{\prime }=\{\begin{array}{ll}{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{array}$$

参数设置

• 种群规模$N=100$
• 个体长度$Size=2$
• 演化代数$T=3000$
• 杂交概率$p_c=0.7$
• 变异概率$p_m=0.1$
• 函数上界$Upp=30.0$

初始化

在区间内随机初始化种群的个体，并置个体的适应值，适应值之和以及相对适应值比例为$0$。

终止条件

采用代数作为终止条件，当算法运行到指定的最大代数时，程序停止。

实验代码

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            using namespace std; const int COLONY_SIZE=100; //个体数目 const int Size=2;//个体的长度 const int Generation=3000;//代数 const double OVER=0.7;//杂交的概率 const double MUTATE=0.1;//变异的概率 const double UPPER=30.0;//函数的上界 struct Indival { double code[Size]; double fitness; double cfitness; double rfitness; }Group[COLONY_SIZE]; Indival newGroup[COLONY_SIZE]; Indival bestChrom;//记录最好的个体 int GenNum=0; double random(double, double); void initiate(); void calvalue(); void select(); void crossOver(); void xOver(int,int); void mutate(); double delta(int,double,double,double); void sort(); /*主函数*/ int main() { ofstream output; srand((unsigned)time(NULL)); initiate(); calvalue(); output.open("data.txt"); while(GenNum<=Generation) { GenNum++; select(); crossOver(); mutate(); calvalue(); sort(); if (bestChrom.fitness 
           
             =Group[j-1].cfitness&&p 
             
            
           
          
         
        
      

最终结果

我在这里简单介绍了遗传算法，遗传算法是一个研究较多的算法，还有利用遗传算法求解组合优化问题，带约束的优化问题，还有一些遗传算法的理论知识，如模式定理，积木块假设，在这里就不一一列举了，希望我的博文对你的学习有帮助，也欢迎转载，谢谢，有不到位的地方还请指出。