精英反向学习t分布饥饿游戏搜索算法

徐亦凤,刘 升,张伟康,刘宇凇

(上海工程技术大学管理学院,上海 201620)

1 引言

在社会科学、工程和经济等领域中存在着各种各样的优化问题,然而,在以往的基于群体的优化方法中存在着一些缺点和问题。近年来,国内外学者提出了一些基于动物特征的优化方法如灰狼优化算法[1]、鲸鱼优化算法[2]和飞蛾扑火算法[3],甚至一种基于正弦余弦函数模型的正弦余弦算法[4]。这些优化算法具有参数少,优化原理简单,操作易实现等特点,然而,它们的数学模型存在结构相似、性能平庸、验证方法有缺陷以及算法组件略有修改等问题。例如,非常流行的灰狼优化算法由于其初始化生成的种群方法的随机性无法保证良好的种群多样性。鲸鱼优化算法和飞蛾扑火方法的环绕包围机制与灰狼优化算法相同,只是搜索范围略有不同,这些算法实际上没有本质不同只是改变了探索方法。

饥饿游戏搜索算法(Hunger Games Search)[5]是杨玉涛和陈慧玲这两位学者提出的一种根据群居动物的共同特征及其食物搜索而设计的元启发式优化算法,与其它群智能算法相比,HGS算法不仅考虑了动物群体的行为特征还考虑了生理特征,遵循几乎所有动物都使用的计算逻辑规则和游戏,这些竞争活动和游戏通常通过确保更高的生存和食物获取机会来适应进化。该算法具有结构简单、需要调节的参数少和鲁棒性强等特点,因此在对优化问题的求解精度和收敛速度上具有良好的表现。Hoang Nguyen和Xuan-Nam Bui[6]将饥饿游戏搜索算法和人工神经网络相结合提出了HGS-ANN模型,用于预测矿山爆破诱发的地面震动强度,有助于减轻矿山爆破作业的不利影响;Fahim Samuel Raafat等人[7]利用HGS算法来获取质子交换膜燃料电池模型参数的最佳值,正面影响燃料电池的运行与控制,且由于基本的饥饿游戏搜索算法提出的时间较短,现有的论文并没有对基本的饥饿游戏搜索算法进行改进,需对其进行进一步改进与完善以适用于更多优化问题。

尽管已经提出了许多元启发式优化算法,但是根据没有免费的午餐定理,本文提出精英反向学习t分布饥饿游戏搜索算法,该算法在初始化随机种群时引入精英反向解有效增加种群多样性和质量,并且在全局探索过程中引入t分布自适应策略将高斯变异和柯西变异相结合,使得算法在迭代过程中具有良好的全局探索性。

2 基本饥饿游戏搜索算法

动物根据一些计算规则和它们与环境的相互作用来构成它们的感觉信息,这些规则成为它们决策和选择的基础,也成为它们认知结构进化的依据。饥饿是动物生活中行为、决定和行动的最重要的动机和原因之一。尽管各种各样的刺激和相互竞争的需求总是影响动物的生活质量,但当它们面临热量不足时,它们会探求食物来源。为了解决这种体内平衡失调,它们必须定期寻找食物,并以在探索性、防御性和竞争性活动之间切换的形式来靠近食物,这表明它们的进食策略极其流畅。

行为选择和活动选择在动物王国是普遍的,它是自然界中以目标为导向的行为的基本法则。各种因素或因素间的组合会影响物种的行为,观察到的行为取决于其所在地区现有的动机状态和刺激的出现。神经学家认为对任何动物来说,饥饿是其活动、学习和寻找食物的强大动力,是将生活条件改变为更稳定状态的力量。

