算法系列——遗传算法_综合

这篇文章是目前为止我写的最认真的一篇博客。主要涉讲解了遗传算法的编程。关于理论基础详见博客推荐第一篇。
遗传算法博客推荐第一篇理解：遗传算法详解GA，适合初学者.

遗传算法博客推荐第二篇编程：遗传算法(Genetic Algorithm)原理详解和matlab代码解析实现及对应gaot工具箱实现代码.

在开始之前推荐先看完上述两篇遗传算法讲解博客，是很厉害的前辈们写的，写的通俗易懂，但是matlab的版本更新，关于遗传算法的工具箱也更新，如果使用里面的函数会出现问题。
第二篇博客中在不调用库的情况下，自己搭建的遗传算法，网上查了其他的写的基本大同小异。但是关于以下几个问题没有详细的解释。

解决以下问题

源程序有一点点的小错误，进行了修正。
关于不同的取值范围和精度要求，如何设定字符串长度，以及一部分进制转换。
在文中对于处理最小值问题只简单的提了一句取导数，实际改写程序中并不是那么简单。

为了方便可读性，这里先展示一遍原始程序，以下程序摘自前文中提到的第二篇博客。

0 主函数

% 下面举例说明遗传算法 %
% 求下列函数的最大值 %
% f(x)=x+10*sin(5x)+7*cos(4x) x∈[0,10] %
% 将 x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为 (10-0)/(2^10-1)≈0.01 
% 将变量域 [0,10] 离散化为二值域 [0,1023], x=0+10*b/1023, 其中 b 是 [0,1023] 中的一个二值数。 %
% %
%--------------------------------------------------------------------------------------------------------------%
%--------------------------------------------------------------------------------------------------------------% 2.0 主程序
%遗传算法主程序
%Name:genmain05.m
%要求精度不大于0.01，
clear
clc
popsize=20;                         %群体大小
chromlength=10;                  %字符串长度(个体长度)
pc=0.6;                                %交叉概率，只有在随机数小于pc时，才会产生交叉
pm=0.001;                           %变异概率pop=initpop(popsize,chromlength);               %随机产生初始群体
for i=1:2000                                                        %20为遗传代数[objvalue]=calobjvalue(pop);                  %计算目标函数fitvalue=calfitvalue(objvalue);                 %计算群体中每个个体的适应度[newpop]=selection(pop,fitvalue);                 %选择[newpop1]=crossover(newpop,pc);               %交叉[newpop2]=mutation(newpop1,pm);               %变异[objvalue]=calobjvalue(newpop2);                 %计算目标函数fitvalue=calfitvalue(objvalue);                       %计算群体中每个个体的适应度[bestindividual,bestfit]=best(newpop2,fitvalue);     %求出群体中适应值最大的个体及其适应值y(i)=bestfit;                                                              %返回的 y 是自适应度值，而非函数值x(i)=decodechrom(bestindividual,1,chromlength)*10/1023;      %将自变量解码成十进制pop=newpop2;
end
fplot('x+10*sin(5*x)+7*cos(4*x)',[0 10])
hold on
plot(x,y,'r*')                                          
hold on[z ,index]=max(y);             %计算最大值及其位置
x5=x(index)                     %计算最大值对应的x值
ymax=z

1.初始化

主函数中调用，生成20个个体，按照精度要求选择染色体的长度
initpop.m

% 2.1初始化(编码)
% initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)，
% 长度大小取决于变量的二进制编码的长度(在本例中取10位)。%初始化
function pop=initpop(popsize,chromlength) 
pop=round(rand(popsize,chromlength)); % rand随机产生每个单元为 {
    0,1} 行数为popsize，列数为chromlength的矩阵，% round对矩阵的每个单元进行圆整四舍五入。这样产生的初始种群。

2 计算目标函数值

calobjvalue.m函数的功能是实现目标函数的计算，其公式采用本文示例仿真，可根据不同优化问题予以修改。

