第2章 进化计算

第2章进化计算

2.1进化计算导论进化是一个优化过程，目的是在不断变化的竞争环境中提高某生物（或系统）的生存能力。几个世纪以来，进化作为一个概念，曾被激烈地讨论过。直到今天，它仍是一个备受关注的话题。在不同的领域，进化可以有不同的解释。而本课程所关注的是生物中的进化概念。目前，生物进化仍是一个存在大量争论的概念，对于它的定义，Lamarckian和Darwinian的观点现已被广泛接受。Darwin（1809-1882）被认为是进化理论和共同起源法则的奠基人，而Lamarck（1744-1829）可能是把生物进化理论化的第一人。Jean-BaptisteLamarck的进化理论是关于遗传的，如获得性状的遗传。其主要观点是生物个体在生命期中逐渐适应环境，并将性状传给后代，后代也能不断适应。根据Lamarck的理论，适应的过程依赖于使用和丢弃这两个概念：在一段时间中，生物个体丢弃掉它所不需要的性状，表现出它需要的性状。CharlesDarwin的自然选择学说是生物进化的基础。Darwin的进化论可以描述为：在一个资源有限、种群稳定的世界中，每个生物个体都会与其他生物个体为了生存而竞争。拥有优良性状的个体会更加容易获得生存和繁殖的机会，它的性状也更易于传给后代。这些优良性状被下一代继承，经过一段时间便成为种群中的主要性状。Darwin理论的第二部分提到，在幼年生物体的发育过程中，随机事件会导致幼年生物体性状的随机改变。如果新出现的性状有益于生物体，则该生物获得生存的概率会有所提高。进化计算（EC）是指以进化过程作为计算模型的问题解决系统。如自然选择、适者生存、繁殖等都是这个问题解决系统的基本组成部分。Lamarck进化论一切物种都是其他物种演变和进化而来的，而生物的演变和进化是一个缓慢和连续的过程。环境的变化能够引起生物的变异，环境的变化迫使生物发生适应性的进化。有神经系统的动物发生变异的原因，除了环境变化和杂交外，更重要是通过用进废退和获得性状遗传。生物进化的方向从简单到复杂，从低到高。最原始的生物起源于自然发生。生物并不起源于共同祖先。拉马克曾以长颈鹿的进化为例，说明他的“用进废退”观点。长颈鹿的祖先颈部并不长，由于干旱等原因。在低处已找不到食物，迫使它伸长脖颈去吃高处的树叶，久而久之，它的颈部就变长了。一代又一代，遗传下去，它的脖子越来越长，终于进化为现在我们所见的长颈鹿。Darwin进化论包括两部分：遗传(基因)变异；自然选择生物不是静止的，而是进化的。物种不断变异，旧物种消灭，新物种产生。生物的进化是连续和逐渐，不会发生突变。生物之间存在一定的亲缘关系，他们具有共同的祖先。自然选择。生物过渡繁殖，但是它们的生存空间和食物有限，从而面临生存斗争，包括:种内、种间以及生物与环境的斗争。自然选择是达尔文进化论的核心。孟德尔学说1857年，身为神父，孟德尔通过对植物进行一系列仔细的实验。孟德尔发现植物的父母单独地把自身的性状传递给子。至关重要的是，他还发现性状不是单纯地混合在一起，而是保持着独立性：一株高的植物和一株矮的植物繁殖出来的后代要么是高的，要么是矮的，而不是介于两者之间。表明性状是分开独立地遗传给下一代，后来这称为遗传基因。让人惊奇的是，孟德尔的重要发现被人们忽略了数十年，直到20世纪初才被人们认可。

孟德尔学说1、分离定律：基因作为独特的独立单位而代代相传。细胞中有成对的基本遗传单位，在杂交的生殖细胞中，一个来自雄性亲本，一个来自雌性亲本.2、独立分配定律：在一对染色体上的基因对中的等位基因能够独立遗传。孟德尔的这两条遗传基本定律就是新遗传学的起点，孟德尔也因此被后人称为现代遗传学的奠基人。新达尔文主义将达尔文进化论和孟德尔-摩根基因相结合，成为现被广泛接受的新达尔文主义。新达尔文注意认为，只用种群上和物种内的少量统计过程就可以充分地解释大多数生命历史，这些过程就是繁殖、变异、竞争、选择。繁殖是所有生命的共同特性；变异保证了任何生命系统能在正熵世界中连续繁殖自己；对于限制在有限区域中的不断膨胀的种群来说，竞争和选择是不可避免的结论。生物学中的遗传概念在生物细胞中，控制并决定生物遗传特性的物质是脱氧核糖核酸，简称DNA。染色体是其载体。DNA是由四种碱基按一定规则排列组成的长链。四种碱基不同的排列决定了生物不同的表现性状。例如，改变DNA长链中的特定一段（称为基因），即可改变人体的身高。细胞在分裂时，DNA通过复制而转移到新产生的细胞中，新的细胞就继承了上一代细胞的基因。生物学中的遗传概念有性生殖生物在繁殖下一代时，两个同元染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉形成两个新的染色体。在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生新的染色体。这些新的染色体将决定新的个体（后代）的新的性状。生物学中的遗传概念在一个群体中，并不是所有的个体都能得到相同的繁殖机会，对生存环境适应度高的个体将获得更多的繁殖机会；对生存环境适应度较低的个体，其繁殖机会相对较少，即所谓自然选择。而生存下来的个体组成的群体，其品质不断得以改良，称为进化。生物的进化是经过无数次有利的进化积累而成的，不同的环境保留了不同的变异后代！

Time

Initialpopulation（初始种群）Select（选择）Crossover（交叉）AnotherCrossoverAmutation（变异）AnotherMutationOldpopulation+childrenNewPopulation:Generation2Generation3Generation4,etc…遗传算法的基本思想首先实现从性状到基因得映射，即编码工作，然后从代表问题可能潜在解集得一个种群开始进行进化求解。初代种群（编码集合）产生后，按照优胜劣汰的原则，根据个体适应度大小挑选（选择）个体，进行复制、交叉、变异，产生出代表新的解集的群体，再对其进行挑选以及一系列遗传操作，如此往复，逐代演化产生出越来越好的近似解。概念说明选择：通过适应度的计算，淘汰不合理的个体。类似于自然界的物竞天择.复制：编码的拷贝，类似于细胞分裂中染色体的复制。交叉：编码的交叉重组，类似于染色体的交叉重组。变异：编码按小概率扰动产生的变化，类似于基因的突变。这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中得最优个体经过解码（从基因到性状的映射），可以作为问题近似最优解。遗传算法历史1965年，Holland首次提出人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。1967年，Bagley在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博弈中的应用。1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。遗传算法历史1975年Holland出版了他的著名专著《自然系统和人工系统的适应性》该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法极为重要的模式理论，该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，DeJong完成了他的重要论文《遗传自适应系统的行为分析》。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑。遗传算法历史在一系列研究工作的基础上，上世纪80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。产生初始种群计算适应度是否满足优化准则最佳个体选择交叉变异解码（基因到性状）YN父代子代开始结束2.1.1一般进化算法借助于对随机选择的若干个体进行自然选择的进化过程，可以被看作是在染色体值空间中的一个搜索过程。在这个意义上，进化算法就是一种对给定问题求最优解的随机搜索方法。该进化搜索主要受到以下几个部分的影响。（1）编码：与染色体一样，对问题的解编码。（2）适应度函数：用于求适应度的函数，表征个体的生存能力。（3）初始化：种群的初始化。（4）选择：选择算子。（5）繁殖（reproduction）：繁殖算子。一个通用的进化算法：一般进化算法令代数计数器t=0;创建和初始化nx维的群体pop(0)，包含ns个个体；While终止条件不为真do

