APP下载

基于K-means聚类的麻雀搜索算法研究

2022-10-25方旺盛赵如华朱东林

计算机仿真 2022年9期
关键词:测试函数追随者探索者

方旺盛,赵如华,朱东林,王 冲

(江西理工大学,江西 赣州 341000)

1 引言

麻雀搜索算法是2020年由JiankaiXue和BoShen提出的一种新型的仿生物群智能算法,根据麻雀觅食并躲避捕食者的行为而受启发。由于该算法控制参数较少,实现简单易懂,因此可应用在微电网多目标优化、梯级水库调度优化、无人机边缘检测等领域,在解决一些工程问题时具有明显优势,但该算法和许多群智能算法一样仍存在极易陷入局部最优和提早收敛问题。

针对群智能算法的缺陷,许多学者进行了深入研究,并取得了一定的成果。其中,张永和陈锋学者针对鲸鱼优化算法(WOA)收敛速度慢、收敛精度低的问题,在提升性能的基础上保留WOA的简单性,提出一种改进的WOA,利用分段Logistic混沌映射产生混沌序列对种群位置进行初始化,以维持全局搜索时初始种群的多样性。考虑算法的非线性优化过程和搜索过程中个体状态的差异性,在WOA中引入非线性自适应权重策略,以协调全局探索和局部开发能力。樊晓红和万仁霞学者在针对鸟群算法在寻优后期极易陷入局部最优和过早收敛的问题,提出一种基于聚合度改进的鸟群算法,通过引进种群相似度和聚集度的概念来描述鸟群在觅食过程的可行性搜索范围。王晓东,张姣,薛红学者为解决传统K—means算法中因初始聚类中心选择不恰当而导致聚类结果陷入局部极值的问题,采用蝙蝠算法搜寻K-means算法的初始聚类中心,并将模拟退火的思想和基于排挤的小生境技术引入到蝙蝠算法中,以克服原始蝙蝠算法存在后期收敛速度慢、搜索力不强等问题麻雀算法通过位置来接近食物。为了解决存在麻雀搜索算法极易陷入局部最优和提早收敛问题。本文采取k-means聚类的思想将种群初始聚类分化,结合麻雀算法较好的寻优能力,使收敛速度得到了有效提升。

2 基本麻雀搜索算法

在麻雀觅食的过程中,分为探索者和追随者,探索者在种群中负责寻找食物并为整个麻雀种群提供觅食区域和方向,而追随者则是利用探索者指明的区域和方向来获取食物。种群中的个体会监视群体中其它个体的行为,并且该种群中的攻击者会与高摄取量的同伴争夺食物资源,以提高自己的捕食率。此外,当麻雀种群受到捕食者的攻击时会做出反捕食行为。通过仿照麻雀的这一系列行为,仿照麻雀的这些行为构造数学模型,假设在维空间中有只麻雀进行种群觅食活动,在时刻第只鸟的位置,={,…,}表示设计了该算法进行函数最优化求解,具体实现方式如下:

1)具有较好适应度值的探索者在搜索过程中会优先获取食物。由于探索者是负责为整个麻雀种群寻找食物并为追随者提供觅食的方向,所以探索者可以获得比追随者更大的觅食搜索范围。对于追随者在觅食过程中会时刻追随并监视探索者,这些追随者会做出同探索者争夺食物或者在探索者周围觅食的行为。

在每次的迭代过程中,当2<时,这表明此时的觅食环境周围没有捕食者,探索者可以执行广泛的搜索操作。此时探索者的位置更新公式为

(1)

其中代表当前迭代数,是一个常数,表示最大的迭代次数。表示第个麻雀在第维中的位置信息。∈(0,1)是一个随机数。(∈[0,1])和(∈[05,1])分别表示预警值和安全值。

当2≥,这表示种群中的一些麻雀已经发现了捕食者,并向种群中其它麻雀发出了警报,此时所有麻雀都需要迅速飞到其它安全的地方进行觅食。此时探索者的位置更新公式为

(2)

是服从正态分布的随机数。表示一个1×的矩阵,其中该矩阵内每个元素全部为1。

2)对于追随者在觅食过程中会时刻追随并监视探索者,这些追随者会做出同探索者争夺食物或者在探索者周围觅食的行为。

当≤2时,此时追随者在探索者周围进行觅食的行为,此时追随者的位置更新描述如下:

(3)

