Solving NP-Hard Problems with Physarum-Based Ant Colony System

Yuxin Liu, Chao Gao, Zili Zhang, Yuxiao Lu, Shi Chen, Mingxin Liang, Li Tao

Research output: Contribution to journalArticlepeer-review

77 Scopus citations

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.

Original languageEnglish
Pages (from-to)108-120
Number of pages13
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume14
Issue number1
DOIs
StatePublished - 1 Jan 2017
Externally publishedYes

Keywords

  • 0/1 knapsack problem
  • ant colony system
  • NP-hard problem
  • Physarum-inspired mathematical model
  • positive feedback mechanism
  • traveling salesman problem

Fingerprint

Dive into the research topics of 'Solving NP-Hard Problems with Physarum-Based Ant Colony System'. Together they form a unique fingerprint.

Cite this