科学与工程领域的大多数优化问题本质上都是“多模态”的, 这类问题被称为多模态优化问题, 其特点是目标函数同时具有多个全局最优解或局部最优解. 传统使用的求解方法在求解MMOPs时须反复计算多次, 才有可能找到不同的最优解, 这样既费时又费力. 因此, 寻找可行有效的求解MMOPs的新算法一直以来备受广大科技工作者的关注^[1-4]. 为此, 许多被称为小生境的技术包括拥挤^[5]、共享^[6]、聚类^[7]、物种^[8]和种群拓扑^[9]等被提出. 小生境的主要思想是将整个种群划分为几个小生境(亚种群), 每个亚种群集中于寻找一个或几个最优值.

差分进化算法(Differential Evolution, DE)^[10]是由Storn和Price在1995年提出的一种全局优化启发式算法. 由于其简单、有效, 已被用于处理各种各样的优化问题, 例如全局优化问题^[11], MMOPs^[12], 多目标优化问题^[13]等. 近年来,一些基于小生境的DE变体^[14-18]被提出以处理MMOPs, 但是, 这些方法在最优解数量大、维度高和复杂性高的时候效果往往不太理想.

本文提出了一种基于邻域低密度个体的差分进化算法(Low Density Points Differential Evolutionary, LDPDE)求解MMOPs. 算法在每一代, 首先使用密度峰值聚类的方法求得每一个个体的密度, 然后, 优先对邻域范围密度低于当前个体的目标个体进行突变操作, 随着种群的进化, 种群个体逐渐收敛到小生境中心, 进化过程将会自动的从探索阶段转化为收敛阶段, 进而平衡算法的探索与收敛能力. LDPDE算法的主要特点有: (1) LDPDE是一种基于距离的小生境方法, 它可以通过邻域范围内个体的密度变化达到算法探索与收敛之间的平衡. (2) 提出了一种新的DE变异算子, 称为DE/low-density/1, 该算子在算法的探索阶段可以寻找尽可能多的有效个体.

1 差分进化算法

考虑优化模型:

$\mathop {\min }\limits_{x \in \Omega \subseteq {R^n}} f(X)$

(1)

其中, $X = [{x_1},{x_2}, \cdots ,{x_n}]$ 为 $n$ 维向量, $\Omega \in {R^n}$ 为求解区域, $f( \cdot )$ 为目标函数.

差分进化算法是一种简单有效的全局优化启发式算法. 与其他进化算法类似, DE有4个步骤: 初始化、变异、交叉和选择. 标准的DE算法过程如下:

(1) 初始化

首先, DE从最小和最大界限约束的搜索空间内对个体进行均匀随机化, 可以表示为:

$x_{i,n}^j = x_{\min }^j + rand(0,1) \cdot \left( {x_{\max }^j - x_{\min }^j} \right)$

其中, $x_{i,n}^j$ 表示第n代第i个个体 ${x_{i,n}}$ 在第j个维度上的值. $x_{\max }^j$ 和 $x_{\min }^j$ 表示第 $j$ 个变量的上下边界. 下标i和j在 $[1,NP]$ 和 $[1,D]$ 范围内, 其中NP表示种群大小, D表示问题维度. $rand(0,1)$ 表示从0到1生成均匀分布的随机值.

(2) 变异

初始化后, 从当前种群中随机选择的个体经过变异算子产生突变个体 ${v_i}$ . 在标准DE中, 使用以下运算方法:

${v_i} = {x_{r_1^i,n}} + F \cdot \left( {{x_{r_2^i,n}} - {x_{r_3^i,n}}} \right)$

其中, $r_1^i,r_2^i$ 和 $r_3^i$ 是从 ${{\{ 1,2, \cdots ,NP\} } / {\{ i\} }}$ 中生成的互斥整数, F是比例因子, 一般取值为0.1到0.9之间.

(3) 交叉

交叉算子通过重新组合目标个体 $x_{i,n}^j$ 和突变个体 ${v_i}$ 来生成实验个体 ${u_i}$ . 在标准DE中, 使用了两种类型的算子, 即指数和二项式. 在本文研究中, 我们使用二项式运算符. 在二项式运算符中, 实验个体中的每个元素都继承用户指定的概率为Cr的突变个体的值, 并以 $(1 - Cr)$ 的概率继承目标个体的值. 实验个体 ${u_i}$ 为:

