File(s) under permanent embargo
Solving NP-hard problems with physarum-based ant colony system
journal contribution
posted on 2017-01-01, 00:00 authored by Y Liu, C Gao, Zili ZhangZili Zhang, Y Lu, S Chen, M Liang, L TaoNP-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.
History
Journal
IEEE/ACM transactions on computational biology and bioinformaticsVolume
14Issue
1Pagination
108 - 120Publisher
IEEELocation
Piscataway, N.J.Publisher DOI
ISSN
1545-5963Language
engPublication classification
C Journal article; C1.1 Refereed article in a scholarly journalCopyright notice
2015, IEEEUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC