并行智能优化算法研究进展_张国.pdf

第 40 卷第 1 期2023 年 1 月控 制 理 论 与 应 用Control Theory&ApplicationsVol.40 No.1Jan.2023并并并行行行智智智能能能优优优化化化算算算法法法研研研究究究进进进展展展张国1,2,王锐1,2,雷洪涛1,2,张涛1,2,王凌3(1.国防科技大学 系统工程学院,湖南 长沙 410073;2.多能源系统智慧互联技术湖南省重点实验室,湖南 长沙 410073;3.清华大学 自动化系,北京 100084)摘要:基于种群迭代搜索的智能优化算法在农业、交通、工业等很多领域都取得了广泛的应用.但是该类算法迭代寻优的特点使其求解效率通常较低,很难应用到大规模、高维或实时性要求较高的复杂优化问题中.随并行分布式技术的发展,国内外很多学者开始着手研究智能优化算法的并行化.本文首要介绍了并行智能优化算法的基本概念;其次从协同机制、并行模型以及硬件结构3个维度综述了几类常见的并行智能优化算法,详细分析阐述了它们优点及不足;最后对并行智能优化算法的未来研究进行了展望.关键词:大规模优化;智能优化算法;并行计算;并行优化算法引用格式:张国,王锐,雷洪涛,等.并行智能优化算法研究进展.控制理论与应用,2023,40(1):1 11DOI:10.7641/CTA.2021.10084Survey on parallel intelligent optimization algorithmsZHANG Guo1,2,WANG Rui1,2,LEI Hong-tao1,2,ZHANG Tao1,2,WANG Ling3(1.College of Systems Engineering,National University of Defense Technology,Changsha Hunan 410073,China;2.Hunan Key Laboratory of Multi-Energy System Intelligent Interconnection Technology(HKL-MESI2T),Changsha Hunan 410073,China;3.Department of Automation,Tsinghua University,Beijing 100084,China)Abstract:Population based intelligent optimization algorithms have been widely used in a variety of fields such asagriculture,transportation and industry.However,their iterative search based behavior makes them inefficient in address-ing large-scale,high-dimensional and complex optimization problems,especially with high real-time requirements.Withthe development of parallel and distributed technology,many scholars in lots of countries began to study the parallel ofintelligent optimization algorithm.In this survey,we first introduce the basic concepts of parallel intelligent optimizationalgorithms.Second,several types of common parallel intelligent optimization algorithms are summarized from the per-spectives of coordination mechanism,parallel models and hardware structure.Also,their advantages and disadvantages arediscussed in detail.Finally,some future research on the parallelization of intelligent optimization algorithms is prospected.Key words:large-scale optimization;intelligent optimization algorithms;parallel computing;parallel optimizationalgorithmsCitation:ZHANG Guo,WANG Rui,LEI Hongtao,et al.Survey on parallel intelligent optimization algorithms.ControlTheory&Applications,2023,40(1):1 111引引引言言言国家大型工程设计、军事复杂系统决策、大规模交通网络优化以及工厂设备作业的调度中都存在各式各样的复杂优化问题,这些问题给基于梯度下降法这类传统数学优化方法带来了极大的挑战,特别是很多优化问题的目标函数不可导,甚至无法解析表达.智能优化算法是基于计算智能的机制求解复杂优化问题最优解或满意解的方法.它通过对生物、物理、化学、社会、艺术等系统或领域中的相关行为、功能、经验、规则、作用机理的认知,揭示优化算法的设计原理,在特定问题特征的导引下提炼相应的特征模型,设计智能化的迭代搜索型优化算法.简言之,基于种群的智能优化算法,如遗传算法(genetic algorithm,GA)1、蚁群算法(ant colony optimization,ACO)2、粒子群算法(particle swarm optimization,PSO)3等,采用个体表达待求解优化问题的候选解,随机生成初收稿日期:20210123;录用日期:20210923.通信作者.E-mail:;Tel.:+86 18874962006.本文责任编委:陈增强.国家优秀青年科学基金(62122093),国家自然科学基金项目(61973310),国防科技大学自主科研计划项目(ZZKYZX1104)资助.Supported by the National Science Fund for Outstanding Young Scholars(62122093),the National Natural Science Foundation of China(61973310)and the Scientific Key Research Project of National University of Defense Technology(ZZKYZX1104).2控 制 理 论 与 应 用第 40 卷始化种群,然后执行交叉、变异、评估、选择等操作,经过多次迭代搜索获得问题的最优解.相比于传统梯度下降优化方法,智能优化算法不需要问题目标函数的具体数学表达式,鲁棒性高,且全局搜索能力强,因而成为当前解决复杂优化问题的有效方法.同时,很多实际工程问题需要同时优化两个或两个以上的目标函数,统称为多目标优化问题.因为目标函数之间通常具有一定的冲突,即提升一个目标函数性能的同时会降低另一个目标函数的性能,即不存在一个解使得所有目标函数都达到最优,而是存在一组互有利弊的解集,称为Pareto最优前沿.传统数学优化方法因其一次运行只能找到一个解,因此在求解多目标优化问题时效率较低.基于种群思想的多目标优化算法,在一次寻优迭代的过程中可以找到多个Pareto解,逐渐成为解决多目标优化问题的主流方法.尽管上述智能优化算法在标准测试集或实际工程问题中都得到了良好的应用,但是随着大数据时代的到来,现实优化问题的规模和复杂性不断增加,对智能优化算法提出了新的挑战.例如面对大规模复杂优化问题时,尤其是搜索空间涉及大量局部最优点和个体解适应度计算成本较高的情况,仅在一个处理器上运行这类迭代搜索型优化算法时,常常会发生内存溢出问题,或者无法在可接受的时间成本内获得近似最优解.随着多核处理器(central processing unit,CPU)、图形处理器(graphics processing unit,GPU)、分布式计算机集群等物理硬件的更新,计算能力有了很大提升4.与此同时分布式并行技术也在不断发展,出现了很多先进的计算平台与框架,如:OpenCL,CUDA,Spark,Hadoop等.并行智能优化算法就是利用基于种群的智能优化算法具有天然的并行性特点和分布式并行技术,将智能优化算法部署在分布式系统上可以提高种群的多样性进而增强算法跳出局部最优的能力;另一方面结合分而治之的协同机制有望提高解决大规模复杂优化问题的能力.鉴于此,近些年来国内外学者对智能优化算法的并行化开展了大量研究,如图1所示.本文对智能优化算法的并行化相关研究进行综述,以便更好地梳理该领域取得的成绩和总结该领域未来发展的趋势.文章简单介绍了并行智能优化算法中的并行协同机制以及几类常见迁移拓扑结构.从4类主要并行模型(主从模型、细胞模型、岛屿模型、混合模型)以及硬件结构出发对智能优化算法并行化现有进展进行了讨论和总结.最后对未来研究进行了展望.2并并并行行行协协协同同同机机机制制制和和和迁迁迁移移移拓拓拓扑扑扑智能优化算法中的协同机制是将多个对象通过一定的策略展开协同搜索,以达到提升算法性能的目的,蕴含并行的思想在内5.下面将从种群协同、个体协同、算法协同、操作协同4个角度对并行智能优化算法中的协同机制进行简单介绍.500002002 2005文献数量趋势2008 2010 2012202020182015文献数量40000100002000030000年份2000图 1 并行智能优化算法相关研究发展趋势图(数据来源于Google学术搜索)Fig.1 The development trend diagram of parallel intel-ligent optimization algorithms(Data from GoogleScholar search)2.1种种种群群群协协协同同同种群协同机制主要借鉴同物种多子种群协同进化的原理,通过划分子种群与迁移精英个体实现协同搜索,通常基于岛屿模型,各岛屿(子种群)各自独立进化,岛屿间通过定期迁移精英个体共享搜索信息,协同进化,相关研究在本文第3.1节中再行阐述.2.2个个个体体体协协协同同同个体协同机制基于细胞模型选择不同的个体进行协作,个体被固定在物理拓扑结构下的网格内,通过邻域内的个体相互协作实现种群的进化,相关研究在本文第3.2节中再行阐述.2.3算算算法法法协协协同同同并行智能优化算法中的算法协同机制通过利用各种算法各自的优势协同搜索改善算法的性能,以解决日益复杂的问题.例如Risco等6异构并行执行SPEAII和NSGAII,要比其串行版本得到解质量更高且速度更快.刘福英等7结合SPEAII和NSGAII的优点,提出新的并行多目标进化算法并证明了其有效性.Wiak等8在主节点上利用椋鸟群优化算法(flock-of-starlings optimization,FSO)探索整个解空间,从节点执行PSO搜索解空间局部有效区域,并利用细菌趋化性算法(bacterial chemotaxis algorithm,BCA)改进PSO得到的解.Xing等9提出了集成GA与蚂蚁算法(ACO)的分布式协同进化算法.Deng等10提出集成GA和PSO并行协同算法优化模糊神经网络参数(fuzzy neu-ral network).Li等11融合了人工鱼群