SCIENCE CHINA Information Sciences, Volume 60, Issue 3: 032105(2017) https://doi.org/10.1007/s11432-016-0089-7

Feature based problem hardness understanding for requirements engineering

More info
  • ReceivedMay 22, 2016
  • AcceptedJul 8, 2016
  • PublishedDec 6, 2016


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.



This work was supported in part by National Program on Key Basic Research Project (Grant No. 2013CB035906), New Century Excellent Talents in University (Grant No. NCET-13-0073), National Natural Science Foundation of China (Grant Nos. 61370144, 61403057), and Fundamental Research Funds for the Central Universities (Grant Nos. DUT15TD37, DUT16RC(4)62).


[1] Gong W, Cai Z, Liang D. Adaptive ranking mutation operator based differential evolution for constrained optimization. newblock IEEE Trans Cybern, 2015, 45: 716-727 Google Scholar

[2] Gong W, Cai Z. Differential evolution with ranking-based mutation operators. IEEE Trans Cybern, 2013, 43: 2066-2081 CrossRef Google Scholar

[3] Luo C, Cai S, Su K, et al. Clause states based configuration checking in local search for satisfiability. newblock IEEE Trans Cybern, 2015, 45: 1014-1027 Google Scholar

[4] Chen W N, Zhang J. Ant colony optimization for software project scheduling and staffing with an event-based scheduler. newblock IEEE Trans Softw Eng, 2013, 39: 1-17 Google Scholar

[5] Haeri S, Trajkovic L. Intelligent deflection routing in buffer-less networks. newblock IEEE Trans Cybern, 2015, 45: 316-327 Google Scholar

[6] Tang K, Yang P, Yao X. Negatively correlated cooperative search. arXiv:1504.04914. Google Scholar

[7] Jiang H, Xuan J, Ren Z. Approximate backbone based multilevel algorithm for next release problem. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, Portland, 2010. 1333--1340. Google Scholar

[8] Smith-Miles K A. Cross-disciplinary perspectives on meta-learning for algorithm selection. newblock ACM Comput Surv, 2008, 41: 6-327 Google Scholar

[9] Smith-Miles K A, van Hemert J I. Discovering the suitability of optimisation algorithms by learning from evolved instances. newblock Ann Math Artif Intell, 2011, 61: 87-104 Google Scholar

[10] Mersmann O, Bischl B, Trautmann H, et al. A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem. newblock Ann Math Artif Intell, 2013, 69: \-182 Google Scholar

[11] Smith-Miles K A. Towards insightful algorithm selection for optimisation using meta-learning concepts. In: Prcoeedings of International Joint Conference on Neural Networks, Hong Kong, 2008. 4118--4124. Google Scholar

[12] van Hemert J I. Evolving combinatorial problem instances that are difficult to solve. newblock Evol Comput, 2006, 14: 433-462 Google Scholar

[13] Vilalta R, Drissi Y. A perspective view and survey of meta-learning. newblock Artif Intell Rev, 2002, 18: 77-95 Google Scholar

[14] Oentaryo R J, Handoko S D, Lau H C. Algorithm selection via ranking. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence, Austin Texas, 2015. 1826--1832. Google Scholar

[15] van Hemert J I. Property analysis of symmetric travelling salesman problem instances acquired through evolution. In: Evolutionary Computation in Combinatorial Optimization. Berlin: Springer, 2005. 122--131. Google Scholar

[16] Xuan J, Jiang H, Ren Z, et al. Solving the large scale next release problem with a backbone-based multilevel algorithm. newblock IEEE Trans Softw Eng, 2012, 38: 1195-1212 Google Scholar

[17] Nie L, Jiang H, Ren Z, et al. Query expansion based on crowd knowledge for code search. newblock IEEE Trans Serv Comput, 2016, 9: 771-783 CrossRef Google Scholar

[18] Xuan J F, Martinez M, DeMarco F, et al. Nopol: automatic repair of conditional statement bugs in java programs. IEEE Trans Softw Eng, in press. doi: 10.1109/TSE.2016.2560811. Google Scholar

[19] Bagnall A J, Rayward-Smith V J, Whittley I M. The next release problem. newblock Inf Softw Tech, 2001, 43: 883-890 Google Scholar

[20] Greer D, Ruhe G. Software release planning: an evolutionary and iterative approach. newblock Inf Softw Tech, 2004, 46: 243-253 Google Scholar

[21] Ignatiev A, Janota M, Marques-Silva J. Towards efficient optimization in package management systems. In: Proceedings of the 36th International Conference on Software Engineering, Hyderabad, 2014. 745--755. Google Scholar

[22] Sun J, Zhang Q, Yao X. Meta-heuristic combining prior online and offline information for the quadratic assignment problem. newblock IEEE Trans Cybern, 2014, 44: 429-444 Google Scholar

[23] Ren Z, Jiang H, Xuan J, et al. New insights into diversification of hyper-heuristics. newblock IEEE Trans Cybern, 2014, 44: 1747-1761 Google Scholar

[24] Gao W F, Liu S Y, Huang L L. A novel artificial bee colony algorithm based on modified search equation and orthogonal learning. newblock IEEE Trans Cybern, 2013, 43: 1011-1024 Google Scholar

[25] Ren Z, Zhang A, Wen C, et al. A scatter learning particle swarm optimization algorithm for multimodal problems. newblock IEEE Trans Cybern, 2014, 44: 1127-1140 Google Scholar

[26] He J, Zhang J Y, Xuan J F, et al. A hybrid {ACO} algorithm for the next release problem. In: Proceedings of the 2nd International Conference on Software Engineering and Data Mining, Chengdu, 2010. 166--171. Google Scholar

