MATLAB试验遗传算法与优化设计

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

2、较大的欧姆损耗。根据微带传输线理论，高频工作状态下（假定信号频率 1GHZ）,电极 的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加） ： 其中Rs = ； “0二为金属的表面电阻率，二为电阻率。可见电极的结构参数影响着电极损耗， 通过合理设计这些参数可以使电极的欧姆损耗做到最小， 这就是所谓的最优化问题或者称为 规划设计问题。此处设计变量有 3个：W D t，它们组成决策向量W, D ,t T,待优化函 数一:s（W, D, t）称为目标函数。 上述优化设计问题可以抽象为数学描述： min f (X ) * st. gj(X )兰0,j =1,2,，p 图1微带线横截面结构以及

3、场分布示意图 (1) 1欢迎下载 精品文档 其中X = （xx2 ,.,xn T是决策向量，xi,，xn为n个设计变量。这是一个单目标的数学 规划问题：在一组针对决策变量的约束条件 gX 0,j =1,.,p下，使目标函数最小化（有时 也可能是最大化，此时在目标函数f X前添个负号即可）。满足约束条件的解 X 称为可行解， 所有满足条件的 X 组成问题的可行解空间。 2. 遗传算法基本原理和基本操作 遗传算法（Genetic Algorithm, GA） 是一种非常实用、高效、鲁棒性强的优化技术，广 泛应用于工程技术的各个领域 （如函数优化、机器学习、图像处理、 生产调度等）。遗传算法 是模拟

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

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

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

7、决策向量）进行某种编码，以便借鉴生物 学中染色体和基因等概念。在遗传算法中，将每一个决策向量 X用一个染色体 V来表示： X hX1,.,Xn 二 V -V1,V2,.,Vm r （3） （表现型） （基因型） 2欢迎下载 精品文档 其中每一个Vi代表一个基因，染色体的长度 m不一定等于设计变量的数目 n,取决于染色体 上基因的编码方式。一般有两种编码方式：二进制编码和浮点数编码。如果是二进制编码， 每一个设计变量 Xi的真实值用一串二进制符号 0和1按照一定的编码规则来表示，每个二 进制符号就代表一个基因， 因此染色体长度要远大于设计变量的数目。 这种由二进制编码构 成的排列形式 V就是染色

8、体（也称个体）的基因型，而基因型经过解码后所对应的决策向量 X （即可行解）就是个体的表现型。如果是浮点数编码，每个设计变量 xi用其取值范围 Umin，U max 1内的一个浮点数表示，构成染色体的一个基因 Vi，因此个体的编码长度 m也就 等于决策变量的个数 n,由于这种编码方式使用的是决策变量的真实值，所以也称真值编码 方法。无论哪种编码方式，所有可能的染色体（个体） V构成问题的搜索空间（种群），遗 传算法对最优解的搜索就是在搜索空间中搜索适应度最高的染色体 （后面叙述适应度的计 算），因此通过编码将一个问题的可行解从其解空间转换到了遗传算法能够处理的搜索空间。 经过个体的编码后，就可

9、以进行遗传算法的基本操作：选择、交叉和变异。 选择（复制）操作 选择也就是复制，是在群体中选择适应度高的个体产生新群体的过程。 生物的进化是以 集团为主体的，与此相应，遗传算法的运算对象是有 M个个体或染色体组成的集合，称为种 群，M也称为种群规模。遗传算法在模拟自然选择时，以个体的适应度（ Fitness ）高低为 选择依据，即适应度高的个体被遗传到下一代种群的概率较高， 而适应度低的个体遗传到下 一代的概率则相对较低。 个体适应度由适应度函数 Fit f X计算， 适应度函数总是和个体 表现型（i.e. X ）的目标函数值f（X）关联，一般是由目标函数经过一定的变换得到。一种最 简单的方法

10、就是直接使用目标函数 f（X）作为适应度函数： 选定了适应度函数之后，个体适应度也随之确定，则在选择操作时，个体被选中的概率 其中Fi为个体的适应度。这种选择方式称为比例选择，也称轮盘赌选择。除此之外还有多 种选择方法，如随机竞争选择、均匀选择、无回放随机选择等，不一一介绍。 f X 目标函数最小化问题 Fit f X = -f X目标函数最大化问题 ， 交叉操作 所谓交叉就是以一定的概率 （交叉概率）从群体中选择两个个体 （染色体）按照某种方式 交换其部分基因，从而形成两个新的个体。 在遗传算法中它是产生新个体同时也是获得新的 3欢迎下载 精品文档 优良个体的主要方法， 它决定了遗传算法的全

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

