Solving 0-1 knapsack problems based on amoeboid organism algorithm

Xiaoge Zhang, Shiyan Huang, Yong Hu, Yajuan Zhang, Sankaran Mahadevan, Yong Deng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

78 Citations (Scopus)

Abstract

The 0-1 knapsack problem is an open issue in discrete optimization problems, which plays an important role in real applications. In this paper, a new bio-inspired model is proposed to solve this problem. The proposed method has three main steps. First, the 0-1 knapsack problem is converted into a directed graph by the network converting algorithm. Then, for the purpose of using the amoeboid organism model, the longest path problem is transformed into the shortest path problem. Finally, the shortest path problem can be well handled by the amoeboid organism algorithm. Numerical examples are given to illustrate the efficiency of the proposed model.

Original languageEnglish
Pages (from-to)9959-9970
Number of pages12
JournalApplied Mathematics and Computation
Volume219
Issue number19
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • 0-1 Knapsack problem
  • Bio-inspired algorithm
  • Network converting algorithm
  • Optimization
  • Shortest path problem

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Cite this