Use a genetic algorithm to evolve populations of bit strings.
No puede seleccionar más de 25 temas Los temas deben comenzar con una letra o número, pueden incluir guiones ('-') y pueden tener hasta 35 caracteres de largo.
 
 
 

214 líneas
4.5 KiB

  1. //
  2. #include "BitEvolver/Random.h"
  3. #include "BitEvolver/Chromosome.h"
  4. #include "BitEvolver/Breeder.h"
  5. //
  6. #include <iostream>
  7. //
  8. namespace BitEvolver
  9. {
  10. //
  11. using std::cout;
  12. using std::endl;
  13. //
  14. Breeder::Breeder(std::shared_ptr<Random> _random)
  15. {
  16. //
  17. this->random = _random;
  18. }
  19. //
  20. std::shared_ptr<Chromosome> Breeder::Breed(
  21. std::shared_ptr<Chromosome> mama,
  22. std::shared_ptr<Chromosome> papa,
  23. Enums::CrossoverType crossover_type,
  24. Enums::CrossoverOrder crossover_order,
  25. Enums::CrossoverBounds crossover_bounds,
  26. double crossover_point,
  27. double crossover_point_std,
  28. double mutation_rate
  29. )
  30. {
  31. //
  32. std::shared_ptr<Chromosome>
  33. parent_primary,
  34. parent_secondary,
  35. kiddo
  36. ;
  37. // Choose primary / secondary parents
  38. switch( crossover_order )
  39. {
  40. //
  41. case Enums::CrossoverOrder::MamaPapa:
  42. parent_primary = mama;
  43. parent_secondary = papa;
  44. break;
  45. //
  46. case Enums::CrossoverOrder::ByFitness:
  47. if ( mama->GetFitness() > papa->GetFitness() ) {
  48. parent_primary = mama;
  49. parent_secondary = papa;
  50. }
  51. else{
  52. parent_primary = papa;
  53. parent_secondary = mama;
  54. }
  55. break;
  56. }
  57. // Directly copy the primary parent first
  58. kiddo = std::shared_ptr<Chromosome>(new Chromosome(this->random, parent_primary->GetBitCount()));
  59. *kiddo = *parent_primary;
  60. // Apply crossover with the secondary parent
  61. this->ApplyCrossover(
  62. kiddo, parent_secondary,
  63. crossover_type, crossover_bounds, crossover_point, crossover_point_std
  64. );
  65. // Apply mutation
  66. this->Mutate(kiddo, mutation_rate);
  67. // Reset kiddo's fitness
  68. kiddo->ResetFitness();
  69. // Increment kiddo's generation number
  70. kiddo->IncrementGenerationNumber();
  71. return kiddo;
  72. }
  73. //
  74. void Breeder::Mutate(std::shared_ptr<Chromosome> chromosome, double mutation_rate)
  75. {
  76. //
  77. int
  78. i,
  79. size
  80. ;
  81. //
  82. size = chromosome->GetBitCount();
  83. for ( i=0; i<size; i++ ) {
  84. //
  85. if ( this->random->RollBool(mutation_rate) ) {
  86. chromosome->FlipBit(i);
  87. }
  88. }
  89. //
  90. chromosome->ResetFitness();
  91. }
  92. //
  93. int Breeder::PickRandomCrossoverPoint(
  94. std::shared_ptr<Chromosome> chromosome,
  95. Enums::CrossoverBounds crossover_bounds,
  96. double crossover_point,
  97. double crossover_point_std
  98. )
  99. {
  100. //
  101. int crossover_point_index;
  102. int bit_count;
  103. double random_double;
  104. //
  105. bit_count = chromosome->GetBitCount();
  106. /**
  107. Choose a double between [0.0,1.0] for the crossover point.
  108. Use normal distribution, with the mean and std from the parameters.
  109. That way, there is still randomness to the crossover point,
  110. but it still generally sticks near the chosen point.
  111. */
  112. random_double = this->random->GetNormal(crossover_point, crossover_point_std);
  113. // Apply to the actual int length
  114. crossover_point_index = floor(random_double * bit_count);
  115. // Loop around to keep in bounds?
  116. if ( crossover_bounds == Enums::CrossoverBounds::Wrap ) {
  117. while ( crossover_point_index < 0 )
  118. {
  119. crossover_point_index += bit_count;
  120. }
  121. while ( crossover_point_index >= bit_count)
  122. {
  123. crossover_point_index -= bit_count;
  124. }
  125. }
  126. else if ( crossover_bounds == Enums::CrossoverBounds::Clip ) {
  127. if ( crossover_point_index < 0 ) {
  128. crossover_point_index = 0;
  129. }
  130. else if ( crossover_point_index >= bit_count ) {
  131. crossover_point_index = bit_count-1;
  132. }
  133. }
  134. else{
  135. throw std::runtime_error("Breeder::PickRandomCrossoverPoint() - Invalid crossover_bounds");
  136. }
  137. return crossover_point_index;
  138. }
  139. //
  140. void Breeder::ApplyCrossover(
  141. std::shared_ptr<Chromosome> kiddo,
  142. std::shared_ptr<Chromosome> parent,
  143. Enums::CrossoverType crossover_type,
  144. Enums::CrossoverBounds crossover_bounds,
  145. double crossover_point,
  146. double crossover_point_std
  147. )
  148. {
  149. //
  150. int
  151. bits_count,
  152. crossover_point_index,
  153. i
  154. ;
  155. // Only proceed if using sexual crossover
  156. if (crossover_type != Enums::CrossoverType::Sexual) {
  157. return;
  158. }
  159. // For now, don't crossover unless the bit lengths are identical
  160. bits_count = kiddo->GetBitCount();
  161. if ( parent->GetBitCount() != bits_count ) {
  162. throw std::runtime_error("Breeder::ApplyCrossover() - Parent incompatible with Kiddo (bit lengths don't match)");
  163. }
  164. // Pick random crossover point
  165. crossover_point_index = this->PickRandomCrossoverPoint(kiddo, crossover_bounds, crossover_point, crossover_point_std);
  166. // Begin copying the parent at the crossover point and beyond
  167. // (not before)
  168. for ( i=crossover_point_index; i<bits_count; i++) {
  169. kiddo->SetBit( i, parent->GetBit(i) );
  170. }
  171. //
  172. kiddo->ResetFitness();
  173. }
  174. };