| Title: | Solving NP-Hard Problems with Physarum-Based Ant Colony System |
| Author(s): | Liu Y; Gao C; Zhang Z; Lu Y; Chen S; Liang M; Tao L; |
| Journal Title: | IEEE/ACM Trans Comput Biol Bioinform |
| DOI: | 10.1109/TCBB.2015.2462349 |
| ISSN/ISBN: | 1557-9964 (Electronic) 1545-5963 (Linking) |
| Abstract: | "NP-hard problems exist in many real world applications. Ant colony optimization (ACO) algorithms can provide approximate solutions for those NP-hard problems, but the performance of ACO algorithms is significantly reduced due to premature convergence and weak robustness, etc. With these observations in mind, this paper proposes a Physarum-based pheromone matrix optimization strategy in ant colony system (ACS) for solving NP-hard problems such as traveling salesman problem (TSP) and 0/1 knapsack problem (0/1 KP). In the Physarum-inspired mathematical model, one of the unique characteristics is that critical tubes can be reserved in the process of network evolution. The optimized updating strategy employs the unique feature and accelerates the positive feedback process in ACS, which contributes to the quick convergence of the optimal solution. Some experiments were conducted using both benchmark and real datasets. The experimental results show that the optimized ACS outperforms other meta-heuristic algorithms in accuracy and robustness for solving TSPs. Meanwhile, the convergence rate and robustness for solving 0/1 KPs are better than those of classical ACS" |
| Keywords: | "*Algorithms Animals Ants/*physiology Biomimetics/*methods Computer Simulation *Decision Support Techniques Models, Biological Models, Statistical Pheromones/*metabolism Physarum/*physiology;" |
| Notes: | "MedlineLiu, Yuxin Gao, Chao Zhang, Zili Lu, Yuxiao Chen, Shi Liang, Mingxin Tao, Li eng Research Support, Non-U.S. Gov't 2017/02/10 IEEE/ACM Trans Comput Biol Bioinform. 2017 Jan-Feb; 14(1):108-120. doi: 10.1109/TCBB.2015.2462349" |
