base.py 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368
  1. """Basic Algorithm class
  2. """
  3. # main imports
  4. import logging
  5. import sys, os
  6. from macop.utils.progress import macop_text, macop_line, macop_progress
  7. # Generic algorithm class
  8. class Algorithm():
  9. """Abstract Algorithm class used as basic algorithm implementation with some specific initialization
  10. This class enables to manage some common usages of operation research algorithms:
  11. - initialization function of solution
  12. - validator function to check if solution is valid or not (based on some criteria)
  13. - evaluation function to give fitness score to a solution
  14. - operators used in order to update solution during search process
  15. - policy process applied when choosing next operator to apply
  16. - callbacks function in order to do some relative stuff every number of evaluation or reload algorithm state
  17. - parent algorithm associated to this new algorithm instance (hierarchy management)
  18. Attributes:
  19. initialiser: {function} -- basic function strategy to initialise solution
  20. evaluator: {:class:`~macop.evaluators.base.Evaluator`} -- evaluator instance in order to obtained fitness (mono or multiple objectives)
  21. operators: {[:class:`~macop.operators.base.Operator`]} -- list of operator to use when launching algorithm
  22. policy: {:class:`~macop.policies.base.Policy`} -- Policy implementation strategy to select operators
  23. validator: {function} -- basic function to check if solution is valid or not under some constraints
  24. maximise: {bool} -- specify kind of optimisation problem
  25. verbose: {bool} -- verbose or not information about the algorithm
  26. currentSolution: {:class:`~macop.solutions.base.Solution`} -- current solution managed for current evaluation comparison
  27. bestSolution: {:class:`~macop.solutions.base.Solution`} -- best solution found so far during running algorithm
  28. callbacks: {[:class:`~macop.callbacks.base.Callback`]} -- list of Callback class implementation to do some instructions every number of evaluations and `load` when initialising algorithm
  29. parent: {:class:`~macop.algorithms.base.Algorithm`} -- parent algorithm reference in case of inner Algorithm instance (optional)
  30. """
  31. def __init__(self,
  32. initialiser,
  33. evaluator,
  34. operators,
  35. policy,
  36. validator,
  37. maximise=True,
  38. parent=None,
  39. verbose=True):
  40. """Basic Algorithm initialisation
  41. Args:
  42. initialiser: {function} -- basic function strategy to initialise solution
  43. evaluator: {:class:`~macop.evaluators.base.Evaluator`} -- evaluator instance in order to obtained fitness (mono or multiple objectives)
  44. operators: {[:class:`~macop.operators.base.Operator`]} -- list of operator to use when launching algorithm
  45. policy: {:class:`~macop.policies.base.Policy`} -- Policy implementation strategy to select operators
  46. validator: {function} -- basic function to check if solution is valid or not under some constraints
  47. maximise: {bool} -- specify kind of optimisation problem
  48. parent: {:class:`~macop.algorithms.base.Algorithm`} -- parent algorithm reference in case of inner Algorithm instance (optional)
  49. verbose: {bool} -- verbose or not information about the algorithm
  50. """
  51. # public members intialization
  52. self.initialiser = initialiser
  53. self.evaluator = evaluator
  54. self.validator = validator
  55. self.policy = policy
  56. # protected members intialization
  57. self._operators = operators
  58. self._callbacks = []
  59. self._bestSolution = None
  60. self._currentSolution = None
  61. # by default
  62. self._numberOfEvaluations = 0
  63. self._maxEvaluations = 0
  64. # other parameters
  65. self._parent = parent # parent algorithm if it's sub algorithm
  66. #self.maxEvaluations = 0 # by default
  67. self._maximise = maximise
  68. self._verbose = verbose
  69. # track reference of algorihtm into operator (keep an eye into best solution)
  70. for operator in self._operators:
  71. if self._parent is not None:
  72. operator.setAlgo(self.getParent())
  73. else:
  74. operator.setAlgo(self)
  75. # also track reference for policy
  76. if self._parent is not None:
  77. self.policy.setAlgo(self.getParent())
  78. else:
  79. self.policy.setAlgo(self)
  80. def addCallback(self, callback):
  81. """Add new callback to algorithm specifying usefull parameters
  82. Args:
  83. callback: {:class:`~macop.callbacks.base.Callback`} -- specific Callback instance
  84. """
  85. # specify current main algorithm reference for callback
  86. if self._parent is not None:
  87. callback.setAlgo(self.getParent())
  88. else:
  89. callback.setAlgo(self)
  90. # set as new
  91. self._callbacks.append(callback)
  92. def resume(self):
  93. """Resume algorithm using Callback instances
  94. """
  95. # load every callback if many things are necessary to do before running algorithm
  96. for callback in self._callbacks:
  97. callback.load()
  98. def getParent(self):
  99. """Recursively find the main parent algorithm attached of the current algorithm
  100. Returns:
  101. {:class:`~macop.algorithms.base.Algorithm`}: main algorithm set for this algorithm
  102. """
  103. current_algorithm = self
  104. parent_alrogithm = None
  105. # recursively find the main algorithm parent
  106. while current_algorithm._parent is not None:
  107. parent_alrogithm = current_algorithm._parent
  108. current_algorithm = current_algorithm._parent
  109. return parent_alrogithm
  110. def setParent(self, parent):
  111. """Set parent algorithm to current algorithm
  112. Args:
  113. parent: {:class:`~macop.algorithms.base.Algorithm`} -- main algorithm set for this algorithm
  114. """
  115. self._parent = parent
  116. @property
  117. def result(self):
  118. """Get the expected result of the current algorithm
  119. By default the best solution (but can be anything you want)
  120. Returns:
  121. {object}: expected result data of the current algorithm
  122. """
  123. return self._bestSolution
  124. @result.setter
  125. def result(self, result):
  126. """Set current default result of the algorithm
  127. Args:
  128. result: {object} -- expected result data of the current algorithm
  129. """
  130. self._bestSolution = result
  131. def initRun(self):
  132. """
  133. initialise the current solution and best solution using the `initialiser` function
  134. """
  135. self._currentSolution = self.initialiser()
  136. # evaluate current solution
  137. self._currentSolution.evaluate(self.evaluator)
  138. self.increaseEvaluation()
  139. # keep in memory best known solution (current solution)
  140. if self._bestSolution is None:
  141. self._bestSolution = self._currentSolution
  142. def increaseEvaluation(self):
  143. """
  144. Increase number of evaluation once a solution is evaluated for each dependant algorithm (parents hierarchy)
  145. """
  146. current_algorithm = self
  147. while current_algorithm is not None:
  148. current_algorithm._numberOfEvaluations += 1
  149. current_algorithm = current_algorithm._parent
  150. def getGlobalEvaluation(self):
  151. """Get the global number of evaluation (if inner algorithm)
  152. Returns:
  153. {int}: current global number of evaluation
  154. """
  155. parent_algorithm = self.getParent()
  156. if parent_algorithm is not None:
  157. return parent_algorithm.getGlobalEvaluation()
  158. return self._numberOfEvaluations
  159. def getEvaluation(self):
  160. """Get the current number of evaluation
  161. Returns:
  162. {int}: current number of evaluation
  163. """
  164. return self._numberOfEvaluations
  165. def setEvaluation(self, evaluations):
  166. """Set the current number of evaluation
  167. Args:
  168. evaluations: {int} -- current expected number of evaluation
  169. """
  170. self._numberOfEvaluations = evaluations
  171. def getGlobalMaxEvaluation(self):
  172. """Get the global max number of evaluation (if inner algorithm)
  173. Returns:
  174. {int}: current global max number of evaluation
  175. """
  176. parent_algorithm = self.getParent()
  177. if parent_algorithm is not None:
  178. return parent_algorithm.getGlobalMaxEvaluation()
  179. return self._maxEvaluations
  180. def stop(self):
  181. """
  182. Global stopping criteria (check for parents algorithm hierarchy too)
  183. """
  184. parent_algorithm = self.getParent()
  185. # based on global stopping creteria or on its own stopping critera
  186. if parent_algorithm is not None:
  187. return parent_algorithm._numberOfEvaluations >= parent_algorithm._maxEvaluations or self._numberOfEvaluations >= self._maxEvaluations
  188. return self._numberOfEvaluations >= self._maxEvaluations
  189. def evaluate(self, solution):
  190. """
  191. Evaluate a solution using evaluator passed when intialize algorithm
  192. Args:
  193. solution: {:class:`~macop.solutions.base.Solution`} -- solution to evaluate
  194. Returns:
  195. {float}: fitness score of solution which is not already evaluated or changed
  196. Note:
  197. if multi-objective problem this method can be updated using array of `evaluator`
  198. """
  199. return solution.evaluate(self.evaluator)
  200. def update(self, solution):
  201. """
  202. Apply update function to solution using specific `policy`
  203. Check if solution is valid after modification and returns it
  204. Args:
  205. solution: {:class:`~macop.solutions.base.Solution`} -- solution to update using current policy
  206. Returns:
  207. {:class:`~macop.solutions.base.Solution`}: updated solution obtained by the selected operator
  208. """
  209. # two parameters are sent if specific crossover solution are wished
  210. sol = self.policy.apply(solution)
  211. # compute fitness of new solution if not already computed
  212. if sol._score is None:
  213. sol.evaluate(self.evaluator)
  214. if (sol.isValid(self.validator)):
  215. return sol
  216. else:
  217. logging.info("-- New solution is not valid %s" % sol)
  218. return solution
  219. def isBetter(self, solution):
  220. """
  221. Check if solution is better than best found
  222. - if the new solution is not valid then the fitness comparison is not done
  223. - fitness comparison is done using problem nature (maximising or minimising)
  224. Args:
  225. solution: {:class:`~macop.solutions.base.Solution`} -- solution to compare with best one
  226. Returns:
  227. {bool}:`True` if better
  228. """
  229. if not solution.isValid(self.validator):
  230. return False
  231. # depending of problem to solve (maximizing or minimizing)
  232. if self._maximise:
  233. if solution.fitness > self._bestSolution.fitness:
  234. return True
  235. else:
  236. if solution.fitness < self._bestSolution.fitness:
  237. return True
  238. # by default
  239. return False
  240. def run(self, evaluations):
  241. """
  242. Run the specific algorithm following number of evaluations to find optima
  243. """
  244. # append number of max evaluation if multiple run called
  245. self._maxEvaluations += evaluations
  246. # check if global evaluation is used or not
  247. if self.getParent() is not None and self.getGlobalEvaluation() != 0:
  248. # init number evaluations of inner algorithm depending of globalEvaluation
  249. # allows to restart from `checkpoint` last evaluation into inner algorithm
  250. rest = self.getGlobalEvaluation() % self._maxEvaluations
  251. self._numberOfEvaluations = rest
  252. else:
  253. self._numberOfEvaluations = 0
  254. logging.info(
  255. f"Run {self.__str__()} with {(self.__str__(), evaluations)} evaluations"
  256. )
  257. def progress(self):
  258. """
  259. Log progress and apply callbacks if necessary
  260. """
  261. if len(self._callbacks) > 0:
  262. for callback in self._callbacks:
  263. callback.run()
  264. if self._verbose:
  265. macop_progress(self, self.getGlobalEvaluation(),
  266. self.getGlobalMaxEvaluation())
  267. logging.info(
  268. f"-- {type(self).__name__} evaluation {self._numberOfEvaluations} of {self._maxEvaluations} - BEST SCORE {self._bestSolution._score}"
  269. )
  270. def end(self):
  271. """Display end message into `run` method
  272. """
  273. macop_text(
  274. self,
  275. f'({type(self).__name__}) Found after {self._numberOfEvaluations} evaluations \n - {self._bestSolution}'
  276. )
  277. macop_line(self)
  278. def information(self):
  279. logging.info(
  280. f"-- Best {self._bestSolution} - SCORE {self._bestSolution.fitness}"
  281. )
  282. def __str__(self):
  283. return f"{type(self).__name__} using {type(self._bestSolution).__name__}"