crossovers.py 6.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169
  1. """Crossover implementations for discrete solutions kind
  2. """
  3. # main imports
  4. import random
  5. import sys
  6. # module imports
  7. from macop.operators.base import Crossover
  8. class SimpleCrossover(Crossover):
  9. """Crossover implementation which generated new solution by splitting at mean size best solution and current solution
  10. Attributes:
  11. kind: {:class:`~macop.algorithms.base.Algorithm`} -- specify the kind of operator
  12. Example:
  13. >>> # operators import
  14. >>> from macop.operators.discrete.crossovers import SimpleCrossover
  15. >>> from macop.operators.discrete.mutators import SimpleMutation
  16. >>>
  17. >>> # policy import
  18. >>> from macop.policies.reinforcement import UCBPolicy
  19. >>>
  20. >>> # solution and algorithm imports
  21. >>> from macop.solutions.discrete import BinarySolution
  22. >>> from macop.algorithms.mono import IteratedLocalSearch
  23. >>> from macop.algorithms.mono import HillClimberFirstImprovment
  24. >>>
  25. >>> # evaluator import
  26. >>> from macop.evaluators.discrete.mono import KnapsackEvaluator
  27. >>>
  28. >>> # evaluator initialization (worths objects passed into data)
  29. >>> worths = [ random.randint(0, 20) for i in range(10) ]
  30. >>> evaluator = KnapsackEvaluator(data={'worths': worths})
  31. >>>
  32. >>> # validator specification (based on weights of each objects)
  33. >>> weights = [ random.randint(20, 30) for i in range(10) ]
  34. >>> validator = lambda solution: True if sum([weights[i] for i, value in enumerate(solution.data) if value == 1]) < 200 else False
  35. >>>
  36. >>> # initialiser function for binary solution using specific solution size
  37. >>> initialiser = lambda x=10: BinarySolution.random(x, validator)
  38. >>>
  39. >>> # operators list with crossover and mutation
  40. >>> simple_crossover = SimpleCrossover()
  41. >>> simple_mutation = SimpleMutation()
  42. >>> operators = [simple_crossover, simple_mutation]
  43. >>> policy = UCBPolicy(operators)
  44. >>> local_search = HillClimberFirstImprovment(initialiser, evaluator, operators, policy, validator, maximise=True, verbose=False)
  45. >>> algo = IteratedLocalSearch(initialiser, evaluator, operators, policy, validator, localSearch=local_search, maximise=True, verbose=False)
  46. >>>
  47. >>> # using best solution, simple crossover is applied
  48. >>> best_solution = algo.run(100)
  49. >>> list(best_solution.data)
  50. [1, 1, 0, 1, 1, 1, 0, 1, 1, 1]
  51. >>> new_solution_1 = initialiser()
  52. >>> new_solution_2 = initialiser()
  53. >>> offspring_solution = simple_crossover.apply(new_solution_1, new_solution_2)
  54. >>> list(offspring_solution.data)
  55. [1, 0, 1, 1, 0, 0, 0, 1, 0, 0]
  56. """
  57. def apply(self, solution1, solution2=None):
  58. """Create new solution based on best solution found and solution passed as parameter
  59. Args:
  60. solution1: {:class:`~macop.solutions.base.Solution`} -- the first solution to use for generating new solution
  61. solution2: {:class:`~macop.solutions.base.Solution`} -- the second solution to use for generating new solution
  62. Returns:
  63. {:class:`~macop.solutions.base.Solution`}: new generated solution
  64. """
  65. size = solution1.size
  66. # copy data of solution
  67. firstData = solution1.data.copy()
  68. # copy of solution2 as output solution
  69. copy_solution = solution2.clone()
  70. splitIndex = int(size / 2)
  71. if random.uniform(0, 1) > 0.5:
  72. copy_solution.data[splitIndex:] = firstData[splitIndex:]
  73. else:
  74. copy_solution.data[:splitIndex] = firstData[:splitIndex]
  75. return copy_solution
  76. class RandomSplitCrossover(Crossover):
  77. """Crossover implementation which generated new solution by randomly splitting best solution and current solution
  78. Attributes:
  79. kind: {:class:`~macop.operators.base.KindOperator`} -- specify the kind of operator
  80. Example:
  81. >>> # operators import
  82. >>> from macop.operators.discrete.crossovers import RandomSplitCrossover
  83. >>> from macop.operators.discrete.mutators import SimpleMutation
  84. >>>
  85. >>> # policy import
  86. >>> from macop.policies.reinforcement import UCBPolicy
  87. >>>
  88. >>> # solution and algorithm imports
  89. >>> from macop.solutions.discrete import BinarySolution
  90. >>> from macop.algorithms.mono import IteratedLocalSearch
  91. >>> from macop.algorithms.mono import HillClimberFirstImprovment
  92. >>>
  93. >>> # evaluator import
  94. >>> from macop.evaluators.discrete.mono import KnapsackEvaluator
  95. >>>
  96. >>> # evaluator initialization (worths objects passed into data)
  97. >>> worths = [ random.randint(0, 20) for i in range(10) ]
  98. >>> evaluator = KnapsackEvaluator(data={'worths': worths})
  99. >>>
  100. >>> # validator specification (based on weights of each objects)
  101. >>> weights = [ random.randint(20, 30) for i in range(10) ]
  102. >>> validator = lambda solution: True if sum([weights[i] for i, value in enumerate(solution.data) if value == 1]) < 200 else False
  103. >>>
  104. >>> # initialiser function for binary solution using specific solution size
  105. >>> initialiser = lambda x=10: BinarySolution.random(x, validator)
  106. >>>
  107. >>> # operators list with crossover and mutation
  108. >>> random_split_crossover = RandomSplitCrossover()
  109. >>> simple_mutation = SimpleMutation()
  110. >>> operators = [random_split_crossover, simple_mutation]
  111. >>> policy = UCBPolicy(operators)
  112. >>> local_search = HillClimberFirstImprovment(initialiser, evaluator, operators, policy, validator, maximise=True, verbose=False)
  113. >>> algo = IteratedLocalSearch(initialiser, evaluator, operators, policy, validator, localSearch=local_search, maximise=True, verbose=False)
  114. >>>
  115. >>> # using best solution, simple crossover is applied
  116. >>> best_solution = algo.run(100)
  117. >>> list(best_solution.data)
  118. [1, 1, 1, 1, 1, 0, 1, 1, 0, 0]
  119. >>> new_solution_1 = initialiser()
  120. >>> new_solution_2 = initialiser()
  121. >>> offspring_solution = random_split_crossover.apply(new_solution_1, new_solution_2)
  122. >>> list(offspring_solution.data)
  123. [0, 0, 0, 1, 1, 1, 1, 0, 0, 1]
  124. """
  125. def apply(self, solution1, solution2=None):
  126. """Create new solution based on best solution found and solution passed as parameter
  127. Args:
  128. solution1: {:class:`~macop.solutions.base.Solution`} -- the first solution to use for generating new solution
  129. solution2: {:class:`~macop.solutions.base.Solution`} -- the second solution to use for generating new solution
  130. Returns:
  131. {:class:`~macop.solutions.base.Solution`}: new generated solution
  132. """
  133. size = solution1.size
  134. # copy data of solution
  135. firstData = solution1.data.copy()
  136. # copy of solution2 as output solution
  137. copy_solution = solution2.clone()
  138. splitIndex = random.randint(0, size)
  139. if random.uniform(0, 1) > 0.5:
  140. copy_solution.data[splitIndex:] = firstData[splitIndex:]
  141. else:
  142. copy_solution.data[:splitIndex] = firstData[:splitIndex]
  143. return copy_solution