This thesis concerns the convergence of several heuristic
algorithms for multiobjective optimization problems.
A heuristic optimization algorithm is a computational algorithm
that tries to imitate some physical or biological processes
such as the evolution of the species, the human immune system,
the social behavior of some animal groups (for instance,
bees and ants), and so on.
These processes are themselves optimization processes and so
they naturally suggest computational algorithms applicable
to mathematical optimization problems.
Some of these algorithms and related references are:
* simulated annealing [23, 39],
* genetic algorithms [17],
* evolution strategies [45],
* evolutionary programming [15, 14],
* artificial immune system algorithm [6, 37],
* particle swarm optimization [22, 12].
These heuristic techniques are extremely useful, in particular
for optimization problems for which the traditional methods are
difficult to apply.
As we already noted, our work deals with multiobjective
optimization problems (MOPs). A typical example is when we try
to maximize a certain utility or revenue function, but simultaneously
we wish to minimize, say, an operation cost. Thus in a MOP we can
have objective functions representing conflicting interests. In
many of these situations, the heuristic algorithms usually perform
quite well, but there were no mathematical results ensuring the
convergence of the algorithms. Here is where the main contribution
of our work comes in: we give conditions for the convergence, in a
suitable sense, of some of the most common heuristic algorithms for
MOPs.
A feature of MOP is that, as a rule, the solution set can be quite
large, possibly infinite, and of course we would like our algorithms
to describe as well as possible this set. Here we propose some modified
algorithms that allow us to obtain very good representations of the
solutions sets.
Finally, to illustrate our approach, we consider the
Markowitz portfolio selection problem. This is an important problem
in which one wishes to find an investment portfolio that maximizes
the expected return, with minimum risk.
This work is organized as follows: in Chapter 1 we present the
multiobjective optimization problem. The simulated annealing algorithm
and the proof of its convergence, for the multiobjective case, are in
Chapter 2. The convergence of a general heuristic optimization, again
for the multiobjective case, appears in Chapter 3. Chapter 4 contains
the algorithm of the artificial immune system and its convergence. A
new scheme to maintain diversity, based on stripes, is presented in
Chapter 5. Finally, in Chapter 6 we apply our results to the Markowitz
portfolio selection problem.