Analyse et résolution approchée de problèmes d'optimisation combinatoire : application au problème de coloration de graphe Espaces abstraits Partitions (mathématiques) Coloriage de graphes Optimisation combinatoire Heuristique Recherche opérationnelle Logiciels intégrés Algorithmes parallèles Algorithmes génétiques 003 Nous avons exploré plusieurs aspects théoriques et expérimentaux de l'optimisation combinatoire. Premièrement, nous avons défini une notion de structure permettant de s'échapper du résultat du théorème du No Free Lunch. Deuxièmement nous avons formalisé la symétrie de l'espace de recherche des problèmes de partitionnements. A l'aide de cette formalisation, nous pûmes concevoir des outils travaillant efficacement sur cette espace. Plus précisément nous avons développé un test d'égalité, une mesure de distance et un nouvel opérateur de Cross over. Nous avons utilisé ces résultats pour classifier les benchmarks classique de la coloration de graphe. Pour finir, nous avons développé pour ce problème une métaheuristique parallèle qui équilibre l'intensification et la diversification pendant la recherche. Text Electronic Thesis or Dissertation FR application/pdf 1 : 1382482 https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/2004/50376-2004-Weinberg.pdf Weinberg Benjamin 2004LIL10121 2004-01-01 Informatique Université Lille1 - Sciences et Technologies thesis.degree.grantor_1 026404184 Doctorat non oui Talbi El-Ghazali Université Lille1 - Sciences et Technologies ASCII 1382482