The Research Of The Hardness Of Travelling Salesman Problem Based On Multi-objective Approaches

The NP-hard combinatorial optimization problem has drawn wide attention in recent yea rs. To address this problem, many algorithms have been proposed and how to select a proper method is a hot topic. The main contribution of this paper is to research the hardness of Tra-velling Salesman Problem (TSP) for the 2-opt method. We extract the features with respect to TSP instances to conduct detailed analysis about the relationships between these features and the hardness of 2-opt method, so as to predict the hardness of the current instance for 2-opt.In the existing literatures, there are two kinds of methods for assessing the hardness of T SP instances for 2-opt from the single perspective. One is the efficiency of 2-opt when addres sing some TSP instances. They think 2-opt possesses high efficiency when solving simple TS P instances and vice versa. The other is the effectiveness of the solutions achieved by 2-opt to evaluate the hardness of the instances, based on which simple TSP instances generally achiev e high quality solutions and vice versa.However, these two approaches both adopt a genetic algorithm to evolve hard and simple TSP instances, and generate comparative analysis with respect to the discrimination of these t wo instances and the relationship between the features and the hardness of instances. Howeve r, these two objectives may conflict with each other. To address this challenge, we evaluate th e hardness of TSP instances by the combination of both the effectiveness and the efficiency objectives. The multi-objective approaches use NSGA-II algorithm and MOEA/D algorithm to generate simple and hard TSP instances, and select features to investigate the relationship b etween the features and the hardness of TSP instances. Experimental results demonstrate that t he multi-objective approaches outperform the single objective approaches with respect to disc overing the relationships between features and the instance hardness. Meanwhile, these new a pproaches facilitate us to predict the distribution of instances in the objective space.