遗传算法

遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，本质是一种高效、并行、全局搜索的方法。

基本概念

编码方式

假设一个具体的问题的解为 $X = (x_1,x_2, \cdots, x_n )$ ，并且每个变量都有取值范围$x_j \in [a_j,b_j]，j=1,2,\cdots,n$.

符号编码： 二进制编码和格雷码编码 统称符号编码。即单个基因无实际意义。有时候整数编码也叫符号编码。

序号编码： 实数编码和整数编码。

以下概念都按照二进制编码给出，其余编码几乎都类似。

染色体

染色体：又称个体或者解（即对应问题的解），解$X$中所有分量按二进制编码并依次排列的二进制串称为染色体。

基因

基因：染色体上的每一个二进制位都称为一个基因.

群体

群体： 选定的一组解，其中解的个数为群体的规模。

选择

选择（又称复制或者选择算子）: 根据各个个体的适应度值，按照一定的规则或者方法从上一代群体中选择出一些优良的个体遗传到下一代群体中。体现了群体中的个体进行优胜劣汰操作。

一般地，选择的优良个体数目 = 种群数目，是从种群中直接选择与种群数目相等的个体生成新种群。若有重复选取的个体则保留。

常见选择算子

交叉

交叉：又称交叉算子，将群体内的各个个体随机搭配成对，对每一对个体，以某个概率（称为交叉概率，预先给定）交换他们之间的部分染色体。

一般地，交叉次数 = 种群数目 $\times$ 交叉概率。 交叉时直接更新种群，直至达到交叉次数则停止交叉。

常见交叉算子：

名称	具体做法	特点	适用编码
单点交叉 （符号编码常用）		标准遗传算法	符号编码
两点(三点)交叉		使用较多	符号编码
均匀交叉		无	符号编码
算术交叉 实数编码常用	算术交叉是指由两个个体的线性组合而产生出两个新的个体。 具体交叉公式如下： $$  \begin{cases} X_A^{t+1} = \alpha XB^{t}+(1-\alpha ) X{A}^{t} \X_B^{t+1} = \alpha XA^{t}+(1-\alpha ) X{B}^{t} \end{cases}$$ 其中$X_A^{t},X_B^{t} $ 第t次进化时要交叉的个体，$X_A^{t+1},X_B^{t+1}$为交叉产生的新个体， $\alpha $ 为一个参数，可以指定为常数，也可以随机产生(常用),也可以根据进化代数所决定。	无	序号编码

变异

变异：又称变异算子，对群体中的每一个个体，以某一概率(称为变异概率，预先给定)改变染色体上的一个或者多个基因。

常用变异算子

**注意： **

1.根据不同问题选择不同的编码方式，选择、交叉、变异对应的算子一般也是不同的。

2. 编码时初始种群时应该检查每个染色体是否符合解的要求（取值范围或者约束条件），

3.种群进行交叉（变异）操作一定要检查交叉（变异）后的染色体是否符合解的要求，若不满足，应该重新进行交叉（变异），直到交叉（变异）成功为止.

基本步骤

(1) 根据实际问题确认参数集

(2)根据参数集进行编码，并且生成初始种群P(1)

(3) 通过种群解码得到对应的参数值，并带入目标函数得到适应值。

(4) 群体经过选择、交叉、变异运算后得到下一代群体。

(5)终止条件判断：若达到迭代次数则停止算法，输出群体中的最有解，否则转到(3)

预先设置的参数

群体大小，一般取20~100

终止进化代数, 一般取100~500

交叉概率, 一般取0.4~0.99

变异概率,一般取0.0001~0.1

具体案例分析

利用遗传算法求以下问题，并精度为小数点后4位。 $$ \max f(x_1,x_2) = 21.5 +x_1sin(4\pi x_1)+x_2sin(20\pi x_2)
s.t. \quad -3.0\le x_1\le 12.1
4.1\le x_2 \le5.8 $$ 具体步骤：

假设种群大小为10 ，终止进化代数为100，交叉概率为0.4，变异概率为0.1

(1) 根据实际问题确认参数集，

​ 该问题的参数集为$X=(x_1,x_2)$,

(2)根据参数集进行编码，并且生成初始种群P(1),

​ 根据其精度要求，利用公式计算出，$x_1，x_2$分别编码成18位、15位二进制串，并生成10个初始种群P(1).

​ 具体算法 :

​ $x_1$ : $17.2042 = \log_2^{(12.1-(-3.0))\cdot10^4+1} \le 15 < \log_2^{(12.1-(-3.0))\cdot10^4}+1 =18.2042$, 故取18

​ $x_2$ : $14.0533=\log_2^{(5.8-4.1)\cdot10^4+1} \le x_2 < \log_2^{(5.8-4.1)\cdot10^4}+1 = 15.0532$,故取15，

