Selection in evolutionary algorithms for the traveling salesman problem
Jens Gottlieb, Torben A. Kruse · 2000
Empirical results, obtained with an evolutionary algorithm for the traveling salesman problem, reveal that the replacement scheme strongly affects the choice of an appropriate selection pressure for the parent selection phase.Some popular methods like linear ranking fail to yield a sufficiently high selection pressure for generational replacement.The (p + 1)-replacement scheme induces enough selection pressure, such that the parents might be selected pure randomly.Additional experiments with the inver-over operator demonstrate classical replacement schemes failing for such an atypical operator.Further, we present a proof of the expected fitness distribution's equivalence of linear ranking and binary tournament selection (with replacement).This theoretical result enables an empirical demonstration of stochastic universal sampling's superiority to the implicit sampling of tournament selection.