获得每个个体xi(t)的适应度值f(xi(t));

采用复制算法来产生后代;

选择新群体pop(t+1);

进入下一代，即t=t+1;end编码在进化计算中，每个个体都代表一个优化问题的备选解；个体的性状由染色体（也叫基因组）表示。而性状是指最优化问题所搜索的变量，每个需要优化的变量被称为基因——携带信息的最小单位。这些变量在可行域中的一组值叫等位基因。个体的性状可以被分为两类进化信息：基因型和表现型。基因型描述了个体的基因组成，它继承于父代。表现型是一个个体在特定环境里所表现出的行为特征，它定义了个体的样貌。

在设计进化算法中，一个重要的步骤是找到备选解的合适的表示方案（如染色体）。搜索算法的效率与复杂性很大程度上依赖于这个表示方案。不同典型方法中的不同进化算法往往使用不同的表示方案。多数进化算法把解表示为某种数据类型的向量，但遗传编程是个例外，它把个体表示为树的形式。以遗传算法为例进行说明解空间一个解的编码染色体编码其中的一个码和码所在的位置基因/基因位求下述二元函数的最大值：遗传算法的运算对象是表示个体的符号串，所以必须把变量x1,x2编码为一种符号串。本题中，用无符号二进制整数来表示。因x1,x2

为0~7之间的整数，所以分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可行解。例如，基因型X＝101110所对应的表现型是：x＝[5，6]。个体的表现型x和基因型X之间可通过编码和解码程序相互转换。初始种群进化算法是一种基于种群的随机搜索算法。因此，每个进化算法都会维护一个由备选解构成的种群。应用进化算法解决优化问题的第一步是产生一个初始种群。产生初始种群的标准方法是在可行域中产生随机值，并分配给每个染色体的每个基因。随机选择的目标是确保初始种群为整个搜索空间的均匀表示。如果初始种群没有覆盖搜索空间，则有可能使得未覆盖区域被搜索过程所忽略。初始种群的大小会影响计算复杂性和空间搜索能力。大量的个体能增加多样性，进而提高种群的空间搜索能力。然而，个体越多，每代的计算量越大。当每代的计算时间增加时，可能只需要较小的代数便能找到可以接受的解；另一方面，如果一个种群的个体数量较小，则只能探索空间中的较小部分。虽然每代的计算时间减少了，但进化算法需要更多的代数才能收敛得到一个与大种群相当的结果。X1=[011101]=[x1,x2]=[3,5]X2=[101011]=[x1,x2]=[5,3]X3=[011100]=[x1,x2]=[3,4]X4=[111001]=[x1,x2]=[7,1]遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始群体数据。本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机方法产生。适应度函数在达尔文式的进化模型里，拥有最好性状的个体获得生存和繁殖的机会更大。在进化算法中，为确定一个个体的生存能力，我们用一个数学函数来表征染色体所表示的解有多好。

所谓适应度函数f，将把一个染色体映射成一个标量值：f:Гnx→R

式中，Г代表nx维染色体元素的数据类型。适应度函数可以用目标函数来表示。本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度。注意：不同的优化问题要求适应度函数的形式不同。（1）在无约束优化问题中，适应度函数即为目标函数。（2）在带约束的优化问题中，进化算法的适应度函数要包含两个目标：一个原始的目标函数，另一个是约束惩罚函数。（3）在多目标优化问题（MOP）中，可以通过带权重的聚集方法解决，适应度函数为全部子目标的加权和。另一种解决方法为基于Pareto的优化算法。（4）在动态和噪声问题中，解的函数值随着时间而改变，动态适应度函数依赖于时间，而噪声函数往往会添加高斯噪声成分。

适应度函数的角色在进化算法中非常重要。进化算子，如选择、交叉、变异和精英选择，都会用适应度函数来评估染色体。例如，当选择父代个体用于交叉时，选择算子会更倾向最适应的个体，而变异算子会倾向最不适应的个体。选择选择是进化算法中的主要算子之一，与达尔文的适者生存的概念直接相关，选择算子的主要目标是获得更好的解。在每一代的结束，一个由备选解构成的新种群会被选择作为下一代种群。新种群可以仅从后代中选择，或是同时从后代与父代中选择。选择算子的目标是确保优良个体能存活到下一代。下面介绍两个最常用的选择算子：（1）随机选择随机选择是最简单的选择算子，它让每个个体都有1/ns的概率被选择（ns为种群中个体的总数）。不使用适应度信息，这就意味着最好的个体与最差的个体有相同的几率存活到下一代。

（2）比例选择使选择倾向于更具适应性的个体，可使用一个正比于适应度的概率分布用于个体选择：（2）比例选择使选择倾向于更具适应性的个体，可使用一个正比于适应度的概率分布用于个体选择：其中，为xi被选择的概率。

在本例中，采用比例选择算子来确定各个个体复制到下一代群体中的数量。具体操作过程如下：1）先计算出群体中所有个体的适应度的总和

；2）其次计算出每个个体的相对适应度的大小，它即为每个个体被遗传到下一代群体中的概率；3）每个概率值组成一个区域，全部概率值之和为1；4）最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。繁殖繁殖是从选择的父代中应用交叉和变异算子生成子代的过程。交叉是通过组合随机选择的两个或多个父代个体的基因物质生成新个体的过程。如果选择关注的是最具适应能力的个体，则选择压力可能会降低新种群的多样性而引起过早收敛。

本例采用单点交叉的的方法，其具体操作过程是：（1）先对群体进行随机配对；（2）其次随机设置交叉点位置；（3）最后再相互交换配对染色体之间的部分基因。变异是随机改变染色体基因值的过程。其主要目标是使种群引入新的基因物质，提高基因的多样性。应用变异的过程应该注意不要破坏高适应度个体的优良基因为此，变异通常以较低的概率进行。另一方面，变异概率也可与个体的适应度成反比：适应度越低的个体，变异越高。为了提高前期迭代的探索能力，变异概率可以初始为较大值，并随着时间逐渐减少直到最后一代。本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：（1）首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，其中的数字表示变异点设置在该基因处；（2）然后依照某一概率将变异点的原有基因值取反。对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。事实上，这里已经找到了最佳个体“111111”。

