搜索空间特征分析的新方法及其在适应性演化算法设计中的应用

In recent years, when we design evolutionary algorithms to solve real-world combinatorial optimization problems, there are few applications of the thoeretic results from problem analysis area. We have to spend lots of time and money to design algorithms or find the best parameters of algorithms. One of its major causes is that the application of thoeretic results of problem analysis is hard to use. In our proposal, we will design some new landscape descriptions, which are the results of problem analysis, and the process of computing their values. We will develop the mechanism of combinating algorithm execution process and the new landscape description computation process. And then, We will solve the core problem of this proposal -- landscape description based adaptive evolutionary algorithm design. our research work will focus on the trade-off between computation cost and acurracy of the landscape description. Our research work proposed will extend the new ideas for adaptive evolutionary algorithm design. Meanwhile, search based software engineering is a new research area originated from the combination of software engineering and optimization research, and there are lots of unsolved real-world optimization problems. To verify the performances of our adaptive evolutionary algorithms, We will evaluate our adaptive evolutionary algorithms on at least 4 classes optimization problems from software engineering area.

目前在演化优化算法的设计中，理论上分析优化问题特征的研究成果与算法设计实践之间联系较少，理论成果不能很好地应用到算法设计中，是造成算法实践中需要花费大量人工时间和精力进行算法设计和参数调优的主要原因之一。本项目申请针对该问题，通过设计优化问题搜索空间特征的新分析方法，并将其计算过程融入算法执行过程，研究二者相结合的机制，并以适应性演化算法设计目标展开研究，着重解决搜索空间特征描述计算代价和准确性二者的平衡问题。本项目的适应性算法研究将为适应性算法的研究发展拓展新的思路。在应用方面，基于搜索的软件工程是新兴的研究方向，源自软件工程领域和优化领域的交叉，其中有很多未解决的实际组合优化问题，本项目申请拟将设计的适应性演化算法应用于软件工程过程中至少4类不同的优化问题求解，验证本项目设计的适应性演化算法的有效性。

优化问题求解是实际工程应用中面临最基本问题，在其众多解法中，演化算法是适应能力最强，应用领域最广泛的方法。虽然演化优化算法的设计门槛相对较低，但是优化问题的特征与演化算法的设计实践之间关联甚少，导致演化算法在特定问题上与针对问题特征设计的优化方法相比，往往不能获得更好的结果，所以演化算法实践中需要花费大量人工时间和精力进行算法设计和参数调优。本项目研究了问题特征和演化算法设计关联起来的方法及其应用，项目研究内容和成果为进一步扩展演化算法在优化问题求解的能力具有重要科学意义。本项目主要研究内容和重要成果包括两个方面：(1) 设计和比较了4种不同的优化问题搜索空间特征分析方法。决策变量的权值学习方法，用学习的权值表征问题搜索空间的特征； “适应度-逃离概率云”方法，用于计算问题难度度量值，并设计了其采样计算过程；通过松弛原问题，分析决策变量作用，对变量进行分组和添加约束条件，实现对原优化问题的“强化”；设计了核矩阵来描述问题求解过程中群体的特征，用群体特征来描述问题搜索空间的局部特征。优化问题搜索特征空间的分析，为适应性演化算法的设计打下了基础。(2)适应性演化算法的设计及应用。将问题的特征“适应度-逃离概率”表示为“编码-适应度-逃离概率”映射表，设计新的算法并应用于集合覆盖问题；演化算法超参数的设计是应用中常面临的问题，提出了一种Parzen估计器应用于协方差矩阵适应性演化策略算法的超参数寻优问题；提出了一种基于行列式点过程的环境选择策略，用于超多目标优化问题，在解决不同类型的帕累托前沿面的优化问题中获得了目前最好的结果；我们设计了不同的适应性演化算法并用于软件工程领域中Web 服务组合问题、测试用例选择问题和下一版本问题的求解。