operators.rst 6.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200
  1. Apply operators to solution
  2. ==============================
  3. Applying an operator to a solution consists of modifying the current state of the solution in order to obtain a new one. The goal is to find a better solution in the search space.
  4. Operators definition
  5. ~~~~~~~~~~~~~~~~~~~~~~~~~
  6. In the discrete optimisation literature, we can categorise operators into two sections:
  7. - **mutators**: modification of one or more elements of a solution from its current state.
  8. - **crossovers**: Inspired by Darwin's theory of evolution, we are going here from two solutions to generate a so-called offspring solution composed of the fusion of the data of the parent solutions.
  9. Inside **Macop**, operators are also decomposed into these two categories. Inside ``macop.operators.discrete.base``, generic class ``Operator`` enables to manage any kind of operator.
  10. .. code-block:: python
  11. class Operator():
  12. """
  13. Abstract Operator class which enables to update solution applying operator (computation)
  14. """
  15. @abstractmethod
  16. def __init__(self):
  17. pass
  18. @abstractmethod
  19. def apply(self, solution):
  20. """
  21. Apply the current operator transformation
  22. """
  23. pass
  24. def setAlgo(self, algo):
  25. """
  26. Keep into operator reference of the whole algorithm
  27. """
  28. self._algo = algo
  29. Like the evaluator, the operator keeps **track of the algorithm** (using ``setAlgo`` method) to which he will be linked. This will allow better management of the way in which the operator must take into account the state of current data relating to the evolution of research.
  30. ``Mutation`` and ``Crossover`` classes inherite from ``Operator``. An ``apply`` function is required for any new operator.
  31. .. code-block:: python
  32. class Mutation(Operator):
  33. """Abstract Mutation extend from Operator
  34. Attributes:
  35. kind: {KindOperator} -- specify the kind of operator
  36. """
  37. def __init__(self):
  38. self._kind = KindOperator.MUTATOR
  39. def apply(self, solution):
  40. raise NotImplementedError
  41. class Crossover(Operator):
  42. """Abstract crossover extend from Operator
  43. Attributes:
  44. kind: {KindOperator} -- specify the kind of operator
  45. """
  46. def __init__(self):
  47. self._kind = KindOperator.CROSSOVER
  48. def apply(self, solution1, solution2):
  49. raise NotImplementedError
  50. We will now detail these categories of operators and suggest some relative to our problem.
  51. Mutator operator
  52. ~~~~~~~~~~~~~~~~~~~~~
  53. As detailed, the mutation operator consists in having a minimum impact on the current state of our solution. Here is an example of a modification that could be done for our problem.
  54. .. image:: ../_static/documentation/project_knapsack_mutator.png
  55. :width: 800 px
  56. :align: center
  57. In this example we change a bit value randomly and obtain a new solution from our search space.
  58. .. warning::
  59. Applying an operator can conduct to a new but invalid solution from the search space.
  60. The modification applied here is just a bit swapped. Let's define the ``SimpleBinaryMutation`` operator, allows to randomly change a binary value of our current solution.
  61. .. code-block:: python
  62. """
  63. modules imports
  64. """
  65. from macop.operators.discrete.base import Mutation
  66. class SimpleBinaryMutation(Mutation):
  67. def apply(self, solution):
  68. # obtain targeted cell using solution size
  69. size = solution._size
  70. cell = random.randint(0, size - 1)
  71. # copy of solution
  72. copy_solution = solution.clone()
  73. # swicth values
  74. if copy_solution._data[cell]:
  75. copy_solution._data[cell] = 0
  76. else:
  77. copy_solution._data[cell] = 1
  78. # return the new obtained solution
  79. return copy_solution
  80. We can now instanciate our new operator in order to obtain a new solution:
  81. .. code-block:: python
  82. """
  83. BinaryMutator instance
  84. """
  85. mutator = SimpleBinaryMutation()
  86. # using defined BinarySolution
  87. solution = BinarySolution.random(5)
  88. # obtaining new solution using operator
  89. new_solution = mutator.apply(solution)
  90. .. note::
  91. The developed ``SimpleBinaryMutation`` is available into ``macop.operators.discrete.mutators.SimpleBinaryMutation`` in **Macop**.
  92. Crossover operator
  93. ~~~~~~~~~~~~~~~~~~~~~~~
  94. Inspired by Darwin's theory of evolution, crossover starts from two solutions to generate a so-called offspring solution composed of the fusion of the data of the parent solutions.
  95. .. image:: ../_static/documentation/project_knapsack_crossover.png
  96. :width: 800 px
  97. :align: center
  98. In this example we merge two solutions with a specific splitting criterion in order to obtain an offspring.
  99. We will now implement the SimpleCrossover crossover operator, which will merge data from two solutions.
  100. The first half of solution 1 will be saved and added to the second half of solution 2 to generate the new solution (offspring).
  101. .. code-block:: python
  102. """
  103. modules imports
  104. """
  105. from macop.operators.discrete.base import Crossover
  106. class SimpleCrossover(Crossover):
  107. def apply(self, solution1, solution2):
  108. size = solution1._size
  109. # default split index used
  110. splitIndex = int(size / 2)
  111. # copy data of solution 1
  112. firstData = solution1._data.copy()
  113. # copy of solution 2
  114. copy_solution = solution2.clone()
  115. copy_solution._data[splitIndex:] = firstData[splitIndex:]
  116. return copy_solution
  117. We can now use the crossover operator created to generate new solutions. Here is an example of use:
  118. .. code-block:: python
  119. """
  120. SimpleCrossover instance
  121. """
  122. crossover = SimpleCrossover()
  123. # using defined BinarySolution
  124. solution1 = BinarySolution.random(5)
  125. solution2 = BinarySolution.random(5)
  126. # obtaining new solution using crossover
  127. offspring = crossover.apply(solution1, solution2)
  128. .. warning::
  129. The developed ``SimpleCrossover`` is available into ``macop.operators.discrete.crossovers.SimpleCrossover`` in **Macop**.
  130. However, the choice of halves of the merged data is made randomly.
  131. Next part introduce the ``policy`` feature of **Macop** which enables to choose the next operator to apply during the search process based on specific criterion.