solutions.rst 4.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
  1. Solutions
  2. =============
  3. Representing a solution to a specific problem is very important in an optimisation process. In this example, we will always use the **knapsack problem** as a basis.
  4. In a first step, the management of the solutions by the macop package will be presented. Then a specific implementation for the current problem will be detailed.
  5. Generic Solution
  6. ~~~~~~~~~~~~~~~~~~~~~~~~~
  7. Inside ``macop.solutions.base`` module of `Macop`, the ``Solution`` class is available. It's an abstract solution class structure which:
  8. - stores the solution data representation into its ``data`` attribute
  9. - get ``size`` (shape) of specific data representation
  10. - stores the ``score`` of the solution once a solution is evaluated
  11. Some specific methods are available:
  12. .. code-block:: python
  13. class Solution():
  14. def __init__(self, data, size):
  15. """
  16. Abstract solution class constructor
  17. """
  18. ...
  19. def isValid(self, validator):
  20. """
  21. Use of custom function which checks if a solution is valid or not
  22. """
  23. ...
  24. def evaluate(self, evaluator):
  25. """
  26. Evaluate solution using specific `evaluator`
  27. """
  28. ...
  29. def fitness(self):
  30. """
  31. Returns fitness score
  32. """
  33. ...
  34. @staticmethod
  35. def random(size, validator=None):
  36. """
  37. Initialize solution using random data with validator or not
  38. """
  39. ...
  40. def clone(self):
  41. """
  42. Clone the current solution and its data, but without keeping evaluated `_score`
  43. """
  44. ...
  45. From these basic methods, it is possible to manage a representation of a solution to our problem.
  46. Allowing to initialize it randomly or not (using constructor or ``random`` method), to evaluate it (``evaluate`` method) and to check some constraints of validation of the solution (``isValid`` method).
  47. .. note::
  48. Only one of these methods needs specification if we create our own type of solution. This is the ``random`` method, which depends on the need of the problem.
  49. We will now see how to define a type of solution specific to our problem.
  50. Solution representation for knapsack
  51. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  52. We will now use the abstract ``Solution`` type available in the ``macop.solutions.base`` module in order to define our own solution.
  53. First of all, let's look at the representation of our knapsack problem. **How to represent the solution?**
  54. Knapsack solution
  55. ************************
  56. A valid solution can be shown below where the sum of the object weights is 15 and the sum of the selected objects values is 8 (its fitness):
  57. .. image:: ../_static/documentation/project_knapsack_solution.png
  58. :width: 800 px
  59. :align: center
  60. Its representation can be translate as a **binary array** with value:
  61. .. code-block::
  62. [1, 1, 0, 0, 1]
  63. where selected objects have **1** as value otherwise **0**.
  64. Binary Solution
  65. **********************
  66. We will now define our own type of solution by inheriting from ``macop.solutions.base.Solution``, which we will call ``BinarySolution``.
  67. First we will define our new class as inheriting functionality from ``Solution`` (such as child class).
  68. We will also have to implement the ``random`` method to create a new random solution.
  69. .. code-block:: python
  70. """
  71. modules imports
  72. """
  73. from macop.solutions.base import Solution
  74. import numpy as np
  75. class BinarySolution(Solution):
  76. @staticmethod
  77. def random(size, validator=None):
  78. # create binary array of specific size using numpy random module
  79. data = np.random.randint(2, size=size)
  80. # initialize new solution using constructor
  81. solution = BinarySolution(data, size)
  82. # check if validator is set
  83. if not validator:
  84. return solution
  85. # try to generate solution until solution validity (if validator is provided)
  86. while not validator(solution):
  87. data = np.random.randint(2, size=size)
  88. solution = BinarySolution(data, size)
  89. return solution
  90. .. note::
  91. The current developed ``BinarySolution`` is available into ``macop.solutions.discrete.BinarySolution`` in **Macop**.
  92. Using this new Solution representation, we can now generate solution randomly:
  93. .. code-block:: python
  94. solution = BinarySolution.random(5)
  95. In the next part, we will see how to verify that a solution meets certain modeling constraints of the problem.