写在最前

本栏参考《智能优化算法及其MATLAB实例（第二版）》包子阳 余继周 杨彬 编著

4.1 遗传算法

4.1.1遗传算法的基本概念

简单而言，遗传算法使用群体搜索技术，将种群代表一组解，通过对当前种群施加选择、交叉和变异等一系列遗传操作来产生新一代种群。并逐步使种群进化到包含近似最优解的状态。

遗传算法中的术语有一般如下：
群体和个体-----群体是生物进化过程中的一个集团，表示可行解集。个体是组成群体的单个生物体，表示可行解。
染色体和基因-----染色体是包含生物体所有遗传信息的化合物，表示可行解的编码。基因是控制生物体某种性状(即遗传信息)的基本单位，表示可行解编码的分量。
遗传编码-----遗传编码将优化变量转化为基因的组合表示形式，优化变量的编码机制有二进制编码，十进制编码等等。

适应度-----即生物群体中个体适应生存环境的能力。在遗传算法中，用来评价个体优劣的数学函数，称为个体的适应度函数。遗传算法在进化搜索中基本上不用外部信息，仅以适应度函数为依据。它的目标函数不受连续可微的约束，且定义城可以为任意集合。对适应度函数的唯一要求是，针对输入可计算出能进行比较的结果。这特点使得遗传算法应用范围很广。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数评估是选择操作的依据，适应度函数设计直接影响到遗传算法的性能。常见的适应度函数构造方法主要有：目标函数映射成适应度函数，基于序的适应度函数等。

4.1.2 遗传算法的操作和流程

遗传算法中最优解的搜索过程也模仿生物的遗传进化的过程，使用所谓的遗传算子来实现，即选择算子、交叉算子和变异算子。

（1）选择算子：根据个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些代良的个体遗传到作代群体P(1+t)中。
其中“轮盘赌”选择法是遗传算法中最早提出的种选择方法。它是一种基于比例的选择，利用各个个体适应度所占比例的大小来决定其子孙保留的可能性。若某个个体i的适应度为fi，种群大小为NP,则它被选取的概率表示为pi=fi/(f1+f2+f3+…+fNP)。个体适应度越大，则其被选择的机会也越大，反之亦然。

（2）交叉算子：将群体P(t)中选中的各个个体随机搭配，对每一对个体。以某一概率(交叉概率Pc)交换它们之间的部分染色体。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉操作一般分为以下几个步骤：首先，从交配池中随机取出要交配的一对个体；然后，根据位串长度L，对要交配的一对个体，随机选取[1,L-1]中的一个或多个整数k作为交叉位置；最后，根据交叉概率Pc实施交叉操作，配对个体在交叉位置处，相互交换各自的部分基因，从而形成新的一对个体。

(3)变异算子：对群体中的每个个体，以某一 概率(交异概率Pm)将某一个或某些基因座上的基因值改变为其他的等位基因值。根据个体编码方式的不同，变异方式有:实值变异、二进制交异。对于二进制的变异，对相应的基因值取反；对于实值的变异，对相应的基因值用取值范围内的其他随机值整代。变异操作的一般步骤为：首先，对种群中所有个体按事先设定的变异概率判断是否进行变异；然后，对进行变异的个体随机选择变异位置进行变异。

遗传算法的运算流程 如图所示。具体步骤如下:

(1)初始化。设置进化代数计数器g=0，设置最大进化代数G，随机生成NP个个体作为初始群体P(0)。

(2)个体评价。计算群体P(t)中各个个体的适应度。

(3)选择运算。将选择算子作用于群体，根据个体的适应度，按照一定的规则或方法，选择一些优良个体遗传到下一代群体。

(4)交叉运算。将交叉算子作用于群体，对选中的成对个体，以某概率交换它们之间的部分染色体，产生新的个体
。
(5)变异运算。将变异算子作用于群体，对选中的个体，以某概率改变某一个或某些基因值为其他的等位基因。群体P(t)经过选择、交叉和变异运算之后得到下一代群体P(t+1)，计算适应度值，并根据适应度值进行排序，准备进行下一次遗传操作。

(6)终止条件判断：如g≤G则g=g+1转到步骤(2)，若g>G则进化过程中所得到的具有最大适应度的个体作为最优解输出，中止计算。

4.1.3遗传算法实例
例如求解y=x+10sin(5x)+7cos(4x)在X=[0,10]上的极大值。

% % % ----------------标准遗传算法求函数极值-------------
% % % -----------------------初始化参数-----------------
clear;clc;
NP=50;L=20;Pc=0.8;Pm=0.1;G=100;Xs=10;Xx=0;              
% % % NP--种群数量;L--二进制数串长度;Pc--交叉率;Pm--变异率
% % % G--最大遗传代数;Xs--上限;Xm--下限

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);  % % 20位的二进制范围映射回[Xm,Xs]区间，也是个体对应X轴的值
        Fit(i)= x(i)+10*sin(5*x(i))+7*cos(4*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);  % %归一化适应度值，减去最小除以值域，所有值在0,1之间表示大小
    sum_Fit=sum(Fit);
    fitvalue=Fit./sum_Fit; 
    fitvalue=cumsum(fitvalue);  % % 占比权重顺序求和，最后一个数必为1，表示为适应度集合（1X50)
  
    
% % % -----------------------------遗传操作-------------------------------
    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],L,1); 
            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;  % %最优个体的X坐标
figure
plot(trace)
xlabel('迭代次数')
ylabel('目标函数值')
title('适应度进化曲线')

其中函数曲线和遗传算法迭代曲线为：