求解非线性规划问题的遗传算法设计实现分析范文

./摘要非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用。传统的解决非线性规划问题的方法,如梯度法、罚函数法、拉格朗日乘子法等,稳定性差,对函数初值和函数性态要求较高,且容易陷入局部最优解。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。遗传算法是一种全局搜索算法,简单、通用、鲁棒性强,对目标函数既不要求连续,也不要求可导,适用于并行分布处理,应用范围广。本文在分析传统的非线性规划算法的不足和遗传算法的优越性的基础上,将遗传算法应用于非线性规划。算法引进惩罚函数的概念,构造带有惩罚项的适应度函数；通过实数编码,转轮法选择,双点交叉,均匀变异,形成了求解非线性规划问题的遗传算法。与传统的非线性规划算法——外点罚函数法的比较结果表明该算法在一定程度上有效地克服了传统的非线性规划算法稳定性差,对函数初值和函数性态要求较高,且容易陷入局部最优解的缺陷,收敛更合理,性能更稳定。关键词：非线性规划；遗传算法；罚函数法ABSTRACTNon-linearprogramminghasawiderangeofapplicationsinengineering,management,economic,scientific,andmilitaryaspects.Traditionalmethodstosolvethenon-linearprogrammingproblem,suchasthegradientmethod,penaltymethod,Lagrangemultipliermethod,havepoorstability.Theyaresensitivetothefunctioninitialvalueandrequesttheobjectivefunctiontobecontinuousanddifferential.Theresultsarealsoeasilytrappedintolocaloptimalsolution.GeneticalgorithmisakindofcalculatemodelwhichsimulatesDarwin'sgeneticselectionandbiologicalevolutionofnaturalselection.Geneticalgorithmisaglobalsearchalgorithm.Ithassimple,universal,robustfeatures,anddoesnotrequesttheobjectivefunctiontobecontinuousanddifferential,andissuitableinparalleldistributionprocessing.Geneticalgorithmiswidelyappliedinmanyareas.Basedontheanalysisofthedisadvantageoftraditionalnon-linearprogrammingalgorithmandtheadvantageofgeneticalgorithm,geneticalgorithmisappliedtonon-linearprogramminginthispaper.Theintroductionoftheconceptofpenaltyfunctionisusedtoconstructthefitnessfunctionwithpunishment.Byusingreal-coded,RouletteWheelselectionmethod,two-pointcrossover,uniformmutation,weformedageneticalgorithmtosolvethenon-linearprogrammingproblem.Comparedwiththemostclassicalandwidelyusedtraditionalnon-linearprogrammingproblemalgorithm–SUMTalgorithm,theresultsshowthatthenewalgorithmcouldeffectivelyovercomethedefectofthetraditionalalgorithminacertainextent.Thenewalgorithmismorestable,lesssensitivetothefunctioninitialvalueandconditions,andalwayscouldreceivetheoptimalsolutionorapproximateoptimalsolution.Itsconvergenceresultsaremorereasonable,theperformanceismorestable.KeyWords:Non-linearProgramming;GeneticAlgorithm;SUMTAlgorithm.目录1概论11.1背景介绍11.1.1非线性规划简介11.1.2遗传算法简介11.2研究内容22非线性规划32.1非线性规划的概念32.2非线性规划的数学模型32.3非线性规划的求解方法42.3.1一维最优化方法42.3.2无约束最优化方法42.3.3约束最优化方法52.4非线性规划的应用53传统非线性规划算法——外点罚函数法63.1算法概述63.2算法描述63.3算法性能分析73.4外点罚函数法的程序设计8程序步骤8程序流程图84遗传算法104.1遗传算法概述104.1.1遗传算法的生物学基础104.1.2遗传算法的一般结构104.1.3遗传算法的特点124.1.4遗传算法的应用124.2遗传算法实现的关键技术135求解非线性规划问题的遗传算法设计165.1实用遗传算法设计165.2求解非线性规划问题的遗传算法程序设计215.2.1算法过程描述215.2.2遗传算法程序流程图225.2.3遗传算法中所设计的辅助算法的设计226算法的结果分析246.1概述246.2结果比较247总结28致谢29参考文献30.1概论1.1背景介绍非线性规划简介具有非线性约束条件或目标函数的数学规划,称为非线性规划。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W.库恩和A.W.塔克发表的关于最优性条件<后来称为库恩－塔克条件>的论文是非线性规划正式诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法,它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法,70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用,为最优化设计提供了有力的工具。随着计算机的产生与发展,非线性规划作为一门独立的学科越来越受到人们的重视。在非线性规划理论研究的基础上,人们日益重视非线性规划问题求解方法的研究。传统的解决非线性规划问题的方法有多种,如搜索法、梯度法、变尺度法、罚函数法、拉格朗日乘子法、可行方向法等,虽然解法很多,非线性规划目前还没有能适用于各种问题的算法,各个方法都有自己特定的适用范围。遗传算法简介遗传算法〔GeneticAlgorithm,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,它是由美国Michigan大学J.Holland教授于1975年首先提出来的,并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》,GA这个名称才逐渐为人所知,J.Holland教授所提出的GA通常为简单遗传算法〔SGA。遗传算法是一种特别有效的算法,它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程,从而得到最优解或准最优解。它的主要特点是简单、通用、鲁棒性强,对目标函数既不要求连续,也不要求可导,适用于并行分布处理,应用范围广。遗传算法提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于很多领域,如函数优化、组合优化、生产调度问题、自动控制、机器人智能控制、图像处理,人工生命、遗传编程、机器学习等。并且取得了令人瞩目的成果。1.2研究内容传统的非线性规划算法的缺陷是计算烦琐且精度不高,稳定性差,对函数初值和函数性态要求较高,且容易陷入局部最优解。而遗传算法是一种鲁棒性很强的种全局搜索算法,理论上可以克服传统非线性规划算法的缺陷。本文的主要内容就是应用遗传算法的基本思想,结合本次实验的实际情况,对基本遗传算法加以改进,将遗传算法应用于求解非线性规划问题,形成求解非线性规划问题的遗传算法。具体内容包括编码方法设计,适应度函数设计,选择算子、交叉算子、变异算子等遗传算子设计,算法流程设计,并在设计的基础上用MATLAB语言实现该算法的程序,运行并调试程序,直至得到正确的结果。并对实验所得结果进行分析,比较求解非线性规划问题的遗传算法与传统的非线性规划算法的优缺点。2非线性规划2.1非线性规划的概念具有非线性约束条件或目标函数的数学规划,称为非线性规划。非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的极值问题,且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。2.2非线性规划的数学模型对实际规划问题作定量分析,必须建立数学模型。建立数学模型首先要选定适当的目标变量和决策变量,并建立起目标变量与决策变量之间的函数关系,称之为目标函数。然后将各种限制条件加以抽象,得出决策变量应满足的一些等式或不等式,称之为约束条件[4]。非线性规划问题的一般数学模型可表述为求未知量,使满足约束条件：〔2.1并使目标函数达到最小值<或最大值>。其中,诸和诸都是定义在n维向量空间的某子集<定义域>上的实值函数,且至少有一个是非线性函数。

