最优化技术基础

最优化技术基础第1页，课件共38页，创作于2023年2月1、遗传算法概述

1.1遗传算法的生物学背景

1859年达尔文发表《物种起源》,提出以自然选择为基础的生物进化论学说,认为生物进化发展主要有3个原因:遗传、变异和选择。生物遗传物质的主要载体是染色体。染色体主要是由DNA和蛋白质构成。其中DNA在染色体里含量稳定，结构也相对稳定，能够自我复制和产生可遗传的变异，是主要的遗传物质。而生物的性状遗传，主要是通过染色体上的基因遗传给后代的。基因是遗传物质的基本单位，又称遗传因子。生物的变异有3种可能性：基因重组、基因突变和染色体变异。基因重组是指控制不同性状的基因的重新组合。基因突变是指基因内部的化学变化。每种生物的染色体无论结构或数目都是相对稳定的，但在自然或人为条件的作用下，染色体的结构和数目都可以发生变化，不过染色体数目的改变是染色体变异的一个主要方面。由于生物进化论揭示了生物自然选择的进化发展规律，人们从中受到了启迪，生物进化论的自然选择过程蕴含着一种搜索和优化的先进思想，将这种思想用于科学研究和工程技术领域而发展起来的方法，称为遗传算法GA(GeneticAlgorithm)，这种算法为解决许多传统的优化方法难以解决的优化问题提供了崭新的途径。第2页，课件共38页，创作于2023年2月

目前，遗传算法发展迅速，已被广泛应用于解决各种问题，例如，系统优化、机器学习、工程控制、模式识别、人工智能、故障诊断以及计算机技术等领域，取得了良好的效果。随着遗传算法的基本原理、方法及其应用技巧的深入研究，其应用范围也越来越广泛，几乎渗透到从工程到社会科学的诸多领域，必须要编制遗传算法的程序进行计算。使用者希望找一个现成的程序，MATLAB的遗传算法工具箱正好满足要求。

Matlab语言有着丰富的由世界著名专家、学者开发出的各种工具箱，Matlab的优化工具箱提供了对各种优化问题的解决方案，遗传算法优化工具箱就是其中之一。采用MATLAB遗传算法优化工具箱，不仅具有简单、易用、易于修改的特点，而且为解决许多传统搜索的优化方法难以解决的非线性、多峰值之类的复杂问题提供了有效的途径。遗传算法的研究和应用具有很好的应用前景。第3页，课件共38页，创作于2023年2月1.2遗传算法的特点

①遗传算法处理的是待求问题变量的编码，而不是变量的本身。②遗传算法使用概率规则而不是确定性规则指导搜索，只要一个适应度函数值，而不必要求其他辅助信息，诸如连续性、导数存在和单峰等，因而具有极好的鲁棒性和广泛的适应性。③遗传算法通过控制群体中N个数字串，能处理各代中大量的模式，在每一代中被处理的模式数目大概是N3，这一切在群体中并行进行的，也就是说，遗传算法同时搜索解空间中许多个点而不是一个点，因而能够快速全局收敛。遗传算法这种隐含的并行性是它区别于其他优化方法最主要的因素。④遗传算法像撒网一样，在变量空间中进行寻优，由N个数字串组成的群体在遗传因子的作用下，同时对空间中不同的区域进行充分搜索，从而构成一个不断优化的群体序列。遗传算法是通过保持在解空间不同区域中各个点的搜索，而不是盲目地穷举或瞎碰，故相对其他优化方法而言，遗传算法能以很大的概率找到优化问题的全局最优解。第4页，课件共38页，创作于2023年2月1.3遗传算法的基本步骤

GA是基于生物自然选择与遗传机理的一种随机搜索算法，与传统搜索算法不同，GA从一组随机产生的称为“种群(population)”的初始解开始嫂索过程。种群中的每个个体是问题的一个解，称为“染色体(chromosome)”。染色体是一串符号，比如一个二进制字符串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用“适值(fitness)”来测量染色体的好坏，生成的下一代染色体称为后代(offspring)。后代是由前一代染色体通过交叉(crossover)或者变异(mutation)运算形成的。在新一代形成过程中，根据适值的大小选择部分后代，淘汰部分后代．从而保持种群大小是常数。适值高的染色体被选中的概率较高，这样经过若干代之后．算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。第5页，课件共38页，创作于2023年2月1.4GA基本构成要素输入参数:染色体个数N,交叉概率Pc,变异概率Pm;通过初始化过程产生N个染色体;计算所有染色体的评价函数;根据评价函数抽样选择染色体;对染色体进行交叉和变异操作;重复若干次(下一代的代数)计算评价函数、选择、交叉和变异.设计表示问题的染色体生成初始染色体计算每个染色体的适应度是否满足算法停止条件选择高适应度染色体进行复制交叉变异

