genetic-vsp/Main.cpp

#include <algorithm>
#include <chrono>
#include <climits>
#include <iostream>

#include "Reader.h"

int center;
Reader r;

struct Data {
    std::vector<int> order;
    std::vector<int> vehicles;
    mutable int fitness = -1;

    Data(int size) : order(size, 0), vehicles(size, rand() % 4) {
        int counter = -1;
        for(int& i : order) {
            counter++;
            if(counter == center) {
                counter++;
            }
            i = counter;
        }
    }

    int getFitness() const {
        if(fitness != -1) {
            return fitness;
        }
        int last[4] = {center, center, center, center};
        int sum[4] = {0, 0, 0, 0};
        fitness = 0;
        for(size_t i = 0; i < order.size(); i++) {
            int v = vehicles[i];
            sum[v] += r[last[v]][order[i]];
            last[v] = order[i];
        }
        for(int i = 0; i < 4; i++) {
            sum[i] += r[last[i]][center];
        }
        int max = std::max(std::max(sum[0], sum[1]), std::max(sum[2], sum[3]));
        fitness = sum[0] + sum[1] + sum[2] + sum[3] + max * 4;
        return fitness;
    }

    void mutate() {
        if(rand() & 1) {
            vehicles[rand() % vehicles.size()] = rand() % 4;
        } else {
            int a = rand() % vehicles.size();
            int b = rand() % vehicles.size();
            if(b <= a) {
                std::swap(a, b);
            }
            int oldB = order[b];
            for(int i = b; i > a; i--) {
                order[i] = order[i - 1];
            }
            order[a] = oldB;

            oldB = vehicles[b];
            for(int i = b; i > a; i--) {
                vehicles[i] = vehicles[i - 1];
            }
            vehicles[a] = oldB;
        }
        fitness = -1;
    }

    void print() const {
        for(int i : order) {
            std::cout << i << " ";
        }
        std::cout << "| ";
        for(int i : vehicles) {
            std::cout << i << " ";
        }
        std::cout << "| " << getFitness() << "\n";
    }

    void prettyPrint() const {
        for(int i = 0; i < 4; i++) {
            std::cout << i << ": " << r.getName(center) << " -> ";
            for(size_t k = 0; k < order.size(); k++) {
                if(vehicles[k] == i) {
                    std::cout << r.getName(order[k]) << " -> ";
                }
            }
            std::cout << r.getName(center) << "\n";
        }
    }

    bool operator<(const Data& other) const {
        return getFitness() < other.getFitness();
    }
};

std::vector<Data> population;

static void init() {
    for(int i = 0; i < 1000; i++) {
        population.push_back(Data(r.getSize() - 1));
    }
    for(Data& data : population) {
        for(int i = 0; i < 40; i++) {
            data.mutate();
        }
    }
}

static void sort() {
    std::sort(population.begin(), population.end());
}

static void findCenter() {
    int min = INT_MAX;
    int index = 0;
    for(int i = 0; i < r.getSize(); i++) {
        int sum = 0;
        for(int k = 0; k < r.getSize(); k++) {
            sum += r[i][k];
        }
        if(sum < min) {
            index = i;
            min = sum;
        }
    }
    center = index;
}

long getNanos() {
    return std::chrono::high_resolution_clock::now().time_since_epoch().count();
}

int main() {
    long start = -getNanos();

    if(r.read("romaniaroads.pl")) {
        return 0;
    }
    findCenter();

    r.print();

    start += getNanos();

    long loop = -getNanos();
    init();
    sort();

    for(int gens = 0; gens < 250; gens++) {
        size_t half = population.size() / 2;
        for(size_t i = half; i < population.size(); i++) {
            int parent = rand() % half;
            population[i] = population[parent];
            population[i].mutate();
        }
        sort();
    }

    for(size_t i = population.size(); i > 0; i--) {
        population[i - 1].print();
    }

    population[0].prettyPrint();
    std::cout << "center is " << r.getName(center) << "\n";

    loop += getNanos();

    std::cout << "Start: " << start / 1'000'000 << "ms\n";
    std::cout << "Loop: " << loop / 1'000'000 << "ms\n";

    return 0;
}