遗传算法——通俗讲解，轻松掌握

系列链接

        遗传算法讲解及实例

        差分进化算法讲解及实例

        模拟退火算法讲解及实例

一、定义

        简单来说，遗传算法就是将染色体的一些性质如“选择、交叉、变异”用在了求解的过程中，用于求解复杂方程的数值解，求解的效率较传统算法更高一些。

二、算法思想

        遗传算法就是对当前的一些解概率性的选择留下，或者发生一些交叉和变异，更新为新的解，然后用一个评价函数用来评价解的好坏。而好坏程度则有决定这些解在下一代解中出现的概率，往复迭代，直到满足终止条件。

基因的选择

        我们假设一串数01101代表染色体，每个数字代表一种基因，每一位的0和1代表两种等位基因，所以该染色体数经过选择后依然是01101，也就是生存了下来，遗传给了后一代。

基因的变异

        依旧以01101为例，如果第一位发生了变异，则会变为它的等位基因1，变为11101，这就是染色体中的基因突变。

基因的交叉

        对于两个染色体11011和01101，这两个染色体的前两位发生了交叉，那么两个染色体将变为01011和11101，这就是基因的交叉。

算法精度

        使用一堆二进制的数来代表解，比如用8位二进制的数来代表区间 [0,1] 那么求解精度为1/256≈0.004。

术语

三、算法步骤

                  

初始化

        对于一般的计算问题，随机初始化就足够了

适应度计算

        实际上就是当前解带入目标函数后的函数值，比如你要求最大值，那么将当前解带入后值越大则说明适应度越好

终止条件

        一般是完成了规定的迭代次数

选择操作

        一般选用“轮盘赌”，类似抽奖，一个圆中占得扇形面积最大就最容易中奖，因此适用性越高的约容易留下，详细可参见链接

交叉操作

        确定一个概率，对每一个有P的概率交叉L*P个基因，其中L表示一个染色体中的基因个数

变异操作

        同上，指定一个概率，使一定数量的基因被替换成等位基因

四、练习一下

到目前为止大致思想说完了，还觉得不够清晰？那就以一道题目为例：

        例：求 f(x)=x+10sin(5x)+7cos(4x) 在[0,10]上的最大值

                       

        先把图像画出来如上图所示，这显然是个具有多峰的函数，下面我们使用遗传算法来求解一下，先放求解结果，左图是适应度的迭代过程，看得出来每一代的适应度都在提升，右图中红色的点是求解的最优值，很明显求解的结果是很好的，没有陷入局部最优。

下边我贴出代码，代码参考“智能优化算法及其MATLAB实例”

脚本1 —— 画图

%%%%%%%%%f(x)=x+10sin(5x)+7cos(4x)%%%%%%%%%%
clear all;              %清除所有变量
close all;              %清图
clc;                    %清屏
x=0:0.01:10;
y=x+10*sin(5*x)+7*cos(4*x);
plot(x,y)
xlabel('x')
ylabel('f(x)')
title('f(x)=x+10sin(5x)+7cos(4x)')

脚本2 —— 适应度评价函数

%%%%%%%%%%%%%%%%%%%%%%%%%适应度函数%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function result=func1(x)
fit= x+10*sin(5*x)+7*cos(4*x);
result=fit;

标本3 —— 遗传算法

%%%%%%%%%%%%%%%%%%%%标准遗传算法求函数极值%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%初始化参数%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;              %清除所有变量
close all;              %清图
clc;                    %清屏
NP=50;                  %种群数量
L=20;                   %二进制数串长度
Pc=0.8;                 %交叉率
Pm=0.1;                 %变异率
G=100;                  %最大遗传代数
Xs=10;                  %上限
Xx=0;                   %下限
f=randi([0,1],NP,L);        %随机获得初始种群
%%%%%%%%%%%%%%%%%%%%%%%%%遗传算法循环%%%%%%%%%%%%%%%%%%%%%%%%
for k=1:G
    %%%%%%%%%%%%将二进制解码为定义域范围内十进制%%%%%%%%%%%%%%
    for i=1:NP
        U=f(i,:);
        m=0;
        for j=1:L
            m=U(j)*2^(j-1)+m;
        end
        x(i)=Xx+m*(Xs-Xx)/(2^L-1);
        Fit(i)= func1(x(i));
    end
    maxFit=max(Fit);           %最大值
    minFit=min(Fit);           %最小值
    rr=find(Fit==maxFit);
    fBest=f(rr(1,1),:);        %历代最优个体   
    xBest=x(rr(1,1));
    Fit=(Fit-minFit)/(maxFit-minFit);  %归一化适应度值
    %%%%%%%%%%%%%%%%%%基于轮盘赌的复制操作%%%%%%%%%%%%%%%%%%%
    sum_Fit=sum(Fit);
    fitvalue=Fit./sum_Fit;
    fitvalue=cumsum(fitvalue);
    ms=sort(rand(NP,1));
    fiti=1;
    newi=1;
    while newi<=NP
        if (ms(newi))<fitvalue(fiti)
            nf(newi,:)=f(fiti,:);
            newi=newi+1;
        else
            fiti=fiti+1;
        end
    end   
    %%%%%%%%%%%%%%%%%%%%%%基于概率的交叉操作%%%%%%%%%%%%%%%%%%
    for i=1:2:NP
        p=rand;
        if p<Pc
            q=randi([0,1],1,L);
            for j=1:L
                if q(j)==1;
                    temp=nf(i+1,j);
                    nf(i+1,j)=nf(i,j);
                    nf(i,j)=temp;
                end
            end
        end
    end
    %%%%%%%%%%%%%%%%%%%基于概率的变异操作%%%%%%%%%%%%%%%%%%%%%%%
    i=1;
    while i<=round(NP*Pm)
        h=randi([1,NP],1,1);      %随机选取一个需要变异的染色体
        for j=1:round(L*Pm)         
            g=randi([1,L],1,1);   %随机需要变异的基因数
            nf(h,g)=~nf(h,g);
        end
        i=i+1;
    end
    f=nf;
    f(1,:)=fBest;                   %保留最优个体在新种群中
    trace(k)=maxFit;                %历代最优适应度
end
xBest;                              %最优个体
figure
plot(trace)
xlabel('迭代次数')
ylabel('目标函数值')
title('适应度进化曲线')
 

注：感觉代码还是通俗易懂的，我在参考代码上加了点注释，修改了几个过时函数