Genetic algorithm for solving a puzzle

Question

Edit. Version 2.

I am working on a genetic algorithm in order to solve a little "puzzle."

Given a text file with N rows with 4 int each, the idea is to establish 2 bijections between 2 x 2 columns and the same number of 0 in each column. For this purpose, the program is only allowed to shift the data to the right. For example, if a row has elements {1, 2, 3, 4}, they can be not shifted at all, shift 1 place ({4, 1, 2, 3}), 2 places ({3, 4, 1, 2}) or 3 places ({2, 3, 4, 1)}. No vertical permutations are allowed. No horizontal shuffles are allowed (e.g: {1, 4, 2, 3} is forbidden).

When a solution is found, a text file outputs the DNA of this puzzle with each gene being 0, 1, 2, or 3, that is if and how many times each row is shifted. Example: a 36 rows puzzle can give: 1113311331133111, the first 1 refering to the fact that row #1 is shifted one time to the right; the last 1 refering to the fact that row #16 is also shifted one time to the right.

This input text is formated like this: 1. 2 3 4 5. The first number 1. is the identification of the row, and 2 3 4 5 are the elements of this row. The bijections are to be established between the column containing the first elements and the third one; and between the second one and the fourth one.

I hope my explanation is clear. If not, it is detailed here.

My program works, but it does not seem efficient. Of course, it is difficult to evaluate the efficiency of a genetic algorithm, but I think the way I code is far from being optimal (see for example the horrible use of Goto that seems to me extremely useful in this context, but is not recommended...).

My code is a little bit long, and I doubt you have time to go into the details of its implementation, of course. But I think you can easily spot what seems wrong with my code, or what can be improved. Indeed, I think my code does not use the memory efficiently, but I do not know how to solve this issue. I have selected only the relevent segments of the code (I show the deleted segments with [. . .]); the full source code is released here if you are interested.

Moreover, if you have any comment regarding the genetic algorithm parameters (population, mutation, etc) feel free to share them.

#define PUZZLE 36
#define POPULATION 30
#define COMPTEUR PUZZLE * POPULATION * 50

#define TEST 0

#define COUPE 50
#define MUTATION 1

#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <string>
#include <math.h>
#include <random>
#include <functional>
#include <stdlib.h>
#include <ctime>
#include <iomanip>

using namespace std;

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

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

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

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

int main()
{
    unsigned long compteur = 0;
    int i, j, k;
    string e1, e2, e3, e4, e5;
    vector<int> R, A, B, C, D; // A droite, B bas, C gauche, D haut

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


/*  -----------------------
      OPENING OF THE FILE  
    -----------------------
*/
    [. . .]

/*  -------------------
     INTEGRITY CHECKS
    -------------------
*/
    [. . .]

/*  ------------------
      INITIALIZATION  
    ------------------
*/

    [. . .]
    Pieces * pieces = new Pieces[POPULATION];


/*  -------------
      EVOLUTION
    -------------
*/

    do
    {
        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());
            }
        }

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

        do 
        {
            compteur++;

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


/*  --------------
      EVALUATION
    --------------
*/

            int rotation;

            for (i = 0; i < POPULATION; i++)
            {
                int** evaluation = new int*[4];
                for (k = 0; k < 4; k++)
                    evaluation[k] = new int[PUZZLE];

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

                    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];
                }
                double eval = 0;

                // EVAL BORDURES
                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++;


                // EVAL DOUBLONS

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

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

                bijA.clear(); bijC.clear();

                eval += abs(PUZZLE - (int)intersection.size());
                pieces[i].intersections = 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));

                bijB.clear(); bijD.clear();

                eval += abs(PUZZLE - (int)(intersection.size()));
                pieces[i].intersections += PUZZLE - (int)intersection.size();

                intersection.clear();

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

                if (pieces[i].fitness == 1)
                {
                    pieces[i].solution = true;
                    goto Solution;
                }

                for (k = 0; k < 4; k++)
                    delete[] evaluation[k];
                delete[] evaluation;
            }


/*  -------------
      SELECTION
    -------------
*/

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

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

            if (fitness > fitness_ref)
            {
                fitness_ref = fitness;

                k = 0;
                for (i = 0; i < POPULATION; i++)
                {
                    if (pieces[i].best == true && k == 0)
                    {
                        cout << pieces[i].intersections << "\t" << fitness << endl;
                        k++;
                    }
                } 
            }


            // Roulette
            double fitness_total = 0;

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

            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), 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
    ------------
*/

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


/*  ------------
      SOLUTION
    ------------
*/

    Solution:

        for (i = 0; i < POPULATION; i++)
        {
            if (pieces[i].solution == true)
            {
                [. . .] // Save the output text file
            }
        }

        compteur = 0;
        cout << " *RESET*" << endl << endl;

    } while (1);
}

Answer 1

Constants

