赞
踩
遗传算法是通过模拟自然界中生物的遗传进化过程,对优化问题的最优解进行搜索。算法维护一个代表问题潜在解的群体,对于群体的进化,算法引入了类似自然进化中选择、交配以及变异等算子。
遗传算法搜索全局最优解的过程是一个不断迭代的过程(每一次迭代相当于生物进化中的一次循环),直到满足算法的终止条件为止。
在利用遗传算法求解问题时,问题的每一个可能解都被编码成一个“染色体”,即个体,若干个个体构成了群体(所有可能解)。在遗传算法开始时,总是随机的产生一些个体(即初始解),根据预定的目标函数对每一个个体进行评估,给出一个适应度值,基于此适应度值,选择一些个体用来产生下一代,选择操作体现了“适者生存”的原理,“好”的个体被用来产生下一代,“坏”的个体则被淘汰,然后选择出来的个体,经过交叉和变异算子进行再组合生成新的一代,这一代的个体由于继承了上一代的一些优良性状,因而在性能上要优于上一代,这样逐步朝着最优解的方向进化。
遗传算法的基本思想是从初始种群出发,采用优胜劣汰、 适者生存的自然法则选择个体,并通过杂交、变异来产生新 一代种群,如此逐代进化,直到满足目标为止。
遗传算法所 涉及到的基本概念主要有以下几个:
• 种群(Population):种群是指用遗传算法求解问题时, 初始给定的多个解的集合。遗传算法的求解过程是从这个子 集开始的。
•个体(Individual):个体是指种群中的单个元素,它通常 由一个用于描述其基本遗传结构的数据结构来表示。例如, 可以用0、1组成的长度为l的串来表示个体。
• 染色体(Chromosome):染色体是指对个体进行编码后 所得到的编码串。染色体中的每1位称为基因,染色体上由 若干个基因构成的一个有效信息段称为基因组。
• 适应度(Fitness)函数:适应度函数是一种用来对种群中 各个个体的环境适应性进行度量的函数。其函数值是遗传 算法实现优胜劣汰的主要依据 • 遗传操作(Genetic Operator):遗传操作是指作用于种 群而产生新的种群的操作。标准的遗传操作包括以下3种基本形式:
– 选择(Selection)
– 杂交(Crosssover)
– 变异(Mutation)
遗传算法的基本步骤:
Step1. 初始化规模为N的群体,其中染色体每个基因的值采用随机数产生器生成并满足问题定义的范围。当前进化代数Generation=0。
Step2. 采用评估函数对群体中所有染色体进行评价,分别计算每个染色体的适应值,保存适应值最大的染色体Best。
Step3. 采用轮盘赌选择算法对群体的染色体进行选择操作,产生规模同样为N的种群。
Step4. 按照概率Pc从种群中选择染色体进行交配。每两个进行交配的父代染色体,交换部分基因,产生两个新的子代染色体,子代染色体取代父代染色体进入新种群。没有进行交配的染色体直接复制进人新种群。
Step5. 按照概率 Pm对新种群中染色体的基因进行变异操作。发生变异的基因数值发生改变。变异后的染色体取代原有染色体进人新群体,未发生变异的染色体直接进人新群体。
Step6. 变异后的新群体取代原有群体,重新计算群体中各个染色体的适应值。倘若群体的最大适应值大于Best 的适应值,则以该最大适应值对应的染色体替代Best。
Step7. 当前进入代数Generation加1.如果Generation超过规定的最大进化代数或Best达到规定的误差要求,算法结束。否则返回Step3.
遗传算法流程图:
遗传算法伪代码:
/* P(t)表示某一代的群体,t为当前进化代数 Best表示目前已找到的最优解 */ Procedure GA begin t←0; initialize(P(t)); evaluate(P(t)); keep_best(P(t)); while(不满足终止条件) do begin P(t)←selection(P(t)); P(t)←crossover(P(t)); P(t)←mutation(P(t)); t←t+1; P(t)←P(t-1); evaluate(P(t)); if (P(t)的最优适应值大于Best的适应值) //以P(t)的最优染色体替代Best replace(Best); end if end end
GA:
clc;clear all; format long;%设定数据显示格式 %初始化参数 T=500;%仿真代数 N=80;% 群体规模 pm=0.05;pc=0.8;%交叉变异概率 umax=30;umin=-30;%参数取值范围 L=10;%单个参数字串长度,总编码长度Dim*L Dim=2;%Dim维空间搜索 bval=round(rand(N,Dim*L));%初始种群,round函数为四舍五入 bestv=-inf;%最优适应度初值 funlabel=1; %选择待优化的函数,1为Rastrigin,2为Schaffer,3为Griewank Drawfunc(funlabel);%画出待优化的函数,只画出二维情况作为可视化输出 %迭代开始 tic; for ii=1:T %解码,计算适应度 for i=1:N %对每一代的第i个粒子 for k=1:Dim y(k)=0; for j=1:1:L %从1到L,每次加以1 y(k)=y(k)+bval(i,k*L-j+1)*2^(j-1);%把第i个粒子转化为十进制的值,例如y1是第一维 end x(k)=(umax-umin)*y(k)/(2^L-1)+umin;%转化为实际的x1 end % obj(i)=100*(x1*x1-x2).^2+(1-x1).^2; %目标函数 obj(i)=fun(x,funlabel); xx(i,:)=x; end func=obj;%目标函数转换为适应度函数 p=func./sum(func); q=cumsum(p);%累加 [fmax,indmax]=max(func);%求当代最佳个体 if fmax>=bestv bestv=fmax;%到目前为止最优适应度值 bvalxx=bval(indmax,:);%到目前为止最佳位串 optxx=xx(indmax,:);%到目前为止最优参数 end Bfit1(ii)=bestv; % 存储每代的最优适应度 %%%%遗传操作开始 %轮盘赌选择 for i=1:(N-1) r=rand; tmp=find(r<=q); newbval(i,:)=bval(tmp(1),:); end newbval(N,:)=bvalxx;%最优保留 bval=newbval; %单点交叉 for i=1:2:(N-1) cc=rand; if cc<pc point=ceil(rand*(2*L-1));%取得一个1到2L-1的整数 ch=bval(i,:); bval(i,point+1:2*L)=bval(i+1,point+1:2*L); bval(i+1,point+1:2*L)=ch(1,point+1:2*L); end end bval(N,:)=bvalxx;%最优保留 %位点变异 mm=rand(N,Dim*L)<pm;%N行 mm(N,:)=zeros(1,Dim*L);%最后一行是精英不变异,强制赋0 bval(mm)=1-bval(mm); end fprintf('当目标函数的解空间维度为Dim= %d 且群体规模为N= %d 时所消耗的时间资源为:',Dim,N); toc; %输出 figure; plot(-Bfit1);% 绘制最优适应度进化曲线 bestv %输出最优适应度值 optxx %输出最优参数
计算粒子适应度值的函数fun():
function y = fun(x,label)
%函数用于计算粒子适应度值
%x input 输入粒子
%y output 粒子适应度值
if label==1
y=-Rastrigin(x);
elseif label==2
y=-Schaffer(x);
elseif label==3
y=-Griewank(x);
else
y=-Ackley(x);
end
绘制函数图像函数Drawfunc():
function Drawfunc(label) x=-5:0.05:5;%41列的向量 if label==1 y = x; [X,Y] = meshgrid(x,y); [row,col] = size(X); for l = 1 :col for h = 1 :row z(h,l) = Rastrigin([X(h,l),Y(h,l)]); end end surf(X,Y,z); shading interp xlabel('x1-axis'),ylabel('x2-axis'),zlabel('f-axis'); title('mesh'); end if label==2 y = x; [X,Y] = meshgrid(x,y); [row,col] = size(X); for l = 1 :col for h = 1 :row z(h,l) = Schaffer([X(h,l),Y(h,l)]); end end surf(X,Y,z); shading interp xlabel('x1-axis'),ylabel('x2-axis'),zlabel('f-axis'); title('mesh'); end if label==3 y = x; [X,Y] = meshgrid(x,y); [row,col] = size(X); for l = 1 :col for h = 1 :row z(h,l) = Griewank([X(h,l),Y(h,l)]); end end surf(X,Y,z); shading interp xlabel('x1-axis'),ylabel('x2-axis'),zlabel('f-axis'); title('mesh'); end if label==4 y = x; [X,Y] = meshgrid(x,y); [row,col] = size(X); for l = 1 :col for h = 1 :row z(h,l) = Ackley([X(h,l),Y(h,l)]); end end surf(X,Y,z); shading interp xlabel('x1-axis'),ylabel('x2-axis'),zlabel('f-axis'); title('mesh'); end
GRIEWANK FUNCTION 点击可查看Griewank函数的更多信息。
function y=Griewank(x) %Griewan函数 %输入x,给出相应的y值,在x=(0,0,…,0)处有全局极小点0. %编制人: %编制日期: [row,col]=size(x); if row>1 error('输入的参数错误'); end y1=1/4000*sum(x.^2); y2=1; for h=1:col y2=y2*cos(x(h)/sqrt(h)); end y=y1-y2+1; %y=-y;
当目标函数的解空间维度为Dim= 2 且群体规模为N= 80 时所消耗的时间资源为:0.527370 秒。
输出最优适应度值:
bestv =
-0.007424952499097
输出最优参数:
optxx =
-3.137829912023459 -4.428152492668623
>>
当目标函数的解空间维度为Dim= 5 且群体规模为N= 80 时所消耗的时间资源为:0.756145 秒。
输出最优适应度值:
bestv =
-0.270427781527473
输出最优参数:
optxx =
21.906158357771261 8.533724340175951 4.897360703812318 0.557184750733139 0.322580645161292
>>
当目标函数的解空间维度为Dim= 2 且群体规模为N= 20 时所消耗的时间资源为:0.154992 秒。
输出最优适应度值:
bestv =
-0.010262924724034
输出最优参数:
optxx =
3.137829912023463 4.545454545454547
>>
当目标函数的解空间维度为Dim= 5 且群体规模为N= 20 时所消耗的时间资源为:0.201569 秒。
输出最优适应度值:
bestv =
-0.170506022226074
输出最优参数:
optxx =
-6.598240469208211 0.029325513196483 -15.923753665689150 -5.953079178885631 0.029325513196483
>>
对比四种不同参数设置的运行结果可得:
RASTRIGIN FUNCTION 点击可查看Rastrigin函数的更多信息。
function y = Rastrigin(x)
% Rastrigin函数
% 输入x,给出相应的y值,在x = ( 0 , 0 ,…, 0 )处有全局极小点0.
% 编制人:
% 编制日期:
[row,col] = size(x);
if row > 1
error( ' 输入的参数错误 ' );
end
y =sum(x.^2-10*cos(2*pi*x)+10);
%y =-y;
当目标函数的解空间维度为Dim= 2 且群体规模为N= 80 时所消耗的时间资源为: 0.493056 秒。
输出最优适应度值:
bestv =
-1.311359672053284
输出最优参数:
optxx =
0.029325513196483 -0.967741935483872
>>
当目标函数的解空间维度为Dim= 5 且群体规模为N= 80 时所消耗的时间资源为:0.728897 秒。
输出最优适应度值:
bestv =
-1.116636425397291e+02
输出最优参数:
optxx =
7.243401759530791 0.850439882697948 -0.850439882697948 4.956011730205276 0.674486803519063
>>
当目标函数的解空间维度为Dim= 2 且群体规模为N= 20 时所消耗的时间资源为: 0.153193 秒。
输出最优适应度值:
bestv =
-2.741442067565775
输出最优参数:
optxx =
-1.085043988269796 0.029325513196483
>>
当目标函数的解空间维度为Dim= 5 且群体规模为N= 20 时所消耗的时间资源为: 0.206011 秒。
输出最优适应度值:
bestv =
-1.341034172832627e+02
输出最优参数:
optxx =
8.826979472140764 -0.029325513196483 4.076246334310852 1.495601173020528 -3.079178885630498
>>
对比四种不同参数设置的运行结果可得如下结论:
ACKLEY FUNCTION 点击可查看Ackley函数的更多信息。
function result=Ackley(x)
%Ackley 函数
%输入x,给出相应的y值,在x=(0,0,…,0) 处有全局极小点0,为得到最大值,返回值取相反数
%编制人:
%编制日期:
[row,col]=size(x);
if row>1
error('输入的参数错误');
end
result=-20*exp(-0.2*sqrt((1/col)*(sum(x.^2))))-exp((1/col)*sum(cos(2*pi.*x)))+exp(1)+20;
result=-result;
当目标函数的解空间维度为Dim= 2 且群体规模为N= 80 时所消耗的时间资源为:0.546779 秒。
输出最优适应度值:
bestv =
22.289642531756776
输出最优参数:
optxx =
29.472140762463340 -29.472140762463344
>>
当目标函数的解空间维度为Dim= 5 且群体规模为N= 80 时所消耗的时间资源为:时间已过 0.808950 秒。
输出最优适应度值:
bestv =
22.247963558862615
输出最优参数:
optxx =
27.536656891495603 -24.486803519061581 26.480938416422291 -27.478005865102638 29.589442815249264
>>
当目标函数的解空间维度为Dim= 2 且群体规模为N= 20 时所消耗的时间资源为:0.162487 秒。
输出最优适应度值:
bestv =
22.289642531756776
输出最优参数:
optxx =
-29.472140762463344 29.472140762463340
>>
当目标函数的解空间维度为Dim= 5 且群体规模为N= 20 时所消耗的时间资源为: 0.263552 秒。
输出最优适应度值:
bestv =
22.262829111685726
输出最优参数:
optxx =
29.530791788856305 29.472140762463340 20.557184750733136 -29.530791788856305 -28.475073313782993
>>
对比四种不同参数设置的运行结果可得如下结论:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。