An (1+1) Evolutionary Strategy for the Solution of the Symmetric Traveling Salesman Problem

摘要

This paper describes a heuristic approach for the generation of good solutions to the Symmetric Traveling Salesman Problem (TSP). The search method implemented follows the principles of a particular Evolution Strategy (ES) called ES(1+1). This kind of ES involves only one parent and one descendant per generation and, as a consequence, the reproduction schema is mutation-based. Since the TSP is a sequencing problem, the original approach of the ES(1+1) to real number optimization has been altered retaining, as possible, the analogies to the original ideas. In each generation an offspring is produced by a TSP specific mutation, for which an ad hoc operator is introduced. The heuristic behind the mutation operator lies on the fact that a good Euclidean TSP tour, and particularly the optimal, does not have crossing edges (or knots). The mutation technique aims to untie the knots and consequently, the evolutionary search is quickly executed over lesser-knotted solutions. Experiments were performed over several instances of the TSP. In all cases the ES quickly reaches high quality solutions which in the worst cases differ only in marginal manner with the best known solutions. A comparison with a GA approach and also some comments about the results of other heuristics are made.