Remplissage de container
Le problème
Définition
On souhaite ranger des cartons dans un camion, pour un déménagement, en exploitant au mieux le volume disponible dans le camion. Il faut pour cela agencer les cartons pour qu'ils s'agencent en prenant le minimum de place. On modélisera ce problème en 2D. Les cartons sont alors des rectangles, et le camion est un rectangle à l'intérieur duquel devront être rangés les cartons.
En fait, on considérera que la camion a une largeur fixe, mais peut être arbitrairement long. On y rangera les cartons à partir du fond, sans les tourner, en maintenant les côtés des cartons parallèles aux bords du camion. L'interdiction de tourner un carton signifie non seulement que les côtés du carton restent parallèles aux bords du camion, mais aussi qu'un carton plus long que large ne peut être tourné de 90 degrés pour être considéré comme un carton plus large que long. La qualité d'un rangement est alors définie par la longueur minimum de camion nécessaire pour ranger tous les cartons.
Résolution
Le problème posé est un problème de placement, que nous allons tenter de résoudre à l'aide d'un algorithme génétique.
Prise en main
Compilation C++
On réalisera ce TP en C++, à l'aide de gcc par exemple. La compilation s'effectue comme suit:
g++ -o test.bin test.cc
Une fois l'exécutable créé, on lance le programme par :
./test.bin
Affichage de figures avec xfig
Il sera utile de dessiner des containers avec des cartons dedans, pour voir ce que fait l'algorithme. Les programmes que vous réaliserez devront pour cela générer des fichiers xfig. Pour les visualiser :
xfig toto.fig &
On peut également convertir ces fichiers en pdf, pour les visionner avec un lecteur pdf.
fig2dev -L pdf toto.fig toto.pdf
Code fourni
Le code nécessaire à la représentation et la manipulation du problème de cartons vous est fourni, de sorte que votre effort de programmation ne concerne que l'algorithme génétique lui-même. Pour utiliser ces outils dans vos programmes, il suffit de copier le fichier ga.hpp dans votre répertoire de travail.
Vous n'avez pas à lire ce fichier, vous apprendrez à utiliser les outils fournis par des exemples, c'est l'objet de ce qui suit.
Etude des exemples
Chacun des exemples est un fichier de code C++, qui commence par un commentaire rappelant la ligne de compilation permettant d'en faire un exécutable. Attention, les fichiers d'exemples sont fournis sous forme html (votre navigateur afficje du code coloré quand vous cliquez sur les liens). Pour essayer les exemples, vous devrez créer un fichier texte, selectionner le code affiché dans votre navigateur, et le copier dans ce fichier texte pour ensuite le compiler.
Définition de la liste de cartons
L'exemple ga-example-001.cc montre comment se définir l'ensemble de cartons avec lesquels on va travailler, c'est-à-dire ceux que l'on a à ranger dans le camion. Les collections se basent sur la STL. Nous utiliserons principalement les vector et les map (associations clé-valeur). A titre indicatif, voici comment sont définis les types du problème.
typedef std::pair<double,double>          Block;
typedef std::pair<double,double>          Position;
typedef std::vector<Block>                Blocks;
typedef std::map<unsigned int,Position>   Setup;
typedef std::map<double,double>           Push;  
Disposition de cartons dans le camion
L'exemple ga-example-002.cc montre comment est codée une disposition de cartons dans le camion, et comment on l'affiche. La disposition (Setup) est une map, dont les clés sont le numéro de carton, et la valeur la position du centre de gravité du carton dans le camion.
Disposition à la Tétris
L'exemple ga-example-003.cc montre comment utiliser une disposition des blocks en les poussant au fond du camion. Il suffit pour cela de choisir une position latérale d'insersion, et de pousser le block au fond du camion, verticalement, jusqu'à ce que ça bloque. Cette fonction push est utile pour simplifier la génération d'un placement pas trop mauvais.
Meilleure insertion ?
L'exemple ga-example-004.cc montre l'utilisation de la structure Push pour analyser les différentes possibilités pour insérer un block. Cela peut être utile quand on décide d'insérer un block à une certaine colonne, pour le caler latéralement à la butée la plus proche.
Manipulation d'une population
L'exemple ga-example-005.cc vous montre comment programmer une classe individu, et comment manipuler efficacement une population (principe de double-bufferring et utilisation de références). Dans cet exemple, le chromosome est un entier, ce qui est idiot. Vous devrez définir vous-même un chromosome, ainsi que les opérateurs de mutation et de crossing-over idoines.
Programmation de l'algorithme génétique
Version dégénérée
On considère que l'on insère un carton dans le camion là où il arrive le plus au fond. Pour deux positions possibles équivalente, on choisira celle qui est la plus à gauche. Vous pourrez utiliser la structure Push pour ce faire. Le codage d'un individu se résume donc à l'ordre dans lequel on insérera, de cette façon-là, les cartons. Vous n'implémenterez pas de crossing over, mais simplement un operateur de mutation, qui sera une permutation aléatoire de la position de deux cartons dans l'ordre d'insertion.
Version de base
Implémentez un crossing over.
Version améliorée
Implémenter du fitness sharing entre les individus, afin de favoriser la création et le maintien de niches dans la population. Il vous faudra pour ce faire définir une distance génotypique, c'est-à-dire une distance entre 2 Setup.