张砦-遗传算法在多目标优化中的应用

遗传算法在多目标优化中的应用张砦目录一、遗传算法概述二、多目标优化问题三、实例1——Rosenbrock函数最值问题四、实例2——智能组卷问题一、遗传算法概述1.1遗传算法的生物学基础1.2遗传算法搜索机制1.3遗传算法的发展1.4基本遗传算法（SGA）1.5遗传算法的特点1.6遗传算法的收敛性分析1.7遗传算法研究的主要问题1.8遗传算法的应用1.1遗传算法的生物学基础生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法(GeneticAlgorithms，简称GAs)所借鉴的生物学基础是生物的遗传和进化。(1)生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；(2)染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；(3)生物的繁殖过程是由其基因的复制过程来完成的；(4)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。(5)对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。1.2遗传算法搜索机制遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象（染色体的变化），将实际问题的解答描述成染色体的形式，进行类似生物进化现象的操作以求解。对每次迭代中保留的候选解，按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。1.3遗传算法的发展(1)萌芽期(50年代后期至70年代初期)•50年代后期，一些生物学家着手采用电子计算机模拟生物的遗传系统，尽管这些工作纯粹是研究生物现象，但其中已使用现代遗传算法的一些标识方式。•1965年，德国的L.Rechenberg等人正式提出进化策略的方法，当时的进化策略只有一个个体，而且进化操作也只有变异一种。•1965年，美国的L.j.Fogel正式提出进化规划，在计算中采用多个个体组成的群体，而且只运用变异操作。•60年代期间，美国J.H.Holland在研究自适应系统时，提出系统本身与外部环境相互协调的遗传算法。1968年，J.H.Holland教授又提出模式理论，它成为遗传算法的主要理论基础。•1967年，Bagley发表了关于遗传算法应用的论文，在其论文中首次使用“遗传算法（GeneticAlgorithm）”一词。(2)成长期(70年代中期至80年代末期)•1975年，J.H.Holland教授的专著《AdaptationinNaturalandArtificialSystem》正式出版，全面地介绍了遗传算法，人们常常把这一事件视作遗传算法问世的标志，Holland也被视作遗传算法的创始人。•1975年，De.Jong在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。•1987年，美国D.Lawrence总结人们长期从事遗传算法的经验，公开出版《GeneticAlgorithmandSimulatedAnnealing》一书，以论文集形式用大量实例介绍遗传算法。•1985年，作为Holland的学生，D.E.Goldberg博士出版专著《GeneticAlgorithms——inSearch，OptimizationandMachineLearning》，全面、系统地介绍遗传算法，使这一技术得到普及与推广。该书被人们视为遗传算法的教科书。•1985年，在美国举行第一届遗传算法国际学术会议(InternationalConferenceonGeneticAlgorithms，简称ICGA），与会者交流运用遗传算法的经验。随后，每2年左右都举行一次这种会议。(3)发展期(90年代以后)90年代，遗传算法不断地向广度和深度发展。•1991年，D.Lawrence出版《HandbookofGeneticAlgorithms》一书，详尽地介绍遗传算法的工作细节。•1996年Z.Michalewicz的专著《遗传算法+数据结构=进化程序》深入讨论了遗传算法的各种专门问题。同年，T.Back的专著《进化算法的理论与实践：进化策略、进化规划、遗传算法》深入阐明进化算法的许多理论问题。•1992年，Koza出版专著《GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection》，该书全面介绍了遗传规划的原理及应用实例，表明遗传规划己成为进化算法的一个重要分支。•1994年，Koza又出版第二部专著《GeneticProgrammingⅡ:AutomaticDiscoveryofReusablePrograms》，提出自动定义函数的新概念，在遗传规划中引入子程序的新技术。同年，K.E.Kinnear主编《AdvancesinGeneticProgramming》，汇集许多研究工作者有关应用遗传规划的经验和技术。1.4基本遗传算法（SGA）1.4.1基本遗传算法的构成要素(1)染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集{0，1}组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：100111001000101101，就可表示一个个体，该个体的染色体长度是18。(2)个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。(3)遗传算子基本遗传算法使用下述三种遗传算子：•选择运算：使用比例选择算子；•交叉运算：使用单点交叉算子；•变异运算：使用基本位变异算子。(4)基本遗传算法的运行参数基本遗传算法有下述4个运行参数需要提前设定：•M：群体大小，即群体中所含个体的数量，一般取20-100。•T：遗传运算的终止进化代数，一般取100-500•pc：交叉概率，一般取0.4-0.99•pm：变异概率，一般取0.0001-0.1说明:这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。1.4.2基本遗传算法的形式化定义基本遗传算法可定义为一个7元组：GA＝(M,F,s,c,m,pc,pm)M——群体大小；F——个体适应度评价函数；s——选择操作算子；c——交叉操作算子：m——变异操作算子；pc——交叉概率；pm——变异概率；1.4.3基本遗传算法的实现（1）编码与解码假设某一参数的取值范围是[umin,umax]，我们用长度为λ的二进制编码符号串来表示该参数，则它总共能够产生2λ种不同的编码，参数编码时的对应关系如下：00000000…00000000＝0umin00000000…00000001＝1umin+00000000…00000010＝2umin+2……11111111…11111111=2λ–1umax其中，为二进制编码的编码精度，其公式为：=umaxumin2λ1x=umin+(bi·2i-1)·1i=lUmaxumin2l1假设某一个体的编码是：x：blbl-1bl-2……b2b1则对应的解码公式为：[例]设-3.0≤x≤12.1,精度要求=1/10000，由公式：Umaxumin2l=+11/1000012.1+3.0+1==151001即：217151001218x需要18位{0/1}符号表示。如：010001001011010000解码：x=umin+(bi·2i-1)·1i=lUmaxumin2l1=-0.3+70352(12.1+3)/(218-1)=1.052426=Umaxumin2l1得：（2）个体适应度评价(1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度F(X)就等于相应的目标函数值f(X)，即：F(X)＝f(X)(2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：minf(X)＝max(-f(X))但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求。（3）选择算子作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。比例选择算子：指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。轮盘选择：轮盘法的基本精神是：个体被选中的概率取决于个体的相对适应度，显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。（4）交叉算子作用：通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。单点交叉算子的具体计算过程如下：Ⅰ.对群体中的个体进行两两随机配对。Ⅱ.每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。Ⅲ.对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。单点交叉A；1011011100A’：1011011111B：0001110011B’：0001110000（5）变异算子基本位变异算子：最简单和最基本的变异操作算子。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1，反之，若原有基因值为1，则变异操作将其变为0。具体执行过程：Ⅰ.对个体的每一个基因座，依变异概率pm指定其为变异点。Ⅱ.对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。A：1010101010A’：1010001010变异点基本位变异开始Gen=0编码随机产生M个初始个体满足终止条件?计算群体中各个体适应度从左至右依次执行遗传算子j=0j=0j=0根据适应度选择复制个体选择两个交叉个体选择个体变异点执行变异执行交叉执行复制将复制的个体添入新群体中将交叉后的两个新个体添入新群体中将变异后的个体添入新群体中j=j+1j=j+2j=j+1j=M?j=pc·M?j=pm·L·M?Gen=Gen+1输出结果终止YNYYYNNNpcpm1.4.4算法流程图1.5遗传算法的特点（1）群体搜索，易于并行化处理；（2）不是盲目穷举，而是启发式搜索；（3）适应度函数不受连续、可微等条件的约束，适用范围很广。遗传算法的本质：对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。1.6遗传算法的收敛性分析遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。(1)种群规模对收敛性的影响通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。(2)选择操作对收敛性的影响选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。(3)交叉概率对收敛性的影响交