近年来,随着人工智能技术的迅速发展,越来越多的国内外学者将群智能(swarm intelligence, SI)算法应用于函数优化、神经网络等领域,并取得了许多成果。群智能算法是受自然界中生物种群社会行为的启发构造出的一类具有简单性、自适应性、灵活性等特点的元启发式算法,而蛇优化(snake optimizer, SO)算法[1]就是在2022年提出来的。一般来说,元启发式算法没有标准的分类。在文献[1]中,将其分为四类。
1) 进化算法(evolution-based algorithms)。它是模拟生物遗传学中个体基因之间选择、交叉、突变等规则随机对群体进行更新与替换的算法。运用较广的进化算法有遗传算法(genetic algorithm, GA)[2-3]、差分进化算法(differential evolution algorithm, DE)[4-5]等。
2) 物理化学算法(physical & chemical-based algorithms)。它是模拟宇宙中存在的物理现象或化学定律的算法。如莱维飞行算法(Levy flight algorithm, LFA)、模拟退火算法(simulated annealing algorithm, SA)[6]、猎鹰优化算法(falcon optimizer algorithm, FOA)等。
3) 人类算法(human-based algorithms)。它是受人类心理活动或者社会行为启发的算法。如教学优化算法(teaching-learning-based optimization, TLBO)、社会进化与学习优化算法(socio evolution and learning optimization, SELO)等。
4) 群智能算法。它是模仿自然界生物的个体或者种群行为,构架出具有随机性、可行性的优化算法。应用较多的有人工蜂群算法(artificial bee colony algorithm, ABC)[7-8]、粒子群算法(particle swarm optimization, PSO)[9-10]、灰狼优化算法(gray wolf optimization algorithm, GWO)[11-12]、鲸鱼优化算法(whale optimizer algorithm, WOA)[13-15]、北方苍鹰算法(northern goshawk optimizer, NGO)[16]等。
目前对SO算法的改进研究不多,例如Hu等[17]提出了一种引入双向搜索、进化种群动力学和精英反向策略的SO算法,取得了良好的效果。Khurma等[18]对比了两种基于SO算法的特征选择算法,第一种是在S形变换函数基础上构建的二进制蛇优化(binary SO, BSO)算法;第二种是引入了三种进化交叉算子(即一点交叉、两点交叉和均匀交叉),并通过切换概率进行控制的BSO算法(BSO-CV),实验表明BSO-CV具有更高的优越性。
本文针对SO算法存在前期收敛速度较慢和易陷入局部最优等问题,提出一种改进的SO算法(improved snake optimizer, ISO)。首先引入反向学习机制提高种群质量,扩大搜索范围,从而提升算法的遍历性;然后融合差分进化策略中的优胜劣汰规则,降低算法易陷入局部最优的风险。通过10个基准测试函数,并与其他群智能算法比较,验证了ISO算法具有更好的寻优能力。将其应用于支持向量机(support vector machine,SVM)参数优化选取中,进一步验证了ISO算法的有效性。
1 蛇优化算法蛇优化算法的灵感来源于蛇的觅食与繁殖行为,其搜索过程可分为勘探和开发两个阶段。
勘探阶段描述了环境因素,即温度和食物,且在该阶段不会存在蛇只在它周围的环境中寻找食物这种情况,保证算法能够遍历尽量大的搜索空间。开发阶段包括战斗模式和繁殖模式,这两个模式用来提高算法的搜索效率。在战斗模式中,每个雄蛇之间会战斗得到最好的雌蛇,每个雌蛇会选出最好的雄蛇。在繁殖模式中,每对蛇繁殖行为的发生取决于食物的数量和温度。如果繁殖行为发生,雄蛇与雌蛇就会更新至当前循环的最差位置,进行下一轮的迭代与更新。
下面用数学模型表示SO算法的基本过程。
1) 种群初始化。
$ U_{i}=U_{\min }+r \times\left(U_{\max }-U_{\min }\right), $ | (1) |
其中:Ui为第i个蛇的位置;r是[0, 1]范围内的随机数;Umax和Umin分别是求解问题的上界和下界。
2) 将种群分为雌性和雄性两个组。假设种群数量为N,分为雄蛇组和雌蛇组。
$ N_{\mathrm{m}} \approx N / 2, $ | (2) |
$ N_{\mathrm{f}}=N-N_{\mathrm{m}}, $ | (3) |
其中:
计算两组的适应度值并找出各组中最好的个体, 得到当前雄蛇组最好的个体
$ { Temp }=\exp ((-t) / T), $ | (4) |
其中:t为当前的迭代次数;T为最大迭代次数。
$ Q=c_{1} \times \exp ((t-T) / T), $ | (5) |
这里c1为一个常数,取0.5。
3) 勘探阶段。若
$ \begin{align*} & U_{i, \mathrm{~m}}(t+1)=U_{ {rand }, \mathrm{m}}(t) \pm c_{2} \times A_{\mathrm{m}} \times \\ & \left(\left(U_{\max }-U_{\min }\right) \times { rand }+U_{\min }\right), \end{align*} $ | (6) |
其中:
$ A_{\mathrm{m}}=\exp \left(\left(-f_{ {rand }, \mathrm{m}}\right) / f_{i, \mathrm{~m}}\right), $ | (7) |
其中:
若雄蛇位置能够确定,则雌蛇位置也可以确定,其表达式为
$ \begin{align*} & U_{i, \mathrm{f}}(t+1)=U_{rand.\text {f }}(t) \pm c_{2} \times A_{\mathrm{f}} \times \\ & \left(\left(U_{\max }-U_{\text {min }}\right) \times { rand }+U_{\text {min }}\right), \end{align*} $ | (8) |
其中:
$ A_{\mathrm{f}}=\exp \left(\left(-f_{ {rand }, \mathrm{f}}\right) / f_{i, \mathrm{f}}\right) $ | (9) |
其中:
在式(6)和(8)中都出现了标志方向运算符±,其目的是帮助蛇个体更新位置时,在给定的搜索空间内能探索所有可能的方向,保证算法有一定的遍历性。
4) 开发阶段。在
$ \begin{align*} & U_{i, j}(t+1)=U_{\text {food }} \pm c_{3} \times { Temp } \times { rand } \times \\ & \left(U_{\text {food }}-U_{i, j}(t)\right), \end{align*} $ | (10) |
其中:
在
① 战斗模式。
$ \begin{align*} & U_{i, \mathrm{~m}}(t+1)=U_{i, \mathrm{~m}}(t)+c_{3} \times F_{\mathrm{m}} \times { rand } \times \\ & \left(Q \times U_{\text {best }, \mathrm{f}}-U_{i, \mathrm{~m}}(t)\right) , \end{align*} $ | (11) |
其中:Ui, m为第i个雄蛇的位置;Ubest, f为雌蛇组中的最佳位置;Fm为雄蛇战斗能力。
$ \begin{aligned} & U_{i, \mathrm{f}}(t+1)=U_{i, \mathrm{f}}(t)+c_3 \times F_{\mathrm{f}} \times { rand } \times \\ & \left(Q \times U_{\text {best }, \mathrm{m}}-U_{i, \mathrm{f}}(t)\right), \end{aligned} $ | (12) |
其中:
$ F_{\mathrm{m}}=\exp \left(\left(-f_{\text {best }, \mathrm{f}}\right) / f_{i, \mathrm{~m}}\right), $ | (13) |
$ F_{\mathrm{f}}=\exp \left(\left(-f_{\text {best }, \mathrm{m}}\right) / f_{i, \mathrm{f}}\right), $ | (14) |
其中:fbest, f为雌蛇组中最佳位置Ubest, f的适应度值;fbest, m为雄蛇组中最佳位置Ubest, m的适应度值;fi, m, fi, f分别为雄蛇组和雌蛇组中当前个体的适应度值。
② 繁殖模式。
$ \begin{aligned} & U_{i, \mathrm{~m}}(t+1)=U_{i, \mathrm{~m}}(t)+c_3 \times M_{\mathrm{m}} \times \text { rand } \times \\ & \left(Q \times U_{i, \mathrm{f}}(t)-U_{i, \mathrm{~m}}(t)\right), \end{aligned} $ | (15) |
$ \begin{aligned} & U_{i, \mathrm{f}}(t+1)=U_{i, \mathrm{f}}(t)+c_3 \times M_{\mathrm{f}} \times \text { rand } \times \\ & \left(Q \times U_{i, \mathrm{~m}}(t)-U_{i, \mathrm{f}}(t)\right), \end{aligned} $ | (16) |
其中:
$ M_{\mathrm{m}}=\exp \left(\left(-f_{i, \mathrm{f}}\right) / f_{i, \mathrm{~m}}\right), $ | (17) |
$ M_{\mathrm{f}}=\exp \left(\left(-f_{i, \mathrm{~m}}\right) / f_{i, \mathrm{f}}\right), $ | (18) |
其中:
如果繁殖成功,选择最差的雄蛇和雌蛇,并替换它们。
$ U_{\text {worst }, \mathrm{m}}=U_{\min }+ { rand } \times\left(U_{\max }-U_{\min }\right) \text {, } $ | (19) |
$ U_{\text {worst }, \mathrm{f}}=U_{\min }+ { rand } \times\left(U_{\max }-U_{\min }\right) \text {, } $ | (20) |
其中:
本节主要介绍反向学习机制和差分进化策略,并将这两个概念引入蛇优化算法中。
2.1 反向学习机制在许多情况下,问题的求解过程一般是从零或者一个随机值开始向着最优解靠近。例如,神经网络的权值、群智能算法的种群参数、支持向量机的核参数等等。若一开始随机值在最优解附近,则问题可快速解决。然而也存在最坏的情况,即随机值出现在离最优解相反的地方,那么求解过程就会花费大量的时间。在没有先验知识的基础上,不可能初始就得到较好的随机值。且从逻辑上来说,问题的求解可以从各个方向进行搜索,如果引入最优解的反向解一起作为问题的可行解,也就扩大了搜索空间,则寻优效率也会随之更高。这就是反向学习[19]的核心理论。将反向学习机制应用于ISO算法,可帮助提升初始种群的质量和多样性,保证算法可以在搜索空间更全面地寻优,增加找到全局最优值的几率。个体
$ R_{U_{i}}=k \times\left(U_{\max }+U_{\min }\right)-U_{i}, $ | (21) |
其中:
差分进化算法是在遗传算法基础上提出的群智能算法,两者相同之处是都通过随机生成初始化种群,以种群中每个个体的适应度值为选择标准,且迭代过程都包括变异、交叉和选择三个步骤。不同之处在于遗传算法是直接根据适应度值来选择是否与父代杂交生成新个体,但新个体的适应度值不能保证会比原个体的适应度值好。而差分进化算法是选择两个不同的个体相减产生差分个体,将差分个体赋予权值后与第三个个体向量相加,产生变异个体。若变异个体的适应度值优于父代个体的适应度值,则选用变异个体进入下一轮迭代,否则保留父代个体。通过不断进化,保留优胜的个体,引导搜索过程向最优解逼近。显然差分进化算法的逼近效果比遗传算法更加显著。
由于SO算法拥有三种遍历方式,与大部分群智能算法相比,能寻到更优的适应度值,但这也限制了算法的收敛速度。同时,SO算法在寻优后期,容易趋近最优值附近,导致算法陷入局部最优。为解决此问题,引入了差分进化策略:首先将全部个体的顺序随机排列,并选定两个变异个体Ua和Ub供变异操作产生一个中间体;然后将当前最优个体与中间体进行交叉操作得到一个新个体;最后将新个体与当前个体进行比较,选择两者中的较优个体。
新个体用数学模型表示为
$ N_{U_{i}}=U_{\text {food }}+ { beta } \times\left(U_{a}-U_{b}\right), $ | (22) |
其中:
$ { beta }= { beta }_{\max }-t \times\left( { beta }_{\max }- { beta }_{\min }\right) / T, $ | (23) |
其中:betamax为缩放因子上界,本文设置为0.8;betamin为缩放因子下界,设置为0.2。
2.3 算法流程改进的蛇优化算法流程如算法1所示。
算法1 改进的蛇优化算法(ISO)
输入:种群数量N、当前迭代次数t、最大迭代次数T、问题上界UB及下界LB、维度dim。
输出:最优解。
Step1 初始化种群,得到初始解x。
Step2 将初始解x分为雄蛇组和雌蛇组。
Step3 计算温度Temp和食物数量Q。
IF (Q < 0.25) {由公式(6)、(8)更新雄蛇和雌蛇的位置}。
ELSE
IF (Temp>0.6) {由公式(10)更新雄蛇和雌蛇的位置}。
ELSE
IF (rand>0.6) {由公式(11)、(12)更新雄蛇和雌蛇的位置}。
ELSE {由公式(15)、(16)更新雄蛇和雌蛇的位置,并由公式(19)、(20)更新种群中最差的雄蛇与雌蛇位置}。
END IF
END IF
END IF
Step4分别在雄蛇组与雌蛇组中,根据差分进化策略计算全新解NUi。
Step5根据反向学习机制计算全新解的反向解RUi。
Step6分别在雄蛇组与雌蛇组中依次比较NUi与RUi,两者间保留较优解。
Step7比较雄蛇组与雌蛇组中的最优解,得到唯一最优解。
Step8判断算法是否达到终止条件(t≤T)。若是,终止算法,输出最优解; 否则转Step3。
3 仿真实验为验证ISO算法是否有效,本文将ISO与SO[1]、DE[4-5]、PSO[9-10]、GWO[11-12]、WOA[13-15]、NGO[16]七个算法进行基准测试函数比较实验和SVM分类效果对比实验。
3.1 基准测试函数比较实验本实验选取10个基准测试函数,所用的群智能算法种群数量设定为30,最大迭代次数为200,每个基准测试函数单独运行30次。
表 1为基准测试函数的基本信息,测试函数F1~F4为单峰函数,函数F5~F10为多峰函数。图 1为ISO算法与各算法的寻优收敛曲线,可对比t种算法之间的收敛速度和优化结果。
![]() |
表 1 基准测试函数信息 Tab. 1 Benchmark function information |
分析图 1可知,ISO算法不论是在单峰函数还是在多峰函数中,都能在找到最优值的情况下,迭代次数较SO算法更少,说明其收敛速度更快。且SO算法存在易陷入局部最优问题,而ISO算法能跳出局部最优值。与其他群智能算法相比,虽然ISO算法在部分函数的收敛速度上存在劣势,但它能更深地搜索空间,保证寻优精度更高。因此,在相同的迭代次数下,ISO算法的求解精度略高于SO算法和其他群智能算法。
![]() |
图 1 基准测试函数收敛曲线 Fig. 1 The convergence curves of benchmark functions |
本实验选取UCI标准数据库的数据集,包括Iris、Parkinsons、Fire、Heart和Ionosphere共五个数据集。各数据集经过处理后信息如表 2所示。
![]() |
表 2 数据集基本信息 Tab. 2 Information of the datasets |
以Iris数据集为例,分别从三类样本Iris setosa、Iris versicolour和Iris virginica中抽取50%的数据作为训练集,剩余的数据作为测试集。接下来将训练集和测试集的数据归一化到[0, 1]区间,以方便SVM模型训练。然后通过七种群智能算法各自选择出最佳的SVM参数组合(惩罚参数C和高斯核的带宽σ),再利用七组最佳参数训练SVM模型并进行分类实验,以测试集分类准确率作为评判标准并分析实验结果。为减小实验随机误差,共进行10轮测试并取平均值,结果如表 3所示。
![]() |
表 3 各SI算法优化SVM参数后的分类结果 Tab. 3 Classfication results of SVM after parameter optimization by SI algorithms |
分析表 3中数据可得(表中黑体数据为较优结果),基于ISO算法的SVM分类准确率在五个数据集中都高于SO算法。相较于其他算法,ISO算法在Iris数据集上的分类准确率与PSO算法持平,其余四个数据集都能达到最高的准确率。可见,ISO算法的改进是有效且优于SO算法的,应用在SVM参数优化上有明显提升。
4 结束语本文针对SO算法存在的前期收敛速度慢和易陷入局部最优问题,提出一种基于反向学习机制和差分进化策略的ISO算法。实验结果表明,ISO算法具有更高的寻优性能和更快的收敛速度,运用在SVM参数优化上是可行且有效的。
虽然ISO算法用于优化SVM参数取得了一定的成果,让模型能够获得较高的预测和分类精度,但还是存在一定的局限性。主要问题有:在1~2个测试函数中ISO算法寻优结果不如SO算法;ISO算法能在一定条件下避免陷入局部最优,但是依然存在陷入局部最优的可能性;与其他群智能算法相比,ISO算法在单峰函数上优化效果明显,而部分多峰函数的效果不太明显。后续将根据这些问题提出相应的改进方法,并应用于其他领域的实际问题。
[1] |
HASHIM F A, HUSSIEN A G. Snake optimizer: a novel meta-heuristic optimization algorithm[J]. Knowledge-based systems, 2022, 242: 108320. DOI:10.1016/j.knosys.2022.108320 ( ![]() |
[2] |
CHEN R, ZHANG Q W, PENG R T, et al. Hybrid identification method of material parameters based on genetic algorithm and improved homotopy algorithm[J]. Materials today communications, 2022, 33: 104380. DOI:10.1016/j.mtcomm.2022.104380 ( ![]() |
[3] |
OZCALICI M, BUMIN M T. Optimizing filter rule parameters with genetic algorithm and stock selection with artificial neural networks for an improved trading: the case of Borsa Istanbul[J]. Expert systems with applications, 2022, 208: 118120. DOI:10.1016/j.eswa.2022.118120 ( ![]() |
[4] |
SONG Y J, ZHAO G Y, ZHANG B, et al. An enhanced distributed differential evolution algorithm for portfolio optimization problems[J]. Engineering applications of artificial intelligence, 2023, 121: 106004. DOI:10.1016/j.engappai.2023.106004 ( ![]() |
[5] |
OPARA K R, ARABAS J. Differential Evolution: a survey of theoretical analyses[J]. Swarm and evolutionary computation, 2019, 44: 546-558. DOI:10.1016/j.swevo.2018.06.010 ( ![]() |
[6] |
吴宇翔, 王晓峰, 于卓, 等. 一种求解Max-SAT问题的快速模拟退火算法[J]. 郑州大学学报(理学版), 2023, 55(4): 46-53. WU Y X, WANG X F, YU Z, et al. A fast simulated annealing algorithm for solving max-SAT problem[J]. Journal of Zhengzhou university (natural science edition), 2023, 55(4): 46-53. ( ![]() |
[7] |
刘拥民, 王靖枫, 黄浩, 等. 模拟人工蜂群的高维数据特征选择算法研究[J]. 郑州大学学报(理学版), 2023, 55(3): 57-64. LIU Y M, WANG J F, HUANG H, et al. Research on high-dimensional data feature selection algorithm simulating artificial bee colony[J]. Journal of Zhengzhou university (natural science edition), 2023, 55(3): 57-64. ( ![]() |
[8] |
封硕, 刘琨. 融合差分进化思想的自适应人工蜂群算法[J]. 郑州大学学报(理学版), 2021, 53(3): 72-78. FENG S, LIU K. Adaptive artificial bee colony algorithm based on differential evolution[J]. Journal of Zhengzhou university (natural science edition), 2021, 53(3): 72-78. ( ![]() |
[9] |
ABBASZADEH M, SOLTANI-MOHAMMADI S, AHMED A N. Optimization of support vector machine parameters in modeling of Iju deposit mineralization and alteration zones using particle swarm optimization algorithm and grid search method[J]. Computers & geosciences, 2022, 165: 105140. ( ![]() |
[10] |
CAI B, ZHU X P, QIN Y X. Parameters optimization of hybrid strategy recommendation based on particle swarm algorithm[J]. Expert systems with applications, 2021, 168: 114388. DOI:10.1016/j.eswa.2020.114388 ( ![]() |
[11] |
WANG E L, XIA J Y, LI J, et al. Parameters exploration of SOFC for dynamic simulation using adaptive chaotic grey wolf optimization algorithm[J]. Energy, 2022, 261: 125146. DOI:10.1016/j.energy.2022.125146 ( ![]() |
[12] |
LI S, XU K, XUE G Z, et al. Prediction of coal spontaneous combustion temperature based on improved grey wolf optimizer algorithm and support vector regression[J]. Fuel, 2022, 324: 124670. DOI:10.1016/j.fuel.2022.124670 ( ![]() |
[13] |
李天翼, 陈红梅. 一种用于解决特征选择问题的新型混合演化算法[J]. 郑州大学学报(理学版), 2021, 53(2): 41-49. LI T Y, CHEN H M. A new hybrid evolutionary algorithm for solving feature selection problem[J]. Journal of Zhengzhou university (natural science edition), 2021, 53(2): 41-49. ( ![]() |
[14] |
CHAKRABORTY S, KUMAR SAHA A, SHARMA S, et al. A novel enhanced whale optimization algorithm for global optimization[J]. Computers & industrial engineering, 2021, 153: 107086. ( ![]() |
[15] |
ELAZIZ M A, MIRJALILI S. A hyper-heuristic for improving the initial population of whale optimization algorithm[J]. Knowledge-based systems, 2019, 172: 42-63. ( ![]() |
[16] |
DEHGHANI M, HUBALOVSKY S, TROJOVSKY P. Northern goshawk optimization: a new swarm-based algorithm for solving optimization problems[J]. IEEE access, 2021, 9: 162059-162080. ( ![]() |
[17] |
HU G, YANG R, ABBAS M, et al. BEESO: multi-strategy boosted snake-inspired optimizer for engineering applications[J]. Journal of bionic engineering, 2023, 20(4): 1791-1827. ( ![]() |
[18] |
ABU KHURMA R, ALBASHISH D, BRAIK M, et al. An augmented Snake Optimizer for diseases and COVID-19 diagnosis[J]. Biomedical signal processing and control, 2023, 84: 104718. ( ![]() |
[19] |
TIZHOOSH H R. Opposition-based learning: a new scheme for machine intelligence[C]//International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce. Piscataway: IEEE Press, 2006: 695-701.
( ![]() |