examples.rst 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626
  1. Some examples
  2. =====================================
  3. 1. Some information
  4. --------------------
  5. The package consists of several modules:
  6. - **algorithms**: generic and implemented OR algorithms.
  7. - **evaluator**: contains all the implemented evaluation functions.
  8. - **solutions**: all declared solutions classes used to represent problem data.
  9. - **operators**: mutators, crossovers update of solution. This module also has policies classes to manage the way of update and use solution.
  10. - **callbacks**: contains Callback class implemenration for making callback instructions every number of evaluations.
  11. 1.1 Implemented algorithms
  12. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  13. Both single and multi-objective algorithms have been implemented for demonstration purposes. The mono-objective Iterated Local Search algorithm which aims to perform local searches and then to explore again (explorations vs. exploitation trade-off). On the multi-objective side, the MOEA/D algorithm has been implemented using the weighted-sum of objectives method (Tchebycheff approach can also be used). This algorithm aims at decomposing the multi-objective problem into `mu` under single-objective problem in order to obtain the pareto front.
  14. 1.2 Available solutions
  15. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  16. Currently, only combinatorial solutions are offered, with the well-known knapsack problem as an example. Of course, it's easy to add your own representations of solutions.
  17. 1.3 Update solutions
  18. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  19. A few mutation and crossover operators have been implemented, however it remains quite simple. What is interesting here is that it is possible to develop one's own strategy for choosing operators for the next evaluation. The available UCBPolicy class proposes this functionality as an example, since it will seek to propose the best operator to apply based on a method known as Adaptive Operator Selection (AOS) via the use of the Upper Confidence Bound (UCB) algorithm.
  20. 1.4 Backup feature
  21. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  22. The use of callback instance allows both to save every `k` evaluations of the information but also to reload them once the run of the algorithm is cut. Simply inherit the abstract Callback class and implement the **apply** method to backup and **load** to restore. It is possible to add as many callbacks as required.
  23. 2. Mono-objective
  24. -----------------------
  25. In this tutorial, we introduce the way of using `macop` and running your algorithm quickly.
  26. First of all we need to define the kind of solution which best represent the problem. As example, we use the well known knapsack problem using 30 objects (solution size of 30).
  27. 2.1 Problem definition
  28. ~~~~~~~~~~~~~~~~~~~~~~
  29. Hence, we define our problem :
  30. - value of each component of knapsack
  31. - weight associated to each of these components (objects)
  32. .. code:: python
  33. """
  34. imports part
  35. """
  36. import random
  37. """
  38. Problem definition
  39. """
  40. random.seed(42)
  41. elements_score = [ random.randint(1, 20) for _ in range(30) ] # value of each object
  42. elements_weight = [ random.randint(5, 25) for _ in range(30) ] # weight of each object
  43. We can now define the solution representation. In knapsack problem we want to fill our knapsack in an optimization way selecting or not each component (object).
  44. The best way to represent this problem is to use the `BinarySolution` from `macop` which stores solution as a binary array.
  45. Using the solution representation, we need to define multiple elements to fit our algorithm :
  46. - function which validates or not a solution (based on constraints)
  47. - function which evaluates the solution (in order to obtain fitness)
  48. - initialization solution function
  49. .. code:: python
  50. """
  51. imports part
  52. """
  53. import random
  54. from macop.solutions.BinarySolution import BinarySolution
  55. """
  56. Problem definition
  57. """
  58. random.seed(42)
  59. elements_score = [ random.randint(1, 20) for _ in range(30) ] # value of each object
  60. elements_weight = [ random.randint(5, 25) for _ in range(30) ] # weight of each object
  61. # 1. validator function (we accept only bag with maximum weight 80kg)
  62. def validator(_solution):
  63. weight_sum = 0
  64. for index, elem in enumerate(_solution.data):
  65. weight_sum += elements_weight[index] * elem
  66. if weight_sum <= 80:
  67. return True
  68. else:
  69. False
  70. # 2. function which computes fitness of solution
  71. def evaluator(_solution):
  72. fitness = 0
  73. for index, elem in enumerate(_solution.data):
  74. fitness += (elements_score[index] * elem)
  75. return fitness
  76. # 3. function which here initializes solution ramdomly and check validity of solution
  77. def init():
  78. return BinarySolution([], 30).random(validator)
  79. 2.2 Operators and Policy
  80. ~~~~~~~~~~~~~~~~~~~~~~~~
  81. In our algorithm we need to use some operators in order to improve current best solution found at current `n` evaluations.
  82. In `macop` you have some available operators. In this example, we use 3 of them.
  83. .. code:: python
  84. """
  85. imports part
  86. """
  87. ...
  88. from macop.operators.mutators.SimpleMutation import SimpleMutation
  89. from macop.operators.mutators.SimpleBinaryMutation import SimpleBinaryMutation
  90. from macop.operators.crossovers.SimpleCrossover import SimpleCrossover
  91. """
  92. Problem definition
  93. """
  94. ...
  95. """
  96. Algorithm parameters
  97. """
  98. # list of operators instance to use
  99. operators = [SimpleBinaryMutation(), SimpleMutation(), SimpleCrossover(), RandomSplitCrossover()]
  100. As we defined multiple operators, we have to tell how we want to select them into the algorithm. This is why **Policy** classes have been implemented.
  101. `Policy` class implementation enables to select the next operator to use and once new solution is generated, computes its score (in `apply` method). This class requires all the operators use to be instanciate.
  102. Why computing score into **Policy** `apply` method ? Because it's a way to get some important statistics from solution improvment using specific operator.
  103. **UCBPolicy** as example, based on Upper Confidence Bound (UCB_), computes reward each time a new solution is generated from an operator in order to better select next operator later. We use in this example the `UCBPolicy` implementation.
  104. .. _UCB: https://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm/
  105. .. code:: python
  106. """
  107. imports part
  108. """
  109. ...
  110. from macop.operators.mutators.SimpleMutation import SimpleMutation
  111. from macop.operators.mutators.SimpleBinaryMutation import SimpleBinaryMutation
  112. from macop.operators.crossovers.SimpleCrossover import SimpleCrossover
  113. from macop.operators.policies.UCBPolicy import UCBPolicy
  114. """
  115. Problem definition
  116. """
  117. ...
  118. """
  119. Algorithm parameters
  120. """
  121. # list of operators instance to use
  122. operators = [SimpleBinaryMutation(), SimpleMutation(), SimpleCrossover(), RandomSplitCrossover()]
  123. # `policy` instance is created using specific value for Upper Confidence Bound
  124. policy = UCBPolicy(operators, C=100.)
  125. 2.3 Before running algorithm
  126. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  127. Before running algorithm we can define a logger to keep track of the all algorithm run.
  128. .. code:: python
  129. """
  130. imports part
  131. """
  132. ...
  133. import logging
  134. """
  135. Problem definition
  136. """
  137. ...
  138. """
  139. Algorithm parameters
  140. """
  141. ...
  142. if not os.path.exists('data'):
  143. os.makedirs('data')
  144. # logging configuration
  145. logging.basicConfig(format='%(asctime)s %(message)s', filename='data/example.log', level=logging.DEBUG)
  146. We can now instanciate our algorithm. We use the Iterated Local Search in this example. It is mainly used to avoid local optima using multiple local search.
  147. .. code:: python
  148. """
  149. imports part
  150. """
  151. ...
  152. import logging
  153. from macop.algorithms.mono.IteratedLocalSearch import IteratedLocalSearch as ILS
  154. """
  155. Problem definition
  156. """
  157. ...
  158. """
  159. Algorithm parameters
  160. """
  161. ...
  162. if not os.path.exists('data'):
  163. os.makedirs('data')
  164. # logging configuration
  165. logging.basicConfig(format='%(asctime)s %(message)s', filename='data/example.log', level=logging.DEBUG)
  166. algo = ILS(init, evaluator, operators, policy, validator, _maximise=True)
  167. The algorithm is now well defined and is ready to run ! But one thing can be done, and it's very interesting to avoid restart from scratch the algorithm run.
  168. The use of checkpoint is available in `macop`. A `BasicCheckpoint` class let the algorithm save at `every` evaluations the best solution found. This class is based on callback process.
  169. A Callback is runned every number of evaluations but can also implement the `load` method in order to do specific instrusctions when initializing algorithm.
  170. It's important to note, we can add any number of callbacks we want. For tabu search as example, we need to store many solutions.
  171. In our case, we need to specify the use of checkpoint if we prefer to restart from.
  172. .. code:: python
  173. """
  174. imports part
  175. """
  176. ...
  177. import logging
  178. from macop.algorithms.mono.IteratedLocalSearch import IteratedLocalSearch as ILS
  179. from macop.callbacks.BasicCheckpoint import BasicCheckpoint
  180. """
  181. Problem definition
  182. """
  183. ...
  184. """
  185. Algorithm parameters
  186. """
  187. ...
  188. if not os.path.exists('data'):
  189. os.makedirs('data')
  190. # logging configuration
  191. logging.basicConfig(format='%(asctime)s %(message)s', filename='data/example.log', level=logging.DEBUG)
  192. algo = ILS(init, evaluator, operators, policy, validator, _maximise=True)
  193. # create instance of BasicCheckpoint callback
  194. callback = BasicCheckpoint(_every=5, _filepath='data/checkpoint.csv')
  195. # Add this callback instance into list of callback
  196. # It tells the algorithm to apply this callback every 5 evaluations
  197. # And also the algorithm to load checkpoint if exists before running by using `load` method of callback
  198. algo.addCallback(callback)
  199. We can also add the `UCBCheckpoint` callback which keeps track of UCB data obtained during previous run:
  200. .. code:: python
  201. """
  202. imports part
  203. """
  204. ...
  205. import logging
  206. from macop.callbacks.UCBCheckpoint import UCBCheckpoint
  207. """
  208. Problem definition
  209. """
  210. ...
  211. """
  212. Algorithm parameters
  213. """
  214. ...
  215. # add UCB Checkpoint callback to keep track of UCB statistics obtained
  216. algo.addCallback(UCBCheckpoint(_every=5, _filepath='data/ucbPolicy.csv'))
  217. In this way, now we can run and obtained the best solution found in `n` evaluations
  218. .. code:: python
  219. bestSol = algo.run(10000)
  220. print('Solution score is {}'.format(evaluator(bestSol)))
  221. 3. Multi-objective
  222. -------------------
  223. 3.1 Problem definition
  224. ~~~~~~~~~~~~~~~~~~~~~~
  225. In this example we also use the knapsack problem, with here, 2 kinds of value for each object in the knapsack :
  226. - value 1 of each component of knapsack
  227. - value 2 of each component of knapsack
  228. - weight associated to each of these components (objects)
  229. In multi-objective algorithm, we do not only found one solution but a set of non-dominated solutions called Pareto front as we have multiple objectives.
  230. .. code:: python
  231. """
  232. imports part
  233. """
  234. import random
  235. """
  236. Problem definition
  237. """
  238. random.seed(42)
  239. elements_score1 = [ random.randint(1, 20) for _ in range(200) ] # value 1 of each object
  240. elements_score2 = [ random.randint(1, 20) for _ in range(200) ] # value 2 of each object
  241. elements_weight = [ random.randint(5, 25) for _ in range(200) ] # weight of each object
  242. We can now define the solution representation. In knapsack problem we want to fill our knapsack in an optimization way selecting or not each component (object).
  243. The best way to represent this problem is to use the `BinarySolution` from `macop` which stores solution as a binary array.
  244. Using the solution representation, we need to define multiple elements to fit our algorithm :
  245. - function which validates or not a solution (based on constraints)
  246. - the first objective function which evaluates the solution (fitness score for objective 1)
  247. - the second objective function which evaluates the solution (fitness score for objective 2)
  248. - initialization solution function
  249. .. code:: python
  250. """
  251. imports part
  252. """
  253. import random
  254. from macop.solutions.BinarySolution import BinarySolution
  255. """
  256. Problem definition
  257. """
  258. random.seed(42)
  259. elements_score1 = [ random.randint(1, 20) for _ in range(200) ] # value 1 of each object
  260. elements_score2 = [ random.randint(1, 20) for _ in range(200) ] # value 2 of each object
  261. elements_weight = [ random.randint(5, 25) for _ in range(200) ] # weight of each object
  262. # 1. validator function (we accept only bag with maximum weight 80kg)
  263. def validator(_solution):
  264. weight_sum = 0
  265. for index, elem in enumerate(_solution.data):
  266. weight_sum += elements_weight[index] * elem
  267. if weight_sum <= 80:
  268. return True
  269. else:
  270. False
  271. # 2. functions which computes fitness of solution for the two objectives
  272. def evaluator1(_solution):
  273. fitness = 0
  274. for index, elem in enumerate(_solution.data):
  275. fitness += (elements_score1[index] * elem)
  276. return fitness
  277. def evaluator2(_solution):
  278. fitness = 0
  279. for index, elem in enumerate(_solution.data):
  280. fitness += (elements_score2[index] * elem)
  281. return fitness
  282. # 3. function which here initializes solution ramdomly and check validity of solution
  283. def init():
  284. return BinarySolution([], 200).random(validator)
  285. 3.2 Operators and Policy
  286. ~~~~~~~~~~~~~~~~~~~~~~~~
  287. In our algorithm we need to use some operators in order to improve current best solution found at current `n` evaluations.
  288. In `macop` you have some available operators. In this example, we use 3 of them.
  289. .. code:: python
  290. """
  291. imports part
  292. """
  293. ...
  294. from macop.operators.mutators.SimpleMutation import SimpleMutation
  295. from macop.operators.mutators.SimpleBinaryMutation import SimpleBinaryMutation
  296. from macop.operators.crossovers.SimpleCrossover import SimpleCrossover
  297. """
  298. Problem definition
  299. """
  300. ...
  301. """
  302. Algorithm parameters
  303. """
  304. # list of operators instance to use
  305. operators = [SimpleBinaryMutation(), SimpleMutation(), SimpleCrossover(), RandomSplitCrossover()]
  306. As we defined multiple operators, we have to tell how we want to select them into the algorithm. This is why **Policy** classes have been implemented.
  307. `Policy` class implementation enables to select the next operator to use and once new solution is generated, computes its score (in `apply` method). This class requires all the operators use to be instanciate.
  308. Why computing score into **Policy** `apply` method ? Because it's a way to get some important statistics from solution improvment using specific operator.
  309. **UCBPolicy** as example, based on Upper Confidence Bound (UCB_), computes reward each time a new solution is generated from an operator in order to better select next operator later. We use in this example the `UCBPolicy` implementation.
  310. .. _UCB: https://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm/
  311. .. code:: python
  312. """
  313. imports part
  314. """
  315. ...
  316. from macop.operators.mutators.SimpleMutation import SimpleMutation
  317. from macop.operators.mutators.SimpleBinaryMutation import SimpleBinaryMutation
  318. from macop.operators.crossovers.SimpleCrossover import SimpleCrossover
  319. from macop.operators.policies.UCBPolicy import UCBPolicy
  320. """
  321. Problem definition
  322. """
  323. ...
  324. """
  325. Algorithm parameters
  326. """
  327. # list of operators instance to use
  328. operators = [SimpleBinaryMutation(), SimpleMutation(), SimpleCrossover(), RandomSplitCrossover()]
  329. # `policy` instance is created using specific value for Upper Confidence Bound
  330. policy = UCBPolicy(operators, C=100.)
  331. 3.3 How works multi-objective in macop ?
  332. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  333. As we have now multiple objectives, we define a new algorithm named MOEAD for `MultiObjective Evolutionary Algorithm with Decomposition` inside `macop.algorithms.multi.MOEAD`.
  334. The principle of this algorithm is to decompose the multi-objective problem into several single-objective problems (see MOEAD_ documentation framework).
  335. To implement this algorithm, we now define the attribute `evaluator` as a list of evaluators. The number of objectives is defined by the length of this list and generated weights for each sub problem too.
  336. The `mu` attribute represent the number of sub problems and hence our current population of solutions.
  337. .. _MOEAD: https://sites.google.com/view/moead/home
  338. In order to represent the `mu` mono-objective sub problems (obtained from weighted decomposition), we define the `macop.algorithms.multi.MOSubProblem` class.
  339. This class enables to compute and find best solution from weighted decomposition. The `weights` attribute of this class stores the weight for each objective of this sub problem instance.
  340. The `evaluator` of MOSubProblem is defined as below:
  341. .. code:: python
  342. def moEvaluator(_solution, _evaluator, _weights):
  343. scores = [eval(_solution) for eval in _evaluator]
  344. # associate objectives scores to solution
  345. _solution.scores = scores
  346. # return the weighted sum
  347. return sum([scores[i] for i, w in enumerate(_weights)])
  348. ...
  349. # compute weighted sum from solution using list of evaluators and weights for current sub problem
  350. sub_evaluator = lambda _solution: moEvaluator(_solution, _evaluator, weights[i])
  351. This function computes the weighted sum of objectives (to transform sub problem into mono-objective) and also stores the objectives scores into solution using the dynamic added `scores` attributes.
  352. This is an example, we based our function using classical weighted sum, we can also implement Tchebychev_ method.
  353. .. _Tchebychev: https://repository.lib.ncsu.edu/handle/1840.16/272
  354. We can now instance our MOEAD algorithm:
  355. .. code:: python
  356. """
  357. imports part
  358. """
  359. ...
  360. import logging
  361. from macop.algorithms.multi.MOEAD import MOEAD
  362. """
  363. Problem definition
  364. """
  365. ...
  366. """
  367. Algorithm parameters
  368. """
  369. ...
  370. if not os.path.exists('data'):
  371. os.makedirs('data')
  372. # logging configuration
  373. logging.basicConfig(format='%(asctime)s %(message)s', filename='data/example.log', level=logging.DEBUG)
  374. algo = MOEAD(init, [evaluator1, evaluator2], operators, policy, validator, _maximise=True)
  375. 3.4 Checkpoint multi-objective solutions
  376. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  377. To keep track of our `mu` population and `pfPop` pareto front set, 2 new callbacks have been defined:
  378. .. code:: python
  379. """
  380. imports part
  381. """
  382. ...
  383. import logging
  384. from macop.algorithms.multi.MOEAD import MOEAD
  385. from macop.callbacks.MultiCheckpoint import MultiCheckpoint
  386. from macop.callbacks.ParetoCheckpoint import ParetoCheckpoint
  387. """
  388. Problem definition
  389. """
  390. ...
  391. """
  392. Algorithm parameters
  393. """
  394. ...
  395. if not os.path.exists('data'):
  396. os.makedirs('data')
  397. # logging configuration
  398. logging.basicConfig(format='%(asctime)s %(message)s', filename='data/example.log', level=logging.DEBUG)
  399. algo = ILS(init, evaluator, operators, policy, validator, _maximise=True)
  400. # Add this callback instance into list of callback
  401. # It tells the algorithm to apply this callback every 5 evaluations
  402. # And also the algorithm to load checkpoint if exists before running by using `load` method of callback
  403. algo.addCallback(MultiCheckpoint(_every=5, _filepath='data/checkpointMOEAD.csv'))
  404. # add Pareto Checkpoint callback instance too
  405. algo.addCallback(ParetoCheckpoint(_every=5, _filepath='data/paretoMOEAD.csv'))
  406. These callbacks only stores the last states of `mu` population and `pfPop`.
  407. We can also add the `UCBCheckpoint` callback which keeps track of UCB data obtained during previous run:
  408. .. code:: python
  409. """
  410. imports part
  411. """
  412. ...
  413. import logging
  414. from macop.callbacks.UCBCheckpoint import UCBCheckpoint
  415. """
  416. Problem definition
  417. """
  418. ...
  419. """
  420. Algorithm parameters
  421. """
  422. ...
  423. # add UCB Checkpoint callback to keep track of UCB statistics obtained
  424. algo.addCallback(UCBCheckpoint(_every=5, _filepath='data/ucbPolicy.csv'))
  425. We can now run the MOEAD algorithm instance:
  426. .. code:: python
  427. paretoFront = algo.run(10000)
  428. print("Pareto front is composed of", len(paretoFront), "solutions")