封朋成|Pengcheng Feng's Homepage

    在达尔文的进化论中，自然界物种间和同物种个体间，因为生存竞争而优胜劣汰。但随着人们对自然界的不断观察和研究，发现自然界不只存在竞争，而且存在利他合作，对达尔文进化论进行了补充和发展，形成了新达尔文学说。在自然界中，同一物种和不同物种的种群之间，都存在竞争和共生关系，并且合作比竞争更为普遍。

    1990年，Daniel Hillis受Hamilton启发，创造性地将自然界中捕食者－被捕食者的协同进化现象（predator-prey coevolution）引入进化算法，提出了协同进化算法(CEA,co-evolutionary algorithm)，并将之用于求解排序网络优化问题，取得了良好的效果。

    在Hillis提出协同遗传算法中，存在两个种群，一个种群是候选解，一个种群是测试集，每次只选取少数具有高难度的测试对个体进行评估，两个种群互相评价，共同进化，类似于自然界中捕食者与被捕食者的相互促进的关系，形成协同进化。该算法不仅可以避免陷入局部最优，而且大幅度提升了计算效率。

    Paredis在Hillis基础上，加入了个体全生命周期适应值评估机制（LTFE，life-time fitness evaluation），从而能够引入多种个体学习机制（LTL，life-time learning），包括Back-Propagation等学习机制，形成了更强大的协同进化算法，并将之用于优化分类神经网络和求解约束优化问题。

    与一般的个体评估机制不同的是，全生命周期适应值评估机制不是单纯的使用适应值函数评估，而是尽量将复杂的问题分成小问题，每次评估一个子问题，并且是两个群体互相评估。这样既减小了评估代价，并且总是优先解决当前较难的子问题；同时，种群也不易陷入局部最优，保持了较好的多样性。特别是在求解约束优化问题时，将约束条件作为一个种群，使用全生命周期适应值评估机制后，搜索效率提升明显，具有更强的搜索可行解的能力。

    约束优化问题是很普遍的问题，应用范围广。而进化算法在求解约束优化问题时，具有参数少、不依赖具体问题、计算简单的特点，具有较大优势。目前使用进化算法求解约束优化问题，有几个关键点：

1. 约束处理技术：约束处理技术主要有三种：（1）惩罚函数法。这种方法概念简单，使用广泛。但是权重的确定是个比较难的问题，目前都使用自适应权重；（2）偏好可行解与不可行解法。随机选择适应值或违反约束条件值来选择个体，近年来Yao使用得较多；（3）多目标法。将适应值和违反约束条件看作两个目标，使用多目标求解方法求解，但特别设计算子来计算。这是最近兴起的一种约束处理技术。
2. 可行解与不可行解：在约束问题中，有许多问题都是可行域非常小的，找到可行解是非常困难的，因此在计算过程中寻找可行解是非常重要的。而有些问题的可行域又非常大，寻找最优解是相对困难的，这时候寻找最优解具有较高的优先级。区别这两种情况的办法，是利用可行解和不可行解的比例，自适应使用不同策略解决问题。
3. 全局与局部搜索：解决约束优化问题需要全局和局部搜索能力都强的算法。算法在考虑的时候，一定要关注到其搜索能力的特点，不能单关注全局搜索或者局部搜索，而是要两者兼顾，在搜索过程中，同时又全局搜索和局部搜索的动作。