$u_i^j = \left\{ {\begin{array}{*{20}{l}} {v_i^j},&{rand < Cr \vee j = {j_{rand}}} \\ {x_{i,n}^j},&{\rm otherwise} \end{array}} \right.$

其中, ${j_{rand}} \in \{ 1,2, \cdots ,NP\} $ 是随机选择的索引, 可确保 ${u_i}$ 至少继承突变个体 ${v_i}$ 中的至少一个分量.

(4) 选择

选择运算符确定目标或实验个体是否进入到下一代. 如果新的实验个体的函数值等于或小于目标个体的函数值, 它将替换相应的目标个体. 下一代 ${x_{i,n + 1}}$ 中的目标向量为:

${x_{i,n + 1}} = \left\{ {\begin{array}{*{20}{l}} {{u_i}},&{f({u_i}) \le f({x_{i,n}})} \\ {{x_{i,n}}},&{f({x_{i,n}}) < f({u_i})} \end{array}} \right.$

最后, DE继续执行变异、交叉和选择运算符, 直到满足终止条件为止. 算法1中以伪代码的形式给出了标准DE的算法过程.

算法1. 标准差分进化算法(DE)

输入: 目标函数(最小值)f(x); 比例因子F; 交叉率Cr; 种群大小NP; 进化代数MaxIt.

1)　随机初始化种群 $\scriptstyle{X_1} = [{x_{1,1}},{x_{2,1}}, \cdots ,{x_{NP,1}}]$ ;

2)　 $\scriptstyle{\rm{for}}\;n = 1, \cdots ,MaxIt\;{\rm{do}}$

3)　　 $\scriptstyle {\rm{for}}\;i = 1, \cdots ,NP\;{\rm{do}}$

4)　　　 $\scriptstyle{v_i} = {x_{r_1^i,n}} + F \cdot \left( {{x_{r_2^i,n}} - {x_{r_3^i,n}}} \right),$

5)　　 $\scriptstyle u_i^j = \left\{ {\begin{array}{*{20}{l}} \scriptstyle{v_i^j},&\scriptstyle{rand < Cr \vee j =\scriptstyle{j_{rand}}}\\ \scriptstyle{x_{i,n}^j},&\scriptstyle{\rm otherwise} \end{array}} \right.$

6)　 $\scriptstyle {\rm{end}}\;{\rm{for}}$

7)　 $\scriptstyle{\rm{for}}\;i = 1, \cdots ,NP\;{\rm{do}}$

8)　　　 $\scriptstyle{x_{i,n + 1}} = \left\{ {\begin{array}{*{20}{l}} \scriptstyle{{u_i}},&\scriptstyle{f({u_i}) \ge f({x_{i,n}})} \\ \scriptstyle{{x_{i,n}}},&\scriptstyle{f({u_i}) < f({x_{i,n}})} \end{array}} \right.$

9)　　 $\scriptstyle{\rm{end}}\;{\rm{for}}$

10) $\scriptstyle{\rm{end}}\;{\rm{for}}$

11) 输出 $\scriptstyle{X_{MaxIt}}$ 中使得 $\scriptstyle f(x)$ 最大的个体.

2 准备工作 2.1 密度峰值聚类

密度峰值聚类^[19]是一种简单有效的快速聚类方法, 由Rodriguez和Laio^[20]通过发现潜在簇的密度峰值提出. 对于每个数据点 $x(i)$ , 该算法都会计算其局部密度 $\;\rho (i)$ 以及与距其最近密度更大点的距离 $\sigma (i)$ , 由此可以得到每个数据点的孤立性. 以下介绍密度峰值聚类的原理.

数据点 $x(i)$ 的局部密度的定义如下所示:

$\rho (i) = \sum\limits_{j \in {I_S}\backslash \{ i\} } {{{\rm e}^{ - {{\left( {\textstyle\frac{{{d_{ij}}}}{{{d_c}}}} \right)}^2}}}} $

(2)

其中, ${d_{ij}}$ 是第i个和第j个数据点之间的距离, ${d_c}$ 是截止距离. 对于截止距离 ${d_c}$ , 原始论文没有提供正确设置的有效方法. 在文献[21]中, 作者提出了一种基于潜在熵的方法, 可以根据数据域自动设置. 对于一个数据集 $x(i),\; i = 1,2, \cdots ,n$ , 计算第i个数据点 $x(i)$ 的电势 $\psi (i)$ :

