基于密度聚类的多模态多目标优化算法

王莉利 ,  张海洋 ,  高新成

吉林大学学报(工学版) ›› 2026, Vol. 56 ›› Issue (8) : 2210 -2218.

PDF (1206KB)
吉林大学学报(工学版) ›› 2026, Vol. 56 ›› Issue (8) : 2210 -2218. DOI: 10.13229/j.cnki.jdxbgxb.20250006
计算机科学与技术

基于密度聚类的多模态多目标优化算法

作者信息 +

Multi-modal multi-objective optimization algorithm based on density clustering

Author information +
文章历史 +
PDF (1234K)

摘要

针对多模态多目标优化算法存在等价解分布不均和多样性收敛性方面的问题,提出基于密度聚类的多模态多目标优化算法(MMO_DBSCAN_BWO)。首先,混沌映射初始化种群,使个体均匀分布于决策空间,增强其全局搜索能力;其次,基于不同层级的非支配解集使用密度聚类算法生成小生境,识别出游离个体,提出层级进化策略和同级环形拓扑进化策略,加强搜索能力;然后,引入档案机制,保留个体历史最优解;最后,基于特殊拥挤距离非支配排序和基于欧氏距离的截断档案机制选取分布较为均匀的Pareto最优解。通过在2020年CEC多模态多目标测试函数上进行测试,并与3种算法进行对比实验,结果表明,MMO_DBSCAN_BWO的总体性能优于对比算法。同时,将算法应用于JavaScript恶意代码检测图模型超参数优化问题,模型准确率得到进一步提升,达到99.3%,证明了算法的有效性。

Abstract

In order to solve the problems of unequal distribution and convergence of the equivalent solutions obtained by the multi-modal multi-objective optimization algorithm, a multi-modal multi-objective optimization algorithm based on density clustering (MMO_DBSCAN_BWO) is proposed. Firstly, the chaotic mapping initializes the population, makes the individuals evenly distributed in the decision space, and enhances its global search ability. Secondly, density clustering algorithm is used to generate niches based on non-dominated solution sets of different levels, identify stray individuals, and propose hierarchical evolutionary strategies and hierarchical ring topological evolutionary strategies to enhance search ability. Then, the archival mechanism is introduced to preserve the optimal solution of individual history. Finally, the optimal Pareto solution with uniform distribution is selected based on special congestion distance non-dominated sorting and Euclidean distance truncation mechanism. The overall performance of MMO_DBSCAN_BWO is better than that of the comparison algorithm by testing on the 2020 CEC multimodal multiobjective test function and comparing with the three algorithms. At the same time, the algorithm is applied to the hyperparameter optimization problem of JavaScript malicious code detection graph model, and the accuracy of the model is further improved, reaching 99.3%, which proves the effectiveness of the algorithm.

Graphical abstract

关键词

多模态多目标优化 / 白鲸优化 / 密度聚类 / 图神经网络

Key words

multimodal multi-objective optimization / beluga optimization / density clustering / graph neural networks

引用本文

引用格式 ▾
王莉利,张海洋,高新成. 基于密度聚类的多模态多目标优化算法[J]. 吉林大学学报(工学版), 2026, 56(8): 2210-2218 DOI:10.13229/j.cnki.jdxbgxb.20250006

登录浏览全文

4963

注册一个新账户 忘记密码

0 引 言

多模态多目标优化问题(Multimodal multiobjective optimization problem,MMOP) [1,2]是其决策空间中存在两个或两个以上帕累托最优解集(Pareto-optimal sets,PSs)对应目标空间中同一个Pareto前沿。如何获取决策空间尽可能多的PSs,提高决策空间的多样性以及算法的搜索能力一直是多模态多目标优化问题存在的难点[3]。

