A Stable Matching-Based Selection and Memory
Enhanced MOEA/D for Evolutionary Dynamic
Multiobjective Optimization
Xiaofeng Chen
Department of Computer Science
Xiamen University
Xiamen, China
Defu Zhang
Department of Computer Science
Xiamen University
Xiamen, China
dfzhang@xmu.edu.cn
Xiangxiang Zeng
Department of Computer Science
Xiamen University
Xiamen, China
Abstract—In the real world, dynamic changes may occur during
multi-objective optimization. In those situations, it is vital to
track the time-varying Pareto optimal set over time. This paper is
to integrate a memory-enhanced multi-objective evolutionary
algorithm based on decomposition (denoted by dMOEA/D-M)
with a simple and effective stable matching (STM) model
(denoted by dMOEA/D-STM). MOEA/D is an effective algorithm
for optimizing static multi-objective problems. For adapting to
the dynamic changes, firstly, an improved environment detector
is presented. Then, memory and matching skills is designed to
address the difficulties of re-initialization. The STM model,
which originates from economics, guides the re-initialization in
dMOEA/D-STM. Empirical experiments prove the effectiveness
of the memory strategy and STM model.
Keywords- dynamic environment; evolutionary algorithm; multi-
objective optimization; memory approach; stable matching
I. INTRODUCTION
Multi-objective optimization problems (MOPs) exist in
many real-world situations. Due to the goals of the problems
conflict with each other, a trade-off set of solutions, namely
Pareto optimal set (POS), is desired. Evolutionary multi-
objective optimization (EMO) focuses on applying
evolutionary algorithms to solve MOPs. EMO has become a
hot research topic. Lots of effective algorithms have been
proposed, such as vector evaluation genetic algorithm (VEGA)
[1], Pareto archived evolutionary strategy (PAES) [2], strength
Pareto evolutionary algorithm II (SPEA-II) [3], non-dominated
sorting genetic algorithm II (NSGA-II) [4], multi-objective
evolutionary algorithm based on decomposition (MOEA/D) [5]
and Local search-based multi-objective optimization algorithm
[6]. MOEA/D decomposes a multi-objective optimization
problem into a number of scalar optimization sub-problems and
optimizes them simultaneously. It won the CEC2009
Competition. Compared to most of the Multi-objective
Optimization Evolutionary Algorithms (MOEAs), MOEA/D
can obtain lower computation complexity, better solution set
convergence and distribution.
However, when dealing with Dynamic Multi-objective
Optimization Problems (DMOPs), the optimization algorithm
must be capable of not only evolving a near-optimal and
diverse Pareto optimal front (POF), but also tracking the time-
varying environment. Evolutionary Algorithms (EAs) and
Particle swarm optimization (PSO) are two excellent tools to
address DMOPs due to their inspiration from natural self-
organized systems and biological evolution, which must cope
with dynamic environment [6]. In dynamic optimization, it is
important to maintain diversity in the population in order to
improve the tracking ability. Three major ways of handling
population diversity are: diversity introduction, diversity
maintenance and employing multiple populations. Two other
techniques include prediction-based and memory approaches
are also being used to solve DMOPs.
Since most of the MOEAs are designed for Static Multi-
objective Optimization Problems (SMOPs), Deb et al. [8]
extended the NSGA-II to deal with dynamic environment. A
way to detect environment changes is added and two strategies
are proposed when changes are detected. The algorithm can
either be restarted by introducing diversity using random
initialization or select a number of solutions for hyper-mutation
[8]. Goh and Tan [9] proposed Dynamic Competitive-
Cooperative Algorithm (dCOEA) that hybridizes competitive
and cooperative mechanisms to allow adaptive problem
decomposition. Stochastic competitors which introduce
diversity and a technique to handle outdated archived solutions
which exploits useful information of the previous environments
are integrated into dCOEA. dMOEA/D-M [10] is proposed by
Liu and Zeng. They adapted the MOEA/D to Dynamic
Changes. This paper proposes a modified dMOEA/D-M which
is integrated with stable matching (STM) model [11]. Stable
matching, proposed by economists, has solid theoretical
foundations and has been used in various fields. The STM
model has been introduced to Multi-Objective Optimization in
[11]. Li el al. [11] shows that STM model is effective to
balance convergence and diversity of the evolutionary search.
The organization of this paper is as follows. Section II
provides a brief description of the dynamic MO optimization
problem and related work. Brief introduction of MOEA/D and
stable matching model are presented in Section III. Section IV
describes the detailed dMOEA/D-STM. Extensive empirical
studies are conducted in Section V to prove the effectiveness of
STM model. Conclusions are drawn in Section VI.
2015 IEEE 27th International Conference on Tools with Artificial Intelligence
1082-3409/15 $31.00 © 2015 IEEE
DOI 10.1109/ICTAI.2015.77
477
2015 IEEE 27th International Conference on Tools with Artificial Intelligence
1082-3409/15 $31.00 © 2015 IEEE
DOI 10.1109/ICTAI.2015.77
478
2015 IEEE 27th International Conference on Tools with Artificial Intelligence
1082-3409/15 $31.00 © 2015 IEEE
DOI 10.1109/ICTAI.2015.77
478