Genetic C++ programming with Brainfuck

Question

This was a project I worked on for fun that basically uses a genetic algorithm to produce simple Brainfuck programs that output whatever the user specifies.

I was just was hoping for criticism of the code, mainly if I'm doing anything blatantly wrong. I'm not too familiar with the STL, so there may have been algorithms I could've used from there but I'm not sure. I realize this is a somewhat decent amount of code, so if you just want to focus on a single function or section, that's fine.

/**************************************************************************************************************
 * Brainfuck Evolved                                                                                          *
 * Written by Kurtis Dinelle (http://kurtisdinelle.com)                                                       *
 *                                                                                                            *
 * This program attemps to write programs of its own in the brainfuck language, using a genetic algorithm.    *
 * The fitness function will take into account how close the output matches, and how concise the program is.  *
 * Shorter programs receive a slight bonus.                                                                   *
 **************************************************************************************************************/

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include "interpreter.h"

// Don't modify this group of constants.
const unsigned CHAR_SIZE = 255;  // The max value of a 'cell' in the memory tape.
const unsigned NUM_MUTATIONS = 3;  // The number of types of mutations: (ADD, DELETE, CHANGE).
const char INSTRUCTIONS[] = {'+', '-', '>', '<', '[', ']', '.'};  // The list of brainfuck instructions.
const unsigned NUM_INSTRUCTIONS = (sizeof(INSTRUCTIONS) / sizeof(INSTRUCTIONS[0]));  // Holds the number of instructions allowed.
const unsigned NUM_CHILDREN = 2;  // Number of children two parents create upon reproduction.

// Modify any constants below.
const unsigned POP_SIZE = 10;  // The size of the population. This always remains the same between generations.
const unsigned MIN_PROGRAM_SIZE = 10;  // The minimum size a possible program can be.
const unsigned MAX_PROGRAM_SIZE = 500;  // The maximum size a possible program can be.
const double MUTATION_RATE = 0.01;  // The chance of a 'gene' in a child being mutated.
const double ERROR_SCORE = 1.0;  // The score an erroneous program receives.
const double LENGTH_PENALTY = 0.001;  // The size of the program is multiplied by this then added to score.
const unsigned DISPLAY_RATE = 10000;  // How often to display the best program so far.

// These aren't constant because they can be changed by the user.
std::string GOAL_OUTPUT = "Robots";
size_t GOAL_OUTPUT_SIZE = GOAL_OUTPUT.length();



/* These two functions used to generate either a random double or unsigned int.
   Why didn't I just overload one function? Slipped my mind at the time. */
double get_random(double low, double high)
{
    return low + static_cast<double>(rand()) / static_cast<double>(static_cast<double>(RAND_MAX) / (high - low));
}

unsigned get_random_int(unsigned low, unsigned high)
{
    return (rand() % (high - low + 1)) + low;
}


char get_random_instruction()
{
    return INSTRUCTIONS[get_random_int(0, NUM_INSTRUCTIONS - 1)];
}


void add_instruction(std::string &program, unsigned index)
{
    std::string instr(1, get_random_instruction());  // Need to convert char to string for use by insert.

    if((program.length() + 1) <= MAX_PROGRAM_SIZE)
        program.insert(index, instr);
}


void remove_instruction(std::string &program, unsigned index)
{
    // Subtract 2 instead of 1 to account for the off-by-one difference between a string length and the last element index.
    if((program.length() - 2) >= MIN_PROGRAM_SIZE)
        program.erase(index, 1);
}


void mutate_instruction(std::string &program, unsigned index)
{
    program[index] = get_random_instruction();
}


// Creates a random program by first randomly determining its size and then adding that many instructions randomly.
std::string create_random_program()
{
    std::string program;
    unsigned program_size = get_random_int(MIN_PROGRAM_SIZE, MAX_PROGRAM_SIZE);

    for(unsigned i = 1; i <= program_size; ++i)
        program += get_random_instruction();

    return program;
}


