Knapsacking

From jecoliwiki
Jump to: navigation, search

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.
Personal tools