Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 21 Février 2006

Heuristiques de base pour le placement de cercles

par Hakim Akeb (Laboratoire de Recherche en Informatique d'Amiens)

Le Placement de cercles (identiques ou non-identiques) dans des containers de différentes formes est un problème qu'on rencontre dans beaucoup de domaines (Découpe, Transport, fibres optiques, ...). Le calcul des placements les plus denses est NP-Complet.

Nous proposons des heuristiques de base pour résoudre ces différents problèmes. Une heuristique de base est implémentée à travers un algorithme glouton qui définit une (des) règle(s) permettant de séletionner la position du prochain cercle à chaque étape.

Nous proposons d'abord une heuristique appelée "Degré Maximum de Trou" (Maximum Hole Degree, MHD) pour le problème du placement de cercles identiques dans le rectangle. Cette heuristique consiste à calculer la largeur minimale du container rectangulaire (dont la hauteur est fixée) afin d'y placer tous les cercles sans chevauchement. MHD obtient actuellement les meilleurs résultats de la littérature sur des instances connues (instances de Stoyan & Yaskov).

Pour le problème du placement de cercles identiques dans le cercle, les approches qui donnent actuellement les meilleurs résultats sont de type stochastique comme la "Simulation de Billard" (BS) dont les résultats pour placer jusqu'à 500 cercles sont connus. L'inconvénient de telles méthodes est que le temps de calcul explose avec le nombre de cercles à placer. Il faut des semaines sinon des mois pour s'assurer que la solution ne peut plus àªtre améliorée. Nous proposons une heuristique de base, appelée "Dommage Minimum" (Minimum Damage, MinD) pour placer un grand nombre de cercles identiques dans le cercle (plusieurs milliers). Les résultats de MinD ont été comparés avec ceux obtenus par différentes méthodes connues dans la litérature. Les résultats expérimentaux ont montré que notre approche obtient des résultats avec un bon rapport entre la qualité des solutions et le temps de calcul.

Enfin, nous proposons une coopération entre les deux heuristiques (MHD et MinD) pour résoudre le problème du placement de cercles identiques dans le cercle sur des instances contenant des proportions différentes de cercles identiques et non-identiques. L'heuristique obtenue s'appelle "Dommage Nul MHD" (Null-Dammage MHD, NDMHD).

Mots clés : Circle packing, Heuristiques, Algorithmes gloutons, Optimisation combinatoire.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr