neat_genome.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>
#include <map>
#include <random>
#include <stdexcept>
#include <utility>
#include <vector>
 
namespace pulsatrix {
 
struct NodeGene {
    enum class Type { Input, Bias, Output, Hidden };
    int id;
    Type type;
};
 
struct ConnectionGene {
    int in_node;
    int out_node;
    double weight;
    bool enabled;
    int innovation;
};
 
class InnovationTracker {
public:
    explicit InnovationTracker(int next_node_id) : next_node_id_(next_node_id) {}
 
    int GetConnectionInnovation(int in_node, int out_node) {
        auto key = std::make_pair(in_node, out_node);
        auto it = connection_innovations_.find(key);
        if (it != connection_innovations_.end()) {
            return it->second;
        }
        int innovation = next_innovation_++;
        connection_innovations_[key] = innovation;
        return innovation;
    }
 
    int GetNodeIdForSplit(int split_connection_innovation) {
        auto it = node_ids_by_split_.find(split_connection_innovation);
        if (it != node_ids_by_split_.end()) {
            return it->second;
        }
        int node_id = next_node_id_++;
        node_ids_by_split_[split_connection_innovation] = node_id;
        return node_id;
    }
 
private:
    std::map<std::pair<int, int>, int> connection_innovations_;
    std::map<int, int> node_ids_by_split_;
    int next_innovation_ = 0;
    int next_node_id_;
};
 
class NEATGenome {
public:
    NEATGenome(int num_inputs, int num_outputs, bool has_bias, InnovationTracker& tracker) {
        if (num_inputs <= 0 || num_outputs <= 0) {
            throw std::invalid_argument("NEATGenome: num_inputs and num_outputs must be positive");
        }
        int next_id = 0;
        std::vector<int> input_ids;
        for (int i = 0; i < num_inputs; ++i) {
            nodes_.push_back(NodeGene{next_id, NodeGene::Type::Input});
            input_ids.push_back(next_id);
            ++next_id;
        }
        if (has_bias) {
            nodes_.push_back(NodeGene{next_id, NodeGene::Type::Bias});
            input_ids.push_back(next_id);
            ++next_id;
        }
        std::vector<int> output_ids;
        for (int i = 0; i < num_outputs; ++i) {
            nodes_.push_back(NodeGene{next_id, NodeGene::Type::Output});
            output_ids.push_back(next_id);
            ++next_id;
        }
        for (int in_id : input_ids) {
            for (int out_id : output_ids) {
                int innovation = tracker.GetConnectionInnovation(in_id, out_id);
                connections_.push_back(ConnectionGene{in_id, out_id, 0.0, true, innovation});
            }
        }
    }
 
    [[nodiscard]] const std::vector<NodeGene>& nodes() const { return nodes_; }
    [[nodiscard]] const std::vector<ConnectionGene>& connections() const { return connections_; }
 
    void SetConnectionWeight(int innovation, double weight) {
        auto it = std::find_if(connections_.begin(), connections_.end(),
                                [&](const ConnectionGene& c) { return c.innovation == innovation; });
        if (it == connections_.end()) {
            throw std::invalid_argument("NEATGenome::SetConnectionWeight: no connection with that innovation");
        }
        it->weight = weight;
    }
 
    void AddConnectionBetween(int in_node, int out_node, double weight, InnovationTracker& tracker) {
        if (!HasNode(in_node) || !HasNode(out_node)) {
            throw std::invalid_argument("NEATGenome::AddConnectionBetween: node not found in this genome");
        }
        for (const auto& c : connections_) {
            if (c.in_node == in_node && c.out_node == out_node) {
                throw std::invalid_argument("NEATGenome::AddConnectionBetween: connection already exists");
            }
        }
        int innovation = tracker.GetConnectionInnovation(in_node, out_node);
        connections_.push_back(ConnectionGene{in_node, out_node, weight, true, innovation});
    }
 