$\psi (i) = \sum\nolimits_{j = 1}^n {{{\rm e}^{ - {{\left( {\textstyle\frac{{\left\| {x(i) - x(j)} \right\|}}{\sigma }} \right)}^2}}}} $

(3)

则熵H为:

$H = - \sum\nolimits_{i = 1}^n {\frac{{\psi (i)}}{{\textit{z}}}\log \left( {\frac{{\psi (i)}}{{\textit{z}}}} \right)} $

(4)

其中, 归一化因子z为:

${\textit{z}} = \sum\nolimits_{i = 1}^n {\psi (i)} $

(5)

现在只要找到使得H值最小的 $\sigma $ , 记为 ${\sigma '}$ , 即可得到截止距离 ${d_c}$ . 显然, ${d_c}$ 的值一定处于 $\min \{ \left\| {x(i) - x(j)} \right\|\} $ 和 $\max \{ \left\| {x(i) - x(j)} \right\|\} $ 之间, 对于简单的一维优化问题本文使用黄金分割法求得 $\sigma $ , 最后将临界值设置为 ${d_c}{\rm{ = 3}} \cdot {\sqrt 2 ^{ - 1}}{\sigma '}$ .

2.2 其他多模态优化算法

为了解决多模态优化问题, 许多策略被提出并将嵌入到DE中. 以下将简要介绍与DE相结合的各种策略.

(1) 拥挤(CDE): 文献[14]将拥挤方案和健身共享嵌入到DE中, 分别形成CDE算法和SharingDE算法. 在CDE算法中, 对于每个子代个体, 通过在父代种群中随机选择C个父代个体, 然后将子代与该群体中最相似(欧氏距离最近)的父代进行比较. 如果子代更好, 它将取代该种群中最相似的父代个体. 否则, 子代个体将被遗弃. SharingDE算法则利用共享方案来防止种群收敛到同一个高峰.

(2) 物种(SDE): 在SDE算法^[15]中, 根据个体的适宜性和小生半径r将整个种群分为几个物种. 每个物种都有一个具有最佳适应性的物种种子, 并且DE运算符只在当前物种种群内执行. 然后将生成的N个子代个体与N个父代个体合并为一个种群, 从合并种群中选择N个最佳个体, 形成一个新的种群.

(3) 聚类: Qu等^[16]提出了嵌入到CDE算法和SDE算法中的邻域突变策略(包括NCDE和NSDE)中, DE运算符在每个个体的欧几里得邻域中执行. 遵循这一思想, Gao等^[17]提出了一种具有自适应策略(包括self-CCDE和CSDE)的聚类DE, 它采用自适应参数控制来增强DE的搜索能力. Zhang等^[18]提出了一种新的基于位置敏感哈希的小生境技术以降低时间复杂度, 并将其应用于NCDE中, 称为Fast-NCDE算法.

以上这些方法在处理MMOPs问题时已经显示出各方面的有效性, 但它们也有一定的缺点. 一方面, 随着MMOPs问题全局最优解的数量增加, 这些方法将全部最优值点找到的机会就越小; 另一方面, 在解决具有高维度和高复杂性的MMOPs时, 几乎所有这些固定方法都会失效. 因此, 为解决高维度和高复杂性的MMOPs, 许多其他基于DE的多模态算法被提出. Biswas等^[22]提出了一种新的信息共享机制, 该机制使用本地信息矩阵来诱导有效的利基行为, 称为LoINDE算法(包括LoICDE算法和LoISDE算法). 同时, 他们还提出了一种新的以父代为中心的标准化邻域(PCNN)变异算子, 以维持多个最优值, 称为PNPCDE算法^[23]. Wang等^[24]提出了是一种基于距离的小生境方法, 称为MSTDE算法, 通过DPR策略切割少量大的加权边来形成多个小生境, 平衡收敛性和多样性.

3 基于低密度的差分进化算法

在本节中, 我们将提出基于密度峰值的差分进化算法(LDPDE).

3.1 基于孤立个体的变异算子

受文献[25]启发, 提出一种用于多模态优化的新DE变异算子, 称为DE/low-density/1. 该算子的主要特征是它在当前个体邻域中随机选择密度低于当前个体的个体作为变异算子的目标个体, 因此, 目标个体可以被选择变异算子迁移到隔离区域. 在典型的小生境方法中, 同一山谷中的个体倾向于通过在山谷中下降聚集在一起. 而在本文提出的方法中, 个体积极地迁移到其他山谷. DE/low-densit/1中使用的变异算子描述如下:

