基于自适应学习策略的改进鸽群优化算法
2021-01-06胡耀龙冯强海星朔任羿
胡耀龙,冯强,海星朔,任羿
(北京航空航天大学 可靠性与系统工程学院,北京100083)
仿生智能优化算法是根据自然界中生物种群所表现出来的群体行为特性所总结的一种算法,这类算法在处理复杂问题中具有良好的表现。
2014年,Duan和Qiao[1]根据鸽群归巢这一过程中鸽群所表现出的特殊的导航行为提出了鸽群优化(Pigeon-Inspired Optimization,PIO)算法,该算法在无人机编队和控制参数优化等领域已有很好表现[2-6],但是仍然存在一些诸如过早收敛、容易陷入局部最优等不足之处[7]。针对这些不足,许多学者提出了一些改进方案,从不同角度对标准PIO算法进行了改进。Duan等[8]通过使用导航过渡因子见表2因子tr将标准PIO两个算子合并在一个迭代循环中,并将鸽群的捕食逃逸机制引入到标准PIO中,提出了一种基于捕食逃逸鸽群优化(CPIO)算法。Yang等[9]提出了一种基于柯西分布的柯西变异鸽群启发优化(CMPIO)算法,在CMPIO算法中,分别利用柯西突变机制对PIO算法中的地图、指南针算子和地标算子进行了改进。Zhang和Duan[10]根据鸽群在飞行过程中个体间的等级制度,提出了一种新的基于社会等级的鸽群优化(SCPIO)算法,利用社会等级策略来增强标准PIO的收敛能力。Hua等[11]提出了一种自适应鸽群优化(APIO)算法,在APIO算法中,地图和指南针因子的参数设置随着迭代的进行而变化。Xiang等[12]提出了一种基于禁忌表的鸽群综合学习策略(CLPIO-TL),该策略利用综合学习策略和自适应调节机制,不同程度地提高了鸽群的学习能力,此外,CLPIO中还使用了自适应机制来增强全局搜索能力和局部搜索能力之间的平衡。Huo等[13]提出了一种基于动态对立学习策略的突变鸽群激励优化(MPIO)算法,该算法利用具有非线性特征的突变算子增强全局搜索能力,加速全局最优鸽子的收敛速度,同时引入动态的基于对立的学习策略,使算法具有较好的收敛速度。Hu等[14]提出了一种自适应算子量子行为鸽群启发优化(AOQPIO)算法,该算法采用地图和指南针因子R随着迭代次数的变化来平衡全局搜索能力和局部搜索能力,在地标算子阶段,提出了一个新的种群更新方程来增加搜索多样性。Liu等[15]提出了一种改进的粒子群优化(IPIO)算法,将粒子群优化(PSO)算法、逆因子和高斯因子引入PIO算法,该改进算法将原地图与指南针算子替换为PSO算法,避免了所有粒子的聚集状态,从而增加了群体的多样性,在地标算子中引入高斯因子,增强了全局搜索能力,将反向学习引入到算法中,并与粒子群的粒子学习相结合,有效地平衡全局搜索能力和局部搜索能力。Xu等[16]提出了一种独立搜索和多区域收敛鸽群启发优化(ISMCPIO)算法,该算法在PIO中引入独立搜索策略和多区域收敛机制,对包含可疑最优解的多区域进行综合搜索,提高了搜索的精度。Chen等[17]提出了一种基于量子数的混合鸽群优化(QPIO)算法,在该算法中,当前的最优解被认为是2个概率状态的线性叠加,通过量子旋转门平衡全局搜索能力和局部搜索能力。Hai等[18]将进化博弈理论引入到PIO算法中,提出了一种基于进化博弈论的自适应鸽群优化(EGTPIO)算法,在鸽群中展开双重策略进化博弈,在提高搜索效率的同时,通过增强操作符和参数之间的协调和分配来提高标准PIO算法的适应性。
本文在标准PIO算法的基础之上,引入自适应学习策略,提出了一种基于自适应学习策略的改进PIO(ALPIO)算法。所提算法针对标准PIO算法容易陷入局部最优的缺点,提出了一种基于容差的搜索方向调整策略,该策略通过判断鸽群的迭代信息,对鸽群的搜索方向进行调整;采用了基于自学习的候选者生成策略来保证该算法的搜索能力,采用了基于竞争学习的预测策略来保证算法的可用性。
1 改进的鸽群优化算法
在复杂优化问题的求解过程中,标准PIO算法容易陷入局部最优[19]。为此,本文在标准PIO算法地图与指南针算子的迭代过程中引入自适应学习策略,增强种群多样性,确保种群中个体具有更强的搜索能力、适应能力,提高算法搜索到全局最优的概率。ALPIO算法的流程如图1所示,图中t为迭代次数。3种策略的具体描述见1.2~1.4节。
1.1 ALPIO算法描述
步骤1 设定算法中各个参数的值,如种群数量N、搜索空间维数D、指南针因子R、地图和指南针算子最大迭代次数T1、地标算子最大迭代次数T2、最大迭代次数MaxIter。
图1 ALPIO算法流程Fig.1 Flowchart of ALPIO algorithm
步骤2 初始化个体的位置和速度,计算每个个体的适应度值,找出当前最好的位置。
步骤3 操作地图与指南针算子。更新个体的速度和位置,更新全局最优和个体历史最优。
步骤4 如果Prob_adjust>rand(),则停止使用当前全局最优;否则,转回到步骤3。
步骤5 使用基于自学习的候选者生成策略产生一个候选者。
步骤6 使用基于竞争学习的预测策略从候选者和当前全局最优中选取较优的作为新的全局最优。
步骤7 使用基于容差的搜索方向调整策略更新容差T和Prob_adjust。
步骤8 判断是否达到地图与指南针算子的最大迭代次数,若是,转到下一个操作;否则,转回到步骤3。
步骤9 操作地标算子。更新种群数量和位置,计算种群中心位置,更新全局最优和个体历史最优。
步骤10 判断是否达到地标算子的最大迭代次数,若是,输出全局最优解;否则,转回到步骤9。
1.2 基于容差的搜索方向调整策略
在鸽群优化算法地图与指南针算子的迭代过程在,个体的速度和位置更新方式为
时,可以认为鸽群有可能会陷入局部最优。式中:F(Xi)t为第i个个体在第t次迭代后的适应度值;Xi为第i个个体的位置。但是不能直接判定鸽群一定会陷入局部最优,因为在复杂优化问题的求解过程中,第t次迭代后的全局最优值Xgbest具有引导种群进化的潜力,在之后的迭代中有希望寻找到全局最优值。因此,为了避免算法陷入局部最优并充分利用Xgbest的进化潜力,本文提出了一个基于容差的搜索方向调整机制[20]。
定义一个容差T作为计数器,每当在一次迭代后,所有个体的最佳位置没有变化,T就根据式(3)进行更新。
Prob_adjust在每一次的迭代过程中更新一次,当满足Prob_adjust>rand()时,种群的搜索方向进行调整。种群不再使用当前全局最优位置Xgbest,而转向使用一个新候选者个体。
1.3 基于自学习的候选者生成策略
为了生成一个候选者来代替Xgbest在鸽群中的引导作用,本文提出了一种基于自学习的候选者生成策略。候选者的生成需要满足以下要求:①要充分利用鸽群中每个个体的最优位置信息;②要保证生成候选的候选者与全局最优Xgbest具有相似的结构。这种策略可以保证算法在每次的迭代过程中,充分利用每个个体的最优解结构,学习自身的优势。
为了使所生成的候选者能够有效地利用鸽群中所有个体的最优位置信息,并将种群引导出当前局部最优,对候选者的定义为
式中:N为种群数量。
综上所述,该策略充分利用了当前种群所有个体各自的个体最优解结构,保证了算法的寻优能力。
1.4基于竞争学习的预测策略
当候选者生成之后,不能直接用候选者代替Xgbest。因为候选者引导种群跳出当前局部最优的能力不一定比当前全局最优强。因此,为了提高算法的利用率,本文提出了一种竞争学习策略来预测候选算法的潜在引导能力。候选者生成后,ALPIO算法将在下一次迭代中通过评价个体学习候选者和Xgbest的性能来预测其潜在的引导能力。这2种个体学习的速度更新将遵循以下规则。
2 仿真实验
为了验证ALPIO算法的有效性和处理复杂优化问题的能力,在CEC2013基准测试函数[21]中分别选取2个单峰函数、4个多峰函数以及2个组合函数,在维度D=10、30以及50的情况下分别与标准PIO、标准PSO和EGTPIO进行对比优化实验,如表1所示。
2.1 参数设置
本文通过对5种算法在不同维度下的测试函数进行优化实验,其参数设置如表2所示。其中,迭代次数以及种群数量随着优化函数维度的不同而不同;PSO 算法中的学习因子c1、c2按照文献[22]推荐选择。
表1 测试函数Tab1e 1 Test functions
表2 参数设置Tab1e 2 Parameter setting
2.2 实验结果分析
为了直观体现ALPIO算法的优越性,选取同一个基准函数f17在不同维度(10维、30维和50维)下5个算法的迭代曲线。由图2(a)~(c)可以看出,随着搜索维度的增加,PIO、PSO以及EGTPIO容易过早收敛,陷入局部最优值;SCPIO虽然最终也能搜索到全局最优值,但在开始时会陷入局部最优;ALPIO由于增加了种群多样性,因此在每个维度下都能较快地收敛到全局最优值。可以看出,ALPIO不仅具有较好的收敛精度和较强的全局搜索能力,而且在不同维度上都表现出了良好的性能,具有普遍适用性。
针对不同维度(10维、30维、50维)在8个基准测试函数上对ALPIO、PIO、PSO、SCPIO和EGTPIO进行51次独立运行。这8个基准测试函数包含有单峰函数、多峰函数以及组合函数,因此具有一定的代表性,其测试结果能很好地显示所有算法的性能。测试结果如表3~表5所示。下面的数据涵盖寻优结果的最好值、最差值、中位数、平均值以及方差;其中,均值越小表明算法的搜索能力越强,方差越小表明算法的稳定性越强。
由数据可以看出,在不同维度下,ALPIO在所有的测试函数中都达到了最优值并保证方差为0。在单峰函数上,ALPIO的性能明显优于PIO,在10维基准函数f18上的性能表现:ALPIO =SCPIO>EGTPIO>PIO>PSO,随着维度的增加,ALPIO仍然保持着性能上的优势;在多峰函数上,ALPIO的最好值、最差值、中位数、平均值以及方差要明显优于PIO和PSO,在不同维度基准函数f17上,ALPIO的各项性能都要优于EGTPIO;在组合函数上,ALPIO的性能要优于PIO和PSO,与SCPIO和EGTPIO在各方面的指标都相同。综上所述,ALPIO在每个维度下都表现出了最优性能。
图2 D=10,30,50时f17迭代曲线Fig.2 Iteration curves of f17 at D=10,30,50
表3 D=10时测试函数上算法的性能比较Tab1e 3 Performance comparison of a1gorithms on test functions at D=10
表4 D=30时测试函数上算法的性能比较Tab1e 4 Performance comparison of a1gorithms on test functions at D=30
表5 D=50时测试函数上算法的性能比较Tab1e 5 Performance comparison of a1gor ithms on test functions at D=50
续表
3 结 论
针对标准PIO算法容易陷入局部最优值这一问题,本文提出了一种基于自适应学习策略的改进鸽群优化(ALPIO)算法。
1)所提算法通过基于容差的搜索方向调整策略和基于自学习的候选者生成策略及时调整种群的搜索方向,增强种群多样性和全局搜索能力,避免陷入局部最优。
2)所提算法通过基于竞争学习的预测策略选择具有更强领导能力的全局最优,从而增强局部搜索能力。
3)在不同维度上的基准函数优化实验结果表明,与标准的PIO、PSO、CPIO以及最新的EGTPIO算法相比,ALPIO在解决复杂性优化问题方面表现出明显的优势;实验结果表明,ALPIO不仅可以收敛到全局最优,而且可以跳出局部最优。