Algoritmo baseado em evolução diferencial para solução de problemas de otimização combinatória

Abstract

Combinatorial optimization problems are defined on sets and the solution for these problems can be seen as choosing a subset of possible elements to optimize an objective function, subject to some constraints. Problems of this nature can be found in many real situations but, despite being simple to understand, the task of finding optimal solution can be prohibitive. Many combinatorial optimization problems belongs to the class NP-hard. Thus, the study and development of new algorithmic techniques to obtain good solutions is very important. An algorithm that has attracted the attention of researches is the differential evolution (DE) by its good convergence characteristics, and also for its simplicity of implementation. However, the DE was originally designed to solve continuous optimization problems. Due to its features, some researchers have attempted to adapt this algorithm for solving combinatorial optimization problems. However, these adaptations do not preserve the features that has attracted the attention to the original DE, and their behavior has been found to essentially perform little more than a random search. This is due to an inappropriate choice for encoding solutions. To address this issues we adopt an set-based approach for use with the structure of DE algorithm. The arithmetic operators of the differential mutation are replaced by operations on sets and still maintaining its features. Computational experiments suggest the superiority of the proposed technique over existing DE adaptations for combinatorial optimization, using instances of the traveling salesman problem as a testbed. The proposed adaptation was also compared to other usual approaches for combinatorial optimization, and returned competitive results for the capacitated centered clustering problem.