2
\$\begingroup\$

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 << ". ";
    }   
}
\$\endgroup\$
2
\$\begingroup\$
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).

|improve this answer|||||
\$\endgroup\$
-3
\$\begingroup\$

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.)

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Anyone care to explain the downvote? \$\endgroup\$ – Cees Timmerman May 1 '15 at 11:56
  • 2
    \$\begingroup\$ No, it would also be problematic if your project is using an identifer that clashes with an identifier in std::. You may not even get any compiler errors or warnings depending on the clash, just incorrect behavior from your program. \$\endgroup\$ – Snowbody May 1 '15 at 13:29
  • 2
    \$\begingroup\$ It's also a bad habit to leave out the curly braces. In the event that you ever need to add statements to the body of the loop, you'll have to remember to put them back. If you ever forget, one of the statements will be left outside the loop and the program will malfunction. \$\endgroup\$ – Snowbody May 1 '15 at 13:30
  • 2
    \$\begingroup\$ Using C++ appears to be the wrong choice if you don't want weird namespace bugs. \$\endgroup\$ – Cees Timmerman May 1 '15 at 13:42
  • 5
    \$\begingroup\$ I downvoted for std and curly braces \$\endgroup\$ – Caridorc May 2 '15 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.