IteratedLocalSearch.py 3.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
  1. """Iterated Local Search Algorithm implementation
  2. """
  3. # main imports
  4. import logging
  5. # module imports
  6. from ..Algorithm import Algorithm
  7. from .LocalSearch import LocalSearch
  8. class IteratedLocalSearch(Algorithm):
  9. """Iterated Local Search used to avoid local optima and increave EvE (Exploration vs Exploitation) compromise
  10. Attributes:
  11. initalizer: {function} -- basic function strategy to initialize solution
  12. evaluator: {function} -- basic function in order to obtained fitness (mono or multiple objectives)
  13. operators: {[Operator]} -- list of operator to use when launching algorithm
  14. policy: {Policy} -- Policy class implementation strategy to select operators
  15. validator: {function} -- basic function to check if solution is valid or not under some constraints
  16. maximise: {bool} -- specify kind of optimization problem
  17. currentSolution: {Solution} -- current solution managed for current evaluation
  18. bestSolution: {Solution} -- best solution found so far during running algorithm
  19. callbacks: {[Callback]} -- list of Callback class implementation to do some instructions every number of evaluations and `load` when initializing algorithm
  20. """
  21. def run(self, _evaluations, _ls_evaluations=100):
  22. """
  23. Run the iterated local search algorithm using local search (EvE compromise)
  24. Args:
  25. _evaluations: {int} -- number of global evaluations for ILS
  26. _ls_evaluations: {int} -- number of Local search evaluations (default: 100)
  27. Returns:
  28. {Solution} -- best solution found
  29. """
  30. # by default use of mother method to initialize variables
  31. super().run(_evaluations)
  32. # enable resuming for ILS
  33. self.resume()
  34. # initialize current solution
  35. self.initRun()
  36. # passing global evaluation param from ILS
  37. ls = LocalSearch(self.initializer,
  38. self.evaluator,
  39. self.operators,
  40. self.policy,
  41. self.validator,
  42. self.maximise,
  43. _parent=self)
  44. # add same callbacks
  45. for callback in self.callbacks:
  46. ls.addCallback(callback)
  47. # local search algorithm implementation
  48. while not self.stop():
  49. # create and search solution from local search
  50. newSolution = ls.run(_ls_evaluations)
  51. # if better solution than currently, replace it
  52. if self.isBetter(newSolution):
  53. self.bestSolution = newSolution
  54. # number of evaluatins increased from LocalSearch
  55. # increase number of evaluations and progress are then not necessary there
  56. #self.increaseEvaluation()
  57. #self.progress()
  58. self.information()
  59. logging.info("End of %s, best solution found %s" %
  60. (type(self).__name__, self.bestSolution))
  61. self.end()
  62. return self.bestSolution