problem.rst

Problem instance

In this tutorial, we introduce the way of using Macop and running your algorithm quickly using the well known knapsack problem.

Problem definition

The knapsack problem is a problem in combinatorial optimisation: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

The image below provides an illustration of the problem:

In this problem, we try to optimise the value associated with the objects we wish to put in our backpack while respecting the capacity of the bag (weight constraint).

Warning

It is a combinatorial and therefore discrete problem. Macop decomposes its package into two parts, which is related to discrete optimisation on the one hand, and continuous optimisation on the other hand. This will be detailed later.

Problem implementation

During the whole tutorial, the example used is based on the previous illustration with:

Hence, we now define our problem in Python:

• worth value of each objects
• weight associated to each of these objects

"""
Problem instance definition
"""

elements_score = [ 4, 2, 10, 1, 2 ] # worth of each object
elements_weight = [ 12, 1, 4, 1, 2 ] # weight of each object

Once we have defined the instance of our problem, we will need to define the representation of a solution to that problem.

Let's define the SimpleBinaryCrossover operator, allows to randomly change a binary value of our current solution.