FixedSum : a novel algorithm for generating weight vectors in decomposition-based multiobjective optimization

• Autorzy: Qasim Syed Zaffar , Ismail Muhammad Ali

Identyfikatory

DOI

10.37190/ord250204

• Języki publikacji: EN

Abstrakty

EN

Many multiobjective optimization algorithms employ weight vectors (WVs) for decomposing a problem into multiple subproblems. These weight vectors should be uniformly spread along the Pareto front. Recently, some studies about the development of decomposition-based multiobjective evolutionary algorithms have adopted different methods for generating weight vectors. However, these WVs are often clustered, either near the boundary or in inner regions of the search space. In this paper, we have proposed a novel algorithm, FixedSum, for the generation of an arbitrary number of WVs of any user-specified dimension. These weight vectors are more uniformly spread in the search space, and we have compared our results with other methods on 5D, 8D, 10D and 12D weight vectors. For further validation, we have applied our weight vectors along with the WVs of two other methods for solving the DTLZ problems. All the results demonstrate the improved spreadability of our method compared to competing approaches.

Słowa kluczowe

EN

multiple objective programming; weight vector; many-objective optimization; decomposition-based multiobjective algorithm; FixedSum

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2025
• Tom: Vol. 35, No. 2
• Strony: 93--119
• Opis fizyczny: Bibliogr. 42 poz., rys.

Twórcy

autor

Qasim Syed Zaffar

• Department of Computer and Information Systems, NED University, Karachi, Pakistan

• https://orcid.org/0009-0001-0307-6030

autor

Ismail Muhammad Ali

• Department of Computer and Information Systems, NED University, Karachi, Pakistan

Bibliografia

