·434 智能系统学报 第12卷 如图3所示，若6个候选个体的适应度函数值皆劣 数，初值为0，i=1,2,…,Np。若{nu.c}持续增加，则 于个体A,则个体A将保留到下一代。若个体B、C、 说明DE算法无法为目标个体i产生极值解。 D也重复个体A的情况，意味着下一代种群与现有 克服进化算法搜索停滞的一般方法是在算法 种群相同，即出现搜索停滞的情况。因此虽然种群 中引入能够在整个解空间中进行广泛搜索的策略， 仍然保持多样性，但无法再进一步收敛。 另外通过jitter/dither扰动技术，也可以降低搜索停 15f 滞出现的概率[]。在不改变种群规模的情况下，文 献[46]指出，通过收缩因子F和增大交叉因子CR 可以增加种群个体的多样性：文献[33]指出，通过 5 设置收缩因子F在进化过程中为随机数，可以有效 ●C A 增加候选个体的数量，实现算法稳定性的提高。 B 也有学者4]为平衡算法集中搜索与多样化搜 -5 ●D 索策略之间的矛盾，提出外在的种群多样化测度方 法，根据群体多样化测度值在算法的不同搜索阶段 -10 使用不同搜索策略，从而克服搜索停滞的缺陷。但 -15 群体多样化测度方法通常是针对某一算法构造的， -15 -10 -5 0 5 1015 缺乏对搜索停滞的起因、表现特征深入系统的研 (a)现有种群 究，因此具有较大的局限性。 在研究DE算法大量文献中，很少提及搜索停 15 滞问题产生机理。文献[48]进一步对群体优化算 10 法的搜索机理进行探讨，针对集中化搜索与多样化 搜索对进化停滞的影响进行了研究，从而证明了集 5 中化搜索策略具有将候选解趋于单一化的特点，是 A 0 导致算法搜索停滞的主要原因：而多样化搜索策略 00 则具有将候选解泛化的特点，即从任何一个候选解 -5 中o 可以搜索到整个解空间的任意一点，但其缺点是使 -10 算法不收敛。文献[44]指出，无法确切地发现搜素 停滞的原理，但是通过增加种群个体的多样性及规 -15 -15-10-5 051015 模可以在一定程度上降低该问题出现的概率。 (b)个体A的候选个体 3差分进化算法的改进策略 图3差分进化算法搜索停滞 针对DE算法的理论研究主要集中在如何提高 Fig.3 Search stagnation of DE 算法的寻优能力、收敛速度以及克服启发式算法常 DE算法出现搜索停滞具有以下两个特征4： 见的早熟收敛以及搜索停滞等缺陷方面。近年来， 1)种群个体不收敛：2)个体进化更新机制失效。 研究人员从多个角度不断改进算法以适应更为复 当DE算法搜索停滞发生时，停滞特征1)可以 杂的优化问题和满足更高的求解质量，改进算法大 用第G代的目标个体与其重心之间的平均距离来 致分为控制参数设置、差分策略选择、种群结构以 描述： 及与其他最优化算法混合等四大类。 de=(1/Np)∑Ixc-el (1) 1)控制参数 式中：&=(1/N,)∑”xe为标个体的重心。若 DE算法的控制参数主要有种群规模Vp、缩放 因子F以及交叉概率CR。如果参数选择不恰当 平均距离没有下降到一个很小值，则意味着种群未 可能会由于过度强调搜索能力导致算法搜索停滞 收敛到一个极值点。 或者过度强调开发能力导致算法早熟收敛。其中 DE算法发生搜索停滞时的特征2)可以用第G 种群规模主要影响种群的多样性以及收敛速度：增 代目标个体最近连续未更新次数来描述： 大N。可以提高种群的多样性，但同时降低种群的 (0,fu.c)≤fx.c） nui.G+1= (2) 收敛速度：减小N可以提高收敛速度，但易导致早 (n.c+1,其他 熟收敛。缩放因子F主要影响搜索步长：增大F可 式中：n.c为第G代目标个体i未最近连续更新次 以增加算法的搜索范围，提高种群多样性但同时消如图 ３ 所示，若 ６ 个候选个体的适应度函数值皆劣 于个体 Ａ，则个体 Ａ 将保留到下一代。 若个体 Ｂ、Ｃ、 Ｄ 也重复个体 Ａ 的情况，意味着下一代种群与现有 种群相同，即出现搜索停滞的情况。 因此虽然种群 仍然保持多样性，但无法再进一步收敛。 （ａ） 现有种群 （ｂ）个体 Ａ 的候选个体 图 ３ 差分进化算法搜索停滞 Ｆｉｇ．３ Ｓｅａｒｃｈ ｓｔａｇｎａｔｉｏｎ ｏｆ ＤＥ ＤＥ 算法出现搜索停滞具有以下两个特征［４４］ ： １）种群个体不收敛；２）个体进化更新机制失效。 当 ＤＥ 算法搜索停滞发生时，停滞特征 １）可以 用第 Ｇ 代的目标个体与其重心之间的平均距离来 描述： ｄＧ ＝ （１ ／ ＮＰ ）∑ ＮＰ １ ‖ｘｉ，Ｇ － ｘ － Ｇ‖ （１） 式中： ｘ － Ｇ ＝ （１ ／ ＮＰ ）∑ ＮＰ １ ｘｉ，Ｇ 为目标个体的重心。 若 平均距离没有下降到一个很小值，则意味着种群未 收敛到一个极值点。 ＤＥ 算法发生搜索停滞时的特征 ２）可以用第 Ｇ 代目标个体最近连续未更新次数来描述： ｎｕｉ，Ｇ＋１ ＝ ０， ｆ（ｕｉ，Ｇ ） ≤ ｆ（ｘｉ，Ｇ ） ｎｉ，Ｇ { ＋ １， 其他 （２） 式中：ｎｕｉ，Ｇ为第 Ｇ 代目标个体 ｉ 未最近连续更新次 数，初值为 ０，ｉ ＝ １，２，…，ＮＰ 。 若 ｎｕｉ，Ｇ { }持续增加，则 说明 ＤＥ 算法无法为目标个体 ｉ 产生极值解。 克服进化算法搜索停滞的一般方法是在算法 中引入能够在整个解空间中进行广泛搜索的策略， 另外通过 ｊｉｔｔｅｒ／ ｄｉｔｈｅｒ 扰动技术，也可以降低搜索停 滞出现的概率［４５］ 。 在不改变种群规模的情况下，文 献［４６］指出，通过收缩因子 Ｆ 和增大交叉因子 ＣＲ 可以增加种群个体的多样性；文献［３３］ 指出，通过 设置收缩因子 Ｆ 在进化过程中为随机数，可以有效 增加候选个体的数量，实现算法稳定性的提高。 也有学者［４７］ 为平衡算法集中搜索与多样化搜 索策略之间的矛盾，提出外在的种群多样化测度方 法，根据群体多样化测度值在算法的不同搜索阶段 使用不同搜索策略，从而克服搜索停滞的缺陷。 但 群体多样化测度方法通常是针对某一算法构造的， 缺乏对搜索停滞的起因、表现特征深入系统的研 究，因此具有较大的局限性。 在研究 ＤＥ 算法大量文献中，很少提及搜索停 滞问题产生机理。 文献［４８］ 进一步对群体优化算 法的搜索机理进行探讨，针对集中化搜索与多样化 搜索对进化停滞的影响进行了研究，从而证明了集 中化搜索策略具有将候选解趋于单一化的特点，是 导致算法搜索停滞的主要原因；而多样化搜索策略 则具有将候选解泛化的特点，即从任何一个候选解 可以搜索到整个解空间的任意一点，但其缺点是使 算法不收敛。 文献［４４］指出，无法确切地发现搜素 停滞的原理，但是通过增加种群个体的多样性及规 模可以在一定程度上降低该问题出现的概率。 ３ 差分进化算法的改进策略 针对 ＤＥ 算法的理论研究主要集中在如何提高 算法的寻优能力、收敛速度以及克服启发式算法常 见的早熟收敛以及搜索停滞等缺陷方面。 近年来， 研究人员从多个角度不断改进算法以适应更为复 杂的优化问题和满足更高的求解质量，改进算法大 致分为控制参数设置、差分策略选择、种群结构以 及与其他最优化算法混合等四大类。 １）控制参数 ＤＥ 算法的控制参数主要有种群规模 ＮＰ 、缩放 因子 Ｆ 以及交叉概率 ＣＲ。 如果参数选择不恰当， 可能会由于过度强调搜索能力导致算法搜索停滞 或者过度强调开发能力导致算法早熟收敛。 其中 种群规模主要影响种群的多样性以及收敛速度：增 大 ＮＰ 可以提高种群的多样性，但同时降低种群的 收敛速度；减小 ＮＰ 可以提高收敛速度，但易导致早 熟收敛。 缩放因子 Ｆ 主要影响搜索步长：增大 Ｆ 可 以增加算法的搜索范围，提高种群多样性但同时消 ·４３４· 智 能 系 统 学 报 第 １２ 卷