Yue等[4]提出了环形拓扑和特殊拥挤距离的多目标粒子群优化算法,通过环形拓扑结构限制种群内的信息传递速度,形成稳定的小生境;高海军等[5]提出了一种星型结构的多目标粒子群算法用于求解多模态多目标问题;章恩泽等[6]提出了基于环形拓扑结构和动态领域的多模态多目标优化算法;顾清华等[3]提出了一种融合聚类和小生境搜索的多模态多目标优化算法,利用基于聚类的特殊拥挤距离非支配排序方法初始化种群,引入自适应物种形成策略生成稳定的小生境;李占山等[7]提出了一种基于自适应搜索的多模态多目标优化算法。传统基于聚类的多模态多目标优化算法一般采用k-means[8]聚类的方式,然而,k-means聚类算法需要预先指定k值,且对噪声点异常点敏感,并不适用于形状复杂的簇。基于这些问题,本文提出了一种基于密度聚类的多模态多目标优化算法。

随着互联网技术的不断发展,网络安全事件频发,JavaScript(JS)恶意代码检测已成为网络安全领域主要研究课题之一。在现有异构图JS恶意代码检测模型的基础上,结合本文提出的多模态多目标优化算法,重点解决模型超参数选取问题。针对上述问题及研究目的,本文主要贡献如下:①提出了一种基于密度聚类的多模态多目标优化算法,有效识别出不规则小生境,增强种群搜索和进化能力;②提出了一种基于支配等级的层级进化策略和同级环形拓扑进化策略,增强种群的局部搜索能力和全局搜索能力,更好地发现最优解集。

1 相关内容

1.1 多模态多目标优化算法

多目标优化问题[2]是指包含两个或两个以上的待优化目标函数,且目标函数之间存在一定的相互制约,所得结果为一个最优解集。多目标优化问题数学公式定义为:

F(x)={fi(x)|i=1,2,⋯,m}

式中:x=(x1,x2,⋯,xn)为可行域S中的n维变量;S为n维实数域的一个子集;fi(x)为第i个目标函数;F()为所有目标函数的目标空间。

多模态是指优化问题中存在多个近似最优解的情况,目标空间中的一个目标值在决策空间中有两个及以上的解与之对应,即两个以上的Pareto解集(PS1,PS2)对应同一个F(x)。

1.2 白鲸优化算法

白鲸优化算法是由Zhong等[9]于2022年提出的,相比于粒子群优化算法具有更好的搜索性能。算法通过模拟白鲸的3个阶段:游泳、觅食和“鲸鱼坠落”,实现种群的进化过程,游泳阶段注重于全局搜索,觅食阶段注重于局部搜索。

白鲸游泳行为数学模型如式(2)所示:

Xi,jT+1=Xi,pjT+(Xr,p1T-Xi,pjT)(1+r1)sin(2πr2),                 j=evenXi,jT+1=Xi,pjT+(Xr,p1T-Xi,pjT)(1+r1)cos(2πr2),                 j=odd

式中:Xi,jT+1为下一次迭代时,第i个个体在第j维上的位置;p为随机的另一个白鲸个体;r1、r2为在(0,1)内的随机数。

白鲸的局部开发阶段的灵感来自于白鲸的觅食,考虑最佳个体和其他个体对位置更新的影响,使用Levy飞行策略来增强收敛性,该阶段位置更新模型公式如下:

XiT+1=r3XbestT-r4XiT+C1⋅LF⋅(XrT-XiT)
C1=2×r4×(1-tT)
LF=0.05×u×σ|v|1/β
σ=(Γ(1+β)×sin(πβ/2)Γ((1+β)/2)×β×2(β-1)/2)1/β

式中:C1为随机跳跃度,用来衡量Levy飞行的强度;r3、r4为在(0,1)内的随机数;LF为飞行实际步长;u和v是正态随机数N(0,1);β为一个常数,一般取值1.5;σ为Levy分布的尺度因子;Γ(⋅)为Gamma函数。

在白鲸坠落行为中,使用白鲸当前位置和鲸落下坠的步长来建立的位置更新公式,如式(7)(8),鲸落概率如式(9),其会随着迭代次数的增加而不断减小。

XiT+1=r5XiT-r6XrT+r7Xstep
Xstep=(ub-lb)exp(-C2T/Tmax)
Wf=0.1-0.05T/Tmax

式中:r5、r6、r7为在(0,1)内的随机数;ub,lb分别为搜索区域的上、下界。

2 基于密度聚类的多模态多目标优化算法

