闵 涛, 杨 胜
(西安理工大学 理学院应用数学系, 西安 710054)通讯作者: 闵 涛摘 要: 针对多模态优化问题(MultiModal Optimization Problems, MMOPs)的求解, 提出了一种基于邻域低密度个体的差分进化算法. 该算法在每一代, 首先使用密度峰值聚类的方法求得每一个个体的密度, 然后, 将当前个体邻域范围内密度更低的个体作为变异算子的基向量, 随着种的进化, 算法将会自动从探索阶段转化为收敛阶段, 进而平衡算法的探索与收敛能力. 将提出的算法应用于CEC2013多模态基准测试函数并进行仿真实验, 结果表明本文算法在评价指标峰值比和稳定性上与其它基于差分进化的多模态优化算法相比具有明显的优势, 并随着测试函数的维度与复杂性的增大, 优势就更加明显, 其性能优于许多现有的基于差分进化的多模态优化算法.关键词: 差分进化; 邻域突变; 多模态; 优化问题; 密度
引用格式: 闵涛，杨胜.多模态优化问题的邻域低密度个体差分进化算法.计算机系统应用,2021,30(3):117–125. /1003-3254/7824.html
Differential Evolution Algorithm Based on Low-Density Individual in Neighborhood for Multimodal Optimization Problem
MIN Tao, YANG Sheng
(School of Science, Xi’an University of Technology, Xi’an 710054, China)
Abstract : A differential evolution algorithm based on low-density individuals in the neighborhood is proposed to solve MultiModal Optimization Problems (MMOPs). In each generation, the algorithm first relies on density peak clustering to find the density of each individual and then take the lower-density individuals in the neighborhood of the current individual as a base vector of the mutation operator. As the population evolves, the algorithm will automatically transform from the exploration st
age to the convergence stage, thereby balancing its exploration and convergence capabilities. The proposed algorithm is applied to the CEC2013 multimodal benchmark function for simulation experiments. Results demonstrate that the algorithm has obvious advantages over other multimodal optimization algorithms based on differential evolution in evaluating the peak ratios and stability of indexes, and the advantage is more distinct with the increasing dimensionality and complexity of the test function. It behaves better than many existing multimodal optimization algorithms based on differential evolution.
Key words : differential evolution; neighborhood mutation; multimodal; optimization problem; density
科学与工程领域的大多数优化问题本质上都是“多模态”的, 这类问题被称为多模态优化问题, 其特点
是目标函数同时具有多个全局最优解或局部最优解.传统使用的求解方法在求解MMOPs 时须反复计算多
计算机系统应用 ISSN 1003-3254, CODEN CSAOBN
E-mail: Computer Systems & Applications,2021,30(3):117−125 [doi: 10.15888/jki.csa.007824] ©中国科学院软件研究所版权所有.
熟人作案
Tel: +86-10-62661041
① 基金项目: 国家自然科学基金 (51679186); 陕西省自然科学基础研究计划(2019JM-284)
Foundation item: National Natural Science Foundation of China (51679186); Fundamental Research Program of Natural Science of Shaanxi Province (2019JM-284)
收稿时间: 2020-07-10; 修改时间: 2020-08-11; 采用时间: 2020-08-21; csa 在线出版时间: 2021-03-03
117
次, 才有可能到不同的最优解, 这样既费时又费力.因此, 寻可行有效的求解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 差分进化算法
考虑优化模型:
X =[x 1,x 2,···,x n ]n Ω∈R n f (·)其中, 为维向量, 为求解区域,
为目标函数.
交聘差分进化算法是一种简单有效的全局优化启发式算法. 与其他进化算法类似, DE 有4个步骤: 初始化、变异、交叉和选择. 标准的DE 算法过程如下:
(1) 初始化
首先, DE 从最小和最大界限约束的搜索空间内对个体进行均匀随机化, 可以表示为:
x j
i ,n x i ,n x j max x j
min j [1,NP ][1,D ]rand (0,1)其中, 表示第n 代第i 个个体在第j 个维度上的值. 和表示第个变量的上下边界. 下标i 和j 在和范围内, 其中NP 表示种大小, D 表示问题维度. 表示从0到1生成均匀分布的随机值.
(2) 变异
v
初始化后, 从当前种中随机选择的个体经过变异算子产生突变个体. 在标准DE 中, 使用以下运算方法:
r i 1,r i 2r i 3
{1,2,···,NP }/{i }其中, 和是从中生成的互斥整数,F 是比例因子, 一般取值为0.1到0.9之间.
(3) 交叉
x j
i ,n v i u i (1−Cr )u
交叉算子通过重新组合目标个体和突变个体
来生成实验个体. 在标准DE 中, 使用了两种类型的
算子, 即指数和二项式. 在本文研究中, 我们使用二项式运算符. 在二项式运算符中, 实验个体中的每个元素都继承用户指定的概率为Cr 的突变个体的值, 并以
的概率继承目标个体的值. 实验个体为:
j rand ∈{1,2,···,NP }u i v i 其中, 是随机选择的索引, 可确保
至少继承突变个体中的至少一个分量.
(4) 选择
x i ,n +1选择运算符确定目标或实验个体是否进入到下一代. 如果新的实验个体的函数值等于或小于目标个体的函数值, 它将替换相应的目标个体. 下一代中的目标向量为:
最后, DE 继续执行变异、交叉和选择运算符, 直到满足终止条件为止. 算法1中以伪代码的形式给出了标准DE 的算法过程.
民兵誓词算法1. 标准差分进化算法(DE)
输入: 目标函数(最小值)f (x ); 比例因子F ; 交叉率Cr ; 种大小NP ；进化代数MaxIt .
X 1=[x 1,1,x 2,1,···,x NP ,1]1) 随机初始化种;for n =1,···,MaxIt do 2) for i =1,···,NP do
3) v i =x r i 1
,n +F ·(
x r i 2,n −x r i 3
,n ),
4) u j i = v j i ,
rand <Cr ∨j =j rand x j i ,n
,otherwise
5) 计算机系统应用
2021 年 第 30 卷 第 3 期
118
end for 6) for i =1,···,NP do
7) x i ,n +1= u i ,
f (u i )≥f (x i ,n )x i ,n ,f (u i )<f (x i ,n )
8) end for
9) end for
10) X MaxIt f (x )11) 输出中使得最大的个体.
2 准备工作
2.1 密度峰值聚类
x (i )ρ(i )σ(i )密度峰值聚类[19]是一种简单有效的快速聚类方法, 由Rodriguez 和Laio [20]通过发现潜在簇的密度峰值提出. 对于每个数据点, 该算法都会计算其局部密度以及与距其最近密度更大点的距离, 由此可以得到每个数据点的孤立性. 以下介绍密度峰值聚类的原理.
x (i )数据点的局部密度的定义如下所示:
d i j d c d c x (i ),i =1,2,···,n x (i )ψ(i )其中, 是第i 个和第j 个数据点之间的距离, 是截止距离. 对于截止距离, 原始论文没有提供正确设置的有效方法. 在文献[21]中, 作者提出了一种基于潜在熵的方法, 可以根据数据域自动设置. 对于一个数据集
, 计算第i 个数据点的电势 :
则熵H 为:
其中, 归一化因子z 为:
σσ′d c d c min {∥x (i )−x (j )∥}max {∥x (i )−x (j )∥}σd c =3·
√2−1σ′现在只要到使得H 值最小的, 记为, 即可得到截止距离. 显然, 的值一定处于和之间, 对于简单的一维优化问题本文使用黄金分割法求得, 最后将临界值设置为.
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
2021 年 第 30 卷 第 3 期
计算机系统应用
119
变异算子, 称为DE/low-density/1. 该算子的主要特征是它在当前个体邻域中随机选择密度低于当前个体的个体作为变异算子的目标个体, 因此, 目标个体可以被选择变异算子迁移到隔离区域. 在典型的小生境方法中, 同一山谷中的个体倾向于通过在山谷中下降聚集在一起. 而在本文提出的方法中, 个体积极地迁移到其他山谷. DE/low-densit/1中使用的变异算子描述如下:
r p
1{p near (j )<p (i )|j =1,2,···,N d 1}p near x i ,n N d 1r i 2
{1,2,···,NP }/{i ,r p
1}x ′r i 2
,n
x r i 2
,n N d 2N d 1N d 2∈{1,2,···,NP −1}
N d 1N d 2NP −1F 1其中, 是从中生成随
机整数, 是的近邻个体的密度. 是从中生成随机整数, 差分向量的第二项是从
的近邻中随机选取, 和是用户指定的控制参数. 当和取值为时，差分向量的选取方法就与标准DE 的差分向量取法相同, 只是目标个体不是随机取得. 第二项的设计意图是生成绝对接近孤立个体的实验个体. 是比例因子.
3.2 邻域变异算子同业竞争
x i ,n x i ,n N d 1f ind (i )=
{p near (j )<p (i )|j =1,2,···,N d 1}当是的邻域内密度最大的个体时, 为空, 此时上述差分算
子将会失效, 这种情况下我们使用如下邻域变异算子来解决困境, 变异运算符如下:
x near r i 1,n
x i ,n N d 1r i 1r i 1∈{1,2,···,N d 1}x ′r i 2,n x ′r i 3,n x i ,n N d 3x near r i 1,n x ′r i 2,n x ′r i 3
,n N d 3∈{1,2,···,NP −1}N d 3=NP −1F 2其中, 是在的近邻个体中随机选取的第个
个体, . 和是从的近邻中
随机选取, 且、和互不相同, 是用户指定的控制参数. 的情况与nifeshe
标准DE 的差分向量取法相同. 是比例因子.
3.3 改进的变异算子
如图1所示[25], 图1(a)为邻域变异算子的行为特征, 图1(b)为基于孤立个体的变异算子的行为特征. 基于
孤立个体的变异算子可以促使种个体向孤立个体附近迁移, 提高算法的多模态开发能力, 而邻域变异算子只在小生境内进行, 避免差分进化的贪婪原则带来的错误替换, 提高算法的收敛性.
将以上两种变异操作结合形成的改进的变异算子描述如下:
{p near (j )|j =1,2,···,N d 1}f ind (i )随着种的进化, 的值会趋于相等, 为空的情况增多, 基于孤立个体的变异算子的使用率下降, 邻域变异算子的使用率提升, 进而实现算法从探索阶段到收敛阶段的转变, 平衡算法的探索与收敛能力.
(a) 邻域变异算子
(b) 孤立个体变异算子
(x ))
x x
图1 两种变异算子的行为特征
LDPDE 的算法过程的伪代码的在算法2给出.
算法2. 基于邻域低密度个体的差分进化算法(LDPDE)
N d 1,N d 2,N d 3输入: 目标函数(最小值)f (x ); 比例因子F ; 交叉率Cr ; 种大小NP ；最大计算次数MaxFEs ; 邻域大小X 1=[x 1,1,x 2,1,···,x NP ,1]1) 随机初始化种;n =0;
2) while FEs <=MaxFEs do 3) n =n +1;
4) for i =1,···,NP do 5) d i ,i =0;
6) for j =i +1,···,NP do
7) d i ,j =d j ,i =∥x i ,n −x j ,n ∥2;8) end for 9) end for
10) σ′=3·√
2−1argmin σ
H (σ);11) for i =1,···,NP do 12) ρ(i )=
∑
j ∈I S \{i }
exp (−(d i j
d c )2)
;
13) end for
14) for i =1,···,NP do
15) v i =
x near r p 1,n +F 1· x r i 2,n −x ′r i 2,n ,f ind (i )非空x near r i 1,n +F 2· x ′r i 2,n −x ′r i 3,n
,otherwise 16) u j i =
v j i ,
rand <Cr ∨j =j rand x j i ,n ,otherwise 17) end for
18) for i =1,···,NP do
19) x i ,n +1= u i ,f (u i )≥f (x i ,n )x i ,n ,f (u i )<f (x i ,n )
20) end for 21) end for
22) X MaxIt 23) 输出中每个小生境中最优个体.
4 实验与讨论
4.1 测试函数
本文采用了CEC2013测试套件[26]中所有20种常
计算机系统应用
2021 年 第 30 卷 第 3 期
120
用的多模态测试函数来评估LDPDE 的性能, 该测试套件中的测试函数具有各种不同的特征, 这使实验更加全面且令人信服. 下面对这20个基准测试函数作简要说明.
x ∈[0,30]F 1: Five-Uneven-Peak Trap(1D), . 全局最优点数量为2.
x ∈[0,1]F 2: Equal Maxima(1D), . 全局最优点数量为5.
x ∈[0,1]F 3: Uneven Decreasing Maxima(1D), . 全局最优点数量为1.
x 1,x 2∈[−6,6]F 4: Himmelblau(2D), . 全局最优点数量为4.
x 1∈[−
1.9,1.9]x 2∈[−1.1,1.1]F 5: Six-Hump Camel Back(2D), ,
. 全局最优点数量为2.
x i ∈[−10,10]D i =1,
2,···,D F 6, F 8: Shubert(2D, 3D), , . 全局最优点数量分别为18和81.
x i ∈[0.25,10]D i =1,
2,···,D F 7, F 9: Vincent(2D, 3D), , . 全局最优点数量分别为36和216.
x i ∈[0,1]D ,i =1,2,···,D F 10: Modified Rastrigin-All Global Optima(2D),. 全局最优点数量为12.
k 1=3,k 2=4其中, .
CF 1,CF 2,CF 3CF 4x i ∈[−5,5]D ,i =1,2,···,D 剩下的10个函数为4个复合函数在不同维度大小的情况, 把4个函数简称为和, 定义域均为. 复合函数的具体定
义可以参考文献[26].
F 11: CF 1(2D). 全局最优点数量为6.F 12: CF 2(2D). 全局最优点数量为8.
F 13, F 14, F 16, F 18: CF 3(2D, 3D, 5D, 10D). 全局最优点数量为6.
F 15, F 17, F 19, F 20: CF 4(3D, 5D, 10D, 20 D). 全局最优点数量为8.
将LDPDE 与几种基于DE 的多模态算法进行比较, 包括CDE 算法, SDE 算法, NCDE 算法, NSDE 算法, LoICDE 算法, LoISDE 算法, PNPCDE 算法, Fast-NCDE 算法和MSTDE 算法. 这些算法横跨从2004年到2019年的时间间隔. 此外, 为了具有可比性, 所有对比算法的参数配置都与原始论文中的设置相同.
小雪花的泪
4.2 参数设置
F 1F 2N d 2N d 3N d 1LDPDE 中的放大系数和分别设置为0.9和0.5, 交叉速率Cr 设置为0.9, 和分别为5和15. 针对不同的函数参数、种规模N 和最大计算次数MaxFEs 设置如表1所示.
表1 参数设置
函数编号
N d 1
N MaxFEs F 1–F 55
805e+4F 61001002e+5F 73003002e+5F 8–F 93003004e+5F 1051002e+5F 11–F 1352002e+5F 14–F 1752004e+5F 18–F 20
2
2004e+5
LDPDE 中的种规模、最大计算次数MaxFEs 和比较算法的结果参考自文献[24]. 所有的结果都是在
同一测试套件中使用相同的MaxFEs 下得到的, 每种算法均运行51次以进行统计并避免随机性.
ε=10−4对于给定的MaxFEs 在精度水平下, 使用峰值比(Peak Ratio, PR)和成功率(Success Ratio,SR)评估算法的性能. 峰值比为到的全局最优解个数与所有全局最优解数之比, 成功率为所有全局最优解被到次数与实验总次数之比. PR 和SR 均为0到1.0之间的实数, 数值越大说明算法效果越好. 当PR 和SR 均为1.0时说明算法每次都能到函数所有的最优解.
4.3 结果与讨论
表2列出了LDPDE 与其他多模态算法在F 1–F 20上PR 和SR 的详细比较结果. 为了结果清晰, 最佳PR
2021 年 第 30 卷 第 3 期
计算机系统应用
121
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议