ian@0: //  Copyright 2011, Ian Hobson.
ian@0: //
ian@0: //  This file is part of gpsynth.
ian@0: //
ian@0: //  gpsynth is free software: you can redistribute it and/or modify
ian@0: //  it under the terms of the GNU General Public License as published by
ian@0: //  the Free Software Foundation, either version 3 of the License, or
ian@0: //  (at your option) any later version.
ian@0: //
ian@0: //  gpsynth is distributed in the hope that it will be useful,
ian@0: //  but WITHOUT ANY WARRANTY; without even the implied warranty of
ian@0: //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
ian@0: //  GNU General Public License for more details.
ian@0: //
ian@0: //  You should have received a copy of the GNU General Public License
ian@0: //  along with gpsynth in the file COPYING. 
ian@0: //  If not, see http://www.gnu.org/licenses/.
ian@0: 
ian@0: #include "population.hpp"
ian@0: 
ian@0: #include "boost_ex.hpp"
ian@0: #include "graph_helpers.hpp"
ian@0: #include "logger.hpp"
ian@0: #include "statistics.hpp"
ian@0: #include "std_ex.hpp"
ian@0: 
ian@0: #include "boost/bind.hpp"
ian@0: #include "boost/filesystem.hpp"
ian@0: #include "boost/lexical_cast.hpp"
ian@0: #include "boost/math/special_functions/fpclassify.hpp"
ian@0: 
ian@0: #include <algorithm>
ian@0: #include <cmath>
ian@0: #include <fstream>
ian@0: #include <iterator>
ian@0: #include <limits>
ian@0: #include <map>
ian@0: #include <numeric>
ian@0: #include <set>
ian@0: #include <sstream>
ian@0: #include <vector>
ian@0: 
ian@0: namespace bf = boost::filesystem;
ian@0: 
ian@0: namespace {
ian@0:   
ian@0:   const std::string g_default_work_folder = "/tmp";
ian@0:   
ian@0: // mutated graphs might have imported parameters outside of the graph's range
ian@0: // or removed parameter inputs making some parameters redundant
ian@0: void UpdateParameters(sg::Graph& graph) {
ian@0:   std::size_t parameter_count = graph[boost::graph_bundle].parameters_.size();
ian@0:   // scan through vertices to find parameter inputs
ian@0:   std::map<int, std::vector<sg::Vertex> > parameters;
ian@0:   sg::VertexIterator vertex;
ian@0:   sg::VertexIterator vertex_end;
ian@0:   for (boost::tie(vertex, vertex_end) = boost::vertices(graph); 
ian@0:        vertex != vertex_end; 
ian@0:        ++vertex) {
ian@0:     const sg::Node& node_info = graph[*vertex];
ian@0:     if (node_info.type_ == sg::kParameter) {
ian@0:       parameters[node_info.id_].push_back(*vertex);
ian@0:     }
ian@0:   }
ian@0:   // check if any corrections required
ian@0:   if (parameters.size() == parameter_count) {
ian@0:     if (parameter_count == 0) {
ian@0:       // no parameters in the graph, nothing to do
ian@0:       return;
ian@0:     }
ian@0:     // check that last parameter id is correct, otherwise corrections are needed
ian@0:     if (parameters.rbegin()->first == (parameter_count)) {
ian@0:       // all seems well, get out of here
ian@0:       return;  
ian@0:     }
ian@0:   } else if (parameters.size() > parameter_count) {
ian@0:     // add extra parameters to the graph
ian@0:     std::generate_n(std::back_inserter(graph[boost::graph_bundle].parameters_),
ian@0:                     parameters.size() - parameter_count,
ian@0:                     stdx::RandomCoefficient);
ian@0:   } else {
ian@0:     // remove redundant parameters
ian@0:     graph[boost::graph_bundle].parameters_.resize(parameters.size());
ian@0:   }
ian@0:   // reassign parameter ids through the graph
ian@0:   int parameter_id = 1;
ian@0:   typedef std::map<int, std::vector<sg::Vertex> >::value_type ParameterMapping;
ian@0:   foreach (ParameterMapping p, parameters) {
ian@0:     foreach (sg::Vertex v, p.second) {
ian@0:       graph[v].id_ = parameter_id;
ian@0:     }
ian@0:     ++parameter_id;
ian@0:   }
ian@0:   // job done
ian@0: }
ian@0: 
ian@0: } // namespace
ian@0: 
ian@0: Population::Population(GrammarInterface* grammar,
ian@0:                        ConverterInterface* converter,
ian@0:                        EvaluatorInterface* evaluator)
ian@0: : grammar_(grammar),
ian@0:   converter_(converter),
ian@0:   evaluator_(evaluator),
ian@0:   generation_(0),
ian@0:   max_generations_(0),
ian@0:   fitness_threshold_(0),
ian@0:   tournament_size_(7),
ian@0:   crossover_rate_(0.65),
ian@0:   mutation_rate_(0.3),
ian@0:   reproduce_best_(false),
ian@0:   keep_temp_folders_(false)
ian@0: {
ian@0:   evaluator_->SetListener(this);
ian@0:   mutators_.push_back(boost::bind(&GrammarInterface::MutationReplaceSubTree,
ian@0:                                   grammar, _1));
ian@0:   mutators_.push_back(boost::bind(&GrammarInterface::MutationAddSubTree,
ian@0:                                   grammar, _1));
ian@0:   mutators_.push_back(boost::bind(&GrammarInterface::MutationModifyInputs,
ian@0:                                   grammar, _1));
ian@0:   mutators_.push_back(boost::bind(&GrammarInterface::MutationModifyConnections,
ian@0:                                   grammar, _1));
ian@0:   mutators_.push_back(boost::bind(&GrammarInterface::MutationReplaceCommand,
ian@0:                                   grammar, _1));
ian@0: //  mutators_.push_back(boost::bind(&GrammarInterface::MutationInsertCommand,
ian@0: //                                  grammar, _1));
ian@0:   SetupGeneticOperationSelector();
ian@0:   SetWorkFolder(g_default_work_folder);
ian@0: }
ian@0: 
ian@0: void Population::SetWorkFolder(const std::string &path) {
ian@0:   work_folder_ = path;
ian@0:   log_folder_ = path + "/logs";
ian@0:   render_folder_ = path + "/render";
ian@0:   dot_folder_ = path + "/dot";
ian@0:   export_folder_ = path + "/export";
ian@0: }
ian@0: 
ian@0: void Population::Evolve(int max_generations) {
ian@0:   max_generations_ = max_generations;
ian@0:   // make sure the folders for storing best outputs are created
ian@0:   bf::create_directories(render_folder_);
ian@0:   bf::create_directories(dot_folder_);
ian@0:   bf::create_directories(export_folder_);
ian@0:   bf::create_directories(log_folder_);
ian@0:   for (generation_ = 1; generation_ <= max_generations; generation_++) {
ian@0:     NewGenerationMessage();
ian@0:     SetGenerationFolder();
ian@0:     ExportToDOT();
ian@0:     EvaluateGeneration();
ian@0:     AnalyzeGeneration();
ian@0:     SaveGenerationBest();
ian@0:     CleanTempFolders();
ian@0:     if (CheckThreshold()) {
ian@0:       logger::Log("Fitness threshold reached\n");
ian@0:       return;
ian@0:     }
ian@0:     BreedNewGeneration();
ian@0:   }
ian@0: }
ian@0: 
ian@0: void Population::NewGenerationMessage() const {
ian@0:   std::stringstream message;
ian@0:   message << "Generation " << generation_ << '\n';
ian@0:   logger::Log(message.str());
ian@0: }
ian@0: 
ian@0: void Population::SetGenerationFolder() {
ian@0:   std::stringstream path;
ian@0:   path << work_folder_ << "/generation_" 
ian@0:        << std::setw(std::log10(max_generations_) + 1) << std::setfill('0')
ian@0:        << generation_ << '/';
ian@0:   generation_folder_ = path.str();
ian@0: }
ian@0: 
ian@0: bool Population::CheckThreshold() const {
ian@0:   double best_fitness = population_[best_fit_][boost::graph_bundle].fitness_;
ian@0:   return best_fitness <= fitness_threshold_;
ian@0: }
ian@0: 
ian@0: void Population::CleanTempFolders() const {
ian@0:   if (!keep_temp_folders_) {
ian@0:     bf::remove_all(generation_folder_);
ian@0:   }
ian@0: }
ian@0: 
ian@0: void Population::InitializePopulation(std::size_t size) {
ian@0:   population_.resize(size);
ian@0:   fitnesses_.resize(size);
ian@0:   for (int i = 0; i < size; i++) {
ian@0:     grammar_->RandomGraph(population_[i]);
ian@0:     population_[i][boost::graph_bundle].id_ = i;
ian@0:   }
ian@0: }
ian@0: 
ian@0: void Population::EvaluateGeneration() {
ian@0:   // make sure we have a clean temp folder for the generation
ian@0:   bf::remove_all(generation_folder_);
ian@0:   evaluator_->SetWorkFolder(generation_folder_);
ian@0:   evaluator_->RateGraphs(population_);
ian@0:   logger::Log("\n");
ian@0:   // store graph fitnesses
ian@0:   for (std::size_t i = 0, size = population_.size(); i < size; i++) {
ian@0:     fitnesses_[i] = population_[i][boost::graph_bundle].fitness_;
ian@0:   }
ian@0: }
ian@0: 
ian@0: void Population::AnalyzeGeneration() {
ian@0:   double mean_fitness = stats::Mean(fitnesses_.begin(), fitnesses_.end());
ian@0:   if (boost::math::isnan(mean_fitness)) {
ian@0:     logger::Log("ruh roh\n"); // TODO
ian@0:   }
ian@0:   std::stringstream message;
ian@0:   std::vector<double>::const_iterator best_fitness;
ian@0:   best_fitness = std::min_element(fitnesses_.begin(), fitnesses_.end());
ian@0:   best_fit_ = static_cast<int>(best_fitness - fitnesses_.begin());
ian@0:   message << "Average Fitness:" << mean_fitness
ian@0:           << " Best"
ian@0:           //<< " [" << best_fit_ << "]"
ian@0:           << ':' << *best_fitness << '\n';
ian@0:   logger::Log(message.str());
ian@0:   // save fitness values to logs
ian@0:   std::stringstream average;
ian@0:   average << generation_ << ' ' << mean_fitness;
ian@0:   stdx::AppendToFile(average.str(), log_folder_ + "/average_fitnesses.txt");
ian@0:   std::stringstream best;
ian@0:   best << generation_ << ' ' << *best_fitness;
ian@0:   stdx::AppendToFile(best.str(), log_folder_ + "/best_fitnesses.txt");
ian@0: }
ian@0: 
ian@0: void Population::SaveGenerationBest() {
ian@0:   std::stringstream generation_prefix;
ian@0:   generation_prefix << "generation_" 
ian@0:                     << std::setw(std::log10(max_generations_) + 1) 
ian@0:                     << std::setfill('0')
ian@0:                     << generation_;
ian@0:   const sg::Graph& best_graph = population_[best_fit_];
ian@0:   const sg::GraphProperties& graph_properties = best_graph[boost::graph_bundle];
ian@0:   // copy the rendered output for the graph
ian@0:   bf::path path = graph_properties.render_path_;
ian@0:   if (bf::exists(path)) {
ian@0:     std::string render_path = render_folder_ + '/' 
ian@0:                               + generation_prefix.str() 
ian@0:                               + path.extension().string();
ian@0:     bf::copy_file(path, render_path);
ian@0:   }
ian@0:   // copy the dot script for the graph
ian@0:   path = graph_properties.dot_path_;
ian@0:   if (bf::exists(path)) {
ian@0:     std::string dot_path = dot_folder_ + '/' 
ian@0:                            + generation_prefix.str() 
ian@0:                            + path.extension().string();
ian@0:     bf::copy_file(path, dot_path);
ian@0:   }
ian@0:   // tell the converter to export the graph
ian@0:   converter_->Export(best_graph, export_folder_, generation_prefix.str());
ian@0: }
ian@0: 
ian@0: void Population::PerformCrossover(sg::Graph& child_1, sg::Graph& child_2) {
ian@0:   int parent_id_1 = SelectIndividual();
ian@0:   int parent_id_2;
ian@0:   do {
ian@0:     parent_id_2 = SelectIndividual(); 
ian@0:   } while (parent_id_1 == parent_id_2);
ian@0:   // pick the crossover points via the grammar
ian@0:   const sg::Graph& parent_1 = population_[parent_id_1];
ian@0:   const sg::Graph& parent_2 = population_[parent_id_2];
ian@0:   sg::Vertex crossover_1;
ian@0:   sg::Vertex crossover_2;
ian@0:   grammar_->PickCrossoverNodes(parent_1, parent_2, &crossover_1, &crossover_2);
ian@0:   // swap the subtrees
ian@0:   SwapSubTrees(crossover_1, crossover_2, parent_1, parent_2, child_1, child_2);
ian@0: }
ian@0: 
ian@0: // called for mutated graphs to prepare for next generation
ian@0: void Population::PrepareNewChild(sg::Graph& child) {
ian@0:   // reset fitness rating
ian@0:   child[boost::graph_bundle].fitness_ = sg::kFitnessUnrated;
ian@0:   // make sure parameters in graph are valid
ian@0:   UpdateParameters(child);
ian@0: }
ian@0: 
ian@0: void Population::BreedNewGeneration() {
ian@0:   // Used to store reproduced graph ids, prevents a graph being reproduced
ian@0:   // more than once.
ian@0:   std::set<int> reproduced;
ian@0:   std::vector<sg::Graph> next_generation;
ian@0:   next_generation.reserve(population_.size());
ian@0:   if (reproduce_best_) {
ian@0:     next_generation.push_back(population_[best_fit_]);
ian@0:   }
ian@0:   std::size_t population_size = population_.size();
ian@0:   while (next_generation.size() < population_size) {
ian@0:     GeneticOperation operation;
ian@0:     operation = static_cast<GeneticOperation>(genetic_operation_selector_());
ian@0:     if (operation == kCrossover) {
ian@0:       // Crossover
ian@0:       // create two empty graphs to receive results of crossover
ian@0:       // (creating them directly in the next_generation container causes
ian@0:       // memory problems when performing crossover, couldn't fathom why..)
ian@0:       sg::Graph child_1;
ian@0:       sg::Graph child_2;
ian@0:       PerformCrossover(child_1, child_2);
ian@0:       PrepareNewChild(child_1);
ian@0:       PrepareNewChild(child_2);
ian@0:       next_generation.push_back(child_1);
ian@0:       next_generation.push_back(child_2);
ian@0:     } else if (operation == kMutation) {
ian@0:       // mutation
ian@0:       // store a copy of an individual from current population
ian@0:       next_generation.push_back(population_[SelectIndividual()]);
ian@0:       sg::Graph& child = next_generation.back();
ian@0:       // call random mutation operator on child
ian@0:       bool mutated;
ian@0:       do {
ian@0:         // some mutators might not be able to operate on a specific graph
ian@0:         // and will return false, so try another mutator
ian@0:         mutated = mutators_[stdx::Random(mutators_.size())](child);
ian@0:       } while (!mutated);
ian@0:       PrepareNewChild(child);
ian@0:     } else {
ian@0:       // reproduction
ian@0:       int graph_id = SelectIndividual();
ian@0:       // only reproduce the individual if it hasn't already been reproduced
ian@0:       if (reproduced.find(graph_id) == reproduced.end()) {
ian@0:         next_generation.push_back(population_[graph_id]);
ian@0:         reproduced.insert(graph_id);
ian@0:       }
ian@0:     }
ian@0:   }
ian@0:   // we might have an extra individual from crossover
ian@0:   next_generation.resize(population_size);
ian@0:   // reassign graph ids
ian@0:   for (std::size_t i = 0, size = population_.size(); i < size; i++) {
ian@0:     next_generation[i][boost::graph_bundle].id_ = static_cast<int>(i);
ian@0:   }
ian@0:   // replace the population with the newly created generation
ian@0:   population_.swap(next_generation);
ian@0: }
ian@0: 
ian@0: // tournament selection 
ian@0: int Population::SelectIndividual() {
ian@0:   // select n individuals from the population
ian@0:   std::set<std::size_t> tournament;
ian@0:   while (tournament.size() < tournament_size_) {
ian@0:     tournament.insert(stdx::Random(population_.size()));
ian@0:   }
ian@0:   double best_fitness = std::numeric_limits<double>::max();
ian@0:   std::size_t result = -1;
ian@0:   // find best graph from selection
ian@0:   foreach (std::size_t graph_id, tournament) {
ian@0:     if (fitnesses_[graph_id] < best_fitness) {
ian@0:       best_fitness = fitnesses_[graph_id];
ian@0:       result = graph_id;
ian@0:     }
ian@0:   }
ian@0:   return static_cast<int>(result);
ian@0: }
ian@0: 
ian@0: void Population::ExportToDOT() {
ian@0:   std::string dot_folder = generation_folder_ + "/dot/";
ian@0:   bf::create_directories(dot_folder);
ian@0:   std::stringstream path;
ian@0:   foreach (sg::Graph& graph, population_) {
ian@0:     path.str("");
ian@0:     path << dot_folder 
ian@0:          << "gpsynth_" << graph[boost::graph_bundle].id_ << ".dot";
ian@0:     std::ofstream file(path.str().c_str());
ian@0:     file << converter_->ToDOT(graph);
ian@0:     file.close();
ian@0:     graph[boost::graph_bundle].dot_path_ = path.str();
ian@0:   }
ian@0: }
ian@0: 
ian@0: void Population::GraphRatedNotification(std::size_t graphs_rated) {
ian@0:   std::stringstream message;
ian@0:   message << "\rRated " << graphs_rated << " / " << population_.size();
ian@0:   logger::Log(message.str());
ian@0: }
ian@0: 
ian@0: void Population::SetCrossoverRate(double rate) {
ian@0:   crossover_rate_ = rate;
ian@0:   SetupGeneticOperationSelector();
ian@0: }
ian@0: 
ian@0: void Population::SetMutationRate(double rate) {
ian@0:   mutation_rate_ = rate;
ian@0:   SetupGeneticOperationSelector();
ian@0: }
ian@0: 
ian@0: void Population::SetupGeneticOperationSelector() {
ian@0:   std::vector<double> genetic_probabilities(2);
ian@0:   genetic_probabilities[kCrossover] = crossover_rate_;
ian@0:   genetic_probabilities[kMutation] = mutation_rate_;
ian@0:   // reproduction is left over probability
ian@0:   genetic_operation_selector_.SetProbabilities(genetic_probabilities);
ian@0: }