DGSA: discrete gravitational search algorithm for solving knapsack problem

Hedieh Sajedi () and Seyedeh Fatemeh Razavi
Additional contact information
Hedieh Sajedi: University of Tehran
Seyedeh Fatemeh Razavi: University of Tehran

Operational Research, 2017, vol. 17, issue 2, No 10, 563-591

Abstract: Abstract The 0–1 knapsack problem is one of the classic NP-hard problems. It is an open issue in discrete optimization problems, which plays an important role in the real applications. Therefore, several algorithms have been developed to solve it. The Gravitational Search Algorithm (GSA) is an optimization algorithm based on the law of gravity and mass interactions. In the GSA, the searcher agents are a collection of masses that interact with each other based on the Newtonian gravity and the laws of motion. In this algorithm the position of the agents can be considered as the solutions. The GSA is a nature-inspired algorithm that is used for finding the optimum value of continuous functions. This paper introduces a Discrete version of the GSA (DGSA) for solving 0–1 knapsack problem. In this regard, we introduce an approach for discretely updating the position of each agent. In addition, a fitness function has been proposed for 0–1 knapsack problem. Our experimental results show the effectiveness of the DGSA in comparison with other similar algorithms in terms of the accuracy and overcoming the defect of local convergence.

Keywords: Knapsack problem; Gravitational search algorithm; Discrete optimization (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-016-0240-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:17:y:2017:i:2:d:10.1007_s12351-016-0240-2

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-016-0240-2

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().