Genetic algorithm for solving a puzzle (v. 2)

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.

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:
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;
}

{
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++)
{

for (j = 0; j < PUZZLE; j++)
{
}
}

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

if (pieces[i].fitness == 1)
{
for (j = 0; j < PUZZLE; j++)
{
}
}
}

// 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)
{
}
}

for (i = 1; i < POPULATION; i++)
{
for (j = 0; j < PUZZLE; j++)
{
reproduction
(
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)
{
}
}
}

} while (compteur < COMPTEUR);

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


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

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)


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

• Anyone care to explain the downvote? May 1 '15 at 11:56
• 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. May 1 '15 at 13:29
• 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. May 1 '15 at 13:30
• Using C++ appears to be the wrong choice if you don't want weird namespace bugs. May 1 '15 at 13:42
• I downvoted for std and curly braces May 2 '15 at 19:43