C++ Genetic algorithm with templates

Question

This is a genetic algorithm I made. Currently, it seems to be flexible enough for my purposes. Since I am quite new to c++, I'd like to know what you think.

I am uncertain about several things and looking for advice!

• Probably there are unnecessarily copying of whole Candidates. Where do they actually happen? How to avoid them? Should I use smart_ptrs?

• Am I using static template function correctly, with the crossover method?

• Is it Ok, to have whole template classes in a header file?

At the bottom, there is a simple usage that finds out a simple text.

GA.hpp

namespace GA{
    // Candidate
    template<class T, size_t SIZE>
    class Candidate{
    public:
        std::array<T, SIZE> genes{};
        float cost {std::numeric_limits<float>::infinity()};

        void mutate(float mutation_rate){
            /*!
             this is called to mutate a candidate
             */
            return tweak_mutate(mutation_rate);
        }

        template<class TT>
        static std::array<TT, 2> crossover(TT const & mother, TT const & father, float crossover_rate){
            /*!
             this is called to create children form parents
             */
            return uniform_crossover(mother, father, crossover_rate);
        }

        // Mutation Techniques
        void tweak_mutate(float mutation_rate){
            for (auto cell_idx=0; cell_idx < genes.size(); cell_idx++) {
                if (RANDOM_NUM < mutation_rate) {
                    genes[cell_idx] += RANDOM_NUM<0.5 ? -1 : +1;
                }
            }
        }

        // Crossover Techniques
        template<class TT>
        static std::array<TT, 2> uniform_crossover(TT const & mother, TT const & father, float crossover_rate){
            auto child1 = mother;
            auto child2 = father;
            if (RANDOM_NUM < crossover_rate)
                for(auto cell=0; cell < mother.genes.size(); cell++){
                    if(RANDOM_NUM < 0.5)
                        std::swap(child1.genes[cell], child2.genes[cell]);
                }

            return std::array<TT, 2>({child1, child2});
        }
    };

    // Population
    template<class T>
    class Population{
    public:
        std::vector<T> candidates;
        unsigned int generation{0};

        void init(size_t size){
            candidates.clear();
            generation = 0;
            for(auto i=0; i<size; i++){
                T candidate;
                candidates.push_back(candidate);
            }
        }

        std::array<T, 2> tournament_selection(){
            size_t tournament_size = 2;
            std::array<T, 2> parents; //select two parents;

            for(auto i=0; i<parents.size(); i++){
                T leader = candidates[rand()%candidates.size()];
                for(auto j=0; j<tournament_size; j++){
                    T opponent = candidates[rand()%candidates.size()];
                    if(opponent.cost <  leader.cost)
                        leader = opponent;
                }
                parents[i] = leader;
            }
            return parents;
        }

        void breed(){
            std::vector<T> offsprings;
            while(offsprings.size() < candidates.size()){
                std::array<T, 2> parents = tournament_selection();
                std::array<T, 2> children = T::crossover(parents[0], parents[1], 0.3);

                for(auto & child : children)
                    child.mutate(0.003);

                for(auto const & child : children)
                    offsprings.push_back(child);
            }
            std::swap(candidates, offsprings);
            generation++;
        }
    };
};

main.cpp

example usage to find out a simple text

#include <iostream>
#include <stdio.h>
#include "TemplateGA.hpp"

struct MyCandidate : public GA::Candidate<unsigned char, 28>{
    std::string phenotype;
};

std::string decode(MyCandidate const & candidate){
    std::string text = "";
    for(auto cell : candidate.genes)
        text += (char)cell;
    return text;
}

float distance(std::string const & a, std::string const & b){
    float d{0};
    size_t length = std::min(a.size(), b.size());
    for(auto i=0; i<length;i++){
        d += abs((int)a[i] - (int)b[i]);
    }
    return 1.0 * d/length;
}

int main(int argc, const char * argv[]) {
    // insert code here...

    // initalize
    GA::Population<MyCandidate> pop;
    pop.init(9);

    while(true) {
        // evaluate
        for(auto & candidate : pop.candidates){
            candidate.phenotype = decode(candidate);
            candidate.cost = distance(candidate.phenotype, "Whats up, Genetic Algorhytm!");
        }

        // show population
        std::cout << pop.generation << std::endl;
        for(auto & candidate : pop.candidates){
            std::cout << candidate.phenotype << " | " << candidate.cost << std::endl;
        }

        // breed population
        pop.breed();
    };

    return 0;
}

