MATLAB实验遗传算法及优化设计

1、实验六遗传算法与优化设计、实验目的1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）2.学习使用Matlab中的遗传算法工具箱（gatool）来解决优化设计问题;、实验原理及遗传算法工具箱介绍1. 一个优化设计例子图1所示是用于传输微波信号的微带线 （电极）的横截面结构示意图,上下两根黑条分别代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质（如空气，陶瓷等）。微带电极的结构参数如图所示，W、t分别是上电极的宽度和厚度,D是上下电极间距。当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。根据微带传输线理论，高频工作状态下（

2、假定信号频率1GHz），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）图1微带线横截面结构以及场分布示意图Rs8.68a = + 50DjW 2( W TV D W ；+-ln fTie (云+0.94jy <"d+ 0.94丿L W兀wI tD丿(1)可见电极的结构参数影响着电极损耗,其中Rs =臥为金属的表面电阻率，F为电阻率。这就是所谓的最优化问题或者称为通过合理设计这些参数可以使电极的欧姆损耗做到最小，规划设计问题。此处设计变量有 3个：W、D、t,它们组成 决策向量W, D ,t T，待优化函数a（W,D,t）称为目标函数。上述优化设计问题可以抽

3、象为数学描述:min f (X )* st.gj(x)兰0,j =12.,P其中=（X1,X2,.,Xn T是决策向量,X1,，Xn为n个设计变量。这是一个单目标的数学其中每一个Vi代表一个基因，染色体的长度m不一定等于设计变量的数目n,取决于染色规划问题：在一组针对决策变量的约束条件gj（<0,j =1,.,p下，使目标函数最小化（有时也可能是最大化，此时在目标函数f（x ）前添个负号即可）。满足约束条件的解 X称为可行解，所有满足条件的 X组成问题的可行解空间。2.遗传算法基本原理和基本操作遗传算法（Genetic Algorithm, GA）是一种非常实用、高效、鲁棒性强的优化技术

4、，广泛应用于工程技术的各个领域 （如函数优化、机器学习、图像处理、生产调度等）。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化算法。按照达尔文的进化论，生物在进化过程中“物竞天择”，对自然环境适应度高的物种被保留下来，适应度差的物种而被淘汰。物种通过遗传将这些好的性状复制给下一代，同时也通过种间的交配（交叉）和变异不断产生新的物种以适应环境的变化。从总体水平上看，生物在进化过程中子代总要比其父代优良，因此生物的进化过程其实就是一个不断产生优良物种的过程，这和优化设计问题具有惊人的相似性，从而使得生物的遗传和进化能够被用于实际的优化设计问题。按照生物学知识，遗传信息一基

5、因（Gene）的载体是染色体（Chromosome），染色体中一定数量的基因按照一定的规律排列（即编码），遗传基因在染色体中的排列位置称为基因座（Locus），在同一个基因座上所有可能的基因就称为等位基因（Allele），生物所持有的基因以及基因的构成形式称为生物的基因型（Genotype），而该生物在环境中所呈现的相应性状称为该生物的 表现型（Phenotype）。在遗传过程中，染色体上的基因能够直接复制给子代从交叉（Crossover）而重组，即两个染色体在某个相同的位置处被截断，其前后两串基因交叉组合而形成两个新的染色体。在基而使得子代具有亲代的特征，此外，两条染色体之间也通过因复制时也

6、会产生微小的 变异（Mutation），从而也产生了新的染色体。因此交叉和变异是产生新物种的主要途径。由于自然选择，在子代群体新产生的物种（或染色体）当中，只有那些对环境 适应度高的才能生存下来，即适应度越高的被选择的概率也越大，然后又是通过遗传和变异再自然选择， 一代一代不断进化。因此生物遗传和进化的基本过程就是：选择（即复制）、交叉和变异。遗传算法就是通过模拟生物进化的这几个基本过程而实现的。编码编码是设计遗传算法首要解决的问题。在生物进化中，选择、交叉、变异这些基本过程都是基于遗传信息的编码方式进行的，即基于染色体的基因型而非表现型，因此要模拟生物进化过程，遗传算法必须首先对问题的可行解

7、X （决策向量）进行某种编码，以便借鉴生物学中染色体和基因等概念。在遗传算法中，将每一个决策向量X用一个染色体 V来表示:X =(X1,.,Xn $ = V =V1,V2,.,Vm（表现型）（基因型）体上基因的编码方式。一般有两种编码方式：二进制编码和浮点数编码。如果是二进制编码，每一个设计变量 Xi的真实值用一串二进制符号0和1按照一定的编码规则来表示，每个二进制符号就代表一个基因， 因此染色体长度要远大于设计变量的数目。这种由二进制编码构Xi用其取值范围成的排列形式 V就是染色体（也称 个体）的基因型，而基因型经过解码后所对应的决策向 量X （即可行解）就是个体的表现型。如果是浮点数编码，

8、每个设计变量Vi,因此个体的编码长度m也就Umin,U Lax 内的一个浮点数表示，构成染色体的一个基因等于决策变量的个数 n由于这种编码方式使用的是决策变量的真实值，所以也称真值编码方法。无论哪种编码方式，所有可能的染色体（个体）V构成问题的搜索空间（种群），遗（后面叙述适应度的计传算法对最优解的搜索就是在搜索空间中搜索适应度最高的染色体 算），因此通过编码将一个问题的可行解从其解空间转换到了遗传算法能够处理的搜索空间。经过个体的编码后，就可以进行遗传算法的基本操作：选择、交叉和变异。 选择（复制）操作生物的进化是以选择也就是复制，是在群体中选择适应度高的个体产生新群体的过程。集团为主体的，

9、与此相应，遗传算法的运算对象是有M个个体或染色体组成的集合，称为种群，M也称为种群规模。遗传算法在模拟自然选择时，以个体的适应度（Fitness）高低为而适应度低的个体遗传到下选择依据，即适应度高的个体被遗传到下一代种群的概率较高,代的概率则相对较低。个体适应度由适应度函数Fit（f（X ）计算，适应度函数总是和个体一种最简单表现型（i.e. X ）的目标函数值f（X）关联，一般是由目标函数经过一定的变换得到。的方法就是直接使用目标函数f（X）作为适应度函数:'f （X ）目标函数最小化问题Fit（f（X）眾l-f （ X ）目标函数最大化问题选定了适应度函数之后，个体适应度也随之确定

10、,则在选择操作时，个体被选中的概率Pi = M三Fi(i =1,2,，M )其中Fi为个体的适应度。这种选择方式称为比例选择，也称轮盘赌选择。除此之外还有多种选择方法，如随机竞争选择、均匀选择、无回放随机选择等，不一一介绍。 交叉操作所谓交叉就是以一定的概率（交叉概率）从群体中选择两个个体（染色体）按照某种方式交 换其部分基因，从而形成两个新的个体。 在遗传算法中它是产生新个体同时也是获得新的优良个体的主要方法，它决定了遗传算法的全局搜索能力。对于不同的编码方式，交叉操作的具体方法也不相同，对于浮点数编码，一般使用算术交叉； 对于二进制编码有单点交叉和多Pc,这个概率表明种群点交叉等方式。不论

11、何种方式，在交叉操作时首先应定义交叉概率中参与交叉的个体数目的期望值是PC ”M，M是种群规模。通常交叉概率应取较大的值,以便产生较多的新个体，增加全局搜索力度。但是Pc过大时优良个体被破坏的可能性也越大，如果Pc太小则搜索进程变慢，影响算法的运行效率。一般建议的取值范围是 0.4-0.99。 变异操作Pm用其遗传算法中的变异操作就是将染色体上某些基因座上的基因以一定的变异概率 他的等位基因替代， 从而形成新的个体。 对于浮点数编码，变异操作就是将变异点处的基因1”变用该基因取值范围内的一个随机数替换。对于二进制编码则是将变异点处的基因由“ 成“ 0”，“0”变成“1”。变异操作也有多种方法，

12、如均匀变异、非均匀变异、高斯变异等。变异操作的概率Pm要比交叉操作的概率 Pc小得多，变异只是产生新个体的辅助手段。但它是遗传算法必不可少的一个环节，因为变异操作决定了算法的局部搜索能力，它弥补了交叉操作无法对搜索空间的细节进行局部搜索的不足,因此交叉和变异操作相互配合共同完成对搜索空间的全局和局部搜索。以上简要介绍了遗传算法的基本原理和操作，归纳起来，基本遗传算法一般可以表示为一个8元组:SGA=（C,E,F0,M ,工甲,T）式中，C个体的编码方法；E个体适应度评价函数；P0初始种群；M种群规模；选择 操作；r交叉操作；普变异操作；T是进化终止代数（进化终止条件）。其中有4个运行参 数需要

13、预先设定：M, T, Pc，Pm种群规模 M 一般取为20100 ；终止代数T 一般取100500 ；交叉概率Pc一般取0.4-0.99;变异概率Pm一般取0.0001-0.1最后给出遗传算法的基本步骤：选择二进制编码或浮点数编码把问题的解表示成（个体），也就是初始种群。计算每一个个体的适应度值，按适者生存的原则，从中选择出适应度较大的 “染色体”进行复制，再通过交叉、“染色体”。随机产生一群“染色体”变异过程产生更适应环境的新一代“染色体”群，即子代。重复第3步。经过这样的一代一代地进化，最后就会收敛到最适应环境（适应度最大）的一个“染色体”（即个体）上，它就是问题的最优解。图 2给出了基本

14、遗传算法设计流程图，其中t代表当前代数，T是进化终止代数。t=l,初始化种群个体适应度计算进化结束*图2基本遗传算法设计流程图3. Matlab遗传算法工具箱（gatool）Matlab的遗传算法工具箱有一个精心设计的图形用户界面，可以帮助用户直观、方便、 快速地利用遗传算法求解最优化问题。在Matlab命令窗口输入命令：gatool可以打开遗传算法工具箱的图形用户界面，如图3所示。GA工具箱的参数设置步骤如下:输入适应度函数输入适应度一 函数中的变量数目开始执行遗f专算法结果彎态显示图3.遗传算法工具示数述 显参描（1）首先，使用遗传算法工具箱必须输入下列信息:Fitness functio

15、n（适应度函数）这里指的是待优化的函数，也即目标函数。该工具箱总是试图寻找目标函数的最小值。输入适应度函数的格式为fitnessfun，其中符号 产生函数fitnessfun的句柄，fitnessfun代表用户编写的计算适应度函数 （目标函数）的M文件名，该M文件的编写方法如下:假定我们要计算Rastrigin函数的最小值2 2f (x1,x2)=20+x1 +X2 -10(cos2；ix1 +cos2；ix2)M函数文件确定这个函数必须接受一个长度为2的行向量X，也即决策向量，向量的长度等于变量数目，行向量X的每个元素分别和变量X1和X2对应。另外 M文件要返回一个标量乙其值等于该函数的值。

16、下面是计算Rastrigin函数的M文件代码:function Z=Ras_fu n(X)Z=20+X(1)A2+X(2)A2-10*(cos(2* pi*X(1)+cos(2* pi*X(2);M文件编写、保存后，再在 gatool工具箱界面Fitness function栏输入 Ras_fun Number of variable（变量个数）2。目标函数中的变量数目，也即适应度函数输入向量的长度。在上例中，它的值是（2）其次，设置遗传算法参数，即Options设置。以下只介绍部分运行参数的设置，其他未提及的参数采用默认设置即可。种群参数（Population ）Population siz

17、e （种群规模）：每一代中的个体数目，一般是20-100之间。种群规模大,算法搜索更彻底，可以增加算法搜索全局最优而非局部最优的概率，但是耗时也更长。variable），第一行是每个变量的下限，第二行是每个变量的上限。如果只输入2©的矩阵，则每个变量的初始搜索范围都一样。注意，初始范围仅限定初始种群中个体Initial range （初始范围）：其值是两行的矩阵，代表初始种群中个体的搜索范围，实际上 是决策向量X中每个变量Xi的初始搜索范围。矩阵的列数等于变量个数（ Number of（或决 策向量）的范围，后续各代中的个体可以不在初始范围之内。初始范围不能设置太小， 否则造成个体之

18、间的差异过小，即种群的多样性降低，不利于算法搜索到最优解。复制参数(Reproduction )0.40.99，默认 0.8。100500，默认是 100。当遗传算法运行到该参Crossover fraction （交叉概率）：一般取算法终止准则（Stopping Criteria提供了 5种算法终止条件:Gen eratio ns：最大的进化代数，一般取数指定的世代，计算终止。Inf （无穷大）。计算终止。缺省是-Inf。Time limit :指明算法终止执行前的最大时间，单位是秒。缺省是Fitness limit（适应度限）：当最优适应度值小于或等于此参数值时,Stall gen era

19、tio n（停滞代数）：如果每一代的最佳适应度值在该参数指定的代数没有改善, 则终止计算。缺省是50代。Stall time（停滞时间）：如果每一代的最佳适应度值在该参数指定的时间间隔内没有改 善，则终止计算。缺省是20秒。（3）设置绘图参数，即 Plots设置。绘图参数（Plots）工作时可以从遗传算法得到图形数据。当选择各种绘图参数并执行遗传算法时，一个图形窗口在分离轴上显示这些图形。下面介绍其中2个参数Best fitn ess：选择该绘图参数时，将绘制每一代的最佳适应度值和进化世代数之间的关系图，如图4的上图所示。图中蓝色点代表每一代适应度函数的平均值，黑色点代表每一代的最佳值。Dis

20、ta nee:选择此参数时，绘制每一代中个体间的平均距离。它反映个体之间的差异程度，所以可用来衡量种群的多样性。图4的下图显示的即是每一代个体间的平均距离。20304D5060Generation708090100Best 0.00089516 Mean 0.0611227Average Distance Benween Individuals20SO4。5060Generation70SO90100(4)执行算法：参数设置好了之后，点击工具箱界面上的按钮“Star”执行求解器。在算法运行的同时，“Curre nt gen eration (当前代数)”文本框中显示当前的进化代数。通过单击&q

21、uot;Pause”按钮可以使计算暂停，之后再点击“ Resume可以恢复计算。当计算完成时，“Status and results”窗格中出现如图 5所示的情形。Status and results:IGh ruMtinfi.GA ttrminated-Fitness function value_ 0. 003909079476933379Optinii lati on terminated： maciimum number o£ generati ons eKceeded.<|Final Point:1 2其中包含下列信息:算法终止时适应度函数的最终值一即目标函数的最优值

22、Fit ness fun ctio n value: 0.003909079476983379算法终止原因Op timizati on term in ated: maximum nu mber of gen erati ons exceeded/ 超出最大进化世代数 ） 最终点一即目标函数的最优解X1 X2 = -0.004-0.00193（两个变量的例子）三、实验内容1. Rastrigin函数的最小值问题函数表达式如 式，函数图像如下图6所示，它有多个局部极小值，但是只有一个全局最小值。Rastrigin函数的全局最小值的精确解是0,出现在X1 X2=0 0处。使用遗传算法工具箱近似求解Rastrigin函数的最小值首先编写计算适应度函数的 M文件，然后设置运行参数（绘图参数Plots勾选Best fitness 和Distanee两项，其它参数可以使用默认值），执行求解器（Run solver）计算Rastrigin函数 的最优值。观察种群多样性对优化结果的影响决定遗传算法的一个重要性能是种群的多样性。个体之间的距离越大，则多样性越高；反之则多样性越低。多样性过高或过低遗传算法都可能运行不好。通过实验调整Population（种群）的Initial range（初始范围）参数可得到种群适当的多样性。取Initial range参数值1; 1.1观察Rastr