社交生活促使动物避开捕食者,寻找食物来源,因为它们在自然协作中工作,这增加了它们的生存机会,这是进化的本质。健康的动物可以更好地找到食物来源,它们比弱小的动物有更大的生存机会,这种现象可以被称为自然界的饥饿游戏。无论是捕食者还是被捕食者,任何错误的决定都可能改变游戏的结果,导致一个个体的死亡,甚至整个物种的灭绝。动物的日常行为很大程度上受到一些动机情况的影响,例如饥饿和被猎人杀死的紧张感。饥饿是长时间“不吃东西”的一个特征,饥饿感越强烈,对食物的渴望就越强烈,机体就越积极地在短时间内寻找食物,以免为时已晚并导致饥饿或死亡。因此,当食物来源有限时,饥饿的动物之间会有一个寻找食物来源并赢得生存机会的逻辑博弈。因此,饥饿游戏是一种基于物种的逻辑博弈。

饥饿游戏搜索机制分为靠近食物和饥饿角色两部分。

1)靠近食物

群居动物在觅食过程中经常相互合作,但不排除少数个体不参与合作的可能性。为了用数学公式表示动物靠近食物的行为,该过程的位置更新公式如下:

(1)

表1 各算法实验参数设置

E=sech(|F(i)-BF|)

(2)

(3)

(4)

其中rand是[0,1]中的随机数。

2)饥饿角色

在这一部分中,个体在搜索中的饥饿特征通过一个提出的模型进行数学模拟。

(5)

(6)

其中b=1,x1=-π+(1-τ)·2π

x2=-π+τ·2π代表个体的饥饿程度,N代表个体的数量,SHungry是所有个体饥饿程度的总和,r3、r4和r5是[0,1]之间的随机数。

hungry(i)的公式如下

(7)

其中AllFitness(i)代表当前迭代位置的适应度值。

H的公式如下:

(8)

(9)

其中r6是[0,1]之间的随机数,F(i)代表每个个体的适应度值,BF是在当前迭代过程中获得的最佳适应度,WF是在当前迭代过程中获得的最差适应度,UB和LB代表搜索空间中的上限和下限。

综上所述,基本饥饿游戏搜索算法的流程图如图1所示。

图1 HGS算法流程图

3 精英反向学习t分布饥饿游戏搜索算法

3.1 精英反向学习策略

Tizhoosh[8]于2005年提出了一种反向解比当前解更接近于全局最优解的一种策略——精英反向学习策略,其主要原理是对问题的可行解求其反向解,并对原始解和反向解进行排序,从中选出较优解作为新一代个体进行下一次迭代。该策略可以增加种群多样性以及避免早熟现象。

(10)

(11)

精英反向学习(Elite Opposition-Based Learning,EOBL)是通过当前问题的可行解构造其反向解以此来自增加种群多样性,该策略已成功应用于多种算法的改进,如郭雨鑫、刘升[9]等人将EOBL策略引入黏菌算法的改进,提高了黏菌种群的多样性和种群质量。刘琨[10]等人将EOBL策略与纵横交叉策略来改进鲸鱼优化算法,提高算法跳出局部最优的能力。韩江、闵杰[11]在烟花爆炸式免疫遗传算法的基础上引入EOBL策略扩大全局搜索,有效解决了免疫遗传算法局部搜索能力弱、易早熟收敛的问题。

3.2 自适应t分布变异

t分布含参数自由度n,其曲线形态与自由度n的大小有关,n值越大,曲线越陡峭,曲线中间越高、双侧尾部态势越低,t(n→∞)→N(0,1),t(n=1)=c(0,1),其中N(0,1)为高斯分布,c(0,1)为柯西分布,即标准高斯分布和柯西分布是t分布的两个边界特例分布,三者的函数分布如图2所示。

图2 部分测试函数收敛曲线图

图2 t分布、高斯分布和柯西分布函数分布图

对于饥饿角色的位置状态xi=(xi1,xi2,…,xin)定义见下式

(12)

自适应t分布变异使用算法的迭代次数作为t分布的自由度参数,在算法运行初期,迭代次数较少,t分布变异近似于柯西分布变异,提高了算法的全局探索能力;在算法运行后期,t分布变异近似于高斯分布变异,提高算法的局部开发能力;在算法运行中期,t分布变异介于柯西变异和高斯变异之间,此时t分布变异算子结合了柯西变异算子和高斯变异算子的优势,即同时提高了算法的局部开发与全局探索的能力。

