Development of techniques to improve computational efficiency in multi-objective evolutionary algorithms


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.