Multi-operator Differential Evolution with MOEA/D for Solving Multi-objective Optimization Problems

• Autorzy: Aggarwal Sakshi , Mishra Krishn K.

Identyfikatory

DOI

10.26636/jtit.2022.161822

• Języki publikacji: EN

Abstrakty

EN

In this paper, we propose a multi-operator differentia evolution variant that incorporates three diverse mutation strategies in MOEA/D. Instead of exploiting the local region, the proposed approach continues to search for optimal solutions in the entire objective space. It explicitly maintains diversity of the population by relying on the benefit of clustering. To promowe convergence, the solutions close to the ideal position, in the objective space are given preference in the evolutionary process. The core idea is to ensure diversity of the population by applying multiple mutation schemes and a faster convergence rate, giving preference to solutions based on their proximity to the ideal position in the MOEA/D paradigm. The performance of the proposed algorithm is evaluated by two popular test suites. The experimental results demonstrate that the proposed approach outperforms other MOEA/D algorithms.

Słowa kluczowe

EN

erential evolution; multi-objective; mutation operator; weighted-aggregation

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2022
• Tom: nr 3
• Strony: 85--95
• Opis fizyczny: Bibliogr. 40 poz., rys., tab.

Twórcy

autor

Aggarwal Sakshi

• Department of Computer Science and Engineering, Motilal Nehru National Institute of Technology Allahabad, Prayagraj, India

autor

Mishra Krishn K.

• Department of Computer Science and Engineering, Motilal Nehru National Institute of Technology Allahabad, Prayagraj, India

Bibliografia

