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>, typename Gene = GeneArray::value_type>
    class GeneticAlgorithm
    {
    public:
        typedef GAPopulation<GeneArray, Compare> Population;

    private:
        std::vector<Gene> candidates;

        bool unique;

        double mutationRate;

        size_t tournament;

    public:
        GeneticAlgorithm(const std::vector<Gene> &candidates, bool unique, double mutationRate = 0.015, size_t tournament = 10)
        {
            this->candidates = candidates;
            this->unique = unique;

            this->mutationRate = mutationRate;
            this->tournament = tournament;
        };

        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> geneArray, size_t population, size_t generation) const -> std::shared_ptr<GeneArray>
        {
            std::shared_ptr<Population> myPopulation(new Population(geneArray, 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> geneArray(new GeneArray(*parent1));
            size_t size = parent1->size();

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

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

                //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;

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

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

                if (candidates.empty() == true)
                {
                    // WHEN CANDIDATES ARE NOT SPECIFIED, JUST SHUFFLE SEQUENCE OF GENES
                    size_t j = (size_t)(Math::random() * geneArray->size());
                    std::swap(geneArray->at(i), geneArray->at(j));
                }
                else if (unique == false)
                {
                    // PICK A CANDIDATE
                    geneArray->at(i) = candidates.at((size_t)(Math::random() * candidates.size()));
                }
                else // HAS CANDIDATES AND NEED TO BE UNIQUE
                {
                    Gene item;
                    bool duplicated = true;

                    // PICK ONE
                    while (duplicated == true)
                    {
                        item = candidates.at((size_t)(Math::random() * candidates.size()));

                        duplicated = false;

                        for (size_t j = 0; j < geneArray->size(); j++)
                            if (i != j && geneArray->at(i) == geneArray->at(j))
                            {
                                duplicated = true;
                                break;
                            }
                    }

                    geneArray->at(i) = item;
                }
            }
        };
    };
};
};