改进的蝴蝶优化聚类算法①

2020-11-13郑洪清

计算机系统应用 2020年10期

郑洪清

(广西外国语学院信息工程学院,南宁 530222)

聚类是将数据集中的样本划分为若干个通常不相交的子集,每个子集称为“族”,同一族中的对象具有较高的相似度,不同族中的对象差别较大.聚类分析已成为数据挖掘领域的研究热点问题,K 均值算法(K-means)是一种经典的聚类算法,因其受初始聚类中心的影响容易陷入局部最优等缺陷而限制了其应用范围.许多学者提出一系列智能聚类算法,如蜜蜂交配优化聚类算法[1]、萤火虫聚类算法[2]、差分进化聚类算法[3]、布谷鸟聚类算法[4]、弹性网络聚类算法[5]、花朵授粉聚类算法[6]、蝙蝠聚类算法[7]、灰狼与郊狼混合优化算法[8]、自适应细菌觅食聚类优化算法[9]、拓展差异度的高维数据聚类算法[10]、无人仓系统订单分批问题及K-max 聚类算法[11]等.各种改进算法均取得了一定成效,但对于一些复杂问题仍存在精度不高和收敛速度慢等问题.

蝴蝶优化算法[12](Butterfly Optimization Algorithm,BOA)是2018年Sankalap Arora 提出一种新的全局优化算法,其灵感来自于蝴蝶的觅食行为.该行为由蝴蝶的合作向食物来源位置移动,蝴蝶接收并感知空气中的气味以确定食物来源或交配伙伴的潜在方向,但其本质不同于文献[13,14].由于提出时间短,国外可参考的文献很少,国内暂无相关论文报道.蝴蝶优化算法与其他群智能算法一样,也存在收敛速度和易陷入局部最优等缺陷,因此本文尝试提出了一种改进蝴蝶优化算法(Improved Butterfly Optimization Algorithm,IBOA),首先描述了蝴蝶优化算法的特点及实施步骤,重新定义蝴蝶优化算法的局部迭代公式,再将遗传算法的轮盘赌选择、交叉操作和变异操作融入蝴蝶优化算法中,通过标准的数据集测试验证IBOA 算法的有效性.

1 基本的蝴蝶优化算法

蝴蝶优化算法是模拟蝴蝶的觅食行为,该思想的条件假设如下:

1)所有的蝴蝶都应该散发出某种香味,使蝴蝶能够互相吸引.

2)每只蝴蝶都会随机移动,或朝着散发出更多香味的最佳蝴蝶移动.

3)蝴蝶的刺激强度受目标函数值的影响或决定.

当蝴蝶能感觉到其他任何蝴蝶的香味时并朝它移动,在该算法中,该阶段称为全局搜索.在另一种情况下,当蝴蝶不能感觉周围的香味时,然后它会随机移动这个阶段称为局部搜索.利用转换概率控制全局和局部搜索过程,其迭代公式为:

式(1)中的f是香味感知量,c是感觉形式,I是刺激强度,a是香味,通常a和c的取值范围为[0,1]之间;式(2)中的表示第i只蝴蝶在第t+1代的位置,r∈[0,1]的随机数,g∗表示全局最优解,fi表示第i只蝴蝶的香味感知量;式(3)中的,,分别表示第i,j,k只蝴蝶在第t代的位置;式(4)中的b为常数,ct,表示第t代的值,Ngen为最大迭代次数.

基于上述描述,蝴蝶优化算法的实施步骤如下:

Step 1.初始化种群规模n及转换概率p等参数.

Step 2.利用式(5)计算每只蝴蝶的适应度值,并求出当前最优值fmin和最优解Best.

Step 3.利用式(1)计算香味感知量,如果rand

Step 4.利用式(5)重新计算每只蝴蝶的适应度值Fnew,ifFnew

Step 5.利用式(4)更新c.

Step 6.判断是否达到最大迭代次数,如果是输出最优值和最优解,否则跳至Step 3.

2 改进的蝴蝶优化算法

由于基本的BOA 算法聚类效果差,本文对其进行改进,提出一种改进的蝴蝶优化聚类算法.重新定义蝴蝶的局部搜索方式,同时结合轮盘赌选择、交叉操作和变异操作,提高算法的寻优能力,使聚类效果稳定.

2.1 编码方法

采用实数编码,一只蝴蝶的位置表示一组聚类中心,假设有m个聚类中心,数据集的属性有d个,则每只蝴蝶的维数为nd=d×m.则第t代蝴蝶i的位置编码为xi(t)=[c1(t),c2(t),···,cm(t),],其中cj(t)表示第t代蝴蝶的第j个聚类中心,j=1,2,···,m.

2.2 评价函数

本文采用如下的聚类准则作为适应度值:

其中,nc为聚类样本数,yi为第i个样本,f(xi(t))表示所有数据到聚类中心的最小值,值越小表示聚类效果越好.

2.3 重新定义迭代公式

鉴于基本的蝴蝶优化算法局部寻优能力较差,故结合精英策略将式(3)重新定义如下:

式(6)中g∗为全局最优解即为精英,其他蝴蝶在精英附近进行搜索,因此能提高算法的精度.

为了提高聚类效果和鲁棒性,融合遗传算法相关操作.

