Release Time:2019-03-11  Hits:

Indexed by: Conference Paper

Date of Publication: 2014-12-15

Included Journals: CPCI-S、EI

Volume: 8886

Page Number: 216-227

Key Words: TSP; 2-opt; multi-objective optimization algorithm; random forest

Abstract: It becomes a great challenge in the research area of metaheuristics 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 literature, two approaches are available to measure the hardness of TSP instances for 2-opt based on the single objective: the efficiency or the effectiveness 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 optimization 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.