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




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