A Non-dominated Sorting based Evolutionary Algorithm for Many-objective Optimization Problems

Document Type : Article

Authors

Department of Computer Science and Engineering, Koneru Lakshmaiah Education Foundation (Deemed to be University), Vaddeswaram, Guntur Dist., AP, India

Abstract

The optimization problems with more than three objectives are many-objective optimization problems exist in various scientific and engineering domains. The existing multi-objective evolutionary algorithmic approaches primarily developed to address problems up to three objectives. Such multi-objective evolutionary algorithms do not found effective to address the many-objective optimization problems. The limitations of existing multi-objective evolutionary algorithms initiated the need to develop a specific algorithm which efficiently solves the many-objective optimization problems. The proposed work presents the design of the MaOHDE to address MaOPs. Initially, NS-MODE & NS-MOPSO algorithms developed by incorporating the non-dominated sorting approach from NSGA-II, the ranking approach, weight vector, and reference points. The widely used Tchebycheff – a decomposition-based approach applied to decompose the MaOPs. The MaOHDE algorithm developed by hybridizing the NS-MODE with NS-MOPSO. The presented approach’s strength is revealed using 20 instances of DTLZ functions. The effectiveness and efficiency are verified by comparing with MaOJaya, RD-EMO, NSGA-III, MOEA/D, MOEA/DD, RVEA, and MOEA/D-M2M algorithms. From the results, it is observed that the hybridization of NS-MODE and NS-MOPSO as MaOHDE responds better than its competitors for most of the test instances or it is competitive. The convergence rate is also good as compared with other state-of-art algorithms.

Keywords