停止输出最优解GA流程图第6页，课件共38页，创作于2023年2月1.5遗传算法中的基本概念和术语

遗传算法中使用的基本概念和术语如下：

染色体——遗传物质的主要载体，指多个基因的集合。

基因——控制生物性状的遗传物质的功能和结构的基本单元，又称遗传因子。

基因型——它是性状染色体的内部表现，或者说，由遗传因子组合的模式，称为基因型。

表现型——它是由染色体决定性状的外部表现，或者说，根据遗传因子形成的个体，称为表现型。

个体——指染色体带有特征的实体称为个体；

群体——染色体带有特征的个体的集合，称为群体，该集合内的个体数目称为群体规模。

适应度函数——各个个体自适应环境的程度函数，称为适应值函数或适应度函数。

选择——用某种方法从群体中选取若干个体的操作称为选择。

交叉——把两个染色体重新组合的操作称为交叉，又称杂交。

变异——让遗传因子以一定的概率变化的操作称为变异。

编码——从表现型到基因型的映射称为编码。

解码(释码)——从基因型到表现型的映射称为解码。第7页，课件共38页，创作于2023年2月1.6GA的3个基本算子:①选择(selection)：选择算子从群体中按某一概率选择个体,某个体Xi被选择的概率Pi与其适应值成正比.最通常的实现方法是轮盘赌(roulettewheel)模型.②交叉(crossover)：交叉算子将被选中的2个个体的基因链按概率Pc

进行交叉,生成2个新的个体,交叉位置是随机的.其中Pc

是一个系统参数,即交叉概率.③变异(mutation)：变异算子按一定概率Pm

将新个体的基因链的各位进行变异,对二值基因链(0,1编码)来说即是取反.Pm

也是一个系统参数,即变异概率.以上各种算子的实现方法是多种多样的,而且许多高级算子正不断提出,以改进GA的某些性能.第8页，课件共38页，创作于2023年2月选择选择的方法根据不同的优化问题有多种方案，这里介绍适应度函数值比例选择法适应度函数值比例法，又称转轮法，这种方法是利用比例于各个个体适应度函数值的概率来决定其后代的遗传可能性。若某个个体，被选取的选择概率Psi表示为式中，fi为个体i的适应度函数值，N为群体中的个体数目。表1-1给出了4个个体，每个个体对应的适应度函数值及用适应度函数值比例法表示的选择概率(以下简称为选择率)。当选择率确定后，用随机变量试验，产生0～1区间内的随机数。由那个随机变量值决定哪个个体被选取，于是选择率大的个体就能多次被选中和参加交配，它的遗传因子就会在群体中扩大。第9页，课件共38页，创作于2023年2月表1一1个体及其适应度函数值和选择率编号个体适应度函数值选择率1011011690.1442110005760.492301000640.0554100113610.309

