Use of Coevolution and Fitness Inheritance for Multiobjective Particle Swarm Optimization


In this dissertation, we present our studies and proposals for reducing computational cost in multi-objective evolutionary optimization. First, we describe a coevolutionary multi-objective approach that we designed in the first stage of our work, whose main motivation was to achieve a computational cost reduction. The main idea of the proposed coevolutionary algorithm is to obtain information throughout the evolutionary process in order to subdivide the search space into subregions, use a subpopulation for each of these subregions and focus the search in the “promising” subregions of the search space. The proposed approach is validated using several test functions taken from the specialized literature. Then, with the aim of improving the results provided by the coevolutionary approach (especially in functions with high-dimensional decision search space), a new multiobjective particle swarm optimization algorithm was designed to replace the genetic algorithm originally adopted as search engine. This new multi-objective approach is based on the use of Pareto dominance, crowding factors, different mutation operators and e-dominance. This approach is detailed and validated, and its parameters are studied by means of an analysis of variance. As a result, on-line mechanisms to adapt the values of the most important parameters are proposed. Also, several test functions are studied in order to explore those types of problems in which our algorithm has some difficulties. Furthermore, this algorithm is also tested with constrained functions and it is finally incorporated into the coevolutionary approach previously mentioned. After that, we provide an enhancement technique based on fitness inheritance, proposed to reduce the computational cost when applying the multi-objective particle swarm approach previously mentioned. In fitness inheritance, the fitness value of an offspring is obtained from the fitness values of its parents. In this way, we do not need to evaluate every individual at each generation, and the computational cost is reduced. We perform a study of several different techniques to incorporate fitness inheritance into our approach, and propose a dynamical scheme to obtain the larger possible amount of savings (in terms of function evaluations), without affecting in a significant way the quality of the results. Finally, we discuss some theoretical issues related to the work developed, covering both particle swarm optimization and fitness inheritance.