上述模型可简记为：〔2.2〔2.3其中属于定义域,符号min表示"求最小值",符号s.t.表示"受约束于"。定义域中满足约束条件的点称为问题的可行解。全体可行解所成的集合称为问题的可行集。对于一个可行解,如果存在的一个邻域,使目标函数在处的值优于<指不大于或不小于>该邻域中任何其他可行解处的函数值,则称为问题的局部最优解〔简称局部解。如果优于一切可行解处的目标函数值,则称x*为问题的整体最优解〔简称整体解。实用非线性规划问题要求整体解,而现有解法大多只是求出局部解。2.3非线性规划的求解方法一维最优化方法指寻求一元函数在某区间上的最优值点的方法。这类方法不仅有实用价值,而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法[1]。①黄金分割法,又称0.618法。它适用于单峰函数。其基本思想是：在初始寻查区间中设计一列点,通过逐次比较其函数值,逐步缩小寻查区间,以得出近似最优值点。②切线法,又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个猜测点附近将目标函数的导函数线性化,用此线性函数的零点作为新的猜测点,逐步迭代去逼近最优点。③插值法,又称多项式逼近法。其基本思想是用多项式〔通常用二次或三次多项式去拟合目标函数。此外,还有斐波那契法、割线法、有理插值法、分批搜索法等。无约束最优化方法指寻求n元实函数在整个n维向量空间上的最优值点的方法。这类方法的意义在于：虽然实用规划问题大多是有约束的,但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解[1]。无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两类。一类需要用目标函数的导函数,称为解析法。另一类不涉及导数,只用到函数值,称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向,沿这个方向进行一维寻查,得出新的近似点。然后对新点施行同样手续,如此反复迭代,直到满足预定的精度要求为止。根据搜索方向的取法不同,可以有各种算法。属于解析型的算法有：=1\*GB3①梯度法：又称最速下降法。这是早期的解析法,收敛速度较慢。②牛顿法：收敛速度快,但不稳定,计算也较困难。③共轭梯度法：收敛较快,效果较好。④变尺度法：这是一类效率较高的方法。其中达维登-弗莱彻-鲍威尔变尺度法,简称DFP法,是最常用的方法。属于直接型的算法有交替方向法〔又称坐标轮换法、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等。约束最优化方法指前述一般非线性规划模型的求解方法。常用的约束最优化方法有4种[1]：=1\*GB3①拉格朗日乘子法：它是将原问题转化为求拉格朗日函数的驻点。②制约函数法：又称系列无约束最小化方法,简称SUMT法。它又分两类,一类叫惩罚函数法,或称外点法；另一类叫障碍函数法,或称内点法。它们都是将原问题转化为一系列无约束问题来求解。③可行方向法：这是一类通过逐次选取可行下降方向去逼近最优点的迭代算法。如佐坦迪克法、弗兰克－沃尔夫法、投影梯度法和简约梯度法都属于此类算法。④近似型算法：这类算法包括序贯线性规划法和序贯二次规划法。前者将原问题化为一系列线性规划问题求解,后者将原问题化为一系列二次规划问题求解。2.4非线性规划的应用在经营管理、工程设计、科学研究、军事指挥等方面普遍地存在着最优化问题。例如：如何在现有人力、物力、财力条件下合理安排产品生产,以取得最高的利润；如何设计某种产品,在满足规格、性能要求的前提下,达到最低的成本；如何确定一个自动控制系统的某些参数,使系统的工作状态最佳；如何分配一个动力系统中各电站的负荷,在保证一定指标要求的前提下,使总耗费最小；如何安排库存储量,既能保证供应,又使储存费用最低；如何组织货源,既能满足顾客需要,又使资金周转最快等。对于静态的最优化问题,当目标函数或约束条件出现未知量的非线性函数,且不便于线性化,或勉强线性化后会招致较大误差时,就可应用非线性规划的方法去处理。3传统非线性规划算法——外点罚函数法3.1算法概述罚函数法求解非线性规划问题的思想是,利用问题中的约束函数做出适当的罚函数,由此构造出带参数的增广目标函数,把问题转化为无约束非线性规划问题。利用罚函数法,可将非线性规划问题的求解,转化为求解一系列无约束极值问题,因而也称这种方法为序列无约束最小化技术,简记为SUMT<SequentialUnconstrainedMinimizationTechnique>。主要有两种形式,一种叫外点罚函数法,另一种叫内点罚函数法。外点罚函数法是从非可行解出发逐渐移动到可行区域的方法。内点罚函数法也称为障碍罚函数法,这种方法是在可行域内部进行搜索,约束边界起到类似围墙的作用,如果当前解远离约束边界时,则罚函数值是非常小的,否则罚函数值接近无穷大的方法。3.2算法描述对于问题〔2.2,本文所述的基本策略是,根据约束特点〔等式或不等式构造某种"罚函数",然后把它加到目标函数中去,使得对约束最优化问题的求解转化为一系列无约束问题。极小点或者无限地向可行域靠近,或者一直保持在可行集内移动,直到收敛于原来约束最优化问题极小点。对于问题〔2.2,构造一函数为〔3.1其中,〔3.2在〔3.2中,又称为惩罚函数,〔3.3〔3.4是一个逐渐增大的参数,称为惩罚因子。又称为问题〔2.2的增广目标函数。显然,增广目标函数是定义在上的一个无约束函数。由增广目标函数的构造知当时〔3.5此时的最优解就是问题〔2.2的最优解；而当时,的最优解就不一定是问题〔2.2的最优解。但是研究时,的最优解不是我们所需要的。为此规定,当时,在点处的函数值迅速变大,换而言之,可行域外的任一点处的函数值都相当大。此时要求在中的最优解,只能让点回到内才有可能,然而一旦点回到内,即,此时就与问题〔2.2有相同的最优解。当时,迅速变大的原因是通过惩罚因子来实现。简言之,外点罚函数法的思想是：当点时,设法加大不可行点处的函数值,使不可行点不能成为在中的最优解。在用外点罚函数法求解问题〔2.2时,首先构造增广目标函数,然后按照无约束优化方法求解。如果求出的最优解为,则判断是否属于。如果,则是问题〔2.2的最优解；如果,则不是问题〔2.2的最优解,此时说明原来的惩罚因子给的太小了,需要加大惩罚因子,使得,然后再重新计算的最优值。3.3算法性能分析通过长期的理论研究和实验结果,人们总结出惩罚函数的优点有：〔1罚函数法是解决非线性规划问题的一种经典算法,这种算法简单易行、熟练数度快,在很多实际问题的求解中得到了应用。〔2计算效率高,稳定性较好。缺点有：〔1罚函数法对于有些问题只能求出局部最优解,而不能求出全局最优。〔2对函数初值和函数性态要求较高。〔3罚函数法在实际计算中的缺点是罚因子的取值难于把握,太小起不到惩罚作用；太大则由于误差的影响会导致错误。在搜索过程开始的时候,一个较大的罚因子将会阻碍非可行域的搜索。另一方面,如果罚因子太小,这样相对于目标函数罚函数项是可以忽略的,则大量的搜索时间将花费在非可行域。这对于进化算法来说非常致命的。3.4外点罚函数法的程序设计为了能和求解非线性规划问题的遗传算法进行比较,我们同时实现最经典的,也是得到最广泛应用的传统的非线性规划算法——外点罚函数法,通过对二者的结果,比较二者性能的差别。3.4.1程序步骤对于问题〔2.2,构造一函数为〔3.6其中,惩罚函数按照式〔3.2构造,给定终止限〔可取。具体过程描述如下：〔1选定初始点,初始惩罚因子〔可取。惩罚因子放大系数,置。〔2假设已获得迭代点,以为初始点,求解无约束问题〔3.7设其最优点为。〔3若,则就是所要求问题的最优解,打印,结束；否则转〔4。〔4置,,转〔2。3.4.2程序流程图外点罚函数法程序流程图如图3-1所示。图3-1外点罚函数法程序流程图4遗传算法4.1遗传算法概述遗传算法的生物学基础遗传算法的生物学基础是达尔文的自然选择学说。自然选择学说认为,生物要生存下去,就必须进行生存斗争。在生存斗争中,具有有利变异〔mutation的个体容易存活下来,并且有更多的机会将有利的变异传给后代；具有不利变异的个体就容易被淘汰,产生后代的机会也少得多。达尔文把这种在生存斗争中适者生存,不适者淘汰的过程叫做自然选择。达尔文的自然选择学说表明,遗传和变异是决定生物进化的内在因素。遗传能使生物的性状不断地传递给后代,因而保持了物种的特性,变异能够使生物的性状发生改变,从而适应新的环境而不断地向前发展[2]。4.1.2遗传算法的一般结构遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。和传统算法不同,遗传算法从一组随机产生的初始解,称为"种群",开始搜索过程。种群中的每个个体是问题的一个解,称为"染色体"。染色体是一串符号,比如一个二进制字符串。这些染色体在后续迭代中不断进化,称为遗传。在每一代中用"适值"来测量染色体的好坏。生成的下一代染色体称为后代。后代是由前一代染色体通过交叉或变异运算形成的。新一代形成中,根据适值的大小选择部分后代,淘汰部分之后,从而保持种群大小是常数。适值高的染色体被选中的概率较高。这样,经过若干代之后,算法收敛于最好的染色体,它很可能就是问题的最优解或者次优解。设和分别表示第t代的双亲和后代,遗传算法的一般结构可描述如下[3]：遗传算法过程：begin；初始化；评估；while不满足终止条件dobegin重组获得；评估；从和中选择；；endend图4-1遗传算法的一般结构通常初始化是随机产生的。重组包括交叉和变异来获得后代。实际上,遗传算法中有两类运算：〔1遗传运算：交叉和变异；〔2进化运算：选择。遗传运算模拟了基因在每一代中创造新后代的繁殖过程,进化运算则是种群逐代更新的过程。4.1.3遗传算法的特点遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法,与传统的优化算法相比,主要有以下特点[3]：〔1遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身,而遗传算法处理决策变量的某种编码形式,使得我们可以借鉴生物学中的染色体和基因的概念,可以模仿自然界生物的遗传和进化机理,也使得我们能够方便的应用遗传操作算子。〔2遗传算法直接以适应度作为搜索信息,无需导数等其它辅助信息。〔3遗传算法使用多个点的搜索信息,具有隐含并行性。〔4遗传算法使用概率搜索技术,而非确定性规则。4.1.4遗传算法的应用遗传算法提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域[2][5]：〔1函数优化。函数优化是遗传算法的经典应用领域,也是对遗传算法进行性能评价的常用算例。〔2组合优化。随着问题规模的增大,组合优化问题的搜索空间也急剧扩大,有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。遗传算法是解决这类问题的最佳工具之一。实践证明,遗传算法对于组合优化中的NP完全问题非常有效。〔3生产调度问题。生产调度问题在许多情况下所建立起来的数学模型难以精确求解,即使经过一些简化之后可以进行求解,也会因简化得太多而使得求解结果与实际相差甚远。现在遗传算法已成为解决复杂调度问题的有效工具,在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。〔4自动控制。在自动控制领域中有许多与优化相关的问题需要求解,遗传算法已在其中得到了初步的应用,并显示出了良好的效果。〔5机器人智能控制。机器人是一类复杂的难以精确建模的人工系统,而遗传算法的起源就来自于对人工自适应系统的研究,所以机器人智能控制理所当然地成为遗传算法的一个重要应用领域。〔6图像处理。在图像处理过程中,不可避免地会产生一些误差,这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。目前遗传算法已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。〔7人工生命。人工生命与遗传算法有着密切的关系,基于遗传算法的进化模型是研究人工生命现象的重要基础理论。遗传算法已在进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力,并且必将得到更为深入的应用和发展。〔8遗传编程。Koza发展了遗传编程的概念,他使用了以LISP语言所表示的编码方法,基于对一种树型结构所进行的遗传操作来自动生成计算机程序。〔9机器学习。基于遗传算法的机器学习,在很多领域中都得到了应用。4.2遗传算法实现的关键技术1、编码方法在遗传算法的运行过程中,它不对所求解问题的实际决策变量直接进行操作,而是对表示可行解的个体编码施加选择、交叉、变异等遗传运算,通过这种遗传操作来达到优化的目的,这是遗传算法的特点之一。在遗传算法中把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码。常用的编码方法有：〔1二进制编码：使用由二进制符号0和1所组成的二值符号集{0,1}进行编码,它所构成的个体基因型是一个二进制编码符号串。它是将可行解用固定长度的二进制串表示,串的长度与问题所要求的求解精度有关。〔2浮点数编码：个体的每个基因值用某一范围内的一个浮点数来表示,个体的编码长度等于其决策变量的个数。它所使用的是决策变量的真实值。〔3符号编码：个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。这个符号集可以是一个字母表,如{A,B,C,D,…}；也可以是一个数字序号表,如{1,2,3,4,5,…}；还可以是一个代码表,如{A1,A2,A3,A4,…}等等。2、适应度函数适应度是度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度[2]。遗传算法的一个特点是它仅使用所求问题的目标函数值就可得到下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。评价个体适应度的一般过程是：〔1对个体编码串进行解码处理后,可得到个体的表现型。〔2由个体的表现型可计算出对应个体的目标函数值。〔3根据最优化问题的类型,由目标函数值按一定的转换规则求出个体的适应度。3、选择算子遗传算法使用遗传算子〔或称为复制算子,ReproductionOperator来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。遗传算法中的选择操作就是确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。遗传操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。常见选择算子：〔1比例选择：各个个体被选中的概率与其适应度大小成正比。设群体大小为pop_size,个体的适应度为,则个体被选中的概率为：〔k=1,2,…,pop_size〔4.1〔2随机联赛选择：每次选取几个个体之中适应度最高的一个个体遗传到下一代群体中。在联赛选择操作中,只有个体适应度之间的大小比较运算,而无个体适应度之间的算术运算,故它对个体适应度是取正值还是负值无特别要求。〔3排序选择：对群体中的所有个体按其适应度大小进行排序,基于这个排序来分配各个个体被选中的概率。4、交叉算子遗传算法中的交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因,从而形成两个新的个体。它是产生新个体的主要方法。遗传算法中,在交叉运算之前必须对群体中的个体进行配对。常用的配对策略是随机配对,即将群体中的M个个体以随机的方式组成对配对个体组,交叉操作是在这些配对个体组中的两个个体之间进行的。常见交叉算子：〔1单点交叉〔One-pointCrossover：在个体编码串中只随机设置一个交叉点,实行交叉时,该点前或后的两个个体的部分结构进行互换,并生成两个新个体。〔2双点交叉〔Two-pointCrossover：在个体编码串中随机设置了二个交叉点,进行交叉时,将两个交叉点之间的部分基因进行互换。〔3均匀交叉〔UniformCrossover：两个配对个体的每一个基因座上的基因以相同的交叉概率进行交换,从而形成两个新的个体。5、变异算子遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换,从而形成一个新的个体。遗传算法导入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力。二是使遗传算法可维持群体多样性,以防止出现未成熟收敛现象。变异算子的操作步骤：在群体中所有个体的码串范围内随机地确定基因座。以事先设定的变异概率Pm来对这些基因座的基因值进行变异。常见变异算子：〔1基本位变异〔SimpleMutation是指对个体编码串中以变异概率Pm随机指定的某一位基因座上的基因值作变异运算。〔2均匀变异〔UniformMutation是指分别用符合某一范围内均匀分布的随机数,以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。〔3逆转算子〔InversionOperator在个体码串中随机挑选二个逆转点,然后将两个逆转点间的基因值以逆转概率Pi逆向排序。6、遗传算法的运行参数〔1编码串长度L。使用二进制编码时,L与问题所要求的求解精度有关；使用浮点数编码时,L与决策变量的个数n相等；使用符号编码是,L由问题的编码方式确定。〔2群体大小pop_size。pop_size表示群体中所含个体的数量。当pop_size取值较小时,可提高遗传算法的运算速度,却降低了群体的多样性,有可能会引起遗传算法的早熟现象；当pop_size取值较大时,又会使遗传算法的运行效率降低。〔3交叉概率Pc。交叉操作是遗传算法中产生新个体的主要方法,所以Pc取值较大。但若过大的话,又会破坏群体中的优良模式,对进化运算产生不利影响；若过小的话,产生新个体的速度又较慢。建议取值范围是0.4～0.99。〔4变异概率Pm。Pm取值过大,虽然能够产生较多的新个体,但也可能破坏掉很多较好的模式,使得遗传算法的性能近似于随机搜索算法的性能；若Pm过小,则变异操作产生新个体的能力和抑制早熟现象的能力就会较差。一般建议取值范围是0.0001～0.2。〔5终止代数T。T表示遗传算法运行到指定的进化代数之后就停止运行,并将当前群体中的最佳个体作为所求问题的最优解输出。一般建议取值范围是100～1000。5求解非线性规划问题的遗传算法设计传统的非线性规划算法的缺陷是计算烦琐且精度不高,稳定性差,对函数初值和函数性态要求较高,且容易陷入局部最优解。而遗传算法是一种全局搜索算法,可以克服传统的非线性规划算法容易陷入局部最优解的缺陷。因此,将遗传算法应用于非线性规划,是改善收敛效果,提高最优化质量的有效途径。本章就是介绍遗传算法在非线性规划中的具体应用,设计并实现求解非线性规划问题的遗传算法。5.1实用遗传算法设计1、编码方法设计非线性规划属于最优化设计的一种,属于约束优化问题,其最终目的是选择一种方法,使目标函数在满足约束的条件下达到最优。从非线性规划的数学模型可知,我们最终要求解的是一组解,其满足约束条件,并使目标函数达到最小值<或最大值>。我们将这组解作为染色体,其中每个相当于染色体上的基因,这也就是编码对象。之后的选择,交叉,变异就是对编码后的染色体基因进行运算。我们最终所求的解是n维向量空间的某子集〔定义域上的一个实数,若采用传统的二进制编码,则编码串长度不固定。如果采用固定长度的二进制编码,不仅会造成存储空间的极大浪费,而且在进行交叉和变异等遗传操作时,由于实际值不等长而很难确定交叉点和变异点,而且很容易产生无效解,降低了算法的效率；如果采用不定长二进制编码,则在进行交叉和变异等遗传操作时很难确定交叉点和变异点,而且容易产生无效解。而且采用二进制编码,又要牵涉到十进制与二进制的转换,在实际操作过程中要频繁进行编码和解码操作,费时费力。所以我们直接采用实数编码,即染色体基因串中基因座的值直接是每组解中各分量的实数值,不再对其进行其他任何形式的编码。每个染色体编码为一个和解向量维数相同的实向量[2]。2、适应度函数设计1满足约束由于对染色体作遗传运算时通常获得不可行的后代,因此运用遗传算法解非线性规划问题的核心问题是如何满足约束的问题。今年来,已经提出了几种运用遗传算法满足约束的技术,这些技术大致可以分为以下几类[3][16]：〔1拒绝策略拒绝策略抛弃所有进化过程中产生的不可行的染色体。这是遗传算法中普遍的作法。当可行的搜索空间是凸的,且为整个搜索空间的适当的一部分时,这种方法应该是有效的。然而,这是很严格的限制。例如,对许多约束优化问题初始种群可能全由非可行染色体构成,这就需要对他们进行修补。对于某些系统〔特别是可行搜索空间非凸时,允许跨过不可行域修复往往更容易达到最优解。〔2修复策略修补染色体是对不可行染色体采用修复程序使之变为可行的。对于许多组合优化问题,构造修复程序相对比较容易。Liepins和他的合作者通过对遗传算法的性能试验测试证明,对于一个有多个不连通可行集的约束组合优化问题,修复策略在速度和计算性能上都远胜过其他策略。修复策略取决于是否存在一个可将不可行后代转化为可行的修复程序。该方法的缺点是它对问题本身的依赖性,对于每个具体问题必须设计专门的修复程序。对于某些问题,修复过程甚至比原问题的求解更复杂。修复后的染色体可以只用来作评估,也可用来替代原染色体进入种群。Liepins等采用永不替代法,即不让修复过的染色体进入种群；而Nakano和Yamada采用了始终替代法。最近,Orvosh和Davis提出了所谓的5%规则：该规则对于多数组合优化问题,若令5%的修复过的染色体替代原染色体,则带有修复程序的遗传算法可取得最好的效果。Michalewicz等则认为对有非线性约束的优化问题,15%的替代率为最好。〔3改进遗传算子策略解决可行性问题的一个合理办法是设计针对问题的表达方式以及专门的遗传算子来维持染色体的可行性。Michalewicz等指出这种方法通常比基于惩罚的遗传算法更可靠。许多领域中的实际工作者采用专门的问题表达方式和遗传算子构造了非常成功的遗传算法,这已是一个普遍的趋势。但是,该方法的遗传搜索收到了可行域的限制。〔4惩罚策略上面三种策略的共同优点是都不会产生不可行解,缺点则是无法考虑可行域外的点。对于约束严的问题,不可行解在种群中的比例很大。这样,将搜索限制在可行域内就很难找到可行解。Glover和Greenberg建议的约束管理技术允许在搜索空间里的不可行域中进行搜索,这比将搜索限制在可行域内的方法能更快地活的最优解或获得更好的最终解。惩罚策略就是这类在遗传搜索中考虑不可行解的技术。2惩罚函数惩罚函数大概是用遗传算法解约束优化问题中最常用的技术。本质上它是通过惩罚不可行解将约束问题转化为无约束问题。在遗传算法中,惩罚技术用来在每代的种群中保持部分不可行解,使遗传搜索可以从可行域和不可行域两边来达到最优解。一般,解空间包含两部分：可行域和不可行域。我们不能对这些子空间作任何假设,特别是当它们是非凸或非连通时,如图5-1所示。控制非可行的染色体远不是一件容易事,从图5-1可知,不可行解b与最优解a的距离比不可行解d和可行解c都近。我们希望给b较小惩罚。可以相信,尽管b是不可行解,但它比c含有更多的有关最优点的信息。然而,我们对最优点没有任何先验知识,所以一般很难判断哪一点更好。图5-1解空间：可行域与不可行域惩罚策略的主要问题是如何设计一个惩罚函数,从而能有效地引导遗传搜索达到解空间的最好区域。不可行染色体和解空间可行部分的关系在惩罚不可行染色体中起了关键作用：不可行染色体的惩罚值相应于某种测试下的不可行性的"测量"。设计惩罚函数没有一般规则,这仍要依赖于待解的问题。惩罚技术通过惩罚不可行解将约束问题转化为无约束问题。构造带有惩罚项的适应度函数的方法一般有两种[3][9]用加法形式：〔5.1其中,x代表染色体；是问题的目标函数；是惩罚项。对于极大化问题,取〔5.2令和分别为现行种群中的的最大值和的最小值。并要求≤以避免出现负的适值。对于极小化问题,则取〔5.3另一种方法是采用乘法形式：〔5.4这时,极大化问题可取为〔5.5求极小化问题则取〔5.6本文中我们采用的是加法形式的惩罚。由于目标函数是求最小,较好的染色体具有较低的适值,因此我们取较大的数作为惩罚项,降低其被选中的概率。本文中选择的惩罚函数为：=-1*<<0>.**1e+3。当不满足约束时,也就是小于0时,括号里的逻辑运算结果为1,由于约束是要求大于等于0,则要对其进行惩罚,乘以-1相当于对取绝对值,再乘以一个较大的数1e+3,则此时为一个较大的实数,实现了其惩罚作用。当满足约束时,大于等于0,此时括号里的结果为0,也为0,即不对其进行惩罚。满足公式〔5.4。然后再根据公式〔5.1,将惩罚函数加入目标函数,也就是将约束条件加入目标函数,确定适应度函数[3][8]。3、选择算子设计遗传算法使用遗传算子来对群体中的个体进行优胜劣汰操作。我们采用最常见的比例选择算子,这是一种回放式随机采样的方法。其基本思想是：各个个体被选中的概率与其适应度大小成正比。多数情况下采用转轮法作为选择方法。它是一种正比选择策略,能够根据与适值成正比的概率选择出新的种群。转轮法由以下步骤构成：〔1对各个染色体计算适值=；k=1,2,…,pop_size〔5.7〔2计算种群中所有染色体的适值和〔5.8〔3对各染色体,计算选择概率；k=1,2,…,pop_size〔5.9〔4对各染色体,计算累积概率；k=1,2,…,pop_size〔5.10选择过程就是旋转转轮pop_size次,每次按如下方式选出一个染色体来构造新的种群：选择步骤：步骤一：在[0,1]区间内产生一个均匀分布的伪随机数r；步骤二：若,则选第一个染色体；否则,选择第k个染色体〔,使得成立。4、交叉算子设计虽然是实数编码,不过也可以模仿二进制表达的交叉。常用的交叉有单点交叉,双点、多点交叉等。考虑到算法效率和实现便捷程度,我们采用双点交叉。令双亲为和,随机生成1到n之间的两个数i和j,若两数不相等,则可作为交叉点。将产生的两个随机数之间的部分交叉,产生的后代为和。例如：现在依据选择算子选择了两条配对染色体：Chromosome1=[1,2,3,4,5],Chromosome2=[6,7,8,9,10]。若随机生成的交叉点为2和5,则将第2号和第5号位置之间的基因值互换,交叉后产生的新染色体为：NewChromosome1=[1,2,8,9,5],NewChromosome2=[6,7,3,4,10]。5、变异算子设计由于染色体基因较少,我们采用均匀变异：对每一个基因以一个指定的变异概率进行变异,若符合变异条件,则用一个随机产生的值替换原有的基因值。由于我们进行变异的粒度较小,为了增大变异力度,所以我们指定的变异概率较大,Pm=0.2。例如：对染色体Chromosome=[1,2,3,4,5]进行变异,从1号位基因开始,每次随机产生一个随机数x,若这个随机数x<Pm,则进行变异,在指定范围内随机产生一个实数,来替换掉1号基因位的值；若x>Pm,则本次不进行变异,继续对2号位基因值进行变异操作,直到5号位结束。由此就产生了新的染色体。6、遗传算子运行参数设计〔1编码长度。由于我们采用实数编码,即染色体基因串中基因座的值直接是每组解中各分量的实数值,每个染色体编码为一个和解向量维数相同的实向量。本文中有7个决策变量,因此染色体长度,也就是编码长度取7。〔2种群大小pop_size。种群大小pop_size表示种群中所含个体的数量。pop_size取值的大小与遗传算法运行速度,种群多样性有关。一般根据问题规模而定,这里我们取300。〔3交叉概率Pc。交叉操作是遗传算法中产生新个体的主要方法。若Pc过大,会破坏群体中的优良模式,对进化运算产生不利影响；若Pc过小,产生新个体的速度又较慢。我们为了获得较大的种群多样性,产生较多的新个体,Pc值取为0.8。〔4变异概率Pm。变异操作是为了保证遗传算法具有局部搜索能力,同时也能保证群体多样性,抑制早熟现象。若Pm取值过大,虽然能够产生较多的新个体,但也可能破坏掉很多较好的模式,使得遗传算法的性能近似于随机搜索算法的性能；若Pm取值过小,则变异操作产生新个体的能力和抑制早熟现象的能力就会较差。这里由于是对每个基因座进行变异操作,为了保证变异效果,Pm取值较大,为0.2。〔5终止代数T。为保证遗传算法能获得近似最优解,T取值为150。即遗传算法迭代150次停止,将得到的最佳个体作为最优解输出。5.2求解非线性规划问题的遗传算法程序设计算法过程描述由前面遗传算法的算法描述再结合本次毕业设计的实际情况,我们设计了以下的具体算法流程[3][9][16]。步骤如下：〔1初始化遗传算法的运行参数：种群大小pop_size,每条染色体基因串长度length,交叉概率Pc,变异概率Pm,算法迭代次数T,当前迭代次数t。〔2根据所给x的范围,种群大小,染色体长度,随机生成符合条件的初始种群A。〔3将约束条件加入目标函数,确定适应度函数,计算适值e。〔4对适值e从小到大排序,排序后的适值记为s,并记录变动情况l。〔5根据排序结果把每一代最小适值赋给M,并记录局部最优值对应的位置〔行,用的行向量B表示。〔6输出每次迭代t对应的局部极值位置B和局部最优值s<1>。〔7计算累积概率。〔8用转轮法进行选择运算。种群由A进化为A1。〔9双点交叉实现交叉运算。实现遗传算法的第一次遗传运算,种群更新为A2。〔10均匀变异实现变异过程。实现第二次遗传运算,种群更新为A3。〔11更新种群,将A3赋给A。〔12判断是否满足迭代结束条件。满足转〔13,不满足转〔3,继续迭代。〔13对每代最小适值M排序,me为排序后的向量。〔14输出最小适值Min,即为所求全局最优。遗传算法程序流程图图5-2求解非线性规划问题的遗传算法程序流程图5.2.3遗传算法中所设计的辅助算法的设计〔1随机数生成。程序中多处涉及到随机数的生成,像一开始初始种群的生成,后面的选择、交叉、变异的循环条件判断,都有用到。这里我们使用常用的rand函数。rand函数的作用是生成0～1之间的浮点型矩阵,通过对函数的简单运算可以生成我们想要的确定范围内的矩阵。〔2累加函数cunsum。程序中计算累积概率部分,可以使用循环运算实现,但我们使用MATLAB中更便捷的函数cumsum直接计算元素累加,如a=[1234],则cumsum<a>=[13610]。〔3上取整函数ceil。ceil<>是向正无穷大舍入,如ceil<2.5>=3,配合rand函数可以随机生成一定范围内的整数。〔4排序函数。因为我们所求是最小化问题,在庞大的种群和多次迭代过程中为方便找出局部最小值和全局最优值,我们可以对每次结果进行排序。sort函数实现按升序排序,如[s,l]=sort<e>,对e从小到大进行排序,s为排序后的矩阵,l为变动情况。〔5选择函数。选择函数是为交叉操作从当前种群中选择两条染色体来进行交叉操作。我们采用转轮法〔RouletteWheel来选择染色体。具体过程如下：=1\*GB3①利用rand函数产生一个0～1之间的随机数r。=2\*GB3②从第一条染色体起,将当前种群中各染色体的选择概率进行累加,当选择概率总和大于等于rand时停止。=3\*GB3③累加结束时的染色体〔即概率之和刚好大于随机数rand的那条染色体即为被选中的染色体。6算法的结果分析6.1概述在以上算法分析设计的基础上,我们用MATLAB语言分别实现了求解非线性规划问题的遗传算法和外点罚函数法。本章我们通过运行实际的算法程序,通过对运行结果进行统计分析,比较两种算法各自的优越性。6.2结果比较为了能直观地表现两种算法的实际执行结果,我们将两种算法的执行结果以图表的形式直观地表达出来。两种算法的计算结果如表6-1,6-2所示。我们通过统计两种算法所得最优值的变化,来比较两种算法的收敛效果。为了充分比较两种算法收敛效果,我们对遗传算法分别采用大小为300和200的两个种群,惩罚函数法分别取初始惩罚因子M为10和1,两种算法分别执行算法10次,得到结果如表6-1所示。表6-1最优适值表遗传算法惩罚函数法执行序号种群300种群200初始惩罚因子M=10初始惩罚因子M=11703.678340689.693431711.150702737.2106052701.530725724.697202817.991629685.3209413702.253432707.968223762.156619749.3026324703.625196713.398107682.4467671497.2846835698.693085717.147253784.342585691.9136556705.082156703.719043685.732024711.1507027714.335545704.113105736.895652817.9916298690.639063719.278202681.898495762.1566199694.401838692.633396684.731999682.44676710704.034177697.344160791.385667784.342585我们统计两种算法之间的最大值、最小值、均值和方差。得到表6-2。表6-2均值和方差表遗传算法惩罚函数法种群300种群200初始惩罚因子M=10初始惩罚因子M=1最大值714.335545724.697202817.9916291497.284683最小值690.639063689.693431681.898495682.446767均值701.83706.9992733.87811.9121方差40.9985136.33732703.859983.06我们将表6-1中的数据以图的形式进行表示,得到两种算法取得最优适应度值的变化曲线,如下图所示。图6-1遗传算法最优值变化曲线图6-2惩罚函数法最优值变化曲线图6-3综合比较曲线从表6-2可以看出,遗传算法所得最优适值的最大值、平均值、方差要比惩罚函数法小得多,说明遗传算法收敛效果更好,结果更合理；图6-1和图6-2说明两个算法对自身参数设定的敏感性,可以看出相对于惩罚函数法,遗传算法受初始参数影响要小很多；图6-3综合比较曲线将两个算法结果放在一个图中比较,可以看出,遗传算法的变化曲线非常平稳,波动较小,而惩罚函数法对初始参数特别敏感,出现了大的波动。这充分体现了遗传算法的优越性,遗传算法的全局搜索能力使其能够不受初始点的影响而找到近似全局最优解。通过以上分析可以看出,求解非线性规划问题的遗传算法能够克服传统算法对初始值敏感,容易陷入局部最优解的缺陷,收敛效果更好,性能更稳定,结果更合理。同时我们比较两种算法的运行时间,如下表。表6-3运行时间比较表遗传算法惩罚函数法种群300种群200初始惩罚因子M=10初始惩罚因子M=1最大值3.0310002.0470000.2340000.203000最小值2.9060001.8910000.1250000.140000均值2.951501.96120.172000.156100从表中可以看出,惩罚函数法在运行时间上明显优于遗传算法,说明传统算法也有其可取优势,不可能被完全取代。下图即为求解非线性规划问题的遗传算法最优适值变化曲线：图6-4求解非线性规划问题的遗传算法最优适值变化曲线7总