Titre original :

Analyse et résolution approchée de problèmes d'optimisation combinatoire : application au problème de coloration de graphe

Mots-clés en français :
  • 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

  • Langue : Français
  • Discipline : Informatique
  • Identifiant : 2004LIL10121
  • Type de thèse : Doctorat
  • Date de soutenance : 01-01-2004

Résumé en langue originale

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.

  • Directeur(s) de thèse : Talbi, El-Ghazali

AUTEUR

  • Weinberg, Benjamin
Droits d'auteur : Ce document est protégé en vertu du Code de la Propriété Intellectuelle.
Accès libre