Charivari de la société contemporaine

De manière plus discrète et moins médiatisé se développent des méthodes de résolutions de problèmes complexes à l'aide des métaheuristiques.

Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l'ingénierie ou de l'intelligence artificielle) pour lesquels on ne connaît pas de méthode classique plus efficace.

Les métaheuristiques sont généralement des algorithmes stochastiques itératifs, qui progressent vers un optimum global, c'est-à-dire l'extremum global d'une fonction, par échantillonnage d’une fonction objectif. Elles se comportent comme des algorithmes de recherche, tentant d’apprendre les caractéristiques d’un problème afin d’en trouver une approximation de la meilleure solution (d'une manière proche des algorithmes d'approximation).

Il existe un grand nombre de métaheuristiques différentes, allant de la simple recherche locale à des algorithmes complexes de recherche globale. Ces méthodes utilisent cependant un haut niveau d’abstraction, leur permettant d’être adaptées à une large gamme de problèmes différents.

Problèmes réels

Dans un numéro spécial de la revue scientifique European Journal of Operational Research, consacré aux applications des métaheuristiques, les éditeurs ont constaté que la majorité des 20 articles publiés le furent dans deux domaines : les problèmes d'ordonnancement et de logistique. Les méthodes les plus utilisées appartiennent à la famille des algorithmes évolutionnaires, souvent hybridés avec des méthodes de recherche locale.

Quelques exemples de problèmes concrets, optimisés via des métaheuristiques :

problèmes de tournée de véhicules,

optimisation de réseaux mobiles UMTS,

gestion du trafic aérien,

optimisation des plans de chargement des cœurs de réacteurs nucléaires,

etc.

Avantages et inconvénients

Les métaheuristiques étant très généralistes, elles peuvent être adaptées à tout type de problème d’optimisation pouvant se réduire à une « boîte noire ». Elles sont souvent moins puissantes que des méthodes exactes sur certains types de problèmes. Elles ne garantissent pas non plus la découverte de l’optimum global en un temps fini. Cependant, un grand nombre de problèmes réels n’est pas optimisable efficacement par des approches purement mathématiques, les métaheuristiques peuvent alors être utilisées avec profit.

La notion d’efficacité se rapporte généralement à deux objectifs contradictoires : la vitesse et la précision. La vitesse est souvent mesurée en nombre d’évaluations de la fonction objectif, qui est la plupart du temps la partie la plus gourmande en temps de calcul. La précision se rapporte à la distance entre l’optimum trouvé par la métaheuristique et l’optimum réel, soit du point de vue de la solution, soit de celui de la valeur. Bien souvent, un algorithme rapide est peu précis, et inversement.

Généralement, un choix doit être fait quant au critère d’arrêt adéquat. Un nombre d’évaluation ou un temps imparti est souvent utilisé, mais on peut également choisir d’atteindre une valeur donnée de la fonction objectif (le but étant alors de trouver une solution associée). Il est également possible de choisir des critères dépendants du comportement de l’algorithme, comme une dispersion minimale de la population de points ou un paramètre interne approprié. En tout état de cause, le choix du critère d’arrêt influencera la qualité de l’optimisation.

Le théorème du « no free lunch » explique qu’aucune instance de métaheuristique ne peut prétendre être la meilleure sur tous les problèmes. Une métaheuristique (M) n’est performante que pour une classe de problème (P) donnée.

L’utilisation de métaheuristiques peut paraître relativement simple, en première approche, mais il est souvent nécessaire d’adapter l’algorithme au problème optimisé. Tout d’abord, principalement dans le cadre de l’optimisation combinatoire, le choix de la représentation des solutions manipulées peut être crucial. Ensuite, la plupart des métaheuristiques disposent de paramètres dont le réglage n’est pas nécessairement trivial. Enfin, obtenir de bonnes performances passe généralement par une étape d’adaptation des diverses étapes de l’algorithme (initialisation, notamment). En pratique, seul le savoir-faire et l’expérience de l’utilisateur permet de gérer ces problèmes.

Il est admis que, d’un point de vue très général, aucune métaheuristique n’est réellement meilleure qu’une autre. En effet, une métaheuristique ne peut prétendre être plus efficace sur tous les problèmes, bien que certaines instances (c’est-à-dire l’algorithme lui-même, mais aussi un choix de paramètres et une implémentation donnée) puissent être plus adaptées que d’autres sur certaines classes de problèmes. Cette constatation est décrite par le théorème du no free lunch (« pas de dîner gratuit »).

En dernière analyse, il est parfois possible que le choix de la représentation des solutions, ou plus généralement des méthodes associées à la métaheuristique, ait plus d’influence sur les performances que le type d’algorithme lui-même. En pratique, cependant, les métaheuristiques se montrent plus puissantes que les méthodes de parcours exhaustif ou de recherche purement aléatoire.

Les métaheuristiques les plus connues sont :

Les algorithmes évolutionnistes, parmi lesquels :

les stratégies d’évolution,

les algorithmes génétiques,

les algorithmes à évolution différentielle,

les algorithmes à estimation de distribution,

les systèmes immunitaires artificiels,

la recomposition de chemin (Path relinking en anglais)

Shuffled Complex Evolution (Duan et al. 1992)

le recuit simulé,

les algorithmes de colonies de fourmis,

Les algorithmes d’optimisation par essaims particulaires,

la recherche avec tabous,

la méthode GRASP.