预览加载中,请您耐心等待几秒...
1/10
2/10
3/10
4/10
5/10
6/10
7/10
8/10
9/10
10/10

亲,该文档总共45页,到这已经超出免费预览范围,如果喜欢就直接下载吧~

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

第4章基于遗传算法随机优化搜索4.1基本概念1.个体与种群●个体就是模拟生物个体而对问题中对象(普通就是问题解)一个称呼,一个个体也就是搜索空间中一个点。●种群(population)就是模拟生物种群而由若干个体组成群体,它普通是整个搜索空间一个很小子集。2.适应度与适应度函数●适应度(fitness)就是借鉴生物个体对环境适应程度,而对问题中个体对象所设计表征其优劣一个测度。●适应度函数(fitnessfunction)就是问题中全体个体与其适应度之间一个对应关系。它普通是一个实值函数。该函数就是遗传算法中指导搜索评价函数。3.染色体与基因染色体(chromosome)就是问题中个体某种字符串形式编码表示。字符串中字符也就称为基因(gene)。比如:个体染色体9----1001(2,5,6)----0101011104.遗传操作亦称遗传算子(geneticoperator),就是关于染色体运算。遗传算法中有三种遗传操作:●选择-复制(selection-reproduction)●交叉(crossover,亦称交换、交配或杂交)●变异(mutation,亦称突变)选择-复制通常做法是:对于一个规模为N种群S,按每个染色体xi∈S选择概率P(xi)所决定选中机会,分N次从S中随机选定N个染色体,并进行复制。交叉就是交换两个染色体一些位上基因。变异就是改变染色体某个(些)位上基因。比如,设染色体s=11001101将其第三位上0变为1,即s=11001101→11101101=s′。s′也能够看做是原染色体s子代染色体。4.2基本遗传算法算法中一些控制参数:■种群规模■最大换代数■交叉率(crossoverrate)就是参加交叉运算染色体个数占全体染色体总数百分比,记为Pc,取值范围普通为0.4~0.99。■变异率(mutationrate)是指发生变异基因位数所占全体染色体基因总位数百分比,记为Pm,取值范围普通为0.0001~0.1。基本遗传算法步1在搜索空间U上定义一个适应度函数f(x),给定种群规模N,交叉率Pc和变异率Pm,代数T;步2随机产生U中N个个体s1,s2,…,sN,组成初始种群S={s1,s2,…,sN},置代数计数器t=1;步3计算S中每个个体适应度f();步4若终止条件满足,则取S中适应度最大个体作为所求结果,算法结束。步5按选择概率P(xi)所决定选中机会,每次从S中随机选定1个个体并将其染色体复制,共做N次,然后将复制所得N个染色体组成群体S1;步6按交叉率Pc所决定参加交叉染色体数c,从S1中随机确定c个染色体,配对进行交叉操作,并用产生新染色体代替原染色体,得群体S2;步7按变异率Pm所决定变异次数m,从S2中随机确定m个染色体,分别进行变异操作,并用产生新染色体代替原染色体,得群体S3;步8将群体S3作为新一代种群,即用S3代替S,t=t+1,转步3;4.3遗传算法应用举例分析原问题可转化为在区间[0,31]中搜索能使y取最大值点a问题。那么,[0,31]中点x就是个体,函数值f(x)恰好就能够作为x适应度,区间[0,31]就是一个(解)空间。这么,只要能给出个体x适当染色体编码,该问题就能够用遗传算法来处理。解(1)设定种群规模,编码染色体,产生初始种群。将种群规模设定为4;用5位二进制数编码染色体;取以下个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数,取适应度函数:f(x)=x2(3)计算各代种群中各个体适应度,并对其染色体进行遗传操作,直到适应度最高个体(即31(11111))出现为止。首先计算种群S1中各个体s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)适应度f(si)。轻易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361再计算种群S1中各个体选择概率。赌轮选择示意在算法中赌轮选择法可用下面子过程来模拟:①在[0,1]区间内产生一个均匀分布随机数r。②若r≤q1,则染色体x1被选中。③若qk-1<r≤qk(2≤k≤N),则染色体xk被选中。其中qi称为染色体xi(i=1,2,…,n)积累概率,其计算公式为选择-复制于是,经复制得群体:s1’=11000(24),s2’=01101(13)s3’=11000(24),s4’=10011(19)交叉设交叉率pc=100%,即S1中全体染色体都参加交叉运算。设s1’与s2’配对,s3’与s4’配对。分别交换后两位基因,得新染色体:s1’’=11001(25),s2’’=01100(