An Evolutionary Algorithm with Diversified Crossover Operator for the Heterogeneous Probabilistic TSP

摘要

This paper focuses on investigating the effectiveness of the diversified crossover (DCX) operator under an evolutionary algorithm framework to solve the PTSP. Different combinations of four well-performed crossover operators for the TSP/PTSP, i.e., edge recombination (ER) crossover, order crossover (OX), order based crossover (OBX), and position based crossover (PBX), were used to investigate its effects. A set of numerical experiments were conducted to test the validity of the proposed strategy based on 90 randomly generated test instances. The numerical results showed that the DCX operator, especially by combining ER and OX crossover operators, can most effectively solve heterogeneous PTSP in most of the tested instances in comparison with the single crossover operator used in most of the previous studies. These findings show the potential of merging the proposed DCX operator into the solution framework of evolutionary algorithm, genetic algorithm or memetic algorithm for effectively solving other complicated optimization problems.