GA_TASK3_II

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

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;

double fRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}
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 = fRand(0, 1);
    }

    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 = fRand(0, 1);
    }

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

    void generatePCX()
    {
        pcx = fRand(0, 1);
    }

    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 = graphDistances[tourOrder[0]][tourOrder[cityCount-1]];
        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 (fRand(0, 1) < 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) {
    int crossoverCount = 0;
    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 < popSize - 1; i += 2) {
        if (pop[i + 1].pcx < pcx && pop[i].pcx < pcx)
        {
            crossoverCount += 2;

            int pos = (int)fRand(1,L-2);
            //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);

            fout << std::endl << pos << std::endl;
            pop[i].showBits();
            pop[i + 1].showBits();
            c1.showBits();
            c2.showBits();
        }
        else break;
    }

    double newpcx = fRand(0, 1);
    if (pop[i].pcx < pcx && newpcx < 0.5) {

        crossoverCount += 2;

        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);
    }
    std::cout << "CROSSOVER ENDED WITH " << crossoverCount << " TOTAL CROSSOVERS \n";
}
*/


Tour CrossoverF(Tour& parent1, Tour& parent2, int k)
{
    Tour child(parent1);
    for (int i = 0; i < child.cityLen * child.cityCount; i++)
    {
        (i < k) ? (child.bits[i] = parent1.bits[i]) : (child.bits[i] = parent2.bits[i]);
    }
    child.recalculate();
    //fout << std::endl << k << std::endl;
    //parent1.showBits();
    //parent2.showBits();
    //child.showBits();

    return child;
}


void crossover(double crossoverP, std::vector<Tour> pop)
{
    //std::cout << "STARTING CROSSOVER \n";
    int c = -1, caux = -1, crossoverCount = 0;
    const int L = pop[0].cityLen * pop[0].cityCount;
    for (int i = 0; i < popSize; i++)
    {
        if (pop[i].pcx < crossoverP)
        {
            if (c == -1) c = i;
            else
            {
                crossoverCount += 2;
                int k = fRand(1, L-1);

                pop.push_back(CrossoverF(pop[c], pop[i], k));
                pop.push_back(CrossoverF(pop[i], pop[c], k));
                //std::cout << "Crossed chromosomes " << c << " and " << i << " at crossing point " << k <<"; \n";
                c = -1;
            }
        }
        else caux = i;
    }
    if ((c != -1) && (fRand(0, 1) < 0.5))
    {
        crossoverCount += 2;
        int k = fRand(1, L - 1);
        pop.push_back(CrossoverF(pop[c], pop[caux], k));
        pop.push_back(CrossoverF(pop[caux], pop[c], k));
        //std::cout << "Crossed chromosomes " << c << " and " << caux << " at crossing point " << k << "; \n";
    }
    //std::cout << "CROSSOVER ENDED WITH " <<crossoverCount<< " TOTAL CROSSOVERS \n";
}




std::vector<Tour> selection(std::vector<Tour>& population,int eliteCount)
{
    std::vector<Tour> newPopulation;
    std::vector<double> sectorFitness;
    double worst = -1;
    //int populationSize = population.size();

    for (int i = 0; i < population.size(); i++)
    {
        if (worst < population[i].tourDistance) worst = population[i].tourDistance;
    }


    for (int i = 0; i < population.size(); i++)
    {
        //population[i].fitness = 1.1 * worst - population[i].tourDistance;
        population[i].fitness = -1*population[i].tourDistance;
    }

    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 < population.size(); 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 = fRand(0, 1) * sectorFitness[sectorFitness.size() - 1];
        for (int j = 0; j < population.size(); j++)
        {
            if (prob <= sectorFitness[j])
            {
                newPopulation.push_back(population[j]);
                j = population.size() + 1; //organic break
            }
        }
    }

    return newPopulation;
}


int main() {

    //srand(__rdtsc());
    srand(time(NULL));
    //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);
    }

    //mutation(0.1, pop);
    //crossover(0.99, pop);


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

    while (g < 1500)
    {

        std::cout << "GENERATION "<< g <<std::endl;
        pop = selection(pop, 5);
        //showEntirePopulation(pop);
        mutation(0.02, pop);
        crossover(0.3, 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 << shortest << std::endl;
        pop[shortestIndex].showPath();
        fout << pop[shortestIndex].tourDistance<<" "<<pop[shortestIndex].fitness<<std::endl;
        fout << "--------------------------------------------------------------\n";
        g++;
    }


    //for (int i = 0; i < pop.size(); i++)
        //fout << pop[i].tourDistance << " " << divFit(&pop[i]) << std::endl;

    Tour test(29);
    test.tourOrder = { 0,27,5,11,8,4,25,28,2,1,19,9,3,14,17,16,13,21,10,18,24,6,22,26,7,23,15,12,20 };
    test.calculateDistance();
    std::cout << std::endl << test.tourDistance;
    fout.close();
    return 0;
}