ILSSurrogate.py 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277
  1. """Iterated Local Search Algorithm implementation using surrogate as fitness approximation
  2. """
  3. # main imports
  4. import os
  5. import logging
  6. import joblib
  7. import time
  8. # module imports
  9. from macop.algorithms.base import Algorithm
  10. from .LSSurrogate import LocalSearchSurrogate
  11. from sklearn.linear_model import (LinearRegression, Lasso, Lars, LassoLars,
  12. LassoCV, ElasticNet)
  13. from wsao.sao.problems.nd3dproblem import ND3DProblem
  14. from wsao.sao.surrogates.walsh import WalshSurrogate
  15. from wsao.sao.algos.fitter import FitterAlgo
  16. from wsao.sao.utils.analysis import SamplerAnalysis, FitterAnalysis, OptimizerAnalysis
  17. class ILSSurrogate(Algorithm):
  18. """Iterated Local Search used to avoid local optima and increave EvE (Exploration vs Exploitation) compromise using surrogate
  19. Attributes:
  20. initalizer: {function} -- basic function strategy to initialize solution
  21. evaluator: {function} -- basic function in order to obtained fitness (mono or multiple objectives)
  22. operators: {[Operator]} -- list of operator to use when launching algorithm
  23. policy: {Policy} -- Policy class implementation strategy to select operators
  24. validator: {function} -- basic function to check if solution is valid or not under some constraints
  25. maximise: {bool} -- specify kind of optimization problem
  26. currentSolution: {Solution} -- current solution managed for current evaluation
  27. bestSolution: {Solution} -- best solution found so far during running algorithm
  28. ls_iteration: {int} -- number of evaluation for each local search algorithm
  29. surrogate_file: {str} -- Surrogate model file to load (model trained using https://gitlab.com/florianlprt/wsao)
  30. start_train_surrogate: {int} -- number of evaluation expected before start training and use surrogate
  31. surrogate: {Surrogate} -- Surrogate model instance loaded
  32. ls_train_surrogate: {int} -- Specify if we need to retrain our surrogate model (every Local Search)
  33. solutions_file: {str} -- Path where real evaluated solutions are saved in order to train surrogate again
  34. callbacks: {[Callback]} -- list of Callback class implementation to do some instructions every number of evaluations and `load` when initializing algorithm
  35. """
  36. def __init__(self,
  37. initalizer,
  38. evaluator,
  39. operators,
  40. policy,
  41. validator,
  42. surrogate_file_path,
  43. start_train_surrogate,
  44. ls_train_surrogate,
  45. solutions_file,
  46. maximise=True,
  47. parent=None):
  48. # set real evaluator as default
  49. super().__init__(initalizer, evaluator, operators, policy,
  50. validator, maximise, parent)
  51. self._n_local_search = 0
  52. self._main_evaluator = evaluator
  53. self._surrogate_file_path = surrogate_file_path
  54. self._start_train_surrogate = start_train_surrogate
  55. self._surrogate_evaluator = None
  56. self._surrogate_analyser = None
  57. self._ls_train_surrogate = ls_train_surrogate
  58. self._solutions_file = solutions_file
  59. def train_surrogate(self):
  60. """Retrain if necessary the whole surrogate fitness approximation function
  61. """
  62. # Following https://gitlab.com/florianlprt/wsao, we re-train the model
  63. # ---------------------------------------------------------------------------
  64. # cli_restart.py problem=nd3d,size=30,filename="data/statistics_extended_svdn" \
  65. # model=lasso,alpha=1e-5 \
  66. # surrogate=walsh,order=3 \
  67. # algo=fitter,algo_restarts=10,samplefile=stats_extended.csv \
  68. # sample=1000,step=10 \
  69. # analysis=fitter,logfile=out_fit.csv
  70. problem = ND3DProblem(size=len(self._bestSolution._data)) # problem size based on best solution size (need to improve...)
  71. model = Lasso(alpha=1e-5)
  72. surrogate = WalshSurrogate(order=2, size=problem.size, model=model)
  73. analysis = FitterAnalysis(logfile="train_surrogate.log", problem=problem)
  74. algo = FitterAlgo(problem=problem, surrogate=surrogate, analysis=analysis, seed=problem.seed)
  75. # dynamic number of samples based on dataset real evaluations
  76. nsamples = None
  77. with open(self._solutions_file, 'r') as f:
  78. nsamples = len(f.readlines()) - 1 # avoid header
  79. training_samples = int(0.7 * nsamples) # 70% used for learning part at each iteration
  80. print("Start fitting again the surrogate model")
  81. print(f'Using {training_samples} of {nsamples} samples for train dataset')
  82. for r in range(10):
  83. print(f"Iteration n°{r}: for fitting surrogate")
  84. algo.run(samplefile=self._solutions_file, sample=training_samples, step=10)
  85. joblib.dump(algo, self._surrogate_file_path)
  86. def load_surrogate(self):
  87. """Load algorithm with surrogate model and create lambda evaluator function
  88. """
  89. # need to first train surrogate if not exist
  90. if not os.path.exists(self._surrogate_file_path):
  91. self.train_surrogate()
  92. self._surrogate = joblib.load(self._surrogate_file_path)
  93. # update evaluator function
  94. self._surrogate_evaluator = lambda s: self._surrogate.surrogate.predict([s._data])[0]
  95. def add_to_surrogate(self, solution):
  96. # save real evaluated solution into specific file for surrogate
  97. with open(self._solutions_file, 'a') as f:
  98. line = ""
  99. for index, e in enumerate(solution._data):
  100. line += str(e)
  101. if index < len(solution._data) - 1:
  102. line += ","
  103. line += ";"
  104. line += str(solution._score)
  105. f.write(line + "\n")
  106. def run(self, evaluations, ls_evaluations=100):
  107. """
  108. Run the iterated local search algorithm using local search (EvE compromise)
  109. Args:
  110. evaluations: {int} -- number of global evaluations for ILS
  111. ls_evaluations: {int} -- number of Local search evaluations (default: 100)
  112. Returns:
  113. {Solution} -- best solution found
  114. """
  115. # by default use of mother method to initialize variables
  116. super().run(evaluations)
  117. # initialize current solution
  118. self.initRun()
  119. # enable resuming for ILS
  120. self.resume()
  121. # count number of surrogate obtained and restart using real evaluations done
  122. nsamples = None
  123. with open(self._solutions_file, 'r') as f:
  124. nsamples = len(f.readlines()) - 1 # avoid header
  125. if self.getGlobalEvaluation() < nsamples:
  126. print(f'Restart using {nsamples} of {self._start_train_surrogate} real evaluations obtained')
  127. self._numberOfEvaluations = nsamples
  128. if self._start_train_surrogate > self.getGlobalEvaluation():
  129. # get `self.start_train_surrogate` number of real evaluations and save it into surrogate dataset file
  130. # using randomly generated solutions (in order to cover seearch space)
  131. while self._start_train_surrogate > self.getGlobalEvaluation():
  132. newSolution = self.initialiser()
  133. # evaluate new solution
  134. newSolution.evaluate(self.evaluator)
  135. # add it to surrogate pool
  136. self.add_to_surrogate(newSolution)
  137. self.increaseEvaluation()
  138. # train surrogate on real evaluated solutions file
  139. self.train_surrogate()
  140. self.load_surrogate()
  141. # local search algorithm implementation
  142. while not self.stop():
  143. # set current evaluator based on used or not of surrogate function
  144. self.evaluator = self._surrogate_evaluator if self._start_train_surrogate <= self.getGlobalEvaluation() else self._main_evaluator
  145. # create new local search instance
  146. # passing global evaluation param from ILS
  147. ls = LocalSearchSurrogate(self.initialiser,
  148. self.evaluator,
  149. self._operators,
  150. self.policy,
  151. self.validator,
  152. self._maximise,
  153. parent=self)
  154. # add same callbacks
  155. for callback in self._callbacks:
  156. ls.addCallback(callback)
  157. # create and search solution from local search
  158. newSolution = ls.run(ls_evaluations)
  159. # if better solution than currently, replace it (solution saved in training pool, only if surrogate process is in a second process step)
  160. # Update : always add new solution into surrogate pool, not only if solution is better
  161. #if self.isBetter(newSolution) and self.start_train_surrogate < self.getGlobalEvaluation():
  162. if self._start_train_surrogate <= self.getGlobalEvaluation():
  163. # if better solution found from local search, retrained the found solution and test again
  164. # without use of surrogate
  165. fitness_score = self._main_evaluator(newSolution)
  166. # self.increaseEvaluation() # dot not add evaluation
  167. newSolution.score = fitness_score
  168. # if solution is really better after real evaluation, then we replace
  169. if self.isBetter(newSolution):
  170. self.result = newSolution
  171. self.add_to_surrogate(newSolution)
  172. self.progress()
  173. # check using specific dynamic criteria based on r^2
  174. r_squared = self._surrogate.analysis.coefficient_of_determination(self._surrogate.surrogate)
  175. training_surrogate_every = int(r_squared * self._ls_train_surrogate)
  176. print(f"=> R^2 of surrogate is of {r_squared}. Retraining model every {training_surrogate_every} LS")
  177. # avoid issue when lauching every each local search
  178. if training_surrogate_every <= 0:
  179. training_surrogate_every = 1
  180. # check if necessary or not to train again surrogate
  181. if self._n_local_search % training_surrogate_every == 0 and self._start_train_surrogate <= self.getGlobalEvaluation():
  182. # train again surrogate on real evaluated solutions file
  183. start_training = time.time()
  184. self.train_surrogate()
  185. training_time = time.time() - start_training
  186. self._surrogate_analyser = SurrogateAnalysis(training_time, training_surrogate_every, r_squared, self.getGlobalMaxEvaluation(), self._n_local_search)
  187. # reload new surrogate function
  188. self.load_surrogate()
  189. # increase number of local search done
  190. self._n_local_search += 1
  191. self.information()
  192. logging.info(f"End of {type(self).__name__}, best solution found {self._bestSolution}")
  193. self.end()
  194. return self._bestSolution
  195. def addCallback(self, callback):
  196. """Add new callback to algorithm specifying usefull parameters
  197. Args:
  198. callback: {Callback} -- specific Callback instance
  199. """
  200. # specify current main algorithm reference
  201. if self.getParent() is not None:
  202. callback.setAlgo(self.getParent())
  203. else:
  204. callback.setAlgo(self)
  205. # set as new
  206. self._callbacks.append(callback)