${v_i} = x_{r_1^p,n}^{\rm near} + {F_1} \cdot \left( {{x_{r_2^i,n}} - x'_{r_2^i,n}} \right)$

(6)

其中, $r_1^p$ 是从 $\left\{ {{p^{\rm near}}(j) < p(i)\left| {j = 1,2, \cdots ,{N_d}_1} \right.} \right\}$ 中生成随机整数, ${p^{\rm near}}$ 是 ${x_{i,n}}$ 的 ${N_{d1}}$ 近邻个体的密度. $r_2^i$ 是从 $\{ 1,2, \cdots , $ $NP\} /\{ i,r_1^p\}$ 中生成随机整数, 差分向量的第二项 $x'_{r_2^i,n}$ 是从 ${x_{r_2^i,n}}$ 的 ${N_{d2}}$ 近邻中随机选取, ${N_{d1}}$ 和 ${N_{d2}} \in \{ 1,2, \cdots ,NP - 1\} $ 是用户指定的控制参数. 当 ${N_{d1}}$ 和 ${N_{d2}}$ 取值为 $NP - 1$ 时, 差分向量的选取方法就与标准DE的差分向量取法相同, 只是目标个体不是随机取得. 第二项的设计意图是生成绝对接近孤立个体的实验个体. ${F_1}$ 是比例因子.

3.2 邻域变异算子

当 ${x_{i,n}}$ 是 ${x_{i,n}}$ 的 ${N_{d1}}$ 邻域内密度最大的个体时, $find(i) = \left\{ {{p^{\rm near}}(j) < p(i)\left| {j = 1,2, \cdots ,{N_d}_1} \right.} \right\}$ 为空, 此时上述差分算子将会失效, 这种情况下我们使用如下邻域变异算子来解决困境, 变异运算符如下:

${v_i} = x_{r_1^i,n}^{\rm near} + {F_2} \cdot \left( {x'_{r_2^i,n} - x'_{r_3^i,n}} \right)$

(7)

其中, $x_{r_1^i,n}^{\rm near}$ 是在 ${x_{i,n}}$ 的 ${N_{d1}}$ 近邻个体中随机选取的第 $r_1^i$ 个个体, $r_1^i \in \{1,2, \cdots ,{N_{d1}}\} $ . $x'_{r_2^i,n}$ 和 $x'_{r_3^i,n}$ 是从 ${x_{i,n}}$ 的 ${N_{d3}}$ 近邻中随机选取, 且 $x_{r_1^i,n}^{\rm near}$ 、 $x'_{r_2^i,n}$ 和 $x'_{r_3^i,n}$ 互不相同, ${N_{d3}} \in \{ 1,2, \cdots , NP - 1\} $ 是用户指定的控制参数. ${N_{d3}} = NP - 1$ 的情况与标准DE的差分向量取法相同. ${F_2}$ 是比例因子.

3.3 改进的变异算子

如图1所示^[25], 图1(a)为邻域变异算子的行为特征, 图1(b)为基于孤立个体的变异算子的行为特征. 基于孤立个体的变异算子可以促使种群个体向孤立个体附近迁移, 提高算法的多模态开发能力, 而邻域变异算子只在小生境内进行, 避免差分进化的贪婪原则带来的错误替换, 提高算法的收敛性.

将以上两种变异操作结合形成的改进的变异算子描述如下:

$ {v_i} = \left\{ {\begin{array}{*{20}{l}} {x_{r_1^p,n}^{\rm near} + {F_1} \cdot \left( {{x_{r_2^i,n}} - x'_{r_2^i,n}} \right)},&{find(i){\text{非空}}}\\ {x_{r_1^i,n}^{\rm near} + {F_2} \cdot \left( {x'_{r_2^i,n} - x'_{r_3^i,n}} \right)},&{\rm otherwise} \end{array}} \right.$

(8)

随着种群的进化, $\left\{ {{p^{\rm near}}(j)\left| {j = 1,2, \cdots ,{N_d}_1} \right.} \right\}$ 的值会趋于相等, $find(i)$ 为空的情况增多, 基于孤立个体的变异算子的使用率下降, 邻域变异算子的使用率提升, 进而实现算法从探索阶段到收敛阶段的转变, 平衡算法的探索与收敛能力.

LDPDE的算法过程的伪代码的在算法2给出.

算法2. 基于邻域低密度个体的差分进化算法(LDPDE)

输入: 目标函数(最小值)f(x); 比例因子F; 交叉率Cr; 种群大小NP; 最大计算次数MaxFEs; 邻域大小 $ \scriptstyle{N}_{d1}, {N}_{d2}, {N}_{d3}$

1)　随机初始化种群 $\scriptstyle{X_1} = [{x_{1,1}},{x_{2,1}}, \cdots ,{x_{NP,1}}]$ ;

2)　 $\scriptstyle n = 0;$

3)　 $\scriptstyle{\rm{while}}\;FEs < {\rm{ = }}MaxFEs\;{\rm{do}}$

4)　　 $\scriptstyle n = n + 1;$

5)　 $\scriptstyle{\rm{for}}\;i = 1, \cdots ,NP\;{\rm{do}}$

6)　　 $\scriptstyle{d_{i,i}} = 0;$

7)　　 $\scriptstyle{\rm{for}}\;j = i + 1, \cdots ,NP\;{\rm{do}}$

