面向大规模优化问题的分布式Memetic算法研究

Traditional centralized evolutionary algorithms (EAs) face the bottleneck problem of computing efficiency when dealing with large-scale and complex optimization problems. By combining the parallel computing power of distributed computing devices with the global and local search capability of memetic algorithms, this project proposes a novel distributed memetic algorithm for solving large-scale optimization problems. By making analysis and summary of the existing distributed model for EAs and the search characteristic of memetic algorithm, this project first proposes a new distributed parallel model for memetic algorithm. Based on the distributed model, multiple sub-populations are constructed and different sub-populations perform different local search strategies. These sub-populations realize cooperative coevolution by exchanging optimization information and accordingly adjust their local search strategies during the evolutionary process. Moreover, through the dynamic perception of the optimization states and environment, the cooperative communication strategy between different sub-populations is adjusted adaptively. As a result, the optimization efficiency of the distributed memetic algorithm can be further enhanced. This project eventually develops an efficient distributed memetic algorithm for large-scale optimization, and the proposed algorithm will be applied to solving large-scale wireless sensor network deployment problems.

传统的集中式进化计算方法在处理大规模复杂优化问题时存在计算效率方面的瓶颈问题。本项目将分布式计算的强大并行计算能力与Memetic算法的全局和局部优化能力相结合，提出一种面向大规模优化问题的新型分布式Memetic算法。首先，基于对已有进化算法分布式模型的总结分析，并结合Memetic算法的搜索特性，提出Memetic算法分布式并行实现的新模型。其次，在Memetic算法的分布式模型下构建多个并行子种群，通过多种群并行执行多种局部搜索策略，同时在进化过程中交换优化信息并相应调整局部搜索策略，实现多种群的协同进化；以及通过对算法优化状态和执行环境的动态感知，实现多种群的自适应协作通讯机制，进一步提高分布式Memetic算法的并行优化效率。最终，基于Memetic算法的分布式模型和协作通讯策略的研究，实现面向大规模优化的高效分布式Memetic算法，并应用于大规模无线传感器网络部署问题。

本项目针对传统集中式Memetic算法在处理大规模复杂优化问题时存在计算效率方面的瓶颈问题，将分布式计算的强大并行计算能力与Memetic算法的优化能力相结合，开展基于差分进化的分布式Memetic算法研究。首先，研究了Memetic算法的分布式并行模型。提出了基于差分“合并”、“分裂”的自适应分布式模型和基于空间位置信息的分布式模型，能够满足大规模优化问题对分布式种群资源高效利用的需求，更好地平衡分布式Memetic算法的全局搜索能力和局部搜索能力。代表性成果已发表在进化计算领域的国际顶级期刊IEEE Transactions on Cybernetics【中科院一区，影响因子：8.803】。其次，研究了分布式Memetic算法的多种群协作与通讯策略。提出了基于竞争的多种群协同进化策略和多样性驱动的自适应通讯策略，为提高分布式Memetic算法效率提供了新型的协同进化模式，并能在协作效率和通讯开销之间取得良好的平衡。代表性成果已发表在国际权威期刊Soft Computing【中科院三区，影响因子：2.367】和进化计算领域的国际顶级会议ACM GECCO、IEEE CEC。最后，将分布式Memetic算法在大规模优化、约束优化、不确定优化、多峰优化以及无线传感器网络部署等复杂实际问题上进行了应用和检验。分别提出了基于双种群协同进化和基于多目标优化的分布式Memetic算法，验证了所提出算法求解实际复杂优化问题的有效性和高效性。代表性成果已发表在国际权威期刊Information Science【中科院一区，影响因子：4.305】和Applied Soft Computing【中科院二区，影响因子：3.907】。基于以上研究，本项目共发表第一标注本项目基金号的国际学术期刊和学术会议论文10篇（项目负责人均为第一作者或通讯作者），其中SCI期刊论文5篇（中科院一区3篇、二区1篇、三区1篇，累计影响因子23.687），国际会议论文5篇（均被EI索引）；协助培养了硕士研究生4名（已毕业）和博士研究生3名（在读）。总体上，本项目已取得预期成果，达到预期目标。