Genetic algorithm for solving a puzzle (v. 2)

Question

Thanks to your wonderful comments regarding the first version of my code, I have been able to improve it. This new version is more readable (I guess). The problem is that it seems to me that there is no overall performance improvement at all.

Here is the full source code.

const int PUZZLE = 16;
const int POPULATION = 50;
const int COMPTEUR = PUZZLE * POPULATION * 10;

const int TEST = 0;

const int COUPE = 50;
const int MUTATION = 1;

// Localtime
#pragma warning(disable: 4996)

#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <string>
#include <cmath>
#include <random>
#include <functional>
#include <cstdlib>
#include <ctime>
#include <iomanip>

[ . . .]

using std::vector;
using std::string;
using std::cout; 
using std::endl;

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<double> dist(0, 4);

auto t = time(nullptr); auto tm = *localtime(&t);

class Pieces
{
public:
    vector<int> ADN;
    double fitness;
    bool best;
    bool candidat;
    bool solution;

    Pieces(){};
    ~Pieces(){};
};


void log(string s)
{
    std::ofstream TXT_log(Chemin + "log.txt", std::ios_base::app | std::ios_base::out);
    TXT_log << endl << s << " " << std::put_time(&tm, "%d-%m-%Y %H-%M-%S") << " :: " << PUZZLE << endl;
}

void lecture(
    vector<int>& R, 
    vector<int>& A, 
    vector<int>& B, 
    vector<int>& C, 
    vector<int>& D)
{
    string e1, e2, e3, e4, e5, ligne;
    string Puzzle = Chemin + "puzzle" + std::to_string(PUZZLE) + ".txt";

    std::ifstream fichier(Puzzle);

    if (fichier.good())
    {
        do
        {
            fichier >> e1 >> e2 >> e3 >> e4 >> e5;
            e1.erase(remove(e1.begin(), e1.end(), '.'), e1.end());

            R.push_back(stoi(e1));
            A.push_back(stoi(e2));
            B.push_back(stoi(e3));
            C.push_back(stoi(e4));
            D.push_back(stoi(e5));
        } while (getline(fichier, ligne));
    }
    else
    {
        cout << "ERREUR FICHIER : ~OUVERTURE" << endl;
    }

    fichier.close();
}

int integrite(
    vector<int>& R, 
    vector<int>& A, 
    vector<int>& B, 
    vector<int>& C, 
    vector<int>& D,
    int& nb_lignes)
{
    if ((int)R.size() != PUZZLE) 
    { cout << "ERREUR FICHIER : ~NOMBRE DE PIECES" << endl; return 0; }

    nb_lignes = (int)sqrt(PUZZLE);

    if (sqrt(PUZZLE) != nb_lignes) 
    { cout << "ERREUR FICHIER : ~SQRT" << endl; return 0; }

    vector<int> ABCD; int i, zeros = 0;

    for (i = 0; i < PUZZLE; i++) ABCD.push_back(A[i]);
    for (; i < PUZZLE * 2; i++) ABCD.push_back(B[i - PUZZLE]);
    for (; i < PUZZLE * 3; i++) ABCD.push_back(C[i - PUZZLE * 2]);
    for (; i < PUZZLE * 4; i++) ABCD.push_back(D[i - PUZZLE * 3]);

    sort(begin(ABCD), end(ABCD));

    for (i = 0; i < (PUZZLE * 4) - 2; i += 2) { 
        if (ABCD[i] != ABCD[i + 1])
        {   cout << "ERREUR FICHIER : ~DOUBLONS" << endl; return 0; }}

    for (i = 0; i < (PUZZLE * 4); i++) if (ABCD[i] == 0) zeros++;

    if (zeros != sqrt(PUZZLE) * 4)
    {   cout << "ERREUR FICHIER : ~BORDURES" << endl; return 0; }

    cout << "PUZZLE : " << PUZZLE << endl;
}

void eval_tableau(
    vector<vector<int> >& evaluation,
    int& rotation,
    int j,
    vector<int>& A,
    vector<int>& B,
    vector<int>& C,
    vector<int>& D
    )
{
    evaluation[(0 + rotation) % 4][j] = A[j];
    evaluation[(1 + rotation) % 4][j] = B[j];
    evaluation[(2 + rotation) % 4][j] = C[j];
    evaluation[(3 + rotation) % 4][j] = D[j];
}