[27] He J, Ren Z L, Li X C, et al. Transformed search based software engineering: a new paradigm of sbse. In: Search-Based Software Engineering. Berlin: Springer, 2015. 203--218. Google Scholar

[28] van Hemert J I. Evolving binary constraint satisfaction problem instances that are difficult to solve. In: Proceedings of Congress on Evolutionary Computation, Canberra, 2003. 1267--1273. Google Scholar

[29] Julstrom B A. Evolving heuristically difficult instances of combinatorial problems. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, Montreal, 2009. 279--286. Google Scholar

[30] Smith-Miles K A, Lopes L. Generalising algorithm performance in instance space: a timetabling case study. In: Proceedings of the 5th International Conference on Learning and Intelligent Optimization, Rome, 2011. 524--538. Google Scholar

[31] Toledo-Su{á}rez C D, Valenzuela-Rend{ó}n M, Terashima-Mar{\'\i}n H, et al. On the relativity in the assessment of blind optimization algorithms and the problem-algorithm coevolution. In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2007. 1436--1443. Google Scholar

[32] Hall N G, Posner M E. Performance prediction and preselection for optimization and heuristic solution procedures. newblock Oper Res, 2007, 55: 703-716 Google Scholar

[33] Leyton-Brown K, Nudelman E, Shoham Y. Empirical hardness models: methodology and a case study on combinatorial auctions. newblock J ACM, 2009, 56: 22-716 Google Scholar

[34] Smith-Miles K, Wreford B, Lopes L, et al. Predicting metaheuristic performance on graph coloring problems using data mining. In: Hybrid Metaheuristics. Berlin: Springer, 2013. 417--432. Google Scholar

[35] Nallaperuma S, Wagner M, Neumann F, et al. A feature-based comparison of local search and the christofides algorithm for the travelling salesperson problem. In: Proceedings of the 12th Workshop on Foundations of Genetic Algorithms XII. New York: ACM, 2013. 147--160. Google Scholar

[36] Smith-Miles K, Baatar D, Wreford B, et al. Towards objective measures of algorithm performance across instance space. newblock Comput Oper Res, 2014, 45: 12-24 Google Scholar

[37] Ruhe G, Ngo-The A. Optimized resource allocation for software release planning. newblock IEEE Trans Softw Eng, 2009, 35: 109-123 Google Scholar

[38] Wen L, Dromey R, Kirk D. Software engineering and scale-free networks. newblock IEEE Trans Syst Man Cybern, 2009, 39: 845-854 Google Scholar

[39] Pisinger D. Core problems in knapsack algorithms. newblock Oper Res, 1999, 47: 570-575 Google Scholar

[40] Pisinger D. Where are the hard knapsack problems? Comput Oper Res, 2005, 32: 2271--2284. Google Scholar

[41] Balas E, Zemel E. An algorithm for large zero-one knapsack problems. newblock Oper Res, 1980, 28: 1130-1154 Google Scholar

[42] Cule E. Ridge: Ridge Regression With Automatic Selection of The Penalty Parameter, 2014. R package version 2.1-3. https://cran.r-project.org/src/contrib/Archive/ridge/. Google Scholar

[43] Friedman J H. Multivariate adaptive regression splines1. newblock Ann Stat, 1991, 19: 1-141 Google Scholar

[44] Breiman L. Random forests. newblock Mach Learn, 2001, 45: 5-32 Google Scholar

[45] Hutter F, Xu L, Hoos H H, et al. Algorithm runtime prediction: methods & evaluation. newblock Artif Intell, 2014, 206: 79-111 Google Scholar

[46] Cule E, de Iorio M. Ridge regression in prediction problems: automatic choice of the ridge parameter. newblock Genetic Epidemiol, 2013, 37: 704-714 Google Scholar

[47] L{ó}pez-Ib{á}nez M, Dubois-Lacoste J, St{ü}tzle T, et al. The Irace Package, Iterated Race for Automatic Algorithm Configuration. Technical Report Technical Report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles, Belgium, 2011. Google Scholar

[48] Kuhn M. Caret: Classification and Regression Training, 2012. R package version 5.15-044. https://cran.r-project.org/ src/contrib/Archive/caret/. Google Scholar

[49] Milborrow S. Earth: Multivariate Adaptive Regression Splines, 2015. R package version 4.4.2. https://cran.r-project. org/src/contrib/Archive/earth/. Google Scholar

[50] Liaw A, Wiener M. Classification and regression by randomforest. newblock R News, 2002, 2: 18-22 Google Scholar

[51] Jiang H, Sun W, Ren Z, et al. Evolving hard and easy traveling salesman problem instances: a multi-objective approach. In: Simulated Evolution and Learning. Berlin: Springer, 2014. 216--227. Google Scholar

[52] Sun X, Gong D, Jin Y, et al. A new surrogate-assisted interactive genetic algorithm with weighted semisupervised learning. newblock IEEE Trans Cybern, 2013, 43: 685-698 Google Scholar

[53] Gong W, Zhou A, Cai Z. A multioperator search strategy based on cheap surrogate models for evolutionary optimization. newblock IEEE Trans Evol Comput, 2015, 19: 746-758 Google Scholar

[54] Nallaperuma S, Wagner M, Neumann F. Parameter prediction based on features of evolved instances for ant colony optimization and the traveling salesperson problem. In: Parallel Problem Solving from Nature --PPSN XIII. Berlin: Springer, 2014. 100--109. Google Scholar

[55] Tang K, Peng F, Chen G, et al. Population-based algorithm portfolios with automated constituent algorithms selection. newblock Inf Sci, 2014, 279: 94-104 Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有