implementation.rst 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146
  1. Macop UBQP implementation
  2. =========================
  3. Let's see how it is possible with the use of the **Macop** package to implement and deal with this UBQP instance problem.
  4. Solution structure definition
  5. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  6. Firstly, we are going to use a type of solution that will allow us to define the structure of our solutions.
  7. The available ``macop.solutions.discrete.BinarySolution`` type of solution within the Macop package represents exactly what one would wish for.
  8. Let's see an example of its use:
  9. .. code:: python
  10. from macop.solutions.discrete import BinarySolution
  11. solution = BinarySolution.random(10)
  12. print(solution)
  13. The resulting solution obtained:
  14. .. code:: bash
  15. Binary solution [1 0 1 1 1 0 0 1 1 0]
  16. UBQP Evaluator
  17. ~~~~~~~~~~~~~~
  18. Now that we have the structure of our solutions, and the means to generate them, we will seek to evaluate them.
  19. To do this, we need to create a new evaluator specific to our problem and the relative evaluation function we need to maximise:
  20. - :math:`f(x)=x′Qx=\sum_{i=1}^{n}{\sum_{j=1}^{n}{q_{ij}⋅x_i⋅x_j}}`
  21. So we are going to create a class that will inherit from the abstract class ``macop.evalutarors.base.Evaluator``:
  22. .. code:: python
  23. from macop.evaluators.base import Evaluator
  24. class UBQPEvaluator(Evaluator):
  25. """UBQP evaluator class which enables to compute UBQP solution using specific `_data`
  26. - stores into its `_data` dictionary attritute required measures when computing a UBQP solution
  27. - `_data['Q']` matrix of size n x n with real values data (stored as numpy array)
  28. - `compute` method enables to compute and associate a score to a given UBQP solution
  29. """
  30. def compute(self, solution):
  31. """Apply the computation of fitness from solution
  32. Args:
  33. solution: {Solution} -- UBQP solution instance
  34. Returns:
  35. {float} -- fitness score of solution
  36. """
  37. fitness = 0
  38. for index_i, val_i in enumerate(solution.getData()):
  39. for index_j, val_j in enumerate(solution.getData()):
  40. fitness += self._data['Q'][index_i, index_j] * val_i * val_j
  41. return fitness
  42. The cost function for the Unconstrained binary quadratic problem is now well defined.
  43. .. tip::
  44. The class proposed here, is available in the Macop package ``macop.evaluators.discrete.mono.UBQPEvaluator``.
  45. Running algorithm
  46. ~~~~~~~~~~~~~~~~~
  47. Now that the necessary tools are available, we will be able to deal with our problem and look for solutions in the search space of our UBQP instance.
  48. Here we will use local search algorithms already implemented in **Macop**.
  49. If you are uncomfortable with some of the elements in the code that will follow, you can refer to the more complete **Macop** documentation_ that focuses more on the concepts and tools of the package.
  50. .. code:: python
  51. # main imports
  52. import numpy as np
  53. # module imports
  54. from macop.solutions.discrete import BinarySolution
  55. from macop.evaluators.discrete.mono import UBQPEvaluator
  56. from macop.operators.discrete.mutators import SimpleMutation, SimpleBinaryMutation
  57. from macop.policies.classicals import RandomPolicy
  58. from macop.algorithms.mono import IteratedLocalSearch as ILS
  59. from macop.algorithms.mono import HillClimberFirstImprovment
  60. # usefull instance data
  61. n = 100
  62. qap_instance_file = 'qap_instance.txt'
  63. # default validator
  64. def validator(solution):
  65. return True
  66. # define init random solution
  67. def init():
  68. return BinarySolution.random(n, validator)
  69. # load UBQP instance
  70. with open(ubqp_instance_file, 'r') as f:
  71. lines = f.readlines()
  72. # get all string floating point values of matrix
  73. Q_data = ''.join([ line.replace('\n', '') for line in lines[8:] ])
  74. # load the concatenate obtained string
  75. Q_matrix = np.fromstring(Q_data, dtype=float, sep=' ').reshape(n, n)
  76. print(f'Q_matrix shape: {Q_matrix.shape}')
  77. # only one operator here
  78. operators = [SimpleMutation(), SimpleBinaryMutation()]
  79. # random policy
  80. policy = RandomPolicy(operators)
  81. # use of loaded data from UBQP instance
  82. evaluator = UBQPEvaluator(data={'Q': Q_matrix})
  83. # passing global evaluation param from ILS
  84. hcfi = HillClimberFirstImprovment(init, evaluator, operators, policy, validator, maximise=True, verbose=True)
  85. algo = ILS(init, evaluator, operators, policy, validator, localSearch=hcfi, maximise=True, verbose=True)
  86. # run the algorithm
  87. bestSol = algo.run(10000, ls_evaluations=100)
  88. print('Solution for UBQP instance score is {}'.format(evaluator.compute(bestSol)))
  89. UBQP problem solving is now possible with **Macop**. As a reminder, the complete code is available in the ubqpExample.py_ file.
  90. .. _ubqpExample.py: https://github.com/jbuisine/macop/blob/master/examples/ubqpExample.py
  91. .. _documentation: https://jbuisine.github.io/macop/_build/html/documentations