qap_example.rst 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308
  1. ===============================
  2. Quadratric Assignment Problem
  3. ===============================
  4. This example will deal with the use of the **Macop** package in relation to a quadratic assignment problem (QAP). We will use a known example of this problem to associate a set of facilities (:math:`F`) to a set of locations (:math:`L`).
  5. .. image:: _static//examples/qap/factories_qap.png
  6. :width: 50 %
  7. :align: center
  8. :alt: Example of QAP facilities to locations problem
  9. .. note::
  10. The full code for what will be proposed in this example is available: qapExample.py_.
  11. .. _qapExample.py: https://github.com/jbuisine/macop/blob/master/examples/qapExample.py
  12. QAP problem definition
  13. ======================
  14. The quadratic assignment problem (QAP) was introduced by Koopmans and Beckman in 1957 in the context of locating "indivisible economic activities". The objective of the problem is to assign a set of facilities to a set of locations in such a way as to minimize the total assignment cost. The assignment cost for a pair of facilities is a function of the flow between the facilities and the distance between the locations of the facilities.
  15. Location assignment example
  16. ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  17. Consider a **facility location problem** with **four** facilities (and **four** locations). One possible assignment is shown in the figure below: facility 4 is assigned to location 1, facility 1
  18. is assigned to location 2, facility 3 is assigned to location 3, and facility 2 is assigned to location 3. This assignment can be written as the permutation :math:`p=\{4,1,3,2\}`,
  19. which means that facility 4 is assigned to location 1, facility 1 is assigned to location 2, facility 3 is assigned to location 3, and facility 2 is assigned to location 3.
  20. In the figure, the line between a pair of facilities indicates that there is required flow between the facilities, and the thickness of the line increases with the value of the flow.
  21. .. image:: _static//examples/qap/factories_qap.png
  22. :width: 50 %
  23. :align: center
  24. :alt: Example of QAP facilities to locations problem
  25. To calculate the assignment cost of the permutation, the required flows between facilities and the distances between locations are needed.
  26. .. tabularcolumns:: |p{1cm}|p{1cm}|p{1cm}|p{1cm}|
  27. .. csv-table:: flow of the current facilities
  28. :header: facility `i`, facility `j`, flow( `i`\, `j` )
  29. :widths: 2, 2, 3
  30. 1, 4, 4
  31. 3, 4, 10
  32. 3, 1, 8
  33. 2, 1, 6
  34. .. csv-table:: distances of between locations
  35. :header: location `i`, location `j`, distances( `i`\, `j` )
  36. :widths: 2, 2, 3
  37. 1, 2, 42
  38. 1, 3, 30
  39. 2, 3, 41
  40. 3, 4, 23
  41. Then, the assignment cost of the permutation can be computed as:
  42. :math:`f(1,4)⋅d(1,2)+f(3,4)⋅d(1,3)+f(1,3)⋅d(2,3)+f(3,2)⋅d(3,4)`
  43. with result :math:`4⋅42+10⋅30+8⋅41+6⋅23=934`.
  44. Note that this permutation is not the optimal solution.
  45. Mathematical definition
  46. ~~~~~~~~~~~~~~~~~~~~~~~
  47. **Sets**
  48. - :math:`N=\{1,2,⋯,n\}`
  49. - :math:`S_n=\phi:N→N` is the set of all permutations
  50. **Parameters**
  51. - :math:`F=(f_{ij})` is an :math:`n×n` matrix where :math:`f_{ij}` is the required flow between facilities :math:`i` and :math:`j`
  52. - :math:`D=(d_{ij})` is an :math:`n×n` matrix where :math:`d_{ij}` is the distance between locations :math:`i` and :math:`j`.
  53. **Optimization Problem**
  54. - :math:`min_{ϕ∈S_n}\sum_{i=1}^{n}{\sum_{j=1}^{n}{f_{ij}⋅d_{\phi(i)\phi(j)}}}`
  55. The assignment of facilities to locations is represented by a permutation :math:`\phi`, where :math:`\phi(i)` is the location to which facility :math:`i` is assigned. Each individual product :math:`f_{ij}⋅d_{\phi(i)\phi(j)}` is the cost of assigning facility :math:`i` to location :math:`\phi(i)` and facility :math:`j` to location :math:`\phi(j)`.
  56. QAP Problem instance generation
  57. ===============================
  58. To define our quadratic assignment problem instance, we will use the available mQAP_ multi-objective quadratic problem generator.
  59. Genration of the instance
  60. ~~~~~~~~~~~~~~~~~~~~~~~~~
  61. We will limit ourselves here to a single objective for the purposes of this example. The file **makeQAPuni.cc**, will be used to generate the instance.
  62. .. code:: bash
  63. g++ makeQAPuni.cc -o mQAPGenerator
  64. ./mQAPGenerator -n 100 -k 1 -f 30 -d 80 -s 42 > qap_instance.txt
  65. with the following parameters:
  66. - **-n** positive integer: number of facilities/locations;
  67. - **-k** positive integer: number of objectives;
  68. - **-f** positive integer: maximum flow between facilities;
  69. - **-d** positive integer: maximum distance between locations;
  70. - **-s** positive long: random seed.
  71. The generated qap_instance.txt_ file contains the two matrices :math:`F` and :math:`D` and define our instance problem.
  72. .. _mQAP: https://www.cs.bham.ac.uk/~jdk/mQAP/
  73. .. _qap_instance.txt: https://github.com/jbuisine/macop/blob/master/examples/instances/qap/qap_instance.txt
  74. Load data instance
  75. ~~~~~~~~~~~~~~~~~~
  76. We are now going to load this instance via a Python code which will be useful to us later on:
  77. .. code:: Python
  78. qap_instance_file = 'qap_instance.txt'
  79. n = 100 # the instance size
  80. with open(qap_instance_file, 'r') as f:
  81. file_data = f.readlines()
  82. print(f'Instance information {file_data[0]}')
  83. D_lines = file_data[1:n + 1]
  84. D_data = ''.join(D_lines).replace('\n', '')
  85. F_lines = file_data[n:2 * n + 1]
  86. F_data = ''.join(F_lines).replace('\n', '')
  87. D_matrix = np.fromstring(D_data, dtype=float, sep=' ').reshape(n, n)
  88. print(f'D matrix shape: {D_matrix.shape}')
  89. F_matrix = np.fromstring(F_data, dtype=float, sep=' ').reshape(n, n)
  90. print(f'F matrix shape: {F_matrix.shape}')
  91. .. note::
  92. As we know the size of our instance and the structure of the document, it is quite quick to look for the lines related to the :math:`F` and :math:`D` matrices.
  93. Macop QAP implementation
  94. ========================
  95. Let's see how it is possible with the use of the **Macop** package to implement and deal with this QAP instance problem.
  96. Solution structure definition
  97. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  98. Firstly, we are going to use a type of solution that will allow us to define the structure of our solutions.
  99. The available macop.solutions.discrete.CombinatoryIntegerSolution_ type of solution within the Macop package represents exactly what one would wish for.
  100. I.e. a solution that stores a sequence of integers relative to the size of the problem, the order of which is not sorted.
  101. Let's see an example of its use:
  102. .. code:: python
  103. from macop.solutions.discrete import CombinatoryIntegerSolution
  104. solution = CombinatoryIntegerSolution.random(10)
  105. print(solution)
  106. The resulting solution obtained:
  107. .. code:: bash
  108. Combinatory integer solution [2 9 8 1 7 6 0 4 3 5]
  109. QAP Evaluator
  110. ~~~~~~~~~~~~~
  111. Now that we have the structure of our solutions, and the means to generate them, we will seek to evaluate them.
  112. To do this, we need to create a new evaluator specific to our problem and the relative evaluation function:
  113. - :math:`min_{ϕ∈S_n}\sum_{i=1}^{n}{\sum_{j=1}^{n}{f_{ij}⋅d_{\phi(i)\phi(j)}}}`
  114. So we are going to create a class that will inherit from the abstract class macop.evaluators.base.Evaluator_:
  115. .. code:: python
  116. from macop.evaluators.base import Evaluator
  117. class QAPEvaluator(Evaluator):
  118. """QAP evaluator class which enables to compute QAP solution using specific `_data`
  119. - stores into its `_data` dictionary attritute required measures when computing a QAP solution
  120. - `_data['F']` matrix of size n x n with flows data between facilities (stored as numpy array)
  121. - `_data['D']` matrix of size n x n with distances data between locations (stored as numpy array)
  122. - `compute` method enables to compute and associate a score to a given QAP solution
  123. """
  124. def compute(self, solution):
  125. """Apply the computation of fitness from solution
  126. Args:
  127. solution: {Solution} -- QAP solution instance
  128. Returns:
  129. {float} -- fitness score of solution
  130. """
  131. fitness = 0
  132. for index_i, val_i in enumerate(solution.getdata = )):
  133. for index_j, val_j in enumerate(solution.getdata = )):
  134. fitness += self._data['F'][index_i, index_j] * self._data['D'][val_i, val_j]
  135. return fitness
  136. The cost function for the quadratic problem is now well defined.
  137. .. tip::
  138. The class proposed here, is available in the Macop package macop.evaluators.discrete.mono.QAPEvaluator_.
  139. Running algorithm
  140. ~~~~~~~~~~~~~~~~~
  141. 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 QAP instance.
  142. Here we will use local search algorithms already implemented in **Macop**.
  143. 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.
  144. .. code:: python
  145. # main imports
  146. import numpy as np
  147. # module imports
  148. from macop.solutions.discrete import CombinatoryIntegerSolution
  149. from macop.evaluators.discrete.mono import QAPEvaluator
  150. from macop.operators.discrete.mutators import SimpleMutation
  151. from macop.policies.classicals import RandomPolicy
  152. from macop.algorithms.mono import IteratedLocalSearch as ILS
  153. from macop.algorithms.mono import HillClimberFirstImprovment
  154. # usefull instance data
  155. n = 100
  156. qap_instance_file = 'qap_instance.txt'
  157. # default validator (check the consistency of our data, i.e. only unique element)
  158. def validator(solution):
  159. if len(list(solution.getdata = ))) > len(set(list(solution.getdata = )))):
  160. print("not valid")
  161. return False
  162. return True
  163. # define init random solution
  164. def init():
  165. return CombinatoryIntegerSolution.random(n, validator)
  166. # load qap instance
  167. with open(qap_instance_file, 'r') as f:
  168. file_data = f.readlines()
  169. print(f'Instance information {file_data[0]}')
  170. D_lines = file_data[1:n + 1]
  171. D_data = ''.join(D_lines).replace('\n', '')
  172. F_lines = file_data[n:2 * n + 1]
  173. F_data = ''.join(F_lines).replace('\n', '')
  174. D_matrix = np.fromstring(D_data, dtype=float, sep=' ').reshape(n, n)
  175. print(f'D matrix shape: {D_matrix.shape}')
  176. F_matrix = np.fromstring(F_data, dtype=float, sep=' ').reshape(n, n)
  177. print(f'F matrix shape: {F_matrix.shape}')
  178. # only one operator here
  179. operators = [SimpleMutation()]
  180. # random policy even if list of solution has only one element
  181. policy = RandomPolicy(operators)
  182. # use of loaded data from QAP instance
  183. evaluator = QAPEvaluator(data={'F': F_matrix, 'D': D_matrix})
  184. # passing global evaluation param from ILS
  185. hcfi = HillClimberFirstImprovment(init, evaluator, operators, policy, validator, maximise=False, verbose=True)
  186. algo = ILS(init, evaluator, operators, policy, validator, localSearch=hcfi, maximise=False, verbose=True)
  187. # run the algorithm
  188. bestSol = algo.run(10000, ls_evaluations=100)
  189. print('Solution for QAP instance score is {}'.format(evaluator.compute(bestSol)))
  190. QAP problem solving is now possible with **Macop**. As a reminder, the complete code is available in the qapExample.py_ file.
  191. .. _qapExample.py: https://github.com/jbuisine/macop/blob/master/examples/qapExample.py
  192. .. _documentation: https://jbuisine.github.io/macop/_build/html/documentations
  193. .. _macop.solutions.discrete.CombinatoryIntegerSolution: macop/macop.solutions.discrete.html#macop.solutions.discrete.CombinatoryIntegerSolution
  194. .. _macop.evaluators.base.Evaluator: macop/macop.evaluators.base.html#macop.evaluators.base.Evaluator
  195. .. _macop.evaluators.discrete.mono.QAPEvaluator: macop/macop.evaluators.discrete.mono.html#macop.evaluators.discrete.mono.QAPEvaluator