Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem
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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2018-10-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2018218/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841539449424445440 |
|---|---|
| author | Xuesen MA Shuai GONG Jian ZHU Hao TANG |
| author_facet | Xuesen MA Shuai GONG Jian ZHU Hao TANG |
| author_sort | Xuesen MA |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-a6f2b7186501482c81e25a15baa4c437 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2018-10-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-a6f2b7186501482c81e25a15baa4c4372025-01-14T07:15:36ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2018-10-0139597159721224Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problemXuesen MAShuai GONGJian ZHUHao TANGTo 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.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2018218/ant colony algorithmconvex hullTSPpartially optimal programming |
| spellingShingle | Xuesen MA Shuai GONG Jian ZHU Hao TANG Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem Tongxin xuebao ant colony algorithm convex hull TSP partially optimal programming |
| title | Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem |
| title_full | Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem |
| title_fullStr | Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem |
| title_full_unstemmed | Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem |
| title_short | Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem |
| title_sort | ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving tsp problem |
| topic | ant colony algorithm convex hull TSP partially optimal programming |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2018218/ |
| work_keys_str_mv | AT xuesenma antcolonyalgorithmofpartiallyoptimalprogrammingbasedondynamicconvexhullguidanceforsolvingtspproblem AT shuaigong antcolonyalgorithmofpartiallyoptimalprogrammingbasedondynamicconvexhullguidanceforsolvingtspproblem AT jianzhu antcolonyalgorithmofpartiallyoptimalprogrammingbasedondynamicconvexhullguidanceforsolvingtspproblem AT haotang antcolonyalgorithmofpartiallyoptimalprogrammingbasedondynamicconvexhullguidanceforsolvingtspproblem |