所以该问题的染色体长度为33，即所有变量的二进制长度之和。

但为了方便一般变量$x_2$的长度也为18，故染色体长度为 $36=18 \times 变量个数$.

(3) 通过种群解码得到对应的参数值，并带入目标函数得到适应值。

​ 若染色体二进制为111101001110101010'000000010101101010 可解码为$X=(11.446273,4.171908)$.然后在带入目标函数得到适应值，

记住：有10个染色体，对应10个适应度值

(4) 群体经过选择、交叉、变异运算后得到下一代群体。

选择（轮盘赌选择方法）： 把适应度值进行求和归一化当做概率，用累计概率把区间[0,1]划分成10份，然后产生10个随机数，若随机数落入对应的区间内，则选择该染色体，作为下一代种群（有重复的染色体，不用删除，每个染色体独立）。

交叉（单点交叉）：基于选择产生的染色体，也产生10个随机数，如对应的随机数低于交叉概率，则选择用来交叉，交叉点的位置也是随机的。

变异（基本位变异）： 基于交叉产生的染色体，也产生10个随机数，如对应的随机数低于变异概率，则用来变异，变异点的位置也是随机的。

于是新的一代种群产生了。

(5)终止条件判断：若达到迭代次数则停止算法，输出群体中的最有解，否则转到(3)

连续函数求最小值 遗传算法通用代码(二进制编码)

需要用到遗传算法工具箱，需要自己配置

%% 清空所有
clc
clear all
close all
%% 定义目标函数值--用向量的形式定义方便以后调用
%ObjFun = @(x,y)21.5+x.*sin(4*pi.*x)+y.*sin(20*pi.*y);
ObjFun = @(X)-(21.5+X(:,1).*sin(4*pi.*X(:,1))+X(:,2).*sin(20*pi.*X(:,2)));

%% 定义遗传算法初始参数
NIND = 100;  % 个体数目，或者种群大小（Number of individual）
MAXGEN = 500 ;  %最大遗传代数 （Maximum number of generation）
NVAR = 2; % 变量的数目，此处为x1 x2两个变量，所以染色体长度为NVAR * PRECI
PRECI = 18; % 变量的二进制位数（Precision of variable ）若当某个变量长度不一样时，取所有变量中编码最长的那个, 
GGAP = 0.9; % 代沟(Generation gap )，
px = 0.7; % 交叉概率
pm =0.01; % 变异概率

%% 建立区域描述器(Build field descriptor),一种特殊矩阵结构。
% 区域描述器结构FieldD =  [len;lb;ub;code;scale;lbin;ubin]
%  其中 len 表示染色体长度；
%  lb、ub 分别指每个变量使用的下界和上界
% code 指明该二进制串是用的什么编码（0代表格雷编码，1代表二进制编码）,常用二进制编码
% scale是否使用对数刻度（为0表示算术刻度，1代表对数刻度），常用算术刻度
% lbin和ubin 表示是否包含变量的上下边界,0表示不包含，1表示包含 ，
%其中rep函数重复某个元素(or矩阵)扩充为指定维度
FieldD = [rep([PRECI],[1,NVAR]);[-3.0 4];[12.1 5.8];[1,1];[0 0];[1 1];[1 1]];

% 也可以简化为 
%FieldD = [rep([PRECI],[1,NVAR]);rep([-10,15],[1,NVAR]);rep([1;0;1;1]),[1,NVAR]];
% rep([PRECI],[1,NVAR])表示为染色体长度 ---对应参数len；
% rep([-10,15],[1,NVAR]) 所有变量的上下界 ---- 对应参数lb和ub;
% rep([1;0;1;1]),[1,NVAR] 基本的参数

Chrom = crtbp(NIND,NVAR * PRECI);% 随机创建初始种群，行代表一个染色体（即个体），NVAR * PRECI 代表染色体长度，每一个变量的长度为PRECI。

%% 遗传算法优化
gen = 0 ; % 迭代计数器
X = bs2rv(Chrom,FieldD);%初始种群转变为十进制数,即解空间
ObjV = ObjFun(X);%计算初始种群的目标函数值
% 优结果的初始跟踪
%trace = zeros(3,MAXGEN) ;% 由于本题巧好是两个变量，方便画图，可用此种方法代替，3代表比变量数目多1，每一列代表每一代种群的最有解和对应的适应度值（最后一个）,
trace = zeros(2,MAXGEN);%通用方法
while gen <MAXGEN 
    FitnV = ranking(ObjV);  %分配适应度 (Assign fitness values),这里求最小值
    SelCh = select('sus',Chrom,FitnV,GGAP);%选择
    SelCh = recombin('xovsp',SelCh,px);% 交叉
    SelCh = mut(SelCh,pm); %变异
    X = bs2rv(SelCh,FieldD);% 子代个体转变为十进制数
    ObjVSel = ObjFun(X); %子代个体的适应度值计算
    [Chrom,ObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel);%重插入子代到父代，得到新种群
    gen = gen+1;  % 迭代计数器更新
    [Y,I] = min(ObjV);% 获取每代的最有解以及其序号，Y为最优解，I为最有解的个体序号（即种群中所在的行数）
    % 对应设置trace = zeros(3,MAXGEN) ;
    %trace(1:2,gen) = X(I,:); % 记下每一代的最有解，因为有两个变量,gen控 制trace矩阵的列,
    %trace(3,gen) = Y;%记下每一代的最有解对应的适应度值
    trace(1,gen)= Y;%记下每一代的最有解对应的适应度值
    trace(2,gen)= sum(ObjV)/length(ObjV);
