版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
尚德敏学唯实惟新MATLAB程序设计CONTENTS目录优化问题概述MATLAB中的优化工具箱优化函数的参数设置与定义7.17.27.37.4基于模拟退火算法的极值求解尚德敏学唯实惟新7.1优化问题概述
在实际的工程优化设计过程中,它包含着两个方面的内容,或者说需要两个重要的步骤:
第一步:建立数学模型:用数学语言来描述最优化问题,把实际问题转换成能够用数学表达式表示的形式,模型中的数学关系式反映了最优化问题的目标和各种约束,为我们理论研究打下坚实的基础。第二步:数学求解选择合理的最优化方法进行求解。尚德敏学唯实惟新1.优化问题模型优化问题的数学标准形式:
其中,X是待求变量,A和b是线性不等式约束的系数向量,Aeq和beq是线性等式约束的系数,b和beq是向量,A和Aeq是矩阵,c(X)和ceq(X)是返回向量的函数,分别是非线性不等式约束和非线性等式约束,lb和u,是变量的上下限。尚德敏学唯实惟新1.优化问题模型问题一:假设某种产品有3个产地A1、A2、A3,他们的产量分别为100、170、200(单位为吨),该产品有3个销售地B1、B2、B3,各地的需求量分别是120、170、180(单位为吨),把产品从第i个产地Ai运到第j个销售地Bj,的单位运价(元/吨)如表7-1所示,问如何安排从Ai到Bj的运输方案,才能满足各地销售的需求又能使总运费最小?B1B2B3产量A1809075100A2608595170A39080110200A4120170180470表7-1产地Ai运到第j个销售地Bj的单位运价表尚德敏学唯实惟新1.优化问题模型建立数学模型如下:设从A到B的运输量为xij,显然总运费的表达式为:80x11+90x12+75x13+60x21+85x22+95x23+90x31+80x32+110x33根据产量要求,则可以建立如式所示的三个等式,作为上述总运费的约束式:x11+x12+x13=100x21+x22+x23=170x31+x32+x33=200根据需求量要求,则可以建立如式所示的三个等式,作为上述总运费的另外的约束式:x11+x12+x13=120x21+x22+x23=170x31+x32+x33=180此外,在实际问题中,运输量不能为负值,所以有如下约束:xij≥0,i,j=1,2,3尚德敏学唯实惟新1.优化问题模型综上所述,此产销平衡问题的数学模型可以写为如下:minf(x)=80x11+90x12+75x13+60x21+85x22+95x23+90x31+80x32+110x33
尚德敏学唯实惟新2.数学求解根据数学模型变量的不同,可以把目前的求解方法分为如下两大类:对于大部分单变量或者相对简单的数学模型,可以采用人工计算的方式进行,根据是否对目标函数求导,又可分为直接法和间接法,直接法主要有消去法和多项式近似法。一种典型的消去法是黄金分割法而间接法需要用到目标函数的导数。多项式近似法。该法用于目标函数比较复杂的情况,此时寻找一个与他近似的函数代替目标函数,常用的近似函数为二次和三次多项式。优化问题在使用MATLAB软件求解时的注意如下:(1)目标函数最小化:一般都要求实现目标函数的最小值,如果优化问题是求最大值,可以通过求原目标函数的负值的最小化来实现,即-f(X)最小化来实现。(2)约束非正:一般都要求不等式约束形式为c(X)<=0,通过对不等式的取负可以达到使大于零的约束形式变为小于零的不等式约束的形式目的。尚德敏学唯实惟新2.数学求解问题:边长为3m的正方形铁板,在4个角处减去四个相等的正方形以制成方形无盖水槽问如何剪才能使水槽容积最大?根据题意,上述问题的数学模型为:属于单变量优化问题,可以采用直接法进行计算可得:也可以采用MATLAB进行计算,需要将原最大值问题转化成最小值问题,如下:在MATLAB命令行窗口输入以下命令,回车后运行结果如下所示:尚德敏学唯实惟新3.非线性最小二乘优化问题非线性最小二乘优化也叫无约束极小平方和函数问题,它是如下无约束极小问题,
程序代码如下:尚德敏学唯实惟新3.非线性最小二乘优化问题拟合结果如下:尚德敏学唯实惟新7.2MATLAB中优化工具箱(1)工具箱的功能:①求解无约束条件非线性极小值;②求解约束条件下非线性极小值,包括目标逼近问题、极大-极小值问题以及半无限极小值问题;③求解二次规划、线性规划和混合整型线性规划问题;④非线性最小二乘逼近和曲线拟合;⑤非线性系统的方程求解;⑥约束条件下的线性最小二乘优化;⑦求解复杂结构的大规模优化问题。尚德敏学唯实惟新7.2MATLAB中优化工具箱123优化函数具有简洁的函数表达式,多种优化算法可以任意选择,算法参数可自由进行设置,使得用户方便灵活地使用优化函数.并行计算功能集成在了优化工具箱的优化求解器中,以便用户在不对现有程序有大的改变的情况下,在多台计算机或集群计算机上进行密集型计算优化问题的求解。提供了定义和求解优化问题并监视求解进度的OptimizationApp,可以方便地打开优化工具,进行优化问题的求解。(2)工具箱的特色:尚德敏学唯实惟新7.2MATLAB中优化工具箱(3)工具箱的结构:尚德敏学唯实惟新7.2MATLAB中优化工具箱全局优化工具箱提供的最优化方法:
全局搜索和多起点优化
遗传算法模拟退火
算法模式搜索算法
全局搜索和多起点优化方法产生若干起始点,然后它们用局部求解器去找到起始点吸引盆处的最优点。遗传算法(GA)用一组起始点(称为种群),通过迭代从种群中产生更好的点,只要初始种群覆盖几个盆,GA就能检查几个盆。模拟退火完成一个随机搜索,通常模拟退火算法接受一个点,只要这个点比前面那个好,它也偶而接受—个比较糟的点,目的是转向不同的盆。模式搜索算法在接受一个点之前要看看其附近的一组点。假如附近的某些点属于不同的盆模式搜索算法本质上是同时搜索若干个盆。尚德敏学唯实惟新7.3优化函数的参数设置与定义MATLAB优化工具箱的主要函数尚德敏学唯实惟新7.3优化函数的参数设置与定义优化函数输入参数定义尚德敏学唯实惟新7.3优化函数的参数设置与定义常用的options参数中常用的几个参数如下:①Display:结果显示方式,取值为off时,不显示任何结果;取值为iter时,显示每次迭代的信息;取值为final时,显示最终结果,默认值为final;取值为notify时,只有当求解不收敛的时候才显示结果。②MaxFunEvals:允许进行函数计算的最大次数,取值为正整数。③MaxIter:允许进行迭代的最大次数,取值为正整数。④TolFun:函数值(计算结果)的精度,取值为正数。⑤TolX:自变量的精度,取值为正数。尚德敏学唯实惟新7.3优化函数的参数设置与定义MATLAB优化函数的输出参数尚德敏学唯实惟新7.3优化函数的参数设置与定义
尚德敏学唯实惟新7.3优化函数的参数设置与定义第一步:建立目标函数文件,命名为my_fun1.m第二步:调用函数fmincon,在命令行窗口输入如下命令,其结果如下所示:尚德敏学唯实惟新7.4基于模拟退火算法的极值求解
尚德敏学唯实惟新7.4基于模拟退火算法的极值求解231Meteopolis准则温度退火进度表这是一个重要的参数,它随着算法的迭代逐步下降,以模拟固体退火过程中的降温过程。一方面,温度用于限制SA产生的新解与当前解之间的距离,即SA的搜索范围;另一方面,温度决定了SA以多大的概率接受目标函数值比当前解的目标函数值差的新解。
是指温度随算法迭代的下降速度。退火过程越缓慢,SA找到全局最优解的机会就越大。退火进度表包括初始温度及温度更新函数的参数。尚德敏学唯实惟新7.4基于模拟退火算法的极值求解在MATLAB中,提供了模拟退火算法的simulannealbnd函数,用于求解目标函数的最小值,在使用时可以直接调用,其格式如下:[xfval]=simulannealbnd(fun,x0,lb,ub,options)说明:options是对模拟退火算法进行参数设置,其格式下:options=saoptimset('param1'value1,'param2',value2...)参数param是设定的参数,如最大迭代次数、初始温度、绘图函数等;value是param
的具体值。尚德敏学唯实惟新7.4基于模拟退火算法的极值求解
MATLAB程序设计第八章智能算法目录8.1粒子群算法8.2遗传算法8.3混合蛙跳算法8.1粒子群算法ParticleSwarmOptimization,简称PSO;粒子群优化算法(PSO)是一种进化计算技术(EvolutionaryComputation),由Eberhart(电子工程学博士)和Kennedy
(社会心理学博士)于1995年源于对鸟群捕食的行为研究。粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解.PSO的优势在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。
肯尼迪对鸟群行为的模拟:Reynolds、Heppner和Grenader提出鸟群行为的模拟。他们发现,鸟群在行进中会突然同步的改变方向,散开或者聚集等。那么一定有某种潜在的能力或规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。在这些早期的模型中仅仅依赖个体间距的操作,也就是说,这中同步是鸟群中个体之间努力保持最优的距离的结果。PSO的产生背景对鱼群行为的研究:生物社会学家E.O.Wilson对鱼群进行了研究。提出:“至少在理论上,鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中的发现和以前的经验,这种受益超过了个体之间的竞争所带来的利益消耗,不管任何时候食物资源不可预知的分散。”这说明,同种生物之间信息的社会共享能够带来好处。这是PSO的基础。群体协作-获取信息、共享信息示意算法介绍设想这样一个场景:一群鸟在随机的搜索食物。在这个区域里只有一块食物,所有的鸟都不知道食物在哪里。但是它们知道自己当前的位置距离食物还有多远。那么,找到食物的最优策略是什么?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO示意图每个鸟抽象为一个无质量,无体积的“粒子”每个粒子有一个适应度函数以模拟每只鸟与食物的距离每个粒子有一个速度决定它的飞行方向和距离,初始值可以随机确定每一次单位时间的飞行后,所有粒子分享信息,下一步将飞向自身最佳位置和全局最优位置的加权中心初始化为一群随机粒子,通过迭代找到最优。每次迭代中,粒子通过跟踪“个体极值(pbest)”和“全局极值(gbest)”来更新自己的位置。粒子速度和位置的更新
假设在D维搜索空间中,有m个粒子;其中第i个粒子的位置为矢量其飞翔速度也是一个矢量,记为第i个粒子搜索到的最优位置为整个粒子群搜索到的最优位置为第i个粒子的位置和速度更新为:注意:上式为PSO的一般形式。其中,c1和c2为两个正的常系数,称为加速(学习)因子。第d(1≤d≤D)维的位置X变化范围为[lbd,ubd],速度V变化范围为[V_lbd,V_ubd],迭代中若位置和速度超过边界范围则取边界值。
KennedyJ,EberhartR.Particleswarmoptimization.ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks.1995.1942~1948.从社会学的角度来看,公式(1)的第一部分称为记忆项,表示上次速度大小和方向的影响;公式第二部分称为自身认知项,是从当前点指向粒子自身最好点的一个矢量,表示粒子的动作来源于自己经验的部分;公式的第三部分称为群体认知项,是一个从当前点指向种群最好点的矢量,反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。该成果以会议论文的形式发表。“惯性部分”,对自身运动状态的信任程度“认知部分”,对粒子本身的思考,即来源于自己经验的部分“社会部分”,粒子间的信息共享,来源于群体中的其它优秀微粒的经验1998年shi等人在进化计算的国际会议上发表了一篇论文《Amodifiedparticleswarmoptimizer》对前面的公式中的第一项通过引入惯性权重因子进行了修正,形成了现在公认的PSO的标准形式。惯性权重w
使粒子保持运动惯性,使其有扩展搜索空间的趋势,有能力探索新的区域。表示微粒对当前自身运动状态的信任,依据自身的速度进行惯性运动。较大的w有利于跳出局部极值,而较小的w有利于算法收敛。初始时,shi将w取为常数,后来实验发现,动态w能够获得比固定值更好的寻优结果。动态w可以在PSO搜索过程中线性变化,也可根据PSO性能的某个测度函数动态改变。目前,采用较多的是shi建议的线性递减权值(linearlydecreasingweight,LDW)策略Gk为最大进化代数,
wini为初始惯性权值,
wend为迭代至最大代数时惯性权值。典型取值
wini=0.9,wend=0.4。
w的引入使PSO算法性能有了很大提高,针对不同的搜索问题,可以调整全局和局部搜索能力,也使得PSO算法能成功的应用于很多实际问题LDW策略加速常数c1和c2
代表将粒子推向pbest和gbest位置的统计加速项的权重。表示粒子的动作来源于自己经验的部分和其它粒子经验的部分。较小的值允许粒子在被拉回之前可以在目标区域外徘徊,而较大的值则导致粒子突然冲向或越过目标区域。
方程中pbest和gbest分别表示微粒群的局部和全局最优位置,当C1=0时,则粒子没有了认知能力,变为只有社会的模型(social-only):被称为全局PSO算法.粒子有扩展搜索空间的能力,具有较快的收敛速度,但由于缺少局部搜索,对于复杂问题比标准PSO更易陷入局部最优。当C2=0时,则粒子之间没有社会信息,模型变为只有认知(cognition-only)模型:被称为局部PSO算法。由于个体之间没有信息的交流,整个群体相当于多个粒子进行盲目的随机搜索,收敛速度慢,因而得到最优解的可能性小。加速常数c1和c2
将c1和c2统一为一个控制参数,φ=c1+c2
如果φ很小,粒子群运动轨迹将非常缓慢;如果φ很大,则微粒位置变化非常快;实验表明,当φ=4.1(通常c1=2.05,c2=2.05)时,具有很好的收敛效果。粒子数
一般取20~40,对较难或特定类别的问题可以取
100~200。最大速度vmax
决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度。终止条件
最大循环数以及最小错误要求。基本粒子群算法的寻优示意4647MATLAB中调用PSOPso现在已作为MATLAB优化工具箱中的基本函数。其格式如下:[xfval]=particleswarm(fun,nars,lb,ub)各参数含义与前述规定基本相同488.2遗传算法遗传算法(Geneticalgorithm,GA)是应用最广泛的一种演化算法,为典型代表。
一切生物都具有产生变异的特性。在生存斗争中,具有有利变异的个体,容易在生存斗争中获胜而生存下去。反之,具有不利变异的个体,则容易在生存斗争中失败而死亡。此过程叫做自然选择。
自然选择过程是一个长期的、缓慢的、连续的过程。由于生存斗争不断地进行,因而自然选择也是不断地进行,通过一代代的生存环境的选择作用,物种变异被定向地向着一个方向积累,于是性状逐渐和原来的祖先不同了,可以说物种也因此得到优化了。50(一)背景CharlesRobertDarwin1859年,达尔文(CharlesRobertDarwin)出版的《物种起源》,提出进化学说51遗传以密码方式存在细胞内,并以基因形式包含在染色体内,每个基因有特殊的位置并控制某种特殊性质,所以每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可以产生更适应于环境的后代,经过存优去劣的自然淘汰,适应性高的基因结构得以保存下来1865年,孟德尔(GregorJohannMendel)
发现遗传定律52生物进化是指一个种群经过漫长的时间所发生的累积变化,这些变化是由于生物体的基因变异或者繁殖期间以不同方式重组基因所产生的,而且这些变化可以被遗传到生物体的后代。从本质上说,它是一个优胜劣汰的自然过程,也是一个优化过程。优化的结果是产生能够很好地适应环境的生物体。此过程也可以看成是在众多可能性中搜索“解”的一种方法。遗传算法(GeneticAlgorithms,GA)是模拟生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。53GA的发展历程20世纪60年代中期,美国的Michigan(密歇根)大学的J.H.Holland借鉴生物自然遗传的基本原理(自然选择、适者生存)提出的一种搜索寻优算法,用于自然和人工系统的自适应行为研究和串编码技术。1967年,他的学生J.D.Bagley在博士论文中首次提出“遗传算法”一词。1975年,Holland出版了著名的“AdaptationinnaturalandArtificialSystems”,标志着遗传算法的正式诞生。(一)产生过程20世纪50年代到60年代,生物学家Fraser试图通过计算的方法来模拟生物界“遗传与选择”的进化过程,
这是遗传算法的最早雏形。5570年代初,Holland提出了“模式定理”(SchemaTheorem),一般认为是“遗传算法的基本定理”,从而也奠定了遗传算法研究的理论基础;1985年,在美国召开了第一届遗传算法国际会议,并且成立了国际遗传算法学会(ISGA,InternationalSocietyofGeneticAlgorithms);1989年,他的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”,系统的总结了遗传算法的主要研究成果,全面完整地论述了GA的基本原理和应用;1991年,L.Davis出版了“HandbookofGeneticAlgorithms”,介绍了GA在科学计算、工程技术和社会经济等领域中的大量应用实例,为推广和普及GA的应用起到了重要的指导作用;(二)发展ProcedureGeneticAlgorithmProcedureEA遗传算法的基本步骤:第1步.根据由问题确定的编码规则,随机产生初始群体;第2步.计算群体中每个个体的适应度值;第3步.如果解满足要求或遗传代数超过指定代数,则结束;否则继续执行第4步;第4步.根据适应值进行选择复制产生新一代;第5步.根据事先确定的交叉和变异概率选择部分个体进行交叉和变异,转第2步;
GA的流程图遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象,在每次迭代中都保留一组候选解,并按某种指标从解群中选取较优的个体,利用遗传算子(选择、交叉和变异)对这些个体进行组合,产生新一代的候选解群,重复此过程,直到满足某种收敛指标为止。
(二)基本遗传算法的计算过程遗传算法的基本思想:在求解问题时从多个解开始,然后通过一定的法则进行逐步迭代以产生新的解(1)编码(产生初始种群)(2)适应度函数(3)遗传算子(选择、交叉、变异)(4)运行参数
编码遗传算法(GA)通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手,而染色体则是由基因排成的串。基本遗传算法(SGA)使用二进制串进行编码。1000101110110101000111
染色体基因
编码示例求下列一元函数的最大值:其中x∈[-1,2],求解结果精确到6位小数。(1)二进制编码要求取多少位?(2)十进制实数与二进制编码之间应满足怎样的数学关系??
编码示例的分析区间长度为3,求解结果精确到6位小数,因此可将自变量定义区间划分为3×106等份。又因为221<3×106<222
,所以二进制编码长度至少需要22位。编码过程实质是将区间[-1,2]内对应的实数值转化为一个二进制串(b21b20b19b18…b1b0)。101010111111……101011000
一个问题对于x∈[-1,2],结果精确到6位小数,十进制实数与二进制编码之间应满足怎样的数学关系?
编码(二进制)与实数(十进制)的转换(1000101110110101000111)2
编码与实数的转换(1000101110110101000111)20.637197基因型与表现型基因型:1000101110110101000111表现型:0.637197
编码解码个体(染色体)基因初始种群基本遗传算法(SGA)采用随机方法生成若干个个体的集合,该集合称为初始种群。初始种群中个体的数量称为种群规模。
适应度函数遗传算法对一个个体(解)的好坏用适应度函数值来评价,适应度函数值越大(或越小),解的质量越好。适应度函数是遗传算法进化过程的驱动力,也是进行自然选择的唯一标准,它的设计应结合求解问题本身的要求而定。选择算子遗传算法使用选择运算对个体进行优胜劣汰操作。适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体,被遗传到下一代群体中的概率小。选择操作的任务就是从父代群体中选取一些个体,遗传到下一代群体。基本遗传算法(SGA)中选择算子采用轮盘赌选择方法。一等奖二等奖三等奖四等奖轮盘赌选择方法(RouletteWheelSelection)轮盘赌选择方法轮盘赌选择又称比例选择算子,其基本思想是:各个个体被选中的概率与其适应度函数值成正比。设群体大小为N,个体xi
的适应度为f(xi),则个体xi的选择概率为:轮盘赌选择法可用如下过程模拟来实现:(1)在[0,1]内产生一个均匀分布的随机数r。(2)若r≤q1,则染色体x1被选中。(3)若qk-1<r≤qk(2≤k≤N),则染色体xk被选中。其中的qi称为染色体xi
(i=1,2,…,n)的积累概率,其计算公式为轮盘赌选择方法积累概率实例:
轮盘赌选择方法0.140.490.060.3100.140.630.691q1q2
q3
q4
积累概率q选择概率P轮盘赌选择方法轮盘赌选择方法的实现步骤:(1)计算群体中所有个体的适应度值;(2)计算每个个体的选择概率P;(3)计算积累概率q;(4)采用模拟赌盘操作(即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配)来确定各个个体是否遗传到下一代群体中。轮盘赌选择方法例如,有染色体
s1=13(01101)
s2=24(11000)
s3=8(01000)
s4=19(10011)
假定适应度函数为f(s)=s2
,则
f(s1)=f(13)=132=169
f(s2)=f(24)=242=576
f(s3)=f(8)=82=64
f(s4)=f(19)=192=361染色体的选择概率为染色体的累计概率为
例如,从区间[0,1]中产生4个随机数:
r1=0.450126,r2=0.110347
r3=0.572496,r4=0.98503
染色体
适应度选择概率积累概率选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001交叉算子交叉运算,是指对两个相互配对的染色体依据交叉概率Pc
按某种方式相互交换其部分基因,从而形成两个新的个体。交叉运算是遗传算法区别于其他演化算法的重要特征,它在遗传算法中起关键作用,是产生新个体的主要方法。基本遗传算法(SGA)中交叉算子采用单点交叉算子。单点交叉运算交叉前:01000|0111000000001000011100|00000111111000101交叉后:01000|00000111111000101(孩子1)11100|01110000000010000(孩子2)交叉点变异算子变异运算,是指改变个体编码串中的某些基因值,从而形成新的个体。变异运算是产生新个体的辅助方法,决定遗传算法的局部搜索能力,保持种群多样性。交叉运算和变异运算的相互配合,共同完成对搜索空间的全局搜索和局部搜索。基本遗传算法(SGA)中变异算子采用基本位变异算子。基本变异算子基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于二进制编码符号串所表示的个体,若需要进行变异操作的某一基因座上的原有基因值为0,则将其变为1;反之,若原有基因值为1,则将其变为0。基本位变异示例变异前:000001110000000010000变异后:000001110001000010000变异点已知x为整数,利用遗传算法求解区间[0,31]上的二次函数y=x2的最大值。
y=x2
31
XY遗传算法的应用举例
[分析]
原问题可转化为在区间[0,31]中搜索能使y取最大值的点a的问题。个体:[0,31]中的任意点x
适应度:函数值f(x)=x2
解空间:区间[0,31]这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。[解]
(1)设定种群规模,编码染色体,产生初始种群。将种群规模设定为4;用5位二进制数编码染色体;取下列个体组成初始种群S1s1=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=169
f(s2)=f(24)=242=576
f(s3)=f(8)=82=64f(s4)=f(19)=192=361评价个体的适应度值再计算种群S1中各个体的选择概率。
由此可求得
P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31再计算种群S1中各个体的积累概率
选择-复制:设从区间[0,1]中产生4个随机数:r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503
染色体
适应度选择概率积累概率选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001于是,经复制得群体:s1’
=11000(24),s2’
=01101(13)s3’
=11000(24),s4’
=10011(19)
被选中两次交叉
设交叉率pc=100%,即S1中的全体染色体都参加交叉运算。
设s1’与s2’配对,s3’与s4’配对。
s1’=11000(24),s2’=01101(13)
s3’=11000(24),s4’=10011(19)分别交换后两位基因,得新染色体:
s1’’=11001(25),s2’’=01100(12)
s3’’=11011(27),s4’’=10000(16)
变异
设变异率pm=0.001。
这样,群体S1中共有
5×4×0.001=0.02位基因可以变异。
0.02位显然不足1位,所以本轮遗传操作不做变异。于是,得到第二代种群S2:
s1=11001(25),s2=01100(12)
s3=11011(27),s4=10000(16)
第二代种群S2中各染色体的情况
染色体
适应度选择概率积累概率
估计选中次数s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001
假设这一轮选择-复制操作中,种群S2中的4个染色体都被选中,则得到群体:
s1’=11001(25),s2’=01100(12)
s3’=11011(27),s4’=10000(16)
做交叉运算,让s1’与s2’,s3’与s4’
分别交换后三位基因,得
s1’’=11100(28),s2’’
=01001(9)
s3’’
=11000(24),s4’’
=10011(19)
这一轮仍然不会发生变异。
于是,得第三代种群S3:
s1=11100(28),s2=01001(9)
s3=11000(24),s4=10011(19)
第三代种群S3中各染色体的情况
染色体
适应度选择概率积累概率
估计的选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001
设这一轮的选择-复制结果为:
s1’=11100(28),s2’=11100(28)
s3’=11000(24),s4’=10011(19)
做交叉运算,让s1’与s4’,s2’与s3’
分别交换后两位基因,得s1’’=11111(31),s2’’=11100(28)
s3’’=11000(24),s4’’=10000(16)
这一轮仍然不会发生变异。被选中两次
于是,得第四代种群S4:
s1=11111(31),s2=11100(28)
s3=11000(24),s4=10000(16)出现了最优解!
显然,在这一代种群中已经出现了适应度最高的染色体s1=11111。于是,遗传操作终止,将染色体(11111)作为最终结果输出。然后,将染色体“11111”解码为表现型,即得所求的最优解:31。
将31代入函数y=x2中,即得原问题的解,即函数y=x2的最大值为961。
YYy=x2
8131924
X第一代种群及其适应度y=x2
12162527
XY第二代种群及其适应度y=x2
9192428
XY第三代种群及其适应度y=x2
16242831
X第四代种群及其适应度刚刚产生四代种群及其适应度。你知道这四代种群之间有何发展规律吗?四代种群的发展规律就是适应度的整体水平越来越好,直到最优解出现!105遗传算法在MATLAB中如何应用?遗传算法的基本流程Step1:对运行参数赋值;Step2:建立区域描述器;
Step3:初始化种群,并评估个体好坏;Step4:进行选择操作Step5:按交叉概率进行交叉操作Step6:按变异概率进行变异操作Step7:执行新个体保存策略,形成新种群Step8:判断是否满足结束条件根据定义编程调用函数ga使用优化工具箱√X√最优化问题的标准型106A和b是线性不等式约束的系数Aeq和beq是线性等式约束的系数c是非线性不等式约束ceq是非线性等式约束lb和ub是变量的上下限107ga函数的基本格式[xfval]=ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)fun:待求的目标函数nvars:变量的个数nonlcon:非线性约束的表达式,匿名函数形式options:遗传算法的参数设置(较复杂)fval:最优个体的函数值一、调用函数ga《MATLAB程序设计》108minf(x)=-x(3-2x)2
x=fminbnd(@(x)-x*(3-2*x)^2,0,1.5)方法1:MATLAB命令行窗口输入以下命令:例1-无约束问题方法2:调用ga函数步骤一:建立目标函数文件:functiony=my_fun(x)y=-x*(3-2*x)^2;步骤二:调用x=ga(@my_fun,1,[],[],[],[],0,1.5)基于内部映射牛顿法fminsearch?例2-线性约束问题109步骤一:建立目标函数文件:functiony=my_fun2(x)y=0.5*x(1)^2+x(2)^2-x(1)*x(2)-2*x(1)-6*x(2);步骤二:调用A=[11;-12;21];b=[2;2;3];lb=[0;0];x=ga(@my_fun2,2,A,b,[],[],lb)110例3-非线性约束问题步骤一:建立目标函数文件:functiony=my_fun3(x)y=100*(x(1)^2-x(2))^2+(1-x(1))^2;function[cceq]=my_fun3_con(x)c=[1.5+x(1)*x(2)+x(1)-x(2);10-x(1)*x(2);];ceq=[];步骤二:建立非线性约束文件:步骤三:调用lb=[0;0];
ub=[1;13];x=ga(@my_fun3,2,[],[],[],[],lb,ub,@my_fun3_con)111二、使用优化工具箱MATLAB系统中带有一个优化工具箱,其调用方式有两种:在命令行输入命令:optimtool
或点击APP标签,选择optimization点击112113遗传算法工具箱problemsetupandresults说明:注意事项:1)需要单独写适应度函数和变量个数2)各约束参数含义与前述相同3)integervariableindices的含义是“整型变量标记约束”114遗传算法工具箱Options说明(1):1)群体(Population)(1)编码类型(populationtype)实数编码(doublevector)二进制编码(bitstring)自定义(custom)(2)种群规模(populationtype)115遗传算法工具箱Options说明(2):2)选择(Selection)算子随机均匀分布(stochasticuniform)残余(remainder)均匀(uniform)联赛选择(
tournament)轮盘赌(
roulette)
自定义(custom)116
没有这两个参数,由交叉函数和变异函数来确定,这也是和基本遗传算法的区别之处。交叉比例(crossoverfraction):由交叉产生的个体占父代中非精英个体数的比例遗传算法工具箱Options说明(3):3)复制(再生、繁殖)算子4)交叉概率和变异概率精英数(elitecount):直接传到下一代的个体数《MATLAB程序设计》117属于算法停止标准,除此之外主要有时间限制(timelimit)和适应值限制(fitnesslimit)
遗传算法工具箱Options说明(3):5)迭代次数(generations)6)结果可视化绘制最佳适应度值(bestfitness)和最佳个体(bestindividual)随迭代次数的变化曲线118例2-线性约束问题119例4-非线性约束问题functiony=my_fun4(x)y=-(2*x(1)+3*x(1)^2+3*x(2)+x(2)^2+x(3));function[cceq]=my_fun4_con(x)c=[x(1)+2*x(1)^2+x(2)+2*x(2)^2+x(3)-10;x(1)+x(1)^2+x(2)+x(2)^2-x(3)-50;2*x(1)+x(1)^2+2*x(2)+x(3)-40];ceq=[x(1)^2+x(3)-2];步骤一:转换目标函数为标准型步骤二:编写目标函数步骤三:编写非线性约束函数120设置一:目标函数及约束条件如图所示:设置二:遗传算法的参数如图所示,具体如下:种群规模:100选择策略:轮盘赌精英数:8交叉比例:0.6迭代次数:200其它参数采用默认值遗传算法属于随机搜索算法,对于复杂、多模态函数问题,每一次的计算结果不完全一致,属于正常情况,需要对算法本身的参数反复调试,直到结果误差在允许范围内优化工具箱和调用ga函数,其核心算法和内核是一样的,不同之处在于,当你想对遗传算法的参数进行设置时,建议使用优化工具箱,因为方便易学。Matlab采用的是现代遗传算法,上一节讲的是基本(简单)遗传算法,二者基本内容是一致的121总结:MATLAB程序设计CONTENTS目录连杆机构设计7.1平面连杆机构运动分析7.3平面机构优化设计7.2尚德敏学唯实惟新9.1连杆机构设计
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论