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

实验六 遗传算法与优化设计一、实验目的1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）；2. 学习使用Matlab中的遗传算法工具箱(gatool)来解决优化设计问题；二、实验原理及遗传算法工具箱介绍1. 一个优化设计例子图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图，上下两根黑条分别代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质(如空气，陶瓷等)。微带电极的结构参数如图所示，W、t分别是上电极的宽度和厚度，D是上下电极间距。当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。根据微带传输线理论，高频工作状态下（假定信号频率1GHz），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）： 图1 微带线横截面结构以及场分布示意图 (1)其中为金属的表面电阻率，r为电阻率。可见电极的结构参数影响着电极损耗，通过合理设计这些参数可以使电极的欧姆损耗做到最小，这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个：W、D、t，它们组成决策向量W, D ,t T，待优化函数称为目标函数。上述优化设计问题可以抽象为数学描述： (2) 其中是决策向量，x1，xn为n个设计变量。这是一个单目标的数学规划问题：在一组针对决策变量的约束条件下，使目标函数最小化（有时也可能是最大化，此时在目标函数前添个负号即可）。满足约束条件的解X称为可行解，所有满足条件的X组成问题的可行解空间。2. 遗传算法基本原理和基本操作遗传算法(Genetic Algorithm, GA)是一种非常实用、高效、鲁棒性强的优化技术，广泛应用于工程技术的各个领域(如函数优化、机器学习、图像处理、生产调度等)。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化算法。按照达尔文的进化论，生物在进化过程中“物竞天择”，对自然环境适应度高的物种被保留下来，适应度差的物种而被淘汰。物种通过遗传将这些好的性状复制给下一代，同时也通过种间的交配(交叉)和变异不断产生新的物种以适应环境的变化。从总体水平上看，生物在进化过程中子代总要比其父代优良，因此生物的进化过程其实就是一个不断产生优良物种的过程，这和优化设计问题具有惊人的相似性，从而使得生物的遗传和进化能够被用于实际的优化设计问题。按照生物学知识，遗传信息基因(Gene)的载体是染色体(Chromosome)，染色体中一定数量的基因按照一定的规律排列（即编码），遗传基因在染色体中的排列位置称为基因座（Locus），在同一个基因座上所有可能的基因就称为等位基因（Allele），生物所持有的基因以及基因的构成形式称为生物的基因型（Genotype），而该生物在环境中所呈现的相应性状称为该生物的表现型（Phenotype）。在遗传过程中，染色体上的基因能够直接复制给子代从而使得子代具有亲代的特征，此外，两条染色体之间也通过交叉(Crossover)而重组，即两个染色体在某个相同的位置处被截断，其前后两串基因交叉组合而形成两个新的染色体。在基因复制时也会产生微小的变异（Mutation），从而也产生了新的染色体。因此交叉和变异是产生新物种的主要途径。由于自然选择，在子代群体新产生的物种（或染色体）当中，只有那些对环境适应度高的才能生存下来，即适应度越高的被选择的概率也越大，然后又是通过遗传和变异再自然选择，一代一代不断进化。因此生物遗传和进化的基本过程就是：选择(即复制)、交叉和变异。遗传算法就是通过模拟生物进化的这几个基本过程而实现的。 编码编码是设计遗传算法首要解决的问题。在生物进化中，选择、交叉、变异这些基本过程都是基于遗传信息的编码方式进行的，即基于染色体的基因型而非表现型，因此要模拟生物进化过程，遗传算法必须首先对问题的可行解X（决策向量）进行某种编码，以便借鉴生物学中染色体和基因等概念。在遗传算法中，将每一个决策向量X用一个染色体V来表示： (3)其中每一个vi代表一个基因，染色体的长度m不一定等于设计变量的数目n，取决于染色体上基因的编码方式。一般有两种编码方式：二进制编码和浮点数编码。如果是二进制编码，每一个设计变量xi的真实值用一串二进制符号0和1按照一定的编码规则来表示，每个二进制符号就代表一个基因，因此染色体长度要远大于设计变量的数目。这种由二进制编码构成的排列形式V就是染色体（也称个体）的基因型，而基因型经过解码后所对应的决策向量X（即可行解）就是个体的表现型。如果是浮点数编码，每个设计变量用其取值范围内的一个浮点数表示，构成染色体的一个基因vi，因此个体的编码长度m也就等于决策变量的个数n，由于这种编码方式使用的是决策变量的真实值，所以也称真值编码方法。无论哪种编码方式，所有可能的染色体（个体）V构成问题的搜索空间（种群），遗传算法对最优解的搜索就是在搜索空间中搜索适应度最高的染色体(后面叙述适应度的计算)，因此通过编码将一个问题的可行解从其解空间转换到了遗传算法能够处理的搜索空间。经过个体的编码后，就可以进行遗传算法的基本操作：选择、交叉和变异。 选择(复制)操作选择也就是复制，是在群体中选择适应度高的个体产生新群体的过程。生物的进化是以集团为主体的，与此相应，遗传算法的运算对象是有M个个体或染色体组成的集合，称为种群，M也称为种群规模。遗传算法在模拟自然选择时，以个体的适应度（Fitness）高低为选择依据，即适应度高的个体被遗传到下一代种群的概率较高，而适应度低的个体遗传到下一代的概率则相对较低。个体适应度由适应度函数计算，适应度函数总是和个体表现型(i.e. X )的目标函数值f(X)关联，一般是由目标函数经过一定的变换得到。一种最简单的方法就是直接使用目标函数f(X)作为适应度函数： (4)选定了适应度函数之后，个体适应度也随之确定，则在选择操作时，个体被选中的概率 (5)其中Fi为个体的适应度。这种选择方式称为比例选择，也称轮盘赌选择。除此之外还有多种选择方法，如随机竞争选择、均匀选择、无回放随机选择等，不一一介绍。 交叉操作所谓交叉就是以一定的概率(交叉概率)从群体中选择两个个体(染色体)按照某种方式交换其部分基因，从而形成两个新的个体。在遗传算法中它是产生新个体同时也是获得新的优良个体的主要方法，它决定了遗传算法的全局搜索能力。对于不同的编码方式，交叉操作的具体方法也不相同，对于浮点数编码，一般使用算术交叉；对于二进制编码有单点交叉和多点交叉等方式。不论何种方式，在交叉操作时首先应定义交叉概率Pc，这个概率表明种群中参与交叉的个体数目的期望值是，M是种群规模。通常交叉概率应取较大的值，以便产生较多的新个体，增加全局搜索力度。但是Pc过大时优良个体被破坏的可能性也越大，如果Pc太小则搜索进程变慢，影响算法的运行效率。一般建议的取值范围是0.40.99。 变异操作遗传算法中的变异操作就是将染色体上某些基因座上的基因以一定的变异概率Pm用其他的等位基因替代，从而形成新的个体。对于浮点数编码，变异操作就是将变异点处的基因用该基因取值范围内的一个随机数替换。对于二进制编码则是将变异点处的基因由“1”变成“0”，“0”变成“1”。变异操作也有多种方法，如均匀变异、非均匀变异、高斯变异等。变异操作的概率Pm要比交叉操作的概率Pc小得多，变异只是产生新个体的辅助手段。但它是遗传算法必不可少的一个环节，因为变异操作决定了算法的局部搜索能力，它弥补了交叉操作无法对搜索空间的细节进行局部搜索的不足，因此交叉和变异操作相互配合共同完成对搜索空间的全局和局部搜索。 以上简要介绍了遗传算法的基本原理和操作，归纳起来，基本遗传算法一般可以表示为一个8元组： (6)式中，C 个体的编码方法；E 个体适应度评价函数；P0 初始种群；M 种群规模；F 选择操作；G 交叉操作；Y 变异操作；T 是进化终止代数(进化终止条件)。其中有4个运行参数需要预先设定：M, T, Pc，Pm 种群规模M一般取为20100； 终止代数T一般取100500；交叉概率Pc一般取0.40.99； 变异概率Pm一般取0.00010.1最后给出遗传算法的基本步骤： 选择二进制编码或浮点数编码把问题的解表示成“染色体”。 随机产生一群“染色体”(个体)，也就是初始种群。 计算每一个个体的适应度值，按适者生存的原则，从中选择出适应度较大的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群，即子代。 重复第3步。经过这样的一代一代地进化，最后就会收敛到最适应环境（适应度最大）的一个“染色体”(即个体)上，它就是问题的最优解。图2给出了基本遗传算法设计流程图，其中t代表当前代数，T是进化终止代数。图2 基本遗传算法设计流程图3. Matlab遗传算法工具箱(gatool) Matlab的遗传算法工具箱有一个精心设计的图形用户界面，可以帮助用户直观、方便、快速地利用遗传算法求解最优化问题。在Matlab命令窗口输入命令：gatool可以打开遗传算法工具箱的图形用户界面，如图3所示。GA工具箱的参数设置步骤如下：图3. 遗传算法工具(1) 首先，使用遗传算法工具箱必须输入下列信息： Fitness function(适应度函数) 这里指的是待优化的函数，也即目标函数。该工具箱总是试图寻找目标函数的最小值。输入适应度函数的格式为fitnessfun，其中符号产生函数fitnessfun的句柄，fitnessfun代表用户编写的计算适应度函数(目标函数)的M文件名，该M文件的编写方法如下：假定我们要计算Rastrigin函数的最小值 (7)M函数文件确定这个函数必须接受一个长度为2的行向量X，也即决策向量，向量的长度等于变量数目，行向量X的每个元素分别和变量x1和x2对应。另外M文件要返回一个标量Z，其值等于该函数的值。下面是计算Rastrigin函数的M文件代码：function Z=Ras_fun(X) Z=20+X(1)2+X(2)2-10*(cos(2*pi*X(1)+cos(2*pi*X(2);M文件编写、保存后，再在gatool工具箱界面Fitness function栏输入 Ras_fun Number of variable(变量个数)目标函数中的变量数目，也即适应度函数输入向量的长度。在上例中，它的值是2。(2) 其次，设置遗传算法参数，即Options设置。 以下只介绍部分运行参数的设置，其他未提及的参数采用默认设置即可。 种群参数(Population) l Population size (种群规模)： 每一代中的个体数目，一般是20-100之间。种群规模大，算法搜索更彻底，可以增加算法搜索全局最优而非局部最优的概率，但是耗时也更长。l Initial range (初始范围)：其值是两行的矩阵，代表初始种群中个体的搜索范围，实际上是决策向量X中每个变量xi的初始搜索范围。矩阵的列数等于变量个数（Number of variable），第一行是每个变量的下限，第二行是每个变量的上限。如果只输入21的矩阵，则每个变量的初始搜索范围都一样。注意，初始范围仅限定初始种群中个体(或决策向量)的范围，后续各代中的个体可以不在初始范围之内。初始范围不能设置太小，否则造成个体之间的差异过小，即种群的多样性降低，不利于算法搜索到最优解。 复制参数(Reproduction)l Crossover fraction (交叉概率)：一般取0.40.99，默认0.8。 算法终止准则(Stopping Criteria)提供了5种算法终止条件：l Generations：最大的进化代数，一般取100500，默认是100。当遗传算法运行到该参数指定的世代，计算终止。l Time limit：指明算法终止执行前的最大时间，单位是秒。缺省是Inf（无穷大）。l Fitness limit(适应度限)：当最优适应度值小于或等于此参数值时，计算终止。缺省是-Inf。l Stall generation(停滞代数)：如果每一代的最佳适应度值在该参数指定的代数没有改善，则终止计算。缺省是50代。l Stall time(停滞时间)： 如果每一代的最佳适应度值在该参数指定的时间间隔内没有改善，则终止计算。缺省是20秒。(3) 设置绘图参数，即Plots设置。绘图参数（Plots）工作时可以从遗传算法得到图形数据。当选择各种绘图参数并执行遗传算法时，一个图形窗口在分离轴上显示这些图形。下面介绍其中2个参数l Best fitness： 选择该绘图参数时，将绘制每一代的最佳适应度值和进化世代数之间的关系图，如图4的上图所示。图中蓝色点代表每一代适应度函数的平均值，黑色点代表每一代的最佳值。l Distance： 选择此参数时，绘制每一代中个体间的平均距离。它反映个体之间的差异程度，所以可用来衡量种群的多样性。图4的下图显示的即是每一代个体间的平均距离。图4(4) 执行算法：参数设置好了之后，点击工具箱界面上的按钮“Star”执行求解器。在算法运行的同时，“Current generation（当前代数）”文本框中显示当前的进化代数。通过单击“Pause”按钮可以使计算暂停，之后再点击“Resume”可以恢复计算。当计算完成时，“Status and results”窗格中出现如图5所示的情形。图5其中包含下列信息： 算法终止时适应度函数的最终值即目标函数的最优值Fitness function value: 0.003909079476983379 算法终止原因Optimization terminated: maximum number of generations exceeded.(超出最大进化世代数) 最终点即目标函数的最优解x1 x2 = -0.004 -0.00193（两个变量的例子）三、实验内容1. Rastrigin函数的最小值问题 函数表达式如(7)式，函数图像如下图6所示，它有多个局部极小值，但是只有一个全局最小值。Rastrigin函数的全局最小值的精确解是0，出现在x1 x2=0 0处。图6 Rastrigin函数图像 使用遗传算法工具箱近似求解Rastrigin函数的最小值首先编写计算适应度函数的M文件，然后设置运行参数（绘图参数Plots勾选Best fitness和Distance两项，其它参数可以使用默认值），执行求解器（Run solver）计算Rastrigin函数的最优值。 观察种群多样性对优化结果的影响决定遗传算法的一个重要性能是种群的多样性。个体之间的距离越大，则多样性越高；反之则多样性越低。多样性过高或过低遗传算法都可能运行不好。通过实验调整Population(种群)的Initial range(初始范围)