kk讲义_遗传算法.ppt

模式识别讲义第7章随机方法,黄可坤嘉应学院,遗传算法,主要内容,0引例：用遗传算法求函数最值1遗传算法的发展2遗传算法的基本思想3遗传算法的具体的步骤3.1编码3.2初始群体生成3.3适应度计算3.4选择3.5交叉3.6变异3.7终止4遗传算法的特点5matlab遗传算法工具箱,0引例：用遗传算法求函数最值,1遗传算法的发展,JohnHolland1975年提出遗传算法。Matlab7.0开始附带遗传算法工具箱，可直接求解各种优化问题。Matlab7.1推出了全新的遗传算法工具箱，可直接求解各种有约束的优化问题。早期的版本(如Matlab6.5)需要下载一个GOAT工具箱。,2遗传算法的基本思想,遗传算法（GeneticAlgorithm）是基于进化论的原理发展起来的一种广为应用，高效的随机搜索与优化的方法。它从一组随机产生的初始解称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，成为“染色体”是一串符号。这些染色体在每一代中用“适应度”来测量染色体的好坏,通过选择、交叉、变异运算形成下一代。选择的原则是适应度越高,被选中的概率越大。适应度越低，被淘汰的概率越大。每一代都保持种群大小是常数。经过若干代之后，算法收敛于最好的染色体，它很可能是问题的最优解或次优解。这一系列过程正好体现了生物界优胜劣汰的自然规律。,3遗传算法的具体的步骤,3.1编码,把所需要选择的特征进行编号，每一个特征就是一个基因，一个解就是一串基因的组合。编码和适应度计算时的解码操作以及交叉和变异算子的设计是需要同时考虑的。编码是最重要的步骤。实数编码：即一个解就是一个实数，没有基因。如引例中求函数的最值，一般采用实数编码，也可使用二进制编码。二进制编码：组合优化问题通常采用二进制编码。如果一个个体（解）的编码是一个全排列（如节点编号53124，作业顺序编号等），则可以化成二进制编码101011001010100，解码时再拆开来，并化成整数从小到大排序。,3.2初始群体(population)的生成,随机产生n个初始串结构数据，每个串结构数据称为一个个体。n个个体，构成了一个群体。GA以这个串结构数据作为初始点开始迭代。这个参数n需要根据问题的规模而确定。对于实数编码，可随机产生n个数。对于二进制编码，也可随机产生。,3.3适应度(fitness)计算,即计算交换产生的新个体的适应度。适应度用来度量种群中个体优劣（符合条件的程度）的指标值。这个判据的选取是GA的关键所在，也是GA唯一需要针对不同问题而需要自行设计的一个步骤，和编码一起考虑。求函数最大值问题，适应度就是函数值。组合优化问题，则需具体问题具体考虑。,3.4选择(selection),选择的目的是为了从交换后的群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是使得适应度高的个体被选的次数比较高，所保留的个体数量和原种群的数量一致。选择实现了达尔文的适者生存原则。选择通常有正态几何分布选择法、轮盘选择法、锦标赛选择法。具体计算公式有点复杂，可以调试matlab的各种选择函数查看所保留的样本。,3.5交换(crossover),交换（也叫杂交）操作是遗传算法中最主要的遗传操作。两个父代通过将相异的部分基因进行交换（如果交换全部相异的就变成了对方而没什么意义），从而产生新的个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。通常交换产生新个体的数量和原种群的个体数量一样，并作为下一次迭代的基础。对于实数编码，可以从两个实数的连线中间随机的产生两个数；也可保留适应度比较高的解，再随机在两个数之间产生一个解。对于二进制编码，可简单交换两个解的若干(具体数量由交换概率控制)相同的位置。这些交换方法matlab都有实现，可调试查看交换效果。,3.6变异(mutation),变异首先在群体中随机选择一定数量个体，对于选中的个体以一定的概率（成为变异概率）随机地改变串结构数据中某个基因的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.0010.01之间。变异为新个体的产生提供了机会。变异在matlab中也有几种方法，可调试matlab的各种变异函数查看所得到的样本。,3.7终止(term),(1)给定一个最大的遗传代数MAXGEN(人为事先确定)，算法迭代在达MAXGEN时停止。(2)给定问题一个下界的计算方法，当进化中达到要求的偏差时，算法终止。(3)当监控得到的算法再进化已无法改进解的性能，即解的适应度无法再提高，此时停止计算。,4遗传算法的特点,遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此操作使得遗传算法可直接对结构对象进行操作。传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。,求解时使用特定问题的信息极少，容易形成通用算法程序。由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数，空间连通、凸性等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，解的定义域可任意混合，故几乎可处理任何问题。选择、交叉和变异都是随机操作，而不是确定的精确规则。这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的覆盖。具有自组织、自适应自学习性。遗传算法利用进化过程获得的信息自行组织，搜索时硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。,5matlab7.0遗传算法工具箱,见”雷英杰-Matlab7.0遗传算法工具箱及应用”,6一般优化方法和遗传算法的对比,求f(x)=x*sin(10*pi*x)+2在(-1,2)时的最小值。ezplot(x*sin(10*pi*x)+2,-1,2);,可用优化工具箱中的fmincon函数进行求解，但需要一个初始值:f=inline(x*sin(10*pi*x)+2);v=;forx0=-1:0.5:2x1,fval=fmincon(f,x0,-1,2);v=v;x1,fval;endv,为了用遗传算法求解，需要建立一个适应度函数文件gafun.m:functiony=gafun(x)ifx2y=1000;elsey=x*sin(10*pi*x)+2;end然后再命令窗口输入：fitnessFunction=gafun;nvars=1;options=gaoptimset(options,PlotFcns,gaplotbestf);options=gaoptimset(options,PopulationSize,30);options=gaoptimset(options,Generations,50);X,FVAL=ga(fitnessFunction,nvars,options),7遗传算法求有约束优化