2020, Vol. 41
2. 吉林大学 符号计算与知识工程教育部重点实验室, 吉林 长春 130012
2. Symbol Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
受蝙蝠回声定位行为的启发, 蝙蝠算法(bat algorithm, BA)于2010年由剑桥大学的Yang[1]提出, 随着研究的深入, 该算法逐渐引起人们的极大关注, 且在应用方面取得较大成功.Tsai等[2]将其改进后应用于解决数值优化问题; Yang[3]用其解决多目标优化问题; Bora等[4]将其应用在直流无刷马达问题上.蝙蝠算法是一种新的群智能算法, 在收敛速度和求解精度上还存在缺陷.该算法也存在易陷入局部最优、震荡、收敛速度慢和求解精度不高等不足.本文针对原始蝙蝠算法提出了一种全局混沌蝙蝠优化算法(GCBA), 将混沌算法与最优解相结合用于解决特征选择问题.在种群初始化时GCBA算法覆盖整个解空间, 使用交叉算子做进一步优化; 此外, 将GCBA算法应用于特征选择领域[5].为了验证GCBA算法的有效性, 将GCBA与其他3个优化算法在多个数据集上进行了测试.结果表明, GCBA算法能够获得更好的分类精度及更快的收敛速度.
1 蝙蝠算法蝙蝠算法是一种采用回声定位原理模拟蝙蝠捕食过程的启发式群智能算法.不同于其他生物, 蝙蝠采用回声定位来探测猎物、捕食猎物和寻找栖息地等.蝙蝠发出的脉冲频率通常在25~150 kHz之间, 波长范围为2~14 mm, 发出的声音响度能达到110 dB.在探测猎物时, 随着蝙蝠与猎物之间的距离逐渐缩短, 蝙蝠发出声音的响度逐渐降低, 脉冲发射率逐渐增加.
为了模拟蝙蝠回声定位的捕食行为, 传统蝙蝠算法的3个理想化假设如下:
1) 假设蝙蝠利用回声定位感知自身与目标之间的距离, 同时具有辨别目标与背景障碍物的能力.
2) 假设第i只蝙蝠在空间位置xi以速度vi随机飞行, 以初始频率fmin、不同的波长λ和初始响度A0进行目标搜索。蝙蝠结合自己和猎物之间的距离调整脉冲发射率r∈[0, 1].
3) 假设响度从最大值A0变化到最小值Amin.
基于以上3个理想化假设, 在搜索空间中, 蝙蝠的频率、速度与位置公式分别为
|
(1) |
|
(2) |
|
(3) |
式中:fi为第i只蝙蝠的脉冲频率; fmin和fmax分别为脉冲频率的最小值和最大值; β为[0, 1]上服从均匀分布的随机数; vit+1和vit分别为第i只蝙蝠在第t+1和t代的飞行速度; xit为第i只蝙蝠在第t代的位置; xit+1为第i只蝙蝠在第t+1代的位置; x*为当前群体中蝙蝠的最优位置.
在搜寻猎物的过程中, 蝙蝠初始发出的超声波响度大, 但发射速率低, 有利于猎物在整个空间进行搜索.当蝙蝠发现猎物以后, 蝙蝠逐渐减小响度、增加脉冲发射率, 这样更有利于精准确定猎物的位置.公式为
|
(4) |
|
(5) |
式中:rit+1为第i只蝙蝠在第t+1代的脉冲发射率; ri0为第i只蝙蝠的最大脉冲发射率; γ>0为脉冲频度增加系数; Ait+1和Ait分别为第i只蝙蝠在第t+1和t代的音量响度; α∈[0, 1]为脉冲音量响度衰减系数.
BA算法的伪代码如下:
目标方程f(x), x=(xi, …, xd)
初始化蝙蝠种群xi和vi(i=1, 2, …, n)
定义发射频率fi在位置xi
初始化脉冲发射率ri和响度Ai
While(t < Max number of iterations)
使用公式(1), (2)和(3)更新蝙蝠的频率、速度和位置
形成新的解
If(rand>ri)
选择出全局最优解
形成一个局部解在最优解附近随机浮动
End if
通过随机飞行形成一个新的解
If(rand < Ai & f(xi) < f(x*))
接受新的解
增大ri并且减小Ai使用公式(4)和(5)
End if
对所有蝙蝠排序并且找到目前最好的解x*
End while
2 全局混沌蝙蝠优化算法 2.1 基于混沌映射的种群初始化群智能搜索算法种群不断迭代, 初始化种群的好坏对种群的收敛速度和寻优性能有着很大的影响[6], 多样性丰富的初始化种群更有利于找到种群的全局最优解.种群的全局最优解是一个未知量, 没有任何先验知识能够知道全局最优解在什么位置, 所以初始化种群的覆盖性很重要, 蝙蝠尽量覆盖整个解空间.然而, BA算法的种群初始化是随机产生的, 不具有覆盖整个解空间的能力, 这大大影响了BA算法的性能.
为了解决BA算法初始化种群随机性的问题, 本文提出全局混沌蝙蝠优化算法(GCBA).该算法使种群的初始化能够遍历整个解空间.目前使用最广泛的混沌映射方法为logistic方法, 该方法产生的初始化种群具有多样性并且能够遍历整个解空间.因此, 本文采用改进的logistic映射方法来进行种群的初始化, 其数学模型为[7]
|
(6) |
式中:yik∈[0, 1]为混沌变量, k=1, 2, …, M, M表示初始化种群维度, i=1, 2, …, N, N表示初始化种群数量.然后, 针对yik做逆映射得到相应解空间的初始化种群xik:
|
(7) |
式中li和ui为变量取值范围的最小值和最大值.
2.2 局部最优和全局最优在BA算法的后期, 种群都趋向于最优区域, 所以种群的多样性降低.如果当前种群个体找到的最优解并非全局最优解, 则算法就会陷入局部最优.算法提前收敛, 陷入早熟, 这也是所有群智能算法的固有缺陷.为了解决这个问题, 本文在每个蝙蝠进行位置更新的时候记录该蝙蝠局部最优位置和种群的全局最优位置.
|
(8) |
式中:Pil为第i只蝙蝠的局部最优位置; Pg为蝙蝠种群的全局最优位置; C1=C2=1.496 18;r1和r2是两个在[0, 1]之间的随机数.
2.3 GCBA应用于特征选择初始化蝙蝠种群时使用一个大小为n×d的矩阵, 其中, n表示蝙蝠样本数量, d表示特征个数.本文使用转换方程对蝙蝠个体的速度进行离散二进制操作, 转换方程为
|
(9) |
式中, vik(t)为在第t次迭代过程中蝙蝠个体i在第k维的速度.
蝙蝠个体的位置更新方程为
|
(10) |
式中, xik(t)和vik(t)分别为第t次迭代过程中蝙蝠个体i在第k维的位置和速度.
当蝙蝠个体i第t次迭代第k维的位置为0时, 表示这个特征不会被选择; 当蝙蝠个体i第t次迭代第k维的位置为1时, 表示这个特征会被选择.
GCBA的伪代码如下:
目标方程f(x), x=(x1, …, xM)
使用混沌映射方法初始化蝙蝠种群xi和vi, (i=1, 2, …, n)
定义发射频率fi在位置xi
初始化脉冲发射率ri和响度Ai
While(t < Max number of iterations)
使用公式(1), (2)和(8)更新蝙蝠的频率、速度和位置
形成新的解
使用式(9)把所有蝙蝠位置转换到二进制空间
If(rand>ri)
使用SVM分类器选择出全局最优解x*
形成一个局部解在最优解附近随机浮动
End if
通过随机飞行形成一个新的解
If(rand < Ai & f(xi) < f(x*))
接受新的解
增大ri并且减小Ai使用公式(4)和(5)
End if
End while
3 实验仿真及分析本文选取UCI公共数据集测试GCBA算法性能, 见表 1.样本数量从76到1 473, 特征数量从4到24, 数据维度的跨度大且特征数量分布广, 数据集的选择具有实际意义.在实验设置上, 把GCBA和BBA[8], PSO[9-10]和GA[11]进行比较, 结合SVM和十折交叉验证方法测试10个UCI数据集.这10个数据集分别是Australian, Ballon, Breastcancer, Bupa liver, Contraceptive Method Choice, Cleveland heart, Diabetes, German, Glass和Heart.对于BBA算法, 初始化参数设置:蝙蝠的数量=30, 响度=1.5, 脉冲发射率=0.5, 频率fmin=0, fmax=1, 最大种群迭代次数=100.对于PSO算法, 初始化参数设置:种群大小=30, ω=2, 系数c1=c2=2, 最大种群迭代次数=100;对于GA算法, 初始化参数设置:种群大小=30, 交换率=0.4, 变异率=0.2, 最大种群迭代次数=100.
|
表 1 数据集说明 Table 1 Detail of data sets |
鉴于篇幅限制, 本文只给出4个算法.Breastcancer和German数据集的分类正确率比较如图 1和图 2所示.从图 1和图 2可以看出, GCBA算法分别在第80次到90次迭代期间获得了最优解, 而其他算法都提前收敛, 陷入局部最优.通过与其他三个算法的比较, 证明GCBA算法具有良好的全局搜索能力.
|
图 1 Breastcancer数据集的分类正确率 Fig.1 Classification accuracy rate of Breastcancer dataset |
|
图 2 German数据集的分类正确率 Fig.2 Classification accuracy rate of German dataset |
从表 2的实验结果可以看出:在所有的数据集上, GCBA算法都达到最优正确率.全局最优和局部最优的引入, 使算法能够有效跳出局部最优.此外, 除了数据集Glass, GCBA在其余数据集上的稳定性表现良好.这是由于在初始化时, 算法引入混动映射方法, 使样本分布更广, 提升了算法的稳定性.
|
|
表 2 实验结果 Table 2 Experimental results |
从表 3的实验结果可以看出:在所有的数据集上, BBA算法结合局部最优(Pl)和全局最优(Pg)都达到更优的分类精度和较好的稳定性.由于全局最优和局部最优思想的引入, 算法能够有效跳出局部最优解.从图 3可以看出, BBA算法在Bupa liver数据集上第30次迭代陷入了局部最优解, 而引入局部最优和全局最优的BBA算法能够跳出局部最优, 获得了全局最优解.
|
图 3 两个算法在Bupa liver数据集的分类正确率 Fig.3 Classification accuracy rates of two algorithms on the Bupa liver dataset |
|
|
表 3 BBA和BBA+Pl+Pg实验结果 Table 3 Experimental results of BBA and BBA+Pl+Pg |
1) 针对蝙蝠算法具有易陷入局部最优, 收敛速度慢和求解精度不高等不足, 本文提出了一种全局混沌蝙蝠优化算法(GCBA).
2) GCBA算法使用混沌映射初始化种群, 增强了初始化种群的丰富性.GCBA算法引入Pl和Pg优化位置更新公式, 提升了算法的全局搜索能力.
3) GCBA, BBA, PSO和GA的实验结果表明, GCBA算法不仅能够得到很好的分类精度, 还具有良好的稳定性和全局搜索能力.验证了GCBA算法的有效性.
| [1] |
Yang X S. A new metaheuristic bat-inspired algorithm[J]. Computer Knowledge & Technology, 2010, 284: 65-74. |
| [2] |
Tsai P W, Pan J S, Liao B Y, et al. Bat algorithm inspired algorithm for solving numerical optimization problems[J]. Applied Mechanics and Materials, 2012, 148/149: 134-137. |
| [3] |
Yang X S. Bat algorithm for multi-objective optimization[J]. International Journal of Bio-inspired Computation, 2012, 3(5): 267-274. |
| [4] |
Bora T C, Coelho L S, Lebensztajn L. Bat-inspired optimization approach for the brushless DC wheel motor problem[J]. IEEE Transactions on Magnetics, 2012, 48(2): 947-950. DOI:10.1109/TMAG.2011.2176108 |
| [5] |
Dash M, Liu H. Feature selection for classification[J]. Intelligent Data Analysis, 1997, 1(1/2/3/4): 131-156. |
| [6] |
杨景明, 马明明, 车海军, 等. 多目标自适应混沌粒子群优化算法[J]. 控制与决策, 2015, 30(12): 2168-2174. (Yang Jing-ming, Ma Ming-ming, Che Hai-jun, et al. Multi-objective adaptive chaotic particle swam optimization algorithm[J]. Control and Decision, 2015, 30(12): 2168-2174.) |
| [7] |
Kazimipour B, Li X, Qin A K.A review of population initialization techniques for evolutionary algorithms[C]//Evolutionary Computation.Beijing, 2014: 2585-2592.
|
| [8] |
Mirjalili S, Mirjalili S M, Yang X S. Binary bat algorithm[J]. Neural Computing and Applications, 2014, 25(3/4): 663-681. |
| [9] |
Kennedy J, Eberhart R.Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks.Perth: IEEE, 2002: 1942-1948.
|
| [10] |
Kennedy J, Eberhart R C.A discrete binary version of the particle swarm algorithm[C]//IEEE International Conference on Systems, Man, and Cybernetics.Orlando: IEEE, 2002: 4104-4108.
|
| [11] |
Alickovic E, Subasi A. Breast cancer diagnosis using GA feature selection and rotation forest[J]. Neural Computing and Applications, 2017, 28(4): 753-763. DOI:10.1007/s00521-015-2103-9 |