8)　　　 $\scriptstyle{d_{i,j}} = {d_{j,i}} = {\left\| {{x_{i,n}} - {x_{j,n}}} \right\|_2};$

9)　　 $\scriptstyle{\rm{end}}\;{\rm{for}}$

10)　 $\scriptstyle{\rm{end}}\;{\rm{for}}$

11)　 $\scriptstyle{\sigma '}{\rm{ = 3}} \cdot {\sqrt 2 ^{ - 1}}\mathop {\arg \min }\limits_\sigma H\left( \sigma \right);$

12)　 $\scriptstyle{\rm{for}}\;i = 1, \cdots ,NP\;{\rm{do}}$

13)　　 $\scriptstyle\rho (i) = \sum\limits_{j \in {I_S}\backslash \{ i\} } {\exp \left( { - {{\left( {\frac{{{d_{ij}}}}{{{d_c}}}} \right)}^2}} \right)} ;$

14)　 $\scriptstyle{\rm{end}}\;{\rm{for}}$

15)　 $\scriptstyle{\rm{for}}\;i = 1, \cdots ,NP\;{\rm{do}}$

16)　　 $\scriptstyle{v_i} = \left\{ \begin{array}{l} x_{r_1^p,n}^{\rm near} + \scriptstyle{F_1} \cdot \left( {{x_{r_2^i,n}} - x'_{r_2^i,n}} \right),{\kern 1pt} {\kern 1pt} {\kern 1pt} find(i){\text{非空}}\\ x_{r_1^i,n}^{\rm near} + \scriptstyle{F_2} \cdot \left( {x'_{r_2^i,n} - x'_{r_3^i,n}} \right),{\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{otherwise}} \end{array} \right.$

17)　　 $\scriptstyle u_i^j = \left\{ {\begin{array}{*{20}{l}} \scriptstyle{v_i^j},&\scriptstyle{rand < Cr \vee j = {j_{rand}}}\\ \scriptstyle{x_{i,n}^j},&\scriptstyle{\rm otherwise} \end{array}} \right.$

18)　 $\scriptstyle{\rm{end}}\;{\rm{for}}$

19)　 $\scriptstyle{\rm{for}}\;i = 1, \cdots ,NP\;{\rm{do}}$

20)　　 $\scriptstyle{x_{i,n + 1}} = \left\{ {\begin{array}{*{20}{c}} {\scriptstyle{u_i}},&\scriptstyle{f({u_i}) \ge f({x_{i,n}})} \\ {\scriptstyle{x_{i,n}}},&\scriptstyle{f({u_i}) < f({x_{i,n}})} \end{array}} \right.$

21)　 $\scriptstyle{\rm{end}}\;{\rm{for}}$

22) $\scriptstyle{\rm{end}}\;{\rm{for}}$

23) 输出 $\scriptstyle{X_{MaxIt}}$ 中每个小生境中最优个体.

4 实验与讨论 4.1 测试函数

本文采用了CEC2013测试套件^[26]中所有20种常用的多模态测试函数来评估LDPDE的性能, 该测试套件中的测试函数具有各种不同的特征, 这使实验更加全面且令人信服. 下面对这20个基准测试函数作简要说明.

