A New Dynamic Multi-objective Optimization Evolutionary Algorithm
Bojin Zheng
College of Computer Science, South-Central University For Nationalities, Wuhan 430074,China
zhengbojin@gmail.com
Abstract
Dynamic Multi-objective Optimization Problems are
very common in real-world applications. The researches
on applying Evolutionary Algorithm into such problems
are attracting more and more researchers. In this paper,
a new Dynamic Multi-objective Optimization Evolutionary
Algorithm which utilizes hyper-mutation operator to deal
with dynamics and Geometrical Pareto Selection to deal
with multi-objective is introduced. The experimental results
show that the performance is satisfactory.
1 Introduction
Many real-world optimization problems involves mul-
tiple objectives which vary with the time, such problems
could be called “Dynamic Multi-objective Optimization
Problems” (DMOP). Since DMOPs involve the Dynamic
Optimization and Multi-objective Optimization simultane-
ously, the principles in both the fields would be useful
to the researches on DMOP. Since Evolutionary Algo-
rithms have been successfully applied into both the fields,
they would be promising in dealing with DMOP. Now
Dynamic Multi-objective Optimization Evolutionary Algo-
rithms (DMOEA) is becoming a hot topic.
Hyper-mutation [4] is an intuitive approach when deal-
ing with the dynamics. To compare with the other popular
Dynamic Optimization Evolutionary Algorithms (DOEAs),
such as memory-based DOEAs, multi-population DOEAs
and prediction based DOEAs etc., this algorithm is simpler
without loss of the efficiency.
As to the Multi-objective Optimization Evolutionary Al-
gorithms (MOEA), many of them, such as NSGA-II[1],
SPEA2[7] etc., are efficient. But considering that DMOEAs
should have a lower time complexity, we choose Geometri-
cal Pareto Selection Algorithm (GPS)[6] to deal with mul-
tiple objectives.
Based on the ideas above, we proposed a new DMOEA.
This algorithm utilizes hyper-mutation operator to deal with
the dynamic environment, Geometrical Pareto Selection as
the archiving algorithm to deal with multiple objectives and
Cellular Genetic Algorithm to generate the individuals.
2 Introduction to Proposed Algorithm
DMOEA should include some strategies to deal with
the dynamics of DMOPs. Since memory-based, multi-
population and prediction based approaches are not easy to
be implemented in DMOEAs, hyper-mutation is chosen in
our algorithm. As to the detection of dynamic environment,
we use some individuals as the sentinels.
Considering that the dynamics of DMOPs would in-
herently desire less running time and enough individuals
should be generated to produce better Pareto front, we hope
the proposed algorithm would spend less time to archiv-
ing algorithm so that we could have more time to generate
more individuals. Since SPEA2 and NSGA-II hold high-
time-complexity archivers[3], that is, more than O(mN
2
)
(here m is the dimensions of objectives and N the population
size), and GPS’s time complexity is O(mN ),weintegrate
GPS into this DMOEA.
In this algorithm, the population is divided into m+1 sub-
populations, every sub-population would evolve toward one
extreme points or the average of all the objectives. Thus,
multi-objective is divided into multiple single-objective.
Cellular Genetic Algorithm is used to optimization every
sub-population.
2.1 Hyper-mutation operator
Obviously, the hyper-mutation operator in DMOEA
would not be same to in DOEA. When the environment
changes, this operator would be executed to utilize the past
elite solutions, that is , copy some elite solutions in the
archive into the population, the other individuals in popu-
lation would be replaced by random individuals.
We use the following formula to determine the number
of selected elite solutions.
NumberOfSelected =
SizeOfArchive
SizeOfArchive + PopSize
(1)