遗传算法及其MATLAB实现.ppt

遗传算法及其MATLAB实现 41组，顾英辉，魏猛，王艺潞,一、遗传算法的概述,1、产生与发展 2、生物学基础 3、算法的特点及定义 二、遗传算法的原理 1、简单遗传算法 2、简单遗传算法原理 3、遗传算法参数选择 三、遗传算法的流程 1、算法流程图 2、遗传算法举例,四，遗传算法的MATLAB程序设计,1、程序设计流程及参数选取 1.1、遗传算法的程序设计伪代码 1.2、适应度函数调整2、遗传算法工具箱核心函数的用法3、Genetic Algorithm and Direct Search Toolbox适应 度函数设计 五，遗传算法的应用实例1、无约束目标函数最大值遗传算法求解策略2、CUMCM中多约束非线性规划问题的求解,一、遗传算法的概述,1.1、产生与发展1.2、生物学基础 1.3、算法的特点及定义,1.1 产生与发展,产生早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程；1963年，德国柏林技术大学的I.Rechenberg和H.P.Schwefel，做风洞实验时，产生了进化策略的初步思想；60年代，L.J.Fogel在设计有限态自动机时提出进化规划的思想。1966年Fogel等出版了基于模拟进化的人工智能，系统阐述了进化规划的思想。,60年代中期，美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然 和人工系统的自适应行为研究和串编码技术；1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(Genetic Algorithms)”一词；1975年，Holland出版了著名的“Adaptation in Natural and Artificial Systems”，标志遗传算法的诞生,发展 遗传算法进化计算计算智能人工智能,70年代初，Holland提出了“模式定理”（Schema Theorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，International Society of Genetic Algorithms)；1989年，Holland的学生D.J.Goldherg出版了“Genetic Algorithms in Search,Optimization,and Machine Learning”，对遗传算法及其应用作了全面而系统的论述；1991年，L.Davis编辑出版了遗传算法手册，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。,1.2 生物学基础,以自然选择学说为核心的现代生物进化理论，其基本观点是：种群是生物进化的基本单位，生物进化的实质是种群基因频率的改变。基因突变和基因重组、自然选择及隔离是物种形成过程的三个基本环节，通过他们的综合运用，种群产生分化，最终导致新物种的形成。新物种形成的途径和方式有两种：渐变式和爆发式。渐变式主要通过变异的逐渐积累而成亚种，再由亚种形成一个或多个新种，新种又分为两种类型，即继承式新种形成和分化式新种形成；爆发式不通过亚种这一阶段而迅速形成新的物种，其分为三种类型，即杂交产生新种，染色体结构变化形成新种和多倍体化的新种形式。,1.3 遗传算法定义及特点,（1）定义 遗传算法是模拟达尔文生物进化论的自然选择和孟德尔遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。特点（2）特点 遗传算法的并行性。遗传算法并行的方式从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。遗传算法的本质 遗传算法本质上是一种启发式的随机搜索算法，所以由遗传算法得出的结果每次都不尽相同。,二、遗传算法的原理,2.1、简单遗传算法 2.2、简单遗传算法原理 2.3、遗传算法参数选择,2.1 简单遗传算法（SGA),（在此只介绍简单遗传算法SGA）SGA由编解码、个体适应评估和遗传运算三大模块构成，而遗传算法又包括染色体复制、交叉、变异、甚至倒位等。在遗传算法中，定义种群或群体为所有编码后的染色体集合，表征每个个体是相应的染色体。,2.2简单遗传算法原理,编码：遗传算法的编码有浮点编码和二进制编码两种，这里只介绍二进制编码规则。二进制编码既符合计算机处理信息的原理也方便了对染色体进行遗传、编译和突变等操作。例：某一参数的取值范围为（L,U),使用长度为k的二进制编码表示该参数，则他共有 种不同的编码。该参数编码时的对应关系为 0000000000000000000=0L 0000000000000000001=1L+0000000000000000010=2L+2.易知：,解码：解码的目的是为了将不直观的二进制数据串还原成十进制。设某一个体的二进制编码为，则对应的解码公式为例：设有参数x【2,4】，现用5位二进制数对x编码，若x=10101,它对应的十进制为则对应参数x的值为个体适应度评估：遗传算法按照与个体适应度成正比的几率决定当前种群各个个体遗传到下一代群体中的机会。个体适应度大的个体更容易被遗传到下一代。通常求目标函数最大值的问题可以直接把目标函数作为检测个体适应度大小的函数。复制运算：复制运算是根据个体适应度大小决定下代遗传的可能性。若设种群中个体总数为N，个体i的适应度为则个体i被选中的几率当个体复制几率决定后在产生【0,1】区间的均匀随机数来决定那些个个体参加复制，若个体适应度高的被选中的几率就大则可能被多次选中它的遗传基因就会在中群众扩散；若个体的复制几率小则会被淘汰。,交配运算：“交配运算”是使用单点或多点进行交叉的算子，首先用随机数产生一个或多个交配点位置，然后两个个体在交配点位置互换部分基因码形成两个子个体。例：有两条染色体,交换后4位基因得,可以被看成是原染色体 和 的子代染色体。突变运算：“突变运算”是使用基本位进行基因突变为了避免在算法后期出现种群过早收敛，对于二进制的基因码组成的个体种群实行基因码的小几率翻转。即对于二进制编码0变1,1变0例：将染色体S=11001101第3位上的0变为1即S=1100110111101101=。可被看作是原染色体的子代染色体。倒位运算：对一复杂的问题可能需要用到“倒位”。倒位是指一个染色体某区段正常排列顺序发生 的颠倒造成染色体内的DNA序列重新排列，它包括臂内倒位和臂间倒位。例：染色体S=10010110101001划线部分倒位得=10010110101001,2.3遗传算法参数选择,种群规模：既不能过大也不能过小。过大会导致结果难以收敛且浪费资源，稳健型下降；过小会导致种群进化不能按照模式定理产生所预测的期望值。种群规模的一个建议值0100。种群初始化：初始种群的生成是随机的。在初始种群的赋予之前，尽量进行一个大概的区间估计，以免初始种群分布在远离全局最优解的编码空间，导致遗传算法的搜索范围受到限制，同时也为算法减轻负担。交配概率：交配概率过大容易破坏已有的有利模式，随机性增大，容易错失最优个体；过小不能有效更新种群。交配概率一般取值0.40.99。,变异概率：变异概率过小时种群多样性下降太快，容易导致有效基因迅速丢失且不容易修补；过大时，尽管种群的多样性得到保证，但是高阶模式被破坏的概率也随之增大。变异概率一般取0.00010.2。进化代数：进化代数过小，算法不容易收敛，种群还没有成熟；过大，算法已经熟练或者种群过于早熟不可能在收敛，继续进化就没有意义，只会增加时间开支和资源浪费。进化代数一般取100500.,三、遗传算法的流程,3.1、算法流程图 3.2、遗传算法举例,3.1 算法流程图,3.2遗传算法举例例：函数，求其在区间0,31的最大值（1）编码 将变量转换成二进制数串，设要求的精度是1，意味着变量应该被分成至少31个部分，由于 31-0,所以二进制数串位数为5。例如：二进制数01010，对应十进制为10，实际值为：x=0+101=10 假设初始种群有五个个体，其染色体可随机生成如下：,（2）评价个体适应度与新种群复制 对一个染色体数串的适应度的评价由下列三个步骤组成：将染色体串进行反编码（解码），转换成真实值；评价目标函数f(x)；将目标函数值转为适应度。依照染色体的适应度值进行新种群的复制，步骤如下：计算染色体 的适应度值=；计算种群的适应度值总和；计算每个染色体被复制的概率；计算每个染色体被复制的累计概率。,依照轮盘选择法，转动轮盘5次（种群中有五条染色体），每次选择一个作为新种群的染色体。假设五次中产生的01随机数序列如下：0.301431 0.322062 0.766503 0.881893 0.350871根据以上的计算方法，可以先计算出种群中每个染色体的适应度和概率，如下表所示：,第一个随机数为0.301431，大于 小于,所以 被选中；第二个随机数为0.322062，大于 小于,所以 被选中；第三个随机数为0.766503，大于 小于,所以 被选中；第四个随机数为0.881893，大于 小于,所以 被选中；第五个随机数为0.350871，大于 小于,所以 被选中；依照轮盘选择法，新种群的染色体组成如下：=11000()=11000()=11111()=11111()=01000(),（3）新种群交配 交配染色体数量的确定 交配染色体的数量等于染色体总量乘以交配概率。这里假设交配概率P为0.4，染色体总量为5条，所以参加交配的染色体数量为2条，符号 表示取整，这里取整数2条，即交配的染色体数目为2条 交配染色体对象的确立 用计算机产生0,1区间的5个随机数如下：0.567461 0.085940 0.392865 0.770714 0.548656假定其分别对应 这5个个体，则其中低于交配概率0.4的 和 参加交配。这样操作的原因是：交配概率越低，低于交配概率以下的随机数的数量越少，所以参加交配的染色体数量与交配概率可能会成正比。在交配池发生交配 染色体 和 被选中作为交配的父辈，交配点的选择以随机数产生。交配的种类有单点交配和多点交配，这里取单点交配。计算机随机生成一个介于0 4的整数。假设所产生的整数为1，那么两个染色体自1位置（即二进制串的第二位）开始分割，在染色体1位置右端部分开始。,进行交换而生成新的子辈染色体，即=11000=11111=11111=11000（4）基因突变 依照突变运算规则并假设突变几率 为0.1，亦即种群内所有基因都有0.1的概率进行突变。在本例中有55=25个基因，即希望每一代中有2.5个突变基因，每个基因的突变几率是均等的。因此，将产生25个介于0 1之间的随机数，然后将随机数小于0.1的选出，并将其对应的基因值加以翻转，假设25次中产生0 1之间的随机数，其小于0.1者如表所示。,在突变后，最终新种群的染色体组成如下：,至此，已完成遗传算法的第一代流程。依此迭代，在第200代得到对应最大目标函数值的染色体：=11111，相应实际值x=31，适应度值eval（U）=f（31）=961,四，遗传算法的MATLAB程序设计,4.1 程序设计流程及参数选取 4.1.1 遗传算法的程序设计伪代码 4.1.2 适应度函数调整4.2 遗传算法工具箱核心函数的用法4.3 Genetic Algorithm and Direct Search Toolbox适 应度函数设计,4.1程序设计流程及参数选取,4.1.1遗传算法的程序设计伪代码BEGINt=0;%遗传代数初始化P(t);%初始化种群或染色体计算P(t)的适应值；while(不满足停止准则）do begin t=t+1;从P(t-1)中选择P(t);%选择 重组P(t);%交叉和变异 计算P(t)的适应值;endEND,4.1.2适应度函数调整（1）在遗传算法运行的初级阶段 群体中可能会有少数几个个体的适应度相对其他个体来说非常高，若按常用适应度函数进行复制计算，则容易导致遗传算法发生早熟现象（或称早期收敛），使遗传算法 所求的解停留在某一局部最优点上，因此，希望在遗传算法运行的初级阶段，算法能够对一些适应度较高的个体进行控制，降低其适应度与其他个体适应度之间的差异程度，从而限制其复制数量，以维护群体的多样性。（2）在遗传算法运行的后期阶段 群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度，使得进化过程无竞争性可言，只是一种随机的选择过程，这将导致无法对某些重点区域进行重点搜索，从而影响遗传算法的运行效率，因此，希望在遗传算法运行的后期阶段，算法能够对个体的适应度进行适当的放大，扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高个体之间的竞争性。,4.2遗传算法工具箱核心函数的用法(1)函数ga 函数ga语法格式为：x,fval,reason=ga(fitnessfun,nvars,options)其中，x为经过遗传进化以后自变量最佳染色体返回值；fval为最佳染色体的适应度；reason为算法停止原因；fitnessfun为适应度句柄函数；nvars为目标函数自变量个数；options为算法的属性设置，该属性是通过函数gaoptimset赋予的。函数ga实现的功能为对目标函数进行遗传运算。,(2)函数gaoptimset,函数gaoptimset的语法格式为 options=gaoptimset（PropertyName1,PropertyValue1,PropertyName 2,PropertyValue2,PropertyName3,PropertyValue3.)函数gaoptimset实现的功能为设置遗传算法的参数和句柄函数。由于遗传算法本质上是一种启发式的随机运算，算法程序经常重复运行多次才能得到理想结果。鉴于此，可以讲前一次运行得到的最后种群作为下一次运行的初始种群，如此操作会得到更多的结果。例如:x,fval,reason,output,final_pop=ga(fitnessfun,nvars,options);最后一个输出变量final_pop返回的就是本次运行得到的最后种群，再将final_pop作为ga的初始种群，语法格式为 options=gaoptimset（InitialPopulation,final_pop);x,fval,reason,output,final_pop2=ga(fitnessfun,nvars,options);,函数gaoptimset常用的11种属性,4.3Genetic Algorithm and Direct Search Toolbox适应度函数设计,实例1 遗传算法和直接搜索工具箱中的函数ga是求解目标函数的最小值，所以求目标函数最小值的问题，可直接令目标函数为适应度函数。编写适应度函数，语法格式如下：function f=fitnessfcn(x)%x为自变量向量 f=f(x);实例2 如果有约束条件（包括自变量的取值范围），对于求解函数的最小值问题，可以使用如下语法格式：function f=fitnessfcn(x)if(x3)%表示有约束x-1和x=3，其他约束条件类推 f=inf;else f=f(x);end,实例3 如果有约束条件(包括自变量的取值范围）,对于求解函数的最大值问题，可以使用如下语法格式：function f=fitnessfcn(x)if(x3)f=inf else f=-f(x);%注意，这里f=f(x)而不是f=f(x)end 若目标函数作为适应度函数，则最终得到的目标函数值为-fval 而不是fval,五，遗传算法应用实例,5.1 无约束目标函数最大值遗传算法求解策略5.2 CUMCM中多约束非线性规划问题的求解,5.1 无约束目标函数最大值遗传算法求解策略求解问题：用MATLAB画出该函数在-2,2区间的图形，如下图所示：,利用MATLAB自带工具Data Cursor 菜单探测出 在区间 上最大值大概为于（1.534,185.1）坐标点附近，具体求解程序见下图。,本程序取运算精度precision=0.0001,初始群popsize=50,进化代数Generationnmax=12,交配概率pcrossover=0.90,变异概率pmutation=0.09，经过12次迭代，程序输出的结果为：,Bestpopulation=1.5319Besttargetfunvalue=185.1128运算结果与理论值一致，且只进化了12代，效果理想，同时，程序输出平均适应度和种群最大适应度的变化趋势如下图：,适应度变化趋势图,由上图可知：（1）最大适应度值在进化过程中变化幅度不大 这是由于较多的染色体和较小的搜索区间让算法最大初始适应度值有更多的机会直接落在理论最优解附近。（2）平均适应度值在进化过程中快速增加 说明遗传算法是一种进化方向异常明确的机器学习方法，不依靠“最优保存”策略，绝大部分情况也能最终寻找到最优解。,5.2 CUMCM中多约束非线性规划问题的求解,s.t.目标函数三维图像,根据GA方法编写求解程序如下：,程序输出结果如下:,输出适应度如下图所示：,谢谢欣赏,