12、成新的个体。 对于浮点数编码，变异操作就是将变异点处的基因 用该基因取值范围内的一个随机数替换。对于二进制编码则是将变异点处的基因由“ 1”变 成“ 0”，“0”变成“1”。变异操作也有多种方法，如均匀变异、非均匀变异、高斯变异等。 变异操作的概率 Pm要比交叉操作的概率 Pc小得多，变异只是产生新个体的辅助手段。 但它是遗传算法必不可少的一个环节， 因为变异操作决定了算法的局部搜索能力， 它弥补了 交叉操作无法对搜索空间的细节进行局部搜索的不足， 因此交叉和变异操作相互配合共同完 成对搜索空间的全局和局部搜索。 以上简要介绍了遗传算法的基本原理和操作，归纳起来，基本遗传算法一般可以表示 为一

13、个8元组： SGA二 C,E,Po,M,：，？，- （6） 式中，C个体的编码方法；E个体适应度评价函数； Po初始种群；M种群规模；G 选择操 作；丨交叉操作；？变异操作；一是进化终止代数（进化终止条件）。其中有4个运行参数 需要预先设定：M, T, Pc ，Pm 种群规模 M般取为20100； 终止代数 T 一般取100500； 交叉概率 R 般取0.40.99 ； 变异概率 Pm般取0.00010.1 最后给出遗传算法的基本步骤：选择二进制编码或浮点数编码把问题的解表示成 “染色体”。随机产生一群“染色体”（个体），也就是初始种群。 计算每一个个体的 适应度值，按适者生存的原则， 从中选

14、择出适应度较大的 “染色体”进行复制，再通过交叉、 变异过程产生更适应环境的新一代“染色体”群，即子代。 重复第3步。经过这样的一 代一代地进化，最后就会收敛到最适应环境（适应度最大）的一个“染色体” （即个体）上, 它就是问题的最优解。图 2给出了基本遗传算法设计流程图，其中 t代表当前代数，T是进 化终止代数。 4欢迎下载 精品文档 图2基本遗传算法设计流程图 忖】忖】 初始化种群初始化种群 下一下一优种群优种群 3. Matlab 遗传算法工具箱（gatool） Matlab 的遗传算法工具箱有一个精心设计的图形用户界面，可以帮助用户直观、方便、 快速地利用遗传算法求解最优化问题。在 M

15、atlab命令窗口输入命令： gatool 可以打开遗传算法工具箱的图形用户界面，如图 3所示。GA工具箱的参数设置步骤如下: 输入适应度输入适应度 函数函数 输入适应度输入适应度 函数中的变函数中的变 量数目量数目 开始执行遗开始执行遗 专算法专算法 结果呼 态显示 - * 图3.遗传算法工具 示数述 （1）首先，使用遗传算法工具箱必须输入下列信息: Fitness function（ 适应度函数） 这里指的是待优化的函数，也即目标函数。该工具箱总是试图寻找 目标函数的最小值 输入适应度函数的格式为 fitnessfun，其中符号产生函数fitnessfun 的句柄，fitnessfun 代

