Differential evolution with Pareto tournament for the multi-objective next release problem.

*(English)*Zbl 1338.90367Summary: Software requirements selection is the engineering process in which the set of new requirements which will be included in the next release of a software product are chosen. This NP-hard problem is an important issue involving several contradictory objectives that have to be tackled by software companies when developing new releases of software packages. Software projects have to stick to a budget, but they also have to cover the highest number of customer requirements. Furthermore, in real instances of the problem, the requirements tackled suffer interactions and other restrictions which complicate the problem. In this paper, we use an adapted multi-objective version of the differential evolution (DE) evolutionary algorithm which has been successfully applied to several real instances of the problem. For doing this, the software requirements selection problem has been formulated as a multiobjective optimization problem with two objectives: the total software development cost and the overall customer’s satisfaction, and with three interaction constraints. On the other hand, the original DE algorithm has been adapted to solve real instances of the problem generated from data provided by experts. Numerical experiments with case studies on software requirements selection have been carried out to demonstrate the effectiveness of the multiobjective proposal and the obtained results show that the developed algorithm performs better than other relevant algorithms previously published in the literature under a set of public datasets.

##### MSC:

90C29 | Multi-objective and goal programming |

68N30 | Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) |

##### Keywords:

software requirements selection; multi-objective evolutionary algorithm; differential evolution metaheuristic; search based software engineering; next release problem##### Software:

MOCell
PDF
BibTeX
XML
Cite

\textit{J. M. Chaves-González} and \textit{M. A. Pérez-Toledano}, Appl. Math. Comput. 252, 1--13 (2015; Zbl 1338.90367)

Full Text:
DOI

##### References:

[1] | Schwaber, K.; Beedle, M., Agile software development with scrum, (2001), Prentice Hall |

[2] | Bagnall, A. J.; Rayward-Smith, V. J.; Whittley, I., The next release problem, Inf. Softw. Technol., 43, 14, 883-890, (2001) |

[3] | Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP completeness, (1990), Freeman New York |

[4] | Coello, C. A.C.; Lamont, G. B.; Veldhuizen, D. A.V., Evolutionary algorithms for solving multiobjective problems, (2007), Springer New York |

[5] | Deb, K., Multi-objective optimization using evolutionary algorithms, (2001), John Wiley & Sons New Jersey · Zbl 0970.90091 |

[6] | Harman, M.; Mansouri, A.; Zhang, Y., Search based software engineering: trends, techniques and applications, ACM Comput. Surv., 45, 1, 11, (2012) |

[7] | Price, K.; Storn, R., Differential evolution - a simple evolution strategy for fast optimization, Dr. Dobb’s J., 22, 4, 18-24, (1997) |

[8] | Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast elitist multi-objective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 182-197, (2002) |

[9] | J. Karlsson, Software requirements prioritizing, in: Proceedings of the Second International Conference on Requirements Engineering (RE ’96), Colorado Springs, 1996, pp. 110-116. |

[10] | P. Baker, M. Harman, K. Steinhofel, A. Skaliotis, Search based approaches to component selection and prioritization for the next release problem, in: Proceedings of the 22nd IEEE International Conference on Software Maintenance, 2006, pp. 176-185. |

[11] | Greer, D.; Ruhe, G., Software release planning: an evolutionary and iterative approach, Inf. Softw. Technol., 46, 4, 243-253, (2004) |

[12] | Y. Zhang, M. Harman, S.A. Mansouri, The multi-objective next release problem, in: Proc. of the 9th conference on Genetic and evolutionary computation (GECCO ‘07), New York, 2007, pp. 1129-1137. |

[13] | Finkelstein, A.; Harman, M.; Mansouri, S. A.; Ren, J.; Zhang, Y., A search based approach to fairness analysis in requirement assignments to aid negotiation, mediation and decision making, Requirem. Eng. J. (RE ’08 Special Issue), 14, 232-245, (2009) |