void eval_bordures(
    double& eval, 
    vector<vector<int> >& evaluation,
    int& nb_lignes
    )
{
    bool OK_zeros = true;
    int zeros;

    for (int col = 0; col < 4; col++)
    {
        zeros = 0;

        for (int j = 0; j < PUZZLE; j++)
        {
            if (evaluation[col][j] == 0)
            {
                zeros++;
            }
        }

        if (abs(nb_lignes - zeros) != 0)
        {
            OK_zeros = false;
            eval += abs(nb_lignes - zeros);
        }
    }

    if (OK_zeros != true) eval++;
}

void eval_doublons(
    double& eval, 
    vector<vector<int> >& evaluation
    )
{
    vector<int> intersection;

    vector<int> bijA, bijB, bijC, bijD;

    for (int j = 0; j < PUZZLE; j++)
    {
        bijA.push_back(evaluation[0][j]);
        bijB.push_back(evaluation[1][j]);
        bijC.push_back(evaluation[2][j]);
        bijD.push_back(evaluation[3][j]);
    }

    sort(begin(bijA), end(bijA));
    sort(begin(bijC), end(bijC));

    set_intersection(begin(bijA), end(bijA),
        begin(bijC), end(bijC),
        back_inserter(intersection));

    eval += abs(PUZZLE - (int)intersection.size());

    intersection.clear();

    sort(begin(bijB), end(bijB));
    sort(begin(bijD), end(bijD));

    set_intersection(begin(bijB), end(bijB),
        begin(bijD), end(bijD),
        back_inserter(intersection));

    eval += abs(PUZZLE - (int)(intersection.size()));
}

 int reproduction(int geneA, int geneB, int j)
{
    if (j < ((COUPE * PUZZLE) / 100))
        return geneA;
    else return geneB;
}

 int aleADN()
{
    if (TEST == 0) 
        return (int)dist(gen);
    else return 0;
}

void solution(string& solution)
 {
     cout << "! ";

     bool nouveau = false;
     bool line = true;
     string comp = Chemin + "Rotations/result" + std::to_string(PUZZLE) + ".txt";
     std::ifstream TXT_comp_result(comp);
     string ligne_result;

     int present = 0;

     if (TXT_comp_result)
     {
         vector<string> TXT_resultats;
         string brin;

         do
         {
             TXT_comp_result >> brin;

             TXT_resultats.push_back(brin);
         } while (getline(TXT_comp_result, ligne_result));

         brin.clear();

         for (int k = 0; k < (int)TXT_resultats.size(); k++)
         {

             if (solution == TXT_resultats[k])
             {
                 present++;
             }
         }
         TXT_resultats.clear();
     }

     else
     {
         nouveau = true;
         line = false;
     }

     TXT_comp_result.close();

     if (present == 0)
         nouveau = true;

     std::ofstream TXT_result(Chemin + "Rotations/result" + std::to_string(PUZZLE) + ".txt", std::ios_base::app | std::ios_base::out);
     std::ofstream TXT_log(Chemin + "log.txt", std::ios_base::app | std::ios_base::out);

     if (nouveau && line)
         TXT_result << endl;

     TXT_log << endl << "**** Résultat ****" << endl;
     TXT_log << solution;

     if (nouveau) TXT_result << solution;

     log("S");
 }


