进化算法

进化算法，或称“演化算法”(evolutionaryalgorithms,EAS)是一个“算法簇”，尽管它有很多的变化，有不同的遗传基因表达方式，不同的交叉和变异算子，特殊算子的引用，以及不同的再生和选择方法，但它们产生的灵感都来自于大自然的生物进化。与传统的基于微积分的方法和穷举法等优化算法相比，进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法，具有自组织、自适应、自学习的特性，能够不受问题性质的限制，有效地处理传统优化算法难以解决的复杂问题。

中文名：进化算法

外文名：evolutionaryalgorithms

别名：演化算法

简称：EAs

1、起源发展

进化计算包括遗传算法(GeneticAlgorithms)、遗传规划（GeneticProgramming）、进化策略(EvolutionStrategies)和进化规划(EvolutionProgramming)4种典型方法。第一类方法比较成熟，现已广泛应用，进化策略和进化规划在科研和实际问题中的应用也越来越广泛。

遗传算法的主要基因操作是选种、交配和突变，而在进化规则、进化策略中，进化机制源于选种和突变。就适应度的角度来说遗传算法用于选择优秀的父代(优秀的父代产生优秀的子代)，而进化规则和进化策略则用于选择子代(优秀的子代才能存在)。遗传算法与遗传规划强调的是父代对子代的遗传链，而进化规则和进化策略则着重于子代本身的行为特性，即行为链。进化规则和进化策略一般都不采用编码，省去了运作过程中的编码—解码手续更适用于连续优化问题，但因此也不能进行非数值优化。进化策略可以确定机制产生出用于繁殖的父代，而遗传算法和进化规则强调对个体适应度和概率的依赖。

此外，进化规则把编码结构抽象为种群之间的相似，而进化策略抽象为个体之间的相似。进化策略和进化规则已应用于连续函数优化、模式识别、机器学习、神经网络训练、系统辨识和智能控制的众多领域。

从本世纪40年代起，生物模拟就构成了计算科学的一个组成部分，象早期的自动机理论，就是假设机器是由类似于神经元的基本元素组成的，它向人们展示了第一个自复制机模型。这些年来诸如机器能否思维、基于规则的专家系统是否能胜任人类的工作，以及神经网络可否使机器具有看和听的功能等有关生物类比的问题已成为人工智能关注的焦点。最近生物计算在机器昆虫和种群动态系统模拟上所取得的成功激励越来越多的人们致力于人工生命领域的研究。当今计算机科学家和分子生物学家已开始携手进行合作研究，并且类比也得到了更为广泛的应用。

自然界生物体通过自身的演化就能使问题得到完美的解决。这种能力让最好的计算机程序也相形见拙。计算机科学家为了某个算法可能要耗费数月甚至几年的努力，而生物体通过进化和自然选择这种非定向机制就达到了这个目的。

近三十年的不断的研究和应用已经清楚地表明了模拟自然进化的搜索过程可以产生非常鲁棒(orbust)的计算机算法，虽然这些模型还只是自然界生物体的粗糙简化。进化算法就是基于这种思想发展起来的一类随机搜索技术，它们是模拟由个体组成的群体的集体学习过程。其中每个个体表示给定问题搜索空间中的一点。进化算法从任一初始的群体出发，通过随机选择(在某些算法中是确定的)、变异和重组(在某些算法中被完全省去)过程，使群体进化到搜索空间中越来越好的区域。选择过程使群体中适应性好的个体比适应性差的个体有更多的复制机会，重组算子将父辈信息结合在一起并将他们传到子代个体，变异在群体中引人了新的变种。

目前研究的进化算法主要有三种典型的算法:遗传算法、进化规划和进化策略。这三种算法是彼此独立发展起来的，遗传算法由美国J.Holand创建，后由K.DeJong，J.Grefenstette，D.Goldberg和L.navis等人进行了改进；进化规划最早由美国的L·J·Fogel，A.J.Owens和M.J.walsh提出，最近又由D.B.Fogel进行了完善；进化策略是由德国的I·Reehenberg和H.p.Sehwefel建立的。