最简单的方法是根据[0，1]区间内的均匀分布的随机变量的试验值进行选择，即将[0，1]区间按群体中N个数字串的选择率分为N个小区间，若随机变量值落入哪个小区间，则相应的个体被选中。例如，表1-1所示的群体，按其对应的选择率所描述的区间，表示如图1-1。若第1次试验，随机变量值为0.34，图中个体1和2的选择率之和即0.144+0.492-0.636>0.34，随机变量值0.34落于个体2所在区间，则个体2被选中；若第2次试验，随机变量值为0.86，落于图中个体4所在区间，则个体4被选中。如此重复，做N次试验，依据随机变量值选出N个个体，被选中的N个个体中会有重复，例如个体2就可能被选中多次，将选出的N个个体放入交配池中，就可以进行交叉操作了。第10页，课件共38页，创作于2023年2月交叉操作交叉是遗传算法中的一个重要算子。交叉是将两个染色体重新组合的操作。交叉操作可以产生新的个体，从而需要检测搜索空间中新的点。选择操作每次仅作用在一个个体上，而交叉操作每次作用在从交配池中随机选取的两个个体上。交叉操作产生两个子代个体，它们一般与其父代个体不同，并且彼此也不同，每个子代个体都包含两个父代个体的遗传物质。交叉操作分为一点交叉、多点交叉和一致交叉等。一点交叉操作的一个重要特性是，它可以产生与原配对个体完全不同的子代个体；另一个重要特性是，它不会改变原配对个体中相同位置上的值。需要指出的是，当两个配对个体完全相同时，交叉是不起作用的。交叉操作分两步进行，首先按照某种方法，随机地从交配池中取出要交叉的一对个体，然后进行交叉，产生一对新的个体。交叉的方法是，先根据个体数字串长度L，随机产生一个交叉位置，即[1，L-1]区间上的一个整数，然后在这个位置上，将双亲的基因码链截断，最后互换尾部。例如,交叉前(双亲)A1=1100|0A2=1001|1式中，符号“|”表示交叉位置，位于数字串上的第4位后。这里的双亲A1和A2，以及交叉位置都是随机选取的。交叉后(后代)A'1=1100|1A'2=1001|0可以看出，后代A'1、A'2和双亲A1、A2都不相同,且后代A'1和A'2也不相同。第11页，课件共38页，创作于2023年2月变异操作变异是遗传算法中的又一重要算子，它模拟了生物进化过程中偶然的基因突变现象。基因变异能增加群体中个体的多样性。变异是以一很小的概率Pm从群体A(t)中随机选取若干个体，对于选中的个体又随机选取染色体中的某一位或多位进行数码翻转，对于二进制数字串就是某一位置上的值1变为0或值0变为1。例如，个体A

变异位置

变异前A=11001

变异后A’=11011在本例中，个体A和变异位置都是随机选取的。第12页，课件共38页，创作于2023年2月1.7系统参数的选取一般遵循以下原则:①种群数目N

种群数目会影响GA的有效性.N太小,GA会很差或根本找不出问题的解,因为太小的种群数目不能提供足够的采样点;N太大,会增加计算量,使收敛时间延长.一般种群数目在20～160之间比较合适.②交叉概率Pc

此参数控制着交叉操作的频率.Pc太大,会使高适应值的结构很快破坏掉;Pc

太小,搜索会停滞不前.一般Pc

取0.25～0.75.③变异概率Pm

它是增大种群多样性的第二因素.Pm

太小,不会产生新的基因块;Pm

太大,会使GA变成随机搜索.一般Pm

取0.01～0.20.第13页，课件共38页，创作于2023年2月2遗传算法工具箱(GAToolbox)2.1遗传算法函数遗传算法工具箱GAOT包括了许多实用的函数,这些函数按照功能可以分为以下几类:主界面函数、选择函数、演化函数、其它的一些终止函数、二进制表示函数、演示程序等等.2.2遗传算法函数的参数

MATLAB的遗传算法工具箱GA其主程序ga.m提供了遗传算法工具箱与外部的接口。在MATLAB环境下执行ga并设定相应的参数,就可以完成优化。第14页，课件共38页，创作于2023年2月(1)初始种群的生成函数

function[pop]=initializega(num,bounds,eevalFN,eevalOps,options)[输出参数]：

pop—生成的初始种群;[输入参数]：

num—种群中的个体数目;bounds—代表变量的上下界的矩阵;eevalFN—适应度函数;eevalOps—传递给适应度函数的参数;options—选择编码形式(浮点编码或是二进制编码)；

