A knee point based NSGA-II multi-objective evolutionary algorithm. (English) Zbl 07240000

Pan, Linqiang (ed.) et al., Bio-inspired computing: theories and applications. 14th international conference, BIC-TA 2019, Zhengzhou, China, November 22–25, 2019. Revised selected papers. Part I. Singapore: Springer. Commun. Comput. Inf. Sci. 1159, 454-467 (2020).
Summary: Many evolutionary algorithms (EAs) can’t select the solution which can accelerate the convergence to the Pareto front and maintain the diversity from a group of non-dominant solutions in the late stage of searching. In this article, the method of finding knee point is embedded in the process of searching, which not only increases selection pressure solutions in later searches but also accelerates diversity and convergence. Besides, niche strategy and special crowding distances are used to solve multimodal features in test problems, so as to provide decision-makers with multiple alternative solutions as much as possible. Finally, the performance indicators of knee point are compared with the existing algorithms on 14 test functions. The results show that the final solution set of the proposed algorithm has advantages in coverage area of the reference knee regions and convergence speed.
For the entire collection see [Zbl 1440.68009].


68Q07 Biologically inspired models of computation (DNA computing, membrane computing, etc.)


Full Text: DOI


[1] Deb, K., Member, A., Pratap, A., et al.: A fast and elitist multi-objective genetic algorithm NSGAII. IEEE Trans. Evol. Comput. 6(2), 182-197 (2002)
[2] Zitzler, E., Laumanns, M., Thiele, L.: SPEA2_improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, pp. 95-100 (2001)
[3] Horn, J., Nafpliotis, N., Goldberg, D.E.: A niched Pareto genetic algorithm for multi-objective optimization. In: IEEE Conference on Evolutionary Computation IEEE World Congress on Computational Intelligence (1994)
[4] Corne, D.W., Knowles, J.D., Oates, M.J.: The Pareto envelope-based selection algorithm for multiobjective optimization. In: Schoenauer, M., et al. (eds.) PPSN 2000. LNCS, vol. 1917, pp. 839-848. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45356-3_82
[5] Zhang, X., Tian, Y., Jin, Y.: A knee point driven evolutionary algorithm for many-objective optimization. IEEE Trans. Evol. Comput. 19(6), 761-776 (2015)
[6] Rachmawati, L., Srinivasan, D.: Multiobjective evolutionary algorithm with controllable focus on the knees of the Pareto front. IEEE Trans. Evol. Comput. 13(4), 810-824 (2009)
[7] Schütze, O., Laumanns, M., Coello, C.A.C.: Approximating the knee of an MOP with stochastic search algorithms. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 795-804. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87700-4_79
[8] Deb, K., Gupta, S.: Understanding knee points in bicriteria problems and their implications as preferred solution principles. Eng. Optim. 43(11), 1175-1204 (2011)
[9] Sudeng, S., Wattanapongsakorn, N.: Adaptive geometric angle-based algorithm with independent objective biasing for pruning Pareto-optimal solutions. In: Science & Information Conference (2013)
[10] Branke, J., Deb, K., Dierolf, H., Osswald, M.: Finding knees in multi-objective optimization. In: Yao, X., et al. (eds.) PPSN 2004. LNCS, vol. 3242, pp. 722-731. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30217-9_73
[11] Bhattacharjee, K., Singh, H., Ryan, M., et al.: Bridging the gap: many-objective optimization and informed decision-making. IEEE Trans. Evol. Comput. 21(5), 813-820 (2017)
[12] Das, I.: On characterizing the “knee” of the Pareto curve based on normal-boundary intersection. Struct. Optim. 18(2-3), 107-115 (1999)
[13] Yu, G., Jin, Y., Olhofer, M.: A Method for a posteriori identification of knee points based on solution density. In: Presented at the Congress on Evolutionary Computation (2018)
[14] Qu, B.Y., Suganthan, P.N.: Novel multimodal problems and differential evolution with ensemble of restricted tournament selection. In: Evolutionary Computation, pp. 3480-3486 (2010)
[15] Preuss, M.: Niching methods and multimodal optimization performance. Multimodal Optimization by Means of Evolutionary Algorithms. NCS, pp. 115-137. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-07407-8_5
[16] While, L., Hingston, P., Barone, L., et al.: A faster algorithm for calculating hypervolume. IEEE Trans. Evol. Comput. 10(1), 29-38 (2006)
[17] Jong, D., Alan, K.: Analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis University of Michigan (1975)
[18] Holland, J.H.: Adaptation in Natural and Artificial Systems, vol. 6, 2nd edn, pp. 126-137. MIT Press, Cambridge (1992)
[19] Petrowski, A.: A clearing procedure as a niching method for genetic algorithms. In: Proceedings of the IEEE International Conference on Evolutionary Computation (1996)
[20] Li, J.P., Balazs, M.E., Parks, G.T., et al.: A species conserving genetic algorithm for multimodal function optimization. Evol. Comput. 10(3), 207-234 (2014)
[21] Liang, J.J., Yue, C.T., Qu, B.Y.: Multimodal multi-objective optimization: a preliminary study. In: Evolutionary Computation (2016)
[22] Yue, C.T., Qu, B., Jing, L.: A Multi-objective particle swarm optimizer using ring topology for solving multimodal multi-objective problems. IEEE Trans. Evol. Comput. 22(5), 805-817 (2017)
[23] Yu, G.
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.