基于决策变量分解的高维多目标优化方法研究

Evolutionary algorithms (EAs) have been widely used for multi-objective optimization problems (MOPs). But the performance of the traditional EAs deteriorates rapidly with the scale of the optimization problems increases. The divide-and-conquer strategy provides a good idea to solve the many-objective optimization problems (MaOPs). However, with no prior knowledge about the decomposition of the objective functions, and the objective functions are commonly conflicting with one another, it is difficult to divide the problem in a reasonable and effective way..With the decomposition of the high dimensional decision variables, this project is aimed at exploring a new many-objective optimization method for solving the large-scale complex problems. Firstly, based on mining the potential control characteristics of decision variables and the interaction relationship between two variables, an automatic decomposition strategy of the decision variables will be proposed, which decomposes the complex high-dimensional problem into a set of low-dimensional sub-problems. Secondly, according to the different characteristics of sub-problem, the candidate solution generation strategy based on the guide and the population selection strategy based on the key indicator would be proposed. Furthermore, the optimization strategy of the algorithm would be researched to overcome the time overhead caused by the high-dimension. Lastly, the large-scale cloud resource deployment case will be illustrated to verify the effectiveness of our methods. This project can expand the research scope of the many-objective optimization methods, and provide an efficient and novel method for solving the large-scale complex many-objective optimization problems. The research achievement can be employed to many practical application problems such as the large-scale cloud resource deployment problems.

进化计算被广泛用于求解多目标优化问题。但随着问题规模的增大，传统多目标优化算法的求解性能急剧下降。分而治之策略为解决高维多目标优化问题提供了新思路，但由于缺少对优化目标分解的先验知识，且多个优化目标间常存在冲突，难以对问题进行合理有效的划分。.本项目对高维决策变量进行分解，旨在提出适合大规模复杂问题求解的高维多目标优化方法。首先，充分挖掘决策变量对求解质量的潜在控制特性和变量间的相互关联，提出高维决策变量自动分解策略，将复杂的高维问题分解为多个规模较小的子问题；其次，针对各组变量的不同控制特性，提出基于向导的候选解产生策略和基于关键指标的种群选择策略；然后，研究算法效率优化策略以克服高维带来的时间开销；最后，通过大规模云资源部署实例开展算法的应用研究。该研究可拓展高维多目标优化计算的研究范畴，为求解大规模复杂多目标优化问题提供有效的新方法，研究成果可用于大规模云资源部署等实际应用领域。

大数据时代的来临使得各行各业所面临的数据都呈爆炸式增长，尤其在云计算领域，随着市场竞争的逐渐白热化，云服务供应商在云服务资源的部署问题上面临着新的挑战。云服务资源的急剧增加极大地扩展了问题搜索空间，部署方案的多样化需求也增大了问题建模的复杂程度。.进化计算被广泛用于求解多目标优化问题。但随着问题规模的增大，传统的多目标优化算法的求解性能急剧下降。针对高维下的多目标优化问题，本研究从候选解产生策略、非支配排序方法，以及算法在云资源部署问题下的应用方面开展了系统研究，为解决复杂环境下的目标优化问题提供了新理论和新方法，有效提高了高维下云资源部署问题的求解质量和求解效率。.本项目的主要创新工作概括如下：.（1）提出了基于向导的候选解产生策略，将每一轮迭代排名为1的解保存为精英解集，利用精英向导信息来指导新的候选解产生。实验结果显示，向导信息的加入可有效提高候选解的产生质量，有利于算法尽快收敛。.（2）提出了基于高效非支配排序的高维多目标优化方法，在算法迭代过程中应用高效非支配排序方法，每个个体仅与已经确定前沿面排名的个体进行比较，就可确定该个体的前沿面排名，避免进行冗余比较。实验结果表明该方法可以有效减少比较次数，大幅度提高运行效率。.（3）以最大化服务质量、最小化成本为优化目标，提出了基于成本效益优化的多目标服务组合模型，以满足用户在有限成本下选择服务质量最优的组合方案的需求。实验结果显示，在大规模服务数据集下，算法在多个评价指标上均可取得较好的效果，说明本算法能较好地应用于高维下的云资源部署问题。.（4）提出基于skyline计算的非线性服务组合方法，通过skyline计算筛选掉每个服务群中的冗余服务，进一步缩小搜索空间，提高云资源部署问题的求解效率。实验结果显示，skyline操作能在保证求解质量的前提下，有效地提高服务组合的求解效率，尤其在大规模服务数据量下，效果更为明显。