A rank-based ant system algorithm for solving 0/1 Knapsack Problem

Shi Chen, Chao Gao, Xianghua Li, Yitong Lu, Zili Zhang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish
Pages (from-to)7423-7430
Number of pages8
JournalJournal of Computational Information Systems
Volume11
Issue number20
DOIs
StatePublished - 15 Oct 2015
Externally publishedYes

Keywords

  • 0/1 knapsack problem
  • AS
  • Ranking

Fingerprint

Dive into the research topics of 'A rank-based ant system algorithm for solving 0/1 Knapsack Problem'. Together they form a unique fingerprint.

Cite this