Biogeography-Based Optimization with Brownian Population for the MultiObjective Next Release
Subject Areas :
Mohsen Qasemi
1
,
Mehdi Talebi
2
1 - Department of Computer Engineering, Larestan Branch, Islamic Azad University, Larestan, Iran
2 - Department of Computer Engineering, Larestan Branch, Islamic Azad University, Larestan, Iran
Keywords: Next release problem, Multiobjective optimization, Biogeography-based optimization, Brownian population, Search-based software engineering,
Abstract :
Software developers must decide which requirements to implement in next version. Selecting a set of requirements for the next software release is a complex NP-hard problem known as the Next Release Problem (NRP). We propose a multi-objective biogeography-based optimization algorithm for this problem. Furthermore, inspired by the Brownian-like random-walk, a population called the Brownian population is produced and combined with the biogeography-based optimization algorithm. We propose a novel approach to calculate the migration probability to each habitat based on the ratio of objective functions. We also employ two approaches: merging solutions and populations with non-duplicate members in algorithm iterations. Two datasets and quality indicators of hypervolume (HV), Spread, and the number of non-dominated solutions (NDS) are used for evaluation. To investigate the impact of the Brownian population and non-duplicate population, we implement the proposed algorithm, along with three other versions of the biogeography-based algorithm, to solve the next release problem and compare their results. The results demonstrate that the proposed method improves the biogeography-based algorithm. The Brownian population is more effective in improving Spread, while the non-duplicate population is more effective in increasing the number of non-dominated solutions. Compared to other similar research, the proposed algorithm outperforms previously reported algorithms.
[1] G. Brau, J. Hugues, N. Navet, "Towards the systematic analysis of non-functional properties in Model-based engineering for real-time embedded systems", Science of Computer Programming, vol. 156, pp. 1–20, Dec. 2017, doi: https://doi.org/10.1016/j.scico.2017.12.007.
[2] M. Harman, S. A. Mansouri, Y. Zhang, "Search-based software engineering", ACM Computing Surveys, vol. 45, no. 1, pp. 1–61, Nov. 2012, doi: https://doi.org/10.1145/2379776.2379787.
[3] S. Katoch, S. S. Chauhan, V. Kumar, "A review on genetic algorithm: past, present, and future", Multimedia Tools and Applications, vol. 80, no. 5, Oct. 2020, doi: https://doi.org/10.1007/s11042-020-10139-6.
[4] T. Chen and M. Li, "The weights can be harmful: pareto search versus weighted search in multi-objective search-based software engineering", ACM Transactions on Software Engineering and Methodology, Apr. 2022, doi: https://doi.org/10.1145/3514233.
[5] A. J. Bagnall, V. J. Rayward-Smith, I. M. Whittley, "The next release problem", Information and Software Technology, vol. 43, no. 14, pp. 883–890, Dec. 2001, doi: https://doi.org/10.1016/s0950-5849(01)00194-x.
[6] B. Liu, G. Zhou, Y. Zhou, Q. Luo, Y. Wei, "Quantum-inspired multi-objective african vultures optimization algorithm with hierarchical structure for software requirement", Cluster Computing, vol. 27, no. 8, pp. 11317–11345, May 2024, doi: https://doi.org/10.1007/s10586-024-04503-6.
[7] José del Sagrado, A. Sierra, I. María, "An estimation of distribution algorithm based on interactions between requirements to solve the bi-objective Next Release Problem", Journal of Systems and Software, vol. 199, p. 111632, May 2023, doi: https://doi.org/10.1016/j.jss.2023.111632.
[8] Seyedali Mirjalili, Jin Song Dong, A. Lewis, "Nature-inspired optimizers", Springer, 2019.
[9] I. Rahimi, A. H. Gandomi, M. R. Nikoo, F. Chen, "A comparative study on evolutionary multi-objective algorithms for next release problem", Applied Soft Computing, vol. 144, p. 110472, May 2023, doi: https://doi.org/10.1016/j.asoc.2023.110472.
[10] C. A. Coello Coello, S. González Brambila, J. Figueroa Gamboa, M. G. Castillo Tapia, R. Hernández Gómez, "Evolutionary multiobjective optimization: open research areas and some challenges lying ahead", Complex & Intelligent Systems, vol. 6, no. 2, pp. 221–236, Jun. 2019, doi: https://doi.org/10.1007/s40747-019-0113-4.
[11] J. Dong, W. Gong, F. Ming, L. Wang, "A two-stage evolutionary algorithm based on three indicators for constrained multi-objective optimization", Expert Systems with Applications, vol. 195, p. 116499, Jun. 2022, doi: https://doi.org/10.1016/j.eswa.2022.116499.
[12] Y. Zhang, M. Harman, S. A. Mansouri, "The multi-objective next release problem", Proceedings of the 9th annual conference on Genetic and evolutionary computation, pp. 1129-1137, London, England, 2007, doi: https://doi.org/10.1145/1276958.1277179.
[13] J. del Sagrado, I. M. del Águila, F. J. Orellana, "Multi-objective ant colony optimization for requirements selection", Empir. Softw. Eng., vol. 20, no. 3, pp. 577–610, 2015.
[14] J. M. Chaves-González, M. A. Pérez-Toledano, A. Navasa, "Teaching learning based optimization with pareto tournament for the multiobjective software requirements selection", Engineering Applications of Artificial Intelligence, vol. 43, pp. 89–101, Aug. 2015, doi: https://doi.org/10.1016/j.engappai.2015.04.002.
[15] S. P. Adam, S.-A. N. Alexandropoulos, P. M. Pardalos, M. N. Vrahatis, "No free lunch theorem: a review", in Springer Optimization and Its Applications, Cham: Springer International Publishing, 2019, pp. 57–82. doi: http://dx.doi.org/10.1007/978-3-030-12767-1_5.
[16] X. Cai, M. Hu, D. Gong, Y. N. Guo, Y. Zhang, Z. Fan, Y. Huang, "A decomposition-based coevolutionary multiobjective local search for combinatorial multiobjective optimization", Swarm and Evolutionary Computation, vol. 49, pp. 178–193, Sep. 2019, doi: 10.1016/j.swevo.2019.05.007.
[17] W. H. Dukhan, M. H. Mohamed, A. A. Amer, E. A. Zanaty, O. Reyad, "Software requirement selection using a combined multi‐objective optimisation technique", IET Software, vol. 16, no. 6, pp. 558–575, Aug. 2022, doi: 10.1049/sfw2.12070.
[18] L. Li, "Exact analysis for next release problem", 2016 IEEE 24th International Requirements Engineering Conference (RE), pp. 438-443, Beijing, China, 2016, doi: 10.1109/RE.2016.7.
[19] P. Singh, M. S. Bhamrah and J. Kaur, "Jaya algorithm using weighted sum approach for the multi-objective next release problem", 2018 First International Conference on Secure Cyber Computing and Communication (ICSCCC), pp. 273-277, Jalandhar, India, 2018, doi: 10.1109/ICSCCC.2018.8703315.
[20] X. Cai and O. Wei, "A hybrid of decomposition and domination based evolutionary algorithm for multi-objective software next release problem", 2013 10th IEEE International Conference on Control and Automation (ICCA), pp. 412-417, Hangzhou, China, Jun. 2013, doi: 10.1109/ICCA.2013.6565143.
[21] M. Á. Domínguez-Ríos, F. Chicano, E. Alba, I. del Águila, J. Del Sagrado, "Efficient anytime algorithms to solve the bi-objective next release problem", Journal of Systems and Software, vol. 156, pp. 217–231, Oct. 2019, doi: https://doi.org/10.1016/j.jss.2019.06.097.
[22] D. Greer and G. Ruhe, "Software release planning: an evolutionary and iterative approach", Information and Software Technology, vol. 46, no. 4, pp. 243–253, Mar. 2004, doi: https://doi.org/10.1016/j.infsof.2003.07.002.
[23] J. J. Durillo, Y. Zhang, E. Alba, M. Harman, A. J. Nebro, "A study of the bi-objective next release problem", Empirical Software Engineering, vol. 16, no. 1, pp. 29–60, Dec. 2010, doi: 10.1007/s10664-010-9147-3.
[24] J. del Sagrado, I. M. del Águila and F. J. Orellana, "Ant colony optimization for the next release problem: a comparative study", 2nd International Symposium on Search Based Software Engineering, pp. 67-76, Benevento, Italy, 2010, doi: 10.1109/SSBSE.2010.18.
[25] J. M. Chaves-González and M. A. Pérez-Toledano, "Differential evolution with pareto tournament for the multi-objective next release problem", Applied Mathematics and Computation, vol. 252, pp. 1–13, Dec. 2014, doi: https://doi.org/10.1016/j.amc.2014.11.093.
[26] N. Ranjith and A. Marimuthu, "A multi objective teacher-learning-artificial bee colony (MOTLABC) optimization for software requirements selection", Indian Journal of Science and Technology, vol. 9, no. 34, Sep. 2016, doi: https://doi.org/10.17485/ijst/2016/v9i34/95638.
[27] A. Hamdy and A. A. Mohamed, "Greedy binary particle swarm optimization for multi-objective constrained next release problem", International Journal of Machine Learning and Computing, vol. 9, no. 5, pp. 561–568, Oct. 2019, doi: https://doi.org/10.18178/ijmlc.2019.9.5.840.
[28] H. Alrezaamiri, A. Ebrahimnejad, H. Motameni, "Parallel multi-objective artificial bee colony algorithm for software requirement optimization", Requirements Engineering, Jan. 2020, doi: https://doi.org/10.1007/s00766-020-00328-y.
[29] Y.T. Qi, F. Liu, J.L. Liu, Y. Ren, L.C. Jiao, "Hybrid Immune algorithm with EDA for multi-objective optimization", Journal of Software, vol. 24, no. 10, pp. 2251–2266, Jan. 2014, doi: https://doi.org/10.3724/sp.j.1001.2013.04341.
[30] I. María and José del Sagrado, "Salience-based stakeholder selection to maintain stakeholder coverage in solving the next release problem", Information & Software Technology, vol. 160, p. 107231, Aug. 2023, doi: https://doi.org/10.1016/j.infsof.2023.107231.
[31] M. Ghasemi, Karamollah Bagherifard, H. Parvin, Samad Nejatian, "Novel multi objective evolutionary framework for solving next release problem", Journal of Intelligent and Fuzzy Systems, vol. 44, no. 2, pp. 3315–3339, Jan. 2023, doi: https://doi.org/10.3233/jifs-200223.
[32] M. Ghasemi, K. Bagherifard, H. Parvin, S. Nejatian, K.-H. Pho, "Multi-objective whale optimization algorithm and multi-objective grey wolf optimizer for solving next release problem with developing fairness and uncertainty quality indicators", Applied Intelligence, vol. 51, no. 8, pp. 5358–5387, Jan. 2021, doi: https://doi.org/10.1007/s10489-020-02018-2.
[33] K. V. Divya and R. J. Anandhi, "Fuzzy branch and bound optimization technique for solving multi-objective next-release problem", SN Computer Science, vol. 5, no. 7, Sep. 2024, doi: 10.1007/s42979-024-03231-3.
[34] S. Verma, M. Pant, V. Snasel, "A comprehensive review on nsga-ii for multi-objective combinatorial optimization problems", IEEE Access, vol. 9, pp. 57757–57791, 2021, doi: 10.1109/access.2021.3070634.
[35] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II", IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, Apr. 2002.
[36] D. Simon, "Biogeography-based optimization", IEEE Transactions on Evolutionary Computation, vol. 12, no. 6, pp. 702–713, Dec. 2008, doi: https://doi.org/10.1109/TEVC.2008.919004.
[37] X. Li and M. Yin, "Multiobjective binary biogeography based optimization for feature selection using gene expression data", IEEE Transactions on NanoBioscience, vol. 12, no. 4, pp. 343–353, Dec. 2013, doi: https://doi.org/10.1109/tnb.2013.2294716.
[38] J. Li, X. Guo, Y. Yang, Q. Zhang, "A hybrid algorithm for multi-objective optimization—combining a biogeography-based optimization and symbiotic organisms search", Symmetry, vol. 15, no. 8, p. 1481, Jul. 2023, doi: 10.3390/sym15081481.
[39] P. Civicioglu, "Transforming geocentric cartesian coordinates to geodetic coordinates by using differential search algorithm", Computers & amp; Geosciences, vol. 46, pp. 229–247, Sep. 2012, doi: 10.1016/j.cageo.2011.12.011.
[40] C. Coello, G. B. Lamont, D. A. van Veldhuizen, "Evolutionary algorithms for solving multi-objective problems", 5th Edition. Springer Science & Business Media, 2007.
[41] J. M. Chaves-González, M. A. Pérez-Toledano, A. Navasa, "Software requirement optimization using a multiobjective swarm intelligence evolutionary algorithm", Knowledge-Based Systems, vol. 83, pp. 105–115, Jul. 2015, doi: 10.1016/j.knosys.2015.03.012.
