Abstract

In this thesis, we present different techniques that aim to improve the efficiency
of the multi-objective evolutionary algorithms. By efficiency, we
refer to reducing the number of fitness function evaluations performed by a
multi-objective evolutionary algorithm when solving problems of moderate
dimensionality (up to 30 decision variables). When solving a multi-objective
problem, it is very important to do a good exploration at the beginning of
the search and find quickly promising solutions. After that, an exploitation
of those good solutions is needed to accelerate the convergence and finally
get to the true Pareto front of the multi-objective problem. Additionally, a
mechanism to keep the nondominated solutions is normally used to retain
a well-distributed set of solutions along the Pareto front. We present here
mechanisms that tackle each of these problems: exploration, exploitation
and distribution.

First, we propose a new multi-objective evolutionary algorithm (MOEA)
based on differential evolution and rough sets theory to show how the hybridization
of a fast multi-objective evolutionary algorithm and a local search
method based on the use of rough sets, is an efficient alternative to obtain a
robust algorithm able to solve difficult unconstrained and constrained multiobjective
optimization problems. The proposed approach adopts an external
archive in order to retain the nondominated solutions found during the evolutionary
process. Additionally, the approach also incorporates the concept
of paǫ-dominance to get a good distribution of the solutions retained. The
main idea of the approach is to use differential evolution (DE) as our main
search engine, trying to translate its good convergence properties exhibited
in single-objective optimization to the multi-objective case. Rough sets theory
is adopted in a second stage of the search in order to improve the spread
of the nondominated solutions that have been found so far. Our hybrid approach
is validated using standard test functions and performance measures
commonly adopted in the specialized literature. Our results are compared
with respect to two approaches that are representative of the state-of-the-art
in the area: NSGA-II, and SPEA2.

Secondly, we propose an approach in which a multi-objective particle
swarm optimizer (MOPSO) is coupled to a surrogate method in order to
explore the search space in an efficient manner. In order to determine which
is the most appropriate surrogate method to be adopted, a small compara-
tive study among three surrogate methods is conducted: an artificial neural
network (ANN), a radial basis function (RBF) and a support vector machine
(SVM). The best performer in this comparative study was the support
vector machine, which was, therefore, adopted for our approach. Also, we
perform a comparative study among different leader selection schemes in a
MOPSO, in order to determine the most appropriate approach to be adopted
for solving the sort of problems of our interest. However, our results indicated
that the spread of solutions achieved by our surrogate-based MOEA
was poor. Thus, we decided to introduce a second phase to the algorithm in
which it is hybridized with the rough sets in order to improve the spread of
solutions and reach the true Pareto front. In this case, the rough sets act as
a local search approach which is able to generate solutions in the neighborhood
of the nondominated solutions previously generated. We show that our
proposed hybrid approach only requires 2,000 fitness function evaluations in
order to solve test problems with up to 30 decision variables.
Finally, we propose a mechanism that can be seen as a variant of ǫdominance,
which we call Pareto-adaptive ǫ-dominance (paǫ-dominance).
Our proposed approach overcomes the main limitations of e-dominance: the
loss of several nondominated solutions from the hypergrid adopted in the
archive because of the way in which solutions are selected within each box.