% 2.2.3 计算目标函数值
% calobjvalue.m函数的功能是实现目标函数的计算，其公式采用本文示例仿真，可根据不同优化问题予以修改。
%遗传算法子程序
%Name: calobjvalue.m
%实现目标函数的计算，将 二值域 中的数转化为 变量域的数
function [objvalue]=calobjvalue(pop)
temp1=decodechrom(pop,1,10);   %将pop每行转化成十进制数
x=temp1*10/1023;                         %在精度不大于0.01时，最小整数为1023，即需要10位二进制
objvalue=x+10*sin(5*x)+7*cos(4*x);   %计算目标函数值

decodechrom.m
（主要针对多个变量时候的一条染色体拆分，此处的例子不用拆分，pop1=pop）

% 2.2.2 将二进制编码转化为十进制数(2)
% decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置
% (对于多个变量而言，如有两个变量，采用20为表示，每个变量10位，则第一个变量从1开始，另一个变量从11开始。本例为1)，
% 参数1ength表示所截取的长度（本例为10）。
%遗传算法子程序
%Name: decodechrom.m
%将二进制编码转换成十进制function pop2=decodechrom(pop,spoint,length)          %1  10
pop1=pop(:,spoint:spoint+length-1);
pop2=decodebinary(pop1);                                           %将pop每行转换成十进制值，结果是20*1的矩阵

decodebinary.m


%产生 [2^n 2^(n-1) ... 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的每行之和

3 计算适应度函数

calfitvalue.m

为了计算后续概率，把小于0的目标函数值设为0

% 2.3 计算个体的适应值
%遗传算法子程序
%Name:calfitvalue.m
%计算个体的适应值
function fitvalue=calfitvalue(objvalue)[px,py]=size(objvalue);                   %目标值有正有负
for i=1:pxif objvalue(i)>0                    temp=objvalue(i);          elsetemp=0.0;endfitvalue(i)=temp;
end
fitvalue=fitvalue';

4 选择

轮盘法选择。
原理如下
下面以轮盘赌选择为例给大家讲解一下：

假如有５条染色体，他们的适应度分别为５、８、３、７、２。

那么总的适应度为：F = 5 + 8 + 3 + 7 + 2 = 25。

那么各个个体的被选中的概率为：

α1 = ( 5 / 25 ) * 100% = 20%=0.2

α2 = ( 8 / 25 ) * 100% = 32%=0.32

α3 = ( 3 / 25 ) * 100% = 12%=0.12

α4 = ( 7 / 25 ) * 100% = 28%=0.28

α5 = ( 2 / 25 ) * 100% = 8%=0.08

怎么用代码实现呢？
思想：

把α1-α5，按比例顺序，放到长度为1的一维的线上，开始随机数生成。
理解成向线上随机撒一个点。撒到哪一段就是选择了哪个个体。

eg:
点到0.25时候，处在α1之后，在α2段，所以α2个体被选择一次。
再随机生成0.55，在α3段，所以α3个体被选择一次。

为了便于排序，先把点生成好，按顺序排列，从小到大的进行比较。
即如下代码：

selection.m

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);                       %20*10
ms=sort(rand(px,1));                   %从小到大排列
fitin=1;
newin=1;
while newin<=px                          %选出20个新个体，有重复情况，和上面介绍的方法不太一样if(ms(newin))<fitvalue(fitin)newpop(newin,:)=pop(fitin,:);newin=newin+1;elsefitin=fitin+1;end
end

5 交叉

单点交叉，以0.6的概率对相邻的两个个体染色体随机选择交叉，并随机选择交叉的位置。

crossover.m

% 2.5 交叉
% 交叉(crossover)，群体中的每个个体之间都以一定的概率 pc 交叉，即两个个体从各自字符串的某一位置
% （一般是随机确定）开始互相交换，这类似生物进化过程中的基因分裂与重组。例如，假设2个父代个体x1，x2为：
% x1=0100110
% x2=1010001
% 从每个个体的第3位开始交叉，交又后得到2个新的子代个体y1，y2分别为：
% y1＝0100001
% y2＝1010110
% 这样2个子代个体就分别具有了2个父代个体的某些特征。利用交又我们有可能由父代个体在子代组合成具有更高适合度的个体。
% 事实上交叉是遗传算法区别于其它传统优化方法的主要特点之一。
%遗传算法子程序
%Name: crossover.m
%交叉function [newpop]=crossover(pop,pc)          %pc=0.6
[px,py]=size(pop);
newpop=ones(size(pop));
for i=1:2:px-1                                             %步长为2，是将相邻的两个个体进行交叉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)];elsenewpop(i,:)=pop(i,:);newpop(i+1,:)=pop(i+1,:);end
end

