大数据共性优化模型的高效算法研究

Many big data application problems can be modeled as some widely used common optimization models: the large-scale complex global optimization model and many-objective optimization model. The essential characteristics of these models are: large-scale, too complex (a huge number of local optimal solutions, nonlinear, nonconvex,etc.), and many objectives to be optimized. The shortcomings of the existing algorithms include: low efficiency (long execution time), low ability (very difficult to find global optimal solutions and easy to trap in local optimal solutions), and very difficult to find a representative set of uniformly distributed Pareto optimal solutions along whole Pareto front.In this project, for these common optimization models widely used and often appeared in various big data application problems, we shall focus our research on the following: design new techniques to transform large scale optimization problem into some small scale problems and thus greatly decrease the difficulty of problem solving; propose efficient methods which can eliminate a lot of local optimal solutions and thus greatly enhance the algorithm efficiency and reduce the difficulty of problem solving; design new methods to jump out from current local optimal solutions to other better ones and ensure the algorithm to find global optimal solution. As a result, the project will provide a new way to solve large scale complex global optimization models. For many objective optimization models, design new methods of sorting candidate solutions so as to overcome the drawback that Pareto optimal solution based sorting method will result in too many Pareto optimal solutions. Meanwhile, design new efficient scalarizing function methods so that it can find a representative set of Pareto optimal solutions which can reflect the whole distribution of Pareto front, and overcome the drawbacks that the existing algorithms can not find a representative set of well distributed solutions.

大数据领域中的很多应用问题可以建成共同类型的优化模型：大规模复杂全局优化模型和超多目标优化模型。这些模型的本质特征是：大规模、复杂（大量局部最优解）、超多目标。已有算法具有如下缺陷：效率低、能力差（难以求出真正的全局最优解，易陷入局部最优解）、对超多目标优化模型难以求出在整个解空间分布均匀的代表解集。本项目对大数据领域各类应用问题经常出现的这些共性模型，研究将大规模问题转化为小规模问题的高效新技术，极大减小求解难度；研究消除大量局部最优解的技术，极大提高求解效率并降低求解难度；研究跳出局部最优解的新技术，保证算法能求出真正全局最优解，为解决大规模复杂全局优化问题提供新的途径。对超多目标优化模型，研究解之间优劣排序的新方法，克服用Pareto最优解概念排序导致最优解数目太多的缺陷；同时研究新的高效聚合函数法，使其能求出反映最优解整体分布的代表解集，克服已有算法难以求出分布好的最优解集的缺陷。

本项目按计划研究了大数据共性优化模型的高效算法，并超额完成了研究计划中的所有任务和所有预期的研究成果。在国际和国内重要刊物上发表学术论文62篇，其中SCI检索期刊论文28篇、EI检索期刊论文15篇（SCI和EI论文不重复计算）、EI检索国际会议19篇。发表的28篇SCI论文中，有8篇发表在中科院一区和二区的国际期刊。所有成果中第一标注是该项目资助共计38篇，第二标注是该项目资助共计21篇。项目的主要研究成果包括：.首先，针对大数据建模成的大规模全局优化问题，为了解决高维度所造成的求解困难这一瓶颈，设计了变量的分组方法。所提方法能够根据函数的结构和特点，自动判别问题是否可以转化为若干小规模问题。再结合协同进化的思想，对多个子问题同时进行优化，提高了问题的求解效率。为了消除大量局部最优解，让算法尽快求出全局最优解，我们通过改造填充函数，放宽一些不易满足的条件，重新定义了一类更易于应用、包含参数更少甚至不包含参数、不容易溢出、效果更好的新函数类。这类函数保留了填充函数能跳出局部最优解的特点并克服了其缺点。再利用与填充函数法类似的框架和过程，对新的函数进行优化，从而可以跳出当前的局部最优解，更快地找到更好的解。.其次，针对大数据建模成的超多目标优化问题，提出了求解超多目标优化问题高效的聚合函数，设计了适合超多目标优化问题解的优劣性的新排序方法。为了使超多目标优化问题的Pareto解集均匀的分布在决策空间中，引入了均匀设计的方法在目标空间产生均匀分布的权向量；利用子种群策略增强算法的局部搜索能力；引入了正交设计与水平集的思想，通过设计合理的交叉算子来增加每个子问题的邻域信息，从而加强子问题间的相关性，提高算法的全局搜索能力。.最后，针对实际大数据环境下的大规模全局优化问题、多目标优化问题和超多目标优化问题，将上述优化理论和优化技术成功的应用于各个具体的大数据应用问题中。实验验证了所提优化模型的有效性和算法的高效性。