Genetic Algorithm Solution for Expression Finding

genetic_algo.cpp

#include <iostream>
#include <vector>
#include <ctime>
#include <queue>
#include <stack>
#include <memory>

int MAX_GENERATION = 10000;
int POPULATION_SIZE;
int TARGET_NUM;
int NUM_COUNT;
int NODE_COUNT;
int SIGN_COUNT;
std::vector<int> numbers;

char ops[] = {'+', '-', '*', '/'};
class Node {
public:
    Node() {};
    Node(char _op) : op(_op) {};
    Node(int _num) : num(_num) {};

    Node& operator=(Node& n) {
        for(int r = 0; r < 2; ++r) l[r] = std::move(n.l[r]);
        copy(n);
        return *this;
    }

    void copy(const Node& n) {
        op = n.op;
        num = n.num;
    }

    float calc() {
        if(op) {
            switch(op){
                case '+': return l[0]->calc() + l[1]->calc();
                case '-': return l[0]->calc() - l[1]->calc();
                case '*': return l[0]->calc() * l[1]->calc();
                case '/': return l[0]->calc() / l[1]->calc();
            }
        }
        return num;
    }

    bool isSign() {
        return op != 0;
    }

    std::string infoAsStr() {
        std::string str = "";
        if(isSign()) return str + op;
        return std::to_string(num);
    }

    std::string toString() {
        if(op) {
            switch(op){
                case '+': return "(" + l[0]->toString() + " + " + l[1]->toString() + ")";
                case '-': return "(" + l[0]->toString() + " - " + l[1]->toString() + ")";
                case '*': return "(" + l[0]->toString() + " * " + l[1]->toString() + ")";
                case '/': return "(" + l[0]->toString() + " / " + l[1]->toString() + ")";
            }
        }
        return std::to_string(num);
    }

    char op = 0;
    int num = 0;

    std::unique_ptr<Node> l[2];
    Node* p = nullptr;
};

class Tree {
public:
    Tree(bool auto_generate = true) { if(auto_generate) generateRandomly(); };
    Tree(const Tree& t) { *this = t; }
    Tree& operator=(const Tree& t) {
        root.reset(t.root.get());
        fitness = t.fitness;
        return *this;
    }

    float getFitness() { return fitness; }

    void calcFitness() {
        fitness = abs(TARGET_NUM - root->calc());
    }

    std::unique_ptr<Node> root;
private:
    float fitness;

    std::unique_ptr<Node> getRandomNode(std::vector<std::unique_ptr<Node>>& pool) {
        if(pool.empty()) return nullptr;

        int r = std::rand() % pool.size();
        std::unique_ptr<Node> n = std::move(pool[r]);
        pool.erase(pool.begin() + r);
        return n;
    };

    void generateRandomly() {
        std::vector<std::unique_ptr<Node>> pool;

        // Initialize leafs
        for(unsigned i = 0; i < numbers.size(); ++i) pool.push_back(std::make_unique<Node>(numbers[i]));
        // Operators
        while(!pool.empty()) {
            std::unique_ptr<Node> sign = std::make_unique<Node>(ops[rand() % 4]);

            for(int r = 0; r < 2; ++r) {
                sign->l[r] = getRandomNode(pool);
                sign->l[r]->p = sign.get();
            }

            if(pool.empty()) root = std::move(sign);
            else pool.push_back(std::move(sign));
        }

        calcFitness();
    };
};

Tree* randomSelection(std::vector<std::unique_ptr<Tree>>& p) {
    float sum_fitness = 0;
    for(unsigned i = 0; i < p.size(); ++i) sum_fitness += p[i]->getFitness();

    float val = std::rand() % std::max(1, (int)sum_fitness);
    for(unsigned i = 0; i < p.size(); ++i) {
        val -= p[i]->getFitness();
        if(val <= 0) return p[i].get();
    }

    return p[p.size() - 1].get();
}