int main()
{
    int i, j, k, nb_lignes;
    unsigned long compteur = 0;

    vector<int> R, A, B, C, D;

    lecture(R, A, B, C, D);
    integrite(R, A, B, C, D, nb_lignes);
    log("N");

    if (TEST != 0) cout << "TEST" << endl;
    cout << "POPULATION : " << POPULATION << endl << endl;

    Pieces * pieces = new Pieces[POPULATION];

    vector<vector<int> > evaluation(4, vector<int>(PUZZLE,0));

    for (;;)
    {
        double fitness = 0;
        double fitness_ref = fitness;

        for (i = 0; i < POPULATION; i++)
        {
            pieces[i].ADN.clear();

            for (j = 0; j < PUZZLE; j++)
            {
                pieces[i].ADN.push_back(aleADN());
            }
        }

        do
        {
            compteur++;

            for (i = 0; i < POPULATION; i++)
            {
                pieces[i].fitness = 0;
                pieces[i].solution = false;
                pieces[i].best = false;
                pieces[i].candidat = false;
                pieces[i].best = false;
            }

            int rotation;

            for (i = 0; i < POPULATION; i++)
            {
                double eval = 0;

                for (j = 0; j < PUZZLE; j++)
                    eval_tableau(evaluation, pieces[i].ADN[j], j, A, B, C, D);

                eval_bordures(eval, evaluation, nb_lignes);
                eval_doublons(eval, evaluation);

                pieces[i].fitness = 1 / (eval + 1);

                string ADN_solution;

                if (pieces[i].fitness == 1)
                {
                    string ADN_solution;
                    for (j = 0; j < PUZZLE; j++)
                    {
                        ADN_solution += std::to_string(pieces[i].ADN[j]);
                    }
                    solution(ADN_solution);
                }
            }


            // Best
            for (i = 0; i < POPULATION; i++)
            {
                if (pieces[i].fitness > fitness)
                {
                    fitness = pieces[i].fitness;
                    pieces[i].best = true;
                    break;
                }
            }

            if (fitness > fitness_ref)
            {
                fitness_ref = fitness;
            }

            double fitness_total = 0;

            // Selection roulette
            for (i = 0; i < POPULATION; i++)
                fitness_total += pieces[i].fitness;

            std::uniform_real_distribution<double> pool_rand(0, fitness_total);

            vector<int> candidats;
            vector<double> pool_fitness;

            for (i = 0; i < POPULATION; i++)
                pool_fitness.push_back(pieces[i].fitness);

            sort(begin(pool_fitness), end(pool_fitness), std::greater<double>());

            do {

                double r = pool_rand(gen);
                k = 0;

                while (r > 0)
                {
                    r -= pool_fitness[k];
                    k++;
                }

                for (i = 0; i < POPULATION; i++)
                {
                    if (pieces[i].fitness == pool_fitness[k - 1])
                    {
                        candidats.push_back(i);
                        break;
                    }
                }

            } while (candidats.size() < POPULATION);

            pool_fitness.clear();

            // Reproduction
            for (i = 0; i < POPULATION; i++)
            {
                if (pieces[i].best == true)
                {
                    pieces[0].ADN = pieces[i].ADN;
                }
            }

            for (i = 1; i < POPULATION; i++)
            {
                for (j = 0; j < PUZZLE; j++)
                {
                    pieces[i].ADN[j] =
                        reproduction
                        (
                        pieces[0].ADN[j],
                        pieces[candidats[i]].ADN[j],
                        j
                        );
                }
            }

            candidats.clear();

            // Mutation
            std::uniform_real_distribution<double> mutation_rand(0, PUZZLE);

            for (i = 1; i < POPULATION; i++)
            {
                for (j = 0; j < PUZZLE; j++)
                {
                    if (mutation_rand(gen) <= MUTATION)
                    {
                        pieces[i].ADN[j] = (int)dist(gen);
                    }
                }
            }

        } while (compteur < COMPTEUR);

        compteur = 0;
        cout << ". ";
    }   
}

Answer 1

auto t = time(nullptr); auto tm = *localtime(&t);

These should be std::time and std::localtime. See this website. Then you don't need the #pragma warning(disable: 4996).

Answer 2

According to this great video, using namespace std; allows you to leave out the many std:: bits. Use using after #include and before your code, preferably not in the global namespace so here's a demo of proper namespace use:

#include <iostream>
#include <cmath>  // Uses ::log, which would be the log() here if it were not in a namespace, see https://stackoverflow.com/questions/11892976/why-is-my-log-in-the-std-namespace

// Silently overrides std::log
//double log(double d) { return 420; }

namespace uniquename {
    using namespace std;  // So we don't have to waste space on std:: when not needed.

    double log(double d) {
        return 42;
    }

    int main() {
        cout << "Our log: " << log(4.2) << endl;
        cout << "Standard log: " << std::log(4.2);
        return 0;
    }
}

// Global wrapper for our contained code.
int main() {
    return uniquename::main();
}

Output:

Our log: 42
Standard log: 1.43508

Your new GA code is about 100 lines longer than your previous version; did you add that much functionality? I prefer more context per screen, so I'd leave out the curly braces of the single statements in favor of more inline documentation, e.g.:

for (i = 1; i < POPULATION; ++i)
    for (j = 0; j < PUZZLE; ++j)
        if (mutation_rand(gen) <= MUTATION)
            pieces[i].ADN[j] = (int)dist(gen);

But people who don't mind curly braces might mess that up. Safer alternatives are Nim, Boo, and Python (Cython or PyPy for speed).

++i is slightly faster than i++, but the compiler should optimize that already. (Not sure, since C++ compilers didn't catch the dead code that led to Apple's SSL bug, nor many memory management mistakes.)