第4期 丁青锋，等：差分进化算法综述 ·433. 势以及并行分布的特点，为解决实际复杂优化问题 大[3]：但种群规模N。过大则会降低找到正确搜索 提供了一种可行途径。但算法中涉及的各种控制 方向的可能性[3) 参数的设置以及进化策略的选择通常都是依据经 2)控制参数。文献[34]指出，种群个体多样性 验确定的，缺乏理论的分析和指导，因此在进行各 的丧失是引发种群早熟的直接诱因。为保持种群 种实际复杂问题优化时易陷入局部最优，出现早熟 多样性，控制参数设置是否合适就显得尤为重要。 收敛或者搜索停滞等现象[3) 其中收缩因子F需要保持一定的变化范围：交叉因 2.1差分进化算法的早熟收敛问题 子CR的大小决定种群个体中元素被替代的程度： DE算法通常是一种在搜索空间内有效的搜索 较小的CR值将造成种群的多样性变化不显著，搜 算法。其中控制参数的设置与进化策略的选择是 索速度也将变慢：较大的CR值意味着种群多样性 决定算法性能好坏的关键，一旦选择不当，往往容 更好，但不利于算法的开发能力，因此算法的收敛 易造成进化种群过早地失去多样性，使种群个体集 性能将会受到影响[3] 中到某一局部最优点，导致种群整体早熟收敛，无 3)进化策略：搜索能力与开发能力是差分进化 法实现向全局最优进化[32】，从图2中可以清楚地看 算法性能重要的标准。其中搜索能力推动在更大 出其全局最优解及局部最优解的分布。一旦进化 范围搜索，从而使候选解具有多样性，因此可提高 个体收敛到局部最优解，新生个体很难获得更优 找到全局最优解的可能性，但搜索能力过强则易导 解，进而出现早熟收敛的情况。 致搜索停滞：开发能力推动在局部最优解附近的搜 索，因此有利于收敛，但开发能力过强则易导致早 ×10 熟收敛36]。进化策略的选择是决定差分进化算法 搜索能力与开发能力平衡的关键，不同的进化策略 3 2 表现出不同的搜索与开发能力的倾向。不同的变 异和交叉策略对算法的收敛性能有不同的影响。 0 针对上述进化种群早熟收敛的问题，很多学者 提出了多种改进的方法，通过设置合适参数和选择 2 恰当的进化策略，以希望在算法有效性（候选解的 质量)和效率（收敛速度）之间达到平衡，主要手段 (a)多峰函数 包括：控制参数调节[7-9]、局部优化[o]和混合其他 优化算法41-。其中，局部优化通过在搜索到的最 优解附近进行精细搜索，最终实现优化结果精确度 局部最优解 的提高。然而，自适应变异策略一方面可以赋予进 化算法快速精确地定位局部最优解，另一方面也是 局部最优解 易陷入早熟收敛从而导致寻优失败[)]。提高种群 全局最优图 的多样性可以增强算法搜索大空间的能力，避免早 熟收敛问题的发生；然而，增强种群多元性虽然能 搜索到更大的空间，但容易降低种群进化的收敛速 0 2 度，甚至陷入局部最优从而导致优化失败。 (b)最优解分布 算法整体收敛速度也是DE算法的一个重要指 图2多峰函数的早熟收敛 标。虽然已有不少文献提出了许多改进算法，但是 Fig.2 The premature convergence of multi-peaks function 针对某些特定问题，其优化结果往往很难令人满 影响DE算法早熟收敛的主要因素可以归纳为 意。对于一种优化算法来说，在保证一定收敛速度 以下几点： 的同时，避免算法陷入早熟收敛是一个需要平衡的 1)种群初始化及种群规模。若种群初始化分 难题。因此，差分进化算法仍需要改进，以适应更 布在解空间的局部区域，则易造成算法收缩空间受 多的优化环境。 限。如果进化种群过小，容易造成有效等位基因的 2.2差分进化算法的搜索停滞问题 缺失，从而降低生成具有竞争力的个体可能性进而 假如进化算法变异、交叉后所产生的进化种群 增加种群早熟收敛的可能性)。为了保持足够的 个体比原种群个体的适应度差，则进化个体的更新 种群多样性，避免早熟收敛，种群规模V。应该足够 机制就陷入停顿，即算法的进一步迭代很难产生适 应度更好的个体，最终导致搜索停滞现象的发生。势以及并行分布的特点，为解决实际复杂优化问题 提供了一种可行途径。 但算法中涉及的各种控制 参数的设置以及进化策略的选择通常都是依据经 验确定的，缺乏理论的分析和指导，因此在进行各 种实际复杂问题优化时易陷入局部最优，出现早熟 收敛或者搜索停滞等现象［３１］ 。 ２．１ 差分进化算法的早熟收敛问题 ＤＥ 算法通常是一种在搜索空间内有效的搜索 算法。 其中控制参数的设置与进化策略的选择是 决定算法性能好坏的关键，一旦选择不当，往往容 易造成进化种群过早地失去多样性，使种群个体集 中到某一局部最优点，导致种群整体早熟收敛，无 法实现向全局最优进化［３２］ ，从图 ２ 中可以清楚地看 出其全局最优解及局部最优解的分布。 一旦进化 个体收敛到局部最优解，新生个体很难获得更优 解，进而出现早熟收敛的情况。 （ａ）多峰函数 （ｂ）最优解分布 图 ２ 多峰函数的早熟收敛 Ｆｉｇ．２ Ｔｈｅ ｐｒｅｍａｔｕｒｅ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｍｕｌｔｉ⁃ｐｅａｋｓ ｆｕｎｃｔｉｏｎ 影响 ＤＥ 算法早熟收敛的主要因素可以归纳为 以下几点： １）种群初始化及种群规模。 若种群初始化分 布在解空间的局部区域，则易造成算法收缩空间受 限。 如果进化种群过小，容易造成有效等位基因的 缺失，从而降低生成具有竞争力的个体可能性进而 增加种群早熟收敛的可能性［３１］ 。 为了保持足够的 种群多样性，避免早熟收敛，种群规模 ＮＰ 应该足够 大［３３］ ；但种群规模 ＮＰ 过大则会降低找到正确搜索 方向的可能性［３１］ 。 ２）控制参数。 文献［３４］指出，种群个体多样性 的丧失是引发种群早熟的直接诱因。 为保持种群 多样性，控制参数设置是否合适就显得尤为重要。 其中收缩因子 Ｆ 需要保持一定的变化范围；交叉因 子 ＣＲ 的大小决定种群个体中元素被替代的程度： 较小的 ＣＲ 值将造成种群的多样性变化不显著，搜 索速度也将变慢；较大的 ＣＲ 值意味着种群多样性 更好，但不利于算法的开发能力，因此算法的收敛 性能将会受到影响［３５］ 。 ３）进化策略：搜索能力与开发能力是差分进化 算法性能重要的标准。 其中搜索能力推动在更大 范围搜索，从而使候选解具有多样性，因此可提高 找到全局最优解的可能性，但搜索能力过强则易导 致搜索停滞；开发能力推动在局部最优解附近的搜 索，因此有利于收敛，但开发能力过强则易导致早 熟收敛［３６］ 。 进化策略的选择是决定差分进化算法 搜索能力与开发能力平衡的关键，不同的进化策略 表现出不同的搜索与开发能力的倾向。 不同的变 异和交叉策略对算法的收敛性能有不同的影响。 针对上述进化种群早熟收敛的问题，很多学者 提出了多种改进的方法，通过设置合适参数和选择 恰当的进化策略，以希望在算法有效性（候选解的 质量）和效率（收敛速度）之间达到平衡，主要手段 包括：控制参数调节［３７－３９］ 、局部优化［４０］ 和混合其他 优化算法［４１－４２］ 。 其中，局部优化通过在搜索到的最 优解附近进行精细搜索，最终实现优化结果精确度 的提高。 然而，自适应变异策略一方面可以赋予进 化算法快速精确地定位局部最优解，另一方面也是 易陷入早熟收敛从而导致寻优失败［４３］ 。 提高种群 的多样性可以增强算法搜索大空间的能力，避免早 熟收敛问题的发生；然而，增强种群多元性虽然能 搜索到更大的空间，但容易降低种群进化的收敛速 度，甚至陷入局部最优从而导致优化失败。 算法整体收敛速度也是 ＤＥ 算法的一个重要指 标。 虽然已有不少文献提出了许多改进算法，但是 针对某些特定问题，其优化结果往往很难令人满 意。 对于一种优化算法来说，在保证一定收敛速度 的同时，避免算法陷入早熟收敛是一个需要平衡的 难题。 因此，差分进化算法仍需要改进，以适应更 多的优化环境。 ２．２ 差分进化算法的搜索停滞问题 假如进化算法变异、交叉后所产生的进化种群 个体比原种群个体的适应度差，则进化个体的更新 机制就陷入停顿，即算法的进一步迭代很难产生适 应度更好的个体，最终导致搜索停滞现象的发生。 第 ４ 期 丁青锋，等：差分进化算法综述 ·４３３·