IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v17y2017i2d10.1007_s12351-016-0240-2.html
   My bibliography  Save this article

DGSA: discrete gravitational search algorithm for solving knapsack problem

Author

Listed:
  • Hedieh Sajedi

    (University of Tehran)

  • Seyedeh Fatemeh Razavi

    (University of Tehran)

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.

Suggested Citation

  • Hedieh Sajedi & Seyedeh Fatemeh Razavi, 2017. "DGSA: discrete gravitational search algorithm for solving knapsack problem," Operational Research, Springer, vol. 17(2), pages 563-591, July.
    • Handle: RePEc:spr:operea:v:17:y:2017:i:2:d:10.1007_s12351-016-0240-2
    DOI: 10.1007/s12351-016-0240-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-016-0240-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s12351-016-0240-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Shams, Masumeh & Rashedi, Esmat & Hakimi, Ahmad, 2015. "Clustered-gravitational search algorithm and its application in parameter optimization of a low noise amplifier," Applied Mathematics and Computation, Elsevier, vol. 258(C), pages 436-453.
    2. Mavrotas, George & Diakoulaki, Danae & Kourentzis, Athanasios, 2008. "Selection among ranked projects under segmentation, policy and logical constraints," European Journal of Operational Research, Elsevier, vol. 187(1), pages 177-192, May.
    3. Lin, Feng-Tse, 2008. "Solving the knapsack problem with imprecise weight coefficients using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 185(1), pages 133-145, February.
    4. Wan-li Xiang & Mei-qing An & Yin-zhen Li & Rui-chun He & Jing-fang Zhang, 2014. "A Novel Discrete Global-Best Harmony Search Algorithm for Solving 0-1 Knapsack Problems," Discrete Dynamics in Nature and Society, Hindawi, vol. 2014, pages 1-12, April.
    5. Florios, Kostas & Mavrotas, George & Diakoulaki, Danae, 2010. "Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms," European Journal of Operational Research, Elsevier, vol. 203(1), pages 14-21, May.
    6. Mavrotas, George & Florios, Kostas & Figueira, José Rui, 2015. "An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: A computational study and comparison with meta-heuristics," Applied Mathematics and Computation, Elsevier, vol. 270(C), pages 25-43.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Madjid Tavana & Kaveh Khalili-Damghani & Amir-Reza Abtahi, 2013. "A fuzzy multidimensional multiple-choice knapsack model for project portfolio selection using an evolutionary algorithm," Annals of Operations Research, Springer, vol. 206(1), pages 449-483, July.
    2. Mavrotas, George & Florios, Kostas, 2013. "An improved version of the augmented epsilon-constraint method (AUGMECON2) for finding the exact Pareto set in Multi-Objective Integer Programming problems," MPRA Paper 105034, University Library of Munich, Germany.
    3. Panos Xidonas & Haris Doukas & George Mavrotas & Olena Pechak, 2016. "Environmental corporate responsibility for investments evaluation: an alternative multi-objective programming model," Annals of Operations Research, Springer, vol. 247(2), pages 395-413, December.
    4. Tsionas, Mike G., 2019. "Multi-objective optimization using statistical models," European Journal of Operational Research, Elsevier, vol. 276(1), pages 364-378.
    5. Caetani, Alberto Pavlick & Ferreira, Luciano & Borenstein, Denis, 2016. "Development of an integrated decision-making method for an oil refinery restructuring in Brazil," Energy, Elsevier, vol. 111(C), pages 197-210.
    6. Yanhong Feng & Xu Yu & Gai-Ge Wang, 2019. "A Novel Monarch Butterfly Optimization with Global Position Updating Operator for Large-Scale 0-1 Knapsack Problems," Mathematics, MDPI, vol. 7(11), pages 1-31, November.
    7. Mavrotas, George & Figueira, José Rui & Siskos, Eleftherios, 2015. "Robustness analysis methodology for multi-objective combinatorial optimization problems and application to project selection," Omega, Elsevier, vol. 52(C), pages 142-155.
    8. Amirhossein Tahmouresi & Esmat Rashedi & Mohammad Mehdi Yaghoobi & Masoud Rezaei, 2022. "Gene selection using pyramid gravitational search algorithm," PLOS ONE, Public Library of Science, vol. 17(3), pages 1-15, March.
    9. Casado, Ramon Swell Gomes Rodrigues & Alencar, Marcelo Hazin & de Almeida, Adiel Teixeira, 2022. "Combining a multidimensional risk evaluation with an implicit enumeration algorithm to tackle the portfolio selection problem of a natural gas pipeline," Reliability Engineering and System Safety, Elsevier, vol. 221(C).
    10. Pérez, Fátima & Gómez, Trinidad & Caballero, Rafael & Liern, Vicente, 2018. "Project portfolio selection and planning with fuzzy constraints," Technological Forecasting and Social Change, Elsevier, vol. 131(C), pages 117-129.
    11. Yanhong Feng & Hongmei Wang & Zhaoquan Cai & Mingliang Li & Xi Li, 2023. "Hybrid Learning Moth Search Algorithm for Solving Multidimensional Knapsack Problems," Mathematics, MDPI, vol. 11(8), pages 1-28, April.
    12. Hadi Jahangir & Mohammad Mohammadi & Seyed Hamid Reza Pasandideh & Neda Zendehdel Nobari, 2019. "Comparing performance of genetic and discrete invasive weed optimization algorithms for solving the inventory routing problem with an incremental delivery," Journal of Intelligent Manufacturing, Springer, vol. 30(6), pages 2327-2353, August.
    13. Rong, Aiying & Figueira, José Rui, 2013. "A reduction dynamic programming algorithm for the bi-objective integer knapsack problem," European Journal of Operational Research, Elsevier, vol. 231(2), pages 299-313.
    14. I. Kaliszewski & J. Miroforidis, 2022. "Probing the Pareto front of a large-scale multiobjective problem with a MIP solver," Operational Research, Springer, vol. 22(5), pages 5617-5673, November.
    15. Schäfer, Luca E. & Dietz, Tobias & Barbati, Maria & Figueira, José Rui & Greco, Salvatore & Ruzika, Stefan, 2021. "The binary knapsack problem with qualitative levels," European Journal of Operational Research, Elsevier, vol. 289(2), pages 508-514.
    16. R?zvan C?t?lin DOBREA & Felicia Alina DINU, 2014. "A Build-Up Algorithm For Sustainable Discount Rates Projections," Proceedings of the INTERNATIONAL MANAGEMENT CONFERENCE, Faculty of Management, Academy of Economic Studies, Bucharest, Romania, vol. 8(1), pages 1181-1191, November.
    17. Cerqueus, Audrey & Przybylski, Anthony & Gandibleux, Xavier, 2015. "Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems," European Journal of Operational Research, Elsevier, vol. 244(2), pages 417-433.
    18. Rong, Aiying & Figueira, José Rui, 2014. "Dynamic programming algorithms for the bi-objective integer knapsack problem," European Journal of Operational Research, Elsevier, vol. 236(1), pages 85-99.
    19. Mavrotas, George & Makryvelios, Evangelos, 2021. "Combining multiple criteria analysis, mathematical programming and Monte Carlo simulation to tackle uncertainty in Research and Development project portfolio selection: A case study from Greece," European Journal of Operational Research, Elsevier, vol. 291(2), pages 794-806.
    20. Mavrotas, George & Florios, Kostas & Figueira, José Rui, 2015. "An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: A computational study and comparison with meta-heuristics," Applied Mathematics and Computation, Elsevier, vol. 270(C), pages 25-43.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:operea:v:17:y:2017:i:2:d:10.1007_s12351-016-0240-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.