---

进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。

遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体（individual）组成。而每个个体实际上又是染色体（chromosome）带有特征的实体，在一开始需要实现从表现型到基因型的映射即编码工作。

由于仿照基因编码的工作很复杂，往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜略汰的原理，逐代（generation）演化产生出越来越好的近似解。

在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。

这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

---

基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其他搜索算法区分开来。

---

遗传算法中的术语

1. 染色体 chromosome
   染色体又可以称为基因型个体（individuals），一定数量的个体组成了群体（population），群体中个体的数量称为群体大小。

2. 基因 gene
   基因是串中的元素，基因用于表示个体的特征。例如有一个串 $S=1011$，则其中的 $1,0,1,1$ 这 $4$ 个元素分别称为基因。它们的值称为等位基因（alleles）。

3. 基因位点 locus
   基因位点在算法中表示一个基因在串中的位置，称为基因位置（gene position），有时也简称为基因位。基因位置由串的左向右计算，例如在串 $S=1101$ 中，$0$ 的基因位置是 $3$。

4. 特征值 feature
   在用串表示整数时，基因的特征值与二进制数的权一致。例如在串 $S=1011$ 中，基因位置 $3$ 中的 $1$，它的基因特征值为 $2$；基因位置 $1$ 中的 $1$，它的基因特征值为 $8$。

5. 适应度 fitness
   各个个体对环境的适应程度称为适应度。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。这个函数是计算个体在群体中被使用的概率。

---

例题：求函数 $f(x)=9\ast \sin (5x)+8\ast \cos (4x),x\in [0,15]$ 的最大值。

1）初始化（编码）

% 1）初始化
function pop = initpop(popsize, chromlength)
    pop = round(rand(popsize,chromlength));
    % rand 随机产生每个单元为 {0,1}，行数为 popsize，列数为 chromlength 的矩阵，
    % round 对矩阵的每个单元进行圆整。产生初始种群。
end

2）目标函数值

% 2）目标函数值
%（1）二进制数转化为十进制数。
function pop2 = decodebinary(pop)
    [px, py] = size(pop);
    % 求 pop 行和列数
    for i = 1:py
        pop1(:,i) = 2.^(py-i).*pop(:,i);
    end
    pop2 = sum(pop1,2);
    % 求 pop1 的每行之和
end

% 2）目标函数值
%（2）二进制编码转化为十进制数。
function pop2 = decodechrom(pop, spoint,length)
    pop1 = pop(:,spoint:spoint+length-1);
    pop2 = decodebinary(pop1);
end

% 2）目标函数值
%（3）计算目标函数值。
function [objvalue] = calobjvalue(pop)
    temp1 = decodechrom(pop,1,10);              % 将 pop 每行转化成十进制数
    x = temp1 * 15 / 1023;                      % 将二值域中的数转化为变量域的数
    objvalue = 9 * sin(5*x) + 8 * cos(4*x);    % 计算目标函数值
end

3）计算个体的适应值

% 3）计算个体的适应值
function fitvalue = calfitvalue(objvalue)
    global Cmin;
    Cmin = 0;
    [px,py] = size(objvalue);
    for i = 1:px
        if objvalue(i)+Cmin>0
            temp = Cmin + objvalue(i);
        else
            temp = 0.0;
        end
        fitvalue(i) = temp;
    end
    fitvalue = fitvalue'
end

4）选择复制

% 4）选择复制
% 4）选择复制
function [newpop] = selection(pop,fitvalue)
    totalfit = sum(fitvalue);       % 求适应值之和
    fitvalue = fitvalue / totalfit; % 单个个体被选择的概率
    fitvalue = cumsum(fitvalue);    % 累计和，如 fitvalue = [1 2 3 4],则 cumsum(fitvalue) = [1 3 6 10]
    [px, py] = size(pop);
    ms = sort(rand(px,1));          % 从小到大排列
    fitin = 1;
    newin = 1;
    while newin <= px
        if(ms(newin))<fitvalue(fitin)
            newpop(newin) = pop(fitin);
            newin = newin + 1;
        else
            fitin = fitin + 1;
        end
    end
end

5）交叉

