A novel two-archive matching-based algorithm for multi- and many-objective optimization.

*(English)*Zbl 1451.90170Summary: In evolutionary multi-objective optimization, it is crucial for the evolutionary algorithm to maintain a good balance between convergence and diversity. The recently proposed Two\(\_\)Arch2 algorithm provides a new perspective to solve this problem. However, due to the properties of the mating mechanism and the limitations of the distance-based diversity maintenance scheme, both the computational complexity and the diversity face great challenges as the number of objectives increases. In this paper, we propose an improved Two-Archive algorithm for both multi- and many-objective optimization, aiming at further promoting the balance between convergence and diversity. In the proposed algorithm, we introduce a decomposition idea into the mating pool of the convergence archive, which increases the number of favorable solutions and reduces the computational complexity. At the same time, we apply a penalty angle-based selection scheme to the diversity archive, which effectively maintains the population diversity. The effectiveness of the proposed algorithm is compared with five state-of-the-art multi-objective evolutionary algorithms on a variety of benchmark problems. The experimental results demonstrate that the proposed algorithm has highly competitive performance on both multi- and many-objective optimization problems – in particular, remedying problems of Two\(\_\)Arch2.

##### MSC:

90C59 | Approximation methods and heuristics in mathematical programming |

68W50 | Evolutionary algorithms, genetic algorithms (computational aspects) |

90C29 | Multi-objective and goal programming |

##### Keywords:

evolutionary algorithm; penalty angle; multi-objective optimization; many-objective optimization; two-archive algorithm
Full Text:
DOI

##### References:

[1] | (Aggarwal, C. C.; Hinneburg, A.; Keim, D. A., On the Surprising Behavior of Distance Metrics in High Dimensional Spaces. ICDT (2001), Springer) · Zbl 1047.68038 |

[2] | Agrawal, R. B.; Deb, K.; Agrawal, R., Simulated binary crossover for continuous search space, Complex Syst., 9, 2, 115-148 (1995) · Zbl 0843.68023 |

[3] | Bader, J.; Zitzler, E., HypE: an algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., 19, 1, 45-76 (2011) |

[4] | Beume, N.; Naujoks, B.; Emmerich, M., SMS-EMOA: multiobjective selection based on dominated hypervolume, Eur. J. Oper. Res., 181, 3, 1653-1669 (2007) · Zbl 1123.90064 |

[5] | Cheng, R.; Jin, Y.; Olhofer, M.; Sendhoff, B., A reference vector guided evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 20, 5, 773-791 (2016) |

[6] | (Corne, D. W.; Knowles, J. D.; etal., PESA-II: region-based selection in evolutionary multiobjective optimization. Proceedings of the Genetic and evolutionary Computation Conference (2001), Morgan Kaufmann Publisher: Morgan Kaufmann Publisher San Francisco) |

[7] | Das, I.; Dennis, J. E., Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems, SIAM J. Optim., 8, 3, 631-657 (1998) · Zbl 0911.90287 |

[8] | Deb, K.; Goyal, M., A combined genetic adaptive search (GeneAS) for engineering design, Comput. Sci. Inform., 26, 30-45 (1996) |

[9] | Deb, K.; 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, 577-601 (2014) |

[10] | Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197 (2002) |

[11] | Deb, K.; Sinha, A.; Korhonen, P. J.; Wallenius, J., An interactive evolutionary multiobjective optimization method based on progressively approximated value functions, IEEE Trans. Evol. Comput., 14, 5, 723-739 (2010) |

[12] | Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E., Scalable test problems for evolutionary multiobjective optimization, Evolutionary Multiobjective Optimization Theoretical Advances and Applications, 105-145 (2005) · Zbl 1078.90567 |

[13] | E Ziztler, M. L.; Thiele, L., Spea2: improving the strength pareto evolutionary algorithm for multiobjective optimization, Evolut. Methods Des. Optim. Control, 95-100 (2002) |

[14] | Elarbi, M.; Bechikh, S.; Gupta, A.; Said, L. B.; Ong, Y.-S., A new decomposition-based NSGA-II for many-objective optimization, IEEE Trans. Syst. Man Cybern. Syst., 48, 7, 1191-1210 (2018) |

[15] | He, X.; Zhou, Y.; Chen, Z.; Zhang, Q., Evolutionary many-objective optimization based on dynamical decomposition, IEEE Trans. Evol. Comput., 99, 1, 1-15 (2018) |

[16] | He, Z.; Yen, G. G.; Zhang, J., Fuzzy-based Pareto optimality for many-objective evolutionary algorithms, IEEE Trans. Evol. Comput., 18, 2, 269-285 (2014) |

[17] | (Hernández Gómez, R.; Coello Coello, C. A., Improved metaheuristic based on the R2 indicator for many-objective optimization. Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (2015), ACM) |

[18] | Huband, S.; Hingston, P.; Barone, L.; While, L., A review of multiobjective test problems and a scalable test problem toolkit, IEEE Trans. Evol. Comput., 10, 5, 477-506 (2006) |

[19] | Jara, E. C., Multi-objective optimization by using evolutionary algorithms: the \(p \)-optimality criteria, IEEE Trans. Evol. Comput., 18, 2, 167-179 (2014) |

[20] | Jensen, M. T., Reducing the run-time complexity of multiobjective EAs: the NSGA-II and other algorithms, IEEE Trans. Evol. Comput., 7, 5, 503-515 (2003) |

[21] | Jiang, S.; Yang, S., A strength pareto evolutionary algorithm based on reference direction for multi-objective and many-objective optimization, IEEE Trans. Evol. Comput., 21, 3, 329-346 (2017) |