// Creates the first generation's population by randomly creating programs.
void initialize_population(std::string programs[])
{
    for(unsigned i = 0; i < POP_SIZE; ++i)
        programs[i] = create_random_program();
}


// The Fitness Function. Determines how 'fit' a program is using a few different criteria.
double calculate_fitness(const std::string &program, Interpreter &bf)
{
    // The score of the worst program possible (Besides erroneous program, and not taking into account program length).
    double max_score = GOAL_OUTPUT_SIZE * CHAR_SIZE;
    double score = 0;
    double final_score;

    std::string output = bf.run(program);

    // Impose a very large penalty for error programs, but still allow them a chance at reproduction for genetic variation.
    if(output == Interpreter::ERROR)
        return ERROR_SCORE;

    /* We need to know whether the goal output or the program's output is larger
       because that's how many iterations of the next loop need to be done. */
    std::string min_str = (output.length() < GOAL_OUTPUT.length()) ? output : GOAL_OUTPUT;
    std::string max_str = (output.length() >= GOAL_OUTPUT.length()) ? output : GOAL_OUTPUT;

    // The more each character of output is similar to its corresponding character in the goal output, the higher the score.
    for(size_t i = 0; i < max_str.length(); ++i)
    {
        unsigned output_char = (i < min_str.length()) ? min_str[i] : max_str[i] + CHAR_SIZE;
        score += abs(output_char - max_str[i]);
    }

    score += (program.length() * LENGTH_PENALTY);  // Impose a slight penalty for longer programs.

    /* The lower the score of a program, the better (think golf).
       However other calculations in the program assume a higher score is better.
       Thus, we subtract the score from max_score to get a final score. */
    final_score = max_score - score;

    return final_score;
}


/* Generates a fitness score for each program in the population.
   This is done by running the program through the brainfuck interpreter and scoring its output.
   Also returns the best program produced. */
std::string score_population(const std::string programs[], double scores[], int &worst_index, Interpreter &bf)
{
    std::string best_program;
    double best_score = 0;
    double worst_score = 9999;  // Arbitrarily high number.

    for(unsigned i = 0; i < POP_SIZE; ++i)
    {
        scores[i] = calculate_fitness(programs[i], bf);

        if(scores[i] > best_score)
        {
            best_program = programs[i];
            best_score = scores[i];
        }
        else if(scores[i] < worst_score)
        {
            worst_index = i;
            worst_score = scores[i];
        }
    }

    return best_program;
}


// Adds every program's fitness score together.
double pop_score_total(const double scores[])
{
    double total = 0;

    for(unsigned i = 0; i < POP_SIZE; ++i)
        total += scores[i];

    return total;
}


/* Selects a parent to mate using fitness proportionate selection.
   Basically, the more fit a program is, the more likely it is to be selected. */
std::string select_parent(const std::string programs[], const double scores[], const std::string &other_parent = "")
{
    double program_chances[POP_SIZE];  // Holds each program's chance of being selected (a # between 0 and 1).
    double score_total = pop_score_total(scores);
    double rand_val = get_random(0.0, 1.0);

    for(unsigned i = 0; i < POP_SIZE; ++i)
    {
        // Cast i to int so when we go to subtract 1, if i is 0 it doesn't overflow (as an unsigned int can't be negative).
        double prev_chance = ((static_cast<int>(i) - 1) < 0) ? 0 : program_chances[i - 1];

        /* We add the previous program's chance to this program's chance because that is its range of being selected.
           The higher the fitness score, the bigger this program's range is. */
        program_chances[i] = (scores[i] / score_total) + (prev_chance);

        // Need to subtract a small amount from rand_val due to floating-point precision errors. Without it, equality check could fail.
        if(program_chances[i] >= (rand_val - 0.001) && (programs[i] != other_parent))
            return programs[i];
    }

    /* If the other parent was the last program in the list, we might get here.
       In that case, just return the 1st program. */
    return programs[0];
}


