搜索
第五节MATLAB遗传算法优化工具箱的应用本节简要介绍遗传算法和基于MATLAB的遗传算法优化工具箱(GA)，结合非线性多峰值函数优化问题的计算，说明遗传算法是一种具有良好的全局寻优性能的优化方法。1、遗传算法概述1.1遗传算法的生物学背景1859年达尔文发表《物种起源》,提出以自然选择为基础的生物进化论学说,认为生物进化发展主要有3个原因:遗传、变异和选择。生物遗传物质的主要载体是染色体。染色体主要是由DNA和蛋白质构成。其中DNA在染色体里含量稳定，结构也相对稳定，能够自我复制和产生可遗传的变异，是主要的遗传物质。而生物的性状遗传，主要是通过染色体上的基因遗传给后代的。基因是遗传物质的基本单位，又称遗传因子。生物的变异有3种可能性：基因重组、基因突变和染色体变异。基因重组是指控制不同性状的基因的重新组合。基因突变是指基因内部的化学变化。每种生物的染色体无论结构或数目都是相对稳定的，但在自然或人为条件的作用下，染色体的结构和数目都可以发生变化，不过染色体数目的改变是染色体变异的一个主要方面。由于生物进化论揭示了生物自然选择的进化发展规律，人们从中受到了启迪，生物进化论的自然选择过程蕴含着一种搜索和优化的先进思想，将这种思想用于科学研究和工程技术领域而发展起来的方法，称为遗传算法GA(GeneticAlgorithm)，这种算法为解决许多传统的优化方法难以解决的优化问题提供了崭新的途径。目前，遗传算法发展迅速，已被广泛应用于解决各种问题，例如，系统优化、机器学习、工程控制、模式识别、人工智能、故障诊断以及计算机技术等领域，取得了良好的效果。随着遗传算法的基本原理、方法及其应用技巧的深入研究，其应用范围也越来越广泛，几乎渗透到从工程到社会科学的诸多领域，必须要编制遗传算法的程序进行计算。使用者希望找一个现成的程序，MATLAB的遗传算法工具箱正好满足要求。Matlab语言有着丰富的由世界著名专家、学者开发出的各种工具箱，Matlab的优化工具箱提供了对各种优化问题的解决方案，遗传算法优化工具箱就是其中之一。采用MATLAB遗传算法优化工具箱，不仅具有简单、易用、易于修改的特点，而且为解决许多传统搜索的优化方法难以解决的非线性、多峰值之类的复杂问题提供了有效的途径。遗传算法的研究和应用具有很好的应用前景。1.2遗传算法的特点①遗传算法处理的是待求问题变量的编码，而不是变量的本身。②遗传算法使用概率规则而不是确定性规则指导搜索，只要一个适应度函数值，而不必要求其他辅助信息，诸如连续性、导数存在和单峰等，因而具有极好的鲁棒性和广泛的适应性。③遗传算法通过控制群体中N个数字串，能处理各代中大量的模式，在每一代中被处理的模式数目大概是N3，这一切在群体中并行进行的，也就是说，遗传算法同时搜索解空间中许多个点而不是一个点，因而能够快速全局收敛。遗传算法这种隐含的并行性是它区别于其他优化方法最主要的因素。④遗传算法像撒网一样，在变量空间中进行寻优，由N个数字串组成的群体在遗传因子的作用下，同时对空间中不同的区域进行充分搜索，从而构成一个不断优化的群体序列。遗传算法是通过保持在解空间不同区域中各个点的搜索，而不是盲目地穷举或瞎碰，故相对其他优化方法而言，遗传算法能以很大的概率找到优化问题的全局最优解。1.3遗传算法的基本步骤GA是基于生物自然选择与遗传机理的一种随机搜索算法，与传统搜索算法不同，GA从一组随机产生的称为“种群(population)”的初始解开始嫂索过程。种群中的每个个体是问题的一个解，称为“染色体(chromosome)”。染色体是一串符号，比如一个二进制字符串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用“适值(fitness)”来测量染色体的好坏，生成的下一代染色体称为后代(offspring)。后代是由前一代染色体通过交叉(crossover)或者变异(mutation)运算形成的。在新一代形成过程中，根据适值的大小选择部分后代，淘汰部分后代．从而保持种群大小是常数。适值高的染色体被选中的概率较高，这样经过若干代之后．算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。1.4GA基本构成要素输入参数:染色体个数N,交叉概率Pc,变异概率Pm;通过初始化过程产生N个染色体;计算所有染色体的评价函数;根据评价函数抽样选择染色体;对染色体进行交叉和变异操作;重复若干次(下一代的代数)计算评价函数、选择、交叉和变异.设计表示问题的染色体生成初始染色体计算每个染色体的适应度是否满足算法停止条件选择高适应度染色体进行复制交叉变异停止输出最优解GA流程图1.5遗传算法中的基本概念和术语遗传算法中使用的基本概念和术语如下：染色体——遗传物质的主要载体，指多个基因的集合。基因——控制生物性状的遗传物质的功能和结构的基本单元，又称遗传因子。基因型——它是性状染色体的内部表现，或者说，由遗传因子组合的模式，称为基因型。表现型——它是由染色体决定性状的外部表现，或者说，根据遗传因子形成的个体，称为表现型。个体——指染色体带有特征的实体称为个体；群体——染色体带有特征的个体的集合，称为群体，该集合内的个体数目称为群体规模。适应度函数——各个个体自适应环境的程度函数，称为适应值函数或适应度函数。选择——用某种方法从群体中选取若干个体的操作称为选择。交叉——把两个染色体重新组合的操作称为交叉，又称杂交。变异——让遗传因子以一定的概率变化的操作称为变异。编码——从表现型到基因型的映射称为编码。解码(释码)——从基因型到表现型的映射称为解码。1.6GA的3个基本算子:①选择(selection)：选择算子从群体中按某一概率选择个体,某个体Xi被选择的概率Pi与其适应值成正比.最通常的实现方法是轮盘赌(roulettewheel)模型.②交叉(crossover)：交叉算子将被选中的2个个体的基因链按概率Pc进行交叉,生成2个新的个体,交叉位置是随机的.其中Pc是一个系统参数,即交叉概率.③变异(mutation)：变异算子按一定概率Pm将新个体的基因链的各位进行变异,对二值基因链(0,1编码)来说即是取反.Pm也是一个系统参数,即变异概率.以上各种算子的实现方法是多种多样的,而且许多高级算子正不断提出,以改进GA的某些性能.选择选择的方法根据不同的优化问题有多种方案，这里介绍适应度函数值比例选择法适应度函数值比例法，又称转轮法，这种方法是利用比例于各个个体适应度函数值的概率来决定其后代的遗传可能性。若某个个体，被选取的选择概率Psi表示为式中，fi为个体i的适应度函数值，N为群体中的个体数目。表1-1给出了4个个体，每个个体对应的适应度函数值及用适应度函数值比例法表示的选择概率(以下简称为选择率)。当选择率确定后，用随机变量试验，产生0～1区间内的随机数。由那个随机变量值决定哪个个体被选取，于是选择率大的个体就能多次被选中和参加交配，它的遗传因子就会在群体中扩大。表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.6360.34，随机变量值0.34落于个体2所在区间，则个体2被选中；若第2次试验，随机变量值为0.86，落于图中个体4所在区间，则个体4被选中。如此重复，做N次试验，依据随机变量值选出N个个体，被选中的N个个体中会有重复，例如个体2就可能被选中多次，将选出的N个个体放入交配池中，就可以进行交叉操作了。交叉操作交叉是遗传算法中的一个重要算子。交叉是将两个染色体重新组合的操作。交叉操作可以产生新的个体，从而需要检测搜索空间中新的点。选择操作每次仅作用在一个个体上，而交叉操作每次作用在从交配池中随机选取的两个个体上。交叉操作产生两个子代个体，它们一般与其父代个体不同，并且彼此也不同，每个子代个体都包含两个父代个体的遗传物质。交叉操作分为一点交叉、多点交叉和一致交叉等。一点交叉操作的一个重要特性是，它可以产生与原配对个体完全不同的子代个体；另一个重要特性是，它不会改变原配对个体中相同位置上的值。需要指出的是，当两个配对个体完全相同时，交叉是不起作用的。交叉操作分两步进行，首先按照某种方法，随机地从交配池中取出要交叉的一对个体，然后进行交叉，产生一对新的个体。交叉的方法是，先根据个体数字串长度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也不相同。变异操作变异是遗传算法中的又一重要算子，它模拟了生物进化过程中偶然的基因突变现象。基因变异能增加群体中个体的多样性。变异是以一很小的概率Pm从群体A(t)中随机选取若干个体，对于选中的个体又随机选取染色体中的某一位或多位进行数码翻转，对于二进制数字串就是某一位置上的值1变为0或值0变为1。例如，个体A变异位置变异前A=11001变异后A’=11011在本例中，个体A和变异位置都是随机选取的。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.2遗传算法工具箱(GAToolbox)2.1遗传算法函数遗传算法工具箱GAOT包括了许多实用的函数,这些函数按照功能可以分为以下几类:主界面函数、选择函数、演化函数、其它的一些终止函数、二进制表示函数、演示程序等等.2.2遗传算法函数的参数MATLAB的遗传算法工具箱GA其主程序ga.m提供了遗传算法工具箱与外部的接口。在MATLAB环境下执行ga并设定相应的参数,就可以完成优化。(1)初始种群的生成函数function[pop]=initializega(num,bounds,eevalFN,eevalOps,options)[输出参数]：pop—生成的初始种群;[输入参数]：num—种群中的个体数目;bounds—代表变量的上下界的矩阵;eevalFN—适应度函数;eevalOps—传递给适应度函数的参数;options—选择编码形式(浮点编码或是二进制编码)；[precisionF-or-B],其中precision为变量进行二进制编码时指定的精度;F-or-B为1时选择浮点编码，否则为二进制编码,并由precision指定精度.(2)主程序ga.mfunction[x,endPop,bPop,traceInfo]=ga(bounds,evalFN,evalOps,startPop,opts,⋯termFN,termOps,selectFN,selectOps,⋯xOverFNs,xOverOps,mutFNs,mutOps)[输出参数]x、endPop、bPop、