This article proposes a new algorithm based on evolutionary
computation and quantum computing. It attempts to
resolve ordering combinatorial optimization problems, the most
well known of which is the traveling salesman problem (TSP).
Classic and quantum-inspired genetic algorithms based on binary
representations have been previously used to solve combinatorial
optimization problems. However, for ordering combinatorial
optimization problems, order-based genetic algorithms are more
adequate than those with binary representation, since a specialized
crossover process can be employed in order to always generate
feasible solutions. Traditional order-based genetic algorithms
have already been applied to ordering combinatorial
optimization problems but few quantum-inspired genetic algorithms
have been proposed. The algorithm presented in this
paper contributes to the quantum-inspired genetic approach to
solve ordering combinatorial optimization problems. The performance
of the proposed algorithm is compared with one orderbased
genetic algorithm using uniform crossover. In all cases
considered, the results obtained by applying the proposed algorithm
to the TSP were better, both in terms of processing times
and in terms of the quality of the solutions obtained, than those
obtained with order-based genetic algorithms.
|