繁殖可以使用替换机制，即当且仅当新产生的子代个体的适应度优于它的父代个体时，才进行替换。终止条件在进化算法中，进化算子不断迭代执行，直到满足终止条件。最简单的终止条件是限制进化算法执行的代数或是调用适应度函数的次数。这个限制不能太小，否则进化算法不会有充足的时间去探索未知空间。除了限制执行时间，另一个用于确定种群是否收敛的标准也经常使用。收敛可以不严格地定义为种群变得稳定的时候，换句话说，就是在种群中没有基因或表现特征改变时。以下是常用的一些收敛准则。（1）当连续几代内都没有提高时则终止。如监视最优个体的适应度，如果在一个给定大小的时间窗内没有显著更新，则进化算法可以终止。相反，如果此条件不满足，则使用其它机制以增加多样性来获得更大的探索空间，如增加变异概率和变异次数。（2）当种群中没有改变时终止。在连续几代内，基因信息的平均改变量太小，则进化算法可以终止。（3）当得到一个可接受的解时终止。如果x*(t)表示目标函数的最优值，则当最优个体xi，满足，则一个可接受的解被找到。为收敛误差，如果过大，则找到的可接受解较差；如果过小，则在给定的时间限制下，进化算法很难终止。（4）当目标函数斜率接近0时终止。2.1.2进化计算与经典优化算法经典的优化算法已经在线性、二次型、强凸性、单模及其他某些特定问题方面取得了很大成功，而进化计算则对连续、不可微、多模和带噪问题更为有效。

进化计算与经典优化算法（ClassicalOptimization，CO）之间的不同主要在于搜索过程及搜索过程中使用的信息。（1）搜索过程：经典优化算法使用确定的规则从搜索空间中的一点移到另一点。进化计算则使用概率变换规则。同时，进化计算还对搜索空间进行并行搜索，而经典优化算法使用顺序搜索。一个进化算法从不同的初始点开始搜索，这样能并行搜索大量空间。经典优化算法只能从一个点，连续地向最优点调整移动。（2）搜索表面信息：经典优化算法使用搜索空间的偏导数信息（通常为一阶或二阶）来启发搜索路径。另一方面，进化计算不使用偏导数信息，它使用个体的适应度来指导搜索。2.2进化策略Rechenberg提出，既然生物过程已经由进化优化，并且进化本身就是一个生物过程，那么进化必然也能优化其本身。由Rechenberg在20世纪60年代首次提出，并由Schwefel进一步发展的进化策略（ES），就是基于“进化的进化”(theevolutionofevolution)。进化策略同时考虑基因型和显型，其重点在于个体的显型表现。每个个体由其基因建造块和一组对其所在环境个体表现建模的策略参数表示。进化包括基因型特征的进化和策略参数的进化，其中基因型特征的进化由策略参数控制。进化策略和其它进化计算范例另外的一个不同点是对于变异个体的接受仅发生在成功情况下。换句话说，变异个体只在变异结果的适应度增加的情况下才被接受。进化策略的另一个有趣的地方是子代可能由多于两个亲代产生。2.2.1一般进化策略算法第一个进化策略由于流体动力学问题的实验优化而被发明（I.Rechenberg.CyberneticSolutionPathofanExperimentalProblem.Technicalreport,MinisteryofAviation,1965）。这种早期的进化策略的种群中只包含一个个体，并且只使用变异操作。在每一代中，变异后的个体与其父代进行比较，并选择较好的一个，这种选择策略被称为（1+1）策略。进化策略中的个体用传统的十进制实型数表示，即：其中，Xt——第t代个体的数值，

N(0,σ)——服从正态分布的随机数，其均值为零，标准差为σ。

一个进化策略由如下几个主要部分组成：（1）初始化：对于每个个体，其基因型被初始化以满足问题边界约束。策略参数同样被初始化。（2）重组：子代由两个及两个以上的亲代通过交叉算子得到。（3）变异：子代进行变异，其变异步长由自适应策略参数决定。（4）评估：通过一个绝对适应度函数来决定个体基因型所表示的解的质量。（5）选择：选择算子在进化策略中用于两种目的。首先，选择亲代以重组；其次，决定何种子代可以生存以产生下一代。

一个实现进化策略的一般框架由如下算法给出。其中，参数μ和λ分别表示亲代和子代的个数。进化策略算法设定代计数器，t=0；初始化策略参数；产生并初始化具有μ个个体的种群pop(0)；for每个个体xi(t)∈pop(t)do

计算适应度f(xi(t))；endwhile终止条件不为真dofori=1,2,……,λdo

随机选择ρ≥2个亲代；

通过应用亲代基因型和策略参数上的交叉算子产生子代；

变异子代策略参数和基因型；计算子代适应度；end

选择新的种群pop(t+1);

进入下一代，即t=t+1;end进化策略的最初试验采用上述算法，主要采用单亲本—单子代的搜索，即“（1+1）进化策略((1+1)-ES)”，其中单个子代是由单个亲本产生的，它们都被置于生存竞争中，较弱的一个要被挑选出来消去。当把这种算法用于函数优化时，发现它有两个缺点：1）各维取定常的标准差使得程序收敛到最优解的速度很慢；2）点到点搜索的脆弱本质使得程序在局部极值附近容易受停滞的影响（虽然此算法表明可以渐近地收敛到全局最优点）。早期的(1十1)-ES，没有体现群体的作用，只是单个个体在进化，具有明显的局限性。随后，Rechenberg又提出(μ+1)-ES，在这种进化策略中，父代有μ个个体(μ＞1)，并且引入重组(Recombination)算子，使父代个体组合出新的个体。在执行重组时，从μ个父代个体中用随机的方法任选两个个体：然后从这两个个体中组合出如下新个体：式中qi＝1或2，它以相同的概率针对i＝1，2，…，n随机选取。对重组产生的新个体执行突变操作，突变方式及σ的调整与(1+1)-ES相同。将突变后的个体与父代μ个个体相比较，若优于父代最差个体，则代替后者成为下一代μ个个体新成员，否则，重新执行重组和突变产生另一新个体。(μ+1)-ES和(1+1)-ES具有相同的策略：只产生一个新个体。(μ+1)-ES的特点在于：

1）采用群体，其中包含μ个个体；

2）增添重组算子，它相当于遗传算法中的交叉算子，从父代继承信息构成新个体。显然，(μ+1)-ES比(1+1)-ES有了明显的改进，为进化策略这种新的进化算法奠定良好的基础。

下面介绍两个主要的进化策略算子，选择算子和交叉算子。

