Genetic algorithm for solving a puzzle

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

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 
#include 

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 `:

#include 
#include 

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

StackExchange Code Review Q#88456, answer score: 10