面向大规模优化问题的基于云计算模型的协同差分进化方法研究

Solving large-scale optimization problems, which involves thousands of variables, is one of the most challenging topics in numerical evolutionary optimization. Based on the model of Cloud Computing and the framework of Differential Evolution algorithm, a novel way was investigated to solve the large-scale optimization problems with divide-and-conquer strategy in this project. Firstly, a model of potential interactions between the decision variables of the problem is constructed and the discrete Differential Evolution was used to optimize the model. Based the model, a way to group the variables which have potential dependence into the same sub problem in Cloud Computing was proposed. Then with the MapReduce programming model, cooperative model and evolution algorithm based on Cloud Computing was investigated. We will develop tailor-made variants of Differential Evolution which will be deployed in the Cloud Computing using novel strategies for parameter control and different evolution schemes to improve its performance. Further, we will investigate the deployment of the different Differential Evolution in Cloud Computing, several different schemes for cooperation and cooperative evolution to solve twenty large-scale optimization benchmark problems using the open source platform Hadoop. The outcomes of this project will reveal the principles of the Cooperative Differential Evolution based the model of Cloud Computing and provide a new scalable method for solving large-scale optimization problems. Thus this project will not only enrich the theory of the Differential Evolution computation, but also enable many new practical engineering applications.

大规模优化问题的求解涉及成千上万个决策变量，一直是数值进化优化领域中的一个挑战。本项目采用"分而治之"策略，基于云计算模型和差分进化算法框架，探索大规模优化问题的求解新方法。首先，建立决策变量相关性检测模型，研究利用离散差分进化算法优化此模型，提出面向云计算模型的大规模优化问题分解方法；其次，利用云计算MapReduce编程模型，从参数控制与进化模式两个方面，研究基于云计算模型的协同差分进化模型与算法；进一步以云计算模型MapReduce的开源实现Hadoop为实验平台，以20个大规模标准测试问题为求解对象，研究云计算平台各个结点之间的协同进化机制。本项目有望揭示基于云计算模型的协同差分进化原理，为大规模优化问题的求解，建立基于云计算模型的协同差分进化求解新方法。本项目研究成果不仅可以丰富差分进化计算理论，也将推动优化理论在工程实际中的应用。

本项目针对大规模复杂优化问题，基于云计算进化模型探索分布式协同差分进化算法。主要研究了大规模优化问题的分解、高性能差分进化优化算法、云模型下的差分进化算法以及基于分解方法的大规模优化问题的分布式求解方法，取得了一系列成果。.1.大规模优化问题的分解。在加性可分原理和经典的DG(Differential Grouping)分组基础上，提出一种新的高效分组方法NDG。在此基础上，提出一种大规模优化求解的新型协同差分进化方法。对于随机分组和几种不同的确定性分组技术进行对比实验，我们发现如果追求分解的精度，必然需要消耗较大的计算资源，而随机分组无需计算资源，是云计算平台下的一种较好选择。.2.高性能差分进化算法。从进化模式，进化算子，实验设计方法，参数控制，基于学习策略等方面，开展了大量的研究工作。设计了新算法基于对偶的Dual of DE、基于精英学习的方法，提出一种ELDDE算法、三角的骨架差分进化算法- tBBDE、基于共生学习与均匀局部学习的差分进化算法CUDE、基于杂合与田口局部搜索的THDE算法、一种带有精英混沌局部搜索的差分进化算法-DEECL、基于正交实验设计的差分进化算法ODDE、DDEOOC。.3. 云模型下的差分进化算法。.分别在MapReduce云模型与RDD云模型下，研究新型分布式优化器。提出一种云DE算法、分布式差分进化算法 DDE-MR、分布式粒子群算法- DPSO-MR、基于弹性分布式数据集模型的并行差分进化算法-PDE、基于RDD云计算模型的并行差分进化算法-SparkDE、一种求解大规模优化问题的云差分进化算法-SparkCUDE。.4.基于分解方法的大规模优化问题求解。研究提出了求解大规模优化问题的新型协同差分进化算法DECC-NDG-CUDE、求解大规模优化问题的云协同差分进化算法- SparkDECC。在SparkDECC中，系统研究了不同协同方式对于求解性能的影响，发现随机组合的协同方式性能优于最优组合与洗牌组合。