% 5）交叉
function [newpop] = crossover(pop,pc)
    [px,py] = size(pop);
    newpop = ones(size(pop));
    for i = 1:2:px-1
        if(rand<pc)
            cpoint = round(rand*py);
            newpop(i,:) = [pop(i,1:cpoint),pop(i+1,cpoint+1:py)];
            newpop(i+1,:) = [pop(i+1,1:cpoint),pop(i,cpoint+1:py)];
        else
            newpop(i,:) = pop(i);
            newpop(i+1,:) = pop(i+1);
        end
    end
end

6）变异

% 6）变异
function [newpop] = mutation(pop,pm)
    [px,py] =  size(pop);
    newpop = ones(size(pop));
    for i=1:px
        if(rand<pm)
            mpoint = round(rand*py);
            if mpoint<=0
                mpoint=1;
            end
            newpop(i) = pop(i);
            if any(newpop(i,mpoint)) == 0
                newpop(i,mpoint) = 1;
            else
                newpop(i,mpoint) = 0;
            end
        else
            newpop(i) = pop(i);
        end
    end
end

7）求出群体中最大适应值及其个体

% 7）求出群体中最大适应值及其个体
function [bestindividual,bestfit] = best(pop, fitvalue)
    [px,py] = size(pop);
    bestindividual = pop(1,:);
    bestfit = fitvalue(1);
    for i = 2:px
        if fitvalue(i)>bestfit
            bestindividual = pop(i,:);
            bestfit = fitvalue(i);
        end
    end
end

主程序

% 8）主程序
clear all
clc
popsize = 15;                                       % 样本数量
chromlength = 10;                                   % 字符串长度（个体长度）
pc = 0.7;                                           % 交叉概率
pm = 0.005;                                         % 变异概率
pop = initpop(popsize, chromlength);                % 随机产生初始群体
pop = [0,0,0,0,0,0,0,0,0,0;
       1,0,0,0,0,0,0,0,0,0;
       1,1,0,0,0,0,0,0,0,0;
       1,1,1,0,0,0,0,0,0,0;
       1,1,1,1,0,0,0,0,0,0;
       1,1,1,1,1,0,0,0,0,0;
       1,1,1,1,1,1,0,0,0,0;
       1,1,1,1,1,1,1,0,0,0;
       1,1,1,1,1,1,1,1,0,0;
       1,1,1,1,1,1,1,1,1,0;
       1,1,1,1,1,1,1,1,1,1;
       1,1,1,1,1,1,1,1,1,0;
       1,1,1,1,1,1,1,1,0,0;
       1,1,1,1,1,1,1,0,0,0;
       1,1,1,1,1,1,0,0,0,0;
       1,1,1,1,1,0,0,0,0,0;
       1,1,1,1,0,0,0,0,0,0;
       1,1,1,0,0,0,0,0,0,0;
       1,1,0,0,0,0,0,0,0,0;
       1,0,0,0,0,0,0,0,0,0;]
for i = 1:1                                            % 20 为迭代次数
    [objvalue] = calobjvalue(pop);                      % 计算目标函数
    fitvalue = calfitvalue(objvalue);                   % 计算群体中每个个体的适应度
    % 三个基本算子
    [newpop] = selection(pop, fitvalue);                % 复制
    [newpop] = crossover(pop, pc);                      % 交叉
    [newpop] = mutation(pop, pm);                       % 变异
    [bestindividual, bestfit] = best(pop, fitvalue);    % 求出群体中适应值最大的个体及其适应值
    y(i) = max(bestfit);
    n(i) = i;
    pop5 = bestindividual;
    x(i) = decodechrom(pop5, 1, chromlength) * 15 / 1023;
    pop = newpop;
end

fplot(@(x)9 * sin(5*x) + 8 * cos(4*x), [0,15])
hold on
plot(x,y,'r *')
hold off

---

利用 GA() 函数

【例题4-3】利用遗传算法求解函数 $f(x,y)=(\cos (x^2+y^2)-0.1)/(1+0.3(x^2+y^2{)}^2)+3$ 的最大值。

首先创建遗传算法的适应度函数

function y = ga43(x)
	y = (cos(x(1)^2 + x(2)^2) - 0.1) / (1 + 0.3*(x(1)^2 + x(2)^2)^2) + 3
end

然后利用遗传算法寻找函数的最大值

[x, fval, exitflag, output, population, scores] = ga(@ga43, 2)

---