平衡探索与利用的广义鸽群优化算法_程适.pdf

平衡探索与利用的广义鸽群优化算法程适1,张明明1,史玉回2*,路辉3,雷秀娟1,王锐41.陕西师范大学计算机科学学院,西安 710119;2.广东省类脑智能计算重点实验室(南方科技大学),深圳 518055;3.北京航空航天大学电子信息工程学院,北京 100191;4.国防科技大学系统工程学院,长沙 410073*E-mail:收稿日期:2021-08-14;接受日期:2021-11-04;网络版发表日期:2022-08-03国家自然科学基金项目(批准号:61806119)、广东省重点实验室项目(编号:2020B121201001)、国家自然科学优秀青年基金项目(批准号:62122093)、季华实验室项目(编号:X210101UZ210)、中央高校基本科研业务费专项资金项目(编号:GK202003078)和陕西师范大学研究生创新团队项目课题(编号:TD2020014Z)资助摘要为了平衡鸽群优化算法的探索与利用能力,本文提出了一种广义鸽群优化算法.传统的鸽群优化算法包含两种优化算子,分别为地图与指南针算子和地标算子.这两种算子依次执行,在一次算法运行中,仅执行一轮迭代.在广义鸽群优化算法中,将算法搜索分为多个阶段,每个阶段分别执行两种算子.在算法的一次运行中,两种算子执行多轮.地图与指南针算子侧重于算法的探索能力,而地标算子侧重于算法的利用能力.改进算法仅改变了两种算子的执行顺序,无需增加额外的函数值计算.此外,广义鸽群优化算法扩展了解集合结构和算子参数设置,这对于提高算法的搜索质量大有裨益.在11个单目标测试函数和8个多模态优化测试函数上进行仿真对比试验,结果表明广义鸽群优化算法提高了鸽群优化算法的搜索效率,改进了算法的搜索结果.关键词群体智能,鸽群优化算法,探索与利用,多模态优化1引言群体智能(swarm intelligence)的核心思想是,若干个简单个体构成一个群体,个体间通过合作、竞争、认知与学习等机制表现出高级和复杂的功能,在缺少局部信息和模型的情况下,仍能够完成对复杂问题的建模、学习和优化求解.广义的群体智能可以分为四个方面:基于群体智能现象的仿真与建模、群体优化算法、群体学习算法、群体智能的应用.狭义的群体智能指群体智能优化算法,是一类利用群体智能来高效求解优化问题的方法.这类算法求解优化问题的模式为随机初始化求解变量,计算各个解对应的目标函数值,利用多个解之间的竞争和协作,不断迭代更新解集合,直到算法找到符合需求的解或者达到最大迭代次数.算法具有不依赖于梯度信息,对待求解问题无连续、可导等要求的特点,使得该类算法既适应连续型数值优化问题,也适应离散型组合优化问题.同时,群体智能优化算法潜在的并行性和分布式特点使引用格式:程适,张明明,史玉回,等.平衡探索与利用的广义鸽群优化算法.中国科学:技术科学,2023,53:268279Cheng S,Zhang M M,Shi Y H,et al.Generalized pigeon-inspired optimization algorithm for balancing exploration and exploitation(in Chinese).SciSin Tech,2023,53:268279,doi:10.1360/SST-2021-0371 2022 中国科学杂志社中国科学:技术科学2023 年第 53 卷第 2 期:268 279SCIENTIA SINICA T群体智能激发汇聚及应用专辑论 文其在处理大数据时具备显著优势.因此,群体智能优化算法受到各个领域越来越多的关注,成为一个热门的重要研究方向.鸽群优化(pigeon-inspired optimization,PIO)算法是一种典型的群体智能优化算法,算法设计基于鸽群独特的导航能力1,2.目前,群体智能优化算法在大多数低维单目标优化问题上取得了较好的优化结果,然而对于多模态优化问题,尚未获得良好的优化结果.多模态优化的目标是在算法的一次搜索过程中,尽可能寻找到多个极值解,并将这些极值解保持到搜索结束.多模态优化问题的难点在于如何平衡算法的求解精度和满足要求解的个数之间的矛盾.一味满足精度的要求,算法易陷入单个解中,解的个数不足;而过于强调解的个数,解集合的精益求精能力不足,优化解难以达到满意的精度.相同算法在不同的优化问题上求解性能差异明显,如何利用搜索中获得的信息,将问题的结构知识与优化算法的搜索状态相结合,是提高优化算法性能的重要途径.在群体智能优化算法中,可以根据求解信息,调整算法的探索(exploration)能力与利用(exploita-tion)能力,从而提高算法的搜索性能.使用过多的算法搜索信息,即过于侧重算法的利用能力,算法容易陷入局部最优解中;而相应地,使用过少的算法搜索信息,即过于侧重算法的探索能力,算法的搜索速度较慢,搜索效率低下.Ishii等人3研究了强化学习中探索与利用的参数控制方法;Alba和Dorronsoro4研究了细胞遗传算法搜索模型中的探索与利用比率;Lin和Gen5提出了一种自动调节策略来平衡演化算法的探索与利用能力;repinek与Hussain等人6,7分别总结了演化算法和基于群体的元启发式算法中的探索与利用能力;Li和Tan8总结了烟花算法中探索能力与利用能力的平衡策略.本文提出了一种平衡探索能力和利用能力的广义鸽群优化(generalized pigeon-inspired optimization,GPIO)算法,并将算法应用于多模态优化问题的求解.本文组织结构如下:第2部分介绍了本文的预备知识,包括群体智能、鸽群优化算法和多模态优化的基础知识;第3部分提出了一种平衡探索能力和利用能力的改进鸽群优化算法,并改进了解集合结构和参数设置;第4部分给出了改进鸽群优化算法在求解单目标优化问题和多模态优化问题上的实验结果;第5部分是本文结论和未来的研究方向.2背景知识本节对群体智能、鸽群优化算法和多模态优化问题进行简要介绍.2.1群体智能广义群体智能指基于多个简单个体组成的群体,利用群体间的协作、竞争、认知与学习模式,完成对复杂问题的学习和优化求解.群体智能包括四个方面的内容:基于群体智能现象的仿真和建模(swarm simu-lation)9、基于群体的智能优化算法(swarm optimiza-tion)、基于群体的智能学习算法(swarm learning)10和基于群体智能的应用,如群体机器人11、基于群体智能的协同通讯模型和协同感知技术12.群体优化算法是群体智能中的热门研究领域,以粒子群优化算法和蚁群优化算法为起始,基于物理学现象、生物学现象和人类群体行为的大量新算法被提出,其中代表性算法包括烟花算法(fireworks algo-rithm)8、头脑风暴优化算法(brain storm optimiza-tion)13,14和鸽群优化算法2,15.群体智能方法获得了广泛的研究和应用,如基于群体智能的协同通讯模型和协同感知技术12、群体机器人的参数控制模型优化16、多机器人室内环境地图构建17等.2.2鸽群优化算法受自然界中鸽群归巢行为的启发,鸽群优化算法模仿了鸽群在不同阶段使用不同导航工具的行为.算法1给出了鸽群优化算法的基本流程.图1是鸽群优化算法1鸽群优化算法基本流程输入:Nc=1,随机生成Np个初始个体(初始解),并分别计算所有个体的函数值;1while未达到预先设定的最大迭代次数do2if 迭代次NNcc1maxthen3利用地图与指南针算子优化解集合,更新Xg,Nc递增;4end if5if迭代次数NNN1).改进算法仅改变了两种算子的执行顺序,无需增加额外的函数值计算.3.2改进地图与指南针算子鸽群优化算法包含两种算子模型,在优化中仅需图 2广义鸽群优化算法的流程图Figure 2Flowchart of generalized pigeon-inspired algorithm.算法2广义鸽群优化算法基本流程输入:Nc=1,随机生成Np个初始个体(初始解),并分别计算所有个体的函数值,算子执行n轮,初始化n=1;1while未达到预先设定的最大迭代次数do2if迭代次数nNNNnN(1)+(1)cccc212then3利用地图与指南针算子优化解集合,更新Xn,NN=+1cc;4end if5if迭代次数nNNnNN+(1)cccc122then6利用地标算子优化解集合,更新Xn,NN=+1cc;7end if8if一组算子运行结束then9进入下一轮迭代,nn=+1;10end if11end while输出:算法找到的函数f()符合要求的优化解集合.中国科学:技术科学2023 年第 53 卷第 2 期271设置算法的参数,在一次求解中,两种算子依次执行各一轮.在地图与指南针算子中,如式(1)所示,算法使用了当前解集合的最优解Xg信息;在地标算子中,如式(3)所示,算法使用了解集合的加权中心位置Xc信息.在初始地图与指南针算子中,Xg为全局最优解信息,而多次使用全局最优解信息,算法容易陷入局部最优.在改进地图与指南针算子中,为解集合添加新的结构,将全局最优解信息Xg更改为局部最优解信息Xn,Xn为解的邻域最优解,可以减缓算法的收敛速度,保持解集合的多样性19.3.3改进地标算子在初始地标算子中,式(4)为种群规模的缩减方式.图3给出了三种设置下的缩减速率示例.由图可知,在初始的鸽群优化算法中,k设置为2,当算法种群规模Np=1024时,地标算子进行10代后,种群规模缩减为1.而当k=1.5时,在10次迭代后,算法种群由58缩减为1(1.510=57.665);当k=1.25时,在10次迭代后,算法种群由10缩减为1(1.2510=9.313).在优化算法求解实际问题中,种群规模Np常小于1000,k值过快的缩减为1,则XcN1c退化为当前全局最优解XgN1c,算法将快速收敛于XgN1c附近,解集合中所有解聚集于一点,算法易陷入局部最优,从而降低搜索效率.为了增加解集合的多样性,降低解集合的收敛速度,式(4)扩展为式(7):NNk=,(7)pNpN1cc其中,k为缩减因子.缩减因子k的设置决定了地标算子中解集合的缩减速率.采用较小的k值(如k=1.25),或将迭代后的种群规模Np维持在固定数值,可以避免种群规模过快缩减.在具有简化(simplified)地标算子的鸽群优化算法中,种群规模Np固定为初始种群规模的一半.4对比实验与结果分析为了检验提出的广义鸽群优化算法的搜索效率,实验采用了11个单目标优化测试函数和8个多模态测试函数,所选取的函数与文献19中一致.4.1算法参数设置在实验中,我们采用了6种算法,分别为3种鸽群优化算法(PIO,PIOr,PIOrs)和3种广义鸽群优化算法(GPIO,GPIOr,GPIOrs).符号G指广义鸽群优化算法,两种算子在一次运行中执行n轮;符号r指地图与指南针算子中,解集合采用环形结构;符号s指简化地标算子,在地标算子中,种群规模固定为原有种群的一半.例如,GPIOrs指广义鸽群优化算法,采用了环形解结构和简化地标算子.在实验中,算法均采用了相同的迭代次数和共同参数设置,地图与指南针因子R=0.2,初始种群规模N=100p,改进地标算子中,种群规模缩减因子k=1.25.所有优化问题均执行50次.4.2单目标优化问题实验采用了11个单目标最小化测试函数,如表1所示,其中f1f5为5个单峰问题,f6f11为6个多峰问题.测试函数均为50维优化问题,所有算法迭代1000次.鸽群优化算法中迭代次数N=900c1max,N=1000c2max;广义鸽群算法中,N=180c1,N=200c2,n=5.表2给出了6种算法在单峰问题的求解结果,表3给出了6种算法在多峰问题的求解结果.表格中,结果加粗部分为实验中6种算法的最优结果.实验结果显示,在50次测试中,GPIO算法找到的最优解和平均解,都优于对应的PIO算法,这表明GPIO算法明显改善了PIO图 3(网络版彩图)地标算子中种群规模N