[precisionF-or-B],其中precision为变量进行二进制编码时指定的精度;F-or-B为1时选择浮点编码，否则为二进制编码,并由precision指定精度.第15页，课件共38页，创作于2023年2月(2)主程序ga.mfunction[x,endPop,bPop,traceInfo]=ga(bounds,evalFN,evalOps,startPop,opts,⋯termFN,termOps,selectFN,selectOps,⋯xOverFNs,xOverOps,mutFNs,mutOps)[输出参数]x、endPop、bPop、traceInfo;x求得的最好的解，包括染色体和适应度endPop最后一代染色体（可选择的）bPop最好染色体的轨迹（可选择的）traceInfo每一代染色体中最好的个体和平均适应度（可选择的）第16页，课件共38页，创作于2023年2月[输入参数](1)bounds(2)evalFN(3)evalOps(4)startPop(5)opts(6)termFN(7)termOps(8)selectFN(9)selectOps(10)xOverFNs(11)xOverOps(12)mutFNs(13)mutOpsBounds变量上下界的矩阵，矩阵的行数确定变量的个数evalFN适应度函数evalOps传递给适应度函数的参数，默认值为(NULL)startPop初始染色体opts一个向量[epsilonprob_opsdisplay],这里epsilon表示两代之间的差距;prob_ops取0表示二进制编码,取1表示浮点数编码;display取0表示运行中不输出,取1表示运行中显示输出.默认值为[1e-610]termFN终止函数的名称，默认值为[‘maxGenTerm’]termOps传递给终止函数的参数，默认值为[100]selectFn选择函数的名称，默认值为[‘normGeomSelect’]selectOps传递给选择函数的参数，默认值为[0.08]xOverFNs交叉函数名称表，二进制编码默认值为[‘simpleXover’],浮点数编码默认值为[‘arithXoverheuristicXoversimpleXover’]xOverOps传递给交叉函数参数表，二进制编码默认值为[0.6],浮点数编码默认值为[20;23;20]mutFNs变异函数名称表,二进制编码默认值为[‘binaryMutation’],浮点数编码默认值为[‘boundaryMutationmultiNonUnifMutationnonUnifMutationunifMutation’]mutOps传递给变异函数参数表,二进制编码默认值为[0.05],浮点数编码默认值为[40;61003;41003;400]第17页，课件共38页，创作于2023年2月(3)有关函数名称和功能初始化函数initializega.m二进制格式和浮点数格式的初始化函数initializeoga.m有序数据的初始化函数选择函数roulette.m常用的轮盘赌法normGeomSelect.m基于归一化的优先选择法tourmSelect.m竞争选择法演化函数交叉simpleXover.m二进制格式货浮点数格式的交叉函数cyclicXover.mlinerXover.mlinerorderXover.m有序数据的交叉函数，可以将演化函数组合使用变异boundaryMutation.m浮点数格式的变异函数nonUnifMutation.m终止函数maxGenTerm.moptMaxGenTerm主程序ga.m用来判断是否满足终止条件二进制表示函数calcbits.m用来计算遗传算法满足精度要求时，染色体所需要的二进制位数f2b.mb2f.m用来完成二进制数和浮点数之间的相互转换第18页，课件共38页，创作于2023年2月[例题1]求f(x)=1/[(x-0.2)^2+0.01]+1/[(x-0.8)^2+0.04]-4

的最大值,其中-1≤x≤2.[分析]选择二进制编码,种群中的个体数目为10,二进制编码长度为20,交叉概率为0.6,变异概率为0.1.(1)编写目标函数存储为fbgalw.m文件:function[sol,val]=GAfyh_1(sol,options)x=sol(1);val=1/[(x-0.2)^2+0.01]+1/[(x-0.8)^2+0.04]-4;3应用实例第19页，课件共38页，创作于2023年2月(2)调用主函数ga.m程序如下:%FileName:GAfyh_2clc,clearfplot('1/[(x-0.2)^2+0.01]+1/[(x-0.8)^2+0.04]-4',[-1,2])holdoninitPop=initializega(10,[-1,2],'GAfyh_1');plot(initPop(:,1),initPop(:,2),'b*')xlabel('x');ylabel('f(x)');holdon[x,endPop,bpop,trace]=ga([-1,2],'GAfyh_1',[],initPop,[1e-6,1,1],...'maxGenTerm',80,'normGeomSelect',[0.1],['arithXover'],[2],...'nonUnifMutation',[2,80,3])plot(endPop(:,1),endPop(:,2),'y*')figure(2)plot(trace(:,1),trace(:,3),'y-')holdonplot(trace(:,1),trace(:,2),'r-')xlabel('generation');ylabel('Fittness');legend('解的变化','种群平均值的变化');第20页，课件共38页，创作于2023年2月（3）运行结果>>GAfyh_2135.6230112370.0533104598.335044678910111213141598.351952161718192098.3854072198.4528332298.499881232425262728293031323334353637383998.5004224098.50099441424398.5013804498.50140145464748495051525354555698.50140857585960616263646566676869707172737475767778798098.501409第21页，课件共38页，创作于2023年2月x=0.200498.5014endPop=0.200498.50140.200498.50140.200498.50140.200498.50140.200498.50140.200498.50140.200498.50140.200498.50140.200498.50140.200498.5014bpop=1.00000.334135.62303.00000.137670.05335.00000.196398.335015.00000.196598.352020.00000.197098.385421.00000.202698.452822.00000.200898.499939.00000.200198.500440.00000.200298.501043.00000.200398.501444.00000.200498.501456.00000.200498.501480.00000.200498.5014第22页，课件共38页，创作于2023年2月trace=1.000035.62309.233014.56942.000035.623020.233717.26713.000070.053332.390320.70384.000070.053343.893719.13685.000098.335066.070622.53526.000098.335065.205924.21997.000098.335074.357022.11388.000098.335082.245110.49049.000098.335086.04579.009310.000098.335079.624224.2394