其中,是服从正态分布的随机数,表示种群的维度,则表示当前全局最差的位置。

当>2时,此时代表着在种群中适应度值较低的第个追随者没有获得食物,需要飞往其它地方觅食,以获得更多的能量。是目前发现者所占据的最优位置,表示一个1×的矩阵,其中每个元素随机赋值为1或-1,并且=()。此时追随者的位置更新描述如下

(4)

3)当整个麻雀种群收到捕食者攻击时,处在种群最外层的麻雀更容易收到捕食者的攻击,所以种群中的麻雀会不断的调整位置来为自己获得更优的位置。与此同时,在种群中心的麻雀也会不断的去接近与其相邻的同伴,可以尽量避免它们处在危险区域。侦察预警的麻雀一般是占到种群的10到20左右,当>表示此时的麻雀正处于种群的边缘,比较容易受到捕食者的攻击。其位置更新的数学表达式如下

(5)

=时,表示种群中间的麻雀收到了危险的信号,需要做出接近其它麻雀的反捕食行为。其位置更新的数学表达式如下

(6)

其中,其中是当前的全局最优位置。作为步长控制参数,是服从均值为0,方差为1的正态分布的随机数。∈[-1,1]是一个随机数,则是当前麻雀个体的适应度值。和分别是当前全局最佳和最差的适应度值。是最小的常数,以避免分母出现零。

为简单起见,当>表示此时的麻雀正处于种群的边缘,比较容易受到捕食者的攻击。当=时,表示种群中间的麻雀收到了危险的信号,需要做出接近其它麻雀的反捕食行为。表示麻雀移动的方向同时也是步长控制参数。

3 K-means原理

K-means算法属于一种经典的无监督的聚类算法。对于一个给定的样本集,根据样本之间的距离大小,将该样本划分为个簇,使得每个簇里的点尽量紧密的连在一起,并且让每个簇之间的间隔尽量大。

如果用数据表达式表示样本集={,…,},k-means算法就是针对聚类划分={,,…,}最小化平方误差

(7)

步骤一:在数据集中随机选择聚类个数,生成个聚类初始中心;

步骤二:计算任意一个样本点到个聚类中心的距离,根据远近聚类;

步骤三:利用均值等方法更新聚类中心,迭代聚类;

步骤四:若聚类中心变动很小(满足收敛要求)或者达到迭代次数,则认为达到稳定状态,迭代结束,对不同的聚类块和聚类中心选择不同的颜色标注。

以此看出,K-means算法实现起来比较简单且聚类效果也不错,算法的可解释度较强主要需要调节的参数仅仅是簇数K。但是该算法仍存在可改进的部分,对于K值的选取不好把握,最终结果和选的初始值有关,容易陷入局部最优。

4 基于k-means的麻雀搜索算法

麻雀搜索算法虽较其它群体优化算法有较好的全局搜索能力,但在局部搜索性能上还是较差,因其种群内部分工较为复杂,导致迭代次数增加,且无意义的次数也在增加。k-means聚类算法在局部有较好的开采能力,适用于局部局部寻优且计算简单。两者结合优势互补,在一定的程度上加快收敛,提升寻优能力。在种群初始化时,群内个体交流繁多,使得误差增大,将种群进行K-means聚类,分类之后同属于一类的群体之间先进行信息交互,且不受其它群体干扰,增大群体之间的容错率,之后再进行信息汇总;同时有效躲避攻击者的抓捕,从而提高个体的捕食率,增强寻优能力和加大收敛速度,具体实现流程如下:

1)初始化种群位置、数量以及迭代次数,包括种群规模N,探索者个数p,侦察预警的麻雀个数s,目标函数的维度D,最大迭代次数T。

2)通过引用3节中的k-means算法确定聚类中心数K,将种群聚类分化(注:聚类中心数K不宜过大,否者个体之间的距离较远,信息难以交互,呈现负效果,K随种群数量增大而增大)。

“完成党的十九大提出的目标任务,必须充分发挥工人阶级主力军作用。”10月29日,习近平总书记在同中华全国总工会新一届领导班子成员集体谈话并发表重要讲话时指出,我国广大职工要牢牢把握为实现中国梦而奋斗的时代主题,把自身前途命运同国家和民族前途命运紧紧联系在一起,把个人梦同中国梦紧密联系在一起,把实现党和国家确立的发展目标变成自己的自觉行动,爱岗敬业、争创一流,以不懈奋斗书写新时代华章,共同创造幸福生活和美好未来。

