Evolving Hard and Easy Traveling Salesman Problem Instances: A Multi-objective Approach


It becomes a great challenge in the research area of meta- heuristics to predict the hardness of combinatorial optimization problem instances for a given algorithm. In this study, we focus on the hardness of the traveling salesman problem (TSP) for 2-opt. In the existing lit- erature, two approaches are available to measure the hardness of TSP instances for 2-opt based on the single objective: the efficiency or the ef- fectiveness of 2-opt. However, these two objectives may conflict with each other. To address this issue, we combine both objectives to evaluate the hardness of TSP instances, and evolve instances by a multi-objective op- timization algorithm. Experiments demonstrate that the multi-objective approach discovers new relationships between features and hardness of the instances. Meanwhile, this new approach facilitates us to predict the distribution of instances in the objective space.