（1）选择算子

在一个进化策略中，选择有两个任务：（a）选择需要重组的亲代；（b）选择新的种群。进化策略的选择有两种：一种为(μ+λ)选择，另一种为(μ,λ)选择。(μ+λ)选择（也被称为加法策略）是从μ个父代个体及λ个子代新个体中确定性地择优选出μ个个体组成下一代新群体。(μ,λ)选择（也被称为逗号策略）是从λ个子代新个体中确定性地择优桃选μ个个体(要求λ＞μ)组成下一代群体，每个个体只存活一代，随即被新个体顶替。粗略地看，似乎(μ+λ)选择最好，它可以保证最优个体存活，使群体的进化过程呈单调上升趋势。但是，深入分析后发现(μ+λ)选择具有下述缺点：粗略地看，似乎(μ+λ)选择最好，它可以保证最优个体存活，使群体的进化过程呈单调上升趋势。但是，深入分析后发现(μ+λ)选择具有下述缺点：1）(μ+λ)选择保留旧个体，它有时会是过时的可行解，妨碍算法向最优方向发展。(μ，λ)选择全部舍弃旧个体，使算法始终从新的基础上全方位进化。2）(μ+λ)选择保留旧个体，有时是局部最优解，从而误导进化策略收敛于次优解而不是最优解。(μ，λ)选择舍弃旧的优良个体，容易进化至全局员优解。3）(μ+λ)选择在保留旧个体的同时，也将进化参数σ保留下来，不利于进化策略中的自适应调整机制。(μ，λ)选择则恰恰相反，可促进这种自适应调整。最佳选择策略的使用由需要解决的问题而定。高度回旋的搜索空间需要更好的搜索性，对此(μ,λ)-ES策略一般优于(μ+λ)-ES，前者已成为当前进化策略的主流。在(μ+λ)-ES中，为了控制群体的多样性和选择的力度，比值μ/λ是一个重要参数，它对算法的收敛速度有很大影响。一方面，μ不能太小，否则群体太单调(例如μ＝1的极端情况)；另一方面，μ也不能太大，否则计算工作量过大。通常，μ取15或更多一些。λ数值的大小，类似于μ的作用，也要适当。某些研究表明，比值μ/λ宜取1/7左右。也就是说，若μ=15，则λ宜取100。

（2）交叉算子(μ+1)-ES策略是第一个利用交叉算子的进化策略。在进化策略中，交叉被同时用于基因型（决策变量向量）和策略参数。交叉算子因用于产生单一子代的亲代个数及组合产生子代的亲代的基因型素材和策略参数不同而不同。一般来说，标记(μ/ρ,+λ)用于表示在交叉算子中使用了ρ个亲代。基于ρ的值，建立起如下两种方法：1）局部交叉（ρ=2），一个子代从两个随机选择的亲代产生。2）全局交叉（2<ρ≤μ），超过两个随机选择的亲代被用于产生子代。ρ的值越大，产生的子代的多样性也就越大。大ρ值的全局交叉提高了进化策略的探索性。

在局部和全局交叉中，重组方式有如下三种：1）离散重组：真正的亲代等位基因被用于构造子代。对于基因型和策略参数向量的每一个成分，相应随机选择的成分被使用。先随机选择两个父代个体：然后将其分量进行随机交换，构成子代新个体的各个分量，从而得出如下新个体：2）中值重组：这种重组方式也是先随机选择两个父代个体，然后将父代个体各分量的平均值作为子代新个体的分量，构成的新个体为：这时，新个体的各个分量兼容两个父代个体信息，而在离散重组中则只含有某一个父代个体的因子。3）混杂重组：这种重组方式的特点在于父代个体的选择上。混杂重组时先随机选择一个固定的父代个体，然后针对子代个体每个分量再从父代群体中随机选择第二个父代个体。也就是说，第二个父代个体是经常变化的。至于父代两个个体的组合方式，既可以采用离散方式，也可以来用中值方式，甚至可以把中值重组中的1/2改为[0,1]之间的任一权值。研究表明，进化策略采用重组后，明显增加算法的收敛速度。Schwefel建议，对于目标变量X宜用离散重组，对于策略因子σ及α宜用中值重组或混杂中值重组。2.2.2高级话题——约束处理方法现实世界中存在大量的优化问题，特别是在科学研究和工程实践领域，而这些问题往往都带有约束。由于问题自身的不同特点，运筹学中的传统方法已难以独立解决。进化算法作为一种基于群体搜索的智能优化方法，鲁棒性强且具有全局搜索能力，十分适合求解约束优化问题。因此，利用进化算法求解这些问题己越来越受到国内外研究者们的关注。

下面以单目标约束优化问题为例进行说明。定义1约束优化问题：不失一般性，以最小化为例，形式化描述如下：其中，f(x)为目标函数，。为n维的搜索空问，常数向量l和u表示其边界，定义为：F为可行区域，满足m个附加的线性或非线性约束(m≥0)：其中，q为不等式约束的数目，m-q为等式约束的数目。对于一个不等式约束在可行区域F的某一点x处满足，则称该约束在点x处是活跃的。因此，所有等式约束在可行解区域F内都是活跃的。一般而言，约束优化问题是难以处理的，特别当目标函数和约束都是任意形式时。这也是运筹学中对约束优化问题进行分类研究的原因。当所有约束都是线性时，问题被称为线性约束优化问题；而此时若目标函数为多项式且次数不超过2，则被称为二次规划问题。在二次规划问题中，最有名的是线性规划问题，即目标函数也是线性的。对于这些特殊类别的约束优化问题，运筹学中已有成熟的方法进行求解；而不属于这些类别的问题则往往难以求解。求解约束优化问题的另一个难点在于局部最优解。因为局部最优解能够满足函数求导上的数学性质，则基于梯度方法的优化技术让往只能找到一个局部最优解。对于约束优化问题，建立一个确定性的全局优化方法(优于穷举搜索)是不可能的。进化算法是一种智能的全局优化方法，可以求解不同类型的问题(如问题不连续或不可微)，因此利用进化算法进行约束优化也越来越受到关注。其中，最为关键的问题就是如何进行有效的约束处理，即如何有效均衡在可行区域与不可行区域的搜索。进化算法中的约束处理是将搜索偏向于可行区域，但为避免算法陷入局部最优，也需要考虑不可行区域的搜索。目前，进化算法中的约束处理方法可分类如下：（1）

