Analyse et résolution approchée de problèmes d'optimisation combinatoire : application au problème de coloration de graphe / par Benjamin Weinberg ; directeur : El-Ghazali Talbi

Résumé / Abstract : 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éveloppe pour ce problème une métaheuristique parallèle qui équilibre l'intensification et la diversification pendant la recherche