examples.rst.txt 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593
  1. Some examples
  2. =====================================
  3. 1. Mono-objective
  4. -----------------------
  5. In this tutorial, we introduce the way of using `macop` and running your algorithm quickly.
  6. 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).
  7. 1.1 Problem definition
  8. ~~~~~~~~~~~~~~~~~~~~~~
  9. Hence, we define our problem :
  10. - value of each component of knapsack
  11. - weight associated to each of these components (objects)
  12. .. code:: python
  13. """
  14. imports part
  15. """
  16. import random
  17. """
  18. Problem definition
  19. """
  20. random.seed(42)
  21. elements_score = [ random.randint(1, 20) for _ in range(30) ] # value of each object
  22. elements_weight = [ random.randint(5, 25) for _ in range(30) ] # weight of each object
  23. 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).
  24. The best way to represent this problem is to use the `BinarySolution` from `macop` which stores solution as a binary array.
  25. Using the solution representation, we need to define multiple elements to fit our algorithm :
  26. - function which validates or not a solution (based on constraints)
  27. - function which evaluates the solution (in order to obtain fitness)
  28. - initialization solution function
  29. .. code:: python
  30. """
  31. imports part
  32. """
  33. import random
  34. from macop.solutions.BinarySolution import BinarySolution
  35. """
  36. Problem definition
  37. """
  38. random.seed(42)
  39. elements_score = [ random.randint(1, 20) for _ in range(30) ] # value of each object
  40. elements_weight = [ random.randint(5, 25) for _ in range(30) ] # weight of each object
  41. # 1. validator function (we accept only bag with maximum weight 80kg)
  42. def validator(_solution):
  43. weight_sum = 0
  44. for index, elem in enumerate(_solution.data):
  45. weight_sum += elements_weight[index] * elem
  46. if weight_sum <= 80:
  47. return True
  48. else:
  49. False
  50. # 2. function which computes fitness of solution
  51. def evaluator(_solution):
  52. fitness = 0
  53. for index, elem in enumerate(_solution.data):
  54. fitness += (elements_score[index] * elem)
  55. return fitness
  56. # 3. function which here initializes solution ramdomly and check validity of solution
  57. def init():
  58. return BinarySolution([], 30).random(validator)
  59. 1.2 Operators and Policy
  60. ~~~~~~~~~~~~~~~~~~~~~~~~
  61. In our algorithm we need to use some operators in order to improve current best solution found at current `n` evaluations.
  62. In `macop` you have some available operators. In this example, we use 3 of them.
  63. .. code:: python
  64. """
  65. imports part
  66. """
  67. ...
  68. from macop.operators.mutators.SimpleMutation import SimpleMutation
  69. from macop.operators.mutators.SimpleBinaryMutation import SimpleBinaryMutation
  70. from macop.operators.crossovers.SimpleCrossover import SimpleCrossover
  71. """
  72. Problem definition
  73. """
  74. ...
  75. """
  76. Algorithm parameters
  77. """
  78. # list of operators instance to use
  79. operators = [SimpleBinaryMutation(), SimpleMutation(), SimpleCrossover(), RandomSplitCrossover()]
  80. 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.
  81. `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.
  82. Why computing score into **Policy** `apply` method ? Because it's a way to get some important statistics from solution improvment using specific operator.
  83. **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.
  84. .. _UCB: https://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm/
  85. .. code:: python
  86. """
  87. imports part
  88. """
  89. ...
  90. from macop.operators.mutators.SimpleMutation import SimpleMutation
  91. from macop.operators.mutators.SimpleBinaryMutation import SimpleBinaryMutation
  92. from macop.operators.crossovers.SimpleCrossover import SimpleCrossover
  93. from macop.operators.policies.UCBPolicy import UCBPolicy
  94. """
  95. Problem definition
  96. """
  97. ...
  98. """
  99. Algorithm parameters
  100. """
  101. # list of operators instance to use
  102. operators = [SimpleBinaryMutation(), SimpleMutation(), SimpleCrossover(), RandomSplitCrossover()]
  103. # `policy` instance is created using specific value for Upper Confidence Bound
  104. policy = UCBPolicy(operators, C=100.)
  105. 1.3 Before running algorithm
  106. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  107. Before running algorithm we can define a logger to keep track of the all algorithm run.
  108. .. code:: python
  109. """
  110. imports part
  111. """
  112. ...
  113. import logging
  114. """
  115. Problem definition
  116. """
  117. ...
  118. """
  119. Algorithm parameters
  120. """
  121. ...
  122. if not os.path.exists('data'):
  123. os.makedirs('data')
  124. # logging configuration
  125. logging.basicConfig(format='%(asctime)s %(message)s', filename='data/example.log', level=logging.DEBUG)
  126. 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.
  127. .. code:: python
  128. """
  129. imports part
  130. """
  131. ...
  132. import logging
  133. from macop.algorithms.mono.IteratedLocalSearch import IteratedLocalSearch as ILS
  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. algo = ILS(init, evaluator, operators, policy, validator, _maximise=True)
  147. 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.
  148. 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.
  149. A Callback is runned every number of evaluations but can also implement the `load` method in order to do specific instrusctions when initializing algorithm.
  150. 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.
  151. In our case, we need to specify the use of checkpoint if we prefer to restart from.
  152. .. code:: python
  153. """
  154. imports part
  155. """
  156. ...
  157. import logging
  158. from macop.algorithms.mono.IteratedLocalSearch import IteratedLocalSearch as ILS
  159. from macop.callbacks.BasicCheckpoint import BasicCheckpoint
  160. """
  161. Problem definition
  162. """
  163. ...
  164. """
  165. Algorithm parameters
  166. """
  167. ...
  168. if not os.path.exists('data'):
  169. os.makedirs('data')
  170. # logging configuration
  171. logging.basicConfig(format='%(asctime)s %(message)s', filename='data/example.log', level=logging.DEBUG)
  172. algo = ILS(init, evaluator, operators, policy, validator, _maximise=True)
  173. # create instance of BasicCheckpoint callback
  174. callback = BasicCheckpoint(_every=5, _filepath='data/checkpoint.csv')
  175. # Add this callback instance into list of callback
  176. # It tells the algorithm to apply this callback every 5 evaluations
  177. # And also the algorithm to load checkpoint if exists before running by using `load` method of callback
  178. algo.addCallback(callback)
  179. We can also add the `UCBCheckpoint` callback which keeps track of UCB data obtained during previous run:
  180. .. code:: python
  181. """
  182. imports part
  183. """
  184. ...
  185. import logging
  186. from macop.callbacks.UCBCheckpoint import UCBCheckpoint
  187. """
  188. Problem definition
  189. """
  190. ...
  191. """
  192. Algorithm parameters
  193. """
  194. ...
  195. # add UCB Checkpoint callback to keep track of UCB statistics obtained
  196. algo.addCallback(UCBCheckpoint(_every=5, _filepath='data/ucbPolicy.csv'))
  197. In this way, now we can run and obtained the best solution found in `n` evaluations
  198. .. code:: python
  199. bestSol = algo.run(10000)
  200. print('Solution score is {}'.format(evaluator(bestSol)))
  201. 2. Multi-objective
  202. -------------------
  203. 1.1 Problem definition
  204. ~~~~~~~~~~~~~~~~~~~~~~
  205. In this example we also use the knapsack problem, with here, 2 kinds of value for each object in the knapsack :
  206. - value 1 of each component of knapsack
  207. - value 2 of each component of knapsack
  208. - weight associated to each of these components (objects)
  209. 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.
  210. .. code:: python
  211. """
  212. imports part
  213. """
  214. import random
  215. """
  216. Problem definition
  217. """
  218. random.seed(42)
  219. elements_score1 = [ random.randint(1, 20) for _ in range(200) ] # value 1 of each object
  220. elements_score2 = [ random.randint(1, 20) for _ in range(200) ] # value 2 of each object
  221. elements_weight = [ random.randint(5, 25) for _ in range(200) ] # weight of each object
  222. 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).
  223. The best way to represent this problem is to use the `BinarySolution` from `macop` which stores solution as a binary array.
  224. Using the solution representation, we need to define multiple elements to fit our algorithm :
  225. - function which validates or not a solution (based on constraints)
  226. - the first objective function which evaluates the solution (fitness score for objective 1)
  227. - the second objective function which evaluates the solution (fitness score for objective 2)
  228. - initialization solution function
  229. .. code:: python
  230. """
  231. imports part
  232. """
  233. import random
  234. from macop.solutions.BinarySolution import BinarySolution
  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. # 1. validator function (we accept only bag with maximum weight 80kg)
  243. def validator(_solution):
  244. weight_sum = 0
  245. for index, elem in enumerate(_solution.data):
  246. weight_sum += elements_weight[index] * elem
  247. if weight_sum <= 80:
  248. return True
  249. else:
  250. False
  251. # 2. functions which computes fitness of solution for the two objectives
  252. def evaluator1(_solution):
  253. fitness = 0
  254. for index, elem in enumerate(_solution.data):
  255. fitness += (elements_score1[index] * elem)
  256. return fitness
  257. def evaluator2(_solution):
  258. fitness = 0
  259. for index, elem in enumerate(_solution.data):
  260. fitness += (elements_score2[index] * elem)
  261. return fitness
  262. # 3. function which here initializes solution ramdomly and check validity of solution
  263. def init():
  264. return BinarySolution([], 200).random(validator)
  265. 1.2 Operators and Policy
  266. ~~~~~~~~~~~~~~~~~~~~~~~~
  267. In our algorithm we need to use some operators in order to improve current best solution found at current `n` evaluations.
  268. In `macop` you have some available operators. In this example, we use 3 of them.
  269. .. code:: python
  270. """
  271. imports part
  272. """
  273. ...
  274. from macop.operators.mutators.SimpleMutation import SimpleMutation
  275. from macop.operators.mutators.SimpleBinaryMutation import SimpleBinaryMutation
  276. from macop.operators.crossovers.SimpleCrossover import SimpleCrossover
  277. """
  278. Problem definition
  279. """
  280. ...
  281. """
  282. Algorithm parameters
  283. """
  284. # list of operators instance to use
  285. operators = [SimpleBinaryMutation(), SimpleMutation(), SimpleCrossover(), RandomSplitCrossover()]
  286. 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.
  287. `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.
  288. Why computing score into **Policy** `apply` method ? Because it's a way to get some important statistics from solution improvment using specific operator.
  289. **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.
  290. .. _UCB: https://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm/
  291. .. code:: python
  292. """
  293. imports part
  294. """
  295. ...
  296. from macop.operators.mutators.SimpleMutation import SimpleMutation
  297. from macop.operators.mutators.SimpleBinaryMutation import SimpleBinaryMutation
  298. from macop.operators.crossovers.SimpleCrossover import SimpleCrossover
  299. from macop.operators.policies.UCBPolicy import UCBPolicy
  300. """
  301. Problem definition
  302. """
  303. ...
  304. """
  305. Algorithm parameters
  306. """
  307. # list of operators instance to use
  308. operators = [SimpleBinaryMutation(), SimpleMutation(), SimpleCrossover(), RandomSplitCrossover()]
  309. # `policy` instance is created using specific value for Upper Confidence Bound
  310. policy = UCBPolicy(operators, C=100.)
  311. 1.3 How works multi-objective in macop ?
  312. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  313. As we have now multiple objectives, we define a new algorithm named MOEAD for `MultiObjective Evolutionary Algorithm with Decomposition` inside `macop.algorithms.multi.MOEAD`.
  314. The principle of this algorithm is to decompose the multi-objective problem into several single-objective problems (see MOEAD_ documentation framework).
  315. 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.
  316. The `mu` attribute represent the number of sub problems and hence our current population of solutions.
  317. .. _MOEAD: https://sites.google.com/view/moead/home
  318. In order to represent the `mu` mono-objective sub problems (obtained from weighted decomposition), we define the `macop.algorithms.multi.MOSubProblem` class.
  319. 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.
  320. The `evaluator` of MOSubProblem is defined as below:
  321. .. code:: python
  322. def moEvaluator(_solution, _evaluator, _weights):
  323. scores = [eval(_solution) for eval in _evaluator]
  324. # associate objectives scores to solution
  325. _solution.scores = scores
  326. # return the weighted sum
  327. return sum([scores[i] for i, w in enumerate(_weights)])
  328. ...
  329. # compute weighted sum from solution using list of evaluators and weights for current sub problem
  330. sub_evaluator = lambda _solution: moEvaluator(_solution, _evaluator, weights[i])
  331. 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.
  332. This is an example, we based our function using classical weighted sum, we can also implement Tchebychev_ method.
  333. .. _Tchebychev: https://repository.lib.ncsu.edu/handle/1840.16/272
  334. We can now instance our MOEAD algorithm:
  335. .. code:: python
  336. """
  337. imports part
  338. """
  339. ...
  340. import logging
  341. from macop.algorithms.multi.MOEAD import MOEAD
  342. """
  343. Problem definition
  344. """
  345. ...
  346. """
  347. Algorithm parameters
  348. """
  349. ...
  350. if not os.path.exists('data'):
  351. os.makedirs('data')
  352. # logging configuration
  353. logging.basicConfig(format='%(asctime)s %(message)s', filename='data/example.log', level=logging.DEBUG)
  354. algo = MOEAD(init, [evaluator1, evaluator2], operators, policy, validator, _maximise=True)
  355. 1.4 Checkpoint multi-objective solutions
  356. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  357. To keep track of our `mu` population and `pfPop` pareto front set, 2 new callbacks have been defined:
  358. .. code:: python
  359. """
  360. imports part
  361. """
  362. ...
  363. import logging
  364. from macop.algorithms.multi.MOEAD import MOEAD
  365. from macop.callbacks.MultiCheckpoint import MultiCheckpoint
  366. from macop.callbacks.ParetoCheckpoint import ParetoCheckpoint
  367. """
  368. Problem definition
  369. """
  370. ...
  371. """
  372. Algorithm parameters
  373. """
  374. ...
  375. if not os.path.exists('data'):
  376. os.makedirs('data')
  377. # logging configuration
  378. logging.basicConfig(format='%(asctime)s %(message)s', filename='data/example.log', level=logging.DEBUG)
  379. algo = ILS(init, evaluator, operators, policy, validator, _maximise=True)
  380. # Add this callback instance into list of callback
  381. # It tells the algorithm to apply this callback every 5 evaluations
  382. # And also the algorithm to load checkpoint if exists before running by using `load` method of callback
  383. algo.addCallback(MultiCheckpoint(_every=5, _filepath='data/checkpointMOEAD.csv'))
  384. # add Pareto Checkpoint callback instance too
  385. algo.addCallback(ParetoCheckpoint(_every=5, _filepath='data/paretoMOEAD.csv'))
  386. These callbacks only stores the last states of `mu` population and `pfPop`.
  387. We can also add the `UCBCheckpoint` callback which keeps track of UCB data obtained during previous run:
  388. .. code:: python
  389. """
  390. imports part
  391. """
  392. ...
  393. import logging
  394. from macop.callbacks.UCBCheckpoint import UCBCheckpoint
  395. """
  396. Problem definition
  397. """
  398. ...
  399. """
  400. Algorithm parameters
  401. """
  402. ...
  403. # add UCB Checkpoint callback to keep track of UCB statistics obtained
  404. algo.addCallback(UCBCheckpoint(_every=5, _filepath='data/ucbPolicy.csv'))
  405. We can now run the MOEAD algorithm instance:
  406. .. code:: python
  407. paretoFront = algo.run(10000)
  408. print("Pareto front is composed of", len(paretoFront), "solutions")