2.4 轮盘赌选择

1)计算每只蝴蝶的适应度值Fitness;

2)计算每只蝴蝶被遗传到下一代的概率p;

3)计算每只蝴蝶的累加概率q;

本研究中螺钉位置不良17例（共19枚），其中8例为开展该技术早期病例，可能与术者的技术水平密切相关；12例患者椎弓根狭小或无髓腔，术前研究患者影像学资料不充分，置钉路径制定欠佳。

4)在蝴蝶种群中对每一个体产生一个随机数r∈[0,1],执行temp=find(r

2.5 交叉操作

2)若r

2.6 变异操作

设xi=(xi1,xi2,···,xid,xid+1,···,xie,···,xin),随机选取两个位置xid和xie,将两个位置之间的元素进行逆转操作,变换后的位置为=(xi1,xi2,···,xie,xie−1,···,xid,···,xin).

2.7 IBOA 实施步骤

Step 1.初始化种群规模、转换概率、迭代次数N_iter和交叉概率pc等参数.

Step 2.计算每只蝴蝶的适应度值,并求出当前最优值fmin和最优解Best.

Step 3.利用式(1)计算香味感知量,如果rand

Step 4.重新计算每只蝴蝶的适应度值Fnew,ifFnew

Step 5.执行轮盘赌选择、交叉操作和变异操作.重新计算每只蝴蝶的适应度值Fnew,ifFnew

Step 6.利用式(4)更新.

Step 7.判断是否达到最大迭代次数,如果是输出最优值和最优解,否则跳至Step 3.

3 实验分析

3.1 实验环境与参数设置

为了测试IBOA 算法的正确性与有效性,选取6个基准测试函数来验证算法,包括1 个人工数据集和5 个从UCI (http://archive.ics.uci.edu/ml/index.php)数据库中选取了Iris、Wine、Glass、Cancer、Cintraceptive Method Choice (简称CMC)5 组实验数据,所有的实例均运行在处理器为Celeron(R)双核CPU T3100,1.90 GHz、内存为4G 的PC 上,以Matlab R2010a 编写代码.参数设置为:种群规模＝50、转换概率＝0.1、c的初值为0.01,迭代次数N_iter＝200 和交叉概率pc＝0.85.在问题规模一致的情形下,这些算法的复杂度是相同的.

3.2 测试实例结果比较

(1)人工数据集1 (set_data=250,d=3,K=5):为了展示IBOA 的求解过程,分别计算第10 代、第50 代的求解结果如图1和图2中.并将算法独立运行20 次的结果于表1中,Best 表示最优解,Average 表示平均解,Worst 表示最差解,Std 表示标准差.表1中其他算法与数据来源于文献[7],从表1中的计算结果可知IBOA的求解精度及鲁棒性均优于其他算法.

图1 人工数据集1 第10 代的聚类结果

图2 人工数据集1 第50 代的聚类结果

表1 人工数据集1 的20 次独立运行结果比较

(2)UCI 数据集:将算法独立运行20 次,与近几年多种算法比较如表2–表7所示,其中表2–表6中的Kmeans、GA、ACO、PSO、HBMO、IDE 算法数据来源于文献[3]且迭代次数为500 时的计算结果,IBA 算法数据来源于文献[7],IGSO 算法数据来源于文献[2],BPFPA 算法数据来源于文献[6];表7中K-means、PSO、ABC、BA 和IBA 算法数据来源于文献[7].从表2可知,IBOA 算法求解效果与IBA、BPFPA 相当,但比其余8 种算法效果较好;从表3可知,IBOA 算法与BPFPA 求解效果相当,但比其余7 种算法效果优越许多;文中的“－”表示未有相关数据.从表4可知,IBOA 的求结果在迭代次数为200 时优于IDE 和其他算法;从表5可知,IBOA 算法的精度和方差均优于其他算法;从表6可知,IBOA 算法的求解效果差于IDE,与IBA、BPFPA 效果相当,但优于其他算法;从表7可知,IBOA 算法的求解效果与IBA、BPFPA 相当,但优于其他算法.另外,图3展示了IBOA 算法和BOA 算法在Survival 数据集的最优解收敛曲线图,从图3易知,IBOA 算法的求解速度和精度较BOA 算法高.IBOA 求解Iris、Survival、CMC 数据集的聚类效果图如图4–图6所示.

表2 11 种算法在Iris 数据集上聚类结果比较

表3 10 种算法在Wine 数据集上聚类结果比较

表4 9 种算法在Glass 数据集上聚类结果比较

表5 9 种算法在Cancer 数据集上聚类结果比较

表6 10 种算法在CMC 数据集上聚类结果比较

表7 8 种算法在Survival 数据集上聚类结果比较

图3 IBOA 与BOA 求解Survival 数据集函数收敛曲线图

4 结论

本文将精英策略的思想重新定义蝴蝶优化算法的局部搜索迭代公式且遗传算法相结合提出了一种改进的蝴蝶优化聚类算法,通过求解1 个人工数据集和5 个UCI 数据库中不同规模的数据,统计分析结果表明IBOA 算法能够避免陷入局部最优,具有较快的收敛速度和较强的鲁棒性,能够有效解决聚类问题且与其他聚类算法相比具有一定优势.