A genetic algorithm implementation for the multidimensional knapsack problem. The multi-constraint (or multidimensional) knapsack problem is a generalization of the 0/1 knapsack problem. The multi-constraint knapsack problem has m constraints and one objective function to be maximized while all the m constraints are satisfied.
The implementation is similar to the one described in [Chu98], but its significantly different. It uses Lagrangian multipliers as constraint weights and compared to the paper, it finds close to optimum solutions much faster. (Convergence can be controlled using the parameters).
Please see this paper for a detailed description of the algorithm.
@article{shah2019gknap,
title={GKNAP: A Java and C++ package for solving the multidimensional knapsack problem},
author={Shah, Shalin},
journal={Journal of Open Source Software},
volume={4},
number={42},
pages={1756},
year={2019}
}
Usage The usage of this code base is to just compile the code and run it on the command line. The code will output the solution found, the value of the objective function and the chosen items for the knapsack. The code requires a weing formatted file or an orlib formatted file. The weing formatted files are available here. The orlib formatted files are available here (used by P.C.Chu and J.E.Beasley). The orlib formatted files are available here which are named mknapcb1.txt, mknapcb2.txt and so on. Please note that these files contain multiple instances, so to run the algorithm, please use any one of the instances. The distributions of the files are quite different between orlib and weing. If the algorithm is stuck, please increase Constants.DIFF_TOLERANCE on line 31 of GeneticAlgorithm.java. The format of all files is described here. Java implementation I tested the code using JDK 1.8, but any JDK should work fine. If the code does not compile, please open an issue. Compile the Java code and then run GeneticAlgorithm. javac *.java java GeneticAlgorithm filename format (The file name contains the instance in weing or orlib format) (The format is either weing or orlib) Example: java GeneticAlgorithm data.DAT weing C++ implementation The code was tested on a Mac with gcc version 8, downloaded using homebrew. If the code does not compile, please open an issue. Compile the C++ code and then run the executable. g++ cmultiknapsack.cpp ./a.out filename format (The file name contains the instance in weing or orlib format) (The format is either weing or orlib) Example: ./a.out data.DAT weing (Please remove all comments and other extraneous text from data.DAT) (See the tests directory for testcpp.sh and testjava.sh for an example run) Dependencies The code has no other dependencies. A JDK or a gcc compiler is all that is required. Using the code as an API If you want to use the code as an API call from your own code: Java: In GeneticAlgorithm.java, please see the main method. C++: In the C++ code, please see the main method.
The benchmark instances are available here. They have the following format:
//This is the WEING1.DAT data file plus some comments, that are NOT part of the problem instance. 2 28 // 2 knapsacks, 28 objects 1898 440 22507 270 14148 3100 4650 30800 615 4975 1160 4225 510 11880 479 440 490 330 110 560 24355 2885 11748 4550 750 3720 1950 10500 // 28 weights 600 600 // 2 knapsack capacities 45 0 85 150 65 95 30 0 170 0 40 25 20 0 0 25 0 0 25 0 165 0 85 0 0 0 0 100 // #1 constr. 30 20 125 5 80 25 35 73 12 15 15 40 5 10 10 12 10 9 0 20 60 40 50 36 49 40 19 150 // #2 constr. 141278 // optimum value
The comments beginning with "//" are only for the purpose of explaining the format. Please remove all comments before running the algorithm.
The algorithm was run on a few benchmark instances:
| Instance | Optimum | Found - Best | Found - Worst | Time (s) |
| Weing1 | 141278 | 141278 | 141278 | 0 |
| Weing2 | 130883 | 130883 | 130883 | 1 |
| Weing3 | 95677 | 95677 | 95677 | 1 |
| Weing4 | 119337 | 119337 | 119337 | 0 |
| Weing5 | 98796 | 98796 | 98796 | 0 |
| Weing6 | 130623 | 130623 | 130623 | 0 |
| Weing7 | 1095445 | 1095445 | 1095445 | 2 |
| Weing8 | 624319 | 624319 | 624319 | 4 |
| Sento1 | 7772 | 7772 | 7772 | 1 |
| Sento2 | 8722 | 8722 | 8722 | 0 |
| Weish01 | 4554 | 4554 | 4554 | 0 |
| Weish02 | 4536 | 4536 | 4536 | 0 |
| Weish03 | 4115 | 4115 | 4115 | 0 |
| Weish04 | 4561 | 4561 | 4561 | 0 |
| Weish05 | 4514 | 4514 | 4514 | 0 |
| Weish06 | 5557 | 5557 | 5557 | 0 |
| Weish07 | 5567 | 5567 | 5567 | 0 |
| Weish08 | 5605 | 5605 | 5605 | 0 |
| Weish09 | 5246 | 5246 | 5246 | 0 |
| Weish10 | 6339 | 6339 | 6339 | 0 |
| Weish11 | 5643 | 5643 | 5643 | 0 |
| Weish12 | 6339 | 6339 | 6339 | 0 |
| Weish13 | 6159 | 6159 | 6159 | 0 |
| Weish14 | 6954 | 6954 | 6954 | 0 |
| Weish15 | 7486 | 7486 | 7486 | 1 |
| Weish16 | 7289 | 7289 | 7289 | 0 |
| Weish17 | 8633 | 8633 | 8633 | 0 |
| Weish18 | 9580 | 9580 | 9580 | 0 |
| Weish19 | 7698 | 7698 | 7698 | 0 |
| Weish20 | 9450 | 9450 | 9450 | 0 |
| Weish21 | 9074 | 9074 | 9074 | 1 |
| Weish22 | 8947 | 8947 | 8947 | 1 |
| Weish23 | 8344 | 8344 | 8344 | 0 |
| Weish24 | 10220 | 10220 | 10220 | 2 |
| Weish25 | 9939 | 9939 | 9939 | 1 |
| Weish26 | 9584 | 9584 | 9584 | 0 |
| Weish27 | 9819 | 9819 | 9819 | 0 |
| Weish28 | 9492 | 9492 | 9492 | 0 |
| Weish29 | 9410 | 9410 | 9410 | 0 |
| Weish30 | 11191 | 11191 | 11191 | 0 |
| PB1 | 3090 | 3090 | 3076 | 9 |
| PB2 | 3186 | 3186 | 3186 | 2 |
| PB4 | 95168 | 95168 | 95168 | 1 |
| PB5 | 2139 | 2139 | 2139 | 2 |
| PB6 | 776 | 776 | 776 | 0 |
| PB7 | 1035 | 1035 | 1035 | 0 |
| HP1 | 3418 | 3404 | 3404 | 0 |
| HP2 | 3186 | 3186 | 3186 | 4 |
[Ahuja00] “A greedy genetic algorithm for the quadratic assignment problem”, R. Ahuja, J. Orlin, A. Tiwari, Computers and Operations Research, vol. 27, issue 10 (Sept. 2000), 917--934, ACM (2000)
[Angeline95] “Adaptive and self-adaptive evolutionary computations”, P. Angeline, Computational Intelligence: A Dynamic Systems Perspective, IEEE press, 152—163 (1995)
[Coello02] “Theoretical and Numerical Constraint Handling Techniques used with Evolutionary Algorithms: A Survey of the State of the Art”, C. Coello, Computer Methods in Applied Mechanics and Engineering, 191 (11--12), 1245-1287, January 2002 (2002)
[Chu98] “A Genetic Algorithm for the Multidimensional Knapsack Problem”, PC Chu, JE Beasley, Journal of Heuristics, vol. 4, 6 —86 (1998)
[DeJong93] “On the state of evolutionary computation” K. De Jong and W. Spears, Proceedings of the Fifth ICGA, 618--623. Kaufmann, San Mateo, CA. (1993)
[Eshelman91] “The CHC adaptive search algorithm: How to have safe search when engaging in non-traditional genetic recombination”, L. Eshelman, Foundations of Genetic Algorithms, Morgan Kaufmann (1991)
[Goldberg89] “Genetic Algorithm in Search, Optimization and Machine Learning”, D. E. Goldberg, Addison Wesley publishing company, Massachusetts (1989)
[Gordon94] “A note on the performance of genetic algorithms on zero-one knapsack problems”, V. Gordon, A.P. Böhm, D. Whitley, Proceedings of the 1994 ACM symposium on Applied computing, 194--195 (1994)
[Greene00] “Partitioning sets with genetic algorithms”, W. Greene, Proceedings of the Thirteenth International Florida Artificial Intelligence Research Society Conference, 2000, AAAI press, 102—105 (2000)
[Grefen85] “Genetic algorithms for the traveling salesman problem”, J. Grefenstette, R. Gopal, B. Rosimaita, and D. V. Gucht, Proceedings of an International Conference on Genetic Algorithms and their Applications, pp. 160--168, Carnegie Mellon publishers (1985)
[Hill99] “A Monte-Carlo study of genetic algorithm initial population generation methods”, R. Hill, Proceedings of the 31st conference on winter simulation: Simulation---a bridge to the future - Volume 1, 1999, 543--547 (1999)
[Hinterding97] “Adaptation in Evolutionary Computation: A Survey”, R. Hinterding, Z. Michalewicz, A.E. Eiben, In Proc of the 4th IEEE Conf. on Evolutionary Computation (pp. 65-69) (1997)
[Holland75] “Adaptation in natural and artificial systems”, MIT press, Cambridge, Massachusetts (1975)
[Julstrom05] “Greedy, Genetic and Greedy Genetic Algorithms for the Quadratic Knapsack Problem”, B. Julstrom, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2005) vol. 1, 607—614 (2005)
[Julstrom95] “Very greedy crossover in a genetic algorithm for the traveling salesman problem”, B. Julstrom, Proceedings of the 1995 ACM Symposium on Applied Computing, 324--328 (1995)
[Khuri94] “The Zero/One Multiple Knapsack Problem and Genetic Algorithms”, S. Khuri, T. Back and J. Heitkoetter, Proceedings of the 1994 ACM Symposium on Applied Computing, 188---193, March 1994 (1994)
[Kirkpatrick83] “Optimization by simulated annealing”, S. Kirkpatrick, Science, Number 4598, 13 May 1983, volume 220, 4598, 671--680 (1983)
[Kotta98] “A Hybrid Genetic Algorithm for the 0-1 Multiple Knapsack Problem”, C. Kotta and J.M. Troya, Artificial Neural Networks and Genetic Algorithms 3, 251--255, Springer-Verlag 1998 (1998)
[Martello90] “Knapsack Problems Algorithms and Computer Implementations”, S. Martello and P. Toth, John Wiley and Sons (1990)
[Melikhov96] “Some new features in genetic solution of the traveling salesman problem”, K. Melikhov, Proceedings of ACEDC '96 PEDC, University of Plymouth, UK (1996)
[Miller93] “An Evaluation of Local Improvement Operators for Genetic Algorithms”, J. Miller, W. Potter, R. Gandham, C. Lapena, IEEE Transactions on Systems, Man and Cybernetics, vol. 23, number 5, 1340—1351 (1993)
[Pisinger05] “Where are the hard knapsack problems?”, D. Pisinger, Computers and Operations Research, vol. 32, No. 9 (September 2005), 2271—2284 (2005)
[Raidl98] “An Improved Genetic Algorithm for the Multiconstrained 0-1 Knapsack Problem”, G.R. Raidl, Evolutionary Computation Proceedings, 1998. IEEE World Congress on Computational Intelligence, 207—211, May 1998 (1998)
[Simes01] “An Evolutionary Approach to the Zero/One Knapsack Problem: Testing Ideas from Biology”, A. Simes, E. Costa, 5th International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA 2001), Prague, Czech Republic (2001)
[Smith96] “Self adaptation of mutation Rates in a Steady State Genetic Algorithm”, J. Smith, T. Fogarty, Proceedings of IEEE International Conference Evolutionary Computing ICEC ’96 (1996)
[Spears95] “Adapting Crossover in Evolutionary Algorithms”, W. Spears, Proceedings of 4th Annual Conf. on Evolutionary Computing, 367--384, (1995)
[Syswerda89] “Uniform crossover in genetic algorithms”, Proceedings of the 3rd international conference on genetic algorithms, Morgan Kaufman (1989)
[Whitley93] “Serial and Parallel Genetic Algorithms as Function Optimizers”, V. Gordon, L. Whitley, Proceedings of the 5th International Conference on Genetic Algorithms, 177--183, 1993 (1993)