为了更好地处理复杂形状的簇,提出了基于密度聚类的多模态多目标优化算法,称作MMO_DBSCAN_BWO算法,主要由混沌映射种群初始化、密度聚类生成小生境、小生境进化和排序选择等多个部分组成。

2.1 混沌映射初始化种群

从文献[10]中获得启发,为了让种群初始位置更加均匀分布在决策空间中,引入空间金字塔匹配(Spatial pyramid matching,SPM)混沌映射[11]策略应用于种群初始化阶段,加快算法收敛速度,提高全局搜索能力,公式如下:

x(t+1)=mod(x(t)η+μsin(πx(t))+r,1),0≤x(t)<ηmod(x(t)/η0.5-η+μsin(πx(t))+r,1),η≤x(t)<0.5mod((1-x(t))/η0.5-η+μsin(π(1-x(t)))+r,1),0.5≤x(t)<1-ηmod(1-x(t)η+μsin(π(1-x(t)))+r,1),1-η≤x(t)<1

2.2 密度聚类生成小生境

密度聚类算法[12]能有效识别复杂形状的簇,所以本文采用基于密度聚类算法生成小生境。密度聚类算法将同一支配层的白鲸个体分为核心点、边界点和噪声点。小生境示例图如图1所示。

2.3 小生境进化策略

小生境进化策略包括层级进化和同级环形拓扑进化两个部分,层级进化用于探索不同支配层之间的全局区域,从上一支配层中随机选取噪声群体或低密度小生境中个体作为领导个体,进而向其进化,从而形成或扩充小生境。同级环形拓扑进化又包括境间进化和境内进化,探索小生境之间的区域和小生境内低密度区域,概率发生白鲸个体的游泳行为、觅食行为或鲸落行为。小生境算法流程图如图2所示。

2.3.1 层级进化

层级进化实现低支配层级的白鲸个体向高支配层级个体的进化过程,随机从高支配层中的噪声群体和低密度小生境中选取领导个体,达到形成或扩展高支配层中低密度空间的种群规模。层级进化算法步骤如下:

输入:当前小生境current_island;上一层级小生境群the_upper_rank_islands;鲸落概率Whale_fall_pro;Whale_swim_pro游泳概率。

(1)首先,计算上一层级小生境群的平均小生境密度,将低于平均小生境密度的小生境个体添加到领导个体数组中。

(2)其次,遍历当前小生境中的每个白鲸个体,随机从领导个体数组中抽取一个领导个体,根据鲸落概率和游泳概率让白鲸个体发生游泳行为、觅食行为或鲸落行为,进而完成新种群的位置更新。

2.3.2 同级环形拓扑进化

针对最优支配层中的小生境采取同级环型拓扑进行进化,其由境间进化和境内进化两部分组成。境间进化是基于环形拓扑进化方法改进的,只允许高密度小生境内个体向相邻低密度小生境进化,增强小生境之间的相互交互关系,增强全局搜索能力,境内进化图如图3所示。

当一个白鲸个体发生境内进化时,为增强局部空间搜索能力,使个体在决策空间中更加均匀分散,避免大量的集中和堆积,与决策空间拥挤距离排序算法进行结合,从优于当前个体的种群中挑选领导个体,进而基于白鲸进化方法生成下一代个体。

2.4 特殊拥挤距离排序选择

使用文献[13]中提出的特殊拥挤距离(CSCD),综合考虑白鲸个体在决策空间和目标空间的拥挤度作为选择标准,进行排序选择后,得到下一代种群,CSCD计算公式为:

CSCDi=max(CDi,x,CDi,f)if(CDi,x>CDavg,x)or(CDi,f>CDavg,f)min(CDi,x,CDi,f)otherwise

式中:CDi,x和CDavg,x分别表示决策空间的拥挤距离和决策空间的平均拥挤距离;CDi,f和CDavg,f分别表示目标空间的拥挤距离和目标空间的平均拥挤距离。

2.5 基于欧氏距离的截断档案机制

循环迭代完成后,全局最优存档GBA一般存在远大于popSize种群个体规模的最优解集,为了从中获取固定数量的且在决策空间中均匀分布的解集,引入基于欧氏距离的截断档案机制[14]。公式如下:

F(i)=R(i)+D(i)
R(i)=∑j∈Pt,i≺jS(j)
S(i)=|{j|j∈Pt∧j≺i}|
D(i)=1σik+2

式中:R(i)为第i个个体的粗适应度值,表示所有支配个体i的个体j在种群中支配其他个体的数量的总和;S(i)为第i个个体的强度值,即个体i在种群中所支配的个体数量总和;D(i)为第i个个体对应的密度函数;σ为个体i到第k个个体的欧式距离,k为个体总数。

当个体间欧式距离越小,则D(i)越大,个体越密集。通过对每个个体的F(i)从小到大进行排序,选取前popSize个个体,作为最优解集。

2.6 算法流程

图4为将上述策略与白鲸优化算法进行结合,形成的MMO_DBSCAN_BWO算法流程图。

3 实验结果与分析

3.1 测试函数与对比算法

本文选用2020年CEC多模态多目标测试问题中的几个经典函数用于测试算法性能。测试函数列表如表1所示,包括函数名称,维度,目标数和等价解数。

为了比较本文提出的MMO_DBSCAN_BWO算法的性能,将其与DN-NSGAII[15],MO_Ring_PSO_SCD[4]、SS_MOPSO[16]进行对比实验。

3.2 评价指标

多模态多目标优化问题既要求目标空间的分布性能良好,又要保证找到决策空间更多的等价的PSs,因此本文采用了以下评价指标对所提算法进行评价。

3.2.1 Pareto解集逼近度

Pareto解集逼近度[17](PSP) 能反映真实Pareto解集与获取的解集之间的相似性,公式如下:

PSP=CRIGDX

式中:CR为算法求得的Pareto解集对真实解集的覆盖率;IGDX为求得的Pareto解集与真实解集之间的欧式距离;PSP越大则算法性能越好。

3.2.2 决策空间反世代距离

决策空间反世代距离[17](IGDX)公式如下所示:

IGDX(X)=∑y∈X*minx∈X{D(x,y)}|X*|

式中:D(x,y)为解x和解y的欧氏距离;X*为真实Pareto解集中的均匀采样;|X*|为集合X*中解的总个数。IGDX的值越小,表明解集的收敛性和多样性越好。

3.3 实验结果与分析

由于参考Pareto解集个数为400,所以所有算法种群规模和最大评估数分别设置为400和40000,在测试函数上独立运行10次,取不同算法评价指标运行10次后结果的平均值,如表2、表3所示。

实验结果表明,MMO_DBSCAN_BWO算法相比于DN_NSGAII、DN_NSGAII和SS_MOPSO算法在多个测试函数上取得较好的效果,在平均PSP指标上均有不同程度的提升,证明本文算法求解与真实的Pareto解集之间相似性更高,算法性能更好。同时,对应的平均IGDX指标也均有降低,证明本文算法求解的解集收敛性和多样性优于其他3种算法。表明MMO_DBSCAN_BWO算法能找到更多且均匀的全局最优解集。

4 基于图神经网络超参数优化问题的应用

使用基于密度聚类的多模态多目标优化算法解决JS恶意代码检测模型的超参数优化问题,探索其对提高模型的鲁棒性和泛化性方面的实际应用价值。

JavaScript[18]是一种轻量级解释型计算机语言,被广泛应用于Web应用程序,这也使JavaScript代码成为主要恶意攻击手段之一。针对这一背景,构建了一个图层级异构图注意力网络模型[19],模型结构如图5所示。

模型超参数主要包括节点特征向量维度、Word2Vec模型编码方式、Word2Vec模型窗口大小、隐藏神经元个数和注意力头数等。这些超参数的值在一定程度上会影响模型的最终效果,直观体现在模型的评价指标上。在常见分类评价指标中,精确率和召回率存在相互制约关系,且问题具有多模态的特性,是典型的多模态多目标优化问题。基于此,将模型超参数作为算法的决策空间,将召回率和精确率作为算法的目标空间。整体框架结构图如图6所示。

4.1 数据集与实验设置

