点击次数：

论文类型：期刊论文

发表时间：2017-03-01

发表刊物：SCIENCE CHINA-INFORMATION SCIENCES

收录刊物：SCIE、EI、CSCD、Scopus

卷号：60

期号：3

ISSN号：1674-733X

关键字：problem hardness; next release problem; computational intelligence; requirements engineering; evolution algorithm

摘要：Heuristics and metaheuristics have achieved great accomplishments in various fields, and the investigation of the relationship between these algorithms and the problem hardness has been a hot topic in the research field. Related research work has contributed much to the understanding of the underlying mechanisms of the algorithms for problem solving. However, most existing studies consider traditional combinatorial problems as their case studies. In this study, taking the Next Release Problem (NRP) from the requirements engineering as a case study, we investigate the relationship between software engineering problem instances and heuristics. We employ an evolutionary algorithm to evolve NRP instances, which are uniquely hard or easy for the target heuristic (Greedy Randomized Adaptive Search Procedure and Randomized Hill Climbing in this paper). Then, we use a feature-based method to estimate the hardness of the evolved instances, with respect to the target heuristic. Experimental results demonstrate that, evolutionary algorithm can be used to evolve NRP instances that are uniquely hard or easy to solve. Moreover, the features enable the estimation of the target heuristics' performance.