河海大水资源系统工程教案02基于遗传算法的水资源系统优化方法

PAGEPAGE54第2章基于遗传算法的水资源系统优化方法2.1水资源系统优化概述人们在工作、学习、生活、娱乐等活动中总希望活动的效果尽可能好些，这种寻求最优化的思想几乎渗透到人类社会实践活动的一切过程中，大量的社会实践活动逐渐形成优化概念。另一方面，最优化的法则同时也隐藏于各种生物进化过程和各种非生物演化过程中。正是在这些大量社会实践和自然观察的基础上，人类逐渐形成了优化概念。根据系统观点，任何研究问题都可成为系统。所谓系统优化，就是如何寻找影响系统目标的优化变量各分量的某种取值组合，使得系统目标函数在给定约束条件下达到最优或近似最优这样一类问题，解决这类问题的方法称为系统优化方法（optimizationmethodofsystem）[25]。水资源系统优化就是各种优化方法在水资源系统中的应用过程，其中称目标函数、优化变量和约束条件为水资源系统优化的三要素[11]。水资源系统的规划、设计、运行、管理中有许多问题的目标函数和约束条件是复杂的非线性函数，如区域水资源的最优配置、水利工程规模的最优选择、水库和水电站参数的最优选择、水电站的最优运行管理等问题。水资源系统优化，要求在有限的水资源条件下，通过系统内部各变量之间、各变量与各子系统之间、各子系统之间、系统与环境之间的组合和协调，最大限度地满足生产、生活、生态等各用水部门的可持续利用要求，使水资源系统具有最好的社会经济效益和生态环境效益。显然，研究各种水资源系统优化问题在系统工程理论和实践中都具有十分重要的意义[8，13-15，90-93]。水资源系统优化方法也是应用其它水资源系统工程方法的基础，换言之，其它水资源系统工程方法的实现过程从某种角度看都是特定的优化过程。例如，应用水资源系统建模方法的过程，实质上就是如何调整模型的结构形式和模型参数的取值，使得系统模型计算值与系统实际值之间的误差最小；应用水资源系统评价方法的过程，实质上就是如何最佳地把多层次多维系统评价指标转换成单层次一维系统评价指标的过程，这一转换过程既要反映评价对象的主要特征信息，也要反映评价者的价值判断，两者的最终平衡过程就是一种优化过程；水资源系统决策分析问题，等价于以益损值为目标函数、行动方案为优化变量、自然状态为约束条件的复杂优化问题，该问题的求解结果与决策者的经验、态度和判断有很大关系。因此，水资源系统优化方法已成为当代水资源系统工程的“主干线”。根据系统目标、约束条件和优化变量等不同角度，可对现有的水资源系统优化方法进行不同的分类。如根据系统目标的特征，可把系统优化方法分为如下3大类[11，13，94]：一是单层单目标最优化方法，又称标量最优化方法，它是用一个实数变量来表示系统目标的最优化方法。水资源系统的各种功能如防洪、灌溉、发电、航运、旅游、水产养殖等，如果能用可以公度的货币进行统一测度，就成为一个单层单目标优化问题，其最优化方法又可细分为：①无约束优化方法、等式约束优化方法和不等式约束优化方法；②确定性优化方法、随机性优化方法、模糊性优化方法[95]、灰色性优化方法[96]、混沌性优化方法[97]；③线性优化方法和非线性优化方法；④静态优化方法和动态优化方法；⑤连续变量优化方法和离散变量优化方法（包括图论方法、网络优化方法）等。二是单层多目标最优化方法，又称向量最优化方法，它是用两个或两个以上实数变量来表示多个系统目标的最优化方法。例如在流域水资源规划与管理大系统中，所追求的系统目标有国民经济总效益、地方效益的合理分配、社会效益、生态环境效益等多个目标，其中有些目标可能是不相容的，例如防洪与发电、防洪与供水等，有些目标可能是不可公度的，例如防洪子目标系统中减轻财产损失与减少人员伤亡。向量通常是不能最优化的。目前，单层多目标优化方法的出发点或者是把单层多目标最优化问题转换成标量最优化问题，或者引入决策者的价值判断于优化过程。前者如加权法、约束法；后者如目的法、代用价值权衡法等。三是多层多目标最优化方法，又称大系统最优化方法。很多复杂水资源系统问题是由两个或两个以上具有层次性的目标组成，不同层次目标具有相对独立性，它们都服务于上层目标，系统目标体系具有层次结构形式。水资源大系统（例如中国西北水资源承载力系统、南水北调水利工程系统）往往是较大的流域或者是跨流域、跨省市的大区域，在这样的大系统中水资源的各种目标相互交叉、甚至相互矛盾，例如防洪的目标常与发电、灌溉、城市供水的目标发生矛盾，城市供水又与灌溉发生矛盾等，而且常伴有各种自然的和人为的不确定性（包括随机性、混沌性、模糊性等）。如何在这样复杂的系统中协调各种目标的取值，以求得整个系统的满意解，作为水资源大系统最优化方法的最后解。其最优化方法目前仍处于初步阶段，主要以近30年发展起来的大系统分解协调方法，即把大系统分解为多层次结构的优化模型，先从最低层模型开始进行目标的优化，通过伪变量或伪变量函数将信息依次传递到上一层模型，直到最高层才能确定伪变量，然后再向下层传递，从而使得各子系统目标得到定量的优化值，同时也求得整个系统的最优解，实际上这是整个系统的满意解。水资源大系统最优化方法一般是有条件的，在多数情况下只能求得权衡协调后的非劣解集，最后通过决策者和系统工程工作者之间的协调，选定比较合理可行的方案。另外，文献[13]提出了水资源大系统多目标递阶分析的分解—聚合方法。不同的水资源系统优化问题，水资源系统优化方法的求解过程一般也会不同。从方法论的角度看，水资源系统优化方法的一般步骤大致可以分为如下6步[5，98]：①确定被优化系统的目标体系，并用经济、时间、精度、实物等性能指标表示。目标体系不同，相应的优化结果就不同。性能指标选得是否合理直接影响到所得优化结果的实用性。②选择影响系统目标的独立的优化变量集。③确定各优化变量的取值范围即约束条件。约束条件可以用等式、不等式和集合形式等表示，可以是显式约束，也可以是隐式约束。④确定系统优化模型的结构形式，即用目标函数和约束条件来描述各优化变量之间、各优化变量与各性能指标之间的关系式。⑤针对所确定的系统优化模型的结构形式，运用相应的解析优化方法或数值优化方法等进行最终求解。⑥对所得优化结果的合理性、计算精度和敏感性等进行分析和验证。可对优化结果进行协调、修正、评定，确定最终的系统优化结果，作为决策依据，也可根据优化结果的实际应用效果对以上步骤进行不断修改和完善，因此，复杂水资源系统的优化常常是一个多次迭代的过程。能否顺利求解水资源系统优化问题的关键表现在如下几个方面[99]：①目标函数的数目、关系、层次结构、性态、连续性、可微性、凸性、非线性、可计算性等。②优化变量的数目、类型及其关系、取值范围等。③约束条件的数目、关系、连续性、可微性、凸性、非线性等。④初始可行点是否易于获取、可行域的复杂程度、可行域外的目标函数和约束函数是否可计算。⑤系统优化模型中各参数的估计值的可靠性和精度如何。⑥能否对最优解的大致范围、是否存在多个局部最优解等问题有初步的了解和估计。⑦能否理解所用的算法、能否获得或编制该算法的可靠程序。目前，研究水资源系统优化问题的前沿问题主要有[100]：①在不断接近实际的复杂水资源系统优化问题的过程中，需要在求解的思想方法有所更新，优化的方法论需要更新和突破。②目前大量的优化结果偏理论、与真正的实际问题有差距、实用性差，支持决策的作用不强。③受常规系统优化方法的影响，系统优化的数学模型在对系统信息和决策者要求的变化的适应性方面存在局限性。④微观、小型系统的优化模型较多，而宏观大系统的优化模型很少；在系统规划阶段系统优化模型的应用不多，在系统运行管理阶段能实际“在线”应用的优化模型也不多。⑤正面对待实际系统所面临的诸多不确定性和风险性的优化模型不多。⑥非线性优化方法在实际应用中存在着收敛性和局部优化等难点。优化方法需与决策者的要求、实际问题的数据基础和计算技术相适应。⑦系统优化问题的求解需要充分利用决策者的价值判断和决策环境的信息，需要优化系统的分析者、决策者和决策环境通过人—机交互系统进行协调。受天文因子、气候因子、水文气象因子、植被土壤因子、地貌因子、地质因子和人类活动因子等众多因子的综合影响，实际水资源系统优化问题都是十分复杂，水资源系统优化方法至今仍是目前水资源系统工程界的热点和难点之一，就国内外研究现状而言，这方面的研究仍处于积极探索和不断发展阶段。基于以上论述，本章将结合笔者多年来水资源系统优化研究工作的结果，着重探讨用遗传算法处理水资源系统优化问题的几种方法，包括基于二进制编码的遗传算法、基于实数编码的遗传算法、基于整数编码的遗传算法等，同时也为应用以后各章的系统工程方法提供先进的基本工具。2.2遗传算法的理论基础2.2.1遗传算法的运行过程分析[24]自然界中通过基因机制，一系列具有智能、自组织、自修整的器官在不断产生和进化着。遗传算法（GA）就是这样一类利用自然选择和群体遗传机制在高维空间寻优的方法，它不一定能寻得最优（optimal）点，但是它可以找到更优（superior）点，这种思路与人类行为中成功的标志是相似的。例如不必要求某个围棋高手是最优的，要战胜对手只需他（她）比其对手更强即可。因此，GA可能会暂时停留在某些非最优点上，直到变异发生使它迁移到另一更优点上。遗传算法的整体行为是复杂的，但它的运行过程较为简单。遗传算法随编码方式、遗传操作算子的不同而表现为不同形式，因此难以象传统的共轭梯度法那样从形式上给以明确定义，它的识别标志在于它是否具有模拟生物的自然选择和群体遗传机理这一内在特征。为便于说明GA运行过程中的主要特征，现举例来阐述。例2.1设函数优化问题为[101](2.1)遗传算法是这样“翻译”上述优化问题的：把自变量x作为由基因构成的染色体，也称个体，优化准则函数（目标函数）f(x)作为个体适应度函数，优化准则函数和约束条件一起作为个体的生存环境，个体进化的目标是生成具有最佳适应度的基因型个体。GA求解上述问题的步骤如下：步骤1：解变量的编码（encoding）。编码策略采用二进制数编码，设编码长度为e，每个二进制位称之为基因（gene），把变量的取值范围[a，b]等分成2e–1个子区间，即(2.2)式中，gk为二进制数字串的第k位值（基因值）。因此某个二进制数字串si可表示为…(2.3)通过编码，把变量取值范围[a，b]离散成2e个网格点，每个网格点与二进制数字串、个体相互一一对应。步骤2：初始父代个体群的随机生成（productionofforerunnerindividuals）。设群体规模为n个（偶数）个体，从上述2e个二进制数字串均匀随机选取n个串，作为GA的初始点，开始进化迭代。步骤3：父代个体的解码（decoding）和父代个体的适应度评价（evaluationfunctionforindividualfitness）。把二进制数字串｛si｝（i=1，2，…，n）按编码策略解码成变量｛xi｝（i=1，2，…，n）。定义二进制数字串的适应度函数为F(x)=f(x)。把第i个个体xi代入适应度函数，得相应的适应度函数值为Fi=f(xi)。Fi越大则适应度越高，第i个个体越优秀。步骤4：父代个体的概率选择（selection）。令第i个个体的选择概率pi为(2.4)从已有父代群体的n个个体中以概率pi选择第i个个体，这样共选择n个个体，适应度高的个体有更多的机会保留到下一代（generation），适应度低的个体再生（reproduction）的机会少、被淘汰的概率大。可见，选择算子实现了达尔文进化论的“适者生存”、“优胜劣汰”的原则，它是GA的基本算子。步骤5：父代个体的杂交（crossover）。由步骤4得到的n个个体两两配成n/2对双亲。以杂交概率pc选取某对双亲二进制数字串，随机选取两位置cs1和cs2，然后交换cs1和cs2之间的基因，产生两个子代个体，子代个体组合了父代个体的特性，见图2.1。这种杂交算子称为两点杂交算子。杂交算子体现了基因材料交换和信息交换的思想，以实现高效搜索，它模拟了生物遗传规律，是GA的一个重要算子。(父代个体1)1 0 1 0 0 (新子代个体1)1000 0(父代个体2)0 1 0 1 0 (新子代个体2)0111 0(a)cs1=cs2=3(父代个体1)1 1 0 1 0 (新子代个体1)101 0 0(父代个体2)0 0 1 0 1 (新子代个体2)010 1 1(b)cs1=2，cs2=4(父代个体1)1 0 1 0 0 (新子代个体1)0 1 0 1 1(父代个体2)0 1 0 1 1 (新子代个体2)1 0 1 0 0(c)cs1=1，cs2=5图2.1两点杂交示意图步骤6：子代个体的变异（mutation）。对子代个体，以变异概率pm随机地改变二进制数字串中某位的值，即将原值为1的变为0，将原值为0的变为1。同生物界一样，GA中发生变异的概率是很低的，目前常用的取值范围是pm=0.00～0.05[101]。变异的作用是避免在群体遗传、进化中失去一些有用的基因，保持群体中基因的多样性，它是阻止GA早熟收敛的一种有效措施。步骤7：进化迭代（evolutionaryiteration）。由步骤6得到的n个子代个体作为下一轮进化过程的父代，算法转步骤3。如此反复迭代，使群体的平均适应度值不断提高，直到得到满意的个体或达到预定的进化迭代次数，则算法终止。此时，适应度值最高的个体对应的解即为所求优化问题的解。上述遗传算法中，当两点杂交改为单点杂交时，就成为标准遗传算法（SGA）[29]，它的计算机程序流程图如图2.2所示。在例2.1的式(2.1)中现取a=0，b=31，编码长度e=5，群体规模n=4，杂交概率pc=1.0，变异概率pm=0.003。GA的遗传过程见表2.1[101]。在表2.1中，第(1)栏是随机产生的初始群体二进制数字串；第(2)栏是与串对应的优化变量；第(3)栏是与串对应的个体适应度；第(4)栏是选择概率；第(5)栏是选择后的群体，可见原来的“00101”串由于其适应开始(begin)开始(begin)GA参数GA参数e,n,pc,pm的设置（presettingparametersofGA）解变量的编码（encoding）解变量的编码（encoding）初始父代群体的生成（初始父代群体的生成（productionofforerunnerindividuals）父代个体的解码和适应度评价（decodingandevaluation父代个体的解码和适应度评价（decodingandevaluation）父代个体的概率选择（父代个体的概率选择（selection）、杂交（crossover）、变异（mutation）算法终止条件满足否?（endingcondition算法终止条件满足否?（endingcondition）否(no)输出结果（output），结束（end）输出结果（output），结束（end）图2.2标准遗传算法(SGA)的计算机程序流程图度值低在这次选择中被淘汰，而“11011”串因其适应度值高而被选中两次；第(6)栏是随机产生的配对序号，即1与4、2与3个体相互配成双亲；第(7)栏是随机产生的两个杂交位置cs1和cs2；第(8)栏是交换cs1和cs2之间的基因而产生的新群体；第(9)栏是新群体对应的变量；第(10)栏是新群体的适应度，可见适应度值总和从选择前的“62”提高到选择后的“84”，最高适应度值从“27”提高到“31”。第一次进化迭代中GA共处理20个基因，没有发生变异现象。表2.1GA的遗传过程(本表根据文献［101］表1整理、修改而得)个体序号(0)初始个体串si(1)变量xi(2)适应度Fi=xi(3)选择概率pi(4)选择后的个体(5)配对个体序号(6)杂交位置cs1cs2(7)新个体(8)变量xi(9)适应度Fi(10)11010020200.321010043310000161620101010100.1601010315110112727300101550.081101121501010101041101127270.4411011133111113131总数62621.008484平均值15.515.50.252121最大值27270.443131图2.3是群体在某待优化变量x的变化区间［–650，1350］随GA演进过程中的发展趋势图[102]。图2.3说明：当GA演进过程开始时，GA对群体在搜索范围内的选择比较均匀，只是局部区域（x=600附近）稍高些；当演进到第20次进化迭代时已出现对群体的选择向真值附近集中的明显趋势，在x=300附近出现峰值，选择次数约为18，而其它区域最大选择次数也仅为8；当演进到60次进化迭代时GA对真值x=350附近的选择已超过总选择次数（80）的80%以上。可见，随着GA的演化，群体在其搜索范围内逐步向最优点附近集中，最后绝大多数个体分布在最优点附近的一个狭窄带上。(a)初始分布(b)第20次进化迭代后的分布(c)第60次进化迭代后的分布图2.3群体在优化变量的变化区间上的发展趋势示意图从文献[79]中图4至图6的遗传结果分布也可看出：初始群体的个体分布是基本随机的，随着进化迭代的进行，大部分个体逐渐向较优区域集中，表示遗传过程正在“优胜劣汰”，同时使得较优区域内的采样密度加强，找到最优解的概率也在增大；与此同时，在可行域的其它地方仍有个体存在，可以有效地防止陷入局部极小；经过10次进化迭代后大部分个体均已集中在点（0.404，638.7）附近。2.2.2遗传算法的基本理论分析[24]上述GA的运行过程分析使我们直觉到GA模拟了生物的进化机理，运行简单而有效，但其中的许多随机性操作使GA的整体行为复杂化，因此有必要进一步分析GA的机理以免对GA的性能发生疑虑。目前，GA的基本理论主要有模式定理和欺骗问题。（1）模式定理（SchemaTheorem）[28，33，34]模式定理是研究较深入、影响较大的GA理论，它将GA的运行过程理解为模式操作过程，并从模式运算的角度解释GA的运行特性。在GA中，称个体基因串中相似样板为模式（schema），也称图式，它描述的是一个基因串的子集合，在该集合中的基因串之间在某些特征位上具有相同基因值。这里只考虑二进制数编码，则模式的形式可描述为……，，（k=1，2，…，e）(2.5)式中，e为串的长度（编码长度），gk为串中第k位的基因，统配符*为任意基因，代表该位的值不定，即它可以是“0”，也可以是“1”。显然，模式中“*”越多，则该模式表示的串的个数就越多，它所表示的变量区域就越大。一个串共属于含有该串任何位基因的所有模式。例如，“11011”这个串既属于模式“11***”，同时也属于模式“****1”和模式“1*0*1”。其中，模式“1*0*1”是如下4个串的集合（e=5）：1*0*1={11001，11011，10001，10011}对串长为e的模式空间的维数为｜｜=(2.6)一个模式H一般可用4个参数来描述，即：串的长度e（lengthofastring），模式的阶O(H)（orderofaschemaH），模式的长度(H)（lengthofaschemaH）和模式的维数D(H)（dimensionofaschemaH）。其中，O(H)是H中固定基因位的个数，(H)是H中最前固定基因位和最后固定基因位之间的距离，D(H)是H中包含串的个数，且有(2.7)例如对模式H=*1*1*1，有O(H)=3，(H)=4，D(H)=2e–O(H)=26–3=8。GA的工作特点之一是直接对串空间进行操作。在一定程度上，我们不再把串仅仅看作问题变量的另一种形式，因为较高适应度串中的相似性有利于引导GA搜索，这意味着串空间的操作蕴含模式空间的隐形处理，这就是GA运行中所表现出来的最大特点，即隐含并行性（implicitparallelism）[28]。在GA中，一个串共属于含该串任何位元的所有模式（区域），例如11001串，既属于11***模式，也属于1***1模式和**00**等模式。含有不定位元（*）个数越多，模式所代表的区域就越大，群体中表示该模式的串就越多。一般地，对于k个元的字母表（对于二进制编码，k=2），定义在该字母表上的长度为e的位串中所可能包含的最大模式数目为(k+1)e（因为在e个位置中的任一位置上均可取k个字符中的任一个和统配符*，这样共有(k+1)个不同的选择，e个位置上的全排列数为(k+1)e）；一个特定个体串共属于ke个模式，规模为n的群体共属于从ke到nke个模式，具体结果依赖于群体的多样性（若n个位串完全一样则群体匹配的模式数为ke；若n个位串相匹配的模式都不一样则群体匹配的模式数为nke）。与一个模式相匹配的位串之间具有相似性，即使规模不大的群体中也包含了丰富的（从ke到nke个模式）有关这种相似性的信息。这些相似性以及和适应度值之间的相关性正是使GA能进行有效搜索的根本原因所在[34]。因此，一种控制着几千个位元串的GA，实际上能表示数量极大的模式，这就是GA的隐含并行性，它是GA优于其它优化方法的关键所在。GA的这种隐含并行性使其能利用较少的初始串，经遗传演化来检验和发掘搜索解空间中的大量模式，它也有助于GA处理非线性问题。在非线性问题中，一个串有两个特殊的基因块，该串的适应度远大于（或远小于）属于每个基因块的适应度的总和。但是，杂交使GA隐含并行性的作用复杂化。杂交的目的是检验新个体的适应度值，杂交可能使子代离开父代所在的模式而迁移到另一模式，致使不同模式的采样率偏离于平均适应度的严格比例，同时也会降低进化的速度。两个串的子代离开父代所在的模式的概率取决于该模式的确定位元1或0之间的距离，对10****模式，该概率为0.2，而对1****0模式，则该概率为1.0。确定位元1或0挨在一起的模式称为密排基因块，由于它们在杂交后几乎保持原样，这些基因块几乎把携带它们的串的平均适应度按比例传递到子代中，且在串的群体中按密排方式定义的基因块的数量远大于其它串的数量，因此，GA仍表现出隐含并行性。编码长度e=3的二进制串的搜索空间为23个串，此时的搜索空间可以表示为简单的立方体，每个模式对应于搜索空间中的一个超平面，与一个特定模式相匹配的所有位串都在它的超平面上。例如，3阶模式（即一个确定的串，例如“110”）表示搜索空间中的一个点，2阶模式（例如“*01”）表示为一条线，1阶模式（例如“*0*”）表示为一个平面，0阶模式（例如“***”）就表示为整个搜索空间。这一描述可以一般化到高维空间，其中的点、线、平面相应地一般化到e维空间中不同维数的超平面，其中，e为串的长度。一般地，每个串对应于一个e维超立方体的一个角，并且它共属于(2e–1)个不同的超平面。这种把搜索空间表示成超立方体，不仅是一种描述空间的方法，而且它与遗传搜索的理论基础密切相联系。从上述模式的几何表示这一角度来看GA的搜索过程，则可以发现GA是通过不同超平面之间的信息交换、迁移来提高搜索性能的，GA的运行过程就是在模式空间中搜索最优模式的过程。而从信息传递角度看，GA在运行过程中涉及了4个空间，即：问题变量空间、串空间、模式空间和适应度函数空间，它们之间的关系可用图2.4表示[101]。模式空间模式空间隐含并行性串空间GA算子操作：串空间GA算子操作：选择、杂交、变异解码编码变量空间变量空间评价f(x)适应度函数空间适应度函数空间图2.4GA运行过程中的四个空间[101]现在从定量方面进一步分析群体中特定模式所含的个体数目在GA运行过程中的变化情况。设第k次进化迭代时，在规模为n的群体p(k)中某特定模式H所含的个体串数目记为m(H，k)。在GA选择操作时H中的串si按概率，（i=1，2，…，n）(2.8)选择，这种选择方式称之为比例选择。其中f为串的适应度函数；在一次进化迭代中串si的选择次数为npi。令群体中某模式H的平均适应度为f(H)，则(2.9)若考虑选择是有放回地抽样，且在产生p(k+1)时必须从p(k)中选n个位串进行交配，则在第k+1次进化迭代时，群体中模式H所含个体的数目m(H，k+1)为(2.10)式中，fE为群体的平均适应度。若设f(H)=(1+c)fE，其中c为常数，则有(2.11)若从k=0开始，则可得(2.12)上式表明，经选择操作后，平均适应度值高于（或低于）整个群体的平均适应度值的模式，它所含个体的数目将以指数形式增加（或减少）。上述是仅考虑选择操作的作用。设单点杂交概率、单点变异概率分别为pc和pm，某模式H经杂交、变异操作后的生存概率（survivalprobability）分别为psc和psm，则[33]≥(2.13)（«1）(2.14)于是，某模式H在下次进化迭代中经GA的选择、杂交、变异操作作用后，该模式所含个体的数目为≥(2.15)上式就是GA的基本定理——模式定理（schematheorem）。模式定理表明：长度(H)短、阶O(H)低且平均适应度高于整个群体平均适应度的模式，它所含个体串的数目在GA的运行过程中将以指数形式增加。这个结果是指导标准遗传算法（SGA）编码设计的重要原则。选择的编码策略须尽量使(H)短的、O(H)低的、和问题的本质紧密相关的模式对应于所求问题的解。例如，选择一个使问题得以自然表达的最小字母表进行编码，这样使确定规模的群体中包含尽可能多的模式。由于二进制编码方案能获得最大的模式数，故在GA中被广泛采用。上述分析表明，作为GA基本理论的模式定理，为我们提供了一种解释GA运行机理的数学方法，同时对选择和设计编码策略和遗传操作算子策略具有重要的指导作用。（2）欺骗问题GA的另一理论是欺骗问题（deceptiveproblem）。称那些引导遗传算法出错的函数与编码组合为遗传算法的欺骗问题[33，34]。已有的研究结果表明，GA欺骗问题往往包含弧立的最优点，即最好的点往往被差点所包围。文献[33]提出了建筑块假设：在GA运行中短的、低阶的、高于群体平均适应度的模式（建筑块，buildingblocks）逐步组合形成高阶高于平均的模式，直至产生最优解。根据模式定理，如果一个问题的编码满足建筑块假设，用GA求解效率较高，否则效率较低。低阶建筑块错误地引导搜索过程，不能发现高阶高于平均的模式，最终使算法发散，找不到最优解，这种现象就是欺骗问题。研究欺骗问题是为了预测给定问题用GA求解的难易程度。Goldberg设计了一个最小欺骗问题，旨在尽可能使问题的编码违背建筑块假设，使高阶建筑块最优解不能生成；实验结果表明，用GA求解包含欺骗的问题时得到最优解与得不到最优解的情况均可能发生，这说明欺骗不是衡量用GA解决问题的难易程度的唯一标准[103]。2.2.3遗传算法的收敛性分析[24]收敛性和收敛速度是评价迭代算法性能的重要指标。目前对GA收敛性分析的各种结论都是基于标准遗传算法（SGA）模型，而复杂遗传算法的收敛性分析仍是困难的。定义2.1设Fk*=max{f(s(j，k)|j=1，2，…，n}是第k次进化迭代时群体{s(j，k)}中的最大适应度值，F*=max{f(s(j)|j=1，2，…，2e}是GA所求问题的全局最大适应度值。则当且仅当(2.16)成立时，称GA是概率性全局收敛的。其中，p(Fk*=F*)为Fk*=F*的概率。定义2.2[101]设全局最优串为s*=g1*g2*…ge*，则称任一gi*为有效基因。若在某位基因位上，群体中所有串都没有该基因位的有效基因，则称群体有效基因缺失，否则称群体有效基因不缺失。定义2.3设f(sk*)=max{f(s(j，k)|j=1，2，…，n}是标准遗传算法SGA第k次进化迭代时群体{s(j,k)}中的最大适应度，sk*为此时的群体最优串（elitist）。若f(s(j，k+1)>f(sk*)，则令sk+1*=s(j，k+1)，否则sk+1*=sk*。称上述操作为最优串保存操作。加入最优串保存操作的SGA称之为最优串保存标准遗传算法（elitistmaintainingsimplegeneticalgorithm-EMSGA）。定义2.4[62]具有比例选择操作、自适应杂交操作和自适应变异操作的遗传算法，称之为自适应遗传算法（adaptivegeneticalgorithm）。它的杂交概率pc、变异概率pm随被操作串的适应度值的变化而作相应变化：(2.17)(2.18)≤(2.19)式中，fmax为群体中最大适应度，fE为群体的平均适应度，为用于杂交操作的二个串中较大的适应度，f是变异串的适应度。由式(2.17)、(2.18)和(2.19)知，0≤pc或pm≤1；当=fmax时pc=0，当f=fmax时pm=0。因此，通过这种自适应杂交算子操作和自适应变异算子操作，可同样实现最优串保存。GA的极限分析定理[34，101]：如果在进化迭代过程中，GA保留最优串，并且算法以杂交和变异为随机性搜索算子，则对于一个全局优化问题，随着进化代数趋于无穷，GA将以概率1找到全局最优解。该定理表明，GA能够对搜索空间进行持续的搜索，因此GA特别适于全局优化问题。实现GA的全局收敛的基本策略是生成的群体的有效基因不缺失的概率尽可能大，并在GA运行中把已发现的最优串保存下来。最优串保存可以通过合适的选择、杂交、变异算子操作来实现。随机产生的初始父代群体，它的有效基因缺失的概率为(2.20)式中，n为群体规模。例如pag(30)=9.3×10–10，此时有效基因缺失的概率很小。这说明GA在实用中具有较好的全局收敛性。式(2.20)表明，群体规模越大，全局收敛性越好。选择算子操作是产生有效基因缺失的主要原因。对于非线性强的多峰优化问题，GA在某次进化迭代过程中获得的最优解很可能是局部最优解，从而选择较多此类基因串，造成有效基因缺失。这种过强的选择会把群体强有力地吸引到强的局部最优状态，是出现早熟收敛（prematureconvergence）的主要原因。理论上，变异算子操作能够避免有效基因缺失。但由于在标准遗传算法中，变异概率pm很小，而且变异算子操作是在串的随机基因位上进行的。因此，标准遗传算法的变异算子操作实际上并不能有效地避免有效基因缺失。为阻止GA的早熟收敛，需设计合适的选择算子操作，以避免选择算子操作过度受适应度的影响；另外需设计合适的杂交算子操作、变异算子操作和引入新的基因算子操作，以保持群体基因的多样性，摆脱局部最优状态。

另外，Rudolph[52]和恽为民等[104]应用齐次有限马尔科夫链证明了标准遗传算法（SGA）能遍历群体空间，但SGA不是全局收敛的。这说明，SGA具有全局搜索的能力，能发现全局最优解，但不能保证每次运行都能收敛于全局最优解，即使计算时间趋于无穷大。这一点也为许多数值实验所证实。实际应用中更为关心的遗传算法计算效率的分析，目前仍是十分困难的。GA的收敛速度，不仅与选择、杂交、变异等算子的操作方式有关，而且也与编码策略、初始群体串的分布特性以及实际问题本身的规模、非线性程度和复杂程度都有密切的联系。每一次进化迭代有多少新模式产生也是GA计算效率的重要特性。文献[29]得出了每次进化迭代有效保留的模式个数为o(n)3的估计，文献[101]获得了每次至少产生o(2n–1)数量级的新模式的结果。2.2.4标准遗传算法的改进方式标准遗传算法（SGA），至今仍是国内外GA应用中常用的实现方案，SGA由二进制数编码、随机产生初始群体、个体适应度评价、比例选择算子、单点杂交算子、随机位变异算子和进化迭代共7个步骤组成[33]。大量的理论和应用研究表明，SGA存在的主要问题有[24，105]：①SGA的拓扑结构尚未统一。群体规模、选择方式、杂交方式、变异方式、收敛判据和其它算法控制参数均需经验确定，易出现早熟收敛。②SGA的全局优化性能部分来自于初始群体的随机生成和杂交算子，但由于群体的有限性与解空间的高维性之间的矛盾，使得搜索的全局性受到很大限制。另外，由于变异概率一般较小，使得这些少量变异新个体会被大量老个体迅速“同化”，因此SGA的全局搜索能力十分有限。特别是较小的群体规模和选择操作不可避免地使SGA存在“近亲繁殖”、早熟收敛。③SGA适于解决缺乏解析知识、复杂、有噪声的动态系统，目前更适于求解组合优化问题，对实变量优化问题不太适合。④SGA的计算精度受编码长度控制，为得到所需精度的解通常需要耗费比较长的计算时间，对解空间的大小变化缺乏适应性。为完善SGA理论基础和拓宽其应用领域，迫切需要对SGA进行多方面的改进[24，71，105]。实际上GA是优化计算的一种方法论，它提供的只是一种算法框架[24，28，71]，在该框架的每一步中，都可有多种不同的实现方法，从而可构成多种不同格式的GA实现方案，SGA只是GA最早实现的一种经典格式。换言之，在SGA各步骤中都可有不同的替代方案和改进方式来提高SGA的求解效率，以更好地解决各种复杂的实际问题。鉴于此，本节拟对SGA的各种改进方式进行系统深入的探讨，旨在促进GA更深入的理论研究和更广泛的工程应用。2.2.4.1改进编码方式编码是把各种优化问题的解空间表示为统一形式的数字串空间，其逆过程称为解码。借助编码，遗传算子可以有独立于具体优化问题的统一形式，从而使GA具有广泛的适用性。编码既是GA理论中的基础，又是GA应用中的首要问题。编码方案将影响GA的收敛速度和搜索效率，在应用中选择或设计一种便于GA求解问题的编码方案常常需要对问题有深入的理解。GA从原理上要求使用者采用尽量简单的编码方式来表示问题的解空间，这样可以使低阶、长度短的、适应度值高的基因模式能够产生更多的后代从而加快收敛。因此SGA采用二进制数编码，而且在SGA运行过程中编码方法保持不变。对于实变量优化问题的求解精度要求较高时，二进制数编码长度将很大，导致计算量激增，并直接影响全局极值的求解。目前常用的改进方式之一是采用动态参数编码[34]，它先让SGA从低精度开始搜索，当发现最佳个体越过某个值后，起用变焦操作，从而提高一倍精度，如此反复。与此类似，可利用在SGA运行过程中搜索到的优秀个体子群体来逐步缩小SGA的搜索空间，以解决二进制数编码与解精度的矛盾[106]。为克服SGA频繁的编码和解码运算、计算量大、只能产生离散的网格点、还可能产生额外的极值点等缺点，提高算法的运行速度和解的精度，可采用实数编码，通过变换，把初始变化区间[a(j)，b(j)]上的第j个优化变量x(j)对应到[0，1]区间上的实数y(j)，这样每个个体用与解向量同样长的实数向量进行编码[80]。研究表明，对于行商问题、资源分配问题等许多组合问题，一般用整数编码更为方便且有效[71，107]，对运输问题可用矩阵编码来自然表达解的结构[71]，而对于演化自适应建模问题则采用树编码较为合适[63，71]。不同的编码方式将影响遗传算子的形式和GA的进化层次。例如，二进制数编码的进化层次是个体串中的基因，而实数编码的进化层次是个体串，因此相应的理论基础将不同。对于SGA：使用二进制数编码的杂交算子的搜索能力比实数编码的搜索能力强，而且随着群体规模的扩大，这种差别就越明显；而实数编码对于变异操作的群体稳定性比二进制数编码的要好。这些结论在应用SGA时可为选择合适的编码方案提供理论依据[108]。总之，编码须考虑优化问题的解空间特征，所采用的编码方式除了必须保证不丢失全局最优解外，还应考虑SGA的求解效率，并尽量避免产生不可行解，编码方式也可随着算法不同运行阶段而取不同的形式。2.2.4.2改进初始群体的生成方式实际应用中初始群体的分布将影响SGA的搜索效率。由于SGA的杂交位置、变异位置都是随机选取的，这使得SGA的收敛速度对初始群体的选择的依赖性较强，收敛不稳定。用随机方法产生初始群体时，要求它们均匀分布于整个解空间，以便SGA搜索全局最优解。若初始群体缺乏多样性，则选择算子和杂交算子的寻优作用不能发挥，而依靠小变异概率的变异算子进行全局寻优搜索的效率也很低。为提高SGA求解的效率和解的质量，避免早熟收敛，目前的主要改进方式，一是尽可能使初始群体分布于整个解空间的不同区域中[109]，二是增大群体规模，如取300以上来增强初始群体的多样性[106]，三是根据应用问题的具体情况采用其它优化方法如BP算法[110]、启发式方法或人工设定方式等来生成初始群体；四是采用粗粒度、小生境等并行遗传算法方式[109，111]；五是群体规模随着演化的推进而改变[63，71]。2.2.4.3改进适应度函数的定义方式适应度函数F一般是目标函数f的一种数学变换，个体的F值越大，表示该个体的适应能力越高，对应的解越佳[34]，F的形式依赖于实际问题。F值是指导SGA搜索的主要信息来源，它的定义在SGA应用中十分重要。对于有约束优化问题，SGA一般采用罚函数方法将其转化为无约束优化问题[34，71]。在SGA运行早期个体差异较大，当采用比例选择方式时，产生后代的数目与父代个体的适应度值大小成正比，在SGA运行早期容易使个别好的个体的后代充斥整个群体，出现早熟，而在SGA运行后期个体适应度值趋于一致，优秀的个体在产生后代时优势不明显，使整个群体进化停滞。为调节SGA执行过程中个体的复制数目以提高算法的性能，对F进行适当的比例变换很有必要。常用的变换有[34]：线性比例变换（u(F)=aF+b）、幂比例变换（u(F)=Fa）和指数比例变换（u(F)=e–bF）；适应度函数也可在SGA进化迭代过程中进行适当的调整，即在进化早期使群体内各个体差距不是很大，避免早熟收敛，而在进化后期又要拉开距离，以强化竞争和加速收敛，如刘云峰等根据目标函数E（模型的拟含方差）来定义如下适应度函数，其中Ei为第i个个体的目标函数值，N为群体规模，T为类似于模拟退火算法中温度参数，T值随进化次数g的增加而减少[111]。2.2.4.4改进选择算子选择算子主要模拟生物进化过程中的适者生存、优胜劣汰规则。通过选择，低适应度函数值个体趋向于被淘汰，而高适应度函数值个体趋向于被复制，选择算子的作用是提高群体的平均适应度值，同时也损失了群体的多样性，在总体上决定群体向着目标函数值改善的方向进化。SGA采用的转盘式比例选择算子或繁殖池比例选择算子，是根据某个体的适应度函数值占群体适应度函数值之和的比例来确定该个体的选择概率[33，34，63]，当群体规模较小或群体最大适应度函数值与最小适应度函数值之比很大时，这些比例选择算子将使群体的多样性很快丧失，导致早熟收敛。目前的改进方式主要有：一是排序选择[63，67]，即个体的选择概率只决定于该个体适应度函数值在群体中的序号（按适应度函数值从大到小排序），不受适应度函数值的分布和取值范围的直接影响，因此排序选择不需对适应度函数值进行调整；二是竞争选择[63]，即每次选择就在群体中随机选取的k个个体中选择适应度函数值最大的个体，竞争选择可避免超级个体（当前最大适应度函数值个体）的影响，可在一定程度上克服早熟收敛；三是通过随着SGA的运行调节适应度函数的形式，来调整个体的选择概率的表达式，如Boltzmann竞争选择等[63]，或个体选择概率的表达式直接与算法运行的进化代数建立函数关系；四是有条件选择，如根据某个体与超级个体的距离是否大于给定值来决定该个体的取舍[80]；五是最优个体保存策略也可视作一种改进的选择算子。2.2.4.5改进杂交算子杂交算子主要模拟群体染色体的信息交换机制。通过两个父代个体的杂交产生两个子代个体，每个子代个体都包含两个父代个体的遗传信息。杂交算子是GA的主要搜索算子，也是GA区别于其它演化算法的重要特征，其作用是可以检测搜索空间中的新点，它有可能提高群体中最佳个体的适应度函数值，但也可能破坏有效模式。杂交算子一般随编码方式的不同而不同。对二进制数编码，杂交算子可取[63]一点杂交（交换两个父代个体串中随机选取的某位以右的子串）、两点杂交（交换两个父代个体串中随机选取的某两位之间的子串）、多点杂交（一次随机选取多个位，然后间断交换两个父代个体串的对应子串）、均匀杂交（以概率交换两个父代个体串中每一位值）等算子，杂交概率也可随个体的适应度函数值作自适应变化。SGA只采用一点杂交算子，而采用上述其它杂交算子则有利于一个个体承载更多解的信息以提高搜索效率。目前普遍认为两点杂交和均匀杂交这两种方式都优于一点杂交。其中，两点杂交破坏模式的概率较小、有利于保护优良模式，比较适用于较大群体规模；均匀杂交破坏模式的概率较大、但有利于搜索许多新模式，比较适用于较小群体规模。对实数编码，杂交算子主要有离散杂交和算术杂交两类[63]，前者是以某概率分布随机选取两个父代个体的各个分量，然后交换以生成子代个体，后者是以[0,1]区间的均匀随机数对两个父代个体的各个分量进行线性组合来生成子代个体。离散杂交生成的子代个体是父代个体各分量构成的超立方体的顶点，算术杂交生成的子代个体则是父代个体各分量构成的超立方体的内部点，因此算术杂交的搜索范围大于离散杂交。对整数编码，为使杂交后所得到的子代个体满足优化问题的约束条件，常需要设计特定的杂交算子，如对行商问题可采用部分匹配杂交算子、顺序杂交算子等[36]。对其它编码，一般需要优化问题的领域知识来设计特定的杂交算子，这是当前研究的前沿问题之一。杂交算子另外的改进方式很多：如限制杂交，即若杂交后的个体不可行，则按一定概率决定是否接受，以尽可能保证杂交后的解是可行的；杂交概率可随个体的适应度函数值作自适应变化；在杂交算子操作之前可考虑根据个体的适应度函数值来配对等。2.2.4.6改进变异算子变异算子主要模拟生物个体的随机突变现象。对个体串的某些基因位值进行随机改变，其作用是增加GA运行中群体的多样性，是对有效基因缺失的一种补救措施[101]，同时也对因选择操作失去的群体多样性的恢复具有潜在的作用，是实现GA全局优化性能的重要算子之一。由于变异算子在SGA中只是以很小的变异概率pm对个体串的二进制位值进行取反运算，所以它在SGA中的作用远不如杂交算子。变异算子一般随编码方式的不同而不同。对二进制数编码，变异算子可取一点变异（个体每次变异只有一个二进制位的值发生改变）、两点变异（个体每次变异有两个随机选取的二进制位的值发生改变）、多点变异、均匀变异（以某概率随机选取个体串中每一位值进行取反）、逆转变异[36]（随机选取个体串中的两个位，然后将该两个位之间的二进制位值以某概率进行倒序）等算子。对实数编码，变异算子不仅恢复因选择操作失去的群体多样性，而且成为一种重要的搜索算子，目前提出的改进的变异算子很多[63]。其中，均匀变异是随机选取个体的某个分量，然后用该分量的定义域内的均匀随机数代替；正态变异是用正态分布的随机变量代替个体的各个分量；非一致性变异是变异范围随着演化的推进而逐步变小[71]；自适应性变异是个体适应度函数值越小则变异范围越大[71]；混沌具有初值敏感性、内在随机性和遍历性等特性，近来提出了混沌变异算子[112]；以上这些变异算子的组合。对整数编码，变异算子可取[107]换位变异（随机选取个体串上不同的两个基因位置，并交换该两个基因位上的值）、随机变异（随机生成一个新个体，并以某概率代替原个体）、倒位变异（随机选取个体串上不同的两个基因位置，然后对这两个位置之间的基因值反序排列）。变异算子另外的改进方式很多：限制变异，即若变异后的个体不可行，则按一定概率决定是否接受，以尽可能保证变异后的解是可行的；变异概率可以随个体的适应度函数值作自适应变化等。2.2.4.7引进新的遗传算子根据现代进化理论和群体遗传学的成果，引进基因级的新的操作算子如二倍体、隔离、易位等算子，群体级的新的操作算子如迁移、分享、挤聚等算子[63]，以及个体级的其它新的操作算子。2.2.4.8改进算子的执行方式例如，选择算子、杂交算子和变异算子对二进制数编码可以采用串行执行方式，而对实数编码则可采用并行执行方式[24]。2.2.4.9增强SGA搜索过程的方向性引入问题领域知识，采用启发式策略，或利用SGA运行进程中产生的优秀个体的信息[24]，来进一步增强搜索寻优的方向性。2.2.4.10SGA与其它算法相结合GA思想的精髓是交叉，GA的结构是开放的，与具体优化问题无关，所以它易与其它算法相结合。例如，SGA与改进的单纯形法[67]、复合形法[113]、BP算法[34，110]、模拟退火方法[34，63]等相结合，可以更好地解决各种实际问题。2.2.4.11改进父代更新方式SGA把经遗传算子生成的子代群体作为新的父代群体。为克服这种更新方式所带来的演化过程的波动性，改进的方式主要有：一是方式[63]，即从父代群体与其子代群体共+个个体中选取个最优个体作为新的父代群体；二是方式[63]，即对规模为的群体经遗传算子作用生成（大于）个子代群体，再从该子代群体中选取个最优个体作为新的父代群体；三是选取子代个体和父代个体的目标函数值与该两个体与超级个体的距离之比值较小者作为新的父代个体[80]。2.2.4.12改进算法的终止条件常用的改进方法是基于某种判定标准，判定群体已收敛并不再有进化趋势后作为终止条件。例如，把连续几代群体的平均适应度函数值（或最佳适应度函数值）之差小于某个小值，群体适应度函数值的方差小于某个小值，或群体中最佳适应度函数值与群体平均适应度函数值之差小于某个小值，作为终止条件。由于实际优化问题的复杂性和GA本身的运行机理尚不完全被认识清楚，实用中经常根据人机交互信息来确定算法何时终止[24]。2.2.4.13改进算法控制参数的设置SGA中，二进制数编码长度e决定于实际问题解变量的取值范围和对解的精度要求，在进行解变量编码时，可以将各个解变量分别单独编码，也可以将全部解变量编入一条染色体上，各解变量只占染色体的一段。群体规模n是指每一父代个体的总数目，也等于初始群体的个体数目。为了使初始群体在解空间均匀分布，n不能取得太小，否则不能保证群体的多样性，易出现早熟收敛；而如果n选得太大，不但增加了计算时间，而且也不能有效地改进进化迭代的解。确定n的大小需要综合考虑全局收敛速度和计算量；同时，n的确定与所求问题的非线性程度和复杂程度有关，非线性越强、问题越复杂，n应取得越大。目前n还只能依靠经验选定。杂交概率pc越大，优秀个体出现的概率越大，新旧个体替换越快，收敛越快。变异概率pm越大，SGA开拓新的搜索区域的能力越强，产生新个体越多，优秀个体出现的概率越大，找到全局最优的可能性也越大，但是SGA越趋向于随机搜索，算法的收敛性越差。在SGA实际应用中，pm取得太小，个体产生变异的能力不够，会出现整个群体过早地演变成同一个体，但这个个体极可能是一个局部最优点；pm取得太大，个体经常在变异，群体的平均适应度值改变很慢，降低了收敛速度。SGA的这些参数的设置对SGA的优化性能影响很大，但目前对这些参数的设置尚未统一，如Schaffer[114]建议SGA的最优参数范围是：n=20～30，pc=0.75～0.95，pm=0.0~0.05，席裕庚等建议SGA的最优参数范围是[35]：n=20～200，pc=0.5～1.0，pm=0.0～0.05。为探讨SGA控制参数的最优设置，J.Grefenstette利用二级SGA来优化SGA的控制参数，为使SGA达到比较好的优化效果，则需保证一定的群体规模和遗传代数，为此需运行SGA多次（一般在103次以上），计算量非常大，很难实用[34，63]。另一种方法就是试验法，从这些控制参数的若干组不同组合中选取相对最优的组合[63]。目前许多学者提出这些控制参数可随SGA的演化代数或个体的适应度函数值的不同而作自适应变化，以使SGA具有更好的鲁棒性、全局最优性和寻优效率[63，71]。笔者认为，SGA控制参数设置复杂、尚无简明统一的指导原则的主要原因在于，SGA中大的群体规模与少的计算量要求之间、高的变异概率与算法收敛性要求之间存在固有的矛盾。为此，可利用在SGA运行过程中搜索到的优秀个体子群体逐步缩小SGA的搜索空间来改进SGA。大量的应用结果表明，这一改进的SGA的控制参数设置极为简便[24]。2.3基于二进制编码的加速遗传算法[24,115]2.3.1算法的计算原理基于自然选择和自然基因机制的GA，利用简单的编码技术和遗传机制来模拟复杂的优化过程，以解决非常困难的问题。它只要求优化问题是可计算的，突破了对问题结构是否线性、连续、可微、单峰、无噪声等各种限制，同时也不受优化准则函数形式、优化变量数目等的束缚，对搜索空间没有特殊要求（如要求凸性、连通性），它直接在适应度函数值的引导下在搜索空间中进行自适应概率性全局搜索，运行过程简单而计算结果丰富，是目前一类新的优秀的通用性强的优化方法，已在诸如运输问题、行商问题、大规模0—1规划问题、多峰函数优化问题、多目标函数优化问题等[116]遗传计算问题、遗传编程问题和遗传学习问题中得到广泛应用[35]。在研制用于解决实际问题的GA时，必须考虑以下几个问题：①设置GA控制参数，这些参数包括编码长度、群体规模、选择概率、杂交概率、变异概率、收敛判据等，一般根据所要解决的问题适当确定。②编码与解码方式。应用GA时需把问题的解表示成数字串的形式（称为编码），这样GA的杂交、变异等遗传算子可直接对数字串进行操作。数字串一般为二进制串、十进制串等。在计算适应度函数值时又需将数字串译码成解变量。③初始群体的生成。一般采用随机方法，也可利用其它优化方法或领域经验、知识的计算结果来生成。④适应度函数的确定。该函数用于评价每个个体（数字串）所表示的解的优劣，该适应度函数值决定了该个体的生存概率。适应度函数一般为优化问题的目标函数的一种简单代数变换。⑤用于寻优的选择、杂交、变异等遗传算子的确定。在每次迭代中，GA先从当前群体中按适应度函数值选出一些数字串作为父代，适应度函数值越大的串被选中的机会越高。然后，用杂交、变异等算子对父代个体进行操作，产生下一代的父代个体。我们在应用SGA过程中发现，SGA对各种实际优化问题的搜索空间（优化变量空间）的大小变化的适应能力较差，计算量大，容易出现早熟收敛，SGA控制参数的设置技术目前尚无明确准则指导；而利用在SGA运行过程中搜索到的优秀个体逐步调整优化变量的搜索区间，可形成一种称之为加速遗传算法（acceleratinggeneticalgorithm-AGA）的新方法。经大量数值实验和实际应用，初步结果表明AGA对SGA在收敛速度和全局优化性能方面有明显的改进。下面是AGA的计算原理。不失一般性，设模型的参数优化问题为minf=(2.21)s.t.aj≤cj≤bj(j=1，2，…，p)式中，C={cj}为模型p个待优化参数(优化变量)；[aj，bj]为cj的初始变化区间(搜索区间)；X为模型N维输入向量；Y为模型M维输出向量；F为一般非线性模型，即F：RN→RM；｛(Xi，Yi)|i=1，2，…，m｝为模型输入、输出m对观测数据；‖‖为取范数；q为实常数，如当q为1时为最小一乘准则，为2时为最小二乘准则，等等，可视实际建模要求而定；f为优化准则函数。加速遗传算法包括如下8个步骤。步骤1：变量初始变化空间的离散和二进制编码。研究表明，采用二进制编码时，杂交操作的搜索能力比十进制编码时的搜索能力强，而且随着群体规模的扩大，这种差别就越明显，因此，这里决定采用二进制编码。设编码长度为e，把每个变量的初始变化区间[aj，bj]等分成2e–1个子区间，则(j=1，2，…，p)(2.22)式中，子区间长度dj=(bj–aj)/(2e–1)是常数，它决定了GA的解的精度；搜索步数Ij为小于2e的任意十进制非负整数，是变数。经过编码，变量的搜索空间离散成(2e)p个网格点。GA中称每个网格点为个体，它对应p个变量的一种可能取值状态，并用p个e位二进制数{ia(j，k)|j=1，2，…，p；k=1，2，…，e}表示：(j=1，2，…，p)(2.23)这样，通过式(2.22)、式(2.23)的编码，p个变量cj的取值状态、网格点、个体、p个二进制数{ia(j，k)}之间建立了一一对应的关系。可见，优化变量的变化区间及编码长度决定了模型参数实际搜索空间的大小。GA的直接操作对象是这些二进制数。步骤2：初始父代群体的随机生成。设群体规模大小为n。从上述(2e)p个网格点中均匀随机选取n个点作为初始父代群体。也即，生成n组［0，1］区间上的均匀随机数（以下简称随机数），每组有p个，即{u(j，i)|j=1，2，…，p；i=1，2，…，n}，这些随机数经下式转换得到相应的随机搜索步数INT(j=1，2，…，p；i=1，2，…，n)(2.24)式中，INT(·)为取整函数，显然有Ij(i)<2e。这些随机搜索步数{Ij(i)}由式(2.23)对应二进制数{ia(j，k，i)|j=1，2，…，p；k=1，2，…，e；i=1，2，…，n}，又由式(2.22)与n组优化变量{cj(i)|j=1，2，…，p；i=1，2，…，n}一一对应，并把它们作为初始父代个体。步骤3：二进制数的解码和父代个体适应度的评价。把父代个体编码串ia(j，k，i)经式(2.23)和式(2.22)解码成优化变量cj(i)，把后者代入式(2.21)得相应的优化准则函数值fi。fi值越小表示该个体的适应度值越高，反之亦然。把{fi|i=1，2，…，n}按从小到大排序，对应的变量{cj(i)}和二进制数{ia(j，k，i)}也跟着排序，为简便，这些记号仍沿用。称排序后最前面几个个体为优秀个体（superiorindividuals）。定义排序后的第i个父代个体的适应度函数值为(i=1，2，…，n)(2.25)式中，分母中“0.001”是经验设置的，以避免fi为0的情况；fi2是为了增强各个体适应度值的差异。步骤4：父代个体的概率选择。取比例选择方式，则个体i的选择概率为(i=1，2，…，n)(2.26)令，(i=1，2，…，n)，则序列{pi|i=1，2，…，n}把［0，1］区间分成n个子区间，并与n个父代个体一一对应。生成n个随机数{u(k)|k=1，2，…，n}。若u(k)∈(pi-1，pi]，则第i个个体被选中，其二进制数记为ia1(j，k，i)。同理可得另外的n个父代个体{ia2(j，k，i)}。这样从原父代群体中以概率选择第i个个体，共选择两组各n个个体。步骤5：父代个体的杂交。由于杂交概率pc控制杂交算子应用的频率，在每代新群体中，有npc对串进行杂交，pc越高，群体中串的更新就越快，GA搜索新区域的机会就越大，因此这里pc取定为1.0。目前普遍认为两点杂交方式优于单点杂交方式，因此这里决定采用两点杂交。由步骤4得到的两组父代个体随机两两配对，成为n对双亲。先生成2个随机数U1和U2，再转成十进制整数：IU1=INT(1+U1·e)，IU2=INT(1+U2·e)。设IU1≤IU2，否则交换其值。第i对双亲ia1(j，k，i)和ia2(j，k，i)的两点杂交，是指将它们的二进制数串中第IU1位至第IU2位的数字段相互交换，生成两个子代个体：(2.27)(2.28)(j=1，2，…，p；k=1，2，…，e；i=1，2，…，n)步骤6：子代个体的变异。这里采用两点变异，因为它与单点变异相比更有助于增强群体的多样性。生成4个随机数U1～U4。若U1≤0.5时子代取式(2.27)否则取式(2.28)，得到n个子代，记其二进制数为{ia(j，k，i)}。把U2,U3转化成不大于e的整数：INT(2.29)INT(2.30)变异率pm为子代个体发生变异的概率。子代个体ia(j，k，i)的两点变异，即如下变换(2.31)步骤6中：利用随机数U1以0.5的概率选取杂交后生成的两个子代个体的任一个，利用U2和U3来随机选取子代个体串中将发生变异的两个位置，利用U4来控制子代个体发生变异的可能性。步骤7：进化迭代。由步骤6得到的n个子代个体作为新的父代，算法转入步骤3，进入下一次进化过程，如此循环往复，优秀个体将逼近最优点。以上7个步骤构成标准遗传算法（SGA）。步骤8：加速循环。SGA的4个主要控制参数是编码长度e，父代个体数目n，变异率pm和进化迭代次数ni。目前对这些参数的设置尚缺少明确的准则指导；而且SGA的寻优效率明显依赖于优化变量的初始变化区间的大小，优化变量初始变化区间越大，SGA的有效性就越差，应用SGA就十分困难；SGA并不保证全局收敛性，见表2.2和表2.3。表2.2、表2.3中，s为优秀个体数目，为便于分析，优化问题取(2.32)虚拟一组理想无误差的输入、输出资料为(2.33)显然该问题的理论最优点（真值）为C*={1，2，3}。表2.2加速遗传算法与标准遗传算法优化效果的比较(一)SGA进化AGA加优秀个体各变量的变化区间最优化准迭代次数速次数c1c2c3则函数值2[0.892,1.192][1.980,2.186][2.991,2.999]8.201[0.807,1.192][1.861,2.186][2.987,3.012]3.554[0.893,1.198][1.979,2.188][2.990,2.999]4.952[0.810,1.181][1.935,2.502][2.997,3.003]0.436[0.897,1.198][1.985,1.986][2.999,3.000]4.953[0.841,1.170][1.967,2.020][2.999,3.001]0.8020[0.992,1.199][1.985,2.178][2.993,3.000]4.9510[0.974,1.010][1.998,2.003][2.999,3.000]0.0430[0.985,1.198][1.985,2.198][2.987,3.000]4.9515[0.998,1.001][1.999,2.000][2.999,3.00