DLG.cpp

void CSADlg::InitPopulation(void)
{
    for (int i = 0; i < NCREAT; i++)
    {
        cs.population[i] = cs.create_random();
    }
}

void CSADlg::OnStart() 
{

    std::ofstream log ("log.txt", std::ios::app | std::ios::out);

    for (int i = 0; i < 1000; ++i) {
        for (int j = 0; j < 10; ++j) {
            cs.advance_generation();
        }

        auto const& bestEntity = cs.get_best();

        double perf = cs.eval_perf(bestEntity);

        for (unsigned i = 0; i < NCITIES; ++i) {
            log << bestEntity.getPath()[i] << " ";
            path[i] = bestEntity.getPath()[i];
        }
        log << "\n";

        
        double S = 0.0;
        for (unsigned i = 0; i < cs.population.size(); ++i) {
            S += cs.perf_cache[i];
        }

        //length = 1.0 / (perf / 100.0);
        length = S;

        Draw();
    }
}

Entity.hpp

#pragma once

#include <random>
#include <array>
#include <set>
#include <fstream>
// various utils
const unsigned NCITIES = 50;             /*liczba miast - nie zmieniac!*/
const unsigned NCREAT = 20;              /*liczebnosc populacji*/

static std::mt19937 random_engine((std::random_device()()));

inline double get_random_double (double max) {
    std::uniform_real_distribution<double> dist(0, max);
    return dist(random_engine);
}

inline unsigned get_random_unsigned (unsigned max) {
    std::uniform_int_distribution<unsigned> dist (0, max);
    return dist(random_engine);
}

class CitySystem;

class Entity {
    std::array<unsigned, NCITIES> path;

public:
    friend class CitySystem;

    std::array<unsigned, NCITIES> const& getPath() const { return path; }

    static std::pair<Entity, Entity> cross (Entity const& a, Entity const& b) {
        // calculate division point
        unsigned div_point = get_random_unsigned(a.path.size());
        // prefix
        Entity cross_a, cross_b;
        std::set<unsigned> prefix_a, prefix_b;

        std::copy(b.path.begin(), b.path.begin() + div_point, cross_a.path.begin());
        //std::copy(b.path.begin(), b.path.begin() + div_point, prefix_a.begin());
        std::for_each(b.path.begin(), b.path.begin() + div_point, [&prefix_a](unsigned p){ prefix_a.insert(p); });

        std::copy(a.path.begin(), a.path.begin() + div_point, cross_b.path.begin());
        std::for_each(a.path.begin(), a.path.begin() + div_point, [&prefix_b](unsigned p){ prefix_b.insert(p); });
        //std::copy(a.path.begin(), a.path.begin() + div_point, prefix_b.begin());

        unsigned curr_a = div_point;

        for (unsigned i = div_point; i < NCITIES; ++i) {
            unsigned p = a.path[i];
            if (prefix_a.find(p) == prefix_a.end()) 
                cross_a.path[curr_a++] = p;
        }
        for (unsigned i = 0; i < div_point; ++i) {
            unsigned p = a.path[i];
            if (prefix_a.find(p) == prefix_a.end()) 
                cross_a.path[curr_a++] = p;
        }

        unsigned curr_b = div_point;

        for (unsigned i = div_point; i < NCITIES; ++i) {
            unsigned p = b.path[i];
            if (prefix_b.find(p) == prefix_b.end()) 
                cross_b.path[curr_b++] = p;
        }
        for (unsigned i = 0; i < div_point; ++i) {
            unsigned p = b.path[i];
            if (prefix_b.find(p) == prefix_b.end()) 
                cross_b.path[curr_b++] = p;
        }


        //std::copy_if(a.path.begin(), a.path.end(), cross_a.path.begin() + div_point, [&prefix_a](unsigned p){ return prefix_a.find(p) == prefix_a.end(); });
        //std::copy_if(b.path.begin(), b.path.end(), cross_b.path.begin() + div_point, [&prefix_b](unsigned p){ return prefix_b.find(p) == prefix_b.end(); });

        // mutations
        if (get_random_double(1.0) < 0.01) {
            std::swap(cross_a.path[get_random_unsigned(NCITIES-1)], cross_a.path[get_random_unsigned(NCITIES-1)]);
        }
        if (get_random_double(1.0) < 0.01) {
            std::swap(cross_b.path[get_random_unsigned(NCITIES-1)], cross_b.path[get_random_unsigned(NCITIES-1)]);
        }
        /*
        std::ofstream out("crossover.txt", std::ios::out | std::ios::app);
        out << "-----------------------------\n";
        for (int i = 0; i < NCITIES; ++i) {
            out << a.path[i] << " ";
        }
        out << "\n";
        for (int i = 0; i < NCITIES; ++i) {
            out << b.path[i] << " ";
        }
        out << "\n";
        for (int i = 0; i < NCITIES; ++i) {
            out << cross_a.path[i] << " ";
        }
        out << "\n";
        for (int i = 0; i < NCITIES; ++i) {
            out << cross_b.path[i] << " ";
        }
        out << "\n";*/

        return std::make_pair(cross_a, cross_b);
    }
};

class CitySystem {
public:
    std::array<Entity, NCREAT> population;
    std::array<double, NCREAT> perf_cache;
    std::array<std::array<double, NCITIES>, NCITIES> distances;    /*odleglosci miedzy miastami*/

    static Entity create_random () {
        int stop;
        Entity temp;

        for (int j = 0; j < NCITIES; j++) {
            do {
                stop = 1;
                temp.path[j] = rand() % NCITIES;
                int k = 0;
             
                while (k<j)
                {
                    if (temp.path[k] == temp.path[j])
                    {
                        stop = 0;
                        break;
                    }
                    k++;
                };
            }
            while (!stop);
        };
        return temp;
    }

    double eval_perf(Entity const& e) {
        double sum = 0.0;

        for (unsigned i = 0; i < NCITIES-1; ++i) {
            sum += distances[ e.path[i] ][ e.path[i+1] ];
        }
        sum += distances[e.path[0]][e.path[NCITIES-1]];

        double val = 100.0/sum;
        val *= val;
        return val;
    }

    unsigned get_random(double S) {
        double barrier = get_random_double(S);
        double s = 0.0;

        for (unsigned i = 0; i < population.size(); ++i) {
            s += perf_cache[i];
            if (s > barrier) 
                return i;
        }
    }

    void recalc_cache() {
         for (unsigned i = 0; i < population.size(); ++i) {
            perf_cache[i] = eval_perf(population[i]);
         }
    }

    Entity& get_best() {
        unsigned best_ix = 0;
        double best_perf = 0.0;
        for (unsigned i = 0; i < population.size(); ++i) {
            double perf = perf_cache[i];
            if (perf > best_perf) {
                best_ix = i;
                best_perf = perf;
            }
        }

        return population[best_ix];
    }

    void advance_generation() {
        recalc_cache();
        double prev_best = eval_perf(get_best());

        double S = 0.0;

        for (unsigned i = 0; i < population.size(); ++i) {
            S += perf_cache[i];
        }

        for (int i = 0; i < NCREAT / 2; ++i) {
            unsigned a = get_random(S);
            unsigned b = get_random(S);

            double bias = (perf_cache[a] + perf_cache[b]) / 2.0;

            //if (bias + get_random_double(2.0) > prev_best) {
            if (get_random_double(1.0) < 0.85) {
                auto p = Entity::cross(population[a],population[b]);

                population[a] = p.first;
                population[b] = p.second;
            }
        }

        recalc_cache();
    }
};