37
Comme leur nom l’indique, les méta-heuristiques sont des algorithmes d’application génériques
d’heuristiques spécifiques au domaine et à l’espace de recherche, se rapprochant en cela de la plupart
des méthodes exactes, dans le cas par exemple de l’optimisation combinatoire (e.g., choix de l’ordre
de parcours des variables dans la programmation par contraintes, croisement de solutions pour les
problèmes de voyageur de commerce, etc). Elles diffèrent entre elles par les différents agendas
d’application des opérateurs de recherche dans l’espace des solutions qu’elles préconisent. À l’inverse
des méthodes exactes, elles n’offrent aucune garantie, mais permettent par contre de s’attaquer à des
problèmes peu structurés qui échappent aux approches exactes, comme on en rencontre fréquemment
dans le monde réel.
Ainsi, l’un des algorithmes les plus performant dans le domaine de l’optimisation continue est
l’algorithme CMA-ES (Covariance Matrix Adaptation Evolution Strategy), algorithme évolutionnaire
à base de transformations gaussiennes – dont on vient d’ailleurs de prouver qu’il n’est finalement rien
d’autre qu’un algorithme de gradient naturel dans l’espace des distributions gaussiennes. Et certains
``records'' pour des problèmes du voyageur de commerce de très grande taille sont détenus (ou
l’étaient encore il y a peu) par un algorithme utilisant des croisements de solutions très spécifiques.
Mais l’on retrouve ici un problème aujourd’hui essentiel en optimisation (comme d’ailleurs en apprentissage), celui du réglage des hyper-paramètres : on sait bien qu’il n’existera pas d’algorithme universel, et chaque instance de problème est résolu de manière optimale (la plus rapide pour atteindre une
solution, ou donnant la meilleure solution en un temps compté) par un algorithme particulier réglé de
manière spécifique. On parle aujourd’hui de Programming by Optimization (après H. Hoos), ce qui
peut aller, pour une classe de problèmes donnée, du choix du meilleur algorithme parmi un portfolio
(et on rejoint alors le domaine de la recommandation) jusqu’à l’optimisation d’heuristiques pour des
algorithmes exacts, voire la conception d’une hyper-heuristique, algorithme construit à partir de
briques de bases algorithmiques.
Par exemple, le niveau zéro de l’approche – la simple optimisation des hyper-paramètres
d’algorithmes existant – a pu apporter des accélérations de plus d’un ordre de grandeur sur un ensemble de solveurs, qu’ils soient spécifiques (comme dans le domaine du planning) ou génériques
(comme le produit commercial CPlex).
Enjeux actuels
Le corpus de résultats théoriques concernant la convergence des méta-heuristiques s’accroissent rapidement, mais reste encore bien en deçà des succès pratiques. Et de toute façon, ils ne pourront concerner que des résultats de complexité (en moyenne, ou dans le pire cas), les garanties d’optimalité devant
être recherchées ailleurs.
L’application pratique du concept de Programming by Optimization pose plusieurs problèmes: celui
de la représentation des instances de problème, via un ensemble de descripteurs, qui sera l’espace de
recherche de la méta-optimisation ; celui du choix de la classe d’instances pour lesquelles on va chercher des hyper-paramètres optimaux ; et celui de l’algorithme d’optimisation ou d’apprentissage qui
sera utilisé pour apprendre les hyper-paramètres correspondant à un ensemble d’instances donné.
Agents autonomes et systèmes multi-agents
Cette thématique se concentre sur l’analyse, la conception et l’implémentation de systèmes composés
d’entités autonomes et/ou en interaction. La thématique ``Agents Autonomes et Systèmes MultiAgents'' est la cible de la conférence AAMAS et de la revue Journal of Autonomous Agents and Multi-Agent Systems. Une partie de cette thématique est transversale en ceci qu’elle rejoint d’autres sousbranches de l’IA, notamment la représentation des connaissances et le raisonnement pour les problématiques liés aux sociétés d’agents (représentation des états cognitifs des agents, argumentation, né-
Comme leur nom l’indique, les méta-heuristiques sont des algorithmes d’application génériques
d’heuristiques spécifiques au domaine et à l’espace de recherche, se rapprochant en cela de la plupart
des méthodes exactes, dans le cas par exemple de l’optimisation combinatoire (e.g., choix de l’ordre
de parcours des variables dans la programmation par contraintes, croisement de solutions pour les
problèmes de voyageur de commerce, etc). Elles diffèrent entre elles par les différents agendas
d’application des opérateurs de recherche dans l’espace des solutions qu’elles préconisent. À l’inverse
des méthodes exactes, elles n’offrent aucune garantie, mais permettent par contre de s’attaquer à des
problèmes peu structurés qui échappent aux approches exactes, comme on en rencontre fréquemment
dans le monde réel.
Ainsi, l’un des algorithmes les plus performant dans le domaine de l’optimisation continue est
l’algorithme CMA-ES (Covariance Matrix Adaptation Evolution Strategy), algorithme évolutionnaire
à base de transformations gaussiennes – dont on vient d’ailleurs de prouver qu’il n’est finalement rien
d’autre qu’un algorithme de gradient naturel dans l’espace des distributions gaussiennes. Et certains
``records'' pour des problèmes du voyageur de commerce de très grande taille sont détenus (ou
l’étaient encore il y a peu) par un algorithme utilisant des croisements de solutions très spécifiques.
Mais l’on retrouve ici un problème aujourd’hui essentiel en optimisation (comme d’ailleurs en apprentissage), celui du réglage des hyper-paramètres : on sait bien qu’il n’existera pas d’algorithme universel, et chaque instance de problème est résolu de manière optimale (la plus rapide pour atteindre une
solution, ou donnant la meilleure solution en un temps compté) par un algorithme particulier réglé de
manière spécifique. On parle aujourd’hui de Programming by Optimization (après H. Hoos), ce qui
peut aller, pour une classe de problèmes donnée, du choix du meilleur algorithme parmi un portfolio
(et on rejoint alors le domaine de la recommandation) jusqu’à l’optimisation d’heuristiques pour des
algorithmes exacts, voire la conception d’une hyper-heuristique, algorithme construit à partir de
briques de bases algorithmiques.
Par exemple, le niveau zéro de l’approche – la simple optimisation des hyper-paramètres
d’algorithmes existant – a pu apporter des accélérations de plus d’un ordre de grandeur sur un ensemble de solveurs, qu’ils soient spécifiques (comme dans le domaine du planning) ou génériques
(comme le produit commercial CPlex).
Enjeux actuels
Le corpus de résultats théoriques concernant la convergence des méta-heuristiques s’accroissent rapidement, mais reste encore bien en deçà des succès pratiques. Et de toute façon, ils ne pourront concerner que des résultats de complexité (en moyenne, ou dans le pire cas), les garanties d’optimalité devant
être recherchées ailleurs.
L’application pratique du concept de Programming by Optimization pose plusieurs problèmes: celui
de la représentation des instances de problème, via un ensemble de descripteurs, qui sera l’espace de
recherche de la méta-optimisation ; celui du choix de la classe d’instances pour lesquelles on va chercher des hyper-paramètres optimaux ; et celui de l’algorithme d’optimisation ou d’apprentissage qui
sera utilisé pour apprendre les hyper-paramètres correspondant à un ensemble d’instances donné.
Agents autonomes et systèmes multi-agents
Cette thématique se concentre sur l’analyse, la conception et l’implémentation de systèmes composés
d’entités autonomes et/ou en interaction. La thématique ``Agents Autonomes et Systèmes MultiAgents'' est la cible de la conférence AAMAS et de la revue Journal of Autonomous Agents and Multi-Agent Systems. Une partie de cette thématique est transversale en ceci qu’elle rejoint d’autres sousbranches de l’IA, notamment la représentation des connaissances et le raisonnement pour les problématiques liés aux sociétés d’agents (représentation des états cognitifs des agents, argumentation, né-