• [1] Branke, J., Deb, K., Miettinen, K., and Slowiński, R. Multiobjective Optimization: Interactive and Evolutionary Approaches. Vol. 5252 of Lecture Notes in Computer Science, Springer, 2008.
• [2] Chen, J., Ding, J., Tan, K. C., and Chen, Q. A decomposition-based evolutionary algorithm for scalable multi/manyobjective optimization. Memetic Computing 13, 3 (2021), 413–432.
• [3] Chen, X., Yin, J., Yu, D., and Fan, X. A decomposition-based many-objective evolutionary algorithm with adaptive weight vector strategy. Applied Soft Computing 128 (2022), 109412.
• [4] Coello, C. A. C., Lamont, G. B., Van Veldhuizen, D. A. Evolutionary Algorithms for Solving Multi-Objective Problems.Springer, 2007.
• [5] Dai, C., and Wang, Y. A new decomposition based evolutionary algorithm with uniform designs for many-objective optimization. Applied Soft Computing 30 (2015), 238–248.
• [6] Das, I., and Dennis, J. E. Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM Journal on Optimization 8, 3 (1998), 631–657.
• [7] Deb, K. Multi-Objective Optimization Using Evolutionary Algorithms. Vol. 16. John Wiley & Sons, 2001.
• [8] Deb, K. Multi-objective optimisation using evolutionary algorithms: an introduction. In Multi-objective Evolutionary Optimisation for Product Design and Manufacturing (London, 2011), L. Wang, A. H. C. Ng and K. Deb, Eds., Springer, pp. 3–34.
• [9] Deb, K., and Jain, H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: Solving problems with box constraints. IEEE Transactions Evolutionary Computation 18, 4 (2014), 577–601.
• [10] Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (2002), 182–197.
• [11] Deb, K., Thiele, L., Laumanns, M., and Zitzler, E. Scalable test problems for evolutionary multiobjective optimization. In Evolutionary Multiobjective Optimization (London 2005), A. Abraham, L. Jain and R. Goldberg, Eds., Springer, pp. 105–145.
• [12] Fang, K.-T., and Wang, Y. Number-Theoretic Methods in Statistics. Vol. 51, CRC Press, 1993.
• [13] He, L., Camacho, A., Nan, Y., Trivedi, A., Ishibuchi, H., and Srinivasan, D. Effects of corner weight vectors on the performance of decomposition-based multiobjective algorithms. Swarm and Evolutionary Computation 79 (2023), 101305.
• [14] Ishibuchi, H., Imada, R., Masuyama, N., and Nojima, Y. Two-layered weight vector specification in decomposition-based multi-objective algorithms for many-objective optimization problems. In 2019 IEEE Congress on Evolutionary Computation (CEC) (Wellington, New Zealand, 2019), IEEE, pp. 2434–2441.
• [15] Ishibuchi, H., Masuda, H., Tanigaki, Y., and Nojima, Y. Modified distance calculation in generational distance and inverted generational distance. In Evolutionary Multi-Criterion Optimization. 8th International Conference, EMO 2015, Guimarães, Portugal, March 29 –April 1, 2015. Proceedings, Part II (Cham, 2015), A. Gaspar-Cunha, C. Henggeler Antunes and C. A. Coello Coello, Eds., Springer, pp. 110–125.
• [16] Ishibuchi, H., and Murata, T. A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) 28, 3 (1998), 392–403.
• [17] Ishibuchi, H., Tsukamoto, N., and Nojima, Y. Evolutionary many-objective optimization: A short review. In Proceedings of 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence) (Hong Kong, China, 2008), IEEE, pp. 2419–2426.
• [18] Ji, J.-Y., Tan, Z., Zeng, S., See-To, E. W. K., and Wong, M.-L. A surrogate-assisted evolutionary algorithm for seeking multiple solutions of expensive multimodal optimization problems. IEEE Transactions on Emerging Topics in Computational Intelligence 8, 1 (2024),pp. 377-388.
• [19] Ji, J.-Y., Tan, Z., Zeng, S., and Wong, M.-L. An ε-constrained multiobjective differential evolution with adaptive gradient-based repair method for real-world constrained optimization problems. Applied Soft Computing 152 (2024), 111202.
• [20] Ji, J.-Y., Yu, W.-J., Zhong, J., and Zhang, J. Density-enhanced multiobjective evolutionary approach for power economic dispatch problems. IEEE Transactions on Systems, Man, and Cybernetics: Systems 51, 4 (2019), 2054–2067.
• [21] Ji, J.-Y., Zeng, S., and Wong, M. L. ε-constrained multiobjective differential evolution using linear population size expansion. Information Sciences 609 (2022), 445–464.
• [22] Kremmel, T., Kubalík, J., and Biffl, S. Software project portfolio optimization with advanced multiobjective evolutionary algorithms. Applied Soft Computing 11, 1 (2011), 1416–1426.
• [23] Kukkonen, S., and Lampinen, J. GDE3: The third evolution step of generalized differential evolution. In Proceedings of 2005 IEEE Congress on Evolutionary Computation (Edinburgh, UK, 2005), vol. 1, IEEE, pp. 443–450.
• [24] Li, G., Wang, G.-G., and Xiao, R.-B. A novel adaptive weight algorithm based on decomposition and two-part update strategy for many-objective optimization. Information Sciences 615 (2022), 323–347.
• [25] Li, K., Deb, K., Zhang, Q., and Kwong, S. An evolutionary many-objective optimization algorithm based on dominance and decomposition. IEEE Transactions on Evolutionary Computation 19, 5 (2014), 694–716.
• [26] Li, X., Zhan, J., Pan, F., Lv, T., and Wang, S. A multi-objective optimization model of urban passenger transportation structure under low-carbon orientation considering participating subjects. Environmental Science and Pollution Research 30, 54 (2023), 115839–115854.
• [27] Liu, Y., Hu, Y., Zhu, N., Li, K., Zou, J., and Li, M. A decomposition-based multiobjective evolutionary algorithm with weights updated adaptively. Information Sciences 572 (2021), 343–377.
• [28] López Jaimes, A., and Coello Coello, C. A. Some techniques to deal with many-objective problems. In Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers (New York, NY, 2009), ACM, pp. 2693–2696.
• [29] Miettinen, K. M. Nonlinear Multiobjective Optimization. Vol. 12 of International Series in Operations Research & Management Science, Springer Science & Business Media, 2012.
• [30] Moustafa, R. E. Parallel coordinate and parallel coordinate density plots. Wiley Interdisciplinary Reviews: Computational Statistics 3, 2 (2011), 134–148.
• [31] Ngatchou, P., Zarei, A., and El-Sharkawi, A. Pareto multi objective optimization. In Proceedings of the 13th International Conference on Intelligent Systems Application to Power Systems (Arlington, VA, USA, 2005), IEEE, pp. 84–91.
• [32] Prajapati, A. A comparative study of many-objective optimizers on large-scale many-objective software clustering problems. Complex & Intelligent Systems 7, 2 (2021), 1061–1077.
• [33] Qasim, S. Z., and Ismail, M. A. Research problems in search-based software engineering for many-objective optimization. In Proceedings of International Conference on Innovations in Electrical Engineering and Computational Technologies (ICIEECT) (Karachi, Pakistan, 2017), IEEE, pp. 1–6.
• [34] Qasim, S. Z., and Ismail, M. A. Rode: Ranking-dominance-based algorithm for many-objective optimization with oppositionbased differential evolution. Arabian Journal for Science and Engineering 45 (2020), 10079–10096.
• [35] Qasim, S. Z., and Ismail, M. A. DOCEA/D: Dual-operator-based constrained many-objective evolutionary algorithm based on decomposition. Cluster Computing 25, 6 (2022), 4151–4169.
• [36] Qasim, S. Z., and Ismail, M. A. MOSA/D: Multi-operator evolutionary many-objective algorithm with self-adaptation of parameters based on decomposition. Evolutionary Intelligence 16, 3 (2023), 849–871.
• [37] Ramirez, A., Romero, J. R., and Ventura, S. A survey of many-objective optimisation in search-based software engineering. Journal of Systems and Software 149 (2019), 382–395.
• [38] Saxena, D. K., Mittal, S., Kapoor, S., and Deb, K. A localized high-fidelity-dominance based many-objective evolutionary algorithm. IEEE Transactions on Evolutionary Computation 27, 4 (2022), 923–937.
• [39] Yacoubi, S., Manita, G., Chhabra, A., Korbaa, O., and Mirjalili, S. A multi-objective chaos game optimization algorithm based on decomposition and random learning mechanisms for numerical optimization. Applied Soft Computing 144 (2023), 110525.
• [40] Zhang, Q., and Li, H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation 11, 6 (2007), 712–731.
• [41] Zheng, W., Tan, Y., Meng, L., and Zhang, H. An improved MOEA/D design for many-objective optimization problems. Applied Intelligence 48, 10 (2018), 3839–3861.
• [42] Zitzler, E., Laumanns, M., and Thiele, L. SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-report 103, ETH Zurich, Computer Engineering and Networks Laboratory, (2001).

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).