Use a genetic algorithm to evolve populations of bit strings.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 

272 lines
5.1 KiB

  1. //
  2. #include "BitEvolver/Random.h"
  3. #include "BitEvolver/RouletteWheel.h"
  4. #include "BitEvolver/Chromosome.h"
  5. //
  6. #include <vector>
  7. #include <mutex>
  8. #include <algorithm>
  9. #include <memory>
  10. #include <iostream>
  11. //
  12. namespace BitEvolver
  13. {
  14. //
  15. using std::cout;
  16. using std::endl;
  17. //
  18. RouletteWheel::RouletteWheel()
  19. {
  20. //
  21. this->Instantiate();
  22. //
  23. this->Reset();
  24. }
  25. //
  26. void RouletteWheel::Reset()
  27. {
  28. //
  29. this->ClearChromosomes();
  30. }
  31. //
  32. void RouletteWheel::ClearChromosomes()
  33. {
  34. //
  35. std::unique_lock<std::recursive_mutex> lock(this->chromosomes_mutex);
  36. //
  37. this->chromosomes.clear();
  38. this->ChromosomesChanged();
  39. }
  40. //
  41. void RouletteWheel::SetChromosomes(std::vector<std::shared_ptr<Chromosome>> _chromosomes)
  42. {
  43. //
  44. std::unique_lock<std::recursive_mutex> lock(this->chromosomes_mutex);
  45. //
  46. this->ClearChromosomes();
  47. //
  48. this->chromosomes = _chromosomes;
  49. //
  50. this->ChromosomesChanged();
  51. }
  52. //
  53. void RouletteWheel::AddChromosome(std::shared_ptr<Chromosome> _chromosome)
  54. {
  55. //
  56. std::unique_lock<std::recursive_mutex> lock(this->chromosomes_mutex);
  57. //
  58. this->chromosomes.push_back(_chromosome);
  59. this->ChromosomesChanged();
  60. }
  61. //
  62. void RouletteWheel::AddChromosomes(std::vector<std::shared_ptr<Chromosome>> _chromosomes)
  63. {
  64. //
  65. std::unique_lock<std::recursive_mutex> lock(this->chromosomes_mutex);
  66. //
  67. for ( std::shared_ptr<Chromosome> _chromosome : _chromosomes ) {
  68. //
  69. this->chromosomes.push_back(_chromosome);
  70. }
  71. //
  72. this->ChromosomesChanged();
  73. }
  74. //
  75. std::shared_ptr<Chromosome> RouletteWheel::Spin()
  76. {
  77. //
  78. std::unique_lock<std::recursive_mutex> lock(this->chromosomes_mutex);
  79. double
  80. range_min, range_max,
  81. spin
  82. ;
  83. size_t i;
  84. //
  85. this->PopulateSlots();
  86. //
  87. if ( !this->wheel_slots.size() ) {
  88. return nullptr;
  89. }
  90. // Spin a random number in our range
  91. range_min = this->wheel_slots[0].first;
  92. range_max = this->wheel_slots[this->wheel_slots.size()-1].first;
  93. spin = this->random->GetDouble(range_min, range_max);
  94. // Find the corresponding chromosome
  95. for ( i=0; i<this->wheel_slots.size(); i++ ) {
  96. if ( this->wheel_slots[i].first >= spin ) {
  97. return this->wheel_slots[i].second;
  98. }
  99. }
  100. // By default, return the first one I guess
  101. return this->wheel_slots[0].second;
  102. }
  103. //
  104. void RouletteWheel::Instantiate()
  105. {
  106. //
  107. this->random = std::shared_ptr<Random>(
  108. new Random()
  109. );
  110. }
  111. //
  112. std::vector<std::pair<double, std::shared_ptr<Chromosome>>> RouletteWheel::GetNormalizedChromosomeFitness()
  113. {
  114. //
  115. std::unique_lock<std::recursive_mutex> lock(this->chromosomes_mutex);
  116. std::vector< std::pair< double, std::shared_ptr<Chromosome> > > pairs;
  117. std::pair< double, std::shared_ptr<Chromosome> > pair;
  118. double
  119. fitness, fitness_low, fitness_high
  120. ;
  121. //
  122. if ( !this->chromosomes.size() ) {
  123. return pairs;
  124. }
  125. // Locate lowest and highest fitness
  126. fitness_low = fitness_high = this->chromosomes[0]->GetFitness();
  127. for ( std::shared_ptr<Chromosome> chromosome : this->chromosomes ) {
  128. //
  129. fitness = chromosome->GetFitness();
  130. if ( fitness > fitness_high ) {
  131. fitness_high = fitness;
  132. }
  133. if ( fitness < fitness_low ) {
  134. fitness_low = fitness;
  135. }
  136. }
  137. // Generate normalized pairs
  138. for ( std::shared_ptr<Chromosome> chromosome : this->chromosomes ) {
  139. //
  140. pair.first = chromosome->GetFitness() - fitness_low;
  141. pair.first *= pair.first; // Square to enhance the difference a little
  142. pair.second = chromosome;
  143. //
  144. pairs.push_back(pair);
  145. //
  146. //cout << "[" << pair.first << "]" << chromosome->ToString() << endl;
  147. }
  148. return pairs;
  149. }
  150. //
  151. void RouletteWheel::SortChromosomes()
  152. {
  153. //
  154. std::unique_lock<std::recursive_mutex> lock(this->chromosomes_mutex);
  155. //
  156. if ( !this->chromosomes_need_sorting ) {
  157. return;
  158. }
  159. //
  160. std::sort(
  161. this->chromosomes.begin(),
  162. this->chromosomes.end(),
  163. []( const std::shared_ptr<Chromosome>& left, const std::shared_ptr<Chromosome>& right ) -> bool
  164. {
  165. //
  166. if ( left->GetFitness() > right->GetFitness() ) {
  167. return true;
  168. }
  169. return false;
  170. }
  171. );
  172. //
  173. this->chromosomes_need_sorting = false;
  174. }
  175. //
  176. void RouletteWheel::PopulateSlots()
  177. {
  178. //
  179. std::unique_lock<std::recursive_mutex> lock(this->chromosomes_mutex);
  180. std::vector<std::pair<double, std::shared_ptr<Chromosome>>> chromosomes_normalized_fitness;
  181. std::pair<double,std::shared_ptr<Chromosome>> wheel_slot;
  182. double
  183. slot_begin_value
  184. ;
  185. //
  186. if ( !this->slots_need_population ) {
  187. return;
  188. }
  189. //
  190. this->SortChromosomes();
  191. //
  192. this->wheel_slots.clear();
  193. //
  194. slot_begin_value = 0;
  195. chromosomes_normalized_fitness = this->GetNormalizedChromosomeFitness();
  196. for ( std::pair<double, std::shared_ptr<Chromosome>> pair: chromosomes_normalized_fitness ) {
  197. //
  198. wheel_slot.first = pair.first + slot_begin_value;
  199. wheel_slot.second = pair.second;
  200. //
  201. this->wheel_slots.push_back(wheel_slot);
  202. //
  203. slot_begin_value += pair.first;
  204. }
  205. //
  206. this->slots_need_population = false;
  207. }
  208. //
  209. void RouletteWheel::ChromosomesChanged()
  210. {
  211. //
  212. this->chromosomes_need_sorting = true;
  213. this->slots_need_population = true;
  214. }
  215. };