2016年9月7日星期三

T.s.road 总结笔记

         遗传算法解决全局优化（即为最值点如图中C，D），而局部最优解决的是极值点问题（如图中A，B）

1.       遗传算法流程；

 

%遗传算法的伪代码描述：
%Procedure GA
%Begin
%       T=0;
%       Initialize  p(t) ; //p(t)表示 t代种群
%       Evaluate p(t);  //评估第t代种群
%       While not finished do
%       Begin
%            T=t+1;
%            Select p(t) from p(t-1); //从上代种群众选择较优秀的个体到下代子群
%            Reproduce pairs in p(t);
%            Evaluate p(t);
%       End
%End

 

故遗传算法主要过程及流程图如下

1）编码（适应度函数，产生初始种群）

2）遗传算子（选择、交叉、变异）

3）繁衍种群

2.       参数初始化，编码阶段

假设目标函数为 

a.      定义个体基因，基因是遗传密码，这里自变量就是基因所携带的信息，即用2进制来表示自变量的可能取值。基因序列的长度由自变量取值范围确定。

b.     定义适应度函数，目标函数是，适应度函数就定义为。

c.      由a，b可知，我们定义好了个体（基因）与适应度函数，现初始化种群，定义种群大小，及繁衍代数。

（1）M：种群规模

（2）T：遗传运算的终止进化代数

（3）Pc：交叉概率

（4）Pm：变异概率

%% @authors Keung Charteris & T.s.road CZQ
% @version 1.0 ($Revision$)
% @date 7/9/2016 $LastChangedDate$
% @addr. GUET, Gui Lin, 540001,  P.R.China
% @contact : cztsiang@gmail.com
% @date Copyright(c) 2016-2020,  All rights reserved.
% This is an open access code distributed under theCreative Commons Attribution License, which permits
% unrestricted use, distribution, and reproduction in anymedium, provided the original work is properly cited.functionTestGA0904()clc;  %清除所有
clear all;%清除变量
close all;%关闭图片
format long%  step 1 编写目标函数
FUN =@(x) (x)^2+81*sin(x);%  step 2 生成初始种群，大小为100
initPop={[0, 9],100,10};[BestPop,Trace]=fga(FUN,initPop{1,1}(1),initPop{1,1}(2),initPop{1,2},initPop{1,3});

 

3.       遗传算子

         遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。

a.         轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：

 

%% @authorsKeung Charteris & T.s.road CZQ
% @version1.0 ($Revision$)
% @date6/9/2016 $LastChangedDate$
% @addr.GUET, Gui Lin, 540001,  P.R.China
% @contact :cztsiang@gmail.com
% @dateCopyright(c)  2016-2020,  All rights reserved.
% This is anopen access code distributed under the Creative Commons Attribution License,which permits
%unrestricted use, distribution, and reproduction in any medium, provided theoriginal work is properly cited.%选择操作
%采用基于轮盘赌法的非线性排名选择
%各个体成员按适应值从大到小分配选择概率：
%P(i)=(q/1-(1-q)^n)*(1-q)^i,  其中 P(0)>P(1)>...>P(n), sum(P(i))=1function [selectpop]=NonlinearRankSelect(FUN,pop,bounds,bits)global m n
selectpop=zeros(m,n);
fit=zeros(m,1);
for i=1:mfit(i)=feval(FUN(1,:),(b2f(pop(i,:),bounds,bits)));%以函数值为适应值做排名依据
end
selectprob=fit/sum(fit);%计算各个体相对适应度(0,1)
q=max(selectprob);%选择最优的概率
x=zeros(m,2);
x(:,1)=[m:-1:1]';
[yx(:,2)]=sort(selectprob);
r=q/(1-(1-q)^m);%标准分布基值
newfit(x(:,2))=r*(1-q).^(x(:,1)-1);%生成选择概率
newfit=cumsum(newfit);%计算各选择概率之和
rNums=sort(rand(m,1));
fitIn=1;newIn=1;
while newIn<=mifrNums(newIn)<newfit(fitIn)selectpop(newIn,:)=pop(fitIn,:);newIn=newIn+1;elsefitIn=fitIn+1;end
end

b.        交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。 SGA中交叉算子采用单点交叉算子。

 

%% @authorsKeung Charteris & T.s.road CZQ
% @version1.0 ($Revision$)
% @date6/9/2016 $LastChangedDate$
% @addr.GUET, Gui Lin, 540001,  P.R.China
% @contact :cztsiang@gmail.com
% @dateCopyright(c)  2016-2020,  All rights reserved.
% This is anopen access code distributed under the Creative Commons Attribution License,which permits
%unrestricted use, distribution, and reproduction in any medium, provided theoriginal work is properly cited.%交叉操作function [NewPop]=CrossOver(OldPop,pCross,opts)
%OldPop为父代种群，pcross为交叉概率global m NewPop
r=rand(1,m);
y1=find(r<pCross);
y2=find(r>=pCross);
len=length(y1);
if len>2&&mod(len,2)==1%如果用来进行交叉的染色体的条数为奇数，将其调整为偶数y2(length(y2)+1)=y1(len);y1(len)=[];
endif length(y1)>=2for i=0:2:length(y1)-2ifopts==0[NewPop(y1(i+1),:),NewPop(y1(i+2),:)]=EqualCrossOver(OldPop(y1(i+1),:),OldPop(y1(i+2),:));else[NewPop(y1(i+1),:),NewPop(y1(i+2),:)]=MultiPointCross(OldPop(y1(i+1),:),OldPop(y1(i+2),:));endend    
end
NewPop(y2,:)=OldPop(y2,:);

 

c.         所谓变异运算，是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。 SGA中变异算子采用基本位变异算子。

 

%% @authorsKeung Charteris & T.s.road CZQ
% @version1.0 ($Revision$)
% @date6/9/2016 $LastChangedDate$
% @addr.GUET, Gui Lin, 540001,  P.R.China
% @contact :cztsiang@gmail.com
% @dateCopyright(c)  2016-2020,  All rights reserved.
% This is anopen access code distributed under the Creative Commons Attribution License,which permits
%unrestricted use, distribution, and reproduction in any medium, provided theoriginal work is properly cited.%变异操作
function [NewPop]=Mutation(OldPop,pMutation,VarNum)global m n NewPop
r=rand(1,m);
position=find(r<=pMutation);
len=length(position);
if len>=1fori=1:lenk=unidrnd(n,1,VarNum); %设置变异点数，一般设置1点forj=1:length(k)ifOldPop(position(i),k(j))==1OldPop(position(i),k(j))=0;elseOldPop(position(i),k(j))=1;endendend
end
NewPop=OldPop;

结果如下：