Recherche autonome

Systèmes de résolution autonomes et intelligents

Face aux nouveaux défis en matière d’optimisation combinatoire,
les nouveaux problèmes à traiter reposent sur des modèles complexes,
hétérogènes et de grande dimension. Par conséquent, la conception de
solveurs nécessite une expertise croissante de la part de
l’utilisateur s’il souhaite réellement tirer un bénéfice optimal des
techniques de résolution qui sont à sa disposition. De plus, en
raison de l’hétérogénéité des modèles à traiter (variables et
contraintes de nature différentes), il est en général nécessaire de
combiner des approches de résolution différentes, en particulier des
méthodes de recherche exhaustives spécifiques avec des heuristiques
ou méta-heuristiques plus générales. Les solveurs résultants
s’avèrent souvent efficaces mais difficiles à utiliser en raison des
nombreux paramètres inhérents à de telles combinaisons. Il convient
donc d’assister l’utilisateur final dans l’ajustement de ces
paramètres, que ce soit dans la phase de conception du solveur pour
identifier les composants les plus appropriés, ou dans la phase de
résolution pour assurer une coordination optimale du processus de
recherche de solution. Des outils automatiques de réglage sont
actuellement disponibles pour certains solveurs largement utilisés
(par exemple dans CPLEX pour la programmation linéaire). Depuis
plusieurs années, le LERIA a développé ses compétences dans ce
domaine de la résolution autonome de problème (Autonomous Search) et
ses interactions avec la communauté scientifique correspondante qui
s’établit à l’interface de l’optimisation et de l’intelligence
artificielle (apprentissage, algorithmes évolutionnaires et plus
généralement métaheuristiques, programmation par contraintes…).
L’objectif de cette action est donc de poursuivre nos travaux visant
à rendre le plus autonomes possible les outils de résolution de
problèmes d’optimisation ou de satisfaction de contraintes, notamment
sur les aspects suivants :

  • Les modèles algorithmiques évolutionnaires en îles que nous
    avons étudiés permettent, de manière naturelle, d’organiser une
    résolution multi-solveurs ou multi-opérateurs en adaptant, via des
    mécanismes d’apprentissage dynamique, la configuration globale du
    processus de résolution en fonction d’observations locales de l’état
    du calcul. Nous souhaitons donc : (1) développer de nouveau modèles
    et algorithmes d’apprentissage par renforcement (bandits) mieux
    adaptés à des opérateurs plus complexes (par exemple combinant
    plusieurs solutions) et travailler sur tous les composants des
    solveurs (opérateurs heuristiques, fonction d’évaluation …), (2)
    définir de nouvelles mesures de performances plus réactives et
    spécifiques (en lien avec l’analyse de paysage de recherche par
    exemple), (3) mieux prendre en compte l’asynchronisme inhérent à
    l’utilisation de solveurs hétérogènes pour améliorer la répartition
    des charges de calcul dans tels modèles distribués et (4) rendre
    plus homogène des coopérations entre une recherche à base de
    population et une recherche mono-point (par voisinage par exemple),
    notamment au niveau des indicateurs de performance. L’objectif est
    donc ici de poursuivre nos investigations sur le contrôle en ligne
    de solveurs.
  • La configuration de stratégies pour certains solveurs mixtes
    constitue une tâche essentielle pour l’utilisateur et qui s’avère,
    comme déjà mentionné, extrêmement difficile. Dans le contexte des
    solveurs SMT (SAT modulo theory) dont l’utilisation pour la
    vérification et la conception logicielle est très importante, nous
    proposons d’utiliser la programmation génétique pour configurer et
    évaluer automatiquement des tactiques de résolution (une tactique
    consiste à définir comment différentes stratégies de résolution
    doivent coopérer pour résoudre un problème SMT, comportant par
    exemple des contraintes Booléennes, linéaires ou continues). Il
    s’agit donc de proposer de nouveaux outils de configuration
    automatique de solveurs intégrant des contraintes sémantiques et des
    connaissances propres au domaine. Ce projet pourrait se développer
    en collaboration avec Microsoft Research (solveur SMT Z3).
  • La génération et la sélection automatisée de composants de
    résolution vise à définir des briques de bases à partir desquelles
    il est possible de créer des ensembles d’opérateurs heuristiques de
    résolution pour des classes de problèmes suffisamment vastes (par
    exemple problèmes à base de permutations). Tirant parti des
    compétences en terme d’analyse de paysages et de techniques
    d’apprentissage pour le contrôle d’opérateur, l’objectif sera ici de
    proposer des mécanismes permettant, à partir de l’analyse de
    propriétés structurelles du problème à traiter et d’observations
    dynamiques, de concevoir des solveurs très génériques et fiables,
    dans la continuité des travaux sur les hyperheuristiques dont le but
    est de créer et gérer des approches de résolution à un haut niveau
    d’abstraction et d’utilisation (pour porter la déclarativité de la
    programmation par contraintes au niveau des métaheuristiques dans un
    cadre plus vaste).