从Alexa公布的排名网站收集正常样本,从Github和PhishTank等多个平台上获取恶意JS代码样本。最终获得数据集总样本数为9 875个,其中正常样本数为4 975个,恶意样本数为4 900个。将数据集按6∶2∶2比例划分为训练集、验证集和测试集。JS代码预处理流程如图7所示。

将模型超参数构成MMO_DBSCAN_BWO算法的决策空间,验证集的精确率和召回率作为算法的目标空间,最终算法求得一组超参数全局最优解集,解决模型超参数选取问题,进一步提高模型性能效果。其中,超参数设置如下,节点特征向量维度取值范围为[50,100,150,200,250,300]其中的一个值,Word2Vec模型编码方式取值范围[0,1]其中一个值,分别对应CBOW算法和skip-gram算法,窗口大小取值范围为[3,5,7,10]其中的一个值,隐藏神经元个数[10,256]之间的一个整数值,注意力头数为[1,10]之间的一个整数值。

4.2 实验结果与分析

从超参数全局最优解集中选取模型准确率最高的解集,再从中找出综合超参数值较小的解,作为最终的超参数全局最优解。两个异构图检测模型对比实验结果如表4和表5所示。

实验结果表明,融入本文多模态多目标优化算法选取的超参数中特征向量维度、隐藏神经元个数和注意力头数均低于常规超参数数值的同时,模型指标也得到提升,准确率提高了0.1%,F1分数提高了0.1%,AUC值提高了0.001 9。表明本文所提算法能够有效选择最优超参数,进一步提高模型性能,有效解决恶意JS代码检测问题,验证了基于密度聚类的多模态多目标优化算法求解模型超参数问题的有效性。

5 结束语

针对多模态多目标优化算法存在等价解分布不均和多样性收敛性方面的问题,提出了一种基于密度聚类的多模态多目标优化算法。该算法采用密度聚类算法能够有效识别复杂形状的小生境,提高对低密度空间个体的识别效果。提出层级进化策略和同级环形拓扑进化策略,基于白鲸进化方法,增强全局搜索能力和局部空间搜索能力。实验结果表明,MMO_DBSCAN_BWO算法可以有效解决多模态多目标优化问题。然而,上述算法并没有考虑局部最优解的情况,为了更好地适用于不同的应用领域,在后续工作中,将进一步改进层级进化策略和档案机制,保留局部最优解的解集。

参考文献

[1]

Qu B Y, Suganthan P N.Novel multimodal problems and differential evolution with ensemble of restricted tournament selection[C]//IEEE Congress on Evolutionary Computation, Barcelona, Spain, 2010: 1-7.

[2]

Deb K, Pratap A, Agarwal S, et al.A fast and elitist multiobjective genetic algorithm: NSGA-II[J].IEEE Transactions on Evolutionary Computation, 2002,6(2): 182-197.

[3]

顾清华, 唐慧, 李学现, 等.融合聚类和小生境搜索的多模态多目标优化算法[J].智能系统学报,2023,18(5):1127-1141.

[4]

Gu Qing-hua, Tang Hui, Li Xue-xian, et al. A multimodal multi-objective optimization algorithm integrating clustering and small habitat search[J]. Journal of Intelligent Systems,2023,18(5):1127-1141.

[5]

Yue C T, Qu B Y, Liang J. A Multiobjective particle swarm optimizer using ring topology for solving multimodal multiobjective problems[J].IEEE Transactions on Evolutionary Computation, 2018,22(5): 805-817.

[6]

高海军, 潘大志. 星型结构的多目标粒子群算法求解多模态多目标问题[J]. 计算机工程与科学, 2020,42(8): 1472-1481.

[7]

Gao Hai-jun, Pan Da-zhi. Star-structured multi-objective particle swarm algorithm for solving multimodal multi-objective problems[J]. Computer Engineering and Science,2020,42(8):1472-1481.

[8]

章恩泽, 赵哲萱, 韦静月, 等.基于环形拓扑结构和动态邻域的多模态多目标粒子群优化算法[J].扬州大学学报:自然科学版,2023,26(4):19-24.

[9]

