Solving NP-Hard Problems with Physarum-Based Ant Colony System
Authors:
- 29 July 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 14 (1) , 108-120
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
Funding Information
- National Science and Technology Support Program (2012BAD35B08)
- National High Technology Research and Development Program of China (2013AA013801)
- National Natural Science Foundation of China (61402379, 61403315)
- Natural Science Foundation of Chongqing Municipality (cstc2012jjA40013, cstc2013jcyjA40022)
This publication has 34 references indexed in Scilit:
- MapReduce-Based Ant Colony Optimization Algorithm for Multi-Dimensional Knapsack ProblemApplied Mechanics and Materials, 2013
- Ant Colony Optimization Algorithm for the 0-1 Knapsack Problem Based on Genetic OperatorsAdvanced Materials Research, 2011
- A memetic ant colony optimization algorithm for the dynamic travelling salesman problemSoft Computing, 2010
- Rules for Biologically Inspired Adaptive Network DesignScience, 2010
- Particle swarm optimization-based algorithms for TSP and generalized TSPInformation Processing Letters, 2007
- A mathematical model for adaptive transport network in path finding by true slime moldJournal of Theoretical Biology, 2007
- Metaheuristics in Combinatorial OptimizationAnnals of Operations Research, 2005
- Ant colony system: a cooperative learning approach to the traveling salesman problemIEEE Transactions on Evolutionary Computation, 1997
- Some Applications of the Generalized Travelling Salesman ProblemJournal of the Operational Research Society, 1996
- On large deviations of the empiric D. F. of vector chance variables and a law of the iterated logarithmPacific Journal of Mathematics, 1961