进化策略的(μ+λ)策略

对于组合优化问题，有人建议使用(μ+λ)-ES 。(μ+λ)-ES 的种群概念如下：搜索开始时，建立一个初始种群 POP0，包含μ个个体。从初始种群开始，迭代计算一系列种群。在每一次迭代iter中，从当前代POPiter产生 λ个子代。在每种情况下，用三步计算产生一个子代：（1）从当前代POPiter中选择两个个体，作为父代用于重组。父代的选择是无偏的。（2）通过所选父代的重组，产生一个新个体。（3）对新个体施行变异和评估。在迭代结束时，从λ个子代与μ个POPiter代个体组成的集合中，选择μ个个体形成新一代种群POPiter+1。现在，将解的质量作为选择的标准：即，选择μ个具有最高质量的个体来代替当前代。商μ/λ被称为选择压，其值越小，说明选择压越大，反之亦然。以下以资源受限项目调度问题（RCPSP）的进化策略为例，说明进化策略的具体算法。
初始种群的表示和计算
每个个体代表待求解项目调度问题的一个可行调度。使用活动列表来表示。活动列表是满足优先关系的，亦即，任意活动必须位于它所有紧前活动之后。为了产生一个活动列表，使用了经过修改的由Hartmannyu于2002描述的基于优先规则的抽样启发式方法。
一个个体通过串行调度生成方案解码成一个调度。串行调度生成方案按以下方式来从活动列表构建调度：活动按列表指定的顺序来调度。从而，每项活动被分配到最早的满足优先关系和资源约束的开始时间。待调度活动的最早可行开始时间的计算考虑了资源的可获得量。
评估
通过其所代表的调度的解的质量来评估每个个体。解的质量用工期 （在RCPSP情形下）来衡量。
重组和变异
重组用Hartmann于1998年开发的两点交叉来实现。它从两个被选择出的父代个体中计算产生一个新的满足优先约束的活动列表。
在变异的框架下，通过一个著名的局部搜索技术在四个步骤下改变活动列表：（1）通过个体活动的左移对活动列表进行随机修改。（2）解码经过修改的活动列表，并计算其所表示的调度。（3）通过个体活动列表的前向和后向移动来修改调度。（4）用经过修改的调度计算一个新的活动列表。
在第一步中，对活动列表中的每项活动，尝试以概率p随机移动若干位置。在位置移动之后，再进行一次移动，以确保该活动出现在列表中它的所有紧前活动之后。在第二步解码活动列表之后，尝试改善活动列表所代表的调度，这是第三步。为了达到改善的目的，首先对调度施加前向移动，然后施加后向移动。在第四步中，改善的调度能够精确转化为一个编码的活动列表。为了实现这一目的，让活动以其开始时间的顺序依次进入活动列表。如果两项活动开始时间相同，则按照活动编号的升序依次进入。

本文如未解决您的问题请添加抖音号：51dongshi（抖音搜索懂视），直接咨询即可。