Etude des paysages de Fitness // nombre et somme chromatique d'un graphe

Etude des paysages de Fitness // nombre et somme chromatique  d'un graphe

Ce stage vise à estimer les caractéristiques des paysages de fitness des problèmes de coloration en utilisant les métriques de la littérature, et les réseaux d’optima locaux qui synthétisent le paysage au graphe des solutions ”optimum local” (pics). Une attention particulière sera portée à la neutralité des paysages qui correspond aux solutions voisines de qualité équivalente. En effet, cette caractéristique induit des plateaux dans le paysage qui posent des difficultés aux algorithmes d’optimisation qui peuvent ne pas réussir à s’en échapper. Une bonne prise en compte de la neutralité peut cependant permettre aux méthodes d’optimisation de s’en extraire et ainsi d’atteindre de meilleures solutions. La neutralité est très présente sur les problèmes de coloration, où il est alors particulièrement intéressant de l’étudier pour créer des recherches locales plus efficaces. Les travaux seront conduits sur des instances classiques de la littérature, mais également sur des instances générées dans le stage, en combinant des graphes générées aléatoirement avec des graphes issus de problèmes réels, donc plus structurés. Cette approche permettra de produire des instances de problèmes dont la difficulté d’optimisation est ajustable. D’une part ce benchmark d’instances sera mis à disposition de la communauté scientifique, d’autre part il permettra une approche d’apprentissage automatique (machine learning) pour représenter l’ensemble des instances et apprendre de manière automatique la relation entre instances et meilleur algorithme de résolution.

Stage de 4 à 6 mois

Personnes à contacter : sara.tari@univ-littoral.fr (LISIC/ULCO) et corinne.lucet@u-picardie.fr (MIS/UPJV)

https://www.mis.u-picardie.fr/system/files/2021-10/StageM2_MIS_LISIC_2022_0.pdf