بهینه سازی جغرافیای زیستی با جمعیت براونی برای مسئله چندهدفی انتشار نسخه بعد
محورهای موضوعی : مهندسی کامپیوتر-نرم افزار
1 - گروه مهندسی کامپیوتر، واحد لارستان، دانشگاه آزاد اسلامی، لارستان، ایران
2 - گروه مهندسی کامپیوتر، واحد لارستان، دانشگاه آزاد اسلامی، لارستان، ایران
کلید واژه: مسئله انتشار نسخه بعد, بهینه سازی چندهدفی, بهینه سازی جغرافیای زیستی, جمعیت براونی, مهندسی نرم افزار مبتنی بر جستجو,
چکیده مقاله :
توسعه‌دهندگان نرمافزار باید تصمیم بگیرند که چه نیازمندیهایی در نسخه‌های بعدی، پیادهسازی گردد. انتخاب یک مجموعه از نیازمندیها در انتشار نسخه بعدی نرمافزار یک مسئله بغرنج (NP-Hard) است که بنام مسئله انتشار نسخه بعد (NRP) شناخته میشود. در این تحقیق، الگوریتم بهینهسازی جغرافیای زیستی بصورت چندهدفی برای این مسئله ارائه میکنیم. همچنین با الهام از حرکت تصادفی شبه براونی، جمعیتی بنام جمعیت براونی ایجاد كرده و با الگوریتم بهینهسازی جغرافیای زیستی ترکیب میکنیم. احتمال مهاجرت به هریک از زیستگاهها را با رويكردي جديد و براساس نسبت توابع هدف، ايجاد میکنیم. رويكردهاي ادغام پاسخها و جمعيت با اعضاي غيرتكراري را نيز در تکرارهای الگوریتم، بکار میبریم. از دو مجموعهداده و شاخصهای کیفیت ابرحجم، گستردگی و تعداد پاسخهای غیرمغلوب، برای ارزیابی استفاده میشود. برای بررسی تاثیر جمعیت براونی و جمعیت غیرتکراری؛ الگوریتم پیشنهادی؛ یعنی الگوریتم جغرافیای زیستی با جمعیت براونی و جمعيت غيرتكراري را با سه نسخه دیگر الگوریتم جغرافياي زيستي، برای حل مسئله انتشار نسخه بعد، پيادهسازي كرده و نتایجشان را مقايسه مينماييم. نتایج نشان میدهند که روش پیشنهادی، الگوریتم جغرافیای زیستی را بهبود داده است. جمعیت براونی در بهبود گستردگی و جمعیت غیرتکراری در افزایش تعداد پاسخهای غیرمغلوب موثرترند. در مقایسه با تحقیقات مشابه دیگران نیز، الگوريتم پيشنهادي، عملکرد بهتری از دیگر الگوریتمهای گزارش‌شده قبلی دارد.
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.