base.py 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318
  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. initializer: {function} -- basic function strategy to initialize solution
  20. evaluator: {Evaluator} -- evaluator instance in order to obtained fitness (mono or multiple objectives)
  21. operators: {[Operator]} -- list of operator to use when launching algorithm
  22. policy: {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: {Solution} -- current solution managed for current evaluation comparison
  27. bestSolution: {Solution} -- best solution found so far during running algorithm
  28. callbacks: {[Callback]} -- list of Callback class implementation to do some instructions every number of evaluations and `load` when initializing algorithm
  29. parent: {Algorithm} -- parent algorithm reference in case of inner Algorithm instance (optional)
  30. """
  31. def __init__(self,
  32. initializer,
  33. evaluator,
  34. operators,
  35. policy,
  36. validator,
  37. maximise=True,
  38. parent=None,
  39. verbose=True):
  40. # protected members intialization
  41. self._initializer = initializer
  42. self._evaluator = evaluator
  43. self._operators = operators
  44. self._policy = policy
  45. self._validator = validator
  46. self._callbacks = []
  47. self._bestSolution = None
  48. self._currentSolution = None
  49. # by default
  50. self._numberOfEvaluations = 0
  51. self._maxEvaluations = 0
  52. # other parameters
  53. self._parent = parent # parent algorithm if it's sub algorithm
  54. #self.maxEvaluations = 0 # by default
  55. self._maximise = maximise
  56. self._verbose = verbose
  57. # track reference of algorihtm into operator (keep an eye into best solution)
  58. for operator in self._operators:
  59. if self._parent is not None:
  60. operator.setAlgo(self.getParent())
  61. else:
  62. operator.setAlgo(self)
  63. # also track reference for policy
  64. if self._parent is not None:
  65. self._policy.setAlgo(self.getParent())
  66. else:
  67. self._policy.setAlgo(self)
  68. def addCallback(self, callback):
  69. """Add new callback to algorithm specifying usefull parameters
  70. Args:
  71. callback: {Callback} -- specific Callback instance
  72. """
  73. # specify current main algorithm reference for callback
  74. if self._parent is not None:
  75. callback.setAlgo(self.getParent())
  76. else:
  77. callback.setAlgo(self)
  78. # set as new
  79. self._callbacks.append(callback)
  80. def resume(self):
  81. """Resume algorithm using Callback instances
  82. """
  83. # load every callback if many things are necessary to do before running algorithm
  84. for callback in self._callbacks:
  85. callback.load()
  86. def getParent(self):
  87. """Recursively find the main parent algorithm attached of the current algorithm
  88. Returns:
  89. {Algorithm} -- main algorithm set for this algorithm
  90. """
  91. current_algorithm = self
  92. parent_alrogithm = None
  93. # recursively find the main algorithm parent
  94. while current_algorithm._parent is not None:
  95. parent_alrogithm = current_algorithm._parent
  96. current_algorithm = current_algorithm._parent
  97. return parent_alrogithm
  98. def setParent(self, parent):
  99. """Set parent algorithm to current algorithm
  100. Args:
  101. parent: {Algorithm} -- main algorithm set for this algorithm
  102. """
  103. self._parent = parent
  104. def initRun(self):
  105. """
  106. Initialize the current solution and best solution using the `initialiser` function
  107. """
  108. self._currentSolution = self._initializer()
  109. # evaluate current solution
  110. self._currentSolution.evaluate(self._evaluator)
  111. self.increaseEvaluation()
  112. # keep in memory best known solution (current solution)
  113. if self._bestSolution is None:
  114. self._bestSolution = self._currentSolution
  115. def increaseEvaluation(self):
  116. """
  117. Increase number of evaluation once a solution is evaluated for each dependant algorithm (parents hierarchy)
  118. """
  119. current_algorithm = self
  120. while current_algorithm is not None:
  121. current_algorithm._numberOfEvaluations += 1
  122. current_algorithm = current_algorithm._parent
  123. def getGlobalEvaluation(self):
  124. """Get the global number of evaluation (if inner algorithm)
  125. Returns:
  126. {int} -- current global number of evaluation
  127. """
  128. parent_algorithm = self.getParent()
  129. if parent_algorithm is not None:
  130. return parent_algorithm.getGlobalEvaluation()
  131. return self._numberOfEvaluations
  132. def getGlobalMaxEvaluation(self):
  133. """Get the global max number of evaluation (if inner algorithm)
  134. Returns:
  135. {int} -- current global max number of evaluation
  136. """
  137. parent_algorithm = self.getParent()
  138. if parent_algorithm is not None:
  139. return parent_algorithm.getGlobalMaxEvaluation()
  140. return self._maxEvaluations
  141. def stop(self):
  142. """
  143. Global stopping criteria (check for parents algorithm hierarchy too)
  144. """
  145. parent_algorithm = self.getParent()
  146. # based on global stopping creteria or on its own stopping critera
  147. if parent_algorithm is not None:
  148. return parent_algorithm._numberOfEvaluations >= parent_algorithm._maxEvaluations or self._numberOfEvaluations >= self._maxEvaluations
  149. return self._numberOfEvaluations >= self._maxEvaluations
  150. def evaluate(self, solution):
  151. """
  152. Evaluate a solution using evaluator passed when intialize algorithm
  153. Args:
  154. solution: {Solution} -- solution to evaluate
  155. Returns:
  156. {float} -- fitness score of solution which is not already evaluated or changed
  157. Note:
  158. if multi-objective problem this method can be updated using array of `evaluator`
  159. """
  160. return solution.evaluate(self._evaluator)
  161. def update(self, solution):
  162. """
  163. Apply update function to solution using specific `policy`
  164. Check if solution is valid after modification and returns it
  165. Args:
  166. solution: {Solution} -- solution to update using current policy
  167. Returns:
  168. {Solution} -- updated solution obtained by the selected operator
  169. """
  170. # two parameters are sent if specific crossover solution are wished
  171. sol = self._policy.apply(solution)
  172. # compute fitness of new solution if not already computed
  173. if sol._score is None:
  174. sol.evaluate(self._evaluator)
  175. if (sol.isValid(self._validator)):
  176. return sol
  177. else:
  178. logging.info("-- New solution is not valid %s" % sol)
  179. return solution
  180. def isBetter(self, solution):
  181. """
  182. Check if solution is better than best found
  183. - if the new solution is not valid then the fitness comparison is not done
  184. - fitness comparison is done using problem nature (maximising or minimising)
  185. Args:
  186. solution: {Solution} -- solution to compare with best one
  187. Returns:
  188. {bool} -- `True` if better
  189. """
  190. if not solution.isValid(self._validator):
  191. return False
  192. # depending of problem to solve (maximizing or minimizing)
  193. if self._maximise:
  194. if solution.fitness() > self._bestSolution.fitness():
  195. return True
  196. else:
  197. if solution.fitness() < self._bestSolution.fitness():
  198. return True
  199. # by default
  200. return False
  201. def run(self, evaluations):
  202. """
  203. Run the specific algorithm following number of evaluations to find optima
  204. """
  205. # append number of max evaluation if multiple run called
  206. self._maxEvaluations += evaluations
  207. # check if global evaluation is used or not
  208. if self.getParent() is not None and self.getGlobalEvaluation() != 0:
  209. # init number evaluations of inner algorithm depending of globalEvaluation
  210. # allows to restart from `checkpoint` last evaluation into inner algorithm
  211. rest = self.getGlobalEvaluation() % self._maxEvaluations
  212. self._numberOfEvaluations = rest
  213. else:
  214. self._numberOfEvaluations = 0
  215. logging.info(
  216. f"Run {self.__str__()} with {(self.__str__(), evaluations)} evaluations"
  217. )
  218. def progress(self):
  219. """
  220. Log progress and apply callbacks if necessary
  221. """
  222. if len(self._callbacks) > 0:
  223. for callback in self._callbacks:
  224. callback.run()
  225. if self._verbose:
  226. macop_progress(self, self.getGlobalEvaluation(),
  227. self.getGlobalMaxEvaluation())
  228. logging.info(
  229. f"-- {type(self).__name__} evaluation {self._numberOfEvaluations} of {self._maxEvaluations} - BEST SCORE {self._bestSolution._score}"
  230. )
  231. def end(self):
  232. """Display end message into `run` method
  233. """
  234. macop_text(
  235. self,
  236. f'({type(self).__name__}) Found after {self._numberOfEvaluations} evaluations \n - {self._bestSolution}'
  237. )
  238. macop_line(self)
  239. def information(self):
  240. logging.info(
  241. f"-- Best {self._bestSolution} - SCORE {self._bestSolution.fitness()}"
  242. )
  243. def __str__(self):
  244. return f"{type(self).__name__} using {type(self._bestSolution).__name__}"