GeneticAlgorithm.hpp

#pragma once

#include <samchon/library/GAPopulation.hpp>

#include <set>
#include <random>
#include <samchon/library/Math.hpp>

namespace samchon
{
namespace library
{
    template <typename GeneArray, typename Compare = std::less<GeneArray>>
    class GeneticAlgorithm
    {
    public:
        typedef GAPopulation<GeneArray, Compare> Population;

    protected:
        bool unique;

        double mutationRate;

        size_t tournament;

    public:
        GeneticAlgorithm(bool unique, double mutationRate = 0.015, size_t tournament = 10)
        {
            this->unique = unique;
            this->mutationRate = mutationRate;
            this->tournament = tournament;
        };

        inline auto evolveGeneArray(std::shared_ptr<GeneArray> individual, size_t population, size_t generation) const -> std::shared_ptr<GeneArray>
        {
            std::shared_ptr<Population> myPopulation(new Population(individual, population));

            for (size_t i = 0; i < generation; i++)
                myPopulation = evolvePopulation(myPopulation);

            return myPopulation->fitTest();
        };

        auto evolvePopulation(std::shared_ptr<Population> population) const -> std::shared_ptr<Population>
        {
            size_t size = population->children.size();
            std::shared_ptr<Population> evolved(new Population(size));

            //ELITICISM
            evolved->children[0] = population->fitTest();

            #pragma omp parallel for
            for (int i = 1; i < size; i++)
            {
                std::shared_ptr<GeneArray> &gene1 = selection(population);
                std::shared_ptr<GeneArray> &gene2 = selection(population);

                std::shared_ptr<GeneArray> &child = crossover(gene1, gene2);
                mutate(child);

                evolved->children[i] = child;
            }

            /*#pragma omp parallel for
            for (int i = 1; i < size; i++)
                mutate(evolved->children[i]);*/

            return evolved;
        };

    private:
        auto selection(std::shared_ptr<Population> population) const -> std::shared_ptr<GeneArray>
        {
            size_t size = population->children.size();
            Population tornament(size);

            for (size_t i = 0; i < size; i++)
            {
                size_t randomIndex = (size_t)(Math::random() * size);
                if (randomIndex == size)
                    randomIndex--;

                tornament.children[i] = population->children[randomIndex];
            }
            return tornament.fitTest();
        };

        auto crossover(std::shared_ptr<GeneArray> &parent1, std::shared_ptr<GeneArray> &parent2) const -> std::shared_ptr<GeneArray>
        {
            std::shared_ptr<GeneArray> individual(new GeneArray(*parent1));
            size_t size = parent1->size();

            if (unique == false)
            {
                for (size_t i = 0; i < size; i++)
                    if (Math::random() > .5)
                        individual->at(i) = parent2->at(i);
            }
            else
            {
                std::set<GeneArray::value_type> ptrSet;
                std::set<size_t> indexSet;

                // RANGES
                size_t start = (size_t)(Math::random() * size);
                size_t end = (size_t)(Math::random() * size);

                if (start > end)
                    std::swap(start, end);

                //INDEXING
                for (size_t i = 0; i < size; i++)
                    if (start <= i && i < end)
                        ptrSet.insert(parent1->at(i));
                    else
                        indexSet.insert(i);

                //INSERT PARENT_2
                for (size_t i = 0; i < size; i++)
                {
                    GeneArray::value_type &ptr = parent2->at(i);
                    if (ptrSet.find(ptr) != ptrSet.end())
                        continue;

                    individual->at(*indexSet.begin()) = ptr;
                    indexSet.erase(indexSet.begin());
                }
            }
            return individual;
        };

    protected:
        virtual void mutate(std::shared_ptr<GeneArray> individual) const
        {
            for (size_t i = 0; i < individual->size(); i++)
            {
                if (Math::random() > mutationRate)
                    continue;

                // JUST SHUFFLE SEQUENCE OF GENES
                size_t j = (size_t)(Math::random() * individual->size());
                std::swap(individual->at(i), individual->at(j));
            }
        };
    };
};
};