智能控制理论及应用 课件 第11章-11.1遗传算法

主要内容11.1遗传算法11.2粒子群优化算法11.1遗传算法11.1.1引言11.1.2基本概念11.1.3遗传算法的具体实现

11.1.4遗传算法的运算流程总结

第11章11.1遗传算法11.1.1引言自适应启发式搜索算法进化算法达尔文的进化论自然选择中的适者生存孟德尔遗传学理论适者生存基因遗传第11章11.1.1引言11.1.1引言遗传算法最早由美国的J.H.Holland教授及其学生于1975年提出直到90年代才流行起来。参考文献：Holland,J.H.(1992)GeneticAlgorithms.ScientificAmerican,267,66-73./10.1038/scientificamerican0792-66第11章11.1.1引言11.1.2基本概念●Population(种群）：它是给定问题所有可能（编码）解决方案的一个子集。Individual（个体）：种群中的一个解。第11章11.1.2基本概念11.1.2基本概念●Chromosomes（染色体）：染色体是给定问题的这样一个解。Gene(基因）：基因是染色体上的一个特定位置。第11章11.1.2基本概念11.1.2基本概念●Fitnessfunction(适应度函数)适应度即生物群体中个体适应生存环境的能力。在遗传算法中，用来评价个体优劣的数学函数，称为个体的适应度函数。第11章11.1.2基本概念●GeneticOperators(遗传操作)包含选择、交叉、变异三个主要的操作。第11章11.1.2基本概念11.1.2基本概念适应度比例选择：

p(xi)：选择概率选择与复制对于一个包含N个个体的种群s，从s中随机选择N个染色体N次，每次选择的概率为每个染色体

xi∈s的选择概率p(xi)。第11章11.1.2基本概念交叉交换两个父代的部分基因

二进制编码交叉单点交叉两点交叉多点交叉均匀交叉

实数编码交叉第11章11.1.2基本概念交叉单点交叉

两点交叉第11章11.1.2基本概念交叉多点交叉均匀交叉第11章11.1.2基本概念变异染色体的随机变化。二进制变异：位翻转

单点变异

多点变异实值变异：用值域内的随机值替换原基因值（随机重置）第11章11.1.2基本概念变异二进制变异：位翻转

单点变异

多点变异第11章11.1.2基本概念使用遗传算法来求函数y=x2在区间[0,31]上的最大值。y=x2

31

XY11.1.3遗传算法的具体实现第11章11.1.3遗传算法的具体实现解:(1)初始化:确定种群大小:4编码:5位二进制随机生成初始种群:

s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定义适应度函数:f(x)=x2

第11章11.1.3遗传算法的具体实现解:(3)计算当前代的适应度值s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)它们的适应度值分别为

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361第11章11.1.3遗传算法的具体实现解:(4)执行遗传操作选择操作:计算每个个体的选择概率P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361第11章11.1.3遗传算法的具体实现s40.31s20.49s10.14s30.06●roulette-wheel

selection

algorithm赌轮选择法第11章11.1.3遗传算法的具体实现在[0,1]之间随机生成4个随机数，如：

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503染色体适应值选择概率累积概率选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001第11章11.1.3遗传算法的具体实现因此，在选择之后，我们得到了以下种群：s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）第11章11.1.3遗传算法的具体实现交叉假设

pc=100%让s1'和s2'成对,s3'和s4'成对。分别交换各自的最后两个基因以获得新的染色体：

s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）第11章11.1.3遗传算法的具体实现变异设置变异概率

pm=0.001。

因此，在种群中只有0.02的基因可能会发生突变。

5×4×0.001=0.02显然0.02<1，因此，在这一轮的变异操作中没有变异发生。第11章11.1.3遗传算法的具体实现从而得到第二代种群S2

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）第11章11.1.3遗传算法的具体实现第二代染色体适应值选择概率累积概率s1=110016250.360.36s2=011001440.080.44s3=110117290.410.85s4=100002560.151.00第11章11.1.3遗传算法的具体实现

假设在这一轮的选择-繁殖操作中，种群S2中的所有4个染色体都被选中s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

交叉：

让s1'和s2',s3'和s4'分别交换它们各自最后三个基因s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

在这轮中没有发生变异第11章11.1.3遗传算法的具体实现第三代种群S3被衍生出来。s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

第11章11.1.3遗传算法的具体实现

第三代染色体适应值选择概率累积概率s1=111007840.440.44s2=01001810.040.48s3=110005760.320.80s4=100113610.201.00第11章11.1.3遗传算法的具体实现假设选择-繁殖后的种群是:

s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）交叉:

让s1'和s2’,s3'和s4'分别交换最后两个基因s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

这轮没有发生变异第11章11.1.3遗传算法的具体实现因此，我们得到了第四代S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）

第11章11.1.3遗传算法的具体实现YYy=x2

8131924

X第一代y=x2

12162527

XY第二代y=x2

9192428

XY第三代y=x2

16242831

X第四代第11章11.1.3遗传算法的具体实现11.1.4

遗传算法的运算流程第11章11.1.4遗传算法的运算流程11.1.4

遗传算法的运算流程第11章11.1.4遗传算法的运算流程11.1.5仿真示例【例11.1】用遗传算法求下列函数的最大值。第11章11.1.5仿真示例MATLAB代码%初始化参数clearall;%清除所有变量closeall;%关闭图形clc;%清屏NP=50;%种群数量L=20;%二进制数串长度Pc=0.8;%交叉率Pm=0.1;%变异率G=50;%最大遗传代数Xs=10;%自变量的上限Xx=0;%自变量的下限f=randi([0,1],NP,L);%随机获得初始种群%%%%%%%%%%%%%%%%%%%%%%%%%遗传算法循环第11章11.1.5仿真示例MATLAB代码%%%%%%%%%%%%将二进制解码为定义域范围内十进制%%%%%%%%%%%%%%fori=1:NPU=f(i,:);m=0;forj=1:Lm=U(j)*2^(j-1)+m;endx(i)=Xx+m*(Xs-Xx)/(2^L-1);Fit(i)=func1(x(i));endmaxFit=max(Fit);%最大值

minFit=min(Fit);%最小值

rr=find(Fit==maxFit);fBest=f(rr(1,1),:);%历代最优个体

xBest=x(rr(1,1));Fit=(Fit-minFit)/(maxFit-minFit);%归一化适应度值第11章11.1.5仿真示例MATLAB代码Fit=(Fit-minFit)/(maxFit-minFit);%归一化适应度值

%%%%%%%%%%%%%%%%%%基于轮盘赌的选择操作%%%%%%%%%%%%%%%%%%%sum_Fit=sum(Fit);fitvalue=Fit./sum_Fit;fitvalue=cumsum(fitvalue);ms=sort(rand(NP,1));fiti=1;newi=1;whilenewi<=NPif(ms(newi))<fitvalue(fiti)nf(newi,:)=f(fiti,:);newi=newi+1;elsefiti=fiti+1;endend第11章11.1.5仿真示例MATLAB代码%%%%%%%%%%%%%%%%%%%%%%基于概率的交叉操作fori=1:2:NPp=rand;ifp<Pcq=randi([0,1],1,L);forj=1:Lifq(j)==1temp=nf(i+1,j);nf(i+1,j)=nf(i,j);nf(i,j)=temp;endendendend第11章11.1.5仿真示例MATLAB代码%%%%%%%%%%%%%%%%%%%基于概率的变异操作i=1;whilei<=round(NP*Pm)h=randi([1,NP],1,1);%随机选取一个需要变异的染色体

forj=1:round(L*Pm)