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.
 
 
 

794 line
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. };