ILSSurrogate.py 11 KB

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