基于多目标实例演化的问题结构分析及其应用

In the computational intelligence community, faced with the fact that the algorithm evaluation relies heavily on the benchmark instances, recent years have witnessed the increasing popularity of instance evolution based problem analysis. By explicitly generating diverse problem instance, instance evolution approaches are able to analyze both the strength and the weakness of the algorithms, and enabling the predicting the algorithm performance using problem-specific features. However, despite the great success, much remains to be done for the instance evolution studies.. Based on the comprehensive literature review, we summarize a series of research questions, which are presented as follows. (1) From the theoretical aspect: how to ensure the diversity of the problem instances, with respect to both the feature space and the performance space, and analyze the relationships between the two spaces. (2) From the algorithm design aspect: how to accelerate the instance evolution process. (3) From the algorithmic application perspective: how to expand the application scope of instance evolution. With the software upgradability problem as the case study, we propose a practical research plan. Through the project, the effectiveness and the applications of instance evolution based problem structure analysis could be greatly enhanced.

在计算智能领域，近年来针对算法性能评价依赖基准实例的现象，一类基于问题实例演化的方法被提出，并迅速获得研究人员的认可。实例演化方法具有通过生成多样性实例，实现客观分析算法优势和不足的能力，并提供了一种根据问题特征预测算法求解性能的机制。然而，实例演化方法的研究体系还远未完备，在理论基础、算法实现和应用推广层面均存在一系列亟待解决的关键问题。.. 本项目在归纳文献的基础上，凝炼出如下科学问题，包括（1）理论基础层面：如何保证实例问题特征和算法求解性能两个维度同时具有足够的多样性；（2）算法实现层面：如何实现实例演化的速度提升；（3）算法应用层面：如何将问题实例推广至非传统的问题域，如软件工程中的实际问题。结合已有工作基础，本项目设计了基于多目标实例演化的研究方案，并考虑以软件工程中的软件升级问题为例展开研究。本项目的实施，有望显著提升基于问题实例演化方法的效果和应用范围。

在计算智能领域，近年来针对算法性能评价依赖基准实例的现象，一类基于问题实例演化的方法被提出，并迅速获得研究人员的认可。实例演化方法具有通过生成多样性实例，实现客观分析算法优势和不足的能力，并提供了一种根据问题特征预测算法求解性能的机制。本项目在归纳文献的基础上，从三个层面展开研究（1）理论基础层面：如何保证实例问题特征和多样性；（2）算法实现层面：如何实现实例演化的速度提升；（3）算法应用层面：如何将问题实例推广至非传统的问题域，如软件工程中的实际问题。本课题严格按照课题申请书和计划书要求，分别对3个层面进行了深入研究，圆满完成了预定的研究任务。在本课题支持下，在本课题支持下，在 CCF A类期刊会议 IEEE Transactions on Software Engineering，ICSE，ASE，B类期刊会议PPSN，JCST 等领域著名会议上发表论文19篇。本课题一共支持了7位博士生，8 位硕士生，其中 3位博士生毕业，5位硕士生毕业。在课题的支持下，研究团队的科研水平显著提高，在国内外影响力明显提升。