群体搜索策略和群体中个体之间的信息交换是进化算法的两大特点。它们的优越性主要表现在:首先，进化算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的，非规则的或有噪声的情况下，它们也能以很大的概率找到全局最优解；其次，由于它们固有的并行性，进化算法非常适合于巨量并行机；再者，进化算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决非常困难的问题；此外，由于它们容易介人到已有的模型中并且具有可扩展性，以及易于同别的技术混和等因素，进化算法目前已经在最优化、机器学习和并行处理等领域得到了越来越广泛的应用。1993年德国Dortmound大学的等人在一份研究t报告中搜集了篇有关进化算法的应用的科技文献。

2、简介

进化算法包括遗传算法、遗传规划、进化规划和进化策略等等。进化算法的基本框架还是简单遗传算法所描述的框架，但在进化的方式上有较大的差异，选择、交叉、变异、种群控制等有很多变化，进化算法的大致框图可描述如右图所示：

同遗传算法一样，进化算法的收敛性也有一些结果，文献证明了在保存最优个体时通用的进化计算是收敛的，但进化算法的很多结果是从遗传算法推过去的。

遗传算法对交叉操作要看重一些，认为变异操作是算法的辅助操作；而进化规划和进化策略认为在一般意义上说交叉并不优于变异，甚至可以不要交叉操作。

进化计算是基于自然选择和自然遗传等生物进化机制的一种搜索算法。与普通的搜索方法一样，进化计算也是一种迭代算法，不同的是进化计算在最优解的搜索过程中，一般是从原问题的一组解出发改进到另一组较好的解，再从这组改进的解出发进一步改进。而且在进化问题中，要求当原问题的优化模型建立后，还必须对原问题的解进行编码。进化计算在搜索过程中利用结构化和随机性的信息，使最满足目标的决策获得最大的生存可能，是一种概率型的算法。

一般来说，进化计算的求解包括以下几个步骤：给定一组初始解；评价当前这组解的性能；从当前这组解中选择一定数量的解作为迭代后的解的基础；再对其进行操作，得到迭代后的解；若这些解满足要求则停止，否则将这些迭代得到的解作为当前解重新操作。

以遗传算法为例，其工作步骤可概括为：

（1）对工作对象——字符串用二进制的0/1或其它进制字符编码。

（2）根据字符串的长度L，随即产生L个字符组成初始个体。

（3）计算适应度。适应度是衡量个体优劣的标志，通常是所研究问题的目标函数。

（4）通过复制，将优良个体插入下一代新群体中，体现“优胜劣汰”的原则。

（5）交换字符，产生新个体。交换点的位置是随机决定的

（6）对某个字符进行补运算，将字符1变为0，或将0变为1，这是产生新个体的另一种方法，突变字符的位置也是随机决定的。

（7）遗传算法是一个反复迭代的过程，每次迭代期间，要执行适应度计算、复制、交换、突变等操作，直至满足终止条件。

将其用形式化语言表达，则为：假设α∈I记为个体，I记为个体空间。适应度函数记为Φ：I→R。在第t代，群体P(t)={a1(t),a2(t)，…，an(t)}经过复制r(reproduction)、交换c(crossover)及突变m(mutation)转换成下一代群体。这里r、c、m均指宏算子，把旧群体变换为新群体。L：I→{True,Flase}记为终止准则。利用上述符号，遗传算法可描述为：

3、框架

进化算法是以达尔文的进化论思想为基础，通过模拟生物进化过程与机制的求解问题的自组织、自适应的人工智能技术。生物进化是通过繁殖、变异、竞争和选择实现的；而进化算法则主要通过选择、重组和变异这三种操作实现优化问题的求解。如下：

其中r、m、s分别表示重组算子、变异算子、选择算子。

4、特点

进化计算是一种具有鲁棒性的方法，能适应不同的环境不同的问题，而且在大多数情况下都能得到比较满意的有效解。他对问题的整个参数空间给出一种编码方案，而不是直接对问题的具体参数进行处理，不是从某个单一的初始点开始搜索，而是从一组初始点搜索。搜索中用到的是目标函数值的信息，可以不必用到目标函数的导数信息或与具体问题有关的特殊知识。因而进化算法具有广泛的应用性，高度的非线性，易修改性和可并行性。

此外，算法本身也可以采用动态自适应技术，在进化过程中自动调整算法控制参数和编码精度，比如使用模糊自适应法。

5、进化策略

进化策略(ES)是在1965年由Rechenberg和Schwefel独立提出的。

进化策略的一般算法

