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