Research And Implementation Of Knee Point Identification Based On Multi-Objective Optimisation Algorithm

Multi-objective optimisation problems consider simultaneously optimising two or more conflicting objectives.Evolutionary multi-objective optimisation algorithms which finding a set of well-converged and well-diversified solutions that approximate the whole Pareto front,are widely used to solve multi-objective optimisation problems.However,rather than the whole Pareto-optimal region,decision makers usually interest in only a small set of trade-off points most relevant to them.In addition,providing a large number of trade-offs for a decision maker will not only increase the workload,but also impedes the accurate decision making.In reality,the ultimate goal of multi-objective optimisation problems is to provide a decision maker with some solutions that meet her/his preferences.Knee points,characterised as their smallest trade-off loss at all objectives,are attractive to decision makers in multi-criterion decision-making.In contrast,other Pareto-optimal solutions are less attractive since a small improvement on one objective can lead to a significant degradation on at least one of the other objectives.Therefore,this thesis studies knee point identification in evolutionary multi-objective optimization problems.Our major work and contributions are outlined as follows.This thesis provides a systematic overview of the existing developments of knee point identification and briefly put forward the shortcomings of the existing methods.Based on these,this thesis proposes a simple and effective knee point identification method based on trade-off utility,dubbed KPITU,to help decision makers identify knee points from a given set of trade-off solutions.This thesis proposes the knee-dominance.The basic idea of the knee-dominance is to provide the ability to discriminate non-dominated solutions from the trade-off perspective.It is not uncommon that a test problem has more than one knee point,as known as local knee points.To enable the identification of local knee points,we restrict the comparison of knee-dominance within the neighbourhood of each solution.Besides,in order to compare the importance of different local knee points,this thesis proposes the accumulative trade-off utility.Specifically,local knee points can be sorted according to their accumulative trade-off utility.In summary,the basic idea of KPITU is to sequentially validate whether a solution is a knee point or not by comparing its trade-off utility with others within its neighbourhood.More specifically,a solution is a knee point if and only if it has the best trade-off utility among its neighbours.The proposed KPITU is able to identify as many knee point(s)as possible on test problems with different Pareto front shapes and is scalable to any number of objectives.Furthermore,we propose NSGA-II-KPITU in this thesis.Our basic idea is to use KPITU to replace the crowding distance calculation in NSGA-II.KPITU is incorporated into the environmental selection of NSGA-II to demonstrate its usefulness as an operator to guide an EMO algorithm to search for knee points on the fly during the evolutionary process.Finally,in order to validate the effectiveness of KPITU,we first compare KPITU's performance with five state-of-the-art knee point identification methods on CKP,DO2 DK,DEB2DK,DEB3 DK and PMOP test suite.Empirical results fully demonstrate the out-standing performance of KPITU especially on problems with many local knee points.Fur-thermore,KPITU is scalable to any number of objectives and can identify knee point(s)of test problems under any number of objectives.We validate the usefulness of NSGA-II-KPITU for guiding EMO algorithms to search for knee points during the evolution-ary process.Three knee point driven algorithms,i.e.,NSGA-II-CD,NSGA-II-EMU and NSGA-II-CHIM,are used as peer algorithms for comparison purpose.