A comparative study of techniques for handling integer variables using Differential Evolution
Vinicius Kreischer1; Eduardo Krempser2; Helio J. C. Barbosa1
1 Laboratório Nacional de Computação Científica (LNCC); 2 Fundação Oswaldo Cruz (Fiocruz)
Baixar PDF doi:10.20906/CPS/CILAMCE2015-0249
Resumo
Differential Evolution (DE) is a simple and efficient meta-heuristic for global optimization over continuous spaces. As in other Evolutionary Algorithms, a population of candidate solutions is employed alongside operators of recombination, mutation, and selection in order to find better solutions in the search space. Among the main benefits of DE are the reduced number of control parameters and the simplicity to implement, when compared to other EAs, the applicability to problems where an explicit analytical formulation is not available or which lack continuity and/or differentiability, and scalability to complex and/or high dimensional problems. Besides, the results obtained by its application to a wide range of practical problems have proven its robustness. Although DE was initially proposed for problems with continuous variables, a few works have been proposed to extend its applicability to integer valued problems. These works rely on two different approaches, called direct and indirect. In the first approach, the variables of the candidate solutions are encoded using integer representation and the mutation and recombination operators are modified to match this representation. In the indirect approach, the variables are kept as real values, and recombination and mutation operators are not altered. However, mapping techniques are employed so that a real to integer conversion is carried out before a fitness value is computed for a candidate solution. This paper presents a review of some popular techniques found in the literature concerning variants of the original DE aiming at its application to problems with integer variables. Furthermore, three different mapping techniques are applied to a set of 24 integer programming problems in order to establish a comparative analysis using a tool known as Performance Profiles. The results show the influence of problem dimensionality in the performance of the variants studied.
Palavras-chave: Differential Evolution; Integer Programming Problems; Mapping Techniques