Laboratoire de Génie Informatique et d’Automatique de l’Artois

Séminaire

Comparaison des Partitions par la Distance de Transfert pour la Classification de Solutions en Optimisation

Le 22 septembre 2011 à 16h00 Salle des séminaires du LGI2A, FSA, Béthune
Daniel PORUMBEL Maître de conférences LGI2A

La distance de transfert, étudiée initialement par S. Régnier [5] est bien connue en classification
pour comparer des partitions [3, 4]. Rappelons brièvement, qu’étant données deux
partitions P1 et P2 d’un ensemble S, la distance de transfert d (P1 ; P2) est définie comme le nombre minimal d’éléments qui doivent être transférés entre les classes de P1 pour obtenir une partition égale à P2. En classification, elle est souvent utilisée pour valider un algorithme en mesurant l’écart entre le résultat de l’algorithme et une solution connue, ou pour comparer les
résultats de différentes approches. Dans cette communication, nous l’utilisons dans un contexte différent : celui de l’analyse d’espaces de recherche (“fitness landscapes”) pour un problème d’optimisation combinatoire classique : la k-coloration de graphes. L’objectif général est d’utiliser des informations sur les espaces de recherche pour améliorer les performances des algorithmes méta-heuristiques en optimisation combinatoire. En effet, il est bien connu que les performances des méta-heuristiques dépendent étroitement du choix
de paramètres qui est souvent effectué de façon ad-hoc. Une meilleure compréhension des comportements des processus de recherche et des structures des espaces de recherche associés reste nécessaire pour rendre leurs stratégies “mieux informées”. L’intérêt de l’apprentissage et de la fouille de données en optimisation combinatoire est en plein essor comme l’attestent
outre des publications (e.g. [2, 1]) la récente conférence LION (Learning and Intelligent Optimization). Dans cette présentation, nous allons insister sur trois points :
– La classification de solutions candidates pour le problème de coloration de graphe ;
– Sa mise en oeuvre via le calcul de la distance de transfert entre colorations (partitions) ;
– Des différentes stratégies d’optimisation et des résultats expérimentaux sur des instances du benchmark DIMACS de coloration de graphe.
Remerciements Ce travail a été mené en collaboration avec Jin-Kao Hao (LERIA, Angers) et Pascale Kuntz (LINA, Nantes).

Références
[1] R. Battiti, R Brunato, and F. Mascia. Reactive Search and Intelligent Optimization. Springer,
2008.
[2] J. Boyan, W. Buntine, and A. Jagota. Statistical