1. 引言
元启发算法在解决实际优化问题中得到了广泛的应用,它们具有多功能性、有效性和鲁棒性等诸多优良的特点。它们不仅可以用于处理具有连续和可微目标函数和约束的优化问题,还可以用于处理具有连续和离散变量的优化问题 [1]。
现在,有许多元启发算法被提出并应用。算法可以被分为四类:基于进化的、基于物理的、基于群智能的和基于人类行为的。基于进化的算法有:遗传算法(GA) [2]、差分进化算法(DE) [3] 和进化策略(ES) [4] 等;基于物理的算法有:引力搜索算法(GSA) [5]、人工化学反应优化算法(ACROA) [6] 和射线优化算法(RO) [7] 等;基于群智能的算法有:粒子群算法(PSO) [8]、灰狼算法(GWO) [9] 和狮群算法(LSO) [10] 等;基于人类行为的算法有:儿童绘画发展优化算法(CDDO) [11] 和头脑风暴算法(BSO) [12] 等。
鼠群优化算法(Rat Swarm Optimizer, RSO) [13] 是一种由Gaurav Dhiman等人在2020年提出的新型的仿生优化算法。RSO的灵感来自于自然界种鼠群追逐猎物和与猎物搏斗的行为。老鼠具有很丰富的社交智慧,它们通过追逐、跳跃和搏斗等各种行为相互沟通。它们具有很强的领土意识,当它们被侵犯时,就会变得非常有攻击性。RSO在数学上模拟了这种行为,并可以有效解决全局优化问题,此外它还具有结构简单和参数较少的优点。由于RSO的新颖性,关于修改或应用RSO的文献很少,但是它已经开始被应用到医药领域 [14] [15]。
然而,由于模拟鼠群追逐猎物的过程过于随机且不够精确,因此,RSO具有速度过慢和容易陷入局部最优等缺点。
为了改善RSO的性能,本文提出了一种基于反向学习的DE-RSO混合优化算法(Opposition-Based Learning DE-RSO Hybrid Optimizer, OBLDE-RSO),该算法首先使用一种DE-RSO混合策略,将差分进化算法的变异机制应用到RSO中,以增加种群的多样性,然后用反向学习策略(Opposition-Based Learning, OBL) [16],针对性地扩大个体的搜索范围,使个体以更高概率找到潜在的更加理想的求解区域。同时,为了加速算法收敛,对RSO本身的参数进行了调整优化。为了评估OBLDE-RSO的性能,本文使用了IEEE CEC2017基准测试函数集对算法进行测试。
本文的组织结构安排如下,引言后,第2节简单介绍了RSO算法,第3节阐述了OBLDE-RSO算法的详细信息,第4节对算法进行了测试并分析了实验结果,第5节对全文做了总结。
2. 鼠群优化算法
鼠群优化算法(RSO)是一种新型的群智能算法,它模拟了鼠群追逐猎物和与猎物搏斗的过程。
2.1. 追逐猎物
老鼠是一种社会性很强的动物,它们是通过社会群体行为来追逐猎物的。为了从数学上定义这种行为,将种群中最优个体的位置设定为猎物的位置,其他个体通过当前最优个体更新它们的位置。这个过程被定义为公式(1):
(1)
其中,
是鼠群中个体的位置,
是当前最优个体的位置,参数A和C分别通过公式(2)和公式(3)计算:
(2)
其中,
,t是当前迭代次数,MaxIteration是最大迭代次数。
(3)
参数R随机分布在区间[1, 5],参数C随机分布在区间[0, 2]。通过调整参数A和C的取值,以在平衡算法局部搜索和全局搜索之间取得折衷。
2.2. 与猎物搏斗
鼠群与猎物搏斗的过程可以被定义为公式(4):
(4)
其中,
是更新后的下一代个体的位置。该公式保存了全局最优个体的位置并且基于最优位置引导其他个体逐渐向最优位置靠近。表1给出了鼠群优化算法的伪代码。
Table 1. Pseudocode of RSO algorithm
表1. RSO的伪代码
3. 基于反向学习的DE-RSO混合优化算法
本节将DE-RSO混合策略和反向学习策略应用于RSO,提出一种基于反向学习的DE-RSO混合优化算法(OBLDE-RSO)。
3.1. DE-RSO混合策略
为了维持种群的多样性,将DE中的变异机制引入到RSO中,对种群中的个体进行振荡,同时在算法中引入一个参数B以提高算法的收敛速度。我们使用一个比例参数pcr来随机选择采用何种更新方式,所以鼠群搏斗的过程可以描述为公式(5):
(5)
其中,F为缩放参数,随机分布在区间[0.2, 0.8]中,r1和r2是两个互不相等的随机整数,即
和
是种群中随机选择的两个不同的个体,j是种群中个体的维度,jrand是集合
中的一个随机数。如公式(5),pcr是一个比例参数,算法设置当
且j = jrand时,算法将选择利用DE中的变异机制来对个体进行振荡,减小种群中个体落入局部最优的几率,使算法尽可能找到精确的全局最优解。否则,在公式(4)中引入一个衰减参数B,如公式(5),B会随着迭代过程不断变化,变化过程可由公式(6)和公式(7)描述:
(6)
(7)
其中,t是当前迭代次数,Maxiteration是最大迭代次数,由公式(7)可知,b会随着迭代次数的增加而由慢变快地变小,因此由公式(6)可知,B的变化过程与b是类似的,即B也是由慢变快的逐渐减小的。所以,由公式(5)可知,当
时,在算法搜索前期,个体的搜索范围波动较大,有更大的几率找到最优值,随着B的又慢变快地减小,在搜索的中后期,个体的搜索范围会缩小到现有的最优值附近,这样可以加速种群收敛于这个最优值。
3.2. 反向学习策略
学习和搜索是优化算法的基本任务,大多数情况下,学习是从一个随机点开始的,也就是说,从一开始沿着现有最优点的方向移动。例如,PSO的权值的随机初始化,GA中参数的随机配置等都是基于随机性。当我们想要求得一个实际问题的最优点x时,通常会先找一个估计点
。这个估计值并不精确,它可以是基于经验或者完全随机的猜测。在某些情况下,估计值
是令人满意的,但是一般情况下需要进一步缩小估计值
和最优值x的距离。从这个意义上讲,如果将一些优化问题转化为近似函数,那么必须求出其计算复杂度,但是在一般的情况下,计算的时间往往不符合实际问题的需求。
如果估计值距离最优点很近,可以加速算法收敛。反之,如果离最优点很远,并且假设在最坏情况之下,即在最优点的相反的方向,那么搜索过程将会消耗很大的成本。当然,在没有任何先验知识的情况下,很难做出理想的初始猜测。因此,我们应该同时做出多个方向猜测,具体地,应该更加关注相反的方向。如果,我们想要搜索最优点x,搜索相反的方向可以提高靠近最优点的几率,那么,算法搜索的第一步将是计算相反的点
[16]。
设x在区间[a, b]内,那么x的相反值
可以定义为以下形式:
(8)
这样的定义也可以应用于更加高维的情况,假设
是D维搜索空间中的一个点,而
在ai与bi的范围内,相反点
可以通过以下公式(9)得出:
(9)
由公式(8)和公式(9)可以看出,随机的猜测点和猜测它的相反值可以同时以更高的概率来找到潜在的更加理想的求解区域,其中最优解就很有可能位于其中。
在得到一个个体的相反个体后,同时计算该个体与其相反个体的适应度值,比较两者的适应度值,若其相反个体的适应度值优于原个体的适应度值,原个体将被相反个体所替代,这样个体将会用更高的概率靠近最优个体,计算效率和计算精确度会得到明显提高。表2给出了OBLDE-RSO的伪代码。
Table 2. Pseudocode of OBLDE-RSO algorithm
表2. OBLDE-RSO的伪代码
4. 实验结果与分析
本文引入了IEEE CEC2017基准测试函数集,利用该测试函数集测试OBLDE-RSO算法。IEEE CEC2017基准测试函数集由29个函数组成,包括2个单峰函数(g1, g3),7个简单多峰函数(g4-g10),10个混合函数(g11-g20)和10个组合函数(g21-g30)。测试函数集的具体细节可参照文献 [17]。
在本实验中,为了进行公平的比较,操作环境保持不变,如下:
1) 每个函数独立运行30次。
2) 种群规模为150,个体维度为30。
3) 函数的评估总次数为45,000次。
4) 搜索范围为[−100, 100]。
这些实验都是在一台具有I7处理器、windows 10操作系统和8 GB内存的计算机上执行的,所有算法都是在Matlab2018b中进行编码的。
为了证明OBLDE-RSO性能的优越性,我们将基于反向学习的DE-RSO混合优化算法OBLDE-RSO同鼠群算法RSO、差分进化算法DE、狮群算法LSO和遗传算法GA进行比较。表3列出了这些算法的参数。
Table 3. The parameters of the OBLDE-RSO, RSO, DE, LSO and GA
表3. OBLDE-RSO,RSO,DE,LSO和GA的参数
表4是OBLDE-RSO,RSO,DE,LSO和GA的对比结果,结果包括各算法在测试函数集中独立运行30次的平均值(Mean)和标准差(Std)。
由表4可知,在大部分情况下OBLDE-RSO的性能优于RSO、DE、LSO、GA。具体来说,在29个测试函数中,OBLDE-RSO在其中的27个对RSO、DE、LSO、GA表现出了更加出色的性能。OBLDE-RSO在单峰函数、简单多峰函数和混合函数上,在求解的精确度上比其他比较算法具有绝对的优势。在组合函数上,OBLDE-RSO也具有十分优异的性能。这说明DE-RSO混合策略和反向学习策略的使用也可以提高RSO的性能。
另外,在四类测试函数中各挑取一个代表函数(g1, g6, g16, g24)绘制收敛图和盒型图,以进一步分析实验结果。图1和图2分别是算法在四个函数中的测试后的收敛图和盒型图。
图1中可以直观地展示出OBLDE-RSO,RSO,LSO,DE和GA的收敛性能。OBLDE-RSO的收敛趋势线比其他比较算法的收敛速度更快,同时,OBLDE-RSO的收敛精度也高于其他比较算法,这进一步证实了使用两种策略可以提高算法的收敛速度和收敛精度。
在图2中,盒型图展示出4次实验得到的实验结果。由图可以看出,在绝大多数情况下,OBLDE-RSO的结果优于其他比较算法,说明OBLDE-RSO具有更加优越和稳定的数据结构。
Table 4. Comparison results of OBLDE-RSO, RSO, DE, LSO and GA
表4. OBLDE-RSO,RSO,DE,LSO和GA的对比结果
Figure 1. Convergence curves of each test function
图1. 各算法的收敛曲线对比图
Figure 2. Box chart comparison results of each test function
图2. 算法的盒图对比结果
5. 结论
本文提出了一种改进的鼠群优化算法——基于反向学习的DE-RSO混合优化算法,算法使用了DE-RSO混合策略和反向学习策略以提高算法的性能。DE-RSO混合策略使用变异机制以保持种群多样性并降低算法陷入局部最优的可能性,可以有效改善RSO过早收敛的缺点。OBL策略可以针对性地扩大个体的搜索范围,使个体以更高概率找到潜在的更加理想的求解区域。同时添加一个参数B以控制算法在搜索前期和后期的不同搜索任务。通过对比OBLDE-RSO和其它比较算法在IEEE CEC2017测试函数集上的实验数据和图像,证明了使用了两种策略后,算法的局部搜索能力和全局搜索能力都得到了很大的提升。
基金项目
国家自然基金面上项目——基于多智能算法融合模型的多级并行叠前分频波形反演研究,41772123。