HillClimberBestImprovment.py 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
  1. """Hill Climber Best Improvment algorithm starting from new solution and explore using neighborhood and loop over the best one obtained from neighborhood search space
  2. """
  3. # main imports
  4. import logging
  5. # module imports
  6. from ..Algorithm import Algorithm
  7. class HillClimberBestImprovment(Algorithm):
  8. """Hill Climber Best Improvment used as exploitation optimisation algorithm
  9. This algorithm do a neighborhood exploration of a new generated solution (by doing operation on the current solution obtained) in order to find the best solution from the neighborhood space.
  10. Then replace the best solution found from the neighbordhood space as current solution to use.
  11. Do these steps until a number of evaluation (stopping criterion) is reached.
  12. Attributes:
  13. initalizer: {function} -- basic function strategy to initialize solution
  14. evaluator: {function} -- basic function in order to obtained fitness (mono or multiple objectives)
  15. operators: {[Operator]} -- list of operator to use when launching algorithm
  16. policy: {Policy} -- Policy class implementation strategy to select operators
  17. validator: {function} -- basic function to check if solution is valid or not under some constraints
  18. maximise: {bool} -- specify kind of optimisation problem
  19. currentSolution: {Solution} -- current solution managed for current evaluation
  20. bestSolution: {Solution} -- best solution found so far during running algorithm
  21. callbacks: {[Callback]} -- list of Callback class implementation to do some instructions every number of evaluations and `load` when initializing algorithm
  22. """
  23. def run(self, evaluations):
  24. """
  25. Run the local search algorithm
  26. Args:
  27. evaluations: {int} -- number of Local search evaluations
  28. Returns:
  29. {Solution} -- best solution found
  30. """
  31. # by default use of mother method to initialize variables
  32. super().run(evaluations)
  33. # initialize current solution and best solution
  34. self.initRun()
  35. solutionSize = self._currentSolution._size
  36. # local search algorithm implementation
  37. while not self.stop():
  38. for _ in range(solutionSize):
  39. # update current solution using policy
  40. newSolution = self.update(self._currentSolution)
  41. # if better solution than currently, replace it
  42. if self.isBetter(newSolution):
  43. self._bestSolution = newSolution
  44. # increase number of evaluations
  45. self.increaseEvaluation()
  46. self.progress()
  47. logging.info(f"---- Current {newSolution} - SCORE {newSolution.fitness()}")
  48. # stop algorithm if necessary
  49. if self.stop():
  50. break
  51. # set new current solution using best solution found in this neighbor search
  52. self._currentSolution = self._bestSolution
  53. logging.info(f"End of {type(self).__name__}, best solution found {self._bestSolution}")
  54. return self._bestSolution