Hits:

Indexed by:会议论文

Date of Publication:2014-12-15

Journal:10th International Conference on Simulated Evolution and Learning (SEAL)

Included Journals:EI、CPCI-S

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.