    template <typename RNG>
    bool AddConnection(InnovationTracker& tracker, RNG& rng) {
        std::vector<std::pair<int, int>> candidates;
        for (const auto& a : nodes_) {
            if (a.type == NodeGene::Type::Output) {
                continue;  // outputs never originate a connection in a feedforward network
            }
            for (const auto& b : nodes_) {
                if (b.type == NodeGene::Type::Input || b.type == NodeGene::Type::Bias || a.id == b.id) {
                    continue;
                }
                if (ConnectionExists(a.id, b.id)) {
                    continue;
                }
                if (CanReach(b.id, a.id)) {
                    continue;  // adding a.id -> b.id would close a cycle
                }
                candidates.emplace_back(a.id, b.id);
            }
        }
        if (candidates.empty()) {
            return false;
        }
        std::uniform_int_distribution<size_t> pick(0, candidates.size() - 1);
        std::normal_distribution<double> weight_dist(0.0, 1.0);
        auto [in_node, out_node] = candidates[pick(rng)];
        AddConnectionBetween(in_node, out_node, weight_dist(rng), tracker);
        return true;
    }
 
    void AddNodeSplitting(int connection_innovation, InnovationTracker& tracker) {
        auto it = std::find_if(connections_.begin(), connections_.end(), [&](const ConnectionGene& c) {
            return c.innovation == connection_innovation && c.enabled;
        });
        if (it == connections_.end()) {
            throw std::invalid_argument("NEATGenome::AddNodeSplitting: no enabled connection with that innovation");
        }
        it->enabled = false;
        int in_node = it->in_node;
        int out_node = it->out_node;
        double original_weight = it->weight;
 
        int new_node_id = tracker.GetNodeIdForSplit(connection_innovation);
        nodes_.push_back(NodeGene{new_node_id, NodeGene::Type::Hidden});
 
        int innovation_in = tracker.GetConnectionInnovation(in_node, new_node_id);
        connections_.push_back(ConnectionGene{in_node, new_node_id, 1.0, true, innovation_in});
        int innovation_out = tracker.GetConnectionInnovation(new_node_id, out_node);
        connections_.push_back(ConnectionGene{new_node_id, out_node, original_weight, true, innovation_out});
    }
 
    template <typename RNG>
    bool AddNode(InnovationTracker& tracker, RNG& rng) {
        std::vector<int> enabled_innovations;
        for (const auto& c : connections_) {
            if (c.enabled) {
                enabled_innovations.push_back(c.innovation);
            }
        }
        if (enabled_innovations.empty()) {
            return false;
        }
        std::uniform_int_distribution<size_t> pick(0, enabled_innovations.size() - 1);
        AddNodeSplitting(enabled_innovations[pick(rng)], tracker);
        return true;
    }
 
    template <typename RNG>
    void MutateWeights(double sigma, double mutation_probability, RNG& rng) {
        if (sigma < 0.0) {
            throw std::invalid_argument("NEATGenome::MutateWeights: sigma must be non-negative");
        }
        if (mutation_probability < 0.0 || mutation_probability > 1.0) {
            throw std::invalid_argument("NEATGenome::MutateWeights: mutation_probability must be in [0, 1]");
        }
        std::bernoulli_distribution mask(mutation_probability);
        std::normal_distribution<double> noise(0.0, sigma);
        for (auto& c : connections_) {
            if (c.enabled && mask(rng)) {
                c.weight += noise(rng);
            }
        }
    }
 
private:
    [[nodiscard]] bool HasNode(int id) const {
        return std::any_of(nodes_.begin(), nodes_.end(), [&](const NodeGene& n) { return n.id == id; });
    }
 
    [[nodiscard]] bool ConnectionExists(int in_node, int out_node) const {
        return std::any_of(connections_.begin(), connections_.end(), [&](const ConnectionGene& c) {
            return c.in_node == in_node && c.out_node == out_node;
        });
    }
 
    [[nodiscard]] bool CanReach(int from_node, int out_node) const {
        std::vector<int> stack{from_node};
        std::vector<int> visited;
        while (!stack.empty()) {
            int current = stack.back();
            stack.pop_back();
            if (current == out_node) {
                return true;
            }
            if (std::find(visited.begin(), visited.end(), current) != visited.end()) {
                continue;
            }
            visited.push_back(current);
            for (const auto& c : connections_) {
                if (c.enabled && c.in_node == current) {
                    stack.push_back(c.out_node);
                }
            }
        }
        return false;
    }
 
    std::vector<NodeGene> nodes_;
    std::vector<ConnectionGene> connections_;
};
 
}  // namespace pulsatrix