GA_TASK3

#include <iostream>
#include <bitset>
#include <vector>
#include <fstream>
#include <math.h>
#include <intrin.h>
#include <random>


std::ofstream fout("data.out");
std::ifstream fin("data.in");

std::default_random_engine gen01;
std::uniform_real_distribution<double> rand01(0.0, 1.0);

std::default_random_engine gen05;
std::uniform_real_distribution<double> rand05(0.0, 0.5);

unsigned int graphDistances[2000][2000];
unsigned int cityCount;
int popSize = 100;

struct Tour
{
    std::bitset<10000> bits;
    std::vector<unsigned int> values; //vectors are assigned at element creation in order to not repeat memory assignment at every modification
    std::vector<unsigned int> orderedValues; //same as above
    std::vector<unsigned int> tourOrder; //same as above
    unsigned int cityLen; //amount of bits assigned per city; value should always be ceil(log2(cityCount))
    unsigned int cityCount;
    unsigned int tourDistance;
    bool modified; //false if the tourOrder and tourDistance correspond to the current bitset; should be turned to true every time the bitset is modified (for example, at mutation)
    double pcx;
    double fitness;


    Tour(int cityNumber) //constructor; count is the number of cities
    {
        cityCount = cityNumber;
        cityLen = (int)ceil(log2(cityCount));
        tourDistance = 0;
        for (int i = 0; i < cityCount; i++)
            values.push_back(-1), orderedValues.push_back(-1), tourOrder.push_back(-1);
        modified = false;

        randomize();
        calculateValues();
        calculatePath();
        calculateDistance();

        pcx = rand01(gen01);
    }

    Tour(const Tour& t2) //copy contructor
    {
        cityCount = t2.cityCount;
        cityLen = t2.cityLen;
        bits = t2.bits;
        fitness = t2.fitness;
        for (int i = 0; i < cityCount; i++)
            values.push_back(t2.values[i]), orderedValues.push_back(t2.orderedValues[i]), tourOrder.push_back(t2.tourOrder[i]);

        tourDistance = t2.tourDistance;
        modified = t2.modified; //ideally, this should ALWAYS be false
        pcx = rand01(gen01);
    }

    void randomize()
    {
        for (int i = 0; i < 10000; i++)
            bits[i] = rand() % 2;
    }

    void generatePCX()
    {
        pcx = rand01(gen01);
    }

    void showBits()
    {
        for (int i = 0; i < cityCount; i++)
        {
            for (int j = 0; j < cityLen; j++)
                fout << bits[i * cityLen + j];
            fout << " ";
        }

        fout << std::endl;
    }

    void showPath()
    {
        for (int i = 0; i < cityCount; i++)
            fout << tourOrder[i] << " ";
        fout << std::endl;
    }

    void recalculate()
    {
        calculateValues();
        calculatePath();
        calculateDistance();
        modified = false;
    }

    void calculateValues()
    {
        int p2, tValue;

        for (int i = 0; i < cityCount; i++)
        {
            p2 = (int)pow(2, cityLen - 1);
            tValue = 0;
            for (int j = 0; j < cityLen; j++)
            {
                tValue += p2 * bits[i * cityLen + j];
                p2 /= 2;
            }
            values[i] = tValue;
            orderedValues[i] = tValue;
        }

        std::sort(orderedValues.begin(), orderedValues.end());
    }

    void calculatePath()
    {
        for (int i = 0; i < cityCount; i++)
            for (int j = 0; j < cityCount; j++)
                if (values[i] == orderedValues[j])
                {
                    tourOrder[i] = j;
                    orderedValues[j] = -1;
                    j = cityCount + 1;
                }

        //for (int i = 1; i < cityCount; i++)
            //tourDistance += graphDistances[tourOrder[i - 1]][tourOrder[i]]; //NOTE: MIGHT CHANGE ONCE I LEARN HOW TO USE TSPLIB
    }

    void calculateDistance()
    {
        tourDistance = 0;
        for (int i = 1; i < cityCount; i++)
            tourDistance += graphDistances[tourOrder[i - 1]][tourOrder[i]];
    }

    void mutate(double pm)
    {

        for (int i = 0; i < cityCount * cityLen; i++)
            if (rand01(gen01) < pm) {
                bits[i] = !bits[i];
                modified = true;
            }
    }
};

//std::vector<Tour*> pop;

void showEntirePopulation(std::vector<Tour> population)
{
    for (unsigned int i = 0; i < population.size(); i++)
    {
        //population[i].showBits();
        population[i].showPath();
        fout << population[i].tourDistance << " " << population[i].fitness << "\n";
    }
}

