Techniques for achieving balance between convergence and diversity in decomposition multiobjective optimization

基於分解的多目標優化中收斂性與分佈性的平衡技術

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

  • Ke LI

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date3 Oct 2014

Abstract

Many real-world optimization problems simultaneously consider two or more objective functions which are usually in conflict with each other. Instead of a single utopian solution, solving a multiobjective optimization problem (MOP) is to search for a promising set of trade-off solutions that can compromise all those objectives simultaneously. Evolutionary multiobjective optimization approaches, suggested in early nineties, have been widely accepted as a natural choice for solving MOPs. Their popularity is mainly because of their ability to find multiple trade-off solutions in a single run. Most, if not all EMO methodologies are designed to meet two essential but usually conflicting requirements: one is convergence (i.e., the closeness towards the optimal trade-off surface), the other is diversity (i.e., the uniformness of solutions distributed along the surface). However, with the developments of science and technology, real-life optimization scenarios pose even more significant challenges (e.g., complicated Pareto-optimal set, more than three objectives functions and constraints) to the existing EMO algorithms to find a set of satisfied solutions that simultaneously meet those requirements. Multiobjective evolutionary algorithm based on decomposition (MOEA/D) is a recently proposed EMO framework. It decomposes the MOP, in question, into a set of subproblems, whose optima determine the population convergence. The population diversity is controlled by the uniform distribution of weight vectors. In this thesis, under the framework of MOEA/D, extensive research is conducted on the design and analysis of innovative techniques for enhancing the ability of EMO methodologies for handling problems with complicated Pareto-optimal sets, many objectives (more than three) and constraints. At first, based on the stable matching theory, a novel selection operator is developed to assign the appropriate solution to each subproblem. Secondly, based on the multi-armed bandit model, a novel adaptive operator selection mechanism is devised to autonomously select the appropriate mutation operator for offspring generation. Next, in the context of steady-state evolution scheme, instead of conducting the non-dominated sorting from scratch, each time, when introducing a new candidate offspring to the population, an efficient non-domination level update mechanism is suggested to update those solutions that are required to change their non-domination levels. In the final part of this thesis, an unified paradigm, which combines the Pareto dominance- and decomposition-based techniques, is proposed for handling problems with more than three objectives and constraints. Comprehensive experiments fully demonstrate the effectiveness of these proposals in balancing the tradeoff between convergence and diversity in multiobjective optimization.

    Research areas

  • Mathematical optimization