References
[1]      Mohammadi, A., Omidvar, M. N., Li, X., et al., “Integrating user preferences and decomposition methods for many-objective optimization,” Proc. 2014 IEEE Congr. Evol. Comput. CEC 2014, pp. 421–428 (2014).
[2]      Cheng, R., Jin, Y., Olhofer, M. and Sendhoff, B., “A reference vector guided evolutionary algorithm for many-objective optimization,” IEEE Trans. Evol. Comput., 20(5), pp. 773–791 (2016).
[3]      Li, K., Deb, K., Zhang, Q. and Kwong, S., “An evolutionary many-objective optimization algorithm based on dominance and decomposition,” IEEE Trans. Evol. Comput., 19(5), pp. 694–716 (2015).
[4]      Giagkiozis, I. and Fleming, P. J., “Methods for Many-Objective Optimization : An Analysis,” 1030, pp. 1–15 (2012).
[5]      Giagkiozis, I. and Fleming, P. J., “Methods for multi-objective optimization: An analysis,” Inf. Sci. (Ny)., 293, pp. 338–350 (2015).
[6]      Ma, X., Yang, J., Wu, N., et al., “A comparative study on decomposition-based multi-objective evolutionary algorithms for many-objective optimization,” 2016 IEEE Congr. Evol. Comput. CEC 2016, pp. 2477–2483 (2016).
[7]      Wang, H., Jin, Y. and Yao, X., “Diversity Assessment in Many-Objective Optimization,” IEEE Trans. Cybern., 47(6), pp. 1510–1522 (2017).
[8]      Ishibuchi, H., Tsukamoto, N. and Nojima, Y., “Evolutionary Many-Objective Optimization: A Short Review,” pp. 2424–2431 (2008).
[9]      Marler, R. T. and Arora, J. S., “Survey of multi-objective optimization methods for engineering,” Struct. Multidiscip. Optim., 26(6), pp. 369–395 (2004).
[10]    Batista, L.S., Campelo, F., Guimarães, F.G., et al., “A comparison of dominance criteria in many-objective optimization problems,” 2011 IEEE Congr. Evol. Comput. CEC 2011, pp. 2359–2366 (2011).
[11]    Trivedi, A., Srinivasan, D., Sanyal, K., et al., “A survey of multiobjective evolutionary algorithms based on decomposition,” IEEE Trans. Evol. Comput., 21(3), pp. 440–462 (2016).
[12]    Mane, S. U. and Narasinga Rao, M. R., “Many-objective optimization: Problems and evolutionary algorithms - a short review,” Int. J. Appl. Eng. Res., 12(20), pp. 9774-9793 (2017).
[13]    Arabas, K. and Opara, J., “Benchmarking procedures for continuous optimization algorithms,” J. Telecommun. Inf. Technol., pp. 73–80 (2011).
[14]    Jamil, M. and Yang, X. S., “A literature survey of benchmark functions for global optimisation problems,” Int. J. Math. Model. Numer. Optim., 4(2), pp. 150–194 (2013).
[15]    Rao, S. S., “Engineering optimization: theory and practice”, Ed., 5th Edn., John Wiley and Sons, (2019).
[16]    Rao, R., “Jaya: A simple and new optimization algorithm for solving constrained and unconstrained optimization problems,” Int. J. Ind. Eng. Comput., 7(1), pp. 19–34 (2016).
[17]    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 Trans. Evol. Comput., 18 (4), pp. 577–601 (2014).
[18]    Dai, S., Liu, H. and Chen, L., “Evolutionary many-objective optimization algorithm based on improved K-Dominance and M2M population decomposition,” Proc. - 2015 11th Int. Conf. Comput. Intell. Secur. CIS 2015, no. 1, pp. 286–290 (2016).
[19]    Pal, M., Saha, S. and Bandyopadhyay, S., “Clustering based online automatic objective reduction to aid many-objective optimization,” 2016 IEEE Congr. Evol. Comput. CEC 2016, pp. 1131–1138 (2016).
[20]    Ishibuchi, H., Akedo, N. and Nojima, Y., “Behavior of Multiobjective Evolutionary Algorithms on Many-Objective Knapsack Problems,” IEEE Trans. Evol. Comput., 19(2), pp. 264–283 (2014).
[21]    Von Lücken, C., Barán, B. and Brizuela, C., “A survey on multi-objective evolutionary algorithms for many-objective problems,” Comput. Optim. Appl., 58(3), pp. 707–756 (2014).
[22]    Nguyen, X.H., Bui, L.T. and Tran, C.T., “Improving many objective optimisation algorithms using objective dimensionality reduction,” Evol. Intell., 13(3), pp. 365–380 (2020).
[23]    Zhou, A., Wang, Y. and Zhang, J., “Objective extraction via fuzzy clustering in evolutionary many-objective optimization,” Inf. Sci. (Ny)., 509, pp. 343–355 (2020).
[24]    Zhao, H. and Zhang, C., “An online-learning-based evolutionary many-objective algorithm,” Inf. Sci. (Ny).,  509(195), pp. 1–21 (2020).
[25]    Jiang, S., He, X. and Zhou, Y., “Many-objective evolutionary algorithm based on adaptive weighted decomposition,” Appl. Soft Comput. J., 84, p. 105731 (2019).
[26]    Chen, H., Cheng, R., Pedrycz, W., et al., “Solving Many-Objective Optimization Problems via Multistage Evolutionary Search,” IEEE Trans. Syst. Man, Cybern. Syst., pp. 2168–2216 (2019).
[27]    Li, F., Liu, J., Huang, P., et al., “An R2 Indicator and Decomposition Based Steady-State Evolutionary Algorithm for Many-Objective Optimization,” Math. Probl. Eng., (2018).
[28]    Wang, W.L., Li, W. and Wang, Y.L., “An Opposition-Based Evolutionary Algorithm for Many-Objective Optimization with Adaptive Clustering Mechanism,” Comput. Intell. Neurosci., (2019).
[29]    Liu, Y., Qin, H., Zhang, Z., et al., “A region search evolutionary algorithm for many-objective optimization,” Inf. Sci. (Ny)., 488, pp. 19–40 (2019).
[30]    Li, K., Wang, R., Zhang, T., et al., “Evolutionary Many-Objective Optimization: A Comparative Study of the State-of-The-Art,” IEEE Access, 6, pp. 26194–26214 (2018).
[31]    Mane, S. and Narsingrao, M., “A chaotic-based improved many-objective jaya algorithm for many-objective optimization problems,” Int. J. Ind. Eng. Comput., 12(1), pp. 49–62 (2021).
[32]    Bandyopadhyay, S. and Mukherjee, A., “An algorithm for many-objective optimization with reduced objective computations: A study in differential evolution,” IEEE Trans. Evol. Comput., 19(3), pp. 400–413 (2015).
[33]    Britto, A. and Pozo, A., “Reference-point based multi-swarm algorithm for many-objective problems,” Proc. - 2015 Brazilian Conf. Intell. Syst. BRACIS 2015, pp. 252–257 (2016).
[34]    Deb, K., Sundar, J., Udaya Bhaskara, R. N., et al., “Reference Point Based Multi-Objective Optimization Using Evolutionary Algorithms,” Int. J. Comput. Intell. Res., 2(3), pp. 273–286 (2006).
[35]    Storn, R. and Price, K., “Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces,” J. Glob. Optim., 11(4), pp. 341–359 (1997).
[36]    Zhao, M., Liu, R., Li, W., et al., “Multi-objective optimization based differential evolution constrained optimization algorithm,” Proc. - 2010 2nd WRI Glob. Congr. Intell. Syst. GCIS 2010, 1(1), pp. 320–326 (2010).
[37]    Kachitvichyanukul, V., “Comparison of Three Evolutionary Algorithms :,” Ind. Eng. Manag. Syst., 11(3), pp. 215–223 (2012).
[38]    Das, S., Mullick, S.S. and Suganthan, P.N., “Recent advances in differential evolution-An updated survey,” Swarm Evol. Comput., 27, pp. 1–30 (2016).
[39]    Kennedy, J., “Particle Swarm Optimization,” Encyclopedia of machine learning. pp. 760–766 (2011).
[40]    Feng, S., Kang, Q., Chen, X., et al., “A weight-aggregation multi-objective PSO algorithm for load scheduling of PHEVs,” 2016 IEEE Congr. Evol. Comput. CEC 2016, pp. 2896–2902 (2016).
[41]    Song, M.P. and Gu, G.C., “Research on particle swarm optimization: A review,” Proc. 2004 Int. Conf. Mach. Learn. Cybern., 4, pp. 2236–2241 (2004).
[42]    Rini, D.P., Shamsuddin, S.M. and Yuhaniz, S.S., “Particle Swarm Optimization: Technique, System and Challenges,” Int. J. Appl. Inf. Syst., 1(1), pp. 33–45 (2011).
[43]    Poli, R., Kennedy, J. and Blackwell, T., “Particle swarm optimization: An overview,” Swarm Intell., 1(1), pp. 33–57 (2007).
[44]    Banks, A., Vincent, J. and Anyakoha, C., “A review of particle swarm optimization. Part I: Background and development,” Nat. Comput., 6(4), pp. 467–484 (2007).
[45]    Banks, A., Vincent, J. and Anyakoha, C., “A review of particle swarm optimization. Part II: Hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications,” Nat. Comput., 7(1), pp. 109–124 (2008).
[46]    Rana, S., Jasola, S. and Kumar, R., “A review on particle swarm optimization algorithms and their applications to data clustering,” Artif. Intell. Rev., 35(3), pp. 211–222 (2011).
[47]    Garg, H. and Sharma, S.P., “Multi-objective reliability-redundancy allocation problem using particle swarm optimization.,” Comput. Ind. Eng., 64(1), pp. 247–255 (2013).
[48]    Dragoi, E.N. and Dafinescu, V., “Parameter control and hybridization techniques in differential evolution: a survey,” Artif. Intell. Rev., 45(4), pp. 447–470 (2016).
[49]    Jitkongchuen, D., “A hybrid differential evolution with grey Wolf optimizer for continuous global optimization,” Proc. - 2015 7th Int. Conf. Inf. Technol. Electr. Eng. Envisioning Trend Comput. Inf. Eng. ICITEE 2015, pp. 51–54 (2015).
[50]    Liu, T. and Maeda, M., “Set-based differential evolution for traveling salesman problem,” Proc. - 2013 6th Int. Conf. Intell. Networks Intell. Syst. ICINIS 2013, pp. 107–110 (2013).
[51]    Qin, Y., Hu, H., Shi, Y., et al., “An artificial bee colony algorithm hybrid with differential evolution for multi-temporal image registration,” Chinese Control Conf. CCC, vol. 2016-August, pp. 2734–2739 (2016).
[52]    Ye, S., Dai, G., Peng, L., et al., “A hybrid adaptive coevolutionary differential evolution algorithm for large-scale optimization,” Proc. 2014 IEEE Congr. Evol. Comput. CEC 2014, pp. 1277–1284 (2014).
[53]    Garg, H., “A hybrid GA-GSA algorithm for optimizing the performance of an industrial system by utilizing uncertain data,” in Handbook of research on artificial intelligence techniques and algorithms, pp. 620–654 (2015).
[54]    Garg, H., “A hybrid PSO-GA algorithm for constrained optimization problems,” Appl. Math. Comput., 274, pp. 292–305 (2016).
[55]    Patwal, R.S., Narang, N. and Garg, H., “A novel TVAC-PSO based mutation strategies algorithm for generation scheduling of pumped storage hydrothermal system incorporating solar units,” Energy, 142, pp. 822–837 (2018).
[56]    Deb, K., Thiele, L., Laumanns, M., et al., “Scalable Test Problems for Evolutionary Multiobjective Optimization,” Evol. Multiobjective Optim., 1990, pp. 105–145 (2005).
[57]    Liu, R., Liu, J., Zhou, R., et al., “A region division based decomposition approach for evolutionary many-objective optimization,” Knowledge-Based Syst., 194, pp. 105-518 (2020).
[58]    Tian, Y., Cheng, R., Zhang, X., et al., “PlatEMO: A MATLAB Platform for Evolutionary Multi-Objective Optimization [Educational Forum],” IEEE Comput. Intell. Mag., 12(4), pp. 73–87 (2017).
[59]    Yang, W., Chen, L., Wang, Y., et al., “A reference points and intuitionistic fuzzy dominance based particle swarm algorithm for multi/many-objective optimization,” Appl. Intell., 50(4), pp. 1133–1154 (2020).
[60]    Lwin, K., Qu, R. and Kendall, G., “A learning-guided multi-objective evolutionary algorithm for constrained portfolio optimization,” Appl. Soft Comput. J., 24, pp. 757–772 (2014).
[61]    Radziukynienė, I. and Žilinskas, A., “Evolutionary Methods for Multi-Objective Portfolio Optimization,” Lect. Notes Eng. Comput. Sci., 2171(1), pp. 1155–1159 (2008).