×

A novel many-objective evolutionary algorithm based on transfer matrix with kriging model. (English) Zbl 1456.90145

Summary: Due to the curse of dimensionality caused by the increasing number of objectives, it is very challenging to tackle many-objective optimization problems (MaOPs). Aiming at this issue, this paper proposes a novel many-objective evolutionary algorithm, called Tk-MaOEA, based on transfer matrix assisted by Kriging model. In this approach, for the global space optimization, a transfer matrix is used as a map tool to reduce the number of objectives, which can simplify the optimization process. For the objective optimization, the Kriging model is incorporated to further reduce the computation cost. In addition, the fast non-dominated sorting and farthest-candidate selection (FCS) methods are used to guarantee the diversity of solutions. Comprehensive experiments on a set of benchmark functions have been conducted. Experimental results show that Tk-MaOEA is effective for solving complex MaOPs.

MSC:

90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

SPEA2; MOEA/D; ParEGO; MOMBI
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Toffolo, A.; Benini, E., Genetic diversity as an objective in multi-objectiveevolutionary algorithms, Evol. Comput., 11, 2, 151-157 (2003)
[2] Forrester, A. I.J.; Keane, A. J., Recent advances in surrogate-based optimization, Prog. Aerosp. Sci., 45, 1, 50-79 (Jan. 2009)
[3] Chen, B.; Zeng, W.; Lin, Y., A new local search-based multiobjective optimization algorithm, IEEE Trans. Evol. Comput., 19, 1, 1 (2014)
[4] Chugh, T.; Jin, Y.; Miettinen, K., ”A Surrogate-Assisted Reference Vector Guided Evolutionary Algorithm for Computationally Expensive Many-Objective Optimization, IEEE Trans. Evol. Comput., 22, 1, 129-142 (2018)
[5] Brockhoff, D.; Zitzler, E., Are all objectives necessary? On dimensionality reduction in evolutionary multiobjective optimization, (Proc. 9th PPSN, LNCS 4193 (2006)), 533-542
[6] Saxena, D.; Deb, K., Non-linear dimensionality reduction procedures for certain large-dimensional multi-objective optimization problems: employing correntropy and a novel maximum variance unfolding, Evol. Multi-Criterion Optim., 4403, 772-787 (2007)
[7] Zitzler, E.; Künzli, S., Indicator-based selection in multiobjective search, (Parallel Problem Solving from Nature-PPSN VIII. Parallel Problem Solving from Nature-PPSN VIII, Berlin, Germany (2004), Springer), 832-842
[8] Zitzler, E.; Laumanns, M.; Thiele, L., SPEA2: Improving the strength pareto evolutionary algorithm, (Proc. EUROGEN 2001: Evolutionary Methods Design Optimization Control Appl. Ind. Problems. Proc. EUROGEN 2001: Evolutionary Methods Design Optimization Control Appl. Ind. Problems, Athens, Greece (2002)), 95-100
[9] Friedman, M., A Comparison of Alternative Tests of Significance for the Problem of m Rankings, Ann. Math. Stat., 11, 1, 86-92 (1940) · JFM 66.1305.08
[10] Venturelli, G.; Benini, E.; Łaniewski-Wołłk, Ł., A Kriging-assisted multiobjective evolutionary algorithm, Appl. Soft Comput., 58, 155-175 (Sep. 2017)
[11] Venturelli, G.; Benini, E.; Łaniewski-Wołłk, Ł., A Kriging-assisted Multiobjective Evolutionary Algorithm, Appl. Soft Comput., 58, 155-175 (2017)
[12] Ishibuchi, H.; Masuda, H.; Tanigaki, Y.; Nojima, Y., Difficulties in specifying reference points to calculate the inverted generational distance for many-objective optimization problems, (Proc. IEEE Symp. Comput. Intell. Multi-Criteria Decis. Making (MCDM). Proc. IEEE Symp. Comput. Intell. Multi-Criteria Decis. Making (MCDM), Orlando, FL, USA (2014)), 170-177
[13] Ishibuchi, H.; Tanigaki, Y.; Masuda, H.; Nojima, Y., Distance-based analysis of crossover operators for many-objective knapsack problems, (Proc. Int. Conf. Parallel Prob. Solv. Nat.. Proc. Int. Conf. Parallel Prob. Solv. Nat., Ljubljana, Slovenia (2014)), 600-610
[14] Singh, H. K.; Isaacs, A.; Ray, T., A Pareto corner search evolutionary algorithm and dimensionality reduction in many-objective optimization problems, Evol. Comput. IEEE Trans., 15, 4, 539-556 (2011)
[15] Singh, H.; 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)
[16] 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)
[17] Yu, H.; Tan, Y.; Zeng, J., Surrogate-assisted hierarchical particle swarm optimization, Inf. Sci., 454-455 (2018)
[18] Hernandez Gomez, R.; CoelloCoello, C., MOMBI: A new metaheuristic for many-objective optimization based on the R2 indicator, Evol. Comput., 2488-2495 (2013)
[19] Deb, K.; Saxena, D. K., Searching for Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multiobjective optimization problems, (Proc. IEEE CEC (Jul. 2006)), 3353-3360
[20] K. Deb and D. Saxena, “On finding Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems,” Kanpur Genet. Algorithms Lab., Indian Inst. Technol. Kanpur, Kanpur, India, KanGAL Tech. Rep. 2005011, 2005.; K. Deb and D. Saxena, “On finding Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems,” Kanpur Genet. Algorithms Lab., Indian Inst. Technol. Kanpur, Kanpur, India, KanGAL Tech. Rep. 2005011, 2005.
[21] 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 (Apr. 2002)
[22] 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 (Aug. 2014)
[23] Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E., Scalable test problems for evolutionary multi-objective optimization (2001), Dept. Comput. Eng. Netw. Lab., ETH Zurich: Dept. Comput. Eng. Netw. Lab., ETH Zurich Zurich, Switzerland, TIK-Tech. Rep. 112
[24] Deb, K.; Mohan, M.; Mishra, S., Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions, Evol. Comput., 13, 4, 501-525 (2005)
[25] Ikeda, K.; Kita, H.; Kobayashi, S., Failure of Pareto-based MOEAs: does non-dominated really mean near to optimal. Evolutionary Computation, 2001, (Proceedings of the 2001 Congress on, 2 (2001), IEEE), 957-962
[26] Knowles, J., ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems \([J]\), IEEE Trans. Evol. Comput., 10, 1, 50-66 (2006)
[27] Saul, L. K.; Weinberger, K. Q.; Ham, J. H.; Sha, F.; Lee, D. D., Spectral methods for dimensionality reduction, (Schoelkopf, O. C.B.; Zien, A., Semisupervised Learning (2006), MIT Press: MIT Press Cambridge, MA)
[28] Ma, L.; Hu, K.; Zhu, Y.; Chen, H., Cooperative artificial bee colony algorithm for multi-objective RFID network planning, J. Netw. Comput. Appl., 42, 143-162 (2014)
[29] Ma, L.; Hu, K.; Zhu, Y.; Chen, H., Improved Multi-objective Artificial Bee Colony Algorithm for optimal power flow problem, J. Central South University, 21, 11, 4220-4227 (2014)
[30] Ma, L.; Li, X.; Gao, T., Indicator-Based Multi-objective Bacterial Foraging Algorithm with Adaptive Searching Mechanism \([C]\), Bio-Inspired Computing - Theories and Applications, 271-277 (2016), Springer: Springer Singapore
[31] Ma, L.; S. Cheng, X. Wang; M. Huang, H. Shen; He, X.; Shi, Y., Cooperative two-engine multi-objective bee foraging algorithm with reinforcement learning, Knowl.-Based Syst., 133, 278-293 (2017), 2017
[32] Ma, L.; Wang, X.; Huang, M.; Zhang, H.; Chen, H., A novel evolutionary root system growth algorithm for solving multi-objective optimization problems, Appl. Soft Comput., 57, 379-398 (2017)
[33] Ma, L.; Wang, X.; M. Huang, Z. Lin; L. Tian, H. Chen, Two-level master-slave rfid networks planning via hybrid multi-objective artificial bee colony optimizer, IEEE Trans. Syst. Man, Cybern., 99, 1-20 (2017)
[34] Köppen, M.; Yoshida, K., Substitute distance assignments in NSGAII for handling many-objective optimization problems, (Proc. EMO, 4403 (2007)), 727-741
[35] Min, A. T.W.; Ong, Y. S.; Gupta, A., Multi-Problem Surrogates: Transfer Evolutionary Multiobjective Optimization of Computationally Expensive Problems \([J]\), IEEE Trans. Evol. Comput., 99, 1 (2017)
[36] Chen, N.; Chen, W. N.; Gong, Y. J., An evolutionary algorithm with double-level archives for multiobjective optimization, IEEE Trans. Cybern., 45, 9, 1851-1863 (2015)
[37] Zhang, Q.; Li, H., MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 6, 712-731 (Dec. 2007)
[38] Cheng, R.; Jin, Y.; Olhofer, M., A reference vector guided evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput. (2016)
[39] Gómez, R. H.; Coello, C. A.C., Improved metaheuristic based on the R2 indicator for many-objective optimization, (Proc. Genet. Evol. Comput. Conf.. Proc. Genet. Evol. Comput. Conf., Madrid, Spain (2015)), 679-686
[40] Wang, R.; Lai, S.; Wu, G.; L. Xing, L. Wang; Ishibuchide, H., Multi-clustering via evolutionary multi-objective optimization, Inf. Sci., 450, 128-140 (2018) · Zbl 1440.68244
[41] Wang, R.; Chen, S.; Ma, L., Multi-indicator bacterial foraging algorithm with Kriging Model for many-objective optimization \([M]\), Adv. Swarm Intell., 530-539 (2018)
[42] Bandyopadhyay, S.; Mukherjee, A., An Algorithm for Many-Objective Optimization With Reduced Objective Computations: A Study in Differential Evolution, IEEE Trans. Evol. Comput., 19, 3, 400-413 (2015)
[43] Horng, S. C.; Lin, S. Y., Evolutionary algorithm assisted by surrogate model in the framework of ordinal optimization and optimal computing budget allocation, Inf. Sci., 233, 2, 214-229 (2013)
[44] Jeong, S.; Minemura, Y.; Obayashi, S., Optimization of combustion chamber for diesel engine using Kriging model, J. Fluid Sci. Technol., 1, 2, 138-146 (Dec. 2006)
[45] Kukkonen, S.; Lampinen, J., Ranking-dominance and many-objective optimization, (Proc. IEEE Congr. Evol. Comput. (CEC). Proc. IEEE Congr. Evol. Comput. (CEC), Singapore (2007)), 3983-3990
[46] Yang, S.; Li, M.; Liu, X.; Zheng, J., A grid-based evolutionary algorithm for many-objective optimization. Evolutionary Computation, IEEE Trans., 17, 5, 721-736 (2013)
[47] Khare, V.; Yao, X.; Deb, K., Performance scaling of multi-objective evolutionary algorithms, (Proc. Evol. Multi-Criterion Optim.. Proc. Evol. Multi-Criterion Optim., Faro, Portugal (2003)), 376-390 · Zbl 1036.90541
[48] Connover, W. J., Practical Nonparametric Statistics (1999), Wiley: Wiley New York, NY, USA, ch. 5
[49] Zhang, X.; Tian, Y.; Jin, Y., Approximate non-dominated sorting for evolutionary many-objective optimization, Inf. Sci., 369, 14-33 (2016) · Zbl 1428.90185
[50] Jin, Y., Surrogate-assisted evolutionary computation: Recent advances and future challenges, Swarm Evol. Comput., 1, 2, 61-70 (Jun. 2011)
[51] Xiang, Y.; Zhou, Y.; Li, M., A vector angle-based evolutionary algorithm for unconstrained many-objective optimization, IEEE Trans. Evol. Comput., 21, 1, 131-152 (2017)
[52] He, Z.; Yen, G. G., Many-objective evolutionary algorithm: objective space reduction and diversity improvement \([J]\), IEEE Trans. Evol. Comput., 20, 1, 145-160 (2016)
[53] Xiufen, Z.; Yu, C.; Minzhong, L., A new evolutionary algorithm for solving many-objective optimization problems, Syst. Man Cybern. Part B Cybern. IEEE Trans., 38, 5, 1402-1412 (2008)
[54] Jaimes, A. L.; Coello, C. A.C.; Chakraborty, D., Objective reduction using a feature selection technique, (Proc. GECCO (2008)), 673-680
[55] Scholkopf, B.; Smola, A.; Muller, K. R., Nonlinear component analysis as a kernel eigenvalue problem, Neural Comput., 10, 5, 1299-1319 (1998)
[56] Liu, B.; Zhang, Q.; Gielen, G. G.E., A gaussian process surrogate model assisted evolutionary algorithm for medium scale expensive optimization problems, IEEE Trans. Evol. Comput., 18, 2, 180-192 (2014)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.