传统的惩罚函数法该方法最初由Courant于20世纪40年代提出，随后由Carroll、Fiacco和McCormick进行了扩展。该方法的基本思想是：通过对不可行解的目标函数值加上（或减去）一个约束违反程度值，即对不可行解进行惩罚，将约束优化问题转换为不带约束的优化问题。一般而言，惩罚函数法具有两种方式：外部方式和内部方式。在外部方式中，搜索从不可行区域向可行区域移动。而在内部方式中，惩罚项的大小和解与约束边界的距离成反比关系，即当解接近约束边界时，惩罚项将趋于无穷大。内部方式最大的不足是初始群体中要有一个可行解，而对某些问题而言，找到可行解就是一个NP-hard问题。此外，目前惩罚函数法的研究也以外部方式为主。外部惩罚函数的一般形式可表示为：其中，ri和cj是惩罚系数，为正常数，Gi(x)和Hj(x)分别是不等式约束gi(x)和等式约束hj(x)的函数，一般定义为：其中，β和γ一般取值1或2。在求解约束优化问题时，也常将等式约束转换为不等式约束，即其中δ为事先设定的一个很小的正常数。理论上而言，惩罚系数应尽可能的小，使得不可行解刚好不是最优的，这被称为最小惩罚准则(mimimumpenaltyrule)。因为惩罚过大或过小，都不利于进化算法找到可行的最优解；若惩罚过大，算法虽能快速收敛到可行区域，但当问题在搜索空间上具有多个不连续的可行区域时，算法往往只能找到其一，则很可能找到一个可行的局部最优解；若惩罚过小，算法则不能有效地在可行区域中进行搜索，大部分搜索被浪费在不可行区域上，特别的，当问题的可行区域十分小时，算法有可能找不到可行解。因此，设置合适的惩罚系数成为进化算法能否找到最优可行解的关键，也成为惩罚函数法能否有效求解约束优化问题的关键，但惩罚系数往往与问题相关，难以设置。外部方式的惩罚函数可分类如下：静态惩罚、动态惩罚、退火惩罚、反馈惩罚、隔离惩罚和死亡惩罚等。（2）采用特殊的编码和算子在求解一些（特别困难的）问题时，常用的编码方式往往不再有效，即在此编码下的搜索空间十分复杂。因此，对于这些问题，采用特殊的编码方式来简化搜索空间，同时采用特殊的算子来保持解的可行性，将十分有效。Davis在其著作中利用该方法求解了一系列实际问题，Michalewicz在开发的GENOCOP（GeneticalgorithmforNumericalOptimizationforConstrainedProblems）系统中也采用了该方法。特别的，对于那些连可行解都难以找到的问题，该方法的优势将更为明显。总之，该方法最大的优势在于能快速找到可行解，因为采用了特殊的编码和算子；但也因此，该方法的求解范围受到了限制，只能用于求解某一类的约束优化问题。（3）修复方法对于很多组合优化问题而言，如旅行商问题(TravelingSalesmanProblem)、背包问题(KnapsackProblem)等，将不可行解修复为可行解往往十分简单。修复得到的可行解，可仅用于适应度的评估，也可以一定概率替换群体中原来的不可行解。Liepins及其同事在多种组合优化问题上进行了实验对比，结果表明采用修复方法的进化算法在性能上具有明显的优势。对于修复方法而言，关键问题是如何设计修复策略，即将不可行解有效地转换为可行解的方法。然而，目前并没有标准的设计方法，但可以采用贪心方法和随机方法等。修复方法的另一个问题就是修复后的可行解以多大的概率去替换原来的不可行解。从实验结果上来看，对组合优化问题，Orvosh和Davis指出当替换概率为5％时，算法的性能达到最优；对非线性约束的数值优化问题，MichaIewicz指出15％的替换概率是最佳的选择。但是，这些都只是经验值，并没有充分的理论依据。综上，当修复代价较低且不会引起太大的搜索偏向时，修复方法是一个很好的选择。然而，该方法与问题相关，即每个问题都需要特定的修复方法。（4）分离目标和约束的方法该方法是对目标函数和约束违反程度分别处理，避开了传统惩罚函数法中惩罚系数难以选择的问题。但从本质上而言，该方法是一种不需要惩罚系数的惩罚函数法，可以说是对传统惩罚函数法的扩展，也是目前进化约束优化研究中的热点。约束违反程度一般定义为：其中，表示示第i个约束的违反程度，具体定义如下：其中δ为事先设定的一个很小的正常数。分离目标和约束的方法避开了惩罚系数难以选择的困难，是一种更为有效且通用的约束处理机制，但并没有从本质上解决如何有效地均衡可行区域与不可行区域搜索的问题。（5）混合方法该类方法是在进化算法中采用另一种优化技术（常为数值优化方法）来进行约束处理。其中，主要的优化技术有：拉格朗日方法、数学规划方法、模糊逻辑方法等。这些技术为进化约束优化提供了新的解决思路，但往往也将这些方法的不足带到了混合算法中。在以上的五类方法中，惩罚函数法（包括分离目标和约束的方法）由于简单、有效，是目前进化约束优化研究中最为常用的约束处理方法。综上所述，如何有效均衡可行区域和不可行区域的搜索始终是进化约束优化中最为核心的问题。目前的研究工作虽取得了一定的进展，但对于等式约束很多或变量很多的约束优化问题而言，目前的约束处理方法仍难以进行有效搜索，值得我们进一步研究。2.2.3高级话题——多目标优化现实世界中的很多优化问题都具有多个相互冲突的目标。例如投资问题，一般希望投入资金最少、风险最低且收益最大。若没有先验知识，单目标优化中的方法已难以有效地求解这类问题。多目标优化问题(MultiobjectiveOptimizationProblem，简称MOP)的定义如下：定义1多目标优化问题：不失一般性，以最小化问题为例，形式化描述为：其中，表示n维决策空间x中的一个决策向量，与分别表示决策空间第i维的下界与上界，为第k个目标函数。在多目标优化问题中，由于目标之前往往存在冲突，则所有目标不可能同时达到最优，因此多目标优化问题的最优解通常是一个集合。为描述这样的集合，我们先给出Pareto支配的概念。

定义2Pareto支配：对于决策空间X中的任意两个决策向量a和b，a支配b即

当当且仅当(以最小化为例进行讨论)即向量a的目标值都不大于向量b的目标值，且至少存在一个目标，向量a对应的目标值严格小于向量b对应的目标值。定义3Pareto最优解：对决策空间X中的任一向量a，a为Pareto最优，当且仅当即决策空间X中不存在Pareto支配向量a的决策向量。定义4Pareto最优解集(ParetooptimaISet，简称POS)：由决策空间x中的所有Pareto最优解构成，设该集合为P，具体定义如下：并定义该集合对应的目标向量集合为Pareto最优前沿(ParetooptimalFront，简称为POF)。从上述定义中可以看到，多目标优化的目标不是找到单个解，而是获得一个解集，并能满足如下两个要求：（1）逼近性：解集在目标空间中与Pareto最优前沿的距离尽可能小；（2）分布性：解集在目标空间的分布性尽可能的好，即其分布可以表示或近似表示Pareto最优前沿的分布。因此，多目标优化与单目标优化的主要区别体现在：