3)计算每只麻雀的适应度fi,选出当前最优适应度fb和其所对应的位置Xb,以及当前最劣适应度fw和其对应的位置Xw。

4)选取适应度优的前p个麻雀作为探索者,剩余的作为追随者者,当R2n/2时,根据式(4)更新追随者的位置。

5)从麻雀种群中随机选取s只麻雀进行侦察预警,当fi>fg时,根据式(5)更新其位置,当fi=fg时,根据式(6)更新其位置。

6)判断是否达到迭代次数或者求解精度。否,则回到4)步。是,则进行下一步。

7)输出最佳寻优结果。

5 实验结果及分析

5.1 实验环境及参数设置

算法在Window1064bit系统上运行,内存为8GB。算法的种群规模为20、迭代次数为1000次,聚类中心数K=5,采用MATLAB R2018b进行仿真。

5.2 基准测试函数

本文选择了10个典型的基准测试函数如表一所示进行仿真来进行评估KSSA的寻优能力。10个基准测试函数分为2组,前5个是固定维度30来优化测试,且单峰函数与多峰函数各一半,后5个是不同维度的维优化测试,这样不仅可以用来验证算法的收敛速度和收敛精度,也可以用来验证算法的全局寻优能力和局部最优规避能力。

表1 基准函数

在实验时,保证4种智能算法种群搜索个体的数目Num和迭代最大次数Num均保持一致,各组实验均分别独立进行30次实验,并取30次实验最优目标值的平均值(ave)、标准方差(std)、最大值(max)、最小值(min)等4项指标作为性能评价依据,实验统计结果见表2。

表2 基准函数优化结果比较

由表2统计结果可知,KSSA算法在、、在精度和收敛要略高于其它算法,尽管最优值和接近,但稳定性和全局性要比SSA好,且F、F4、F8测试函数上,KSSA表现突出的寻优性能,这充分说明加快了种群的个体之间信息交流使得寻优速度和精度大大提升。、、在寻优效果上并不显著,但不会低于SSA,这说明SSA算法在此函数上寻优效果已接近峰值。

5.3 算法收敛分析

F-F的收敛如图1所示。为了使实验结果更加可观,可以选择对目标函数值进行log变换。

从单峰函数的收敛图可以看出,基于K-means的麻雀搜索算法KSSA在收敛速度上明显快于其它算法,同时KSSA算法的收敛速度相比于其它算法也有着较大的优势。

当测试函数为单峰时,K-means算法的精准快速寻得最优值的效果较好。当测试函数为多峰以及变维度多峰函数时,引入K-means策略能有效地防止算法陷入局部最优,能够更稳定地寻找全局最优值。同时,由F和F可以看出,基于K-means的麻雀搜索算法KSSA在单峰函数的收敛速度更快。

图1 F1一F10的收敛

根据11个测试函数的实验结果进行综合比较,从ave指标来看改进之后的KSSA算法无论是在收敛速度和收敛精度还是对高维单/多峰基准测试函数均表现较强的平均寻优性能都明显强于其它3种算法,同时KSSA算法还具有在最优目标寻找过程中具有较高的算法平稳性或较小的波动差异性,有利于解决实际生活中的寻找最优值问题。KSSA算法在30次统计结果中仍寻得较好的min目标值,展现出KSSA算法较强的局部极值规避性与良好的全局寻优能力,在一定程度上有利于减少实际优化应用中的潜在风险与损失等。

6 基于KSSA的SVM参数优化

6.1 SVM原理及相关参数

SVM(SupportVectorMachine)的主要思想是估计一个模型,在这个模型中,应该找出能够分离数据的最佳超平面。如果训练数据可以达到完美的可分性,则可以使用硬裕度最优。在这种情况下,选择超平面决策边界,使超平面到最近的训练数据点的距离最大。在非线性分类的情况下,超平面仍然是边界,不同的是,超平面在特征空间而不是原始输入中。SVM的决策边界是对训练数据求解的最大边距超平面。基本原理如下:假设有一组训练样本,其中,是n维文本向量,是分类标签,用来表示的所属类别。在二元线性分类中,分类标签有两个值,1和-1。SVM 先通过一个分类超平面分割两个不同类别的样本,尽可能的使不同种类间的间隔最大以获得最优的分类效果。将其用于不等式约束条件下的二次规划求解