void readGraph()
{
    fin >> cityCount;
    for (int i = 0; i < cityCount; i++)
        for (int j = 0; j < cityCount; j++)
            fin >> graphDistances[i][j];
}


void mutation(double pm, std::vector<Tour>& pop)
{
    for (int i = 0; i < pop.size(); i++) {
        pop[i].mutate(pm);
    }
}

bool cmp(const Tour& t1, const Tour& t2) {
    return (t1.pcx < t2.pcx);
}

void crossover(double pcx, std::vector<Tour>& pop) {

    std::sort(pop.begin(), pop.end(), cmp);

    const int L = pop[0].cityLen * pop[0].cityCount;

    std::default_random_engine genint;
    std::uniform_int_distribution<int> randint(1, L - 2);

    for (int i = 0; i < pop.size(); i++)
    {
        pop[i].generatePCX();
    }

    int i;
    for (i = 0; i < pop.size() - 1; i += 2) {
        if (pop[i + 1].pcx < pcx && pop[i].pcx < pcx) {


            int pos = randint(genint);
            //fout << "pos=" << pos << '\n';
            Tour c1(pop[i]);
            Tour c2(pop[i + 1]);

            for (int j = pos; j < L - 1; j++) {
                c1.bits[j] = pop[i + 1].bits[j];
                c2.bits[j] = pop[i].bits[j];
            }
            pop.push_back(c1);
            pop.push_back(c2);
        }
        else break;
    }

    double newpcx = rand05(gen05);
    if (pop[i].pcx < pcx && newpcx < pcx) {
        int pos = randint(genint);
        //fout << "pos=" << pos << '\n';
        Tour c1(pop[i]);
        Tour c2(pop[i + 1]);

        for (int j = pos; j < L - 1; j++) {
            c1.bits[j] = pop[i + 1].bits[j];
            c2.bits[j] = pop[i].bits[j];
        }
        pop.push_back(c1);
        pop.push_back(c2);
    }
}

double divFit(Tour* tour)
{
    return (1 / (tour->tourDistance + 0));
}

std::vector<Tour> selection(std::vector<Tour>& population, double(*fitnessF)(Tour* tour), int eliteCount)
{
    std::vector<Tour> newPopulation;
    std::vector<double> sectorFitness;

    int populationSize = population.size();

    for (int i = 0; i < populationSize; i++)
    {
        population[i].fitness = fitnessF(&population[i]);
    }

    std::sort(population.begin(), population.end(), [](Tour t1, Tour t2) {return t1.fitness > t2.fitness; });

    sectorFitness.push_back(population[0].fitness);
    for (int i = 1; i < populationSize; i++)
        sectorFitness.push_back(sectorFitness[i - 1] + population[i].fitness);

    /*
    for (int i = 0; i < sectorFitness.size(); i++)
    {
        std::cout << i << " " << sectorFitness[i] << " ";
    }
    */
    for (int i = 0; i < eliteCount; i++)
        newPopulation.push_back(population[i]); //Elitism keeps the first eliteCount individuals unchanged

    for (int i = 0; i < popSize - eliteCount; i++)
    {
        double prob = rand01(gen01) * sectorFitness[sectorFitness.size() - 1];
        for (int j = 0; j < populationSize; j++)
        {
            if (prob <= sectorFitness[j])
            {
                newPopulation.push_back(population[j]);
                j = populationSize + 1; //organic break
            }
        }
    }

    return newPopulation;
}


int main() {

    srand(__rdtsc());

    //double pm = 0.1;
    //double pcx = 0.3;

    std::vector<Tour> pop;

    readGraph();

    for (int i = 0; i < popSize; i++)
    {
        Tour newtour(cityCount);
        pop.push_back(newtour);
    }

    int g = 0;
    int shortest = 100000000;
    int shortestIndex = 0;

    while (g < 5)
    {

        std::cout << "GENERATION "<< g <<std::endl;
        pop = selection(pop, divFit, 5);
        mutation(0.0001, pop);
        crossover(0.7, pop);

        shortestIndex = 0;

        for (int i = 0; i < pop.size(); i++)
        {
            if (pop[i].modified) pop[i].recalculate();
            if (pop[i].tourDistance <= shortest)
            {
                //std::cout << shortest << " ";
                shortestIndex = i;
                shortest = pop[i].tourDistance;
                //std::cout << shortest << " ";
            }
        }

        //std::cout << shortestIndex << std::endl;
        pop[shortestIndex].showPath();
        fout << pop[shortestIndex].tourDistance<<" "<<pop[shortestIndex].fitness<<std::endl;
        fout << "--------------------------------------------------------------\n";
        g++;
    }


    fout.close();
    return 0;
}