[14] | A. Finkelstein, M. Harman, S.A. Mansouri, J. Ren, Y. Zhang, Fairness analysis in requirements assignments, in: Proc. 16th IEEE Int. Requirements Engineering Conf., Washington, DC, 2008, pp. 115-124. |

[15] | Charan Kumari, A.; Srinivas, K.; Gupta, M. P., Software requirements optimization using multi-objective quantum-inspired hybrid differential evolution, (Schüze, O.; etal., EVOLVE - A Bridge between Probability, (2013), Springer New York), 107-120 |

[16] | Durillo, J.; Zhang, Y.; Alba, E.; Nebro, A. J., A study of the bi-objective next release problem, Empirical Softw. Eng., 16, 29-60, (2009) |

[17] | H. Jiang, J. Zhang, J. Xuan, Z. Re, Y. Hu, A hybrid ACO algorithm for the next release problem, in: Proc. of the 2nd Intern. Conf. on Software Engineering and Data Mining, Chengdu, 2010, pp. 166-171. |

[18] | J. Knowles, D. Corne, The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimization, in: Proc. Congr. Evol. Comput. (CEC), 1999, pp. 98-105. |

[19] | Nebro, A. J.; Durillo, J. J.; Luna, F.; Dorronsoro, B.; Alba, E., Mocell: a cellular genetic algorithm for multiobjective optimization, Int. J. Intell. Syst., 24, 7, 726-746, (2009) · Zbl 1176.90552 |

[20] | Dorigo, M.; Stützle, T., Ant colony optimization, (2004), MIT Press Cambridge · Zbl 1092.90066 |

[21] | J. del Sagrado, I.M. del Águila, F.J. Orellana, Requirements interaction in the next release problem, in: Proc. of Genetic and Evolutionary Computation Conference (GECCO 2011), 2011, pp. 187-188. |

[22] | del Sagrado, J.; del Águila, I. M.; Orellana, F. J., Multi-objective ant colony optimization for requirements selection, J. Empirical Softw. Eng., (2014) |

[23] | J.T. Souza, C.L. Brito Maia, T.N. Ferreira, R.A. Ferreira do Carmo, M.M. Albuquerque Brasil, An ant colony optimization approach to the software release planning with dependent requirements, in: Proc. of the 3th Int. Symposium on Search Based Software Engineering (SBSE ’11), 2011, pp. 142-157. |

[24] | P. Carlshamre, K. Sandahl, M. Lindvall, B. Regnell, An industrial survey of requirements interdependencies in software product release planning, in: Proceedings of 5th IEEE international symposium on requirements engineering (RE 2001), 2001, pp. 84-93. |

[25] | D. Zaharie, A comparative analysis of crossover variants in differential evolution, in: Proc. of Intern. Multiconference on Computer Science and Information Technology (IMCSIT), 2007, pp. 171-181. |

[26] | Demsar, J., Statistical comparison of classifiers over multiple data sets, J. Mach. Learn. Res., 7, 1-30, (2006) · Zbl 1222.68184 |

[27] | Simmons, E., Requirements triage: what can we learn from a “medical” approach?, IEEE Softw., 21, 4, 86-88, (2004) |

[28] | Wiegers, K. E., Software requirements, (2003), Microsoft Press Redmon, WA |

[29] | Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Trans. Evol. Comput., 3, 4, 257-271, (1999) |

[30] | Chaves-González, J. M.; Vega-Rodríguez, M. A., DNA strand generation for DNA computing by using a multi-objective differential evolution algorithm, BioSystems, 116, 49-64, (2014) |

[31] | Chaves-González, J. M.; Martínez-Gil, J., Evolutionary algorithm based on different semantic similarity functions for synonym recognition in the biomedical domain, Knowl.-Based Syst., 37, 1, 62-69, (2013) |

[32] | Das, S.; Suganthan, P. N., Differential evolution: a survey of the state-of-the-art, IEEE Trans. Evol. Comput., 15, 1, 4-31, (2011) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.