…….20.000098.385495.15407.2491

……..30.000098.499991.256622.9052

…….40.000098.501098.42750.1732

…….50.000098.501498.45170.1370

……60.000098.501498.48280.0578

…….70.000098.501498.50130.000471.000098.501498.50140.000072.000098.501498.50120.000573.000098.501498.50140.000074.000098.501498.50140.000075.000098.501498.50140.000076.000098.501498.50140.000077.000098.501498.50140.000078.000098.501498.50140.000079.000098.501498.50140.000080.000098.501498.50140第23页，课件共38页，创作于2023年2月

如图2和图3所示,图2中标有“*”记号的点为初始值,标有“o”的点为最优值.最优解为

x*=0.20038,fmax=98.501409图2

100次迭代后的寻优结果第24页，课件共38页，创作于2023年2月图3遗传算法的寻优性能第25页，课件共38页，创作于2023年2月[例题2]求f(x)=x+10sin(5x)+7cos(4x)的最大值,其中0≤x≤9[分析

]选择二进制编码,种群中的个体数目为10,二进制编码长度为20,交叉概率为0.95,变异概率为0.08.(1)编写目标函数存储为gademo1eval1.m文件.function[sol,eval]=GAfyh_3(sol,options)x=sol(1);eval=x+10*sin(5*x)+7*cos(4*x);(2)画曲线图：fplot('x+10*sin(5*x)+7*cos(4*x)',[09])(3)随机创建初始种群，大小为10，并在图上表达出来：

initPop=initializega(10,[09],'gademo1eval1');holdonplot(initPop(:,1),initPop(:,2),'g+')第26页，课件共38页，创作于2023年2月(4)调用主函数ga.并作图：[xendPop]=ga([09],'gademo1eval1',[],initPop,[1e-611],'maxGenTerm',25,...'normGeomSelect',[0.08],['arithXover'],[2],'nonUnifMutation',[2253]);%Thebestfoundx%Andplottheresultingtheresultingpopulationplot(endPop(:,1),endPop(:,2),'b*')

运行结果如图4和图5所示，图4中标有“*”记号的点为初始值，标有“+”的点为最优值。最优解为：

x*=7.8569，

fmax=24.8554.第27页，课件共38页，创作于2023年2月图4

25次迭代后的寻优结果第28页，课件共38页，创作于2023年2月（5）画遗传算法的寻优性能曲线figure(2)%Letstakealookattheperformanceofthegaduringtherunplot(trace(:,1),trace(:,3),'r-')holdonplot(trace(:,1),trace(:,2),'k-')xlabel('Generation');ylabel('Fittness');legend('解的变化','种群平均值的变化');迭代次数函数值迭代次数函数值120.1902591124.845763320.5513841524.855317624.2707341624.855361724.4211932524.855361924.7446285024.855361第29页，课件共38页，创作于2023年2月图5遗传算法的寻优性能第30页，课件共38页，创作于2023年2月[例题3]GA在非线性规划中的应用一般非线性规划可描述如下：目标函数Maxf(x)

不等式约束gi(x)≤0,i=1,…,m

等式约束hi(x)=0,i=m+1,…,nx∈ΩGA对染色体做遗传操作通常会产生不可行的后代，因而运用GA解非线性规划的核心是如何满足约束的问题。对于约束条件，常用方法是构造带有惩罚项的适值函数，通过惩罚不可行解，将有约束问题转化