进化策略

(μ+λ)进化策略(1.初始种群的表示和计算 2.评估 3.重组和变异)

进化策略

进化策略(Evolutionary Strategies,ES)是由德国的I.Rechenberg和H.P.Sehwefel于1963年提出的。ES作为一种求解参数优化问题的方法，模仿生物进化原理，假设不论基因发生何种变化，产生的结果（性状）总遵循零均值、某一方差的高斯分布。　 　 进化策略和遗传算法（GA）是进化算法（EAs）的两类重要变种。这两种主流方法的不同之处在于解的表示以及搜索和选择算子的设计。GA常使用二进制或整数编码，与此相比，ES常基于真实值编码。GA和EA之间的一个显著差别在于选择算子。在ES中，父代选择是无偏的，即，当前种群的每一个个体有着相同的概率被选择用以重组。此外，幸存者的确定性选择是ES的驱动力。不过最近几十年涌现出了许多混合方法。一方面，使用整数编码的ES被开发用于组合优化问题的求解。另一方面，也有人提出了使用ES选择模型的GA。

(μ+λ)进化策略

对于组合优化问题，有人建议使用(μ+λ)-ES 。(μ+λ)-ES 的种群概念如下：搜索开始时，建立一个初始种群 POP0，包含μ个个体。从初始种群开始，迭代计算一系列种群。在每一次迭代iter中，从当前代POPiter产生 λ个子代。在每种情况下，用三步计算产生一个子代：（1）从当前代POPiter中选择两个个体，作为父代用于重组。父代的选择是无偏的。（2）通过所选父代的重组，产生一个新个体。（3）对新个体施行变异和评估。在迭代结束时，从λ个子代与μ个POPiter代个体组成的集合中，选择μ个个体形成新一代种群POPiter+1。现在，将解的质量作为选择的标准：即，选择μ个具有最高质量的个体来代替当前代。商μ/λ被称为选择压，其值越小，说明选择压越大，反之亦然。以下以资源受限项目调度问题（RCPSP）的进化策略为例，说明进化策略的具体算法。

1.初始种群的表示和计算

每个个体代表待求解项目调度问题的一个可行调度。使用活动列表来表示。活动列表是满足优先关系的，亦即，任意活动必须位于它所有紧前活动之后。为了产生一个活动列表，使用了经过修改的由Hartmannyu于2002描述的基于优先规则的抽样启发式方法。

一个个体通过串行调度生成方案解码成一个调度。串行调度生成方案按以下方式来从活动列表构建调度：活动按列表指定的顺序来调度。从而，每项活动被分配到最早的满足优先关系和资源约束的开始时间。待调度活动的最早可行开始时间的计算考虑了资源的可获得量。

2.评估

通过其所代表的调度的解的质量来评估每个个体。解的质量用工期 （在RCPSP情形下）来衡量。

3.重组和变异

重组用Hartmann于1998年开发的两点交叉来实现。它从两个被选择出的父代个体中计算产生一个新的满足优先约束的活动列表。

在变异的框架下，通过一个著名的局部搜索技术在四个步骤下改变活动列表：（1）通过个体活动的左移对活动列表进行随机修改。（2）解码经过修改的活动列表，并计算其所表示的调度。（3）通过个体活动列表的前向和后向移动来修改调度。（4）用经过修改的调度计算一个新的活动列表。

在第一步中，对活动列表中的每项活动，尝试以概率p随机移动若干位置。在位置移动之后，再进行一次移动，以确保该活动出现在列表中它的所有紧前活动之后。在第二步解码活动列表之后，尝试改善活动列表所代表的调度，这是第三步。为了达到改善的目的，首先对调度施加前向移动，然后施加后向移动。在第四步中，改善的调度能够精确转化为一个编码的活动列表。为了实现这一目的，让活动以其开始时间的顺序依次进入活动列表。如果两项活动开始时间相同，则按照活动编号的升序依次进入。