#define PUZZLE 36
#define POPULATION 30
#define COMPTEUR PUZZLE * POPULATION * 50

#define TEST 0

#define COUPE 50
#define MUTATION 1

You're using C++. You have type-safe const declarations available. You should be using them instead of the textual substitution of #define macros. Instead write:

const int PUZZLE = 36;
const int POPULATION = 30;
const int COMPTEUR = PUZZLE * POPULATION * 50;

const int TEST = 0;

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

Choice of header files to include

#include <math.h>
#include <stdlib.h>

These happen to be the C versions of the header files. You ought to be using the C++ versions of these files, as you are with <ctime>:

#include <cmath>
#include <cstdlib>

Namespace

using namespace std;

Please, please, please don't do this. It's a really bad idea. You pollute the global namespace with everything from std::, and if anything in std:: conflicts with anything in your project, you're in big trouble.

It's really not that much work to put the std:: prefix before the appropriate types and functions, but if you really want to avoid doing so, you can limit the namespace pollution to just those objects:

using std::random_device;
using std::mt19937;
using std::uniform_real_distribution;
using std::vector;
using std::string;
using std::cout;
using std::endl;
using std::sort;
using std::set_intersection;
using std::abs;

Infinite loops

do
{
   // [...]
} while (1) 

The preferred idiom is for(;;) -- it makes it more clear from the beginning what's going on, without any magic numbers.

Repeated code

Loopy

You don't need to pre-initialize pieces[i].best = false; since it will be initialized in the loop.

A, B, C, D

Whenever you repeat code with slightly different variables, it might be a good idea to put the things in an array and then loop over the array. Particularly since there's a connection between evaluation[0] and A.

Get rid of an unnecessary loop

        for (i = 0; i < POPULATION; i++)
        {
            if (pieces[i].fitness > fitness)
            {
                fitness = pieces[i].fitness;
            }
        }

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

You could get away with only one loop, by maintaining a std::vector that stores the indexes of entries that are tied with the current best, .clear() ing the vector once you find something better, then looping over the vector to set the best entries when you're all done.

Separate user interface and calculations

You've got that cout in the middle of the routine. It should be in a separate routine. The calculation routine should return something; its caller should output.

Answer 2

I'm not sure how to improve the performance, since reading this code is pretty difficult. It's not the worst I've seen, but it could still be improved.

For starters, your main function is way too long. For readability, it's generally recognized that a function should be no longer than what can take up one screen, or one printed page. This helps with readability and maintainability. I like to try to keep mine below about 70 lines.

You're also using a goto, and while this is hotly debated, I'd recommend against using it.

Here's how you might structure this:

class Pieces
{
    [member variables]
};

int aleADN()
{
    [...]
}

string* readFile(string filename){
    [..]
}

int evaluate(Pieces * pieces)
{
    int result = 1;
    [...]
    return result;
}

double selection(Pieces* pieces)
{
    [...]
    return fitness;
}

int reproduction(int geneA, int geneB, int j)
{
    [...]
}

void mate(pieces)
{
    [...]
}

void evolution(Pieces* pieces)
{
    do
    {
        [...]

        int done = evaluate(pieces);
        if (done == 0)
            return;

        fitness = selection(pieces);

        // mating leads to reproduction
        mate(pieces, fitness);

        mutate();

    } while (1);
}

int main()
{
    string* file_lines = readFile(filename);

    checkIntegrity();

    initialization();

    Pieces * pieces = new Pieces[POPULATION];
    evolution(pieces);

    // solution printout here
}

Once you get this structured properly, it will be very easy to set up things like timers or any memory monitoring utility like valgrind to see how much memory each function is using so you can track down what part of your code is taking too long or using too much memory.

Answer 3

I'd like to comment on performance of the code.

You've said it doesn't use memory very efficiently, and you where 100% right. Let me help you to fix this.

First of all I'd like to note that this is not about memory consuption, but about memory reuse. Let me explain. At any given moment of time program will be using more or less constant amount of memory. But in one of it's most inner loops program will repeatedly allocate and free memory, and this can easily be the most time consuming operations.

So, where memory is allocated?

1. Obviosly, anywhere new operator is found. I.E. evaluation array creation. I highly recomend to replace plain C array with the vector. This will be more convenient, less error prone and probably more efficient. And then I'll say how to deal with vectors.

2. Vectors. Every time push_back is done, there is a chance to vector to allocate. To mitigate this, common used practice is to reserve() number of elements needed if it is known upfront (and it is). But reserve() will obvoisly allocate and we still do not whant it in inner loop. Instead, have all your vectors declared and reserved outside of the loop. Inside the loop you can push_back() to initialize and clear() to deinitialize the data.

Secondly, output. IO in general and output to console in particular is very time-consuming process, and should not be done alongside computations. Better way is to save all needed information and then output it one go after computation is finished.