• [1] C.A.C. Coello, D.A.V. Veldhuizen, and G.B. Lamont, “Evolutionary Algorithms for Solving Multi-Objective Problems”, Kluwer Academic, 2007 (DOI: 10.1007/978-0-387-36797-2).
• [2] K.C. Tan, E.F. Khor, and T.H. Lee, “Multiobjective Evolutionary Algorithms and Applications (Advanced Information and Knowledge Processing)”, Springer, 2005 (DOI: 10.1007/1-84628-132-6).
• [3] A. Zhou et al., “Multiobjective evolutionary algorithms: A survey of the state of the art”, Swarm Evol. Comput., vol. 1, no. 1, pp. 32–49, 2011 (DOI: 10.1016/j.swevo.2011.03.001).
• [4] J.D. Knowles and D.W. Corne, “Approximating the nondominated front using the Pareto archived evolution strategy”, Evol. Comput., vol. 8, no. 2, pp. 149–172, 2000 (DOI: 10.1162/106365600568167).
• [5] E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization”, Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, K.C. Giannakoglou, D.T.Tsahalis, J. Periaux, K.D. Papailiou, and T. Fogarty, Eds. Athens, Greece: Int. Center Numer. Methods Eng., pp. 95–100, 2001.
• [6] K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II”, IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, 2002 (DOI: 10.1109/4235.996017).
• [7] Q. Zhang, A. Zhou, and Y. Jin, “RM-MEDA: A regularity modelbased multiobjective estimation of distribution algorithm”, IEEE Trans. Evol. Comput., vol. 12, no. 1, pp. 41–63, 2008 (DOI:10.1109/TEVC.2007.894202).
• [8] E. Zitzler and S. Kunzli, “Indicator-based selection in multiobjective search”, Parallel Problem Solving from Nature (PPSN VIII), vol. 3242, pp. 832–842, 2004 (DOI: 10.1007/978-3-540-30217-9_84).
• [9] J. Bader and E. Zitzler, “HypE: An algorithm for fast hypervolumebased many-objective optimization”, Evol. Comput., vol. 19, no. 1, pp. 45–76, 2011 (DOI: 10.1162/EVCO_a_00009).
• [10] D. Brockhoff, T. Wagner, and H. Trautmann, “R2 indicator-based multiobjective search”, Evol. Comput., vol. 23, no. 3, pp. 369–395, 2015 (DOI:10.1162/EVCO_a_00135).
• [11] S. Jiang, J. Zhang, Y.-S. Ong, A.N. Zhang, and P.S. Tan, “A Simple and fast hypervolume indicator-based multiobjective evolutionary algorithm”, IEEE Trans. Cybern., vol. 45, no. 10, pp. 2202–2213, 2015 (DOI: 10.1109/TCYB.2014.2367526).
• [12] A. Jaszkiewicz, “On the performance of multiple-objective genetic local search on the 0/1 knapsack problem – a comparative experiment”, IEEE Trans. Evol. Comput., vol. 6, no. 4, pp. 402–412, 2002 (DOI:10.1109/TEVC.2002.802873).
• [13] Y. Jin, T. Okabe, and B. Sendho, “Adapting weighted aggregation for multiobjective evolution strategies”, Evolutionary Multi-Criterion Optimization, pp. 96–110, 2001 (DOI: 10.1007/3-540-44719-9_7).
• [14] E.J. Hughes, “Multiple single objective Pareto sampling”, Proc. Congr. Evol. Comput., pp. 2678–2684, 2003 (DOI:10.1109/CEC.2003.1299427).
• [15] H. Ishibuchi, T. Yoshida, and T. Murata, “Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling”, IEEE Trans. Evol. Comput., vol. 7, no. 2, pp. 204–223, 2003 (DOI: 10.1109/TEVC.2003.810752).
• [16] Q. Zhang and H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition”, IEEE Trans. Evol. Comput., vol. 11, no. 6, pp. 712–731, 2007 (DOI: 10.1109/TEVC.2007.892759).
• [17] H. Li and Q. Zhang, “Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II”, IEEE Trans. Evol. Comput., vol. 13, no. 2, pp. 284–302, 2009 (DOI:10.1109/TEVC.2008.925798).
• [18] H. Li, Q. Zhang and J. Deng, “Biased Multiobjective Optimization and Decomposition Algorithm”, IEEE Transactions on Cybernetics, vol. 47, no. 1, pp. 52–66, 2017 (DOI: 10.1109/TCYB.2015.2507366).
• [19] Y. Yuan, H. Xu, B. Wang, B. Zhang, and X. Yao, “Balancing Convergence and Diversity in Decomposition-Based Many-Objective Optimizers”, IEEE Transactions on Evolutionary Computation, vol. 20, no. 2, pp. 180–198, 2016 (DOI:10.1109/TEVC.2015.2443001).
• [20] N. Hansen and S. Kern, “Evaluating the CMA evolution strategy on multimodal test functions”, Parallel Problem Solving from Nature-PPSN VIII, pp. 282–291, 2004 (DOI: 10.1007/978-3-540-30217-9_29).
• [21] A. Auger and N. Hansen, “A restart CMA evolution strategy with increasing population size”, Proc. Congr. Evol. Comput., pp. 1769–1776, 2005 (DOI: 10.1109/CEC.2005.1554902).
• [22] I. Loshchilov, “CMA-ES with restarts for solving CEC 2013 benchmark problems”, Proc. Congr. Evol. Comput., pp. 369–376, 2013 (DOI: 10.1109/CEC.2013.6557593).
• [23] N. Srinivas and K. Deb, “Multiobjective optimization using nondominated sorting in genetic algorithms”, Evol. Comput., vol. 2, no. 3, pp. 221–248, 1994.
• [24] J. Horn, N. Nafpliotis, and D.E. Goldberg, “A niched Pareto genetic algorithm for multiobjective optimization”, Proc. 1st Int. Conf. Evol. Comput., pp. 82–87, 1994 (DOI: 10.1109/ICEC.1994.350037).
• [25] P.A.N. Bosman and D. Thierens, “The balance between proximity and diversity in multiobjective evolutionary algorithms”, IEEE Trans. Evol. Comput., vol. 7, no. 2, pp. 174–188, 2003 (DOI:10.1109/TEVC.2003.810761).
• [26] E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach”, IEEE Trans. Evol. Comput., vol. 3, no. 4, pp. 257–271, 1999 (DOI:10.1109/4235.797969).
• [27] M. Fleischer, “The measure of Pareto optima applications to multiobjective metaheuristics”, Proc. Evol. Multi-Criterion Optim., pp. 519–533, 2003 (https://doi.org/10.1007/3-540-36970-8_37).
• [28] O. Schutze, X. Esquivel, A. Lara, and C.A.C. Coello, “Using the averaged Hausdorff distance as a performance measure in evolutionary multiobjective optimization”, IEEE Trans. Evol. Comput., vol. 16, no. 4, pp. 504–522, 2012 (DOI: 10.1109/TEVC.2011.2161872).
• [29] J. Qi, Y. Yu, L. Wang, and J. Liu, “K*-Means: An Effective and Efficient K-Means Clustering Algorithm”, 2016 IEEE International Conferences on Big Data and Cloud Computing (BDCloud), Social Computing and Networking (Social-Com), Sustainable Computing and Communications (Sustain-Com) (BDCloud-SocialCom-SustainCom), pp. 242–249, 2016 (DOI:10.1109/BDCloud-SocialCom-SustainCom.2016.46).
• [30] X. Ma, Q. Zhang, G. Tian, J. Yang, and Z. Zhu, “On Tchebycheff Decomposition Approaches for Multiobjective Evolutionary Optimization”, IEEE Transactions on Evolutionary Computation, vol. 22, no. 2, pp. 226–244, 2018 (DOI: 10.1109/TEVC.2017.2704118).
• [31] R. Tanabe and A.S. Fukunaga, “Improving the search performance of shade using linear population size reduction”, 2014 IEEE Congress on Evolutionary Computation (CEC), pp. 1658–1665, 2014 (DOI:10.1109/CEC.2014.6900380).
• [32] Y. Tian, R. Cheng, X. Zhang, andY. Jin, “PlatEMO:AMatlab platform for evolutionary multi-objective optimization [educational forum]”, IEEE Computational Intelligence Magazine, vol. 12, no. 4, pp. 73–87, 2017 (DOI: 10.1109/MCI.2017.2742868).
• [33] E. Zitzler, K. Deb, and L. Thiele. “Comparison of multiobjective evolutionary algorithms: Empirical results”, Evolutionary computation 8.2, pp. 173–195, 2000 (DOI: 10.1162/106365600568202).
• [34] A. Zhou, Q. Zhang, Y. Jin, and B. Sendhoff, “Adaptive modelling strategy for continuous multi-objective optimization”, Proc. Congr. Evol. Comput., pp. 431–437, 2007 (DOI:10.1109/CEC.2007.4424503).
• [35] N. Beume, B. Naujoks, and M. Emmerich, “SMS-EMOA: Multiobjective selection based on dominated hypervolume”, Eur. J. Oper. Res., vol. 181, no. 3, pp. 1653–1669, 2007 (DOI:10.1016/j.ejor.2006.08.008).
• [36] A. Auger, J. Bader, D. Brockhoff, and E. Zitzler, “Theory of the hypervolume indicator: Optimal μ-distributions and the choice of the reference point”, Proc. 10th ACM SIGEVO Workshop Found. Genet. Algorithms, pp. 87–102, 2009 (DOI: 10.1145/1527125.1527138).
• [37] H. Ishibuchi, Y. Hitotsuyanagi, N. Tsukamoto, and Y. Nojima, “Manyobjective test problems to visually examine the behavior of multiobjective evolution in a decision space”, Proc. Int. Conf. Parallel Prob. Solv. Nat., pp. 91–100, 2010 (DOI: 10.1007/978-3-642-15871-1_10).
• [38] T. Wagner, N. Beume, and B. Naujoks, “Pareto-, aggregation-, and indicator-based methods in many-objective optimization”, Proc. Evol. Multi-Criterion Optim., pp. 742–756, 2007 (DOI: 10.1007/978-3-540-70928-2_56).
• [39] X. Zou, Y. Chen, M. Liu, and L. Kang, “A new evolutionary algorithm for solving many-objective optimization problems”, IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 38, no. 5, pp. 1402–1412, Oct. 2008 (DOI: 10.1109/TSMCB.2008.926329).
• [40] S. Garcia, A. Fernandez, J. Luengo, and F. Herrera, “Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: Experimental analysis of power”, Information Sciences, vol. 180, no. 10, pp. 2044–2064, 2010 (DOI: 10.1016/j.ins.2009.12.010).

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).