Deakin University
Browse

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 Tao
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.

History

Journal

IEEE/ACM transactions on computational biology and bioinformatics

Volume

14

Pagination

108-120

Location

Piscataway, N.J.

ISSN

1545-5963

Language

eng

Publication classification

C Journal article, C1.1 Refereed article in a scholarly journal

Copyright notice

2015, IEEE

Issue

1

Publisher

IEEE