Comparing decoding algorithms in a weight-coded GA for TSP
Bryant A. Julstrom · 1998
A novel coding of candidate solutions in genetic algorithms for combinatorial problems associates numerical weights with elements of the target problem instance. The solution a chromosome of weights represents is made explicit by a heuristic algorithm for the problem whose actions the weights influence. The choice of the heuristic---called the decoding algorithm---is a crucial one in a genetic algorithm that employs such a coding. This paper describes a weighted coding of tours in a genetic algorithm for the traveling salesman problem and an investigation of nine heuristics for TSP as decoding algorithms in that GA. Two greedy heuristics performed poorly, but heuristics that build tours by insertion--- adding each new city so as to increase the tour length the least---did better. Several showed excellent performance on TSP instances of moderate size. The results indicate both the importance of the decoding algorithm in a GA that uses a weighted coding and the potential of such codings...