3.3 精英反向学习t分布饥饿游戏搜索算法

针对基本的饥饿游戏搜索算法存在寻优精度低、收敛速度慢、易陷入局部最优等缺点,本文提出了一种基于精英反向学习t分布的饥饿游戏搜索算法(EtHGS)。本文使用精英反向学习策略来提高种群多样性,采用群体选择机制,将当前饥饿角色群体与其反向群体按照适应度值排序,从中选出最优个体作为下一代饥饿角色个体来提高种群质量。另外,本文引入自适应t分布策略,在饥饿角色的个体中加入t分布型随机干扰项,充分利用当前种群的信息干扰,使个体跳出局部最优,收敛于全局最优,并且提高了收敛速度。

EtHGS具体执行步骤如下:

步骤1:设置相关参数;

步骤2:种群初始化,主要包括初始化种群个体数N、候选解维度d、最大迭代次数tmax;所有个体饥饿程度的总和SHungry;

步骤3:根据目标函数计算每一个饥饿角色的适应度值;

步骤5:根据αj=min(Xi,j),βj=max(Xi,j)计算个体的当前搜索边界;

步骤6:对种群中的每个个体根据式(10)生成精英反向解并添加到反向种群OP中;

步骤7:从当前种群和反向种群中选取适应度值较好的S个优良个体作为下一代种群;

步骤8:计算位置控制公式E;

步骤9:如果rand

步骤10:如果rand>p,直接利用式(2)来更新解,并对解做越界处理;

步骤11:判断迭代次数是否达到最大;若是,结束算法并输出最优解;反之,转向步骤9。

4 仿真与结果分析

4.1 仿真环境

本次仿真测试环境为:操作系统版本为Win10、64位操作系统,处理器为Intel(R) Core(TM) i5-10210U CPU 1.60GHz 2.11 GHz,内存16.0GB,主频2.11GHz,仿真软件为Matlab2020b。

4.2 实验参数设置

本文选取饥饿游戏搜索算法(HGS)、哈里斯鹰算法[12](HHO)、黏菌算法[13](SMA)、精英反向黄金正弦鲸鱼算法[14](EGoldenSWOA)以及本文提出的精英反向学习t分布饥饿游戏搜索算法对比(EtHGS),所有算法种群规模设置为30,迭代次数设置为500,共有参数保持一致。各算法的参数设置如表1所示。

4.3 测试函数

为了进一步验证EtHGS算法的优化效果和稳定性优于其它算法,本文对18个不同特点的测试函数进行函数优化对比测试,其中f1f5是单峰函数,用以评估算法的寻优精度和收敛速度;f6～f18是多峰函数,对算法的全局探索能力有更好的检验能力。测试函数及其具体信息如表2所示。

表2 本文选用的18个测试函数

4.4 与其它智能算法的对比分析

为验证EtHGS算法改进的合理性和有效性,本文对算法的性能在18个测试函数上进行了验证,为了避免实验偶然性带来的结果偏差,算法在各基准函数上独立运行30次。表3列出了饿游戏搜索算法(HGS)、哈里斯鹰算法(HHO)、黏菌算法(SMA)、精英反向黄金正弦算法(EGoldenSWOA)以及精英反向学习t分布饥饿游戏搜索算法(EtHGS)在多个标准函数上经过30次独立运行后得到的实验结果。

表3 测试函数实验结果

f1～f5为单模态函数,一般用于检测算法的开发能力。根据实验结果可知,对于f1、f3,EtHGS、HGS、SMA以及EGoldenSWOA寻优效果可以达到最优值,HHO的寻优效果最差;对于f2、f4,EtHGS以及HGS的寻优效果最佳,SMA也表现良好,EGoldenSWOA较差,HHO表现最差;对于f5,EGoldenSWOA寻优效果最好,EtHGS次之,HGS寻优效果一般,HHO较差,SMA最差;对于f6、f7、f8、f10、f12～f15,所测试的5种算法寻优效果均能达到最优值;对于f9,EGoldenSWOA寻优效果最好,EtHGS次之,HGS寻优效果一般,HHO较差,SMA最差;对于f11,EtHGS以及HGS的寻优效果最佳,EGoldenSWOA次之,HHO较差,SMA最差;对于f16～f18,EtHGS的寻优效果最佳,其平均值最接近测试函数最优值,标准差最小。综上所述,对于所选的测试函数,EtHGS算法明显好于一些新颖的算法。