std::unique_ptr<Tree> crossOver(Tree* x, Tree* y) {
    // Pick the cut nodes randomly
    Tree* trees[2] = { x, y };

    std::unique_ptr<Tree> child = std::make_unique<Tree>();

    Node genome_signs[3][SIGN_COUNT]; // 2 parents, 1 children
    Node genome_nums[3][NUM_COUNT]; // 2 parents, 1 children
    Node genome[3][NODE_COUNT]; // 2 parents, 1 children

    // Copy parent genomes
    {
        for(unsigned k = 0; k < 2; ++k) {
            std::stack<Node*> q;
            q.push(trees[k]->root.get());

            int g = 0, g_s = 0, g_n = 0;
            genome[k][g++].copy(*q.top());
            if(q.top()->isSign()) genome_signs[k][g_s++].copy(*q.top());
            else                  genome_nums [k][g_n++].copy(*q.top());

            while(!q.empty()) {
                Node* n = q.top();
                q.pop();

                // Push leafs
                for(int r = 0; r < 2; ++r){
                    if(n->l[r] != nullptr) {
                        q.push(n->l[r].get());
                        genome[k][g++].copy(*q.top());
                        if(q.top()->isSign()) genome_signs[k][g_s++].copy(*q.top());
                        else                  genome_nums [k][g_n++].copy(*q.top());
                    }
                }
            }
        }
    }

    // Crossover numbers and signs separately, signs first, Uniform Crossover.
    {
        for(int i = 0; i < SIGN_COUNT; ++i) {
            genome_signs[2][i].copy(rand() % 2 ? genome_signs[0][i] : genome_signs[1][i]);
        }
    }

    // Now crossover the numbers, Order-based Crossover
    {
        bool temp[NUM_COUNT]; // Fill this array with 0, 1 randomly
        std::vector<Node*> temp0s;
        for(int i = 0; i < NUM_COUNT; ++i) {
            temp[i] = rand() % 2;
            // Copy the 1 ones directly
            if(temp[i] == 1) genome_nums[2][i].copy(genome_nums[0][i]);
            else { // Save the 0 ones in temp0s, we will add them with the order of parent-2 later.
                temp0s.push_back(&genome_nums[0][i]);
            }
        }
        for(int i = 0; i < NUM_COUNT && temp0s.size() > 0; ++i) {
            if(temp[i] == 0) { // Fill these empty places with temp0s in parent-2 order
                // Find the first in parent-2
                bool found = false;
                for(int j = 0; j < NUM_COUNT && !found; ++j) { // Loop parent-2
                    for(unsigned k = 0; k < temp0s.size() && !found; ++k) { // Check if current number is in temp0s list
                        // Found!
                        if(genome_nums[1][j].infoAsStr() == temp0s[k]->infoAsStr()){
                            genome_nums[2][i].copy(genome_nums[1][j]);
                            temp0s.erase(temp0s.begin() + k);
                            found = true;
                        }
                    }
                }
            }
        }
    }

    // Now merge numbers and signs with the parent-1 order
    {
        int g_s = 0, g_n = 0;
        for(int i = 0; i < NODE_COUNT; ++i) {
            if(genome[0][i].isSign()) {
                // Mutate sign
                if(rand() % 100 < 20) {
                    int s;
                    do { s = rand() % 4; } while(ops[s] == genome_signs[2][g_s].op);
                    genome_signs[2][g_s].op = ops[s];
                }
                genome[2][i].copy(genome_signs[2][g_s++]);
            }
            else genome[2][i].copy(genome_nums [2][g_n++]);
        }
    }

    // Construct child
    {
        std::stack<std::unique_ptr<Node>> st;
        for(int i = NODE_COUNT - 1; i >= 0; --i) {
            Node* n = &genome[2][i];
            if(n->isSign()) {
                std::unique_ptr<Node> t = std::make_unique<Node>(n->op);
                for(int r = 0; r < 2; ++r){
                    t->l[r] = std::move(st.top());
                    st.pop();
                }
                st.push(std::move(t));
            }
            else {
                st.push(std::make_unique<Node>(n->num));
            }
        }

        child->root = std::move(st.top());
        child->calcFitness();
    }

    return child;
}

int main() {
    std::srand(std::time(NULL));

    while(1){
        std::cout << "\n\n*** GENETIC ALGORITHM SOLUTION FOR EXPRESSION FINDING ***    Tolga Ay 13011057" << std::endl;
        std::cout << "\n Will you enter inputs? (y/n): ";
        char ans = ' ';
        do {
            ans = std::cin.get();
        } while(ans != 'y' && ans != 'n');
        if(ans == 'y') {
            std::cout << "\n Population Size: (e.g. 100): ";
            std::cin >> POPULATION_SIZE;
            std::cout << "\n Target Number: ";
            std::cin >> TARGET_NUM;
            std::cout << "\n Input Number Count: ";
            std::cin >> NUM_COUNT;

            for(int i = 0; i < NUM_COUNT; ++i) {
                std::cout << "\n Num #" << i << ": ";
                int num;
                std::cin >> num;
                numbers.push_back(num);
            }
        }
        else {
            POPULATION_SIZE = 20;
            TARGET_NUM = 72;
            NUM_COUNT = 6;
            numbers = {1, 3, 4, 7, 8, 9};
        }
        std::cout << "\n" << "Target number: " << TARGET_NUM << std::endl;

        POPULATION_SIZE = 5000;
        NODE_COUNT = 2*NUM_COUNT - 1;
        SIGN_COUNT = NUM_COUNT - 1;

        // Initialize the population
        std::vector<std::unique_ptr<Tree>> population(POPULATION_SIZE);
        std::cout << "Population size " << population.size() <<  "\n"<< std::endl;
        for(unsigned i = 0; i < population.size(); ++i) population[i] = std::make_unique<Tree>();

        // Create new generations
        bool found = false;
        for(int t = 0; t < MAX_GENERATION && !found; ++t) {
            std::vector<std::unique_ptr<Tree>> new_population;

            // Create new children
            for(unsigned i = 0; i < population.size(); ++i) {
                //std::cout << "\nCreating new child...";
                std::unique_ptr<Tree> child = crossOver(randomSelection(population), randomSelection(population));

                if(child->root->calc() == TARGET_NUM) {
                    std::cout << "Generation: " << t << "\t\tChild #" << i <<  "     Found answer: " << child->root->toString() << " = " << child->root->calc() << std::endl;
                    found = true; break;
                }
                new_population.push_back(std::move(child));
            }
            if(found) break;

            // Make the new population, current population
            for(unsigned i = 0; i < population.size(); ++i) population[i] = std::move(new_population[i]);

            // Find the best child
            float max_fitness = 0;
            Tree* best = population[0].get();
            for(unsigned i = 0; i < population.size(); ++i) {
                if(population[i]->getFitness() > max_fitness) {
                    max_fitness = population[i]->getFitness();
                    best = population[i].get();
                }
            }
            std::cout << "Generation: " << t << "\t\tBest Child: " << best->root->toString() << " = " << best->root->calc() << std::endl;
        }
    }
    return 0;
}