Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem |
| |
Authors: | Xuesen MA Shuai GONG Jian ZHU Hao TANG |
| |
Affiliation: | 1. School of Computer and Information,Hefei University of Technology,Hefei 230009,China;2. Research Institute of Sanshui &Hefei University of Technology in Guangdong,Foshan 528000,China;3. School of electrical and Automation Engineering,Hefei University of Technology,Hefei 230009,China |
| |
Abstract: | To solve basic ant colony algorithm’s drawbacks of large search space,low convergence rate and easiness of trapping in local optimal solution,an ant colony algorithm of partially optimal programming based on dynamic convex hull guidance was proposed.The improved algorithm dynamically controlled the urban selection range of the ants,which could reduce the search space of ants on basis of helping the algorithm to jump out of local optimal solution to global optimal solution.Meanwhile,the delayed drift factor and the convex hull constructed by the cities to be chosen were introduced to intervene the current ants’ urban choice,it could increase the diversity of the early solution of the algorithm and improve the ability of ants’ partially optimal programming.Then the pheromone updating was coordinated by using construction information of convex hull and the complete path information that combined local with whole,it could improve the accuracy of the algorithm by guiding the subsequent ants to partially optimal programming.The pheromone maximum and minimum limit strategy with convergence was designed to avoid the algorithm’s premature stagnation and accelerate the solving speed of the algorithm.Finally,the proposed algorithm was applied to four classic TSP models.Simulation results show that the algorithm has better optimal solution,higher convergence rate and better applicability. |
| |
Keywords: | ant colony algorithm convex hull TSP partially optimal programming |
|
| 点击此处可从《通信学报》浏览原始摘要信息 |
|
点击此处可从《通信学报》下载全文 |
|