documentations.rst 46 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120
  1. ===================
  2. A tour of Macop
  3. ===================
  4. .. image:: _static/logo_macop.png
  5. :width: 300 px
  6. :align: center
  7. This documentation will allow a user who wishes to use the **Macop** optimisation package to understand both how it works and offers examples of how to implement specific needs.
  8. It will gradually take up the major ideas developed within **Macop** to allow for quick development. You can navigate directly via the menu available below to access a specific part of the documentation.
  9. Introduction
  10. ================
  11. `Macop` is a python package for solving discrete optimisation problems in nature. Continuous optimisation is also applicable but not yet developed. The objective is to allow a user to exploit the basic structure proposed by this package to solve a problem specific to him. The interest is that he can quickly abstract himself from the complications related to the way of evaluating, comparing, saving the progress of the search for good solutions but rather concentrate if necessary on his own algorithm. Indeed, `Macop` offers the following main and basic features:
  12. - **solutions:** representation of the solution;
  13. - **validator:** such as constraint programming, a `validator` is a function which is used to validate or not a solution data state;
  14. - **evaluator:** stores problem instance data and implements a `compute` method in order to evaluate a solution;
  15. - **operators:** mutators, crossovers operators to update and obtain new solution;
  16. - **policies:** the way you choose the available operators (might be using reinforcement learning);
  17. - **algorithms:** generic and implemented optimisation research algorithms;
  18. - **callbacks:** callbacks to automatically keep track of the search space advancement and restart from previous state if nedded.
  19. .. image:: _static/documentation/macop_behaviour.png
  20. :width: 50 %
  21. :align: center
  22. Based on all of these generic and/or implemented functionalities, the user will be able to quickly develop a solution to his problem while retaining the possibility of remaining in control of his development by overloading existing functionalities if necessary.
  23. Problem instance
  24. ===================
  25. In this tutorial, we introduce the way of using **Macop** and running your algorithm quickly using the well known `knapsack` problem.
  26. Problem definition
  27. ~~~~~~~~~~~~~~~~~~~~~~
  28. 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.
  29. The image below provides an illustration of the problem:
  30. .. image:: _static/documentation/knapsack_problem.png
  31. :width: 40 %
  32. :align: center
  33. 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).
  34. .. warning::
  35. 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.
  36. Problem implementation
  37. ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  38. During the whole tutorial, the example used is based on the previous illustration with:
  39. .. image:: _static/documentation/project_knapsack_problem.png
  40. :width: 85 %
  41. :align: center
  42. Hence, we now define our problem in Python:
  43. - worth value of each objects
  44. - weight associated to each of these objects
  45. .. code-block:: python
  46. """
  47. Problem instance definition
  48. """
  49. elements_score = [ 4, 2, 10, 1, 2 ] # worth of each object
  50. elements_weight = [ 12, 1, 4, 1, 2 ] # weight of each object
  51. Once we have defined the instance of our problem, we will need to define the representation of a solution to that problem.
  52. Let's define the ``SimpleBinaryCrossover`` operator, allows to randomly change a binary value of our current solution.
  53. Solutions
  54. =============
  55. 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.
  56. 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.
  57. Generic Solution
  58. ~~~~~~~~~~~~~~~~~~~~~~~~~
  59. Inside macop.solutions.base_ module of `Macop`, the ``Solution`` class is available. It's an abstract solution class structure which:
  60. - stores the solution data representation into its ``data`` attribute
  61. - get ``size`` (shape) of specific data representation
  62. - stores the ``score`` of the solution once a solution is evaluated
  63. Some specific methods are available:
  64. .. caution::
  65. An important thing here are the ``fitness``, ``size`` and ``data`` functions brought as an editable attribute by the ``@property`` and ``@XXXXX.setter`` decorators. The idea is to allow the user to modify these functions in order to change the expected result of the algorithm regardless of the data to be returned/modified.
  66. From these basic methods, it is possible to manage a representation of a solution to our problem.
  67. Allowing to initialise 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).
  68. .. note::
  69. 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.
  70. We will now see how to define a type of solution specific to our problem.
  71. Solution representation for knapsack
  72. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  73. We will now use the abstract ``Solution`` type available in the macop.solutions.base_ module in order to define our own solution.
  74. First of all, let's look at the representation of our knapsack problem. **How to represent the solution?**
  75. Knapsack solution
  76. ************************
  77. 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):
  78. .. image:: _static/documentation/project_knapsack_solution.png
  79. :width: 85 %
  80. :align: center
  81. Its representation can be translate as a **binary array** with value:
  82. .. code-block::
  83. [1, 1, 0, 0, 1]
  84. where selected objects have **1** as value otherwise **0**.
  85. Binary Solution
  86. **********************
  87. We will now define our own type of solution by inheriting from macop.solutions.base.Solution_, which we will call ``BinarySolution``.
  88. First we will define our new class as inheriting functionality from ``Solution`` (such as child class).
  89. We will also have to implement the ``random`` method to create a new random solution.
  90. .. code-block:: python
  91. """
  92. modules imports
  93. """
  94. from macop.solutions.base import Solution
  95. import numpy as np
  96. class BinarySolution(Solution):
  97. @staticmethod
  98. def random(size, validator=None):
  99. # create binary array of specific size using numpy random module
  100. data = np.random.randint(2, size=size)
  101. # initialise new solution using constructor
  102. solution = BinarySolution(data, size)
  103. # check if validator is set
  104. if not validator:
  105. return solution
  106. # try to generate solution until solution validity (if validator is provided)
  107. while not validator(solution):
  108. data = np.random.randint(2, size=size)
  109. solution = BinarySolution(data, size)
  110. return solution
  111. .. note::
  112. The current developed ``BinarySolution`` is available into macop.solutions.discrete.BinarySolution_ in **Macop**.
  113. Using this new Solution representation, we can now generate solution randomly:
  114. .. code-block:: python
  115. solution = BinarySolution.random(5)
  116. In the next part, we will see how to verify that a solution meets certain modeling constraints of the problem.
  117. Validate a solution
  118. ======================
  119. When an optimisation problem requires respecting certain constraints, Macop allows you to quickly verify that a solution is valid.
  120. It is based on a defined function taking a solution as input and returning the validity criterion (true or false).
  121. Validator definition
  122. ~~~~~~~~~~~~~~~~~~~~~~~~~
  123. An invalid solution can be shown below where the sum of the object weights is greater than 15:
  124. .. image:: _static/documentation/project_knapsack_invalid.png
  125. :width: 85 %
  126. :align: center
  127. In fact, **[1, 0, 1, 0, 0]** is an invalid solution as we have a weight of **16** which violates the knapsack capacity constraint.
  128. To avoid taking into account invalid solutions, we can define our function which will validate or not a solution based on our problem instance:
  129. .. code-block:: python
  130. """
  131. Problem instance definition
  132. """
  133. elements_score = [ 4, 2, 10, 1, 2 ] # worth of each object
  134. elements_weight = [ 12, 1, 4, 1, 2 ] # weight of each object
  135. """
  136. Validator function definition
  137. """
  138. def validator(solution):
  139. weight_sum = 0
  140. for i, w in enumerate(elements_weight):
  141. # add weight if current object is set to 1
  142. weight_sum += w * solution.data[i]
  143. # validation condition
  144. return weight_sum <= 15
  145. Use of validator
  146. ~~~~~~~~~~~~~~~~~~~~~
  147. We can now generate solutions randomly by passing our validation function as a parameter:
  148. .. code-block:: python
  149. """
  150. Problem instance definition
  151. """
  152. ...
  153. """
  154. Validator function definition
  155. """
  156. ...
  157. # ensure valid solution
  158. solution = BinarySolution.random(5, validator)
  159. .. caution::
  160. If the search space for valid solutions is very small compared to the overall search space, this can involve a considerable time for validating the solution and therefore obtaining a solution.
  161. The validation of a solution is therefore now possible. In the next part we will focus on the evaluation of a solution.
  162. Use of evaluators
  163. ====================
  164. Now that it is possible to generate a solution randomly or not. It is important to know the value associated with this solution. We will then speak of evaluation of the solution. With the score associated with it, the `fitness`.
  165. Generic evaluator
  166. ~~~~~~~~~~~~~~~~~~~~~~
  167. As for the management of solutions, a generic evaluator class macop.evaluators.base.Evaluator_ is developed within **Macop**:
  168. Abstract Evaluator class is used for computing fitness score associated to a solution. To evaluate all the solutions, this class:
  169. - stores into its ``data`` initialiser dictionary attritute required measures when computing a solution
  170. - has a ``compute`` abstract method enable to compute and associate a score to a given solution
  171. - stores into its ``algo`` attritute the current algorithm to use (we will talk about algorithm later)
  172. We must therefore now create our own evaluator based on the proposed structure.
  173. Custom evaluator
  174. ~~~~~~~~~~~~~~~~~~~~~
  175. To create our own evaluator, we need both:
  176. - data useful for evaluating a solution
  177. - compute the fitness associated with the state of the solution from these data. Hence, implement specific ``compute`` method.
  178. We will define the ``KnapsackEvaluator`` class, which will therefore allow us to evaluate solutions to our current problem.
  179. .. code-block:: python
  180. """
  181. modules imports
  182. """
  183. from macop.evaluators.base import Evaluator
  184. class KnapsackEvaluator(Evaluator):
  185. def compute(self, solution):
  186. # `_data` contains worths array values of objects
  187. fitness = 0
  188. for index, elem in enumerate(solution.data):
  189. fitness += self._data['worths'][index] * elem
  190. return fitness
  191. It is now possible to initialise our new evaluator with specific data of our problem instance:
  192. .. code-block:: python
  193. """
  194. Problem instance definition
  195. """
  196. elements_score = [ 4, 2, 10, 1, 2 ] # worth of each object
  197. elements_weight = [ 12, 1, 4, 1, 2 ] # weight of each object
  198. """
  199. Evaluator problem instance
  200. """
  201. evaluator = KnapsackEvaluator(data={'worths': elements_score})
  202. # using defined BinarySolution
  203. solution = BinarySolution.random(5)
  204. # obtaining current solution score
  205. solution_fitness = solution.evaluate(evaluator)
  206. # score is also stored into solution
  207. solution_fitness = solution.fitness
  208. .. note::
  209. The current developed ``KnapsackEvaluator`` is available into macop.evaluators.discrete.mono.KnapsackEvaluator_ in **Macop**.
  210. In the next part we will see how to modify our current solution with the use of modification operator.
  211. Apply operators to solution
  212. ==============================
  213. 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.
  214. Operators definition
  215. ~~~~~~~~~~~~~~~~~~~~~~~~~
  216. In the discrete optimisation literature, we can categorise operators into two sections:
  217. - **mutators**: modification of one or more elements of a solution from its current state.
  218. - **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.
  219. Inside **Macop**, operators are also decomposed into these two categories. Inside macop.operators.base_, generic class ``Operator`` enables to manage any kind of operator.
  220. 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.
  221. ``Mutation`` and ``Crossover`` classes inherite from ``Operator``. An ``apply`` function is required for any new operator.
  222. We will now detail these categories of operators and suggest some relative to our problem.
  223. Mutator operator
  224. ~~~~~~~~~~~~~~~~~~~~~
  225. 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.
  226. .. image:: _static/documentation/project_knapsack_mutator.png
  227. :width: 90 %
  228. :align: center
  229. In this example we change a bit value randomly and obtain a new solution from our search space.
  230. .. warning::
  231. Applying an operator can conduct to a new but invalid solution from the search space.
  232. 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.
  233. .. code-block:: python
  234. """
  235. modules imports
  236. """
  237. from macop.operators.discrete.base import Mutation
  238. class SimpleBinaryMutation(Mutation):
  239. def apply(self, solution):
  240. # obtain targeted cell using solution size
  241. size = solution.size
  242. cell = random.randint(0, size - 1)
  243. # copy of solution
  244. copy_solution = solution.clone()
  245. # swicth values
  246. if copy_solution.data[cell]:
  247. copy_solution.data[cell] = 0
  248. else:
  249. copy_solution.data[cell] = 1
  250. # return the new obtained solution
  251. return copy_solution
  252. We can now instanciate our new operator in order to obtain a new solution:
  253. .. code-block:: python
  254. """
  255. BinaryMutator instance
  256. """
  257. mutator = SimpleBinaryMutation()
  258. # using defined BinarySolution
  259. solution = BinarySolution.random(5)
  260. # obtaining new solution using operator
  261. new_solution = mutator.apply(solution)
  262. .. note::
  263. The developed ``SimpleBinaryMutation`` is available into macop.operators.discrete.mutators.SimpleBinaryMutation_ in **Macop**.
  264. Crossover operator
  265. ~~~~~~~~~~~~~~~~~~~~~~~
  266. 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.
  267. .. image:: _static/documentation/project_knapsack_crossover.png
  268. :width: 95%
  269. :align: center
  270. In this example we merge two solutions with a specific splitting criterion in order to obtain an offspring.
  271. We will now implement the SimpleCrossover crossover operator, which will merge data from two solutions.
  272. The first half of solution 1 will be saved and added to the second half of solution 2 to generate the new solution (offspring).
  273. .. code-block:: python
  274. """
  275. modules imports
  276. """
  277. from macop.operators.discrete.base import Crossover
  278. class SimpleCrossover(Crossover):
  279. def apply(self, solution1, solution2):
  280. size = solution1.size
  281. # default split index used
  282. splitIndex = int(size / 2)
  283. # copy data of solution 1
  284. firstData = solution1.data.copy()
  285. # copy of solution 2
  286. copy_solution = solution2.clone()
  287. copy_solution.data[splitIndex:] = firstData[splitIndex:]
  288. return copy_solution
  289. We can now use the crossover operator created to generate new solutions. Here is an example of use:
  290. .. code-block:: python
  291. """
  292. SimpleCrossover instance
  293. """
  294. crossover = SimpleCrossover()
  295. # using defined BinarySolution
  296. solution1 = BinarySolution.random(5)
  297. solution2 = BinarySolution.random(5)
  298. # obtaining new solution using crossover
  299. offspring = crossover.apply(solution1, solution2)
  300. .. tip::
  301. The developed ``SimpleCrossover`` is available into macop.operators.discrete.crossovers.SimpleCrossover_ in **Macop**.
  302. However, the choice of halves of the merged data is made randomly.
  303. 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.
  304. Operator choices
  305. ===================
  306. The ``policy`` feature of **Macop** enables to choose the next operator to apply during the search process of the algorithm based on specific criterion.
  307. Why using policy ?
  308. ~~~~~~~~~~~~~~~~~~~~~~~
  309. Sometimes the nature of the problem and its instance can strongly influence the search results when using mutation operators or crossovers.
  310. Automated operator choice strategies have also been developed in the literature, notably based on reinforcement learning.
  311. The operator choice problem can be seen as the desire to find the best solution generation operator at the next evaluation that will be the most conducive to precisely improving the solution.
  312. .. image:: _static/documentation/operators_choice.png
  313. :width: 45 %
  314. :align: center
  315. .. note::
  316. An implementation using reinforcement learning has been developed as an example in the macop.policies.reinforcement_ module.
  317. However, it will not be detailed here. You can refer to the API documentation for more details.
  318. Custom policy
  319. ~~~~~~~~~~~~~~~~~~
  320. In our case, we are not going to exploit a complex enough implementation of a ``policy``. Simply, we will use a random choice of operator.
  321. First, let's take a look of the ``Policy`` abstract class available in macop.policies.base_:
  322. ``Policy`` instance will have of ``operators`` attributes in order to keep track of possible operators when selecting one.
  323. Here, in our implementation we only need to specify the ``select`` abstract method. The ``apply`` method will select the next operator and return the new solution.
  324. .. code-block:: python
  325. """
  326. module imports
  327. """
  328. from macop.policies.base import Policy
  329. class RandomPolicy(Policy):
  330. def select(self):
  331. """
  332. Select specific operator
  333. """
  334. # choose operator randomly
  335. index = random.randint(0, len(self.operators) - 1)
  336. return self.operators[index]
  337. We can now use this operator choice policy to update our current solution:
  338. .. code-block:: python
  339. """
  340. Operators instances
  341. """
  342. mutator = SimpleMutation()
  343. crossover = SimpleCrossover()
  344. """
  345. RandomPolicy instance
  346. """
  347. policy = RandomPolicy([mutator, crossover])
  348. """
  349. Current solutions instance
  350. """
  351. solution1 = BinarySolution.random(5)
  352. solution2 = BinarySolution.random(5)
  353. # pass two solutions in parameters in case of selected crossover operator
  354. new_solution = policy.apply(solution1, solution2)
  355. .. caution::
  356. By default if ``solution2`` parameter is not provided into ``policy.apply`` method for crossover, the best solution known is used from the algorithm linked to the ``policy``.
  357. Updating solutions is therefore now possible with our policy. It is high time to dive into the process of optimizing solutions and digging into our research space.
  358. Optimisation process
  359. =======================
  360. Let us now tackle the interesting part concerning the search for optimum solutions in our research space.
  361. Find local and global optima
  362. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  363. Overall, in an optimization process, we will seek to find the best, or the best solutions that minimize or maximize our objective function (fitness score obtained) in order to respond to our problem.
  364. .. image:: _static/documentation/search_space.png
  365. :width: 95 %
  366. :align: center
  367. Sometimes, the search space can be very simple. A local search can provide access to the global optimum as shown in figure (a) above.
  368. In other cases, the search space is more complex. It may be necessary to explore more rather than exploit in order to get out of a convex zone and not find the global optimum but only a local opmatime solution.
  369. This problem is illustrated in figure (b).
  370. Abstract algorithm class
  371. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  372. An abstract class is proposed within Macop to generalize the management of an algorithm and therefore of a heuristic.
  373. It is located in the macop.algorithms.base_ module.
  374. We will pay attention to the different methods of which she is composed. This class enables to manage some common usages of operation research algorithms:
  375. - initialization function of solution
  376. - validator function to check if solution is valid or not (based on some criteria)
  377. - evaluation function to give fitness score to a solution
  378. - operators used in order to update solution during search process
  379. - policy process applied when choosing next operator to apply
  380. - callbacks function in order to do some relative stuff every number of evaluation or reload algorithm state
  381. - parent algorithm associated to this new algorithm instance (hierarchy management)
  382. She is composed of few default attributes:
  383. - initialiser: {function} -- basic function strategy to initialise solution
  384. - evaluator: {:class:`~macop.evaluators.base.Evaluator`} -- evaluator instance in order to obtained fitness (mono or multiple objectives)
  385. - operators: {[:class:`~macop.operators.base.Operator`]} -- list of operator to use when launching algorithm
  386. - policy: {:class:`~macop.policies.base.Policy`} -- Policy instance strategy to select operators
  387. - validator: {function} -- basic function to check if solution is valid or not under some constraints
  388. - maximise: {bool} -- specify kind of optimisation problem
  389. - verbose: {bool} -- verbose or not information about the algorithm
  390. - currentSolution: {:class:`~macop.solutions.base.Solution`} -- current solution managed for current evaluation comparison
  391. - bestSolution: {:class:`~macop.solutions.base.Solution`} -- best solution found so far during running algorithm
  392. - callbacks: {[:class:`~macop.callbacks.base.Callback`]} -- list of Callback class implementation to do some instructions every number of evaluations and `load` when initialising algorithm
  393. - parent: {:class:`~macop.algorithms.base.Algorithm`} -- parent algorithm reference in case of inner Algorithm instance (optional)
  394. .. caution::
  395. An important thing here are the ``result`` functions brought as an editable attribute by the ``@property`` and ``@result.setter`` decorators. The idea is to allow the user to modify these functions in order to change the expected result of the algorithm regardless of the data to be returned/modified.
  396. The notion of hierarchy between algorithms is introduced here. We can indeed have certain dependencies between algorithms.
  397. The methods ``increaseEvaluation``, ``getGlobalEvaluation`` and ``getGlobalMaxEvaluation`` ensure that the expected global number of evaluations is correctly managed, just like the ``stop`` method for the search stop criterion.
  398. The ``evaluate``, ``update`` and ``isBetter`` will be used a lot when looking for a solution in the search space.
  399. In particular the ``update`` function, which will call the ``policy`` instance to generate a new valid solution.
  400. ``isBetter`` method is also overloadable especially if the algorithm does not take any more into account than a single solution to be verified (verification via a population for example).
  401. The ``initRun`` method specify the way you intialise your algorithm (``bestSolution`` and ``currentSolution`` as example) if algorithm not already initialised.
  402. .. note::
  403. The ``initRun`` method can also be used for intialise population of solutions instead of only one best solution, if you want to manage a genetic algorithm.
  404. Most important part is the ``run`` method. Into abstract, the ``run`` method only initialised the current number of evaluation for the algorithm based on the parent algorithm if we are into inner algorithm.
  405. It is always **mandatory** to call the parent class ``run`` method using ``super().run(evaluations)``. Then, using ``evaluations`` parameter which is the number of evaluations budget to run, we can process or continue to find solutions into search space.
  406. .. warning::
  407. The other methods such as ``addCallback``, ``resume`` and ``progress`` will be detailed in the next part focusing on the notion of callback.
  408. Local search algorithm
  409. ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  410. We are going to carry out our first local search algorithm within our search space. A `local search` consists of starting from a solution, then applying a mutation or crossover operation to it, in order to obtain a new one.
  411. This new solution is evaluated and retained if it is better. We will speak here of the notion of **neighborhood exploration**. The process is then completed in the same way.
  412. The local search ends after a certain number of evaluations and the best evaluated solution obtained is returned.
  413. Let's implement an algorithm well known under the name of hill climber best improvment inheriting from the mother algorithm class and name it ``HillClimberBestImprovment``.
  414. .. code-block:: python
  415. """
  416. module imports
  417. """
  418. from macop.algorithms.base import Algorithm
  419. class HillClimberBestImprovment(Algorithm):
  420. def run(self, evaluations):
  421. """
  422. Run a local search algorithm
  423. """
  424. # by default use of mother method to initialise variables
  425. super().run(evaluations)
  426. # initialise current solution and best solution
  427. self.initRun()
  428. solutionSize = self._currentSolution.size
  429. # local search algorithm implementation
  430. while not self.stop():
  431. for _ in range(solutionSize):
  432. # update current solution using policy
  433. newSolution = self.update(self._currentSolution)
  434. # if better solution than currently, replace it
  435. if self.isBetter(newSolution):
  436. self._bestSolution = newSolution
  437. # increase number of evaluations
  438. self.increaseEvaluation()
  439. # stop algorithm if necessary
  440. if self.stop():
  441. break
  442. # set new current solution using best solution found in this neighbor search
  443. self._currentSolution = self._bestSolution
  444. return self._bestSolution
  445. Our algorithm is now ready to work. As previously, let us define two operators as well as a random choice strategy.
  446. We will also need to define a **solution initialisation function** so that the algorithm can generate new solutions.
  447. .. code-block:: python
  448. """
  449. Problem instance definition
  450. """
  451. elements_score = [ 4, 2, 10, 1, 2 ] # worth of each object
  452. elements_weight = [ 12, 1, 4, 1, 2 ] # weight of each object
  453. # evaluator instance
  454. evaluator = KnapsackEvaluator(data={'worths': elements_score})
  455. # valid instance using lambda
  456. validator = lambda solution: sum([ elements_weight[i] * solution.data[i] for i in range(len(solution.data))]) <= 15
  457. # initialiser instance using lambda with default param value
  458. initialiser = lambda x=5: BinarySolution.random(x, validator)
  459. # operators list with crossover and mutation
  460. operators = [SimpleCrossover(), SimpleMutation()]
  461. # policy random instance
  462. policy = RandomPolicy(operators)
  463. # maximizing algorithm (relative to knapsack problem)
  464. algo = HillClimberBestImprovment(initialiser, evaluator, operators, policy, validator, maximise=True, verbose=False)
  465. # run the algorithm and get solution found
  466. solution = algo.run(100)
  467. print(solution.fitness)
  468. .. note::
  469. The ``verbose`` algorithm parameter will log into console the advancement process of the algorithm is set to ``True`` (the default value).
  470. Exploratory algorithm
  471. ~~~~~~~~~~~~~~~~~~~~~~~~~~
  472. As explained in **figure (b)** of **section 8.1**, sometimes the search space is more complicated due to convex parts and need heuristic with other strategy rather than a simple local search.
  473. The way to counter this problem is to allow the algorithm to exit the exploitation phase offered by local search. But rather to seek to explore other parts of the research space. This is possible by simply carrying out several local searches with our budget (number of evaluations).
  474. The idea is to make a leap in the search space in order to find a new local optimum which can be the global optimum. The explained process is illustrated below:
  475. .. image:: _static/documentation/search_space_simple.png
  476. :width: 45 %
  477. :align: center
  478. We are going to implement a more specific algorithm allowing to take a new parameter as input. This is a local search, the one previously developed. For that, we will have to modify the constructor a little.
  479. Let's called this new algorithm ``IteratedLocalSearch``:
  480. .. code-block:: python
  481. """
  482. module imports
  483. """
  484. from macop.algorithms.base import Algorithm
  485. class IteratedLocalSearch(Algorithm):
  486. def __init__(self,
  487. initialiser,
  488. evaluator,
  489. operators,
  490. policy,
  491. validator,
  492. localSearch,
  493. maximise=True,
  494. parent=None,
  495. verbose=True):
  496. super().__init__(initialiser, evaluator, operators, policy, validator, maximise, parent, verbose)
  497. # specific local search associated with current algorithm
  498. self._localSearch = localSearch
  499. # need to attach current algorithm as parent
  500. self._localSearch.setParent(self)
  501. def run(self, evaluations, ls_evaluations=100):
  502. """
  503. Run the iterated local search algorithm using local search
  504. """
  505. # by default use of mother method to initialise variables
  506. super().run(evaluations)
  507. # initialise current solution
  508. self.initRun()
  509. # local search algorithm implementation
  510. while not self.stop():
  511. # create and search solution from local search (stop method can be called inside local search)
  512. newSolution = self._localSearch.run(ls_evaluations)
  513. # if better solution than currently, replace it
  514. if self.isBetter(newSolution):
  515. self._bestSolution = newSolution
  516. self.information()
  517. return self._bestSolution
  518. In the initialization phase we have attached our local search passed as a parameter with the current algorithm as parent.
  519. The goal is to touch keep track of the overall search evaluation number (relative to the parent algorithm).
  520. Then, we use this local search in our ``run`` method to allow a better search for solutions.
  521. .. code-block:: python
  522. """
  523. Problem instance definition
  524. """
  525. elements_score = [ 4, 2, 10, 1, 2 ] # worth of each object
  526. elements_weight = [ 12, 1, 4, 1, 2 ] # weight of each object
  527. # evaluator instance
  528. evaluator = KnapsackEvaluator(data={'worths': elements_score})
  529. # valid instance using lambda
  530. validator = lambda solution: sum([ elements_weight[i] * solution.data[i] for i in range(len(solution.data))]) <= 15
  531. # initialiser instance using lambda with default param value
  532. initialiser = lambda x=5: BinarySolution.random(x, validator)
  533. # operators list with crossover and mutation
  534. operators = [SimpleCrossover(), SimpleMutation()]
  535. # policy random instance
  536. policy = RandomPolicy(operators)
  537. # maximizing algorithm (relative to knapsack problem)
  538. localSearch = HillClimberBestImprovment(initialiser, evaluator, operators, policy, validator, maximise=True, verbose=False)
  539. algo = IteratedLocalSearch(initialiser, evaluator, operators, policy, validator, localSearch=local_search, maximise=True, verbose=False)
  540. # run the algorithm using local search and get solution found
  541. solution = algo.run(evaluations=100, ls_evaluations=10)
  542. print(solution.fitness)
  543. .. note::
  544. These two last algorithms developed are available in the library within the module macop.algorithms.mono_.
  545. We have one final feature to explore in the next part. This is the notion of ``callback``.
  546. Keep track
  547. ==============
  548. Keeping track of the running algorithm can be useful on two levels. First of all to understand how it unfolded at the end of the classic run. But also in the case of the unwanted shutdown of the algorithm.
  549. This section will allow you to introduce the recovery of the algorithm thanks to a continuous backup functionality.
  550. Logging into algorithm
  551. ~~~~~~~~~~~~~~~~~~~~~~
  552. Some logs can be retrieve after running an algorithm. **Macop** uses the ``logging`` Python package in order to log algorithm advancement.
  553. Here is an example of use when running an algorithm:
  554. .. code-block:: python
  555. """
  556. basic imports
  557. """
  558. import logging
  559. # logging configuration
  560. logging.basicConfig(format='%(asctime)s %(message)s', filename='data/example.log', level=logging.DEBUG)
  561. ...
  562. # maximizing algorithm (relative to knapsack problem)
  563. algo = HillClimberBestImprovment(initialiser, evaluator, operators, policy, validator, maximise=True, verbose=False)
  564. # run the algorithm using local search and get solution found
  565. solution = algo.run(evaluations=100)
  566. print(solution.fitness)
  567. Hence, log data are saved into ``data/example.log`` in our example.
  568. Callbacks introduction
  569. ~~~~~~~~~~~~~~~~~~~~~~~
  570. Having output logs can help to understand an error that has occurred, however all the progress of the research carried out may be lost.
  571. For this, the functionality relating to callbacks has been developed.
  572. Within **Macop**, a callback is a specific instance of macop.callbacks.base.Callback_ that allows you to perform an action of tracing / saving information **every** ``n`` **evaluations** but also reloading information if necessary when restarting an algorithm.
  573. - The ``run`` method will be called during run process of the algo and do backup at each specific number of evaluations.
  574. - The ``load`` method will be used to reload the state of the algorithm from the last information saved. All saved data is saved in a file whose name will be specified by the user.
  575. Towards the use of Callbacks
  576. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  577. We are going to create our own Callback instance called ``BasicCheckpoint`` which will save the best solution found and number of evaluations done in order to reload it for the next run of our algorithm.
  578. .. code-block:: python
  579. """
  580. module imports
  581. """
  582. from macop.callbacks.base import Callback
  583. class BasicCheckpoint(Callback):
  584. def run(self):
  585. """
  586. Check if necessary to do backup based on `every` variable
  587. """
  588. # get current best solution
  589. solution = self.algo._bestSolution
  590. currentEvaluation = self.algo.getGlobalEvaluation()
  591. # backup if necessary every number of evaluations
  592. if currentEvaluation % self._every == 0:
  593. # create specific line with solution data
  594. solution.data = ""
  595. solutionSize = len(solution.data)
  596. for index, val in enumerate(solution.data):
  597. solution.data += str(val)
  598. if index < solutionSize - 1:
  599. solution.data += ' '
  600. # number of evaluations done, solution data and fitness score
  601. line = str(currentEvaluation) + ';' + solution.data + ';' + str(
  602. solution.fitness) + ';\n'
  603. # check if file exists
  604. if not os.path.exists(self._filepath):
  605. with open(self._filepath, 'w') as f:
  606. f.write(line)
  607. else:
  608. with open(self._filepath, 'a') as f:
  609. f.write(line)
  610. def load(self):
  611. """
  612. Load last backup line and set algorithm state (best solution and evaluations)
  613. """
  614. if os.path.exists(self._filepath):
  615. with open(self._filepath) as f:
  616. # get last line and read data
  617. lastline = f.readlines()[-1]
  618. data = lastline.split(';')
  619. # get evaluation information
  620. globalEvaluation = int(data[0])
  621. # restore number of evaluations
  622. if self.algo.getParent() is not None:
  623. self.algo.getParent()._numberOfEvaluations = globalEvaluation
  624. else:
  625. self.algo._numberOfEvaluations = globalEvaluation
  626. # get best solution data information
  627. solution.data = list(map(int, data[1].split(' ')))
  628. # avoid uninitialised solution
  629. if self.algo._bestSolution is None:
  630. self.algo._bestSolution = self.algo.initialiser()
  631. # set to algorithm the lastest obtained best solution
  632. self.algo._bestsolution.data = np.array(solution.data)
  633. self.algo._bestSolution._score = float(data[2])
  634. In this way, it is possible to specify the use of a callback to our algorithm instance:
  635. .. code-block:: python
  636. ...
  637. # maximizing algorithm (relative to knapsack problem)
  638. algo = HillClimberBestImprovment(initialiser, evaluator, operators, policy, validator, maximise=True, verbose=False)
  639. callback = BasicCheckpoint(every=5, filepath='data/hillClimberBackup.csv')
  640. # add callback into callback list
  641. algo.addCallback(callback)
  642. # run the algorithm using local search and get solution found
  643. solution = algo.run(evaluations=100)
  644. print(solution.fitness)
  645. .. note::
  646. It is possible to add as many callbacks as desired in the algorithm in question.
  647. Previously, some methods of the abstract ``Algorithm`` class have not been presented. These methods are linked to the use of callbacks,
  648. in particular the ``addCallback`` method which allows the addition of a callback to an algorithm instance as seen above.
  649. - The ``resume`` method will reload all callbacks list using ``load`` method.
  650. - The ``progress`` method will ``run`` each callbacks during the algorithm search.
  651. If we want to exploit this functionality, then we will need to exploit them within our algorithm. Let's make the necessary modifications for our algorithm ``IteratedLocalSearch``:
  652. .. code-block:: python
  653. """
  654. module imports
  655. """
  656. from macop.algorithms.base import Algorithm
  657. class IteratedLocalSearch(Algorithm):
  658. ...
  659. def run(self, evaluations, ls_evaluations=100):
  660. """
  661. Run the iterated local search algorithm using local search
  662. """
  663. # by default use of mother method to initialise variables
  664. super().run(evaluations)
  665. # initialise current solution
  666. self.initRun()
  667. # restart using callbacks backup list
  668. self.resume()
  669. # local search algorithm implementation
  670. while not self.stop():
  671. # create and search solution from local search
  672. newSolution = self._localSearch.run(ls_evaluations)
  673. # if better solution than currently, replace it
  674. if self.isBetter(newSolution):
  675. self._bestSolution = newSolution
  676. # check if necessary to call each callbacks
  677. self.progress()
  678. self.information()
  679. return self._bestSolution
  680. All the features of **Macop** were presented. The next section will aim to quickly present the few implementations proposed within **Macop** to highlight the modulality of the package.
  681. Advanced usages
  682. =======================
  683. Multi-objective discrete optimisation
  684. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  685. Within the API of **Macop**, you can find an implementation of The Multi-objective evolutionary algorithm based on decomposition (MOEA/D) is a general-purpose algorithm for approximating the Pareto set of multi-objective optimization problems.
  686. It decomposes the original multi-objective problem into a number of single-objective optimization sub-problems and then uses an evolutionary process to optimize these sub-problems simultaneously and cooperatively.
  687. MOEA/D is a state-of-art algorithm in aggregation-based approaches for multi-objective optimization.
  688. .. image:: _static/documentation/search_space_moead.png
  689. :width: 45 %
  690. :align: center
  691. As illustrated below, the two main objectives are sub-divised into 5 single-objective optimization sub-problems in order to find the Pareto front.
  692. - macop.algorithms.multi.MOSubProblem_ class defines each sub-problem of MOEA/D.
  693. - macop.algorithms.multi.MOEAD_ class exploits ``MOSubProblem`` and implements MOEA/D using weighted-sum of objectives method.
  694. An example with MOEAD for knapsack problem is available in knapsackMultiExample.py_.
  695. .. _knapsackMultiExample.py: https://github.com/jbuisine/macop/blob/master/examples/knapsackMultiExample.py
  696. Continuous Zdt problems
  697. ~~~~~~~~~~~~~~~~~~~~~~~
  698. Even if the package is not primarily intended for continuous optimisation, it allows for adaptation to continuous optimisation.
  699. Based on the Zdt_ benchmarks function, it offers an implementation of Solution, Operator and Evaluator to enable the optimisation of this kind of problem.
  700. .. _Zdt: https://en.wikipedia.org/wiki/Test_functions_for_optimization
  701. - macop.solutions.continuous.ContinuousSolution_: manage float array solution in order to represent continuous solution;
  702. - macop.operators.continuous.mutators.PolynomialMutation_: update solution using polynomial mutation over solution's data;
  703. - macop.operators.continuous.crossovers.BasicDifferentialEvolutionCrossover_: use of new generated solutions in order to obtain new offspring solution;
  704. - macop.evaluators.continous.mono.ZdtEvaluator_: continuous evaluator for `Zdt` problem instance. Take into its ``data``, the ``f`` Zdt function;
  705. - macop.callbacks.classicals.ContinuousCallback_: manage callback and backup of continuous solution.
  706. A complete implementation example with the Rosenbrock_ function is available.
  707. .. _macop.algorithms.base: macop/macop.algorithms.base.html#module-macop.algorithms.base
  708. .. _macop.algorithms.mono: macop/macop.algorithms.mono.html#module-macop.algorithms.mono
  709. .. _macop.solutions.base: macop/macop.solutions.base.html#module-macop.solutions.base
  710. .. _macop.solutions.base.Solution: macop/macop.solutions.base.html#macop.solutions.base.Solution
  711. .. _macop.solutions.discrete.BinarySolution: macop/macop.solutions.discrete.html#macop.solutions.discrete.BinarySolution
  712. .. _macop.evaluators.base.Evaluator: macop/macop.evaluators.base.html#macop.evaluators.base.Evaluator
  713. .. _macop.evaluators.discrete.mono.KnapsackEvaluator: macop/macop.evaluators.discrete.mono.html#macop.evaluators.discrete.mono.KnapsackEvaluator
  714. .. _macop.operators.base: macop/macop.operators.base.html#module-macop.operators.base
  715. .. _macop.operators.discrete.mutators.SimpleBinaryMutation: macop/macop.operators.discrete.mutators.html#macop.operators.discrete.mutators.SimpleBinaryMutation
  716. .. _macop.operators.discrete.crossovers.SimpleCrossover: macop/macop.operators.discrete.crossovers.html#macop.operators.discrete.crossovers.SimpleCrossover
  717. .. _macop.policies.reinforcement: macop/macop.policies.reinforcement.html#module-macop.policies.reinforcement
  718. .. _macop.policies.base: macop/macop.policies.base.html#module-macop.policies.base
  719. .. _macop.callbacks.base.Callback: macop/macop.callbacks.base.html#macop.callbacks.base.Callback
  720. .. _macop.algorithms.multi.MOSubProblem: macop/macop.algorithms.multi.html#macop.algorithms.multi.MOSubProblem
  721. .. _macop.algorithms.multi.MOEAD: macop/macop.algorithms.multi.html#macop.algorithms.multi.MOEAD
  722. .. _macop.solutions.continuous.ContinuousSolution: macop/macop.solutions.continuous.html#macop.solutions.continuous.ContinuousSolution
  723. .. _macop.operators.continuous.mutators.PolynomialMutation: macop/macop.operators.continuous.mutators.html#macop.operators.continuous.mutators.PolynomialMutation
  724. .. _macop.operators.continuous.crossovers.BasicDifferentialEvolutionCrossover: macop/macop.operators.continuous.crossovers.html#macop.operators.continuous.crossovers.BasicDifferentialEvolutionCrossover
  725. .. _macop.evaluators.continous.mono.ZdtEvaluator: macop/macop.evaluators.continuous.mono.html#macop.evaluators.continous.mono.ZdtEvaluator
  726. .. _macop.callbacks.classicals.ContinuousCallback: macop/macop.callbacks.classicals.html#macop.callbacks.classicals.ContinuousCallback
  727. .. _Rosenbrock: https://github.com/jbuisine/macop/blob/master/examples/ZdtExample.py