Analysis of Optimization Heuristics for Multiobjective Problems


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.