Multi-Objective Evolutionary Algorithms: From Manual Design to Automatic Design

多目標進化算法: 從人手動到自動設計

Student thesis: Doctoral Thesis

View graph of relations


Related Research Unit(s)


Awarding Institution
Award date19 Jul 2021


Multi-objective optimization, which can be found in a wide range of real-world applications, is an important and active research area. To efficiently solve different kinds of multi-objective optimization problems (MOPs), many multi-objective evolutionary algorithms (MOEAs) have been proposed over the last thirty years, but many challenges remain. This thesis focuses on the following issues: 

How to handle constraints in MOEAs? Most existing MOEAs cannot deal with constraints effectively and efficiently, particularly for problems with many local optimal solutions and a disconnected Pareto set. 

How to automatically design efficient MOEAs for specific problems? It is crucial for real-world applications, particularly when users have no good working knowledge of MOEAs and human resources are expensive. 

How to construct a few complementary MOEAs to make the best use of parallel computing environments effectively? This is important since there is no single MOEA outperforms all the others on certain instance distributions.

The major contributions are as follows: 
We design an efficient detect-and-escape strategy (DAE) to escape the local optimum caused by constraints. Specifically, the proposed DAE uses the feasible ratio and the change rate of overall constraint violation to detect stagnation. Once the current population is trapped in a local optimum, DAE will adjust the weight of the constraint violation and guide the search to escape from stagnation states. In addition, we develop and implement a decomposition-based constrained MOEA with this strategy, named MOEA/D-DAE. The experimental results show MOEA/D-DAE can outperform other state-of-the-art constrained MOEAs.

We show that the design of MOEAs can be done in an automatic way. In the automated design of MOEAs, to instantiate both existing and, more importantly, new MOEAs as candidate solutions in a search space, one can construct a flexible and adjustable MOEA framework, referred to as multi-objective evolutionary architecture search framework (mEAS) in this thesis. Concretely, we use mEAS to define a search space that includes many standard components of MOEA (e.g. mating selection, evolutionary operators, replacement). We demonstrate, using designs in mEAS and seven benchmark sets (WFG, UF, mTSP, mQAP, mBQP, LIRCMOP, NCTP), that searching this space is practical and effective.

We demonstrate how an effective algorithm portfolio for MOPs can be produced automatically from the framework of mEAS. We present an algorithm portfolio construction approach with a remove-and-insert strategy, dubbed RIPC, for automatically building a few complementary MOEAs to solve a set of MOPs with different characteristics. In RIPC, the remove-and-insert strategy iteratively removes the least important solver and inserts a new solver with a strong complementarity to the remaining solvers (i.e., all solvers except the removed one). This process is terminated when no further improvement can be achieved. Applied to a set of MOPs, RIPC can successfully construct algorithm portfolio that has a closer approximation of per-instance best solver's performance than those generated by existing approaches.