Abstract
The 0/1 Knapsack Problem (KP), which is a classical NP-complete problem, has been widely applied to solving many real world problems. Ant system (AS), as one of the earliest ant colony optimization (ACO) algorithms, provides approximate solutions to 0/1 KPs. However, there are some shortcomings such as low efficiency and premature convergence in most AS algorithms. In order to overcome the shortcomings of AS, this paper proposes a rank-based AS algorithm, denoted as RAS to solve 0/1 KP. Taking advantages of the ranked ants with a higher profit, the pheromone of items will be updated with better solutions in RAS. Experimental results in different datasets show that this new kind of AS algorithm can obtain a higher efficiency and robustness when solving 0/1 KP.
Original language | English |
---|---|
Pages (from-to) | 7423-7430 |
Number of pages | 8 |
Journal | Journal of Computational Information Systems |
Volume | 11 |
Issue number | 20 |
DOIs | |
State | Published - 15 Oct 2015 |
Externally published | Yes |
Keywords
- 0/1 knapsack problem
- AS
- Ranking