搜索
应用遗传算法求解非线性问题的全局解的方法姓名：喻光辉学号：200910520101班级：09信息与计算科学摘要：本文简要阐述了遗传算法的基本原理,探讨了在matlab环境中实现遗传算法，通过求解一个非线性极小化问题，先用一般的方法求解该问题，然后再用遗传算法求解，通过对求解结果的分析说明该算法能够对函数的全局最优进行搜索，深刻体现了遗传算法的优越性，并以一个简单的实例说明所编程序在函数全局寻优中的应用。Abstract：TheprincipleofgeneticalgorithmhasbeenpresentedanditsrealizationinMATLABhasbeendiscussed.AfunctionoptimizationproblemhasbeengiventodemonstratetheglobaloptimizationfunctionalityoftheMATLABprogram.Thisarticlediscussedhasrealizedthegeneticalgorithminthematlabenvironment,throughsolvedamisalignmentminimizationproblem,usedthegeneralmethodtosolvethisquestionfirst,thenusedthegeneticalgorithmtosolveagain,throughtosolvedtheresulttheanalysistoexplainthatthisalgorithmcouldbemostsuperiortothefunctionoverallsituationcarriesonthesearch,hasmanifestedthegeneticalgorithmsuperiorityprofoundly.关键词：遗传算法非线性规划matlabkeywords：GeneticalgorithmNonlinearprogrammingmatlab一、遗传算法简介遗传算法（GeneticAlgorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了很有影响的专著《AdaptationinNaturalandArtificialSystems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法是从代表问题可能潜在的解集的一个种群（popula-tion）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，因而需要进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。遗传算法(GeneticAlgorithm,GA)是借鉴生物界自然选择和群体进化机制形成的一种全局寻优算法。与传统的优化算法相比,遗传算法具有如下优点[1]:1)不是从单个点,而是从多个点构成的群体开始搜索;2)在搜索最优解过程中,只需要由目标函数值转换得来的适应值信息,而不需要导数等其它辅助信息;3)搜索过程不易陷入局部最优点。目前,该算法已渗透到许多领域,并成为解决各领域复杂问题的有力工具[2]。在遗传算法中,将问题空间中的决策变量通过一定编码方法表示成遗传空间的一个个体,它是一个基因型串结构数据;同时,将目标函数值转换成适应值,它用来评价个体的优劣,并作为遗传操作的依据。遗传操作包括三个算子:选择、交叉和变异。选择用来实施适者生存的原则,即把当前群体中的个体按与适应值成比例的概率复制到新的群体中,构成交配池(当前代与下一代之间的中间群体)。选择算子的作用效果是提高了群体的平均适应值。由于选择算子没有产生新个体,所以群体中最好个体的适应值不会因选择操作而有所改进。交叉算子可以产生新的个体,它首先使从交配池中的个体随机配对,然后将两两配对的个体按某种方式相互交换部分基因。变异是对个体的某一个或某一些基因值按某一较小概率进行改变。从产生新个体的能力方面来说,交叉算子是产生新个体的主要方法,它决定了遗传算法的全局搜索能力;而变异算子只是产生新个体的辅助方法,但也必不可少,因为它决定了遗传算法的局部搜索能力。交叉和变异相配合,共同完成对搜索空间的全局和局部搜索。二、遗传算法的实现过程2.1初始化定义整数pop_size为种群中染色体的个数，种群的大小视实际情况而定，一般需要30~100个。初始种群的每个个体都是在matlab中通过随机方法产生，并把它作为进化的第一代。2.2评价采用基于序的评价函数,评价个体或解的好坏，并作为以后遗传操作的依据。如设给定参数a，定义基于序的评价函数为：rangel(i)=a(1-a)i-1,i=1,2,….,pop_size其中i=1说明染色体是最好的，i=pop_size说明是最差的。2.3选择选择操作是为了决定那些个体可以进入下一代，一般采用赌轮盘选择法实现，适应性越强的染色体，该染色体被选择的概率就越大。符合适者生存的规律。在该算子中,采用了最优保存策略和比例选择法相结合的思路,即首先找出当前群体中适应值最高和最低的个体,将最佳个体best2indiv保留并用其替换掉最差个体。为保证当前最佳个体不被交叉、变异操作所被坏,允许其不参与交叉和变异而直接进入下一代。然后将剩下的个体evo2gen按比例选择法进行操作。所谓比例选择法,也叫赌轮算法[4],是指个体被选中的概率与该个体的适应值大小成正比。将这两种方法相结合的目的是:在遗传操作中,不仅能不断提高群体的平均适应值,而且能保证最佳个体的适应值不减小。2.4交叉通过两个相互配对的染色体依据交叉概率p_crossover（事先给定）按某种方式相互交换其部分基因，从而形成两个新的个体。为确定交叉的父代，从i=1到pop_size重复产生随机数crossover,如果crossoverp_crossover,则染色体作为父代，对于双亲和，交叉产生的后代为：。其中c为随机产生的数，若不满足约束条件，则重新选择c，直到满足约束条件为止。2.5变异定义参数p_mutation作为遗传系统的变异概率，类似于交叉操作从i=1到pop_size，重复下面过程：从区间（0，1）中产生随机数mutation,如果mutationp_mutation则选择染色体作为变异的父代。用V=(v1,v2,…,vm)表示上面产生的父代，并按下列方法对其进行变异。记M是初始化过程化中所定义的那个足够大的数。在空间中随机产生一个变异方向d，如果染色体V+M.d经检验是不可行的，则置M为0和M之间的随机数，这样又得到了一个新的染色体，再检验其可行性。重复这个过程直到所得的染色体可行为止。如果在预先给定的迭代次数之内没有找到可行解，则置M=0.最后，用染色体X=V+M.d取代原来的染色体V。由上可总结该算法的步骤如下：算法[1]（遗传算法过程）步骤1初始产生popsize个染色体。步骤2对染色体进行交叉和变异操作。步骤3计算所有染色体的函数值。步骤4根据目标函数值，计算每个染色体的适应度。步骤5通过旋转赌轮，选择染色体。步骤6重复步骤2至步骤5直到满足终止条件。步骤7最好的染色体作为最优解。其基本流程可归纳如下图:三、数值举例现在讨论如下的极小化问题现在用传统的非线性方法求解,当初值为x0=[0,0]时，最小值结果为：-1.5915，当初值为：x0=[1,1]时，结果为：-0.8949。由此可见，传统方法求解具有多个极小值点的函数时，求解结果的值与初始值的选择有关，所得的最优解为局部最优解。同时通过画该目标函数的曲面图1-1可知，该曲面存在多个局部极小点。所以，应用传统的解法，容易陷入局部极小值区域。对于这样的问题，用传统的非线性规划求解算法不容易求得全局最优解。现在用遗传算法求解如下：用染色体Xx=(x1,x2)作为解的代码，用以下方法把染色体X变成染色体V=(v1,v2)并把V作为相应的解，x1=v1,x2=v2其中V可由下面的检验函数检验若(v13[]v1-3[]v23[]v2-3)返回0；否则返回1；这里检验数数值为0表示不可行，1表示可行。易知该模型的可行集包含在下列的超几何体中U={(v1,v2)|0v11,0v21}然后就可以容易地从这个超几何中抽取初始染色体v1=U(0,1),v2=U(0,1)(1)其中U(a,b)表示服从区间[a,b]上的均匀分布的随机数，如果该染色体不可行，则拒绝接受，应再由式(1)重新产生一个新的染色体，如果可行，则接受它成为种群中的一名成员。在本次应用遗传算法求解过程中，我所设置相应的参数为：种群规模为30，交叉概率为0.95，变异概率为0.3，基于序的评价系数的参数a为0.05,经过100次迭代后，遗传算法得到最好解为（源代码在后面附录）：V=(v1,v2)=(-3.0000,2.8021)也即是X的最优解为：(x1*，x2*)=(-3.0000,2.8021)目标最优值为：-9.5784。可见利用遗传算法求解，所得的结果是全局最优解，着充分体现了该算法的优越性。目标最优值为：-9.5784。可见利用遗传算法求解，所得的结果是全局最优解，着充分体现了该算法的优越性。参考文献：[1]刘勇,康立山,陈毓屏.非数值并行算法(第二册)———遗传算法[M].北京:科学出版社,1997.[2]席裕庚,柴天佑,恽为民.遗传算法综述[J].控制理论与应用,1996,13(6):6972708.[3]韩祯祥,文福拴.模拟进化优化方法及其应用———遗传算法[J].计算机科学,1995,22(2):47256.[4]刘宝碇、赵瑞清、王刚著.不确定规划及应用北京.清华大学出版社，Springer2003.8[5]韩娟遗传算法概述郑州交通学院西部探矿工程学报2007年第2期[3]张兴华殷铭基于matalb的遗传算法的实现东南大学电子技术应用学报2000年第1期[6]雪定宇陈阳泉著高等应用数学问题的matlab求解清华大学出版社