Pearson correlation coefficient-based pheromone refactoring mechanism for multi-colony ant colony optimization
- PDF / 2,796,034 Bytes
- 23 Pages / 595.224 x 790.955 pts Page_size
- 85 Downloads / 214 Views
Pearson correlation coefficient-based pheromone refactoring mechanism for multi-colony ant colony optimization Han Pan1 · Xiaoming You1
· Sheng Liu1 · Dehui Zhang1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract To solve the problem of falling into local optimum and poor convergence speed in large Traveling Salesman Problem (TSP), this paper proposes a Pearson correlation coefficient-based Pheromone refactoring mechanism for multi-colony Ant Colony Optimization (PPACO). First, the dynamic guidance mechanism is introduced to dynamically adjust the pheromone concentration on the path of the maximum and minimum spanning tree, which can effectively balance the diversity and convergence of the algorithm. Secondly, the frequency of communication between colonies is adjusted adaptively according to a criterion based on the similarity between the minimum spanning tree and the optimal solution. Besides, the pheromone matrix of the colony is reconstructed according to the Pearson correlation coefficient or information entropy to help the algorithm jump out of the local optimum, thus improving the accuracy of the solution. These strategies greatly improve the adaptability of the algorithm and ensure the effectiveness of the interaction. Finally, the experimental results indicate that the proposed algorithm could improve the solution accuracy and accelerate the convergence speed, especially for large-scale TSP instances. Keywords Pearson correlation coefficient · Multi-colony · TSP · Information entropy · Minimum spanning tree
1 Introduction Traveling Salesman Problem is a typical combinatorial optimization problem and a Non-deterministic Polynomial Complete (NP-C) problem. It is a concentrated generalization and simplified form of various complex problems in many fields and has become an indirect comparison standard of heuristic search and optimization algorithms. Besides, TSP is widely used in many fields, such as transportation, computer network, circuit board design, and logistics distribution. Therefore, it has important theoretical value and high practical value to solve TSP quickly and effectively. The TSP can be explained as that the traveler knows the mutual distances between n cities. He starts from a certain city, then visits each city once and only once before returning to the first city. Lastly, he asks to find the shortest
Xiaoming You
[email protected] Han Pan [email protected] 1
Shanghai University of Engineering Science, Shanghai, China
path to traverse n cities. In the beginning, optimal solution algorithms have been used to solve TSP, such as the branch and bound method and the dynamic programming method. Although the optimal solution algorithm yields exact solution, the computation time is intolerable and hence various approximation methods have been developed, such as the MM algorithm, greedy algorithm, and the MST algorithm. These approximation algorithms are not satisfactorily close to the optimal solution, although they can obtain feasible solutions that are close to t
Data Loading...
