基于Matlab的遗传算法程序设计及优化问题求解

("曲靖师范学院学生毕业论文（设计）题目：基于Matlab的遗传算法程序设计及优化问题求解院（系）：数学与信息科学学院专业：信息与计算科学班级：20051121班学号：2005112104论文作者：沈秀娟指导教师：刘俊指导教师职称：教授2009年5月基于Matlab的遗传算法程序设计及优化问题求解摘要遗传算法作为一种新的优化方法，广泛地用于计算科学、模式识别和智能故障诊断等方面，它适用于解决复杂的非线性和多维空间寻优问题，近年来也得到了较为广阔的应用.本文介绍了遗传算法的发展、原理、特点、应用和改进方法，以及基本操作和求解步骤，再基于Matlab编写程序实现遗传算法并求解函数的优化问题.程序设计过程表明，用Matlab语言进行优化计算，具有编程语句简单，用法灵活，编程效率高等优点.经仿真验证，该算法是正确可行的.关键词：遗传算法；Matlab；优化Matlab-basedgeneticalgorithmdesignandoptimizationofproceduresforproblemsolvingAbstract：Asanewoptimizatedmethod,geneticalgorithmiswidelyusedincomputationalscience,patternrecognition,intelligentfaultdiagnosisandsoon.Itissuitabletosolvecomplexnon-linearandmulti-dimensionaloptimizationproblem.Andithasbeenmorewidelyusedinrecentyears.Thispaperdescribesthedevelopmentofgeneticalgorithms,principle,features,applicationandimprovementofmethods.Atthesametime,itin-troducesbasicoperationandsolutionsteps.Andthen,itachievesgeneticalgorithmonthematlabprogrammingandsolvesthefunctionoptimizationproblem.Theprogramdesignprocessshowsthatthisoptimizationcalculationhasadvantagesofsimpleprogramminglanguage,flexibleusageandhighefficiencyinMatlablanguage.Thealgorithmiscorrectandfeasiblebysimulatedauthentication.Keywords:Geneticalgorithm；Matlab；Optimization目录1引言12文献综述12.1国内外研究现状及评价12.2提出问题23遗传算法的理论研究23.1遗传算法的产生背景23.2遗传算法的起源与发展33.2.1遗传算法的起源33.2.2遗传算法的发展33.3遗传算法的数学基础研究43.4遗传算法的组成要素63.5遗传算法的基本原理73.6遗传算法在实际应用时采取的一般步骤83.7遗传算法的基本流程描述93.8遗传算法的特点103.9遗传算法的改进113.10遗传算法的应用领域124基于MATLAB的遗传算法实现145遗传算法的函数优化的应用举例176结论186.1主要发现186.2启示186.3局限性196.4努力的方向19参考文献20致谢21附录221引言遗传算法(GeneticAlgorithm)是模拟自然界生物进化机制的一种算法即遵循适者生存、优胜劣汰的法则也就是寻优过程中有用的保留无用的则去除.在科学和生产实践中表现为在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法即找出一个最优解.这种算法是1960年由Holland提出来的其最初的目的是研究自然系统的自适应行为并设计具有自适应功能的软件系统.它的特点是对参数进行编码运算不需要有关体系的任何先验知识沿多种路线进行平行搜索不会落入局部较优的陷阱，能在许多局部较优中找到全局最优点是一种全局最优化方法[1-3].近年来，遗传算法已经在国际上许多领域得到了应用.该文将从遗传算法的理论和技术两方面概述目前的研究现状描述遗传算法的主要特点、基本原理以及改进算法，介绍遗传算法的应用领域，并用MATLAB实现了遗传算法及最优解的求解.2文献综述2.1国内外研究现状及评价国内外有不少的专家和学者对遗传算法的进行研究与改进.比如：1991年D.WHITEY在他的论文中提出了基于领域交叉的交叉算子（ADJACENCYBASEDCROSSOVER），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证.2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题.国内外很多文献都对遗传算法进行了研究.现查阅到的国内参考文献[1-19]中,周勇、周明分别在文献[1]、[2]中介绍了遗传算法的基本原理；徐宗本在文献[3]中探讨了包括遗传算法在内的解全局优化问题的各类算法，文本次论文写作提出了明确的思路；张文修、王小平、张铃分别在文献[4]、[5]、[6]从遗传算法的理论和技术两方面概述目前的研究现状；李敏强、吉根林、玄光南分别在文献[7]、[8]、[9]中都不同程度的介绍了遗传算法的特点以及改进算法但未进行深入研究；马玉明、张丽萍、戴晓辉、柴天佑分别在文献[10]、[11]、[12]、[13]中探讨了遗传算法产生的背景、起源和发展；李敏强、徐小龙、林丹、张文修分别在文献[14]、[15]、[16]、[17]探讨了遗传算法的发展现状及以后的发展动向；李敏强，寇纪凇，林丹，李书全在文献[18]中主要1论述了遗传算法的具体的实施步骤、应用领域及特点；孙祥，徐流美在文献[19]中主要介绍了Matlab的编程语句及基本用法.所有的参考文献都从不同角度不同程度的介绍了遗传算法但都不够系统化不够详细和深入.2.2提出问题随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出近似最优解或满意解是人们的主要着眼点之一.很多人构造出了各种各样的复杂形式的测试函数，有连续函数，有离散函数，有凸函数，也有凹函数，人们用这些几何特性各异的函数来评价遗传算法的性能.而对于一些非线性、多模型、多目标的函数优化问题用其他优化方法较难求解遗传算法却可以方便地得到较好的结果.鉴于遗传算法在函数优化方面的重要性，该文在参考文献[1-19]的基础上，用Matlab语言编写了遗传算法程序,并通过了调试用一个实际例子来对问题进行了验证，这对在Matlab环境下用遗传算法来解决优化问题有一定的意义.3遗传算法的理论研究3.1遗传算法的产生背景科学研究、工程实际与国民经济发展中的众多问题可归结作“极大化效益、极小化代价”这类典型模型.求解这类模型导致寻求某个目标函数（有解析表达式或无解析表达式）在特定区域上的最优解.而为解决最优化问题目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的.随着研究的深入，人们逐渐认识到：在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出近似最优解或满意解是人们的主要着眼点之一.总的来说，求最优解或近似最优解的方法有三种:枚举法、启发式算法和搜索算法.(1)枚举法.枚举出可行解集合内的所有可行解以求出精确最优解.对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解.另外，当枚举空间比较大时该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解.2(2)启发式算法.寻求一种能产生可行解的启发式规则以找到一个最优解或近似最优解.该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特有的启发式规则，这个启发式规则无通用性不适合于其它问题.(3)搜索算法.寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作以找到问题的最优解或近似最优解.该方法虽然保证了一定能够得到问题的最优解，但若适当地利用一些启发知识就可在近似解的质量和求解效率上达到一种较好的平衡.随着问题种类的不同以及问题规模的扩大，要寻求一种能以有限的代价来解决上述最优化问题的通用方法仍是一个难题.而遗传算法却为我们解决这类问题提供了一个有效的途径和通用框架开创了一种新的全局优化搜索算法.3.2遗传算法的起源与发展3.2.1遗传算法的起源50年代末到60年代初，自然界生物进化的理论被广泛接受生物学家Fraser，试图通过计算的方法来模拟生物界“遗传与选择”的进化过程，这是遗传算法的最早雏形.受一些生物学家用计算机对生物系统进行模拟的启发，Holland开始应用模拟遗传算子研究适应性.在1967年，Bagley关于自适应下棋程序的论文中，他应用遗传算法搜索下棋游戏评价函数的参数集并首次提出了遗传算法这一术语.1975年，Holland出版了遗传算法历史上的经典著作《自然和人工系统中的适应性》，首次明确提出遗传算法的概念.该著作中系统阐述了遗传算法的基本理论和方法，并提出了模式(schematatheorem)[4]，证明在遗传算子选择、交叉和变异的作用下具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将以指数级增长.Holand创建的遗传算法，是基于二进制表达的概率搜索方法.在种群中通过信息交换重新组合新串；根据评价条件概率选择适应性好的串进入下一代；经过多代进化种群最后稳定在适应性好的串上.Holand最初提出的遗传算法被认为是简单遗传算法的基础，也称为标准遗传算法.3.2.2遗传算法的发展(1)20世纪60年代，JohnHolland教授和他的数位博士受到生物模拟技术的启发，认识到自然遗传可以转化为人工遗传算法.1962年，JohnHolland提出了利用群体进化模拟适应性系统的思想，引进了群体、适应值、选择、变异、交叉等基本概念.3(2)1967年，J.D.Bagely在其博士论文中首次提出了“遗传算法”的概念.(3)1975年，Holland出版了《自然与人工系统中的适应性行为》（AdaptationinNaturalandArtificialSystem）.该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定理—模式定理，从而奠定了遗传算法的理论基础.同年DeJong在其博士论文中，首次把遗传算法应用于函数优化问题对遗传算法的机理与参数进行了较为系统地研究并建立了著名的五函数测试平台.(4)20世纪80年代初，Holland教授实现了第一个基于遗传算法的机器学习系统—分类器系统（ClassifierSystem简称CS），开创了基于遗传算法的机器学习的新概念.(5)1989年，DavidGoldberg出版了《搜索、优化和机器学习中的遗传算法》（GeneticAlgorithmsinSearchOptimizationandMachineLearning）.该书全面系统地总结了当时关于遗传算法的研究成果，结合大量的实例完整的论述了遗传算法的基本原理及应用，奠定了现代遗传算法的基础.(6)1992年，JohnR.Koza出版了专著《遗传编程》（GeneticProgramming）提出了遗传编程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面.随着遗传算法的不断深入和发展，关于遗传算法的国际学术活动越来越多，遗传算法已成为一个多学科、多领域的重要研究方向.今天遗传算法的研究已经成为国际学术界跨学科的热门话题之一.遗传算法是一种有广泛应用前景的算法，但是它的研究和应用在国内尚处于起步阶段.近年来遗传算法已被成功地应用于工业、经济管理、交通运输、工业设计等不同领域解决了许多问题.例如可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等.3.3遗传算法的数学基础研究模式定理及隐含并行性原理被看作遗传算法的两大基石，后来又提出了建筑块假设，但是模式定理无法解释遗传算法实际操作中的许多现象，隐性并行性的论证存在严重漏洞，而建筑块假设却从未得到过证明.对遗传算法的基础理论的研究主要分三个方面：模式定理的拓广和深入、遗传算法的新模型、遗传算法的收敛性理论.(1)模式定理的拓广和深入.Holland给出模式定理：具有短的定义长度、低阶、并且模式采样的平均适应值在种群平均适应值以上的模式在遗传迭代过程中将按指数增4长率被采样模式定理可表达为：m(H,t+1)m(H,t)..(1)其中m(Ht)：在t代群体中存在模式H的串的个数.：在t代群体中包含模式H的串的平均适应值.：t代群体中所有串的平均适应值.表示串的长度表示交换概率表示变异概率.Holland的模式定理奠定了遗传算法的数学基础根据隐性并行性得出每一代处理有效模式的下限值是其中n是种群的大小是小整数.Bertoui和Dorigo进行了深入的研究获得当,β为任意值时处理多少有效模式的表达式.上海交通大学的恽为民等获得每次至少产生数量级的结果.模式定理中模式适应度难以计算和分析A.D.Berthke首次提出应用Walsh函数进行遗传算法的模式处理并引入模式变换的概念采用Walsh函数的离散形式有效地计算出模式的平均适应度并对遗传算法进行了有效的分析.1972年Frantz首先发现一种常使GA从全局最优解发散出去的问题，称为GA-欺骗题[5].Goldberg最早运用Walsh模式转换设计出最小的GA-欺骗问题并进行了详细分析.(2)遗传算法的新模型.由于遗传算法中的模式定理和隐性并行性存在不足之处，为了搞清楚遗传算法的机理，近几年来人们建立了各种形式的新模型最为典型的是马氏链模型遗传算法的马氏链模型[6-7]，主要由三种分别是种群马氏链模型、Vose模型和Cerf扰动马氏链模型.种群马氏链模型将遗传算法的种群迭代序列视为一个有限状态马氏链来加以研究，运用种群马氏链模型转移概率矩阵的某些一般性质分析遗传算法的极限行为，但转移概率的具体形式难以表达妨碍了对遗传算法的有限时间行为的研究；Vose模型是在无限种群假设下利用相对频率导出，表示种群的概率的向量的迭代方程，通过这一迭代方程的研究，可以讨论种群概率的不动点及其稳定性，从而导致5对遗传算法的极限行为的刻画，但对解释有限种群遗传算法的行为的能力相对差一些.Cerf扰动模型是法国学者Cerf将遗传算法看成一种特殊形式的广义模拟退火模型，利用了动力系统的随机扰动理论，对遗传算法的极限行为及收敛速度进行了研究.还有其它改进模型，例如张铃、张钹等人提出的理想浓度模型，它首先引入浓度和家族的概念，通过浓度计算建立理想浓度模型[8-10]，其浓度变化的规律为：c(Hi，t+1)=c(H，t)(2)c(Hi，t+1)表示模式Hi在t时刻的浓度，并对其进行分析，得出结论：遗传算法本质上是一个具有定向制导的随机搜索技术，其定向制导原则是导向适应度高的模式为祖先的染色体“家族”方向.(3)遗传算法的收敛性理论.对于遗传算法的马氏链分析本身就是建立遗传算法的收敛性理论[11-12]，Eiben等用马尔可夫链证明了保留最优个体的遗传算法的概率性全局收敛，Rudolph用齐次有限马尔可夫链证明了具有复制、交换、突变操作的标准遗传算法收敛不到全局最优解，不适合于静态函数的优化问题，建议改变复制策略以达到全局收敛，Back和Muhlenbein研究了达到全局最优解的算法的时间复杂性问题，近几年，徐宗本等人建立起鞅序列模型，利用鞅序列收敛定理证明了遗传算法的收敛性.3.4遗传算法的组成要素遗传算法所涉及的五大要素：参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计和控制参数的设定，其具体内容如下：(1)参数编码.遗传算法中常用的编码方法是二进制编码，它将问题空间的参数用字符集{0，1}构成染色体位串，符合最小字符集原则，操作简单，便于用模式定理分析.(2)适应度函数的设计.适应度函数是评价个体适应环境的能力，使选择操作的依据，是由目标函数变换而成.对适应度函数唯一的要求是其结果为非负值.适应度的尺度变换是对目标函数值域的某种映射变换，可克服未成熟收敛和随机漫游现象.常用的适应度函数尺度变化方法主要有线性变换、幂函数变换和指数变换.[13](3)遗传操作的设计.包括选择、交叉、变异.①选择(Selection).选择是用来确定交叉个体，以及被选个体将产生多少个子代6个体.其主要思想是个体的复制概率正比于其适应值，但按比例选择不一定能达到好的效果.选择操作从早期的轮盘赌选择发展到现在最佳个体保存法、排序选择法、联赛选择法、随机遍历抽样法、局部选择法、柔性分段复制、稳态复制、最优串复制、最优串保留等.②交叉(Crossover).交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作，其作用是组合出新的个体，在串空间进行有效搜索，同时降低对有效模式的破坏概率.各种交叉算子均包含两个基本内容：确定交叉点的位置和进行部分基因的交换.常用的交叉操作方法有单点交叉、双点交叉、一致交叉、均匀交叉、算术交叉二维交叉、树结构交叉、部分匹配交叉、顺序交叉和周期交叉等等.③变异(Mutation).变异是指将个体编码串中的某些基因值用其它基因值来替换,形成一个新的个体.遗传算法中的变异运算是产生新个体的辅助方法，其目的是使遗传算法具有局部的随机搜索能力和保持群体的多样性.变异算法包括确定变异点的位置和进行基因值替换.常见的变异算子有基本位变异、均匀变异、高斯变异、二元变异、逆转变异、自适应变异等.(4)控制参数设定.遗传算法中需要确定一些参数取值，主要有串长l，群体大小n，交叉概率pc、变异概率pm等，对遗传算法性能影响很大.目前对参数根据情况进行调整变化研究比较多，而一般确定的参数范围是：n=20～200，pc=015～110，pm=0～0105.3.5遗传算法的基本原理在自然界，由于组成生物群体中各个体之间的差异，对所处环境有不同的适应和生存能力，遵照自然界生物进化的基本原则，适者生存、优胜劣汰，将要淘汰那些最差个体，通过交配将父本优秀的染色体和基因遗传给子代，通过染色体核基因的重新组合产生生命力更强的新的个体与由它们组成的新群体.在特定的条件下，基因会发生突变,产生新基因和生命力更强的新个体；但突变是非遗传的，随着个体不断更新，群体不断朝着最优方向进化，遗传算法是真实模拟自然界生物进化机制进行寻优的.在此算法中,被研究的体系的响应曲面看作为一个群体，相应曲面上的每一个点作为群体中的一个个体，个体用多维向量或矩阵来描述，组成矩阵和向量的参数相应于生物种组成染色体的基因，染色体用固定长度的二进制串表述，通过交换、突变等遗传操作，在参7数的一定范围内进行随机搜索，不断改善数据结构，构造出不同的向量，相当于得到了被研究的不同的解，目标函数值较优的点被保留，目标函数值较差的点被淘汰.[14]由于遗传操作可以越过位垒，能跳出局部较优点，到达全局最优点.遗传算法是一种迭代算法，它在每一次迭代时都拥有一组解，这组解最初是随机生成的，在每次迭代时又有一组新的解由模拟进化和继承的遗传操作生成，每个解都有一目标函数给与评判，一次迭代成为一代.经典的遗传算法结构图如下：图1遗传算法的结构图3.6遗传算法在实际应用时采取的一般步骤(1)根据求解精度的要求，确定使用二进制的长度.设值域的取值范围为[,]，若要求精确到小数点后6位，则由(-)×106<-1求得的最小长度，进而可求出位于区间的任一数：=+decimal(...)×[15](3)其中，i=1，2，...，Popsize；Popsize为种群中染色体的个数；(2)利用随机数发生器产生种群；编码、生成初始种群种群中个体适应渡的计算与评价价物种的选择杂交变异8(3)对种群中每一染色体，计算其对应适应度eval()，i=1，2，…，Popsize；(4)计算种群适应度之和F：F=(4)(5)计算每个染色体选择概率Pi：(5)i=1，2，...，Popsize；(6)计算每个染色体的累加概率：=(6)i=1，2，...，Popsize；(7)产生一个位于[0，1]区间的随机数序列，其长度为N，如果其中任意一数r<，则选择第一个染色体，若2^(i)m=i+1;elsei=i+1;endendpopusize=n;chromlength=m;j=1;popu=round(rand(popusize,chromlength));%随机产生n行m列的初始群体whilej<=30%设置程序中止条件py=chromlength;23fori=1:py%进行二进制转换成十进制的解码操作popu1(:,i)=2.^(py-1).popu(:,i);py=py-1;endpopu2=sum(popu1,2);x=a+popu2(b-a)/(2.^1-1);yvalue=2x.^2.cos(3x)+x.sin(5x)+8;%计算群体中每个个体的适应度fori=1:popusize%执行复制操作ifyvalue(i)<0yvalue(i)=0;endendfitscore=yvalue/sum(yvalue);%个体被选中的概率fitscore=cumsum(fitscore);%群体中个体的累积概率wh=sort(rand(popusize,1));%从小到大排列wheel=1;fitone=1;whilewheel<=popusize%执行转盘式选择操作ifwh(wheel)