MOEAD.py 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347
  1. """Multi-Ojective Evolutionary Algorithm with Scalar Decomposition algorithm
  2. """
  3. # main imports
  4. import pkgutil
  5. import logging
  6. import math
  7. import numpy as np
  8. import sys
  9. from ...utils.color import macop_text, macop_line, macop_progress
  10. from ...utils.modules import load_class
  11. # module imports
  12. from ..Algorithm import Algorithm
  13. from .MOSubProblem import MOSubProblem
  14. def moEvaluator(_solution, _evaluator, _weights):
  15. scores = [eval(_solution) for eval in _evaluator]
  16. # associate objectives scores to solution
  17. _solution.scores = scores
  18. return sum([scores[i] for i, w in enumerate(_weights)])
  19. class MOEAD(Algorithm):
  20. """Multi-Ojective Evolutionary Algorithm with Scalar Decomposition
  21. Attributes:
  22. mu: {int} -- number of sub problems
  23. T: {[float]} -- number of neightbors for each sub problem
  24. nObjectives: {int} -- number of objectives (based of number evaluator)
  25. initalizer: {function} -- basic function strategy to initialize solution
  26. evaluator: {[function]} -- list of basic function in order to obtained fitness (multiple objectives)
  27. operators: {[Operator]} -- list of operator to use when launching algorithm
  28. policy: {Policy} -- Policy class implementation strategy to select operators
  29. validator: {function} -- basic function to check if solution is valid or not under some constraints
  30. maximise: {bool} -- specify kind of optimization problem
  31. population: [{Solution}] -- population of solution, one for each sub problem
  32. pfPop: [{Solution}] -- pareto front population
  33. weights: [[{float}]] -- random weights used for custom mu sub problems
  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. _mu,
  38. _T,
  39. _initalizer,
  40. _evaluator,
  41. _operators,
  42. _policy,
  43. _validator,
  44. _maximise=True,
  45. _parent=None):
  46. # redefinition of constructor to well use `initRun` method
  47. self.initializer = _initalizer
  48. self.evaluator = _evaluator
  49. self.operators = _operators
  50. self.policy = _policy
  51. self.validator = _validator
  52. self.callbacks = []
  53. # by default
  54. self.numberOfEvaluations = 0
  55. self.maxEvaluations = 0
  56. self.nObjectives = len(_evaluator)
  57. # other parameters
  58. self.parent = _parent # parent algorithm if it's sub algorithm
  59. #self.maxEvaluations = 0 # by default
  60. self.maximise = _maximise
  61. # track reference of algo into operator (keep an eye into best solution)
  62. for operator in self.operators:
  63. operator.setAlgo(self)
  64. # by default track reference for policy
  65. self.policy.setAlgo(self)
  66. if _mu < _T:
  67. raise ValueError('`mu` cannot be less than `T`')
  68. self.mu = _mu
  69. self.T = _T
  70. # initialize neighbors for each sub problem
  71. self.setNeighbors()
  72. weights = []
  73. if self.nObjectives == 2:
  74. for i in range(self.mu):
  75. angle = math.pi / 2 * i / (self.mu - 1)
  76. weights.append([math.cos(angle), math.sin(angle)])
  77. elif self.nObjectives >= 3:
  78. # random weights using uniform
  79. for i in range(self.mu):
  80. w_i = np.random.uniform(0, 1, self.nObjectives)
  81. weights.append(w_i / sum(w_i))
  82. else:
  83. raise ValueError('Unvalid number of objectives')
  84. self.weights = weights
  85. self.subProblems = []
  86. for i in range(self.mu):
  87. # compute weight sum from solution
  88. sub_evaluator = lambda _solution: moEvaluator(
  89. _solution, _evaluator, weights[i])
  90. # intialize each sub problem
  91. # use copy of list to keep track for each sub problem
  92. subProblem = MOSubProblem(i, weights[i],
  93. _initalizer, sub_evaluator,
  94. _operators.copy(), _policy, _validator,
  95. _maximise, self)
  96. self.subProblems.append(subProblem)
  97. self.population = [None for n in range(self.mu)]
  98. self.pfPop = []
  99. # ref point based on number of evaluators
  100. if self.maximise:
  101. self.refPoint = [0 for _ in range(self.nObjectives)]
  102. else:
  103. self.refPoint = [
  104. sys.float_info.max for _ in range(self.nObjectives)
  105. ]
  106. def initRun(self):
  107. """
  108. Method which initialiazes or re-initializes the whole algorithm context specifically for MOEAD
  109. """
  110. # initialization is done during run method
  111. pass
  112. def run(self, _evaluations):
  113. """
  114. Run the local search algorithm
  115. Args:
  116. _evaluations: {int} -- number of Local search evaluations
  117. Returns:
  118. {Solution} -- best solution found
  119. """
  120. # by default use of mother method to initialize variables
  121. super().run(_evaluations)
  122. # enable callback resume for MOEAD
  123. self.resume()
  124. # initialize each sub problem if no backup
  125. for i in range(self.mu):
  126. if self.subProblems[i].bestSolution is None:
  127. self.subProblems[i].run(1)
  128. self.population[i] = self.subProblems[i].bestSolution
  129. # if no backup for pf population
  130. if len(self.pfPop) == 0:
  131. for i in range(self.mu):
  132. self.pfPop.append(self.subProblems[i].bestSolution)
  133. # MOEAD algorithm implementation
  134. while not self.stop():
  135. for i in range(self.mu):
  136. # run 1 iteration into sub problem `i`
  137. self.subProblems[i].run(1)
  138. spBestSolution = self.subProblems[i].bestSolution
  139. self.updateRefPoint(spBestSolution)
  140. # for each neighbor of current sub problem update solution if better
  141. improvment = False
  142. for j in self.neighbors[i]:
  143. if spBestSolution.fitness(
  144. ) > self.subProblems[j].bestSolution.fitness():
  145. # create new solution based on current new if better, computes fitness associated to new solution for sub problem
  146. class_name = type(spBestSolution).__name__
  147. # dynamically load solution class if unknown
  148. if class_name not in sys.modules:
  149. load_class(class_name, globals())
  150. newSolution = getattr(
  151. globals()['macop.solutions.' + class_name],
  152. class_name)(spBestSolution.data,
  153. len(spBestSolution.data))
  154. # evaluate solution for new sub problem and update as best solution
  155. self.subProblems[j].evaluate(newSolution)
  156. self.subProblems[j].bestSolution = newSolution
  157. # update population solution for this sub problem
  158. self.population[j] = newSolution
  159. improvment = True
  160. # add new solution if improvment is idenfity
  161. if improvment:
  162. self.pfPop.append(spBestSolution)
  163. # update pareto front
  164. self.pfPop = self.paretoFront(self.pfPop)
  165. # add progress here
  166. self.progress()
  167. # stop algorithm if necessary
  168. if self.stop():
  169. break
  170. logging.info("End of %s, best solution found %s" %
  171. (type(self).__name__, self.population))
  172. self.end()
  173. return self.pfPop
  174. def progress(self):
  175. """
  176. Log progress and apply callbacks if necessary
  177. """
  178. if len(self.callbacks) > 0:
  179. for callback in self.callbacks:
  180. callback.run()
  181. macop_progress(self.getGlobalEvaluation(),
  182. self.getGlobalMaxEvaluation())
  183. logging.info(
  184. "-- %s evaluation %s of %s (%s%%)" %
  185. (type(self).__name__, self.numberOfEvaluations,
  186. self.maxEvaluations, "{0:.2f}".format(
  187. (self.numberOfEvaluations) / self.maxEvaluations * 100.)))
  188. def setNeighbors(self):
  189. dmin = dmax = 0
  190. if self.T % 2 == 1:
  191. dmin = -int(self.T / 2)
  192. dmax = int(self.T / 2) + 1
  193. else:
  194. dmin = -int(self.T / 2) + 1
  195. dmax = +self.T / 2
  196. # init neighbord list
  197. self.neighbors = [[] for n in range(self.mu)]
  198. for direction in range(0, -dmin):
  199. for i in range(self.T):
  200. self.neighbors[direction].append(i)
  201. for direction in range(-dmin, self.mu - dmax):
  202. for i in range(direction + dmin, direction + dmax):
  203. self.neighbors[direction].append(i)
  204. for direction in range(self.mu - dmax, self.mu):
  205. for i in range(self.mu - self.T, self.mu):
  206. self.neighbors[direction].append(i)
  207. def updateRefPoint(self, _solution):
  208. if self.maximise:
  209. for i in range(len(self.evaluator)):
  210. if _solution.scores[i] > self.refPoint[i]:
  211. self.refPoint[i] = _solution.scores[i]
  212. else:
  213. for i in range(len(self.evaluator)):
  214. if _solution.scores[i] < self.refPoint[i]:
  215. self.refPoint[i] = _solution.scores[i]
  216. def paretoFront(self, _population):
  217. paFront = []
  218. indexes = []
  219. nObjectives = len(self.evaluator)
  220. nSolutions = len(_population)
  221. # find dominated solution
  222. for i in range(nSolutions):
  223. for j in range(nSolutions):
  224. if j in indexes:
  225. continue
  226. nDominated = 0
  227. # check number of dominated objectives of current solution by the others solution
  228. for k in range(len(self.evaluator)):
  229. if self.maximise:
  230. if _population[i].scores[k] < _population[j].scores[k]:
  231. nDominated += 1
  232. else:
  233. if _population[i].scores[k] > _population[j].scores[k]:
  234. nDominated += 1
  235. if nDominated == nObjectives:
  236. indexes.append(i)
  237. break
  238. # store the non dominated solution into pareto front
  239. for i in range(nSolutions):
  240. if i not in indexes:
  241. paFront.append(_population[i])
  242. return paFront
  243. def end(self):
  244. """Display end message into `run` method
  245. """
  246. print(
  247. macop_text('({}) Found after {} evaluations'.format(
  248. type(self).__name__, self.numberOfEvaluations)))
  249. for i, solution in enumerate(self.pfPop):
  250. print(' - [{}] {} : {}'.format(i, solution.scores, solution))
  251. print(macop_line())
  252. def information(self):
  253. logging.info("-- Pareto front :")
  254. for i, solution in enumerate(self.pfPop):
  255. logging.info("-- %s] SCORE %s - %s" %
  256. (i, solution.scores, solution))
  257. def __str__(self):
  258. return "%s using %s" % (type(self).__name__, type(
  259. self.population).__name__)