(8)

式中,为惩罚函数;为松弛变量。针对不等式约束条件下求解困难的问题,引进Lagrange乘子,则得出如下的对偶形式

(9)

在非线性的情况下,引入核函数映射

()=((),())

将式转化为

(10)

由式推导,得到决策函数如下

(11)

式中,为基本符号函数;()为和函数;由二次规划确定;为训练样本数;为阈值,其大小由训练样本确定。

当今几种比较常用的核函数表达形式有柯西核函数、多项式核函数、径向基核函数、线性核函数等。因径向基核函数(RBF)有较强的学习能力且泛化能力优越,在多种情况下具有良好的适应性,所以应用比较广泛,本文同样采取RBF,具体表达式如下:

(12)

SVM中C的作用为控制模型复杂度及模型逼近误差的折衷,C越大对数据的拟合程度越高,但泛化能力降低。参数g为核函数的宽度参数,控制了函数的径向作用范围。当g越大,投影空间复杂度越小,数据的线性可分的程度也越小;反之,当g越小,投影空间的复杂度越大,甚至趋向于无穷,虽然能将样本数据映射为高维线性可分,但是会导致严重的过拟合问题。因此,SVM优化的效果主要取决于这两个参数的选择,采用较好的优化算法进行参数选择,才能更好地发挥SVM的分类性能。

6.2 案例数据

本文采用是UCI数据库中的wine数据,该数据来源于在同一区域内三种不同葡萄酒的化学成分。数据包含178个均含有13个特征分量的样本,且每个样本的类别标签均已标注。随机选取这178个样本中的89个样本作为测试集,剩下的89个样本作为训练集,先用训练集对优化的SVM进行训练得到分类模型,再用测试集得到的分类模型对测试集的数据进行类别标签预测。

图2 wine数据的box可视化图

图3 样本

6.3 实现结果

KSSA算法的实验参数与上面一致,图4为最好分类下的预测情况图。

图4 最好分类下的预测情况图

通过实验得到的结果可以看出有一个标签没有成功分类,因此预测概率为98.8674%。为了进一步证明其有效性,本次将遗传算法(GA),粒子群算法(PSO)及基本麻雀搜索算法优化SVM模型进行对比实验,实验参数一致,各算法独立运行十次,计算平均准确率,最优准确率及最差准确率,三个指标可以有效的看出各算法优化SVM参数的稳定性及优良性。

表3 各算法优化情况表

从表中可以看出,KSSA-SVM模型在三个指标上最优,SSA-SVM模型预测精度没有达到最优,但稳定性仅此于KSSA-SVM模型,PSO-SVM模型虽能达到98.8674%的预测效果,但预测结果不稳定,最差达到了57.3034%,GA-SVM在各项指标上都处于最低地位,预测精度不够且稳定性差。

7 结论

1) 通过将最新提出的麻雀搜索算法与K-means聚类算法融合,提出一种KSSA算法,即将K-means算法良好的聚类分化特性及麻雀搜索算法较好的寻优能力相结合,使得种群内部工作交流效率高,摆脱种群随机复杂的工作交流,提高算法的寻优效率和优化性能,准确且迅速的寻求最优值。基准测试函数实验表明改进算法提高了寻优精度及寻优速度,并使算法后期能有效地跳出局部最优,提高了麻雀群体的搜索能力,突出改进策略的有效性和可行性。

2) 将改进后的KSSA算法优化SVM参数得到KSSA-SVM,通过各类算法优化对比,可以看出KSSA-SVM模型具有较好的稳定性,且预测精度较高,这充分说明KSSA寻优性能较好。

3) 文中从更新种群的角度改善了麻雀搜索算法的寻优性能,但改进算法只能在低维空间展现较好的寻优效果,对高维还是个重点研究方向,今后在高维以及疾病诊断中有着较大的研究前景。

猜你喜欢

测试函数追随者探索者
做一名红色记忆的追随者
解信赖域子问题的多折线算法
一种基于精英选择和反向学习的分布估计算法
追随者
基于自适应调整权重和搜索策略的鲸鱼优化算法
越过群山之美品鉴依波探索者系列1910腕表
具有收缩因子的自适应鸽群算法用于函数优化问题
现代教育的探索者——王庭槐
王大辉:复杂系统的探索者
追随者