Modelo de computación evolutivo para redes sostenibles, eficientes y resistentes.

Abstract

We present a new approach to adapt the differential evolution (DE) algorithm so that it can be applied in combinatorial optimization problems. The differential evolution algorithm has been proposed as an optimization algorithm for the continuous domain, using real numbers to encode the solutions, and its main operator, the mutation, uses a arithmetic operations to create a mutant using three different random solutions. This mutation operator cannot be used in combinatorial optimization problems, which have a domain of a discrete and finite set of objects. Based on this concept, we present an idea of representing each solution as a set, and replace the arithmetic operators in the classic DE genetic operators by set operators. Using a well known NP-hard problem, the traveling salesman problem (TSP), as an example of a combinatorial optimization problem, we study different possibilities for the mutation operator, presenting the advantages and disadvantages of each, before setting with the best one. We also explain the modifications made to adapt the algorithm for a multiobjective optimization algorithm. Some of these modifications are inherent to the different type of problems, other modification are proposed to improve the algorithm. Amongst the later modification are using more than one population in the evolution process. We also present a new self-adaptive variation of the multiobjective optimization algorithm, although this is not limited to the multi-objective case, and can be used also in the single-objective.