Answer 1

I haven't really studied your code, or tried to run it, but I'll take a swing at answering your questions. I'm going to answer them in reverse order.

Is it Ok, to have whole template classes in a header file?

Definitely yes. In fact, this is the only way to do templates (for now; modules may change things).

Am I using static template function correctly, with the crossover method?

That's a broad question, with lots of valid answers, so I'll have to guess at what you're getting at.

Consider the two static functions below:

template <typename T, std::size_t SIZE>
struct Candidate
{
    static auto func1() -> void {}

    template <typename TT>
    static auto func2() -> void {}
}

The full signature for the two functions are:

template <typename T, std::size_t Size>
auto Candidate<T, Size>::func1() -> void;

template <typename T, std::size_t Size>
template <typename TT>
auto Candidate<T, Size>::func2<TT>() -> void;

You see, func1() is a function within a class template, while func2() is a function template within a class template.

I'm pretty sure your intention isn't to make the crossover function a template within a template.

So what you probably mean to say is:

template<class T, size_t SIZE>
class Candidate{
public:
    // ...

    static std::array<Candidate<T, SIZE>, 2> crossover(Candidate<T, SIZE> const & mother, Candidate<T, SIZE> const & father, float crossover_rate){
        /*!
         this is called to create children form parents
         */
        return uniform_crossover(mother, father, crossover_rate);
    }

    // ...

And even better: inside the template class, the template arguments are inferred, you can just say Candidate instead of Candidate<T, SIZE>, to get:

template<class T, size_t SIZE>
class Candidate{
public:
    // ...

    static std::array<Candidate, 2> crossover(Candidate const & mother, Candidate const & father, float crossover_rate){
        /*!
         this is called to create children form parents
         */
        return uniform_crossover(mother, father, crossover_rate);
    }

