Knee Points in Multi-objective Optimization

In multi-objective optimization, especially in preference-based multi-objective optimization, the knee points usually play an important role. The knee point is a point for which a small improvement in any objective would lead to a large deterioration in at least one other objective. Due to this feature, it  is  widely  believed  that  knee  points are most interesting solutions, naturally preferred solutions and most likely the optimal choice of the decision maker (DM). In the last decade, several methods have been presented to identify knee points or knee regions. Das [1] refers to the point where the Pareto surface “bulges” the most as the knee point, and this point corresponds to the farthest solution from the convex hull of individual minima which is the minima of the single objective functions. Zitzler [2] defines ε-dominance: a solution a is said to ε-dominate a solution b if and only if 𝑓i(a) + ε ≥ 𝑓i(b) ∀i = 1,…,m where m is the number of objectives. A solution with a higher ε-dominance value with respect to the other solutions in the Pareto front approximation, is a solution having higher trade-offs and in this definition corresponds to a knee point.The authors of [3] propose to calculate the density of solutions projected onto the hyperplane constructed by the extreme points of the non-dominated solutions, then identify the knee regions based on the solution density.

Different algorithms of applying knee points in multi-objective evolutionary algorithms (MOEAs) have also been proposed. Branke [4] modifies the second criterion in NSGA-II [5], and replaces the crowding distance by either an angle-based measure or a utility-based measure. The angle-based method calculates the angle between an individual and its two neighbors in the objective space. The smaller the angle, the more clearly the individual can be classified as a knee point. However, this method can only be used for two objective problems. In the utility-based method, a marginal utility function is suggested to approximate the angle-based measure in the case of more than two objectives. The larger the external angle between a solution and its neighbors, the larger the gain in terms of linear utility obtained from substituting the neighbors with the solution of interest. However, the utility-based measure is not suited for finding knees in concave regions of the Pareto front. Rachmawati [6, 7] proposes a knee-based MOEA which computes a transformation of original objective values based on a weighted sum niching approach. The extent and the density of coverage of the knee regions are controllable by the parameters for the niche strength and pool size. Schütze [8] investigates two strategies for the approximation of knees of bi-objective optimization problems with stochastic search algorithms. Several new definitions for identifying knee points and knee regions for bi-objective optimization problems have been suggested in [9] and the possibility of applying them has also been discussed.

By: Yali Wang

[1] I. Das, On characterizing the “knee” of the pareto curve based on normal- boundary intersection, Structural optimization 18 (2-3) (1999) 107–115.

[2] E. Zitzler, M. Laumanns, S. Bleuler, A tutorial on evolutionary multiobjective optimization, in: Metaheuristics for multiobjective optimisation, Springer, 2004, pp. 3–37.

[3] G. Yu, Y. Jin, M. Olhofer, A method for a posteriori identification of knee points based on solution density, in: 2018 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2018, pp. 1–8.

[4] J. Branke, K. Deb, H. Dierolf, M. Osswald, Finding knees in multi-objective optimization, in: International conference on parallel problem solving from nature, Springer, 2004, pp. 722–731.

[5] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multi- objective genetic algorithm: Nsga-ii, IEEE transactions on evolutionary computation 6 (2) (2002) 182–197.

[6] L. Rachmawati, D. Srinivasan, A multi-objective evolutionary algorithm with weighted-sum niching for convergence on knee regions, in: Proceedings of the 8th annual conference on Genetic and evolutionary computation, 2006, pp. 749–750.

[7] L. Rachmawati, D. Srinivasan, A multi-objective genetic algorithm with controllable convergence on knee regions, in: 2006 IEEE International Con- ference on Evolutionary Computation, IEEE, 2006, pp. 1916–1923.

[8] O. Schütze, M. Laumanns, C. A. C. Coello, Approximating the knee of an mop with stochastic search algorithms, in: International Conference on Parallel Problem Solving from Nature, Springer, 2008, pp. 795–804.

[9] K. Deb, S. Gupta, Understanding knee points in bicriteria problems and their implications as preferred solution principles, Engineering optimization 43 (11) (2011) 1175–1204.