进化驱动算法

① 进化算法的特点

进化计算是一种具有鲁棒性的方法，能适应不同的环境不同的问题，而且在大多数情况下都能得到比较满意的有效解。他对问题的整个参数空间给出一种编码方案，而不是直接对问题的具体参数进行处理，不是从某个单一的初始点开始搜索，而是从一组初始点搜索。搜索中用到的是目标函数值的信息，可以不必用到目标函数的导数信息或与具体问题有关的特殊知识。因而进化算法具有广泛的应用性，高度的非线性，易修改性和可并行性。
此外，算法本身也可以采用动态自适应技术，在进化过程中自动调整算法控制参数和编码精度，比如使用模糊自适应法 。 进化策略(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<μ<λA=个最好的个体；(μ+λ)—ES是从父代和子代个体的并集中选择μ个最好的个体。虽然(μ+λ)—ES保留最优的个体能保证性能单调提高，但这种策略不能处理变化的环境，因此，目前选用最多的还是(μ,λ)—ES。 进化规划(EP)由Fogel在20世纪60年代提出。
1．表示法和适应值度量
进化规划假设—个有界子空间 ，其中ui<vi。搜索区域被扩展到I=R，即个体为目标变量向量，a=x∈I，进化规划把目标函数值通过比例变换到正值，同时加入某个随机改变θ来得到适应值 ，其中δ是比例函数。
2．变异
可简化为：
3．选择
在P个父代个体每个经过一次变异产生P个子代后，进化规划利用一种随机q竞争选择方法从父代和子代的集合中选择P个个体，其中q>1是选择算法的参数。

② 人工智能之进化算法

进化计算的三大分支包括：遗传算法(Genetic Algorithm ，简称GA)、进化规划(Evolu-tionary Programming，简称EP)和进化策略(Evolution Strategies ，简称ES)。这三个分支在算法实现方面具有一些细微的差别，但它们具有一个共同的特点，即都是借助生物进化的思想和原理来解决实际问题。

遗传算法是一类通过模拟生物界自然选择和自然遗传机制的随机化搜索算法，由美国Holand J教授于1975年首次提出。它是利用某种编码技术作用于称为染色体的二进制数串，其基本思想是模拟由这些串组成的种群的进化过程，通过有组织的、然而是随机的信息交换来重新组合那些适应性好的串。遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并根据适应性来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。遗传算法尤其适用于处理传统搜索方法难于解决的复杂的非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的关键技术之一。

1964年，由德国柏林工业大学的RechenbergI等人提出。在求解流体动力学柔性弯曲管的形状优化问题时，用传统的方法很难在优化设计中描述物体形状的参数，然而利用生物变异的思想来随机地改变参数值并获得了较好效果。随后，他们便对这种方法进行了深入的研究和发展，形成了进化计算的另一个分支——进化策略。

进化策略与遗传算法的不同之处在于：进化策略直接在解空间上进行操作，强调进化过程中从父体到后代行为的自适应性和多样性，强调进化过程中搜索步长的自适应性调节;而遗传算法是将原问题的解空间映射到位串空间之中，然后再施行遗传操作，它强调个体基因结构的变化对其适应度的影响。

进化策略主要用于求解数值优化问题。

进化规划的方法最初是由美国人Fogel LJ等人在20世纪60年代提出的。他们在人工智能的研究中发现，智能行为要具有能预测其所处环境的状态，并按照给定的目标做出适当的响应的能力。在研究中，他们将模拟环境描述成是由有限字符集中符号组成的序列。

进化算法与传统的算法具有很多不同之处，但其最主要的特点体现在下述两个方面：

进化计算的智能性包括自组织、自适应和自学习性等。应用进化计算求解问题时，在确定了编码方案、适应值函数及遗传算子以后，算法将根据“适者生存、不适应者淘汰"的策略，利用进化过程中获得的信息自行组织搜索，从而不断地向最佳解方向逼近。自然选择消除了传统算法设计过程中的-一个最大障碍：即需要事先描述问题的全部特点，并说明针对问题的不同特点算法应采取的措施。于是，利用进化计算的方法可以解决那些结构尚无人能理解的复杂问题。

进化计算的本质并行性表现在两个方面：

一是进化计算是内在并行的，即进化计算本身非常适合大规模并行。

二是进化计算的内含并行性，由于进化计算采用种群的方式组织搜索，从而它可以同时搜索解空间内的多个区域，并相互交流信息，这种搜索方式使得进化计算能以较少的计算获得较大的收益。

③ 进化算法的基本步骤

进化计算是基于自然选择和自然遗传等生物进化机制的一种搜索算法。与普通的搜索方法一样，进化计算也是一种迭代算法，不同的是进化计算在最优解的搜索过程中，一般是从原问题的一组解出发改进到另一组较好的解，再从这组改进的解出发进一步改进。而且在进化问题中，要求当原问题的优化模型建立后，还必须对原问题的解进行编码。进化计算在搜索过程中利用结构化和随机性的信息，使最满足目标的决策获得最大的生存可能，是一种概率型的算法。
一般来说，进化计算的求解包括以下几个步骤：给定一组初始解；评价当前这组解的性能；从当前这组解中选择一定数量的解作为迭代后的解的基础；再对其进行操作，得到迭代后的解；若这些解满足要求则停止，否则将这些迭代得到的解作为当前解重新操作。
以遗传算法为例，其工作步骤可概括为：
（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(reproction)、交换c(crossover)及突变m(mutation)转换成下一代群体。这里r、c、m均指宏算子，把旧群体变换为新群体。L：I→{True, Flase}记为终止准则。利用上述符号，遗传算法可描述为：
t=0
initialize P(0):={ a1(0),a2(0)，…，an(0)};
while(l(P(t))≠True) do
evaluate P(t):{ Φ(a1(t)), Φ(a2(t))，…，Φ(an(t))};
reproction: P′(t):=r(P(t));
crossover: P″(t):=c(P′(t));
mutation: P(t+1):= m(P″(t));
t=t+1;
end