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

Document Type : Article


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


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.


[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).