（1）优化目标的区别：多目标优化需要同时满足逼近性和分布性；单目标优化只要满足逼近性即可；

（2）搜索空间的区别：多目标优化不仅需要考虑决策空间，还需要考虑目标空间；单目标优化只需考虑决策空间；（3）人工限制的区别：现实世界中的优化问题往往都具有多个目标，以前的研究者通过人工限制方式将其转换为单目标优化问题，而多目标优化则可以不需要人工限制的介入。按照使用问题先验知识的程度，多目标优化传统方法可分为如下四类：（1）不使用先验知识的方法，即搜索前后都不使用先验知识；（2）搜索后使用先验知识的方法，即找到最优解集后再按先验知识选择；（3）搜索前使用先验知识的方法，即按先验知识搜索最优解集；（4）交互方法，即搜索过程中使用先验知识。目前，代表性的传统方法主要有：（1）加权求和方法通过对目标加权求和，将多目标优化问题转换为单目标优化问题：其中，加权系数λi≥0，且满足。该方法是求解多目标优化问题最简单的方法，且对于Pareto最优前沿为凸的问题，理论上而言，该方法可保证找到Pareto最优解集中的任何一个解。但当决策空间与目标空间的映射关系是非线性时，一组均匀分布的加权系数并不能找到一组均匀分布的解集；另外，使用不同的加权系数并不能保证找到不同的Pareto最优解。而该方法最大的缺陷在于不能找到Pareto最优前沿为凹的解。（2）ε-约束方法Haimes等人于1971年提出将某个目标函数作为优化目标，而约束其它目标函数的方法来求解多目标优化问题，具体方式如下：其中εi

表示约束参数，fk(x)为优化目标。通过设置不同的εi，该方法就可以找到多个不同的Pareto最优解，且对优化问题Pareto最优前沿的凸凹性不敏感。但是，设置合适的εi值，往往需要先验知识，特别是当优化问题的目标数增多时。（3）Benson方法该方法于1978年由Benson提出，具体方式如下：其中，z为目标空间上的向量。该方法的目标就是最大化向量f(x)与向量z构成的超立方体的周长，因此该问题的最优解是一个Pareto最优解。通过设定不同的向量z，就可以获得不同的Pareto最优解；且设置合适的向量z，还可以找到非凸区域上的Pareto最优解。但当目标函数是不可微时，基于梯度的方法往往很难求解。（4）目标规划方法目标规划方法最初是由Charnes等人于1955年在求解单目标线性规划问题时提出的，并在lgnizio和Lee等人的工作之后受到关注。Romero于1991年对该方法进行了深入的总结。该方法的主要思想如下：对目标函数设置预定目标，即目标函数的期望值，并找到能达到或最接近期望值的解。该方式的主要方式有：加权的目标规划方法、字典序的目标规划方法和最小最大的目标规划方法。

该方法的主要特点是求解效率较高，但需要先验知识。

可以看到，传统方法在求解多目标优化问题时往往存在困难（特别是期望获得多个Pareto最优解时），主要体现在：（1）传统方法在一次运行中只能获得一个Pareto最优解，因为传统方法都是将多目标优化问题转化为单目标优化问题进行求解；（2）当Pareto前沿为凹时，一些传统方法不能确保找到所有的Pareto最优解；（3）几乎所有的传统方法都需要一定的先验知识。而传统方法最大的优势是在理论上可以收敛到Pareto最优解集。

相对于上述传统方法，进化算法作为一种群体搜索算法，十分适合求解多目标优化问题。主要因为：（1）进化算法在一次运行中可以获得多个Pareto最优解；（2）进化算法对问题自身的要求低，可以用于不同类型问题。(如不可微、不连续的问题)的求解。2.3差分进化

差分进化（DE）是一个由Storn和Price在1995年提出的社会性的、基于种群的搜索策略。和其它进化算法（EA）一样，DE是一种模拟生物进化的随机模型，通过反复迭代，使得那些适应环境的个体被保存了下来。但相比于进化算法，DE保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性。同时，DE特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题。2.3.1基本的差分进化DE算法主要用于求解连续变量的全局优化问题，其主要工作步骤与其他进化算法基本一致，主要包括变异(Mutation)、交叉(Crossover)、选择(Selection)三种操作。

算法的基本思想是从某一随机产生的初始群体开始，利用从种群中随机选取的两个个体的差向量作为第三个个体的随机变化源，将差向量加权后按照一定的规则与第三个个体求和而产生变异个体，该操作称为变异。然后，变异个体与某个预先决定的目标个体进行参数混合，生成试验个体，这一过程称之为交叉。如果试验个体的适应度值优于目标个体的适应度值，则在下一代中试验个体取代目标个体，否则目标个体仍保存下来，该操作称为选择。在每一代的进化过程中，每一个体矢量作为目标个体一次，算法通过不断地迭代计算，保留优良个体，淘汰劣质个体，引导搜索过程向全局最优解逼近。设f是最小化适应度函数，适应度函数以实数向量的形式取一个候选方案作为参数，给出一个实数数值作为候选方案的输出适应值。其目的是在搜索空间的所有方案

p中找到

m使得

f(m)≤f(p)。最大化是找到一个

m使得

f(m)≥f(p)。

设

X=(x1,x2,…,xn)∈ℝn是种群中一个个体，基本的差分进化算法如下所述：

（1）在搜索空间中随机地初始化所有的个体。

（2）重复如下操作直到满足终止条件（最大迭代数或者找到满足适应值的个体）。（3）随机地从种群中选择三个彼此不同的个体

a，b和

c。

（4）选择一个随机索引

R∈{1,...,n}，n是被优化问题的维数。

（5）通过对每个

i∈{1,...,n}进行如下的迭代，计算可能的新个体Y=[y1,...,yn]生成一个随机数

ri~U(0,1)；

1）如果(i=R)或者(ri<CR)，

yi=ai+F(bi−ci)，否则

yi=xi；

2）如果(f(yi)<f(xi))，则在种群中使用改进的新生成的

yi替换原来的

xi，否则不变。

（6）选择具有最小适应度值的

xi作为搜索的结果。其中：F∈[0,2]为缩放因子，CR∈[0,1]为交叉因子，种群大小NP>3。

基本差分进化算法的一般框架由如下算法给出。差分进化算法设定代计数器，t=0；初始化控制参数β和pr；产生并初始化具有ns个个体的种群pop(0)；while终止条件不为真dofor每个个体xi(t)∈pop(t)do

计算适应度f(xi(t))；通过应用变异算子产生测试向量ui(t)；通过应用交叉算子产生子代x’i(t)；iff(x’i(t))优于f(xi(t))then

将x’i(t)加入pop(t+1);endelse将xi(t)加入pop(t+1);endendend将最佳适应度的个体作为解返回。2.3.1.1差异向量

