Use a genetic algorithm to evolve populations of bit strings.
Vous ne pouvez pas sélectionner plus de 25 sujets Les noms de sujets doivent commencer par une lettre ou un nombre, peuvent contenir des tirets ('-') et peuvent comporter jusqu'à 35 caractères.
 
 
 

794 lignes
16 KiB

  1. //
  2. #include "BitEvolver/Includes.h"
  3. #include "BitEvolver/Random.h"
  4. #include "BitEvolver/Population.h"
  5. #include "BitEvolver/Breeder.h"
  6. #include "BitEvolver/RouletteWheel.h"
  7. #include "BitEvolver/Chromosome.h"
  8. //
  9. #include <memory>
  10. #include <vector>
  11. #include <mutex>
  12. #include <iostream>
  13. #include <algorithm>
  14. #include <thread>
  15. #include <functional>
  16. #include <string>
  17. #include <sstream>
  18. //
  19. namespace BitEvolver
  20. {
  21. //
  22. using std::string;
  23. using std::stringstream;
  24. using std::cout;
  25. using std::endl;
  26. //
  27. Population::Population()
  28. {
  29. //
  30. this->InitRandomGenerator();
  31. this->InitRouletteWheel();
  32. this->InitBreeder();
  33. //
  34. this->Reset();
  35. }
  36. //
  37. void Population::Reset()
  38. {
  39. //
  40. this->evolution_number = 0;
  41. this->population_size = Population::DEFAULT_POPULATION_SIZE;
  42. //
  43. this->SetElitismType(Population::DEFAULT_ELITISM_TYPE);
  44. this->SetElitismRate(Population::DEFAULT_ELITISM_RATE);
  45. this->SetElitismCount(Population::DEFAULT_ELITISM_COUNT);
  46. //
  47. this->SetCrossoverType(Population::DEFAULT_CROSSOVER_TYPE);
  48. this->SetCrossoverOrder(Population::DEFAULT_CROSSOVER_ORDER);
  49. this->SetCrossoverBounds(Population::DEFAULT_CROSSOVER_BOUNDS);
  50. this->SetCrossoverPoint(Population::DEFAULT_CROSSOVER_POINT);
  51. this->SetCrossoverPointStandardDeviation(Population::DEFAULT_CROSSOVER_POINT_STD);
  52. //
  53. this->SetMutationRate(Population::DEFAULT_MUTATION_RATE);
  54. //
  55. this->RandomizePopulation(this->population_size);
  56. }
  57. //
  58. void Population::ClearPopulation()
  59. {
  60. //
  61. this->chromosomes.clear();
  62. this->evolution_number = 0;
  63. }
  64. //
  65. void Population::InitRandomPopulation(int _population_size, int _bit_length)
  66. {
  67. //
  68. this->population_size = _population_size;
  69. //
  70. this->RandomizePopulation(_bit_length);
  71. }
  72. //
  73. void Population::RandomizePopulation(int _bit_length)
  74. {
  75. //
  76. std::shared_ptr<Chromosome> chromosome;
  77. int i;
  78. //
  79. this->ClearPopulation();
  80. for ( i=0; i<this->population_size; i++ ) {
  81. //
  82. chromosome = std::shared_ptr<Chromosome>(
  83. new Chromosome( this->random, _bit_length )
  84. );
  85. this->chromosomes.push_back(chromosome);
  86. }
  87. }
  88. //
  89. void Population::PopulationChanged()
  90. {
  91. //
  92. this->population_needs_sorting = true;
  93. }
  94. //
  95. std::vector<std::shared_ptr<Chromosome>> Population::GetChromosomes()
  96. {
  97. return this->chromosomes;
  98. }
  99. //
  100. void Population::GetChromosomes(std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes)
  101. {
  102. //
  103. _chromosomes->clear();
  104. for ( std::shared_ptr<Chromosome> chromosome : this->chromosomes) {
  105. _chromosomes->push_back(chromosome);
  106. }
  107. }
  108. //
  109. std::shared_ptr<Chromosome> Population::GetChampion()
  110. {
  111. //
  112. this->EnsureSortedPopulation();
  113. //
  114. if ( this->chromosomes.size() > 0 ) {
  115. return this->chromosomes[0];
  116. }
  117. return nullptr;
  118. }
  119. //
  120. double Population::GetAverageFitness()
  121. {
  122. return this->GetAverageFitness(this->chromosomes);
  123. }
  124. //
  125. double Population::GetAverageFitness(std::vector<std::shared_ptr<Chromosome>> _chromosomes)
  126. {
  127. //
  128. double fitness_sum;
  129. double fitness_average;
  130. //
  131. fitness_sum = 0;
  132. for ( std::shared_ptr<Chromosome> chromosome : _chromosomes ) {
  133. fitness_sum += chromosome->GetFitness();
  134. }
  135. //
  136. fitness_average = 0;
  137. if ( _chromosomes.size() > 0 ) {
  138. fitness_average = fitness_sum / _chromosomes.size();
  139. }
  140. return fitness_average;
  141. }
  142. //
  143. void Population::SetCrossoverType(Enums::CrossoverType t)
  144. {
  145. //
  146. this->crossover_type = t;
  147. }
  148. //
  149. Enums::CrossoverType Population::GetCrossoverType()
  150. {
  151. //
  152. return this->crossover_type;
  153. }
  154. //
  155. void Population::SetCrossoverOrder(Enums::CrossoverOrder o)
  156. {
  157. //
  158. this->crossover_order = o;
  159. }
  160. //
  161. Enums::CrossoverOrder Population::GetCrossoverOrder()
  162. {
  163. //
  164. return this->crossover_order;
  165. }
  166. //
  167. void Population::SetCrossoverBounds(Enums::CrossoverBounds b)
  168. {
  169. //
  170. this->crossover_bounds = b;
  171. }
  172. //
  173. Enums::CrossoverBounds Population::GetCrossoverBounds()
  174. {
  175. //
  176. return this->crossover_bounds;
  177. }
  178. //
  179. void Population::SetCrossoverPoint(double p)
  180. {
  181. //
  182. this->crossover_point = p;
  183. }
  184. //
  185. double Population::GetCrossoverPoint()
  186. {
  187. //
  188. return this->crossover_point;
  189. }
  190. //
  191. void Population::SetCrossoverPointStandardDeviation(double std)
  192. {
  193. //
  194. this->crossover_point_std = std;
  195. }
  196. //
  197. double Population::GetCrossoverPointStandardDeviation()
  198. {
  199. //
  200. return this->crossover_point_std;
  201. }
  202. //
  203. void Population::SetMutationRate(double r)
  204. {
  205. //
  206. this->mutation_rate = r;
  207. }
  208. //
  209. double Population::GetMutationRate()
  210. {
  211. //
  212. return this->mutation_rate;
  213. }
  214. //
  215. void Population::SetElitismType(Enums::ElitismType t)
  216. {
  217. //
  218. this->elitism_type = t;
  219. }
  220. //
  221. Enums::ElitismType Population::GetElitismType()
  222. {
  223. //
  224. return this->elitism_type;
  225. }
  226. //
  227. void Population::SetElitismRate(double r)
  228. {
  229. //
  230. this->elitism_rate = r;
  231. }
  232. //
  233. double Population::GetElitismRate()
  234. {
  235. //
  236. return this->elitism_rate;
  237. }
  238. //
  239. void Population::SetElitismCount(int c)
  240. {
  241. //
  242. this->elitism_count = c;
  243. }
  244. //
  245. int Population::GetElitismCount()
  246. {
  247. //
  248. return this->elitism_count;
  249. }
  250. //
  251. void Population::EvaluateFitness(std::function<double(std::shared_ptr<Chromosome>)> evaluation_callback)
  252. {
  253. //
  254. std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_copy;
  255. std::vector<std::shared_ptr<std::thread>> threads;
  256. std::shared_ptr<std::thread> thread;
  257. int
  258. threads_count,
  259. i
  260. ;
  261. // Make a new vector containing all current chromosomes
  262. this->population_modification_mutex.lock();
  263. _chromosomes_copy = std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>>(
  264. new std::vector<std::shared_ptr<Chromosome>>()
  265. );
  266. for ( i=0; i<(int)this->chromosomes.size(); i++ ) {
  267. _chromosomes_copy->push_back( this->chromosomes[i] );
  268. }
  269. this->population_modification_mutex.unlock();
  270. // Spawn threads
  271. threads_count = this->GetThreadCountSuggestion();
  272. for ( i=0; i<threads_count; i++) {
  273. //
  274. thread = std::shared_ptr<std::thread>(
  275. new std::thread(&Population::EvaluateFitness_Thread, this, _chromosomes_copy, evaluation_callback)
  276. );
  277. threads.push_back(thread);
  278. }
  279. // Wait for threads to finish
  280. for ( i=0; i<threads_count; i++ ) {
  281. threads[i]->join();
  282. }
  283. }
  284. //
  285. void Population::EvaluateError(std::function<double(std::shared_ptr<Chromosome>)> evaluation_callback)
  286. {
  287. //
  288. std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_copy;
  289. std::vector<std::shared_ptr<std::thread>> threads;
  290. std::shared_ptr<std::thread> thread;
  291. int
  292. threads_count,
  293. i
  294. ;
  295. // Make a new vector containing all current chromosomes
  296. this->population_modification_mutex.lock();
  297. _chromosomes_copy = std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>>(
  298. new std::vector<std::shared_ptr<Chromosome>>()
  299. );
  300. for ( i=0; i<(int)this->chromosomes.size(); i++ ) {
  301. _chromosomes_copy->push_back( this->chromosomes[i] );
  302. }
  303. this->population_modification_mutex.unlock();
  304. // Spawn threads
  305. threads_count = this->GetThreadCountSuggestion();
  306. for ( i=0; i<threads_count; i++) {
  307. //
  308. thread = std::shared_ptr<std::thread>(
  309. new std::thread(&Population::EvaluateError_Thread, this, _chromosomes_copy, evaluation_callback)
  310. );
  311. threads.push_back(thread);
  312. }
  313. // Wait for threads to finish
  314. for ( i=0; i<threads_count; i++ ) {
  315. threads[i]->join();
  316. }
  317. }
  318. //
  319. void Population::Evolve()
  320. {
  321. //
  322. std::shared_ptr<std::vector< std::shared_ptr<Chromosome> > > population_new;
  323. //
  324. if ( this->chromosomes.size() == 0 ) {
  325. return;
  326. }
  327. //
  328. this->EnsureSortedPopulation();
  329. //
  330. population_new = std::shared_ptr<
  331. std::vector<
  332. std::shared_ptr<Chromosome>
  333. >
  334. >(
  335. new std::vector<std::shared_ptr<Chromosome>>()
  336. );
  337. // Breed the new population
  338. this->BreedNewPopulation(population_new, (int)this->chromosomes.size());
  339. // Replace old population with the new
  340. this->chromosomes = *population_new;
  341. this->evolution_number++;
  342. //
  343. this->PopulationChanged();
  344. }
  345. //
  346. int Population::GetEvolutionNumber()
  347. {
  348. return this->evolution_number;
  349. }
  350. //
  351. void Population::PrintPopulation()
  352. {
  353. //
  354. this->EnsureSortedPopulation();
  355. this->PrintPopulation(this->chromosomes);
  356. }
  357. //
  358. void Population::PrintPopulation(std::vector<std::shared_ptr<Chromosome>> _chromosomes)
  359. {
  360. //
  361. for ( std::shared_ptr<Chromosome> chromosome : chromosomes ) {
  362. cout << chromosome->ToString() << endl;
  363. }
  364. cout << "Average Fitness --> " << this->GetAverageFitness(_chromosomes) << endl;
  365. }
  366. //
  367. void Population::InitRandomGenerator()
  368. {
  369. //
  370. this->random = std::shared_ptr<Random>(
  371. new Random()
  372. );
  373. }
  374. //
  375. void Population::InitRouletteWheel()
  376. {
  377. //
  378. this->roulette_wheel = std::shared_ptr<RouletteWheel>(
  379. new RouletteWheel()
  380. );
  381. }
  382. //
  383. void Population::InitBreeder()
  384. {
  385. //
  386. if ( !this->random ) {
  387. throw std::runtime_error("Population::InitBreeder() - Should come after InitRandomGenerator()");
  388. }
  389. //
  390. this->breeder = std::shared_ptr<Breeder>(
  391. new Breeder( this->random )
  392. );
  393. }
  394. //
  395. void Population::EnsureSortedPopulation()
  396. {
  397. //
  398. if ( !this->population_needs_sorting ) {
  399. return;
  400. }
  401. // Yay std::sort
  402. std::sort(
  403. this->chromosomes.begin(),
  404. this->chromosomes.end(),
  405. []( std::shared_ptr<Chromosome>& left, std::shared_ptr<Chromosome>& right ) -> bool
  406. {
  407. //
  408. if ( left->GetFitness() > right->GetFitness() ) {
  409. return true;
  410. }
  411. return false;
  412. }
  413. );
  414. //
  415. this->population_needs_sorting = false;
  416. }
  417. //
  418. void Population::BreedNewPopulation(std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> population_new, int size)
  419. {
  420. //
  421. std::vector<std::shared_ptr<std::thread>> threads;
  422. std::shared_ptr<std::thread> thread;
  423. int
  424. thread_count,
  425. i
  426. ;
  427. // First, populate the roulette wheel
  428. this->roulette_wheel->SetChromosomes(this->chromosomes);
  429. // Next, seed the population with elites
  430. this->SeedPopulationWithElites(population_new);
  431. // Next, breed until we've reached our new size
  432. thread_count = this->GetThreadCountSuggestion();
  433. for ( i=0; i<thread_count; i++) {
  434. thread = std::shared_ptr<std::thread>(
  435. new std::thread(&Population::BreedNewPopulation_Thread, this, population_new, size)
  436. );
  437. threads.push_back(thread);
  438. }
  439. for ( i=0; i<(int)threads.size(); i++) {
  440. threads[i]->join();
  441. }
  442. // Finally, reset the fitness of the new population
  443. for ( i=0; i<(int)population_new->size(); i++ ) {
  444. population_new->at(i)->ResetFitness();
  445. }
  446. }
  447. //
  448. void Population::BreedNewPopulation_Thread(std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> population_new, int size)
  449. {
  450. //
  451. std::shared_ptr<Chromosome> kiddo;
  452. //
  453. while ( (int)population_new->size() < size )
  454. {
  455. //
  456. kiddo = this->BreedChild();
  457. // Mutexed
  458. this->breed_mutex.lock();
  459. if ( (int)population_new->size() < size ) {
  460. population_new->push_back(kiddo);
  461. }
  462. this->breed_mutex.unlock();
  463. }
  464. }
  465. //
  466. int Population::DetermineEliteCount()
  467. {
  468. //
  469. int count;
  470. //
  471. switch( this->elitism_type )
  472. {
  473. //
  474. default:
  475. case Enums::ElitismType::None:
  476. count = 0;
  477. break;
  478. //
  479. case Enums::ElitismType::Absolute:
  480. count = this->elitism_count;
  481. break;
  482. //
  483. case Enums::ElitismType::Rate:
  484. count = floor( this->chromosomes.size() * this->elitism_rate );
  485. break;
  486. }
  487. return count;
  488. }
  489. //
  490. void Population::SeedPopulationWithElites(std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> population_new)
  491. {
  492. //
  493. std::unique_lock<std::recursive_mutex> lock(this->population_modification_mutex);
  494. std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> elites;
  495. std::vector<std::shared_ptr<std::thread>> threads;
  496. std::shared_ptr<std::thread> thread;
  497. int
  498. elites_count,
  499. i
  500. ;
  501. // Determine how many elites to copy
  502. elites_count = this->DetermineEliteCount();
  503. elites = std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>>(
  504. new std::vector<std::shared_ptr<Chromosome>>()
  505. );
  506. // First, copy over just the pointers
  507. for ( i=0; i<elites_count && i<(int)this->chromosomes.size(); i++) {
  508. elites->push_back( this->chromosomes[i] );
  509. }
  510. // Then, make them full copies (uses threads)
  511. this->CopyChromosomes(elites, population_new);
  512. }
  513. //
  514. void Population::EvaluateFitness_Thread(
  515. std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes,
  516. std::function<double(std::shared_ptr<Chromosome>)> evaluation_callback
  517. )
  518. {
  519. //
  520. std::shared_ptr<Chromosome> chromosome;
  521. double fitness;
  522. //
  523. while (true)
  524. {
  525. // Grab a free chromosome
  526. this->evaluate_fitness_mutex.lock();
  527. chromosome = nullptr;
  528. if ( _chromosomes->size() ) {
  529. chromosome = _chromosomes->at(_chromosomes->size()-1);
  530. _chromosomes->pop_back();
  531. }
  532. this->evaluate_fitness_mutex.unlock();
  533. // Call the evaluation callback
  534. if ( chromosome != nullptr ) {
  535. fitness = evaluation_callback(chromosome);
  536. chromosome->SetFitness(fitness);
  537. }
  538. // We're done if there was nothing to grab
  539. else{
  540. break;
  541. }
  542. }
  543. }
  544. //
  545. void Population::EvaluateError_Thread(
  546. std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes,
  547. std::function<double(std::shared_ptr<Chromosome>)> evaluation_callback
  548. )
  549. {
  550. //
  551. std::shared_ptr<Chromosome> chromosome;
  552. double error;
  553. //
  554. while (true)
  555. {
  556. // Grab a free chromosome
  557. this->evaluate_fitness_mutex.lock();
  558. chromosome = nullptr;
  559. if ( _chromosomes->size() ) {
  560. chromosome = _chromosomes->at(_chromosomes->size()-1);
  561. _chromosomes->pop_back();
  562. }
  563. this->evaluate_fitness_mutex.unlock();
  564. // Call the evaluation callback
  565. if ( chromosome != nullptr ) {
  566. error = evaluation_callback(chromosome);
  567. chromosome->SetError(error);
  568. }
  569. // We're done if there was nothing to grab
  570. else{
  571. break;
  572. }
  573. }
  574. }
  575. //
  576. void Population::CopyChromosomes(
  577. std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_source,
  578. std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_destination
  579. )
  580. {
  581. //
  582. std::vector<std::shared_ptr<std::thread>> threads;
  583. std::shared_ptr<std::thread> thread;
  584. int
  585. threads_count,
  586. i
  587. ;
  588. // Spawn threads
  589. threads_count = this->GetThreadCountSuggestion();
  590. for ( i=0; i<threads_count; i++) {
  591. //
  592. thread = std::shared_ptr<std::thread>(
  593. new std::thread(&Population::CopyChromosomes_Thread, this, _chromosomes_source, _chromosomes_destination)
  594. );
  595. threads.push_back(thread);
  596. }
  597. // Wait for threads to finish
  598. for ( i=0; i<threads_count; i++ ) {
  599. threads[i]->join();
  600. }
  601. }
  602. //
  603. void Population::CopyChromosomes_Thread(
  604. std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_source,
  605. std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_destination
  606. )
  607. {
  608. //
  609. std::shared_ptr<Chromosome>
  610. chromosome_original,
  611. chromosome_copied
  612. ;
  613. stringstream ss;
  614. //
  615. while ( _chromosomes_destination->size() < _chromosomes_source->size() )
  616. {
  617. // Grab the next slot
  618. this->copy_chromosomes_mutex.lock();
  619. chromosome_original = nullptr;
  620. chromosome_copied = nullptr;
  621. if ( _chromosomes_destination->size() < _chromosomes_source->size() ) {
  622. //
  623. chromosome_copied = std::shared_ptr<Chromosome>(
  624. new Chromosome(this->random, 0)
  625. );
  626. _chromosomes_destination->push_back(chromosome_copied);
  627. chromosome_original = _chromosomes_source->at(_chromosomes_destination->size()-1);
  628. }
  629. this->copy_chromosomes_mutex.unlock();
  630. // Make a full copy of the original, outside the lock
  631. if ( chromosome_copied && chromosome_original ) {
  632. *chromosome_copied = *chromosome_original;
  633. }
  634. }
  635. }
  636. //
  637. std::shared_ptr<Chromosome> Population::BreedChild()
  638. {
  639. //
  640. std::shared_ptr<Chromosome>
  641. mama, papa, kiddo
  642. ;
  643. // Pick two parents
  644. mama = this->roulette_wheel->Spin();
  645. papa = this->roulette_wheel->Spin();
  646. //
  647. kiddo = this->breeder->Breed(
  648. mama, papa,
  649. this->crossover_type,
  650. this->crossover_order,
  651. this->crossover_bounds,
  652. this->crossover_point,
  653. this->crossover_point_std,
  654. this->mutation_rate
  655. );
  656. return kiddo;
  657. }
  658. //
  659. int Population::GetThreadCountSuggestion()
  660. {
  661. //
  662. int thread_count;
  663. //
  664. thread_count = std::thread::hardware_concurrency();
  665. return thread_count;
  666. }
  667. };