The 0/1 Knapsacking problem is a classical problem in optimization that is used often used to illustrate how to handle constraints in Evolutionary Algorithms (EAs) and other metaheuristics.
Problem definition
Given a set of N objects, each object i is characterized by its profit (Pi) and weight (Wi).
The aim is to find the subset of the N objects that maximize the sum of their profits and the sum of their weights does not overcome a pre-specified maximum capacity C.
Resolution
We addressed the solution of this problem using three different alternatives for the constraint handling (according to the Z. michalewicz book on Evolutionary Programs, 1996):
- Using binary representations (direct) and applying penalties to the unfeasible solutions. The penalties are proportional to the degree of unfeasibilty.
- Using binary representations (direct) and implementing a correction algorithm to fix the solution before evaluating it.
- Using permutations; in this case, the solution represents the order by which the objects are considered to be included in the solution.
The implementation of these approaches is given in the test/knapsacking package, that contains the following classes:
- Knapsacking - includes all data and methods for the problem specific functions.
- KnapsackingBinaryEvaluationFunction, KnapsackingCorrectionEvaluation, KnapsackingPermutationEvaluationFunction - evaluation functions using the previously mentioned strategies for constraint handling.
- EAKnapsacking - Configuring and running EAs for the Knapsacking problem.