Algorithm.py 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249
  1. """Abstract Algorithm class used as basic algorithm implementation with some specific initialization
  2. """
  3. # main imports
  4. import logging
  5. import pkgutil
  6. import sys
  7. from ..utils.color import macop_text, macop_line, macop_progress
  8. # Generic algorithm class
  9. class Algorithm():
  10. """Algorithm class used as basic algorithm
  11. Attributes:
  12. initalizer: {function} -- basic function strategy to initialize solution
  13. evaluator: {function} -- basic function in order to obtained fitness (mono or multiple objectives)
  14. operators: {[Operator]} -- list of operator to use when launching algorithm
  15. policy: {Policy} -- Policy class implementation strategy to select operators
  16. validator: {function} -- basic function to check if solution is valid or not under some constraints
  17. maximise: {bool} -- specify kind of optimization problem
  18. currentSolution: {Solution} -- current solution managed for current evaluation
  19. bestSolution: {Solution} -- best solution found so far during running algorithm
  20. callbacks: {[Callback]} -- list of Callback class implementation to do some instructions every number of evaluations and `load` when initializing algorithm
  21. parent: {Algorithm} -- parent algorithm reference in case of inner Algorithm instance (optional)
  22. """
  23. def __init__(self,
  24. _initalizer,
  25. _evaluator,
  26. _operators,
  27. _policy,
  28. _validator,
  29. _maximise=True,
  30. _parent=None):
  31. self.initializer = _initalizer
  32. self.evaluator = _evaluator
  33. self.operators = _operators
  34. self.policy = _policy
  35. self.validator = _validator
  36. self.callbacks = []
  37. self.bestSolution = None
  38. self.currentSolution = None
  39. # by default
  40. self.numberOfEvaluations = 0
  41. self.maxEvaluations = 0
  42. # other parameters
  43. self.parent = _parent # parent algorithm if it's sub algorithm
  44. #self.maxEvaluations = 0 # by default
  45. self.maximise = _maximise
  46. # track reference of algo into operator (keep an eye into best solution)
  47. for operator in self.operators:
  48. operator.setAlgo(self)
  49. # also track reference for policy
  50. self.policy.setAlgo(self)
  51. def addCallback(self, _callback):
  52. """Add new callback to algorithm specifying usefull parameters
  53. Args:
  54. _callback: {Callback} -- specific Callback instance
  55. """
  56. # specify current main algorithm reference
  57. _callback.setAlgo(self)
  58. # set as new
  59. self.callbacks.append(_callback)
  60. def resume(self):
  61. """Resume algorithm using Callback instances
  62. """
  63. # load every callback if many things are necessary to do before running algorithm
  64. for callback in self.callbacks:
  65. callback.load()
  66. def initRun(self):
  67. """
  68. Initialize the current solution and best solution
  69. """
  70. self.currentSolution = self.initializer()
  71. # evaluate current solution
  72. self.currentSolution.evaluate(self.evaluator)
  73. # keep in memory best known solution (current solution)
  74. if self.bestSolution is None:
  75. self.bestSolution = self.currentSolution
  76. def increaseEvaluation(self):
  77. """
  78. Increase number of evaluation once a solution is evaluated
  79. """
  80. self.numberOfEvaluations += 1
  81. if self.parent is not None:
  82. self.parent.numberOfEvaluations += 1
  83. def getGlobalEvaluation(self):
  84. """Get the global number of evaluation (if inner algorithm)
  85. Returns:
  86. {int} -- current global number of evaluation
  87. """
  88. if self.parent is not None:
  89. return self.parent.numberOfEvaluations
  90. return self.numberOfEvaluations
  91. def getGlobalMaxEvaluation(self):
  92. """Get the global max number of evaluation (if inner algorithm)
  93. Returns:
  94. {int} -- current global max number of evaluation
  95. """
  96. if self.parent is not None:
  97. return self.parent.maxEvaluations
  98. return self.maxEvaluations
  99. def stop(self):
  100. """
  101. Global stopping criteria (check for inner algorithm too)
  102. """
  103. if self.parent is not None:
  104. return self.parent.numberOfEvaluations >= self.parent.maxEvaluations or self.numberOfEvaluations >= self.maxEvaluations
  105. return self.numberOfEvaluations >= self.maxEvaluations
  106. def evaluate(self, _solution):
  107. """
  108. Evaluate a solution using evaluator passed when intialize algorithm
  109. Args:
  110. solution: {Solution} -- solution to evaluate
  111. Returns:
  112. fitness score of solution which is not already evaluated or changed
  113. Note:
  114. if multi-objective problem this method can be updated using array of `evaluator`
  115. """
  116. return _solution.evaluate(self.evaluator)
  117. def update(self, _solution):
  118. """
  119. Apply update function to solution using specific `policy`
  120. Check if solution is valid after modification and returns it
  121. Args:
  122. solution: {Solution} -- solution to update using current policy
  123. Returns:
  124. {Solution} -- updated solution obtained by the selected operator
  125. """
  126. # two parameters are sent if specific crossover solution are wished
  127. sol = self.policy.apply(_solution)
  128. if (sol.isValid(self.validator)):
  129. return sol
  130. else:
  131. logging.info("-- New solution is not valid %s" % sol)
  132. return _solution
  133. def isBetter(self, _solution):
  134. """
  135. Check if solution is better than best found
  136. Args:
  137. solution: {Solution} -- solution to compare with best one
  138. Returns:
  139. {bool} -- `True` if better
  140. """
  141. # depending of problem to solve (maximizing or minimizing)
  142. if self.maximise:
  143. if _solution.fitness() > self.bestSolution.fitness():
  144. return True
  145. else:
  146. if _solution.fitness() < self.bestSolution.fitness():
  147. return True
  148. # by default
  149. return False
  150. def run(self, _evaluations):
  151. """
  152. Run the specific algorithm following number of evaluations to find optima
  153. """
  154. # append number of max evaluation if multiple run called
  155. self.maxEvaluations += _evaluations
  156. # check if global evaluation is used or not
  157. if self.parent is not None and self.getGlobalEvaluation() != 0:
  158. # init number evaluations of inner algorithm depending of globalEvaluation
  159. # allows to restart from `checkpoint` last evaluation into inner algorithm
  160. rest = self.getGlobalEvaluation() % self.maxEvaluations
  161. self.numberOfEvaluations = rest
  162. else:
  163. self.numberOfEvaluations = 0
  164. logging.info("Run %s with %s evaluations" %
  165. (self.__str__(), _evaluations))
  166. def progress(self):
  167. """
  168. Log progress and apply callbacks if necessary
  169. """
  170. if len(self.callbacks) > 0:
  171. for callback in self.callbacks:
  172. callback.run()
  173. macop_progress(self.getGlobalEvaluation(),
  174. self.getGlobalMaxEvaluation())
  175. logging.info("-- %s evaluation %s of %s (%s%%) - BEST SCORE %s" %
  176. (type(self).__name__, self.numberOfEvaluations,
  177. self.maxEvaluations, "{0:.2f}".format(
  178. (self.numberOfEvaluations) / self.maxEvaluations *
  179. 100.), self.bestSolution.fitness()))
  180. def end(self):
  181. """Display end message into `run` method
  182. """
  183. print(
  184. macop_text('({}) Found after {} evaluations \n - {}'.format(
  185. type(self).__name__, self.numberOfEvaluations,
  186. self.bestSolution)))
  187. print(macop_line())
  188. def information(self):
  189. logging.info("-- Best %s - SCORE %s" %
  190. (self.bestSolution, self.bestSolution.fitness()))
  191. def __str__(self):
  192. return "%s using %s" % (type(self).__name__, type(
  193. self.bestSolution).__name__)