reinforcement.py 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144
  1. """Reinforcement learning policy classes implementations for Operator Selection Strategy
  2. """
  3. # main imports
  4. import logging
  5. import random
  6. import math
  7. import numpy as np
  8. # module imports
  9. from .base import Policy
  10. class UCBPolicy(Policy):
  11. """Upper Confidence Bound (UCB) policy class which is used for applying UCB strategy when selecting and applying operator
  12. Rather than performing exploration by simply selecting an arbitrary action, chosen with a probability that remains constant,
  13. the UCB algorithm changes its exploration-exploitation balance as it gathers more knowledge of the environment.
  14. It moves from being primarily focused on exploration, when actions that have been tried the least are preferred,
  15. to instead concentrate on exploitation, selecting the action with the highest estimated reward.
  16. - Resource link: https://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm/
  17. Attributes:
  18. operators: {[Operator]} -- list of selected operators for the algorithm
  19. C: {float} -- The second half of the UCB equation adds exploration, with the degree of exploration being controlled by the hyper-parameter `C`.
  20. exp_rate: {float} -- exploration rate (probability to choose randomly next operator)
  21. rewards: {[float]} -- list of summed rewards obtained for each operator
  22. occurrences: {[int]} -- number of use (selected) of each operator
  23. Example:
  24. >>> # operators import
  25. >>> from macop.operators.discrete.crossovers import SimpleCrossover
  26. >>> from macop.operators.discrete.mutators import SimpleMutation
  27. >>> # policy import
  28. >>> from macop.policies.reinforcement import UCBPolicy
  29. >>> # solution and algorithm
  30. >>> from macop.solutions.discrete import BinarySolution
  31. >>> from macop.algorithms.mono import IteratedLocalSearch
  32. >>> # evaluator import
  33. >>> from macop.evaluators.discrete.mono import KnapsackEvaluator
  34. >>> # evaluator initialization (worths objects passed into data)
  35. >>> worths = [ random.randint(0, 20) for i in range(20) ]
  36. >>> evaluator = KnapsackEvaluator(data={'worths': worths})
  37. >>> # validator specification (based on weights of each objects)
  38. >>> weights = [ random.randint(5, 30) for i in range(20) ]
  39. >>> validator = lambda solution: True if sum([weights[i] for i, value in enumerate(solution._data) if value == 1]) < 200 else False
  40. >>> # initializer function with lambda function
  41. >>> initializer = lambda x=20: BinarySolution.random(x, validator)
  42. >>> # operators list with crossover and mutation
  43. >>> operators = [SimpleCrossover(), SimpleMutation()]
  44. >>> policy = UCBPolicy(operators)
  45. >>> algo = IteratedLocalSearch(initializer, evaluator, operators, policy, validator, maximise=True, verbose=False)
  46. >>> policy._occurences
  47. [0, 0]
  48. >>> solution = algo.run(100)
  49. >>> type(solution).__name__
  50. 'BinarySolution'
  51. >>> policy._occurences # one more due to first evaluation
  52. [51, 53]
  53. """
  54. def __init__(self, operators, C=100., exp_rate=0.5):
  55. self._operators = operators
  56. self._rewards = [0. for o in self._operators]
  57. self._occurences = [0 for o in self._operators]
  58. self._C = C
  59. self._exp_rate = exp_rate
  60. def select(self):
  61. """Select using Upper Confidence Bound the next operator to use (using acquired rewards)
  62. Returns:
  63. {Operator}: the selected operator
  64. """
  65. indices = [i for i, o in enumerate(self._occurences) if o == 0]
  66. # random choice following exploration rate
  67. if np.random.uniform(0, 1) <= self._exp_rate:
  68. index = random.choice(range(len(self._operators)))
  69. return self._operators[index]
  70. elif len(indices) == 0:
  71. # if operator have at least be used one time
  72. ucbValues = []
  73. nVisits = sum(self._occurences)
  74. for i in range(len(self._operators)):
  75. ucbValue = self._rewards[i] + self._C * math.sqrt(
  76. math.log(nVisits) / (self._occurences[i] + 0.1))
  77. ucbValues.append(ucbValue)
  78. return self._operators[ucbValues.index(max(ucbValues))]
  79. else:
  80. return self._operators[random.choice(indices)]
  81. def apply(self, solution):
  82. """
  83. Apply specific operator chosen to create new solution, computes its fitness and returns solution
  84. - fitness improvment is saved as rewards
  85. - selected operator occurence is also increased
  86. Args:
  87. solution: {Solution} -- the solution to use for generating new solution
  88. Returns:
  89. {Solution} -- new generated solution
  90. """
  91. operator = self.select()
  92. logging.info("---- Applying %s on %s" %
  93. (type(operator).__name__, solution))
  94. # apply operator on solution
  95. newSolution = operator.apply(solution)
  96. # compute fitness of new solution
  97. newSolution.evaluate(self._algo._evaluator)
  98. # compute fitness improvment rate
  99. if self._algo._maximise:
  100. fir = (newSolution.fitness() -
  101. solution.fitness()) / solution.fitness()
  102. else:
  103. fir = (solution.fitness() -
  104. newSolution.fitness()) / solution.fitness()
  105. operator_index = self._operators.index(operator)
  106. if fir > 0:
  107. self._rewards[operator_index] += fir
  108. self._occurences[operator_index] += 1
  109. logging.info("---- Obtaining %s" % (solution))
  110. return newSolution