end
% 求出最有解
[Y,I] = min(ObjV);
X(I,:)  % 最有解
Y       %对应的最优适应度值

% 画出寻优结果轨迹图
figure(1);
plot(trace(1,:));hold on;
plot(trace(2,:),'-.');grid;
legend('种群均值的变化','解的变化');

%% 画出函数图
figure(2);
lbx = -3.0 ; lux = 12.1;
lby = 4.1 ; luy= 5.8;
ezmesh('21.5+x*sin(4*pi*x)+y*sin(20*pi*y)',[lbx,lux,lby,luy],1000)
hold on;
    

连续函数求最小值 遗传算法通用代码(实数编码)

手写

主函数如下:

%%%%% 不用遗传算法工具箱，手写
%% 清空所有
clc
clear all
close all
%% 定义目标函数值--用向量的形式定义方便以后调用
ObjFun = @(X)-(21.5+X(:,1).*sin(4*pi.*X(:,1))+X(:,2).*sin(20*pi.*X(:,2)));
%% GA 
popsize =100; % 种群规模
lenchrom =3  ;% 变量字符串长度
pc = 0.7;  % 交叉概率
pm = 0.3;% 变异概率
maxgen = 100; %进化次数
% 变量的取值范围
popmax =12;
popmin =-5;
bound = [popmin popmax;popmin popmax;popmin popmax];
%% 产生初始种群
for i = 1:popsize
    GApop(i,:) = Code(lenchrom,bound);%随机产生一个染色体--采用实数编码
    fitness(i) = ObjFun(GApop(i,:));% 计算该染色体的适应度
end
% 找到初始种群中最好的染色体和对应的适应度值，并且设置当前的最好染色体和适应度值为全局最好
gbest = GApop;  %当前种群所有的染色体为个体最佳
fitnessgbest=fitness;% 当前种群中所有染色体的适应度值为个体最佳适应度
[bestfitness,bestindex] = min(fitness);
zbest =GApop(bestindex,:);% 当前最好的染色体为全局最佳染色体
fitnesszbest=bestfitness;% 当前最好的染色体对应的适应度值为全局最佳染色体适应度值
yy(1) = fitnesszbest;  % 存储每一代的最优适应度值
%% 迭代寻优
for i = 1:maxgen
    GApop = Select(GApop,fitness,popsize);% 选择
    GApop=Cross(pc,lenchrom,GApop,popsize,bound);% 交叉操作 GA 
    GApop=Mutation(pm,lenchrom,GApop,popsize,[i maxgen],bound);% 变异操作 GA
    pop=GApop;
    for j = 1:popsize
        fitness(j)= ObjFun(pop(j,:));
        % 个体最有值更新
        if fitness(j)<fitnessgbest(j)
            gbest(j,:) = pop(j,:);
            fitnessgbest(j) = fitness(j);
        end
        % 群体最有值更新
        if fitness(j) <fitnesszbest
            zbest= pop(j,:);
            fitnesszbest = fitness(j);
        end
    end
    yy(i+1) = fitnesszbest;
end
 
%% 输出结果
disp('最优值：')
zbest
disp('最优适应度：')
fitnesszbest

%% 画图 -- 进化次数与适应度之间的关系图（折线图）
figure(1)
plot(yy,'linewidth',2);
title(['适应度曲线' ,'终止代数=',num2str(maxgen)]);
xlabel('进化代数');ylabel('适应度');
grid on ;

染色体编码如下：

function ret = Code(lenchrom,bound)
% 本函数将变量编码成染色体，用于随机初始化一个种群
% lenchrom  input : 染色体长度
% bound     input ： 变量的取值范围
% ret       output : 染色体的编码值
flag = 0 ;
while flag ==0
    pick = rand(1,lenchrom);
    ret = bound(:,1)'+(bound(:,2)-bound(:,1))'.*pick;%线性插值,bound(:,1)表示变量的下界。
    flag = test(lenchrom,bound,ret);%染色体可行性检查
end

