|
|
-
-
- //
- #include "BitEvolver/Includes.h"
- #include "BitEvolver/Random.h"
- #include "BitEvolver/Population.h"
- #include "BitEvolver/Breeder.h"
- #include "BitEvolver/RouletteWheel.h"
- #include "BitEvolver/Chromosome.h"
-
-
- //
- #include <memory>
- #include <vector>
- #include <mutex>
- #include <iostream>
- #include <algorithm>
- #include <thread>
- #include <functional>
- #include <string>
- #include <sstream>
-
-
- //
- namespace BitEvolver
- {
- //
- using std::string;
- using std::stringstream;
- using std::cout;
- using std::endl;
-
- //
- Population::Population()
- {
- //
- this->InitRandomGenerator();
- this->InitRouletteWheel();
- this->InitBreeder();
-
- //
- this->Reset();
- }
-
- //
- void Population::Reset()
- {
- //
- this->evolution_number = 0;
- this->population_size = Population::DEFAULT_POPULATION_SIZE;
-
- //
- this->SetElitismType(Population::DEFAULT_ELITISM_TYPE);
- this->SetElitismRate(Population::DEFAULT_ELITISM_RATE);
- this->SetElitismCount(Population::DEFAULT_ELITISM_COUNT);
-
- //
- this->SetCrossoverType(Population::DEFAULT_CROSSOVER_TYPE);
- this->SetCrossoverOrder(Population::DEFAULT_CROSSOVER_ORDER);
- this->SetCrossoverBounds(Population::DEFAULT_CROSSOVER_BOUNDS);
- this->SetCrossoverPoint(Population::DEFAULT_CROSSOVER_POINT);
- this->SetCrossoverPointStandardDeviation(Population::DEFAULT_CROSSOVER_POINT_STD);
-
- //
- this->SetMutationRate(Population::DEFAULT_MUTATION_RATE);
-
- //
- this->RandomizePopulation(this->population_size);
- }
-
- //
- void Population::ClearPopulation()
- {
- //
- this->chromosomes.clear();
- this->evolution_number = 0;
- }
-
- //
- void Population::InitRandomPopulation(int _population_size, int _bit_length)
- {
- //
- this->population_size = _population_size;
-
- //
- this->RandomizePopulation(_bit_length);
- }
-
- //
- void Population::RandomizePopulation(int _bit_length)
- {
- //
- std::shared_ptr<Chromosome> chromosome;
- int i;
-
- //
- this->ClearPopulation();
- for ( i=0; i<this->population_size; i++ ) {
-
- //
- chromosome = std::shared_ptr<Chromosome>(
- new Chromosome( this->random, _bit_length )
- );
- this->chromosomes.push_back(chromosome);
- }
- }
-
- //
- void Population::PopulationChanged()
- {
- //
- this->population_needs_sorting = true;
- }
-
- //
- std::vector<std::shared_ptr<Chromosome>> Population::GetChromosomes()
- {
- return this->chromosomes;
- }
-
- //
- void Population::GetChromosomes(std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes)
- {
- //
- _chromosomes->clear();
- for ( std::shared_ptr<Chromosome> chromosome : this->chromosomes) {
- _chromosomes->push_back(chromosome);
- }
- }
-
- //
- std::shared_ptr<Chromosome> Population::GetChampion()
- {
- //
- this->EnsureSortedPopulation();
-
- //
- if ( this->chromosomes.size() > 0 ) {
- return this->chromosomes[0];
- }
-
- return nullptr;
- }
-
- //
- double Population::GetAverageFitness()
- {
- return this->GetAverageFitness(this->chromosomes);
- }
-
- //
- double Population::GetAverageFitness(std::vector<std::shared_ptr<Chromosome>> _chromosomes)
- {
- //
- double fitness_sum;
- double fitness_average;
-
- //
- fitness_sum = 0;
- for ( std::shared_ptr<Chromosome> chromosome : _chromosomes ) {
- fitness_sum += chromosome->GetFitness();
- }
-
- //
- fitness_average = 0;
- if ( _chromosomes.size() > 0 ) {
- fitness_average = fitness_sum / _chromosomes.size();
- }
-
- return fitness_average;
- }
-
- //
- void Population::SetCrossoverType(Enums::CrossoverType t)
- {
- //
- this->crossover_type = t;
- }
-
- //
- Enums::CrossoverType Population::GetCrossoverType()
- {
- //
- return this->crossover_type;
- }
-
- //
- void Population::SetCrossoverOrder(Enums::CrossoverOrder o)
- {
- //
- this->crossover_order = o;
- }
-
- //
- Enums::CrossoverOrder Population::GetCrossoverOrder()
- {
- //
- return this->crossover_order;
- }
-
- //
- void Population::SetCrossoverBounds(Enums::CrossoverBounds b)
- {
- //
- this->crossover_bounds = b;
- }
-
- //
- Enums::CrossoverBounds Population::GetCrossoverBounds()
- {
- //
- return this->crossover_bounds;
- }
-
- //
- void Population::SetCrossoverPoint(double p)
- {
- //
- this->crossover_point = p;
- }
-
- //
- double Population::GetCrossoverPoint()
- {
- //
- return this->crossover_point;
- }
-
- //
- void Population::SetCrossoverPointStandardDeviation(double std)
- {
- //
- this->crossover_point_std = std;
- }
-
- //
- double Population::GetCrossoverPointStandardDeviation()
- {
- //
- return this->crossover_point_std;
- }
-
- //
- void Population::SetMutationRate(double r)
- {
- //
- this->mutation_rate = r;
- }
-
- //
- double Population::GetMutationRate()
- {
- //
- return this->mutation_rate;
- }
-
- //
- void Population::SetElitismType(Enums::ElitismType t)
- {
- //
- this->elitism_type = t;
- }
-
- //
- Enums::ElitismType Population::GetElitismType()
- {
- //
- return this->elitism_type;
- }
-
- //
- void Population::SetElitismRate(double r)
- {
- //
- this->elitism_rate = r;
- }
-
- //
- double Population::GetElitismRate()
- {
- //
- return this->elitism_rate;
- }
-
- //
- void Population::SetElitismCount(int c)
- {
- //
- this->elitism_count = c;
- }
-
- //
- int Population::GetElitismCount()
- {
- //
- return this->elitism_count;
- }
-
- //
- void Population::EvaluateFitness(std::function<double(std::shared_ptr<Chromosome>)> evaluation_callback)
- {
- //
- std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_copy;
- std::vector<std::shared_ptr<std::thread>> threads;
- std::shared_ptr<std::thread> thread;
- int
- threads_count,
- i
- ;
-
- // Make a new vector containing all current chromosomes
- this->population_modification_mutex.lock();
- _chromosomes_copy = std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>>(
- new std::vector<std::shared_ptr<Chromosome>>()
- );
- for ( i=0; i<(int)this->chromosomes.size(); i++ ) {
- _chromosomes_copy->push_back( this->chromosomes[i] );
- }
- this->population_modification_mutex.unlock();
-
- // Spawn threads
- threads_count = this->GetThreadCountSuggestion();
- for ( i=0; i<threads_count; i++) {
-
- //
- thread = std::shared_ptr<std::thread>(
- new std::thread(&Population::EvaluateFitness_Thread, this, _chromosomes_copy, evaluation_callback)
- );
- threads.push_back(thread);
- }
-
- // Wait for threads to finish
- for ( i=0; i<threads_count; i++ ) {
- threads[i]->join();
- }
- }
-
- //
- void Population::EvaluateError(std::function<double(std::shared_ptr<Chromosome>)> evaluation_callback)
- {
- //
- std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_copy;
- std::vector<std::shared_ptr<std::thread>> threads;
- std::shared_ptr<std::thread> thread;
- int
- threads_count,
- i
- ;
-
- // Make a new vector containing all current chromosomes
- this->population_modification_mutex.lock();
- _chromosomes_copy = std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>>(
- new std::vector<std::shared_ptr<Chromosome>>()
- );
- for ( i=0; i<(int)this->chromosomes.size(); i++ ) {
- _chromosomes_copy->push_back( this->chromosomes[i] );
- }
- this->population_modification_mutex.unlock();
-
- // Spawn threads
- threads_count = this->GetThreadCountSuggestion();
- for ( i=0; i<threads_count; i++) {
-
- //
- thread = std::shared_ptr<std::thread>(
- new std::thread(&Population::EvaluateError_Thread, this, _chromosomes_copy, evaluation_callback)
- );
- threads.push_back(thread);
- }
-
- // Wait for threads to finish
- for ( i=0; i<threads_count; i++ ) {
- threads[i]->join();
- }
- }
-
- //
- void Population::Evolve()
- {
- //
- std::shared_ptr<std::vector< std::shared_ptr<Chromosome> > > population_new;
-
- //
- if ( this->chromosomes.size() == 0 ) {
- return;
- }
-
- //
- this->EnsureSortedPopulation();
-
- //
- population_new = std::shared_ptr<
- std::vector<
- std::shared_ptr<Chromosome>
- >
- >(
- new std::vector<std::shared_ptr<Chromosome>>()
- );
-
- // Breed the new population
- this->BreedNewPopulation(population_new, (int)this->chromosomes.size());
-
- // Replace old population with the new
- this->chromosomes = *population_new;
- this->evolution_number++;
-
- //
- this->PopulationChanged();
- }
-
- //
- int Population::GetEvolutionNumber()
- {
- return this->evolution_number;
- }
-
- //
- void Population::PrintPopulation()
- {
- //
- this->EnsureSortedPopulation();
-
- this->PrintPopulation(this->chromosomes);
- }
-
- //
- void Population::PrintPopulation(std::vector<std::shared_ptr<Chromosome>> _chromosomes)
- {
- //
- for ( std::shared_ptr<Chromosome> chromosome : chromosomes ) {
- cout << chromosome->ToString() << endl;
- }
- cout << "Average Fitness --> " << this->GetAverageFitness(_chromosomes) << endl;
- }
-
- //
- void Population::InitRandomGenerator()
- {
- //
- this->random = std::shared_ptr<Random>(
- new Random()
- );
- }
-
- //
- void Population::InitRouletteWheel()
- {
- //
- this->roulette_wheel = std::shared_ptr<RouletteWheel>(
- new RouletteWheel()
- );
- }
-
- //
- void Population::InitBreeder()
- {
- //
- if ( !this->random ) {
- throw std::runtime_error("Population::InitBreeder() - Should come after InitRandomGenerator()");
- }
-
- //
- this->breeder = std::shared_ptr<Breeder>(
- new Breeder( this->random )
- );
- }
-
- //
- void Population::EnsureSortedPopulation()
- {
- //
- if ( !this->population_needs_sorting ) {
- return;
- }
-
- // Yay std::sort
- std::sort(
- this->chromosomes.begin(),
- this->chromosomes.end(),
- []( std::shared_ptr<Chromosome>& left, std::shared_ptr<Chromosome>& right ) -> bool
- {
- //
- if ( left->GetFitness() > right->GetFitness() ) {
- return true;
- }
-
- return false;
- }
- );
-
- //
- this->population_needs_sorting = false;
- }
-
- //
- void Population::BreedNewPopulation(std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> population_new, int size)
- {
- //
- std::vector<std::shared_ptr<std::thread>> threads;
- std::shared_ptr<std::thread> thread;
- int
- thread_count,
- i
- ;
-
- // First, populate the roulette wheel
- this->roulette_wheel->SetChromosomes(this->chromosomes);
-
- // Next, seed the population with elites
- this->SeedPopulationWithElites(population_new);
-
- // Next, breed until we've reached our new size
- thread_count = this->GetThreadCountSuggestion();
- for ( i=0; i<thread_count; i++) {
- thread = std::shared_ptr<std::thread>(
- new std::thread(&Population::BreedNewPopulation_Thread, this, population_new, size)
- );
- threads.push_back(thread);
- }
- for ( i=0; i<(int)threads.size(); i++) {
- threads[i]->join();
- }
-
- // Finally, reset the fitness of the new population
- for ( i=0; i<(int)population_new->size(); i++ ) {
- population_new->at(i)->ResetFitness();
- }
- }
-
- //
- void Population::BreedNewPopulation_Thread(std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> population_new, int size)
- {
- //
- std::shared_ptr<Chromosome> kiddo;
-
- //
- while ( (int)population_new->size() < size )
- {
- //
- kiddo = this->BreedChild();
-
- // Mutexed
- this->breed_mutex.lock();
- if ( (int)population_new->size() < size ) {
- population_new->push_back(kiddo);
- }
- this->breed_mutex.unlock();
- }
- }
-
- //
- int Population::DetermineEliteCount()
- {
- //
- int count;
-
- //
- switch( this->elitism_type )
- {
- //
- default:
- case Enums::ElitismType::None:
- count = 0;
- break;
-
- //
- case Enums::ElitismType::Absolute:
- count = this->elitism_count;
- break;
-
- //
- case Enums::ElitismType::Rate:
- count = floor( this->chromosomes.size() * this->elitism_rate );
- break;
- }
-
- return count;
- }
-
- //
- void Population::SeedPopulationWithElites(std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> population_new)
- {
- //
- std::unique_lock<std::recursive_mutex> lock(this->population_modification_mutex);
- std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> elites;
- std::vector<std::shared_ptr<std::thread>> threads;
- std::shared_ptr<std::thread> thread;
- int
- elites_count,
- i
- ;
-
- // Determine how many elites to copy
- elites_count = this->DetermineEliteCount();
- elites = std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>>(
- new std::vector<std::shared_ptr<Chromosome>>()
- );
-
- // First, copy over just the pointers
- for ( i=0; i<elites_count && i<(int)this->chromosomes.size(); i++) {
- elites->push_back( this->chromosomes[i] );
- }
-
- // Then, make them full copies (uses threads)
- this->CopyChromosomes(elites, population_new);
- }
-
- //
- void Population::EvaluateFitness_Thread(
- std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes,
- std::function<double(std::shared_ptr<Chromosome>)> evaluation_callback
- )
- {
- //
- std::shared_ptr<Chromosome> chromosome;
- double fitness;
-
- //
- while (true)
- {
- // Grab a free chromosome
- this->evaluate_fitness_mutex.lock();
- chromosome = nullptr;
- if ( _chromosomes->size() ) {
- chromosome = _chromosomes->at(_chromosomes->size()-1);
- _chromosomes->pop_back();
- }
- this->evaluate_fitness_mutex.unlock();
-
- // Call the evaluation callback
- if ( chromosome != nullptr ) {
- fitness = evaluation_callback(chromosome);
- chromosome->SetFitness(fitness);
- }
-
- // We're done if there was nothing to grab
- else{
- break;
- }
- }
- }
-
- //
- void Population::EvaluateError_Thread(
- std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes,
- std::function<double(std::shared_ptr<Chromosome>)> evaluation_callback
- )
- {
- //
- std::shared_ptr<Chromosome> chromosome;
- double error;
-
- //
- while (true)
- {
- // Grab a free chromosome
- this->evaluate_fitness_mutex.lock();
- chromosome = nullptr;
- if ( _chromosomes->size() ) {
- chromosome = _chromosomes->at(_chromosomes->size()-1);
- _chromosomes->pop_back();
- }
- this->evaluate_fitness_mutex.unlock();
-
- // Call the evaluation callback
- if ( chromosome != nullptr ) {
- error = evaluation_callback(chromosome);
- chromosome->SetError(error);
- }
-
- // We're done if there was nothing to grab
- else{
- break;
- }
- }
- }
-
- //
- void Population::CopyChromosomes(
- std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_source,
- std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_destination
- )
- {
- //
- std::vector<std::shared_ptr<std::thread>> threads;
- std::shared_ptr<std::thread> thread;
- int
- threads_count,
- i
- ;
-
- // Spawn threads
- threads_count = this->GetThreadCountSuggestion();
- for ( i=0; i<threads_count; i++) {
-
- //
- thread = std::shared_ptr<std::thread>(
- new std::thread(&Population::CopyChromosomes_Thread, this, _chromosomes_source, _chromosomes_destination)
- );
- threads.push_back(thread);
- }
-
- // Wait for threads to finish
- for ( i=0; i<threads_count; i++ ) {
- threads[i]->join();
- }
- }
-
- //
- void Population::CopyChromosomes_Thread(
- std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_source,
- std::shared_ptr<std::vector<std::shared_ptr<Chromosome>>> _chromosomes_destination
- )
- {
- //
- std::shared_ptr<Chromosome>
- chromosome_original,
- chromosome_copied
- ;
- stringstream ss;
-
- //
- while ( _chromosomes_destination->size() < _chromosomes_source->size() )
- {
- // Grab the next slot
- this->copy_chromosomes_mutex.lock();
- chromosome_original = nullptr;
- chromosome_copied = nullptr;
- if ( _chromosomes_destination->size() < _chromosomes_source->size() ) {
-
- //
- chromosome_copied = std::shared_ptr<Chromosome>(
- new Chromosome(this->random, 0)
- );
- _chromosomes_destination->push_back(chromosome_copied);
- chromosome_original = _chromosomes_source->at(_chromosomes_destination->size()-1);
- }
- this->copy_chromosomes_mutex.unlock();
-
- // Make a full copy of the original, outside the lock
- if ( chromosome_copied && chromosome_original ) {
- *chromosome_copied = *chromosome_original;
- }
- }
- }
-
- //
- std::shared_ptr<Chromosome> Population::BreedChild()
- {
- //
- std::shared_ptr<Chromosome>
- mama, papa, kiddo
- ;
-
- // Pick two parents
- mama = this->roulette_wheel->Spin();
- papa = this->roulette_wheel->Spin();
-
- //
- kiddo = this->breeder->Breed(
- mama, papa,
- this->crossover_type,
- this->crossover_order,
- this->crossover_bounds,
- this->crossover_point,
- this->crossover_point_std,
- this->mutation_rate
- );
-
- return kiddo;
- }
-
- //
- int Population::GetThreadCountSuggestion()
- {
- //
- int thread_count;
-
- //
- thread_count = std::thread::hardware_concurrency();
-
- return thread_count;
- }
- };
-
-
-
-
-
-
-
-
-
|