F1: Five-Uneven-Peak Trap(1D), $x \in [0,30]$ . 全局最优点数量为2.

$F1(x) = \left\{ {\begin{array}{*{20}{l}} {80(2.5 - x)},&{0 \le x < 2.5} \\ {64(x - 2.5)},&{2.5 \le x < 5.0} \\ {64(7.5 - x)},&{5.0 \le x < 7.5} \\ {28(x - 7.5)},&{7.5 \le x < 12.5} \\ {28(17.5 - x)},&{12.5 \le x < 17.5} \\ {32(x - 17.5)},&{17.5 \le x < 22.5} \\ {32(27.5 - x)},&{22.5 \le x < 27.5} \\ {80(x - 27.5)},&{27.5 \le x \le 30} \end{array}} \right.$

F2: Equal Maxima(1D), $x \in [0,1]$ . 全局最优点数量为5.

${F_2}(x) = {\sin ^6}(5\pi x)$

F3: Uneven Decreasing Maxima(1D), $x \in [0,1]$ . 全局最优点数量为1.

$F3(x) = {\operatorname{e} ^{ - 2\log (2){{\left( {\textstyle\frac{{x - 0.08}}{{0.853}}} \right)}^2}}}{\sin ^6}\left( {5\pi \left( {{x^{{3 / 4}}} - 0.05} \right)} \right)$

F4: Himmelblau(2D), ${x_1},{x_2} \in [ - 6,6]$ . 全局最优点数量为4.

$F4({x_1},{x_2}) = 200 - {\left( {x_1^2 + {x_2} - 11} \right)^2} - {\left( {{x_1} + x_2^2 - 7} \right)^2}$

F5: Six-Hump Camel Back(2D), ${x_1} \in [ - 1.9,1.9]$ , ${x_2} \in [ - 1.1,1.1]$ . 全局最优点数量为2.

$F5\left( {{x_1},{x_2}} \right) = - 4\left[ {\left( {4 - 2.1x_1^2 + \frac{{x_1^4}}{3}} \right)x_1^2 + {x_1}{x_2} + \left( {4x_2^2 - 4} \right)x_2^2} \right]$

F6, F8: Shubert(2D, 3D), ${x_i} \in {[ - 10,10]^D}$ , $i = 1, 2, \cdots, D$ . 全局最优点数量分别为18和81.

$F6,8\left( {\overrightarrow x } \right) = - \prod\nolimits_{i = 1}^D {\sum\nolimits_{j = 1}^5 {j\cos \left[ {(j + 1){x_i} + j} \right]} } $

F7, F9: Vincent(2D, 3D), ${x_i} \in {[0.25,10]^D}$ , $i = 1, 2, \cdots, D$ . 全局最优点数量分别为36和216.

$F7,9\left( {\overrightarrow x } \right) = \frac{1}{D}\sum\nolimits_{i = 1}^D {\sin (10\log ({x_i}} ))$

F10: Modified Rastrigin-All Global Optima(2D), ${x_i} \in {[0,1]^D},i = 1,2, \cdots, D$ . 全局最优点数量为12.

$F10\left( {\overrightarrow x } \right) = - \sum\limits_{i = 1}^D {(10 + 9\cos (2\pi {k_i}} {x_i}))$

其中, $ {k_1} = 3,\;{k_2} = 4$ .

剩下的10个函数为4个复合函数在不同维度大小的情况, 把4个函数简称为 $CF1, CF2, CF3$ 和 $CF4$ , 定义域均为 ${x_i} \in {[ - 5,5]^D},i = 1,2, \cdots, D$ . 复合函数的具体定义可以参考文献[26].

F11: CF1(2D). 全局最优点数量为6.

F12: CF2(2D). 全局最优点数量为8.

F13, F14, F16, F18: CF3(2D, 3D, 5D, 10D). 全局最优点数量为6.

F15, F17, F19, F20: CF4(3D, 5D, 10D, 20 D). 全局最优点数量为8.

将LDPDE与几种基于DE的多模态算法进行比较, 包括CDE算法, SDE算法, NCDE算法, NSDE算法, LoICDE算法, LoISDE算法, PNPCDE算法, Fast-NCDE算法和MSTDE算法. 这些算法横跨从2004年到2019年的时间间隔. 此外, 为了具有可比性, 所有对比算法的参数配置都与原始论文中的设置相同.

4.2 参数设置

LDPDE中的放大系数 ${F_1}$ 和 ${F_2}$ 分别设置为0.9和0.5, 交叉速率Cr设置为0.9, ${N_{d2}}$ 和 ${N_{d3}}$ 分别为5和15. 针对不同的函数参数 ${N_{d1}}$ 、种群规模N和最大计算次数MaxFEs设置如表1所示.

LDPDE中的种群规模、最大计算次数MaxFEs和比较算法的结果参考自文献[24]. 所有的结果都是在同一测试套件中使用相同的MaxFEs下得到的, 每种算法均运行51次以进行统计并避免随机性.

对于给定的MaxFEs在精度水平 $\varepsilon = {10^{ - 4}}$ 下, 使用峰值比(Peak Ratio, PR)和成功率(Success Ratio, SR)评估算法的性能. 峰值比为找到的全局最优解个数与所有全局最优解数之比, 成功率为所有全局最优解被找到次数与实验总次数之比. PR和SR均为0到1.0之间的实数, 数值越大说明算法效果越好. 当PR和SR均为1.0时说明算法每次都能找到函数所有的最优解.

4.3 结果与讨论

表2列出了LDPDE与其他多模态算法在F1–F20上PR和SR的详细比较结果. 为了结果清晰, 最佳PR果用黑体标出. 符号"+"、"−"和" $ \approx $ "分别表示LDPDE的性能“显著优于”, “显著低于”和“与对比算法相当”. 以CDE算法为例, 本文算法在13个函数上优于CDE算法, 0个低于CDE算法, 7个与CDE算法结果相当.

从表2可以看到LDPDE在所有函数上都表现很好. 对于简单函数 $F1 - F5$ 和具有众多全局最优值的函数 $F6 - F10$ , LDPDE除了对于具有216个全局最优点的 $F9$ 之外的其它九个函数的 $PR$ 值全部达到了 $1.0$ , 也就是说LDPDE算法在这九个测试函数上每次都能找到函数所有的最优解, 虽然 $F9$ 的 $PR$ 值只有 $0.587$ , 但也明显优于于其它算法. 对于最后的十个高度复杂多模态函数 $F11 - F20$ (其中 $F11 - F15$ 为低维, $F16 - F20$ 为高维), LDPDE的性能几乎处于绝对的优势地位, 只有少数几个算法在一到两个函数可以与本文算法性能相当, 这进一步验证了LDPDE在解决高度复杂的MMOPs方面的可行性和有效性.

多模态函数 $F1 - F20$ 的收敛曲线如图2(a)–图2(d)所示, 目标函数误差值为每个函数运行51次所得每一代最小值的平均值与函数极值之差的绝对值, 为方便观察, 将纵坐标取以 $10$ 为底的对数(值为 $0$ 时曲线未画出). 图2(a)中函数 $F1$ 的曲线极短, 这是由于 $F1$ 函数简单, 算法在很少的进化代数就计算得出最优函数值导致的. 而函数 $F3$ 的计算精度达到 ${10^{ - 7}}$ 之后很难继续改进. 其他18个函数收敛曲线呈现明显的收敛趋势, 虽然随着函数复杂程度的提高收敛速度减慢, 但收敛趋势稳定, 收敛精度也都能达到 ${10^{ - 18}}$ , 这也体现出本文算法在高维复杂多模态函数优化上的优势.

总之, LDPDE在所有20个函数上与CDE, SDE, NCDE, NSDE, LIPS, LoICDE, LoISDE, PNPCDE, self-CCDE, self-CSDE, fast-NCDE和MSTDE算法相比 $PR$ 值都优于或相当于对比算法. 收敛性分析结果表明, LDPDE可以在搜索与收敛之间找到良好的平衡, 具有解决MMOPs的潜力.

5 结论与展望

针对多模态优化问题, 本文提出了一种基于邻域低密度个体的差分进化算法LDPDE, 它可以通过邻域范围内个体的密度变化达到算法探索与收敛之间的平衡, 有效提升了算法的可靠性和收敛速度, 结合新提出的DE/low-density/1变异算子, 使得算法在探索阶段可以寻找尽可能多的有效个体. 在CEC2013多模态基准测试的实验结果表明, LDPDE对比其它多种基于DE的多模态优化算法具有更好的性能, 显示了LDPDE在求解多模态优化问题上的优势.