    // ...

However!

Is there really any reason the crossover functions need to be static class functions?

Suppose I have a pair of Candidate<int, 32>, and I want to call crossover(). Here's what I'd have to do:

GA::Candidate<int, 32> c1;
GA::Candidate<int, 32> c1;

GA::Candidate<int, 32>::crossover(c1, c2);
// or
decltype(c1)::crossover(c1, c2);

That's kind of a pain.

Wouldn't it be nicer to be able to write:

GA::Candidate<int, 32> c1;
GA::Candidate<int, 32> c1;

crossover(c1, c2);

Thanks to argument dependent lookup (ADL), even the namespace is automatically determined.

There are a lot of good reasons to prefer free functions to member functions wherever possible - to many to begin to go into here. So rather than having your crossover functions as static member functions, perhaps you could instead move them out of the class:

template<class T, size_t SIZE>
class Candidate{
public:
    // Candidate class exactly as it is now, except with
    // crossover and uniform_crossover functions removed.
};

template <typename T, std::size_t SIZE>
std::array<Candidate<T, SIZE>, 2> crossover(Candidate<T, SIZE> const & mother, Candidate<T, SIZE> const & father, float crossover_rate){
    /*!
     this is called to create children form parents
     */
    return uniform_crossover(mother, father, crossover_rate);
}

// similarly for uniform_crossover()

Probably there are unnecessarily copying of whole Candidates. Where do they actually happen? How to avoid them? Should I use smart_ptrs?

Again answering your questions in reverse order (I hope that's not too annoying!)....

No, using smart pointers is almost always the wrong answer in C++. C++ has a thousand ways to get more efficient and safer code without relying on reference/handle semantics (which is what smart pointers are).

So let's track down copies function by function and see where improvements might be made.

In the Candidate class, there are no copies made in any functions except uniform_crossover(). Here's what it currently looks like (assuming it's moved out of the class and made a free function):

template <typename T, std::size_t SIZE>
std::array<Candidate<T, SIZE>, 2> uniform_crossover(Candidate<T, SIZE> const & mother, Candidate<T, SIZE> const & father, float crossover_rate){
    auto child1 = mother;
    auto child2 = father;
    if (RANDOM_NUM < crossover_rate)
        for(auto cell=0; cell < mother.genes.size(); cell++){
            if(RANDOM_NUM < 0.5)
                std::swap(child1.genes[cell], child2.genes[cell]);
        }

    return std::array<Candidate<T, SIZE>, 2>({child1, child2});
}

So you're going to need at least two copies here in any case, because you're copying the mother/father into two children then mutating them. But what you have in this function are four copies. First you copy mother and father into child1 and child2, then you swap genes, then you copy child1 and child2 into the array you return.

Instead, consider creating the array right at the start, and doing the copy right then and there. There is no need for the two variables child1 and child2. You could simply call the array children, and child1 will be children[0] and child2 will be children[1].

Arranging the function this way will also allow you to take advantage of named value return optimization (NRVO), meaning that in practice, there will only ever be 2 copies (your bare minimum) made in total for the whole function call, even counting client code.

(There is another technique in modern C++ that can, in some cases, make the total number of copies made zero. The way you'd do that is to take the two Candidate parameters by value, instead of by const &, and take advantage of move semantics. Unfortunately, because your class uses array members, this is one of the fairly rare situations where move semantics won't help you at all. So you might as well stick with const & parameters.)

So that's it for the Candidate class. Let's move on to Population.

In the init() function you initialize your population vector with a loop that creates candidates, then copies them into the vector. This is extremely inefficient. To see why, here's what would happen if size were 3:

1. create a candidate ((default) construct #1)
2. allocate space for the candidate in the vector (allocation #1)
3. copy the candidate into the vector ((copy) construct #2)
4. create a candidate ((default) construct #3)
5. allocate space for the candidate in the vector (allocation #2)
6. copy the candidate into the vector ((copy) construct #4)
7. create a candidate ((default) construct #5)
8. allocate space for the candidate in the vector (allocation #3)
9. copy the candidate into the vector ((copy) construct #6)

So for a population of 3, you need 3 allocations and 6 constructions, including 3 copies. What you want to aim for is a single allocation of size elements, and size default constructions in place in the vector. Can this be achieved?

If you check the documentation for vector, there are a ton of functions for adding elements: insert(), emplace(), push_back(), and so on... but you want to add multiple elements, and there are only 3 functions that can do that: the constructor, assign(), and insert(). You could use insert(), but there's really no point - insert() is for putting stuff in the middle of the vector, but the vector is empty. assign() seems an obvious choice. As a bonus, assign() automatically clears the vector before adding, so there's no need to call clear() anymore.

That turns the init() function into:

void init(size_t size){
    generation = 0;
    candidates.assign(size, T{});
}

Which is: 1 allocation, 1 default construct, and size copies. That's almost perfect. Can we get perfect?

We can, with a trick.

One of vector's constructors (#3) takes just a size argument. This does exactly what you want: it does a single allocation, then size default constructions.

But in init(), the vector is already constructed. We can't call the constructor on an already-constructed object.

But we can do this:

void init(size_t size){
    generation = 0;
    candidates = std::vector<T>(size);
}

This isn't a perfect solution, because if candidates already held size or more elements, assign() could skip the reallocation and just do the copying, but replacing the whole vector means doing the reallocation every time. But this is a symptom of another issue.

The problem is that an init() function is almost always a bad idea. That is a technique called "two-phase initialization", and except in special circumstances, it's something to avoid in C++.

init() should be a constructor:

explicit Population(size_t size) :
    generation{0}, // don't even need this, because it's 0 by default
    candidates(size)
{
    // nothing needed here
}

And in main(), instead of:

GA::Population<MyCandidate> pop;
pop.init(9);

you'd do:

GA::Population<MyCandidate> pop(9);

I think that's enough for an initial review. There are some improvements that could be made to the other two functions in Population, but they'd require some deeper architectural changes.

I'll finish off with some general points:

• size_t should be std::size_t, and don't forget to include one of the required headers.
• You have a lot of for loops. Consider using algorithms instead. They're safer, self-documenting, and can be faster. Also, check for member functions that do what your loop does. I mentioned the loop in init(), but there's also one in breed() that could use vector::insert().
• Avoid C-style casts.
• Don't use rand(). It's probably garbage, and it's really hard to use properly (in fact, you're using it wrong). Use the modern C++ random number facilities in <random>.

Hope this helps!