/* Mutates a program by either inserting, removing, or changing an instruction.
   This returns a string rather than modifying a a string just due to the way it is used in the program. */
std::string mutate(std::string child)
{
    // Loop through each command and randomly decide to mutate it based on the mutation rate.
    for(size_t i = 0; i < child.length(); ++i)
    {
        if(MUTATION_RATE >= get_random(0.0, 1.0))
        {
            unsigned mutation_type = get_random_int(1, NUM_MUTATIONS);

            switch(mutation_type)
            {
            case 1:
                mutate_instruction(child, i);
                break;
            case 2:
                add_instruction(child, i);
                break;
            case 3:
                remove_instruction(child, i);
                break;
            default:
                break;
            }
        }
    }

    return child;
}


// Performs crossover between two parents to produce two children.
void mate(const std::string &parent1, const std::string &parent2, std::string children[])
{
    // We need to find which program is longest.
    std::string min_str = (parent1.length() < parent2.length()) ? parent1 : parent2;
    std::string max_str = (parent1.length() >= parent2.length()) ? parent1 : parent2;

    // Determine a crossover point at random.
    unsigned crosspoint = get_random_int(1, max_str.length() - 1);

    // Find the substring of the program after the crossover point
    std::string max_str_contrib = max_str.substr(crosspoint);

    // Then erase after that point
    max_str.erase(crosspoint);

    /* If the cross-over point is less than the length of the smaller program, then we need to combine part of it with the larger program.
       If not, then we do nothing and just take part of the larger program and add it to it. */
    if(crosspoint <= min_str.length())
    {
        max_str += min_str.substr(crosspoint);
        min_str.erase(crosspoint);
    }

    // Add the 2nd part of the larger program to the smaller program.
    min_str += max_str_contrib;

    // Call the mutate function on the children which has a small chance of actually causing a mutation.
    children[0] = mutate(min_str);
    children[1] = mutate(max_str);
}


bool program_exists(const std::string &program, const std::string programs[])
{
    for(unsigned i = 0; i < POP_SIZE; ++i)
    {
        if(program == programs[i])
            return true;
    }

    return false;
}


void replace_program(const std::string &parent, const std::string &child, std::string programs[])
{
    for(unsigned i = 0; i < POP_SIZE; ++i)
    {
        if(parent == programs[i])
        {
            programs[i] = child;
            break;
        }
    }
}


int main(int argc, char *argv[])
{
    // Check if ran from command line.
    if(argc > 1)
    {
        GOAL_OUTPUT = argv[1];
        GOAL_OUTPUT_SIZE = GOAL_OUTPUT.length();
    }

    // Initialize the brainfuck interpreter and seed random.
    Interpreter brainfuck;
    srand(time(0));

    std::string programs[POP_SIZE];
    double fitness_scores[POP_SIZE];

    initialize_population(programs);

    std::string best_program;

    bool keep_going = false;  // Just used to have the program keep searching after a match is found.

    unsigned long generations = 0;

    // And now we just repeat the process of selection and reproduction over and over again.
    while(1)
    {
        int worst_program_index = 0;

        best_program = score_population(programs, fitness_scores, worst_program_index, brainfuck);

        // Select two parents randomly using fitness proportionate selection
        std::string parent1 = select_parent(programs, fitness_scores);
        std::string parent2 = select_parent(programs, fitness_scores, parent1);

        // Mate them to create children
        std::string children[NUM_CHILDREN];
        mate(parent1, parent2, children);

        /* Replace the parent programs with the children. We replace the parents to lessen the chance of premature convergence.
           This works because by replacing the parents, which are most similar to the children, genetic diversity is maintained.
           If the parents were not replaced, the population would quickly fill with similar genetic information. */
        replace_program(parent1, children[0], programs);
        replace_program(parent2, children[1], programs);

        /* Replace the worst program with the best program if it was replaced by its child. (Elitism).
           This is done to ensure the best program is never lost. */
        if(!program_exists(best_program, programs))
            programs[worst_program_index] = best_program;

        // Report on the current best program every so often.
        if(!(generations % DISPLAY_RATE))
        {
            std::cout << "\n\nBest program evolved so far: " << std::endl;
            std::cout << best_program << std::endl;

            std::string output = brainfuck.run(best_program);
            std::cout << "\nOutput: " << output << std::endl;

            if(output == GOAL_OUTPUT && !keep_going)
            {
                std::cout << "\n\a\a\aProgram evolved!" << std::endl;
                std::cout << "Save source code as a text file? (y/n) ";

                char answer;
                std::cin >> answer;

                if(answer == 'y')
                {
                    std::ofstream srcfile("bfsrc.txt");
                    srcfile << GOAL_OUTPUT << ":\n\n" << best_program;
                    std::cout << "Source code saved as 'bfsrc.txt'\n" << std::endl;
                }

                //std::cout << "It took roughly " << generations << " generations to evolve this program." << std::endl;
                std::cout << "Keep evolving for more efficiency? (y/n) ";
                std::cin >> answer;

                // Quit the program if the user doesn't want to continue.
                if(answer != 'y')
                    return 0;

                keep_going = true;
            }
        }

        ++generations;
    }

    return 0;
}