16、表用户编写的计算适应度函数 （目标函数）的M文件名，该M文件的编写方法如下： 假定我们要计算Rastrigin 函数的最小值 5欢迎下载 精品文档 2 2 f(XpX2) =20 x x2 -10(cos：x1 cos2二 x2) (7) M函数文件确定这个函数必须接受一个长度为 2的行向量X,也即决策向量，向量的长度等 于变量数目，行向量 X的每个元素分别和变量 Xi和X2对应。另外M文件要返回一个标量 Z， 其值等于该函数的值。下面是计算 Rastrigin 函数的M文件代码： function Z=Ras_fu n(X) Z=20+X(1)A2+X(2)A2-10*(cos(2*pi*X

17、(1)+cos(2*pi*X(2); M文件编写、保存后，再在 gatool工具箱界面 Fitness function 栏输入 Ras_fun Number of variable( 变量个数) 目标函数中的变量数目，也即适应度函数输入向量的长度。在上例中，它的值是 2。 (2)其次，设置遗传算法参数，即 Options设置。 以下只介绍部分运行参数的设置，其他未提及的参数采用默认设置即可。 种群参数(Population ) Population size (种群规模)：每一代中的个体数目，一般是 20-100之间。种群规模 大，算法搜索更彻底，可以增加算法搜索全局最优而非局部最优的概率，

18、 但是耗时也更 长。 Initial range (初始范围)：其值是两行的矩阵，代表初始种群中个体的搜索范围，实 际上是决策向量 X中每个变量Xi的初始搜索范围。矩阵的列数等于变量个数 (Number of variable )，第一行是每个变量的下限，第二行是每个变量的上限。如果只输入 2幻的 矩阵，则每个变量的初始搜索范围都一样。注意，初始范围仅限定初始种群中个体 (或 决策向量)的范围，后续各代中的个体可以不在初始范围之内。 初始范围不能设置太小， 否则造成个体之间的差异过小，即种群的多样性降低，不利于算法搜索到最优解。 复制参数(Reproduction ) Crossover fr

19、action ( 交叉概率):一般取 0.40.99，默认 0.8。 算法终止准则(Stopping Criteria ) 提供了 5种算法终止条件： Generations :最大的进化代数，一般取 100500，默认是100。当遗传算法运行到该 参 数指定的世代，计算终止。 Time limit :指明算法终止执行前的最大时间，单位是秒。缺省是 Inf (无穷大)。 Fitness limit( 适应度限)：当最优适应度值小于或等于此参数值时，计算终止。缺省 是-Inf。 Stall generation(停滞代数):如果每一代的最佳适应度值在该参数指定的代数没有改 善，则终止计算。缺省是

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

21、间的平均距离。它反映个体之间的差异 程度，所以可用来衡量种群的多样性。 图4的下图显示的即是每一代个体间的平均距离。 Best 0.00089516 Wear 0W1122 Average Distance Beiween Individuals Generaticin (4)执行算法：参数设置好了之后，点击工具箱界面上的按钮“ Star ”执行求解器。在算法 运行的同时，“ Curre nt gen eration (当前代数)”文本框中显示当前的进化代数。通过单击 “Pause按钮可以使计算暂停， 之后再点击“Resume可以恢复计算。 当计算完成时， “Status and result

22、s ”窗格中出现如图 5所示的情形。 r 2O10 20 30 40 50 60 Generation 70 80 90 ：i 100 10 2D 匍 40 50 60 70 80 90 100 7欢迎下载 图5 其中包含下列信息： 算法终止时适应度函数的最终值一即目标函数的最优值 Fit ness fun ctio n value: 0.003909079476983379 算法终止原因 Optimizati on term in ated: maximum nu mber of gen erati ons exceeded, 超出最大进化 世代数） 最终点一即目标函数的最优解 X1 X2

23、= -0.004 -0.00193 、实验内容 1. Rastrigin 函数的最小值问题 函数表达式如（7）式，函数图像如下图 6所示，它有多个局部极小值，但是只有一个全 局最小值。Rastrigin 函数的全局最小值的精确解是 0,出现在X1 X2=0 0处。 精品文档 （两个变量的例子） 图6 Rastrigin 函数图像 8欢迎下载精品文档 使用遗传算法工具箱近似求解 Rastrigin 函数的最小值 首先编写计算适应度函数的 M文件，然后设置运行参数（绘图参数 Plots勾选Best fitness 和Distanee 两项，其它参数可以使用默认值） ，执行求解器（Run solver ）计算 Rastrigin 函数的最优值。 观察种群多样性对优化结果的影响 决定遗传算法的一个重要性能是种群的多样性。个体之间的距离越大，则多样性越高； 反之则多样性越低。多样性过高或过低遗传算法都可能运行不好。通过实验调整 Population（种群）的Initial range（ 初始范围）参数可得到种群适当的多样性。 取Initial range 参数值1; 1.1 观察Rastrigin 函数最小值的计算结果； 取Initial range 参数值1; 100观察Rastrigin 函数最小值的计算结果； 取Initia