1.简述

      

遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解（所找到的解是全局最优解）的方法。

参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

 1）种群初始化。我们需要首先通过随机生成的方式来创造一个种群，一般该种群的数量为100~500，这里我们采用二进制将一个染色体(解)编码为基因型。随后用进制转化，将二进制的基因型转化成十进制的表现型。

2）适应度计算(种群评估)。这里我们直接将目标函数值作为个体的适应度。

3）选择(复制)操作。根据种群中个体的适应度大小，通过轮盘赌等方式将适应度高的个体从当前种群中选择出来。其中轮盘赌即是与适应度成正比的概率来确定各个个体遗传到下一代群体中的数量。

      具体步骤如下：

     (1)首先计算出所有个体的适应度总和Σfi。

     (2)其次计算出每个个体的相对适应度大小fi/Σfi，类似于softmax。

     (3)再产生一个0到1之间的随机数，依据随机数出现在上述哪个概率区域内来确定各个个体被选中的次数。

4）交叉(交配)运算。该步骤是遗传算法中产生新的个体的主要操作过程，它用一定的交配概率阈值(pc，一般是0.4到0.99)来控制是否采取单点交叉，多点交叉等方式生成新的交叉个体。

     具体步骤如下：

     (1)先对群体随机配对。

     (2)再随机设定交叉点的位置。

     (3)再互换配对染色体间的部分基因。 

5）变异运算。该步骤是产生新的个体的另一种操作。一般先随机产生变异点，再根据变异概率阈值(pm,一般是0.0001到0.1)将变异点的原有基因取反。

6）终止判断。如果满足条件(迭代次数，一般是200~500)则终止算法，否则返回step2。

                   

我们首先从函数出发，既然是寻找全局最优解，我们可以想象一个多元函数的图像。遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。可以这样想象，这个多维曲面里面有数不清的“山峰”，而这些山峰所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遗传算法不一定要找“最高的山峰”，如果问题的适应度评价越小越好的话，那么全局最优解就是函数的最小值，对应的，遗传算法所要找的就是“最深的谷底”）

                                                     

2.代码

主程序：

%%  遗传算法计算最优解
f = inline('x(1)^4-16*x(1)^2-5*x(1)*x(2)+x(2)^4-16*x(2)^2-5*x(2)','x');
l = [-5 -5]; %下限
u = [5 5]; %上限
x0 = [0 0];
Np = 30; %群体大小
Nb = [12 12]; %代表每个变量的二进制位数
Pc = 0.5;  %交叉概率
Pm = 0.01; %变异概率
eta = 0.8;   %学习率
kmax = 200; %最大迭代次数
[xos,fos]=fminsearch(f,x0)
[xo_gen,fo_gen] = genetic(f,x0,l,u,Np,Nb,Pc,Pm,eta,kmax)

子程序：

function P = gen_encode(X,Nb,l,u)
%将群体X的状态编码为二进制数组P
Np=size(X,1); %群体大小
N = length(Nb); %变量（状态）维数
for n = 1:Np
    b2 = 0;
    for m = 1:N
        b1 = b2+1;
        b2 = b2 + Nb(m);
        Xnm =(2^Nb(m)- 1)*(X(n,m) - l(m))/(u(m) - l(m)); %编码方程
        P(n,b1:b2) = dec2bin(Xnm,Nb(m)); %10进制转换为2进制
    end
end

3.运行结果