problem.rst 1.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
  1. Problem instance
  2. ===================
  3. In this tutorial, we introduce the way of using **Macop** and running your algorithm quickly using the well known `knapsack` problem.
  4. Problem definition
  5. ~~~~~~~~~~~~~~~~~~~~~~
  6. 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.
  7. The image below provides an illustration of the problem:
  8. .. image:: ../_static/documentation/knapsack_problem.png
  9. :width: 40 %
  10. :align: center
  11. 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).
  12. .. warning::
  13. 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.
  14. Problem implementation
  15. ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  16. During the whole tutorial, the example used is based on the previous illustration with:
  17. .. image:: ../_static/documentation/project_knapsack_problem.png
  18. :width: 85 %
  19. :align: center
  20. Hence, we now define our problem in Python:
  21. - worth value of each objects
  22. - weight associated to each of these objects
  23. .. code-block:: python
  24. """
  25. Problem instance definition
  26. """
  27. elements_score = [ 4, 2, 10, 1, 2 ] # worth of each object
  28. elements_weight = [ 12, 1, 4, 1, 2 ] # weight of each object
  29. Once we have defined the instance of our problem, we will need to define the representation of a solution to that problem.
  30. Let's define the ``SimpleBinaryCrossover`` operator, allows to randomly change a binary value of our current solution.