Answer 1

There's quite a bit of code here, so I'm not going to get through all of it, but I'll do as much as possible. Also, since I don't have access to your interpreter.h, I can't guarantee everything I've written will compile; there may be syntax errors and a few bugs lurking around, so consider yourself forewarned.

I think in general this is a fun idea, so kudos for that. However, the way it is written is very much C-style with std::string thrown in. I'm going to endeavour to give you a reasonable chunk of it rewritten in modern-style C++, explaining as much as I can along the way. I'll start by separating out a few things that I think can be encapsulated nicely in separate classes.

The first class will be responsible for random number generation and random selection. I'm going to give it the (not fantastic, admittedly) name of random_generator. Further, this is going to replace rand() (which is, without mincing words, pretty much crap), with the pseudo-random generation supplied by C++11:

#include <random>

class random_generator
{
private:

    std::random_device rand_dev;
    std::mt19937       generator;

public:

    random_generator()
      : generator(rand_dev())
    { }

    double next(double low, double high)
    {
        std::uniform_real_distribution<> dist(low, high);
        return dist(generator);
    }

    std::size_t next(std::size_t low, std::size_t high)
    {
        std::uniform_int_distribution<std::size_t> dist(low, high);
        return dist(generator);
    }

    template <typename Sequence>
    typename Sequence::value_type select(const Sequence& seq)
    {
        std::size_t index = next(0, seq.size() - 1);
        return seq[index];
    }
};

The parts that make up this class may be unfamiliar (and a fair bit more complex than simply calling rand()), but will produce much "better" random numbers. std::mt19937 is simply a source of pseudo-randomness to draw from. From this, we can use uniform_real_distribution and uniform_int_distribution. These generate uniformly distributed numbers that lie between (and including) the 2 parameters passed in.

The final function utilises templates to pick random values from any container satisfying operator[]: so things like std::vector and std::array.

Let's move on to the actual brainfuck program itself. We'll again make a class (named, inventively, brainfuck_program) that encapsulates a single program:

#include <vector>

class brainfuck_program
{
private:

    static const std::vector<char> instructions;
    static constexpr unsigned num_children = 2;
    static constexpr unsigned char_size = 255; 
    static constexpr unsigned num_mutations = 3;

    random_generator rand_gen;
    std::string      current_program;

public:

    const std::size_t max_program_size;
    const std::size_t min_program_size; 

    brainfuck_program(std::size_t max_size, std::size_t min_size)
      : max_program_size(max_size),
        min_program_size(min_size)
    { }

