遗传算法及其MATLAB实现PPT课件

遗传算法及其MATLAB实现41组，顾英辉，魏猛，王艺潞,一、遗传算法的概述,1、产生与发展2、生物学基础3、算法的特点及定义二、遗传算法的原理1、简单遗传算法2、简单遗传算法原理3、遗传算法参数选择三、遗传算法的流程1、算法流程图2、遗传算法举例,四，遗传算法的MATLAB程序设计,1、程序设计流程及参数选取1.1、遗传算法的程序设计伪代码1.2、适应度函数调整2、遗传算法工具箱核心函数的用法3、GeneticAlgorithmandDirectSearchToolbox适应度函数设计五，遗传算法的应用实例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在博士论文中首次提出“遗传算法(GeneticAlgorithms)”一词；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，标志遗传算法的诞生,发展遗传算法进化计算计算智能人工智能,70年代初，Holland提出了“模式定理”（SchemaTheorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，InternationalSocietyofGeneticAlgorithms)；1989年，Holland的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，对遗传算法及其应用作了全面而系统的论述；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=0L0000000000000000001=1L+0000000000000000010=2L+2.1111111111111111111=-1U易知：,解码：解码的目的是为了将不直观的二进制数据串还原成十进制。设某一个体的二进制编码为，则对应的解码公式为例：设有参数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=1001011011101110011010101001划线部分倒位得=100101100101001110111101001,2.3遗传算法参数选择,种群规模：既不能过大也不能过小。过大会导致结果难以收敛且浪费资源，稳健型下降；过小会导致种群进化不能按照模式定理产生所预测的期望值。种群规模的一个建议值0100。种群初始化：初始种群的生成是随机的。在初始种群的赋予之前，尽量进行一个大概的区间估计，以免初始种群分布在远离全局最优解的编码空间，导致遗传算法的搜索范围受到限制，同时也为算法减轻负担。交配概率：交配概率过大容易破坏已有的有利模式，随机性增大，容易错失最优个体；过小不能有效更新种群。交配概率一般取值0.40.99。,变异概率：变异概率过小时种群多样性下降太快，容易导致有效基因迅速丢失且不容易修补；过大时，尽管种群的多样性得到保证，但是高阶模式被破坏的概率也随之增大。变异概率一般取0.00010.2。进化代数：进化代数过小，算法不容易收敛，种群还没有成熟；过大，算法已经熟练或者种群过于早熟不可能在收敛，继续进化就没有意义，只会增加时间开支和资源浪费。进化代数一般取100500.,三、遗传算法的流程,3.1、算法流程图3.2、遗传算法举例,3.1算法流程图,3.2遗传算法举例例：函数，求其在区间0,31的最大值（1）编码将变量转换成二进制数串，设要求的精度是1，意味着变量应该被分成至少31个部分，由于-1和x=3，其他约束条件类推f=inf;elsef=f(x);end,实例3如果有约束条件(包括自变量的取值范围）,对于求解函数的最大值问题，可以使用如下语法格式：functionf=fitnessfcn(x)if(x3)f=infelsef=-f(x);%注意，这里f=f(x)而不是f=f(x)end若目标函数作为适应度函数，则最终得到的目标函数值为-fval而不是fval,五，遗传算法应用实例,5.1无约束目标函数最大值遗传算法求解策略5.2CUMCM中多约束非线性规划问题的求解,5.1无约束目标函数最大值遗传算法求解策略求解问题：用MATLAB画出该函数在-2,2区间的图形，如下图所示：,利用MATLAB自带工具DataCursor菜单探测出在区间上最大值大概为于（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）最大适应度值在进化过程