Physarum-Based Ant Colony Optimization And Applications In Traveling Salesman Problem

NP-hard problem is one of the computer science major research questions. Garey proposed that if a problem is defined as NP-hard problem, it can not be solved exactly by computer. This argument laid the foundation for the calculation obscure boundaries, avoiding the researchers to solve such problems without return. But in the practical problems, NP-hard problem can not avoid, such as road network planning, industrial control, network construction, etc. Since the existing judgment indicates that the computer can not solve NP-hard problem exactly, researchers have turned to solve NP-hard problem approximately, and made great progress.As a classical NP-hard problem,(multi-objective) traveling salesman problem has a wide range of applications, such as vehicle scheduling problem and the recommended route. It is important for theory and engineering to proposing an efficient algorithm for solving the(multi-objective) traveling salesman problem. Currently, swarm intelligence algorithms have become the mainstream for solving(multi-objective) traveling salesman problem, including genetic algorithms, particle swarm optimization and ant colony optimization.Ant colony optimization for solving the classical traveling salesman problem reflects the robustness and feasibility, so many researchers use ant colony optimization to solve(multi-objective) traveling salesman problem. Ant colony optimizations are mainly divided into three categories: based on the goal conversion, based on population and based on Pareto optimal categories. Although the current ant colony optimization for solving the(multi-objective) traveling salesman problem have made great progress, due to the communication between the ant populations depending on the pheromone positive feedback, it leads that the ants tend to focus on selecting a limited feasible Pareto front. This situation results in some problems, such as the distribution of the solution too focus, coverage problem solution space too narrow and falling into the local optimal solution; and ant colony optimization has strong blindness in the initial search, resulting in poor search efficiency. In summary, the ant colony optimizations have further room for improvement.In biological experiments, a single-celled slime molds Physarum due to exhibit excellent path optimization capability and ability to navigate the road network attracted the attention of researchers. Tero found a unique feature of Physarum that critical tubes are reserved in the process of network evolution. According this feature, he proposed a mathematical model for the foraging process of Physarum. So, this paper optimizes ant colony optimization based on Physarum mathematical model.In new algorithms, this study first roughly optimizes each object of multi-objective traveling salesman problem by Physarum mathematical model to get a “map”. Although this "map" is not necessarily accurate, but there are some guidance. Meanwhile, using the "map" to initialize the ant colony algorithm pheromone matrix could solve the problem of blindness in the early search process. There is volatile mechanism in ant colony optimization, so that the deviation map will not seriously affect the search process efficiency. In spite of the pheromone evaporation existing, the pheromone carried by the “map” does not quickly disappear. So new algorithms can expand the range of search, get feasible solutions and make the solutions distributed on the Pareto front more extensive, which are proved by a large number of simulation experiments. Then, this paper converts the top ten tourist of Shanxi province attractions route problem to a multi-objective traveling salesman problem. In this problem, there are two factors to balance which are the distance and the time. The route provided by the new algorithms is feasible, and gets a high satisfaction. The application shows that the new algorithms not only have theoretical validity, but also have a real-world practicality.This article compares the optimization algorithm with another Physarum-based swarm intelligence algorithm in the 4 simulated datasets. The results show that the new algorithm is superior to contrast algorithm in the accuracy of feasible solutions, spatial coverage and runtime.