[22] | (Jiawei, Y.; Hai-Lin, L.; Fangqing, G., A cost value based evolutionary many-objective optimization algorithm with neighbor selection strategy. Proceedings of the 2018 IEEE Congress on Evolutionary Computation (CEC) (2018), IEEE: IEEE Piscataway, NJ, USA), 8-13 July 2018 |

[23] | Li, K.; Deb, K.; Zhang, Q.; Kwong, S., An evolutionary many-objective optimization algorithm based on dominance and decomposition, IEEE Trans. Evol. Comput., 19, 5, 694-716 (2015) |

[24] | Li, M.; Yang, S.; Liu, X., Diversity comparison of Pareto front approximations in many-objective optimization, IEEE Trans. Cybern., 44, 12, 2568-2584 (2014) |

[25] | Li, M.; Yang, S.; Liu, X., Bi-goal evolution for many-objective optimization problems, Artif. Intell., 228, 45-65 (2015) · Zbl 1346.90741 |

[26] | Liu, H. L.; Chen, L.; Deb, K.; Goodman, E., Investigating the effect of imbalance between convergence and diversity in evolutionary multi-objective algorithms, IEEE Trans. Evol. Comput., 21, 3, 408-425 (2016) |

[27] | Liu, H. L.; Gu, F.; Zhang, Q., Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems, IEEE Trans. Evol. Comput., 18, 3, 450-455 (2014) |

[28] | Liu, Y.; Gong, D.; Sun, J.; Jin, Y., A many-objective evolutionary algorithm using a one-by-one selection strategy, IEEE Trans. Cybern., 47, 9, 2689-2702 (2017) |

[29] | Lygoe, R. J.; Cary, M.; Fleming, P. J., A real-world application of a many-objective optimisation complexity reduction process, Proc. 7th Int. Conf. Evol. Multi-Criterion Optim. (EMO), 641-655 (2013), Sheffield: Sheffield U.K. |

[30] | Miettinen, K., Nonlinear Multiobjective Optimization, Volume 12 of International Series in Operations Research and Management Science (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht |

[31] | Morgan, R.; Gallagher, M., Sampling techniques and distance metrics in high dimensional continuous landscape analysis: limitations and improvements, IEEE Trans. Evol. Comput., 18, 3, 456-461 (2014) |

[32] | (Praditwong, K.; Yao, X., A new multi-objective evolutionary optimisation algorithm: the two-archive algorithm. 2006 International Conference on Computational Intelligence and Security (2006), IEEE) |

[33] | (Praditwong, K.; Yao, X., How well do multi-objective evolutionary algorithms scale to large problems. 2007 IEEE Congress on Evolutionary Computation, 2007 CEC (2007), IEEE) |

[34] | Saxena, D. K.; Duro, J. A.; Tiwari, A.; Deb, K.; Zhang, Q., Objective reduction in many-objective optimization: linear and nonlinear algorithms, IEEE Trans. Evol. Comput., 17, 1, 77-99 (2013) |

[35] | Singh, H. K.; Isaacs, A.; Ray, T., A Pareto corner search evolutionary algorithm and dimensionality reduction in many-objective optimization problems, IEEE Trans. Evol. Comput., 15, 4, 539-556 (2011) |

[36] | Tian, Y.; Cheng, R.; Zhang, X.; Cheng, F.; Jin, Y., An indicator based multi-objective evolutionary algorithm with reference point adaptation for better versatility, IEEE Trans. Evol. Comput., 22, 4, 609-622 (2018) |

[37] | Tian, Y.; Cheng, R.; Zhang, X.; Su, Y.; Jin, Y., A strengthened dominance relation considering convergence and diversity for evolutionary many-objective optimization, IEEE Trans. Evol. Comput. (2018) |

[38] | Wang, H.; Jiao, L.; Yao, X., Two_Arch2: an improved two-archive algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 19, 4, 524-541 (2015) |

[39] | While, L.; Hingston, P.; Barone, L.; Huband, S., A faster algorithm for calculating hypervolume, IEEE Trans. Evol. Comput., 10, 1, 29-38 (2006) |

[40] | (Wickramasinghe, U. K.; Carrese, R.; Li, X., Designing airfoils using a reference point based evolutionary many-objective particle swarm optimization algorithm. Proceedings of the 2010 IEEE Congress on Evolutionary Computation (CEC) (2010), IEEE) |

[41] | Yang, S. X.; Li, M. Q.; Liu, X. H.; Zheng, J. H., A grid-based evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 17, 5, 721-736 (2013) |

[42] | Ye, T.; Wang, H.; Zhang, X.; Jin, Y., Effectiveness and efficiency of non-dominated sorting for evolutionary multi- and many-objective optimization, Complex Intell. Syst., 3, 4, 247-263 (2017) |

[43] | Yuan, Y.; Xu, H.; Wang, B.; Yao, X., A new dominance relation-based evolutionary algorithm for many-objective optimization[J], IEEE Trans. Evol. Comput., 20, 1, 16-37 (2016) |

[44] | Yuan, Y.; Xu, H.; Wang, B.; Zhang, B.; Yao, X., Balancing convergence and diversity in decomposition-based many-objective optimizers, IEEE Trans. Evol. Comput., 20, 2, 180-198 (2016) |

[45] | Zhang, Q.; Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 6, 712-731 (2007) |

[46] | (Zhou, A.; Jin, Y.; Zhang, Q.; Sendhoff, B.; Tsang, E., Combining model-based and genetics-based offspring generation for multi-objective optimization using a convergence criterion. Proceedings of the 2006 IEEE Congress on Evolutionary Computation, 2006 CEC (2006), IEEE) |

[47] | (Zitzler, E.; Künzli, S., Indicator-based selection in multiobjective search. Proceedings of the International Conference on Parallel Problem Solving from Nature (2004), Springer) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.