遗传算法学习笔记（附MATLAB代码）

原作者: [db:作者] 来自: [db:来源] 收藏邀请

遗传算法
生物在自然环境中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法（Genetic Algorithms，GAs）就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。

基因和染色体
在遗传算法中首先将要解决的问题映射为一个数学问题，所谓的数学建模。那这个问题的一个可行解被称为一条染色体，一个可行解一般由多个元素组成，则每一个元素就被称为染色体上的基因。
例如对函数

[1,2,3] [2,1,3] [3,2,1]均为可行解，即染色体，而1,2,3则为基因。
编码方法
在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接操作，而是对表示可行解的个体编码施加选择、交叉、变异等遗传运算，通过这种遗传操作来达到优化的目的。
二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集{0,1}，它所构成的个体基因是一个二进制编码符号串。
设某一参数的取值范围是[U_min , U_max]用长度为l 的二进制编码符号串来表示该参数，则它总共能够产生 2^l种不同的编码。
000000000……000000 = 0 U_min
000000000……000001 = 1
.
.
.
111111111……111111 =2^l-1 U_max
假设某一个个体的编码是：

则对应的解码公式为：
适应度函数
在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对其生存环境的适应程度。对生存环境适应程度较高的物种将有更多的繁殖机会；而对生存环境适应度较低的物种，其繁殖机会就相对较少，甚至会逐渐灭绝。遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度高的个体找到下一代的概率就较大；而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数（Fitness Function）。
最优化问题可以分为两大类，一类是求目标函数的全局最大值，另一类求目标函数的全局最小值。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能是负数。
对于求目标函数最大值的优化问题，变换方法为：

式中Cmin为一个适当地相对比较小的值。
对于目标函数最小值的优化问题，变换方法为：

式中Cmax为一个适当地相对比较大的值。
选择算子
在生物的遗传和自然进化过程中，对生存环境适应度较高的物种将有更多的机会遗传到下一代；而对生存环境适应程度较低的物种遗传到下一代的机会就相对较少。模仿这个过程，遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较低。
最常用的选择算子是比例选择，也叫作赌盘选择。其基本思想是：各个个体被选中的概率与其适应度大小成正比。由于是随机操作的原因，这种选择方法的选择误差比较大，有时甚至连适应度较高的个体也选择不上。
设群体大小为M，个体i的适应度为Fi，这个体i被选中的概率为Psi为：

适应度越高的个体被选中的概率越大，反之适应度越低的个体被选中的概率也越小。
具体执行过程：
（1）先计算出群体中所有个体的适应度的总合；
（2）其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到下一代群体中的概率；
（3）最后使用模拟赌盘操作（即0到1之间的随机数）来确定各个个体被选中的次数。
交叉算子
在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体，从而产生出新的个体或物种。交配重组是生物遗传和进化过程中的一个主要环节。模仿这个环节，在遗传算法中也使用交叉算子来产生新的个体。
遗传算法中所谓的交叉运算，是指对两个相互配对的染色体按某种方式相互交互其部分基因，从而形成两个新的个体。单点交叉(One-point Crossover)算子是最常用和最基本的交叉操作算子，是指在个体编码中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。
具体执行过程：
（1）对群体的个体进行两两配对；
（2）对每一对相互配对的个体，随机设置交叉点；
（3）对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体，从而产生两个新的个体。
变异算子
在生物的遗传和自然进化过程中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，这样就会导致生物的某些基因发生某种变异，从而产生出新的染色体，表现出新的生物性状。模拟生物遗传和进化过程中的这个变异环节，在遗传算法中引入变异算子来产生新的个体。
遗传算法中的所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。例如，对于二进制编码的个体，其编码字符集为{0,1}，变异操作就是将个体在变异点上的基因取反，即用0替换1或用1替换0。
基本位变异(Simple Mutation)算子是最简单和最基本的变异操作算子，是指对个体编码串中以变异概率pm随机指定的某一位或某几位基因座上的基因值作为变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1；反之，若原有基因值为1，则变异操作将其变为0。
具体执行过程：
（1）对个体的每个基因座，依变异概率pm指定其为变异点；
（2）对每一个指定的变异点，对其基因值做取反运算，或用其他等位基因来代替，从而产生一个新的个体。
遗传算法的运行参数
（1） popsize：群体大小，即群体中所含个体的数量，一般去20~100；
（2） pc：交叉概率，一般取0.4~0.99；
（3） pm：变异概率，一般取0.0001~0.1

使用遗传算法对以下函数进行全局寻优函数

-1<= x <=2

附MATLAB代码

主程序

function main()
 clear;
 clc;
%种群大小
popsize=100;
%二进制编码长度
chromlength=10;
%交叉概率
pc = 0.6;
%变异概率
pm = 0.001;
%初始种群
pop = initpop(popsize,chromlength);

