Research On Several Key Problems Of Many-objective Optimization Algorithms

Many-objective optimization problems are the multi-objective optimization problems that with more than three objectives. With the increment of objectives number, multi-objective optimization problems always become difficult to be solved. In recent years, more and more researchers have drawn their attention to dealing with many-objective optimization problems by evolutionary algorithm and other intelligence algorithms. In view of the weaknesses in many-objective algorithms, this thesis proposes several non-dominated sorting algorithms and many-objective evolutionary algorithms from the viewpoints of improving the efficiency and the performance of the algorithm.Firstly, this thesis proposes a efficient framework for non-dominated sorting called ENS. In ENS, solutions to be sorted need to compared only with those that have already been sorted, so that avoiding many unnecessary non-dominated comparisons. Based on this framework, two non-dominated algorithms with different searching strategies are proposed, namely ENS-SS and ENS-BS. Both theoretical analysis and experimental results have demonstrated that, these two non-dominated sorting algorithms can improve the efficiencies of multi-objective algorithms greatly.Secondly, this thesis proposes an efficient non-dominated sorting algorithm for many-objective optimization problems, which called T-ENS. Each pair of solutions in the same non-dominated front needed to be compared in usual non-dominated sorting algorithms, but it is unnecessary for T-ENS, which employs a tree structure to store solutions. As a result, T-ENS can save many non-dominated comparisons in many-objective optimization problems, where there are many solutions in the same front, so that it can improve the efficiencies of many-objective algorithms effectively.Then, this thesis proposes a non-dominated approximate sorting algorithm based on ENS framework called A-ENS, which is also applied to many-objective optimization problems. Different from other non-dominated sorting algorithms, it is unnecessary to do non-dominated comparison between solutions in A-ENS. Instead of this, the algorithm can estimate the dominance relation of two solutions directly. This estimation strategy decreases the time complexity of non-dominated comparison from 0(M) to 0(1), where M means the number of objectives.Theoretical analysis and experimental result have demonstrated that, many-objective optimization algorithms combined with A-ENS can obtain greater efficiencies and better performances.Finally, for overcoming the shortage of losing selection pressure of non-dominated sorting in many-objective optimization problems, this thesis proposes a new many-objective evolutionary algorithm based on knee point, namely KnEA. Knee points are the solutions which have better convergences in the non-dominated front, the proposed algorithm identifies these knee points with the help of an adaptive method, and gives priority to them in mating selection and environmental selection, so that the selection pressure can be greatly improved. Compared with several popular many-objective evolutionary algorithms in the experiment, it is proved that KnEA can solve many-objective optimization problems more efficiently.