点击次数：

论文类型：会议论文

发表时间：2014-12-15

收录刊物：EI、CPCI-S

卷号：8886

页面范围：216-227

关键字：TSP; 2-opt; multi-objective optimization algorithm; random forest

摘要：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.