(1)问题为寻找实值n维矢量x，使得函数F(x):R→R取极值。不失一般性，设此程序为极小化过程。

(2)从各维的可行范围内随机选取亲本xi，i=1,…,p的始值。初始试验的分布一般是均匀分布。

(3)通过对于x的每个分量增加零均值和预先选定的标准差的高斯随机变量，从每个亲本xi产生子代xi’。

(4)通过将适应度F(xi)和F(xi’)，i=1，…，P进行排序，选择并决定那些矢量保留。具有最小适应度的P个矢量变成下一代的新亲本。

进行新试验，选择具有最小方差的新子代，一直到获得充分解，或者直到满足某个终止条件。

在这个模型中，把试验解的分量看做个体的行为特性，而不是沿染色体排列的基因。假设不管发生什么遗传变换，所造成各个个体行为的变化均遵循零均值和某个标准差的高斯分布。

由于基因多效性和多基因性，特定基因的改变可以影响许多表现型特征。所以在创造新子系时，较为合适的是同时改变亲本所有分量。

(1+1)—ES：

早期的进化策略的种群中只包含一个个体，并且只使用变异操作。在每一代中，变异后的个体与其父代进行比较，并选择较好的一个，这种选择策略被称为(1+1)策略。

(1+1)—ES的缺点：

(1)各维取定常的标推差使得程序收敛到最优解的速度很慢；

(2)点到点搜索的脆弱本质使得程序在局部极值附近容易受停滞的影响(虽然此算法表明可以渐近地收敛到全局最优点)。

(μ+λ)—ES：μ个亲本制造λ个子代，所有解均参加生存竞争，选出最好的μ个作为下一代的亲本。

(μ，λ)—ES：只有λ个子代参加生存竞争，在每代中μ个亲本被完全取代。

1．个体的表示法:

每个解矢量不仅包括了n维试验矢量x，而且还包括了扰动矢量σ，后者给出如何变异x以及它本身如何变异的指令。

2．变异：

设x为当前矢量。σ为对应于x每个维的方差矢量，于是新的解矢量x’，σ’可以这样产生：

3．交叉：

4．选择

在进化策略中，选择是按完全确定的方式进行。(μ,λ)—ES是从λ个子代个体集中选择μ(1

6、进化规划

进化规划(EP)由Fogel在20世纪60年代提出。

1．表示法和适应值度量

进化规划假设—个有界子空间，其中ui

2．变异

可简化为：

3．选择

在P个父代个体每个经过一次变异产生P个子代后，进化规划利用一种随机q竞争选择方法从父代和子代的集合中选择P个个体，其中q>1是选择算法的参数。

7、差分算法

差分进化算法(DifferentialEvolution,DE)是一种新兴的进化计算技术，或称为差分演化算法、微分进化算法、微分演化算法、差异演化算法。它是由Storn等人于1995年提出的，最初的设想是用于解决切比雪夫多项式问题，后来发现DE也是解决复杂优化问题的有效技术。DE与人工生命，特别是进化算法有着极为特殊的联系。

差分进化算法是基于群体智能理论的优化算法，通过群体内个体间的合作与竞争产生的群体智能指导优化搜索。但相比于进化算法，DE保留了基于种群的全局搜索策略，采用实数编码基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性。同时，DE特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题。

差分进化算法是一种基于群体进化的算法，具有记忆个体最优解和种群内信息共享的特点，即通过种群内个体间的合作与竞争来实现对优化问题的求解，其本质是一种基于实数编码的具有保优思想的贪婪遗传算法。

DE是一种用于优化问题的启发式算法。本质上说，它是一种基于实数编码的具有保优思想的贪婪遗传算法。同遗传算法一样，DE包含变异和交叉操作，但同时相较于遗传算法的选择操作，DE采用一对一的淘汰机制来更新种群。由于DE在连续域优化问题的优势已获得广泛应用，并引发进化算法研究领域的热潮。

DE由Storn以及Price提出，算法的原理采用对个体进行方向扰动，以达到对个体的函数值进行下降的目的，同其他进化算法一样，DE不利用目标函数的梯度信息，因此对目标的可导性甚至连续性没有要求，适用性很强。同时，算法与粒子群优化有相通之处，但因为DE在一定程度上考虑了多变量间的相关性，因此相较于粒子群优化在变量耦合问题上有很大的优势。算法的实现参考实现代码部分。