个体的位置提供了关于适应度场景的有价值的信息。一个好的均匀随机初始化算法被用于构建初始种群。之间距离很大的初始个体将提供一个关于整个搜索空间的良好表示。之后，随着搜索进度，个体之间的距离变小，所有的个体收敛到一个相同的解。记住个体之间的初始距离尺度受种群的大小影响。种群中个体数量越多，则距离尺度越小。

个体间的距离是当前种群多样性的一个很好的指标，为了使种群联系到一点，步长的尺度应当被排序。如果存在之间距离很远的个体，个体应该采用更大的步长以探索尽可能多的搜索空间。另一方面，如果个体之间的距离很近，应当采用小步长来探索局部空间。该行为是由差分进化通过计算变异步长作为随机选择的个体之间的加权差异而获得的。因此变异的第一步是首先计算一个或多个差异向量，之后使用这些差异向量来判断步长的尺度和方向。

使用向量差分以存档变量有一些优点：（1）首先，以当前种群表示的关于适应度场景的信息用于指导搜索方向。（2）其次，由于中心极限定理（中心极限定理指出当随机变量的采样数量趋于无穷时，其随机变量的分布服从高斯分布），变异步长呈高斯分布，使得种群显著增大以允许足够数量的差异向量。差异向量形成的分布的均值总是零，提供从种群中均匀选择的用于计算差异向量的个体。在个体被均匀选择的情况下，差异向量(xi1-xi2)和(xi2-xi1)以相同的概率出现，这里xi1和xi2是两个随机选择的个体。结果步长的零均值保证了种群不会由于遗传漂变而受到伤害。同样应当注意到分布的偏移由差异向量的尺度决定。（3）最后，区分变得极微小，导致了非常小的变异。2.3.1.2变异算子

在一些进化算法中，变异步长以相同的概率分布函数被抽样，差分进化与这些进化算法不同在于：（1）变异首先被用于产生一个测试向量，之后用于在交叉算子中产生一个子代。（2）变异步长不以之前我们知道的概率分布函数被抽样。

在差分进化中，变异步长受当前种群的个体间差异影响。差分进化变异算子通过变异加权差分的目标向量对于当前种群的每个个体产生一个微小的向量。然后，这个微小的向量通过交叉算子产生子代。对于每个亲代xi(t)以如下方式产生一个微小的向量ui(t)：从种群中选择一个目标向量xi1(t)，使得i≠i1。然后，从种群中随机选择两个种群xi2(t)和xi3(t)，使得i≠i1≠i2≠i3且i2，i3~U(1,ns)。使用这些个体，测试向量以如下的方式扰动目标向量而形成：ui(t)=xi1(t)+β(xi2(t)+xi3(t))。

式中β∈(0,∞)为标量因子，控制差分变量的放大。在差分进化计算中，每个基因位的改变值取决于其他个体之间的差值，充分利用了群体中其他个体的信息，达到了扩充种群多样性的同时，也避免了单纯在个体内部进行变异操作所带来的随机性和盲目性。在随机向量差分法中每个个体的变异取决于两个随机个体的向量差：采用最优解加随机向量差分法，每个个体由当前最优解决定，分布在当前最优解的邻域范围内，利用了当前最优种群最优个体的信息，加速了搜索速度，但同时如果种群分布密度高，可能会导致算法陷入局部最优解；采用最优解与随机向量差分法，用个体局部信息和群体全局信息指导算法进一步搜索的能力，较最优解加随机向量法降低了陷入局部最优解的危险。当向量偏差大时，导致个体的变异强度高；反之，个体的变异强度低。差分进化计算与种群的分布密度相关，因此如果种群分布密度高，则个体的变异强度较低。2.3.1.3交叉算子

差分进化算子实现了测试向量ui(t)和亲代向量xi(t)的离散重组以产生子代x’i(t)。使用如下方法实现交叉：式中xij(t)表示向量xi(t)的第j个元素，其J是将承受扰动（或交叉位的集合）的元素下标的集合。可以使用不同的方法以判断集合J，以下两种方法较为常用：（1）二项式交叉。交叉位从可能的交叉位集合{1,2,….,n}中随机选出，n是问题维度。在基本差分进化算法中（本PPT第74页），pr是考虑包含交叉位的概率。pr越大，选择交叉位也就越多。这意味着细微向量的更多元素可以被用于产生子代以及更少的亲代向量。因为使用了一个概略决策来包含一个交叉位，其可能出现没有点被选择的情况，在这种情况下，子代就是其亲代xi(t)。这个问题对于低维搜索空间更加明显。为了确保至少有子代的一个元素不同于亲代，交叉位集合ζ初始化为包含一个随机选择的点j*。

对于选择交叉位的差分进化二项式交叉j*~U(1,n)；ζ←ζU{j*}；for每个j∈{1,…,n}doifU(0,1)<pr且j≠j*then

ζ←ζU{j}；endend（2）指数交叉。从一个随机选择的索引，指数交叉算子选择一个邻接点的序列，将这个潜在的交叉位处理为一个环。下面的伪代码表明至少有一个交叉位被选择，并且形成索引，选择下一个直到U(0,1)≥pr，或|ζ|=n。

在差分进化计算中，进行交叉操作的主体是父代个体和由它经过差分变异操作后得到的新个体，虽然这种方法看似没有进行个体之间的信息交互，但由于新个体经过差分变异而来，本身保存有种群中其他个体的信息，因此差分进化的交叉算子同样具有个体之间信息交互的机制。对于选择交叉位的差分进化指数交叉ζ←{}；j~U(1,n-1)；repeat

ζ←ζU{j+1}；j=j+1modn；untilU(0,1)≥pr或|ζ|=n2.3.1.4选择算子

选择用于决定哪个个体将在编译算子中发挥作用以产生测试向量，并且决定哪个亲代或者子代将存活至下一代。结合交叉算子的情况，将使用若干选择方法。使用随机选择从差异向量已被计算的个体中选出个体。对于大多数差分进化实现，要么随机选择目标向量，要么选择最优个体。

为了构建下一代的种群，使用判断选择：如果子代的适应度如果优于其亲代，则子代替换其亲代；否则，亲代存活至下一代。这确保了种群的平均适应度不致恶化。2.3.1.5控制参数

除了种群步长ns，差分进化的性能由两个控制参数控制，规模因子β和重组概率pr（见本PPT第74页基本算法）。这些参数的作用如下：（1）种群大小。种群大小对于差分进化算法的探索性有着直接的影响。种群中个体数量越多，可用的差异向量就越多，则更多的方向可以被探索。然而，应当记住每代计算复杂度随种群大小增加而增加。经验告诉我们ns≈n。然而编译算子的本性提供了个体数量的下界为ns>2nv+1，式中nv是使用的差异的个数。对于nv个差异，需要2nv个个体，对于每个差异有2个。附加的个体表示目标向量。