Zhang En-ze, Zhao Zhe-xuan, Wei Jing-yue, et al. A multimodal multi-objective particle swarm optimization algorithm based on ring topology and dynamic neighborhood[J]. Journal of Yangzhou University(Natural Science Edition),2023,26(4):19-24.

[10]

李占山, 宋志扬, 花昀峤. 一种基于自适应搜索的多模态多目标优化算法[J].东北大学学报: 自然科学版,2023,44(10): 1408-1415.

[11]

Li Zhan-shan, Song Zhi-yang, Hua Yun-qiao. A multimodal multi-objective optimization algorithm based on adaptive search[J]. Journal of Northeastern University (Natural Science Edition),2023,44(10):1408-1415.

[12]

刘衍俊, 刘晓东. 基于鲸鱼优化的k-means初始聚类中心选取研究[J]. 电子设计工程, 2024, 32(22): 42-46.

[13]

Liu Yan-jun, Liu Xiao-dong. A study on k-means initial clustering center selection based on whale optimization[J]. Electronic Design Engineering,2024,32(22): 42-46.

[14]

Zhong C T, Li G, Meng Z. Beluga whale optimization: a novel nature-inspired metaheuristic algorithm[J]. Knowledge-Based Systems, 2022,251: 109215.

[15]

Lian J, Yao X, Li Z S. Research and improvement of crow search algorithm for Feature selection[J]. Journal of Software, 2022,33(11): 3903-3916.

[16]

班多晗, 吕鑫, 王鑫元.基于一维混沌映射的高效图像加密算法[J].计算机科学,2020, 47(4): 278-284.

[17]

Ban Duo-han, Lv Xin, Wang Xin-yuan. An efficient image encryption algorithm based on one-dimensional chaotic mapping[J]. Computer Science,2020,47(4):278-284.

[18]

Ester M, Kriegel H P, Sander J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//National Conferences on Aritificial Intelligence, KDD,1999, 226-231.

[19]

Liang J, Qiao K, Yue C, et al. A clustering-based differential evolution algorithm for solving multimodal multi-objective optimization problems[J]. Swarm and Evolutionary Computation,2021, 60: 100788.

[20]

Zitzler E, Laumanns M, Thiele L.SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization[C]// Proceedings of the EUROG,Athens,Greece, 2001: 19-21.

[21]

Liang J J, Yue C T, Qu B Y.Multimodal multi-objective optimization: a preliminary study[J].IEEE, 2016:2454-2461.

[22]

Qu B, Li C, Liang J,et al.A self-organized speciation based multi-objective particle swarm optimizer for multimodal multi-objective problems[J].Applied Soft Computing, 2020, 86: 13-18.

[23]

岳彩通, 梁静, 瞿博阳, 等.多模态多目标优化综述[J].控制与决策,2021,36(11):2577-2588.

[24]

Yue Cai-tong, Liang Jing, Qu Bo-yang, et al. A review of multimodal multi-objective optimization[J]. Control and Decision Making,2021,36(11):2577-2588.

[25]

纪育青, 方艳红, 谭顺华, 等.基于Bi-LSTM模型的恶意JavaScript代码检测方法[J].计算机应用与软件, 2024, 41(9): 357-362.

[26]

Ji Yu-qing, Fang Yan-hong, Tan Shun-hua, et al. Detection of malicious JavaScript code based on Bi-LSTM model[J]. Computer Applications and Software, 2024, 41(9): 357-362.

[27]

高新成, 张海洋, 朱城枫. 基于图层级异构图注意力网络的JavaScript恶意代码检测[J]. 吉林大学学报: 工学版, 2026, 56(4): 1094-1102.

[28]

Gao Xin-cheng, Zhang Hai-yang, Zhu Cheng-feng. JavaScript malicious code detection based on graph level heterogeneous graph attention network[J]. Journal of Jilin University (Engineering and Technology Edition), 2026, 56(4): 1094-1102.

基金资助

黑龙江省教育科学“十五五”规划2026年度规划课题(GJB1526274)

黑龙江省教育科学“十四五”规划2025年度规划课题(GJB1425352)

AI Summary AI Mindmap
PDF (1206KB)

0

访问

0

被引

详细

导航
相关文章

AI思维导图

/

〈 〉