染色体可行性检查(若有多的约束自己加，也可以加到目标函数中)

function flag = test(lenchrom,bound,code)
% lenchrom input : 染色体长度
% bound    input : 变量的取值范围
% code  output: 染色体的编码值
% 初始变量 
flag =1;
[n,m] = size(code);
for i = 1:n
    if code(i)<bound(i,1) || code(i)>bound(i,2)
        flag =0;
    end
end

选择算子如下：

function ret=Select(individuals,fitness,sizepop)
% 本函数对每一代种群中的染色体进行选择，以进行后面的交叉和变异 
% individuals input : 种群信息
% fitness input : 适应度
% sizepop input : 种群规模
% ret   output : 经过选择后的种群

sumf = cumsum(fitness./sum(fitness));%累计概率
index = [];
for i = 1:sizepop
    pick = rand ; % 产生随机数
    for j = 1:sizepop
        if pick <= sumf(j)
            index =[index j];
            break;
        end
    end
end

individuals = individuals(index,:);
fitness=fitness(index);
ret = individuals;

交叉算子如下：

function ret=Cross(pcross,lenchrom,chrom,sizepop,bound)
%本函数完成交叉操作
% pcorss                input  : 交叉概率
% lenchrom              input  : 染色体的长度
% chrom                 input  : 染色体群
% sizepop               input  : 种群规模
% ret                   output : 交叉后的染色体

for i=1:sizepop 
    
    % 随机选择两个染色体进行交叉
    pick=rand(1,2);
    while prod(pick)==0 %检查产生的两个随机数是否存在0 
        pick=rand(1,2);
    end
    index=ceil(pick.*sizepop);% ceil  向上取整
    % 交叉概率决定是否进行交叉
    pick=rand;
    while pick==0
        pick=rand;
    end
    if pick>pcross
        continue;
    end
    flag=0;
    while flag==0
        % 随机选择交叉位置
        pick=rand;
        while pick==0
            pick=rand;
        end
        pos=ceil(pick.*sum(lenchrom)); %随机选择进行交叉的位置，即选择第几个变量进行交叉，
        							   % 注意：两个染色体交叉的位置相同
        pick=rand; %交叉开始
        v1=chrom(index(1),pos); 
        v2=chrom(index(2),pos);
        chrom(index(1),pos)=pick*v2+(1-pick)*v1;
        chrom(index(2),pos)=pick*v1+(1-pick)*v2; %交叉结束
        flag1=test(lenchrom,bound,chrom(index(1),:));  %检验染色体1的可行性
        flag2=test(lenchrom,bound,chrom(index(2),:));  %检验染色体2的可行性
        if   flag1*flag2==0
            flag=0;
        else flag=1;
        end    %如果两个染色体不是都可行，则重新交叉
    end
end
ret=chrom;

变异算子如下：

function ret=Mutation(pmutation,lenchrom,chrom,sizepop,pop,bound)
% 本函数完成变异操作
% pcorss                input  : 变异概率
% lenchrom              input  : 染色体长度
% chrom                 input  : 染色体群
% sizepop               input  : 种群规模
% pop                   input  : 当前种群的进化代数和最大的进化代数信息
% ret                   output : 变异后的染色体
%pm,l       enchrom,GApop,popsize,[i maxgen],bound
%pmutation,lenchrom,chrom,sizepop,pop,      bound
%pmutation = pm,lenchrom = lenchrom,chrom= GApop,sizepop=popsize,pop=[1 maxgen]
for i=1:sizepop  
    % 随机选择一个染色体进行变异
    pick=rand;
    while pick==0
        pick=rand;
    end
    index=ceil(pick*sizepop);
    % 变异概率决定该轮循环是否进行变异
    pick=rand;
    if pick>pmutation
        continue;
    end
    flag=0;
    while flag==0
        % 变异位置
        pick=rand;
        while pick==0
            pick=rand;
        end
        pos=ceil(pick*sum(lenchrom));  %随机选择了染色体变异的位置，即选择了第pos个变量进行变异
        v=chrom(i,pos); %选择第i个染色体的第pos位置的基因（即第pos个变量）
        v1=v-bound(pos,1); % 计算该基因距离所处变量下界的长度
        v2=bound(pos,2)-v;% 计算该基因距离所处变量上界的长度
        pick=rand; %变异开始-- 应该用的是高斯变异
        if pick>0.5
            delta=v2*(1-pick^((1-pop(1)/pop(2))^2));
            chrom(i,pos)=v+delta;
        else
            delta=v1*(1-pick^((1-pop(1)/pop(2))^2));
            chrom(i,pos)=v-delta;
        end   %变异结束
        flag=test(lenchrom,bound,chrom(i,:));     %检验染色体的可行性
    end
end
ret=chrom;

算法程序链接（二进制与实数编码）：遗传算法