（2）规模因子。规模因子β∈(0,∞)控制差异变量（xi2-xi3）的增大。β值越小，变异步长越小，且算法收敛时间越长。β值较大有利于增加探索性，但可能导致算法超过好的最优值。β值应当足够小以允许差异探索紧凑的空间，并且足够大以维持多样性。当种群数量增加时，规模因子应当减少。种群中个体越多，差异向量的尺度越小，比较靠近的个体将变成同一个个体。因此，较小的步长用于开采局部区域。经验结果建议使用较大的ns和β经常导致早熟，并且β=0.5通常提供了足够好的性能。（3）重组概率。重组的概率pr对于差分进化的多样性有着直接的影响。这个参数控制亲代xi(t)的元素个数。重组的概率越高，在新一代中就引入了越多的变种，由此增加了多样性和探索性。增加pr通常导致更快的收敛，同时减少pr增加了搜索的鲁棒性。

差分进化策略的大多数实现将控制参数作为一个常数。尽管实验表明差分进化收敛于这些参数的不同值有着密切的关系，但是性能（例如精度、鲁棒性和速度）可以通过对于每个新问题寻找控制参数的最佳值而得以提高。2.3.2基本差分进化的变种

2.3.2.1混合差分进化策略

基本的差分进化非常高效和鲁棒，原始差分进化策略的一些自适应方法被发展出来以进一步的提高性能。基本进化策略已经与其它的进化算法，比如梯度下降法、粒子群算法、人工神经网络、模拟退火算法等相结合。下面主要介绍基于梯度的混合差分进化。

最早的混合差分进化之一由Chiou和 Wang发展出来，被称为混合差分进化。混合差分进化引入了两种新的算子：为了提高收敛性能的加速算子（不以牺牲多样性为代价）和提供差分进化挣脱局部极值能力的迁移算子。

如果变异和交叉算子未能提升最佳个体的适应度，则加速算子使用梯度下降法以调整最佳个体的朝向以获得更佳的位置。令表示当前种群pop(t)在应用变异和交叉算子前的最优个体，令为经过应用于变异和交叉于所有的个体的下一代种群中的最佳个体。则假设一个最小化问题，加速算子计算如下向量：式中是学习率或步长；是目标函数f的梯度。新的向量x(t)替换新的种群pop(t)中最差的个体。

讲学习率初始化为1，例如。如果梯度下降未能产生一个具有更好适应度的新向量x(t)，学习率以一个因子削减。梯度下降不断重复直到足够趋近于0，或者已经达到梯度下降步的最大次数。

结合加速和迁移的混合差分进化设定代计数器，t=0；初始化控制参数β和pr；产生并初始化具有ns个个体的种群pop(0)；while终止条件不为真do

当需要时应用迁移算子；for每个个体xi(t)∈pop(t)do

计算适应度f(xi(t))；通过应用变异算子产生测试向量ui(t)；通过应用交叉算子产生一个子代x’i(t)；iff(x’i(t))优于f(xi(t))then

将x’i(t)加入pop(t+1);endelse将xi(t)加入pop(t+1);endend

当需要时应用加速算子；end将最佳适应度的个体作为结果返回。

使用梯度下降可以显著的加速搜索，但其也存在着会陷入局部极值的缺陷。迁移算子通过增加种群多样性以解决这个问题。这是通过将最佳个体繁殖出多个新个体，并将这些个体替代当前种群而做到的。个体按如下方式繁殖：

式中。繁殖出的个体称为。

迁移算子仅当当前种群多样性变得太小时使用，这就是说，当：式中：式中ε1和ε2分别表示考虑最佳个体种群多样性和基因型多样性的忍耐性。如，那么个体i的第j个元素的值就接近于最佳个体的第j个元素的值。

2.3.2.2基于种群的差分进化

为了提高差分进化的探索能力，有学者提出使用两个种群集。第二个种群被称为备用种群popa(t)，作为那些被差分进化选择算子拒绝的亲代的存档。在初始化过程中，随机选择出ns对向量。两个向量中间最佳的那个作为一个个体被插入到种群pop(0)中，另一个向量xia(0)被插入备份种群popa(0)之中。在每一代中，对于每个被产生的子代，如果子代的适应度不优于亲代，与抛弃子代x’i(0)不同，其考虑在备份种群中包括子代。如果f(x’i(t))优于xia(t)，那么x’i(t)替换xia(t)。备份集合周期性的被用于替换pop(t)中最差个体为popa(t)中的最佳个体。2.3.3高级话题——约束控制方法使用如下的方法以应用差分进化以解决第2.2.2节中所定义的约束优化问题。（1）罚方法。通过增加一个函数以惩罚与约束冲突的解来调整目标函数。（2）通过在一个扩展拉格朗日中嵌入约束将约束问题转化为一个非约束问题。（3）为了保持初始解的可行性，采用一些方法决定步长和搜索方向。（4）通过改变差分进化的选择算子，可以拒绝非可行解，并且促进非可行解的修理。为了达到此目的，选择算子接受一个满足如下条件的子代x’i：a)如果x’i满足所有的约束且f(x’i)≤f(xi)，那么x’i替换其亲代xi（假设是一个最小化问题）。b)如果x’i是可行的且xi是不可行的，那么x’i替换xi。c)如果x’i和xi都是不可行的，那么如果x’i违反的约束的数量小于等于xi违反的约束的数量，那么x’i替换xi。

在亲代和子代都表示可行解的情况下，没有朝向更好适应度场景的选择压力；在一定程度上，朝向最小违反约束数量的解。2.3.4高级话题——多目标优化多目标优化需要同时优化多个冲突的目标。多目标差分进化方法包括：

（1）将问题转化为一个最大最小问题。（2）权聚合方法。（3）基于种群的方法。如果K个目标需要优化，则使用K个子种群，这里每个种群优化一个目标。这些子种群组织成一个环拓扑。在每次迭代中，在差分进化繁殖算子的应用之前，种群popk中的最佳个体popk•迁移至种群popk+1，其被用于种群popk+1以产生对这个种群的测试向量。

（4）基于Pareto的方法，其改变差分进化算子以包括支配概念。

变异：有学者提出仅在当前种群中非支配解上应用变异，计算差异为随机选择的个体xi1和随机选择的支配xi1的向量xi2之间的差异；这就是说，xi1

xi2，如果xi1不由当前种群的任何其它个体支配，差异设定为0。

选择：一个对于选择算子的简单变化是当且仅当xi’

xi以子代xi’替换亲代xi。一个替换的方法是，可以使用非支配排序基因算法的办法，这里非支配排序和定级被用于亲代和子代。之后下一代种群优先选择具有较高排序的那些个体。2.4协同进化

协同进化（CoE）是密切相关的物种的互补进化。两个物种的协同进