Dissertação para obtenção do Grau de Mestre em

In multiobjective optimization, usually due to the complex nature of the problems considered, it is sometimes not possible to find all optimal solutions in a reasonable amount of time. One alternative is to use methods to find good approximation sets, such as Stochastic Multiobjective Optimizers. To assess the outcomes produced by these multiobjective optimizers, quality indicators such as the hypervolume indicator have been proposed. The hypervolume indicator is one of the most studied unary quality indicators, and algorithms are available to compute it in any number of dimensions. It has also been included in stochastic optimizers, such as evolutionary algorithms. Therefore, the time spent computing the hypervolume indicator is an important issue. An alternative to the hypervolume indicator is the Empirical Attainment Function (EAF), which is oriented towards the study of the distribution of the output of different executions of the same optimizer, but the algorithms available are restricted to two and three dimensions. In this thesis, new efficient algorithms to compute the hypervolume indicator are proposed, and new algorithms to compute the EAF in two and four dimensions are developed. As a result, the scope of application of the EAF is extended to four objective problems, and the current upper bound on the complexity of the hypervolume indicator in four dimensions is improved to O(n2). Finally, the divide-and-conquer paradigm is shown to hold promise for the development of this type of algorithms