Genetic Algorithms in C++

Genetic Algorithms in C++

·

3 min read

Many aspects of modern technology have been inpired by biology:

  • Air conditioning from termite nests - warm air rises into a network of air ducts near the surface. There, stale air diffuses out the porous sides. Fresh cool air seeps in and descends into an air chamber at the bottom of the mound where it circulates into the nest.

    Termite mound cooling systems | Termites, Termite control, Passive cooling

  • Airplane wings from birds - The curvature of the bird’s wing gives the lift needed to overcome the downward pull of gravity. To avoid a stall, the bird has on the leading edges of its wings rows, or flaps, of feathers that pop up as wing tilt increases, illustrated in blue. These flaps maintain lift by keeping the main airstream from separating from the wing surface. Additionally the alula, a small bunch of feathers that the bird can raise up like a thumb controlling turbulence and preventing “stalling out”, illustrated in orange.

Genertic Algorithms

What are they?

A genetic algorithm is based on the ideas of natural selection. It is an adaptive search algorithm that solves problems of optimisation, copying the process of nature.

It is a heuristic, meaning it uses a problem-solving technique where the most appropriate solution is found by selecting data at successive stages of the program to use in the next step of the program, relying on biologically inspired operators such as mutation, crossover and selection.

Crossover, also called recombination, is a genetic operator used to combine the genetic information of two parents to generate new offspring.

Some examples of genetic algorithm applications include optimising decision trees for better performance, solving sudoku puzzles, hyperparameter optimization, causal inference

Applied in Code

I wanted to make a basic program to demonstrate how these algoirthms work.

Following the diagram below, I created some random initial data, ran a fitness evaluation on it, picked the best outcomes then combined the data to restart the process.

The process can be visualised using coloured squares.

struct Solution
{
    double rank, x, y, z;
    // Fitness evalutation
    void fitness()
    {
        double sol = (6 * x + -y + std::pow(z, 200)) - 25;
        // Closer solution is to 0, the higher the rank (closest fit)
        rank = (sol == 0) ? 9999 : std::abs(1/sol);
    }
};

int main()
{
    // Initial random solutions of numbers between -100 and 100
    std::random_device device;
    std::uniform_real_distribution<double> unif(-100, 100);
    std::vector<Solution> solutions;
    const int NUM = 1000;
    // New solutions with 0 ranking, then random numbers to x, y, z
    for (int i = 0; i<NUM; i++)
    { 
        solutions.push_back(Solution{
            0, 
            unif(device),
            unif(device), 
            unif(device)
        });
    }

    while(true)
    {
        // Check fitness of solutions then sort by rank
        for(auto& s: solutions) {s.fitness();} std::sort(solutions.begin(), solutions.end(), [](const auto& lhs, const auto& rhs)
        {
            return lhs.rank > rhs.rank;
        });

        // Print the first ten solutions
        std::for_each(solutions.begin(), solutions.begin() + 10, [](const auto& s){
            std::cout << std::fixed << "Rank " << static_cast<int>(s.rank) 
            << "\n x: " << s.x << " y: " << s.y << " z: " << s.z << "\n";
        });

        // Discard bottom set
        const int SAMPLE_SIZE = 10;
        std::vector<Solution> sample;
        std::copy(solutions.begin(), solutions.begin() + SAMPLE_SIZE, std::back_inserter(sample));
        solutions.clear();

        // Mutate solutions by 1%
        std::uniform_real_distribution<double> m(0.99, 1.01);
        std::for_each(sample.begin(), sample.end(), [&](auto& s){
            s.x *= m(device);
            s.y *= m(device);
            s.z *= m(device);
        });

        // Cross over
        std::uniform_int_distribution<int> cross(0, SAMPLE_SIZE-1);
        for(int i = 0; i<NUM; i++)
        {
            solutions.push_back(Solution{
                0,
                sample[cross(device)].x,
                sample[cross(device)].x,
                sample[cross(device)].x,
            });
        }
    }
};
Â