    char random_instruction()
    {
        return rand_gen.select(instructions);
    }

    bool add_instruction(std::size_t index)
    {
        if(index < max_program_size) {
            current_program.insert(index, 1, random_instruction());
            return true;
        }
        return false;
    }

    bool remove_instruction(std::size_t index)
    {
        if(current_program.size() - 2 >= min_program_size) {
            program.erase(index, 1);
            return true;
        }
        return false;
    }

    void mutate_instruction(std::size_t index)
    {
        current_program[index] = random_instruction();
    }

    double fitness(Interpreter& bf)
    {
        ...
    }

private:

    void create_random_program()
    {
        std::size_t program_size = rand_gen.next(min_program_size, max_program_size);
        for(std::size_t i = 0; i < program_size; ++i) {
            program += random_instruction();
        }
    } 
};

const std::vector<char> brainfuck_program::instructions = {'+', '-', '>', '<', '[', ']', '.'};  

bool operator==(const brainfuck_program& b1, const brainfuck_program& b2)
{
    return b1.current_program == b2.current_program;
}

Here, I've moved a lot of the global variables to do with brainfuck programs into static class variables (since they shouldn't be changed by the user, they should be the same for all generated brainfuck programs).

Many of the functions that simply operated on a passed in std::string before are now member functions. They now modify a (class private) string instead. The code itself hasn't changed all that much, although we're now using the random_generator class that we defined before to select our random instructions for us. Also, the string that encapsulates the program is initiated when the constructor is called.

Finally, we'll look at a class that is designed to deal with populations of brainfuck programs. Let's call it population_manager:

#include <vector>
#include <numeric>
#include <set>
#include <iterator>
#include <utility>

class population_manager
{
private:

    using prog_score_pair = std::pair<double, brainfuck_program>;

    struct score_sorter
    {
        bool operator()(const prog_score_pair& p, const prog_score_pair& t) const
        {
            return s.second > t.second;
        }
    };

    std::vector<brainfuck_program>          populations;
    std::set<prog_score_pair, score_sorter> population_scores;

public:

    const std::size_t population_size;

    population(std::size_t pop_size)
      : population_size(pop_size),
        populations(population_size)
    { }

    std::pair<brainfuck_program, std::size_t> 
    score_population(Interpreter& bf)
    {
        using prog_inserter = std::insert_iterator<std::set<prog_score_pair, score_sorter>>;
        std::transform(populations.begin(), populations.end(), std::prog_inserter,
                       [&](const brainfuck_program& p) 
                       {
                            auto score = p.fitness(bf); 
                            return std::make_pair(score, p); 
                       });

        return *population_scores.begin();
    }

    double score_total() const
    {
        return std::accumulate(population_scores.begin(), population_scores.end(),
                               0.0, [](const prog_score_pair& p1, const prog_score_pair& p2)
                                    { return p1.first + p2.first; });
    }

 // Other methods...

};

This is more incomplete that the other two classes, but hopefully gives you an outline. Firstly, we use a std::set to store programs in sorted order (descending in this case) of their scores. This allows fast access to each score in order. You lose the ability to find the worst_index (which you use in score_population currently), however this is unused in the rest of the program.

So, that's a fair whack of code, and some of it probably looks a bit strange (depending on your familiarity with some C++ features). What have we gained from this?

1. More type safety: Currently, every program is just a string. Now, that string cannot be accessed directly, but can only be generated and modified through our class interface. This gives us guarantees that certain invariants will be satisfied, and there is less possibility for bugs.

2. We've broken things up into (possibly) reusable pieces. Also, we've separated out things that are logically distinct: random generation is completely separated from the brainfuck programs itself.

3. Logical grouping of things that are NOT distinct. We've removed a lot of global state from the program (to be fair, much of it was const global state, which isn't nearly as bad), but this method makes it more obvious what settings affect what pieces.

Again, apologies in advance for any bugs/syntax errors in what I've shown.