for i = 1:100
    %计算适应度值（函数值）
    objvalue = cal_objvalue(pop);
    fitvalue =  objvalue;
    if fitvalue <= 0
        fitvalue = 0;
    end

    %选择操作
    newpop = selection(pop,fitvalue);
    %交叉操作
    newpop = crossover(newpop,pc);
    %变异操作
    newpop = mutation(newpop,pm);
    %更新种群
    pop = newpop;
    %寻找最优解
    [bestindividual,bestfit] = best(pop,fitvalue);
    x2 = binary2decimal(bestindividual);
    x1 = binary2decimal(newpop);
    y1 = cal_objvalue(newpop);
    if mod(i,10) == 0
        figure;
        fplot('x*sin(10*pi*x)+2',[-1,2]);
        hold on;
        plot(x1,y1,'*');
        title(['迭代次数为n=' num2str(i)]);

    end
end
fprintf('The best X is --->>%5.2f\n',x2);
fprintf('The best Y is --->>%5.2f\n',bestfit);

种群初始化

%初始化种群大小
%输入变量：
%popsize：种群大小
%chromlength：染色体长度-->>转化的二进制长度
%输出变量：
%pop：种群
function pop=initpop(popsize,chromlength)
pop = round(rand(popsize,chromlength)); %随机生成popsize行，chromlength列的0,1矩阵
                                        %即popsize个染色体，每个染色体有chromlength个编码
%rand(3,4)生成3行4列的0-1之间的随机数
% rand(3,4)
% 
% ans =
% 
%     0.8147    0.9134    0.2785    0.9649
%     0.9058    0.6324    0.5469    0.1576
%     0.1270    0.0975    0.9575    0.9706
%round就是四舍五入
% round(rand(3,4))=
% 1 1 0 1
% 1 1 1 0
% 0 0 1 1
%所以返回的种群就是每行是一个个体，列数是染色体长度

二进制转十进制

%二进制转化成十进制函数
%输入变量：
%二进制种群
%输出变量
%十进制数值
function pop2 = binary2decimal(pop)
[px,py]=size(pop);%px = popsize    py = chromlength
for i = 1:py
    pop1(:,i) = 2.^(py-i).*pop(:,i); %对每列进行计算，第一列为2^9*(0或者1)，第二列为2^8*(0或1)
end
%sum(.,2)对行求和，得到列向量
temp = sum(pop1,2);%对行求和，最大值为2^10-1=1023
pop2 = temp*3/1023 - 1; %将值转化为-1到2的范围内

计算函数目标值

%计算函数目标值
%输入变量：二进制数值
%输出变量：目标函数值
function [objvalue] = cal_objvalue(pop)
x = binary2decimal(pop);
%转化二进制数为x变量的变化域范围的数值
%带入染色体值，计算出目标函数值即适应度值
    objvalue = x.*sin(10*pi*x)+2;

选择运算

%选择运算
%输入变量：pop二进制种群，fitvalue：适应度值
%输出变量：newpop选择以后的二进制种群
function [newpop] = selection(pop,fitvalue)
%构造轮盘
[px,py] = size(pop);
totalfit = sum(fitvalue);%将所有适应度值求和相加
p_fitvalue = fitvalue/totalfit;%计算每个适应度值与适应度值和的比

p_fitvalue = cumsum(p_fitvalue);%概率求和排序,和后一个值相加
% cumsum 累积和
% cumsum（A） 返回从大小不为1的A中第一个维度开始的累积和
% 例如 A = [0.1 0.1 0.1 0.2 0.3 0.2]  则返回 [0.1 0.2 0.3 0.5 0.8 1]

ms = sort(rand(px,1));%从小到大排列
%rand(i,j) 返回一个i*j的随机数组，数组元素在0到1之间
%sort(x) 将矩阵x的每列按从小到大排列

fitin = 1;
newin = 1;
while newin<=px
    if(ms(newin)) < p_fitvalue(fitin)
        newpop(newin,:) = pop(fitin,:); %选择大的值
        newin = newin+1;
    else
        fitin = fitin+1;
    end
end

交叉运算

%交叉运算
%输入变量：pop：二进制的父代种群数，pc：交叉的概率
%输出变量：newpop：交叉后的种群数
function [newpop] = crossover(pop,pc)
[px,py] = size(pop);
newpop = ones(size(pop));%生成一个px*py，值全为1的矩阵
for i = 1:2:px-1 %选择相邻的两条染色体进行配对
    if(rand<pc)%判断是否满足交叉概率
        %随机设置一个交叉点
        cpoint = round(rand*py);%round四舍五入
        %在相邻两条染色体之间交叉
        newpop(i,:) = [pop(i,1:cpoint),pop(i+1,cpoint+1:py)];%newpop(i,:)为第i行
        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

变异运算

%变异运算
%输入变量：pop：二进制种群，pm：变异概率
%输出变量：newpop变异以后的种群
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 newpop(i,mpoint) == 0
                newpop(i,mpoint) = 1;
            else newpop(i,mpoint) == 1
                newpop(i,mpoint) = 0;
            end
   else
        newpop(i,:) = pop(i,:);
   end
end

求最优适应度函数

%求最优适应度函数
%输入变量：pop:种群，fitvalue:种群适应度
%输出变量：bestindividual:最佳个体，bestfit:最佳适应度值
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

代码运行结果