7 求出每一代中最大得适应值及其个体

best.m

% 2.7 求出群体中最大得适应值及其个体
%遗传算法子程序
%Name: best.m
%求出第 t 代群体中适应值最大的值
function [bestindividual,bestfit]=best(pop,fitvalue)
[px,py]=size(pop);
bestindividual=pop(1,:);
bestfit=fitvalue(1);
for i=2:pxif fitvalue(i)>bestfitbestindividual=pop(i,:);bestfit=fitvalue(i);end
end

以下为原始程序结果，看似最后也迭代到了峰值的地方

于是我就把他的改成自己要用的程序，然后发现这里里面存在一些细节不是很对，虽然最后结果是看着蛮对的。

首先我对整套程序进行一下复盘,下面是上传到github的代码，可以和解释一起看。

Genetic-Algorithm-max

主函数:

随机产生初始群体，程序中设置种群大小20，设置字符串长度为10。
遗传算法有4个参数需要提前设定，一般在以下范围内进行设置：
（1）群体大小：20~100
（2）遗传算法的终止进化代数：100~500
（3）交叉概率：0.4~0.99
（4）变异概率：0.0001~0.1
上诉4个参数的设置原因见此博客
设置字符串长度为10：
（1）为什么设置成10：此题是对于0-10的数，要求精度小于0.01，所以至少要能表达1000种可能，在2进制中表达1000种可能的最小位数是10位，10位可以表达1024个数，每个数的大小小于0.01。
（2）其他情况下如何设置：上诉是表示了精度小于某个值，如果要求精度刚好为一个值呢？我想到的一个办法是，仍然需要取到大于精度的所需表达的所有情况，但是在目标函数取值的地方做一个过滤，将范围之外但是2进制能表达的范围，设置成最小值（求最大值的情况下）。
（3）针对上诉描述举个例子会更好，比如题目要求整数，范围在0-20000之间。那么我们肯定要选取15位的二进制，2^15=32768>20000,但是我们每个字符串的长度表示的范围却是0-32768，所以我在目标函数计算的函数中加入一个限制，在0-20000之外的数值就取最小值。
欢迎大家的评论区提出更好的想法。
随机产生初始群体（基因）：initpop.m 简单来说就是先随机产生种群大小*字符串长度的数组，其中数组中每个数为整数。
遗传算法迭代开始
计算目标函数（基因的表现型）：首先每行的二进制都代表一个个体，计算目标函数需要把二进制先转换成十进制，并进行转换，代入目标函数计算目标函数值。
计算个体适应值（个体对环境的适应能力）：这里把小于0的值去掉了，目的是为了下一步自然选择做准备，如果出现小于0的目标值，会导致下一步出现逻辑错误。
计算自然选择后新的群体（自然选择）：先把上一步中计算得到的个体对环境的适应能力fitvalue，进行归一化处理，将使得全部概率之和为1，然后将概率从小到大按顺序排序。然后生成一个群体的随机数，当随机数在属于概率中，则新的群体中对应的数即为原始的个体。（好像表述的不太清楚，简单的来说就是进行选择，随机将高适应能力的个体留下来）。
交叉，变异：这里我也没仔细研究，能用就行，反正就是实现和染色体的交叉变异相似的过程。
对选择交叉变异后的群体重新计算目标函数以及个体适应度，并找出适应度最高的个体，保存对应个体及其适应度。并选择交叉变异后的群体赋值给初始群体，重新再开始遗传。

处理最小值问题：

两种情况：是否目标函数值存在负数。
1、如果不存在负数：可以采用取倒数的操作，实现求最小值

2、如果存在负数：可以采用取反的操作，实现求最小值

不论是取反还是取倒数最后计算最小值时，都记得要取回来。

算法系列——遗传算法