资源描述：
《遗传算法补充ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、遗传算法1基本概念2基本遗传算法3遗传算法应用举例4遗传算法的特点与优势5遗传算法中的编码方式讨论1基本概念1.个体与种群●个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。●种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。2.适应度与适应度函数●适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。●适应度函数(fitnessfunction)就是问题中的全体个体与其适应度之间的一个
2、对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。3.染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体染色体9----1001（2，5，6）----0101011104.遗传操作亦称遗传算子(geneticoperator)，就是关于染色体的运算。遗传算法中有三种遗传操作:●选择-复制(selection-reproduction)●交叉(crossover，亦称交换、交配或杂交)●变异(mutation，亦称突变)选择-复制通常做法是：对
3、于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。这里的选择概率P(xi)的计算公式为交叉就是互换两个染色体某些位上的基因。s1′=01000101,s2′=10011011可以看做是原染色体s1和s2的子代染色体。例如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即常用的交叉算子单点交叉双点交叉或多点交叉均匀交叉算术交叉A:1011011100B:0001110011双点交叉A:1011110000B:0001011111A:1011011
4、100B:0001110011单点交叉A:1011011111B:0001110000变异就是改变染色体某个(些)位上的基因。例如,设染色体s=11001101将其第三位上的0变为1,即s=11001101→11101101=s′。s′也可以看做是原染色体s的子代染色体。常用的变异算子基本位变异均匀变异非均匀变异高斯变异A:1010010101基本位变异A:10100101002基本遗传算法遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束算法中的一些控制参数：群体规模popSize，终止进化代数maxGen，交
5、叉概率pc和变异概率pm。群体规模popSize：一般建议为20～100。终止进化代数maxGen：100～1000交叉概率pc：0.4~0.99变异概率pm：0.001～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中随
6、机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1；步6按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；步7按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；3遗传算法举例例4.1利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。y=x231XY分析原问题可转化为在区间［0,31］中搜索
7、能使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)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适
8、应度最高的个体(即31（11111）)出现为止。首先计算种群S1中各个体s1=13(01101),s2=24(11000)s3=8(01