为了直观展示EtHGS算法的寻优速度与性能,本文给出了部分基准函数的收敛曲线,如图2所示。

由图2的收敛曲线可以直观的看出改进EtHGS算法的收敛精度优于HGS、HHO、SMA和EGoldenSWOA,在收敛速度上也相对快于其它四种算法。函数f1～f5属于单模态函数,常常用来测试算法的开发能力,由f1～f4的收敛曲线图可知,改进后EtHGS算法的收敛速度有明显的提升,对于f1、f3,EtHGS算法在350次迭代后可以达到最优值,明显快于其它算法。另外,观察f7、f8、f13和f15的收敛曲线图可知,虽然改进后的算法寻优精度提高相对较小,但根据收敛曲线图可知,改进的算法能更快找到最优值,并且改进的算法在f8上出现了多个拐点,证明改进后的EtHGS算法容易跳出局部最优值,能更好地进行全局最优。

4.5 求解高维函数的实验分析

根据上述实验结果可知,论文改进的EtHGS算法对于低维函数得到了较好的寻优结果。但是一般的改进策略在较为复杂的现实问题上容易陷入“维数灾难”,为了更好地测试EtHGS算法的高维适应性,论文对EtHGS算法进行了高维函数测试实验,使得HGS算法、EtHGS算法、SMA算法、HHO算法在100维、200维、500维的测试函数上分别独立运行30次,其它参数设置同4.1节。

由表4的结果可知,EtHGS算法在各个维度上的四项指标均优于原始HGS算法、HHO算法以及SMA算法。EtHGS算法在3种高维状态下屡次收敛至f1～f4的理论最优值,例如,对于f1函数,EtHGS算法与其它三种算法比较最高提升了115个数量级,说明EtHGS算法提高了求解精度和鲁棒性。对于f5函数,EtHGS算法与其它三种算法在最优值的收敛表现不相上下;对于f9函数,EtHGS算法与其它三种算法相比平均高出1～5个数量级。综上所述,采用精英反向学习策略以及t分布型随机干扰项使得改进后的EtHGS算法可以充分搜索解空间,保留更多的优良个体,为算法奠定高质量迭代基础,并且很好的提高了精度和收敛速度这两方面。

表4 高维函数求解结果

5 结语

饥饿游戏搜索算法是近年来提出的一种新型寻优性能良好的启发式算法,本文针对原始饥饿游戏搜索算法收敛精度不高、易陷入局部最优等缺陷提出了精英反向学习t分布饥饿游戏搜索算法。本文利用精英反向学习策略改善了种群初始化,接着引入自适应t分布策略,在饥饿角色的个体中加入t分布型随机干扰项,使个体跳出局部最优,收敛于全局最优,并且提高了收敛速度,最终优化了整个算法的寻优性能。本文通过单模态、多模态和高维多个测试函数来验证改进后算法的性能,研究结果表明结合两种改进策略较好地提升了原始饥饿游戏搜索算法的全局寻优性能、收敛精度和速度以及算法鲁棒性。

已有文献表明群智能算法经常被应用于多个金融领域,例如金融信用风险评价、经济调度、证券市场分析、金融风险预警和产销不平衡等领域。柳宗伟等[15]提出以GIS (地理信息系统)为可视化分析平台、以神经网络和遗传算法为分析模型的综合选址方法;孙艺等[16]在一种非线性金融风险模型中引入改进后的粒子群算法选择最优控制参数,最大程度降低金融系统的总风险值。今后研究方向主要是拓展EtHGS算法优化神经网络参数在量化投资方面的应用。