Metodi di selezioni approssimati in problemi di ottimizzazione multi e many objectives

Real-world problems often present multiple conflicting criteria (or objectives) to optimise. These problems belong to a class called Multiobjective Optimization. The goal of this engineering task s the search of approximation of the so-called Pareto set. The latter is a set composed of those solutions which cannot be outperformed by other solutions on all the objectives at once (there are no solutions that are clearly better than a Pareto solution). Although several population-based metaheuristics have been demonstrated to be successful at solving this task when two or three objectives are under consideration, in the presence of four or more criteria, they fail at detecting a reliable approximation of the Pareto set. A problem of this category is referred as Many-Objective Optimisation Problem . One of the main challenges related to the consideration of many objectives is the effective and efficient comparison and hence selection of a set of candidate solutions. In order to aid the selection process several indicators have been proposed in the literature with the aim of characterising the quality of a solution and/or of a selected set of solutions. One successful and extremely regarded indicator is the Hypervolume indicator (or s-metric). This indicator measures the n-dimensional objective space that is "contained" by a set of point, thus measuring the quality of a non dominated set. Furthermore, this indicator can be used to measure the contribution of each solution towards the hypervolume. Despite of its potential within the selection process, this indicator is unfortunately not always usable since its calculation can be extremely onerous (it is a NP-hard problem) and its complexity grows exponentially with the dimensionality of objective space. This thesis analyses and compares different selection methods based on the hypervolume indicator and its approximations as well as proposes some approximated solutions which aim at dramatically reduce the computational cost of the hypervolume based selection process. The main ideas in the proposed methods in this thesis are reduction, filtering, and simplified modelling of the population. The approach employed by all the variants proposed in this thesis is the replacement of multiple neighbour solutions (in the objective space) with an artificial solution that represents, within the approximated Pareto, the removed group. The resulting approximated set is then not as highly populated as the original one, thus allowing a much faster estimation of the hypervolume value. Numerical results show that this idea leads to a substantial reduction of computation cost accompanied by a negligible accuracy loss with respect to the full-cost hypervolume values.