A GENETIC ALGORITHM TO SOLVE THE MULTIDIMENSIONAL KNAPSACK PROBLEM

In this paper, The Multidimensional Knapsack Problem (MKP) which occurs in many different applications is studied and a genetic algorithm to solve the MKP is proposed. Unlike the technique of the classical genetic algorithm, initial population is not randomly generated in the proposed algorithm, thus the solution space is scanned more efficiently. Moreover, the algorithm is written in C programming language and is tested on randomly generated instances. It is seen that the algorithm yields optimal solutions for all instances.

Computer Science Mathematics

View graph Source

Paper

Full text

A GENETIC ALGORITHM TO SOLVE THE MULTIDIMENSIONAL KNAPSACK PROBLEM

Semantic Scholar · Computer Science · 2013

Abstract

In this paper, The Multidimensional Knapsack Problem (MKP) which occurs in many different applications is studied and a genetic algorithm to solve the MKP is proposed. Unlike the technique of the classical genetic algorithm, initial population is not randomly generated in the proposed algorithm, thus the solution space is scanned more efficiently. Moreover, the algorithm is written in C programming language and is tested on randomly generated instances. It is seen that the algorithm yields optimal solutions for all instances.

Source of record · Semantic Scholar

References (18)

01The Multidimensional Knapsack Problem: Structure and AlgorithmsJakob Puchinger, G. Raidl, Ulrich Pferschy2010 · INFORMS journal on computing · 220 citations

02Empirical Analysis of Locality, Heritability and Heuristic Bias in Evolutionary Algorithms: A Case Study for the Multidimensional Knapsack ProblemG. Raidl, J. Gottlieb2005 · Evolutionary Computation · 110 citations

03Improved results on the 0-1 multidimensional knapsack problemMichel Vasquez, Yannick Vimont2005 · European Journal of Operational Research · 170 citations

04The multidimensional 0-1 knapsack problem: An overviewA. Fréville2004 · European Journal of Operational Research · 490 citations

05A hybrid approach for the 0-1 multidimensional knapsack problemMichel Vasquez, Jin-Kao Hao2001 · International Joint Conference on Artificial Intelligence · 171 citations

06On the Effectivity of Evolutionary Algorithms for the Multidimensional Knapsack ProblemJ. Gottlieb1999 · Artificial Evolution · 32 citations

07A Bibliographical Survey On Some Well-Known Non-Standard Knapsack ProblemsE. Lin1998 · 108 citations

08A Genetic Algorithm for the Multidimensional Knapsack ProblemP. Chu, J. E. Beasley1998 · J. Heuristics · 923 citations

09An improved genetic algorithm for the multiconstrained 0-1 knapsack problemG. Raidl1998 · 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360) · 139 citations

10Using surrogate constraints in genetic algorithms for solving multidimensional knapsack problemsChristian Haul, S. Voss1997 · 19 citations

11Some Experiences On Solving Multiconstraint Zero-One Knapsack Problems With Genetic AlgorithmsJ. Thiel, S. Voss1994 · 91 citations

12The zero/one multiple knapsack problem and genetic algorithmsS. Khuri, Thomas Bäck, Jörg Heitkötter1994 · ACM Symposium on Applied Computing · 301 citations

Scroll for more · 6 remaining

Similar papers

Applying greedy genetic algorithm on 0/1 multiple knapsack problemVinod Jain, Jay Shankar Prasad2018 · International Journal of Advanced Technology and Engineering Exploration · 0 citations In Library

Genetic Algorithm for the 0/1 Multidimensional Knapsack ProblemShalin S Shah2019 · arXiv.org · 3 citations In Library

Solving Multidimensional Knapsack Problem with Bayesian Multiploid Genetic AlgorithmEmrullah Gazioğlu2022 · Journal of Soft Computing and Artificial Intelligence In Library

Clustered genetic algorithm to solve multidimensional knapsack problemI. Gupta, Abha Choubey, Siddhartha Choubey2017 · International Conference on Computing Communication and Networking Technologies · 3 citations In Library

Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack ProblemHongbo Li, Jitao Xu, Minghao Yin2022 · Applied Soft Computing · 6 citations In Library

Comparing Various Genetic Algorithm Approaches for Multiple-choice Multi-dimensional Knapsack Problem (mm-KP)Admi Syarif, Dian Anggraini, K. Muludi et al.2020 · International Journal of Intelligent Engineering and Systems · 11 citations In Library

Two-step optimization algorithm operated by heuristic and machine learning methodsAbdellah Rezoug, Mohamed Bader–El–Den, Dalila Boughaci2024 · Discrete Mathematics Algorithms and Applications · 2 citations In Library

Iteration split with Firefly Algorithm and Genetic Algorithm to Solve Multidimensional Knapsack ProblemsRavneil Nand, Priynka Sharma2019 · 2019 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE) · 5 citations In Library

An improved sexual genetic algorithm for solving 0/1 multidimensional knapsack problemSoukaina Laabadi, M. Naimi, H. E. Amri et al.2019 · Engineering computations · 3 citations In Library

A Modified Binary Pigeon-Inspired Algorithm for Solving the Multi-dimensional Knapsack ProblemAsaju La’aro Bolaji, Friday Zinzendoff Okwonu, Peter Bamidele Shola et al.2020 · Journal of Intelligent Systems · 15 citations In Library

Source of record

Semantic Scholar

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal