Métaheuristiques d'optimisation

Optimisation et minimums

Les problèmes d’optimisation et de recherche de minimums sont courants, et des résolutions exactes sont compliquées, voire impossibles. L’intelligence artificielle a donc mis au point des algorithmes spécifiquement pour ces problèmes.

Algorithmes gloutons

Les algorithmes gloutons sont les plus simples. Ils ne construisent qu’une seule solution, mais de manière itérative. Ainsi, à chaque pas de temps, on rajoute un élément, le plus prometteur.

Cet algorithme est à adapter à chaque problème. Seul le principe général reste le même.

Ainsi, dans le cas du sac à dos, on va rajouter au fur et à mesure les objets les plus intéressants jusqu’à atteindre la capacité du sac.

Pour cela, on commence par calculer la valeur par kilo de chaque objet :

On trie ensuite chaque objet du plus intéressant (la valeur par kilo la plus haute) au moins intéressant. L’ordre obtenu est le suivant :

A - D - K - I - L - B - C - E - J - H - F - G

On part d’un sac à dos vide. On ajoute le premier élément d’après le tri, donc l’objet A. Le sac à dos contient alors 4 kg et a une valeur totale de 15.

On ajoute ensuite le premier élément de la liste triée restante. L’objet D ne pèse que 3 kg, on peut donc le mettre dans le sac.

Celui-ci contient alors 7 kg et a une valeur...

Descente de gradient

La descente de gradient est une métaheuristique incrémentale. À partir d’une première solution, choisie aléatoirement ou donnée comme base (par exemple la meilleure solution connue des experts), l’algorithme va chercher une optimisation en ne modifiant la solution que d’une unité.

Lorsque le problème est une fonction mathématique, on calcule la dérivée au point représentant la solution actuelle, et on suit la direction de la dérivée la plus forte négativement.

Sur le schéma suivant, les différentes solutions obtenues itérativement sont indiquées : on part de la solution la plus haute, et on va aller dans le sens du gradient, jusqu’à atteindre le minimum.

Intuitivement, c’est l’algorithme utilisé par un randonneur en forêt : si celui-ci cherche à atteindre le sommet d’une montagne, mais qu’il ne peut savoir où celui-ci se trouve, alors il regarde autour de lui dans quelle direction le chemin monte le plus et le suit. À force de monter, il va forcément se retrouver en haut du massif sur lequel...

Recherche tabou

La recherche tabou est une amélioration de la recherche par descente de gradient. En effet, cette dernière reste bloquée dans le premier optimum rencontré.

Dans le cas de la recherche tabou, à chaque itération, on se déplace vers le meilleur voisin même s’il est moins bon que la solution actuelle. De plus, on retient la liste des positions déjà visitées, qui ne sont plus sélectionnables (d’où le nom, les anciennes solutions devenant taboues).

De cette façon, l’algorithme se "promène" dans l’espace de solution et ne s’arrête pas au premier optimum découvert. On s’arrête lorsque tous les voisins ont été visités, au bout d’un nombre d’itérations maximal décidé ou lorsqu’aucune amélioration suffisante n’est détectée en x coups.

La principale difficulté de cette recherche est le choix de la longueur de la liste de positions taboues. En effet, si cette liste est trop courte, on risque de boucler autour des mêmes positions. Au contraire, une liste trop longue peut empêcher de tester d’autres chemins partant d’une même solution potentielle. Il n’existe cependant aucun moyen de connaître la longueur de la liste idéale, elle doit être choisie de manière...

Recuit simulé

Le recuit simulé améliore la descente de gradient et s’inspire du recuit utilisé en métallurgie. En effet, lorsqu’on forge ou coule des métaux, ceux-ci subissent des contraintes importantes. C’est le cas des lames d’épées par exemple.

Pour augmenter la dureté de la lame, on la réchauffe (d’où le nom de recuit). De cette façon, les atomes peuvent se recristalliser sous des structures plus résistantes, et les contraintes mécaniques et thermiques sont diminuées. Les lames de bonne qualité subissent ainsi plusieurs cycles de chauffe et de mise en forme.

En informatique, on va utiliser ce principe pour améliorer les solutions et sortir des optimums locaux. On va donc fixer une température numérique, qui va baisser au cours du temps. Plus cette température est importante et plus les sauts dans l’espace de recherche peuvent être grands. De même, on accepte, contrairement à la descente de gradient, d’aller sur des solutions moins optimales que la solution actuelle.

L’algorithme commence donc par une recherche globale, et va trouver des zones plus intéressantes. Puis lorsque la température décroît, il va se concentrer de plus en plus sur une seule zone, et se termine comme une recherche de gradient classique. Les probabilités...

Optimisation par essaims particulaires

Pour la plupart des métaheuristiques, les résultats sont meilleurs si on lance plusieurs exécutions à partir de solutions initiales différentes. En effet, cela permet de parcourir une plus grande zone de recherche.

Cependant, il est possible de retomber plusieurs fois sur la même solution, et de passer à côté de l’optimum global (ou d’un meilleur optimum local).

L’optimisation par essaims particulaires s’inspire de la biologie. En effet, autant chez les oiseaux que chez les poissons, on peut observer de grands groupes d’animaux se déplaçant ensemble en trois dimensions. Les oiseaux (ou les poissons) ne se rentrent cependant pas dedans : la direction de chacun s’adapte en permanence en fonction de la direction actuelle et de la position des autres. Sa vitesse aussi s’adapte.

Dans cet algorithme, plusieurs solutions potentielles cohabitent dans l’espace de recherche, et chacune se déplace dans une direction donnée. À chaque itération, les solutions vont se déplacer comme une nuée, en allant vers les zones qui semblent les plus intéressantes.

Chaque solution doit connaître sa vélocité actuelle, sous la forme d’un vecteur (ce qui permet d’indiquer la direction du déplacement) et les meilleures positions découvertes jusqu’alors....

Domaines d’application

Ces algorithmes sont très utiles dans de nombreux domaines, en particulier ceux pour lesquels il n’existe pas de moyen de calculer l’optimum de manière mathématique ou lorsque cela prendrait trop de temps.

Ils obtiennent un optimum, local ou global. On espère alors avoir un résultat, s’il n’est pas global, au moins le plus proche de celui-ci au niveau de sa qualité.

On les retrouve ainsi dans tous les domaines nécessitant la conception de pièces ou de systèmes. En effet, ils permettent de trouver facilement des formes ou des matériaux adéquats, en limitant le coût (ou, selon les problèmes, la surface de frottement, les turbulences...). Ils sont utilisés en construction par exemple, pour optimiser les structures porteuses.

Des études ont ainsi été faites pour optimiser le coût de structures en fer pour des constructions devant respecter les normes antisismiques.

En électronique, on s’en sert pour améliorer le design de cartes imprimées, en limitant par exemple la quantité de "fil" nécessaire, ou en minimisant la place requise par les différents composants.

En finance, les métaheuristiques peuvent permettre d’optimiser un portefeuille d’actions, en limitant les risques et en cherchant à maximiser les gains pour une somme...

Implémentation

Dans un premier temps, on implémentera des algorithmes génériques, puis des classes héritant de ces classes mères permettent de résoudre le problème du sac à dos.

Deux versions du problème du sac à dos sont utilisées : la première est celle présentée comme exemple pour l’algorithme glouton (avec 16 objets) et la deuxième est une version plus complexe et aléatoire, qui permet de mieux comparer les différents algorithmes.

Une analyse des résultats obtenus est menée à la fin de cette partie.

public interface ISolution {  
   double getValeur();  
} 

import java.util.ArrayList;  
public interface IProbleme {  
   ArrayList<ISolution> Voisinage(ISolution solutionCourante); 
   ISolution SolutionAleatoire();  
   ISolution MeilleureSolution(ArrayList<ISolution> solutions); 
} 

public interface IHM {  
   void AfficherMessage(String msg);  
} 

Synthèse

Ce chapitre a présenté cinq algorithmes classés comme métaheuristiques. Ceux-ci ont tous pour but de trouver l’optimum d’un problème. S’il est préférable de trouver l’optimum global, lorsqu’il n’existe aucune méthode mathématique pour le faire et que tester toutes les solutions serait trop long, ils sont l’alternative idéale, en permettant de trouver de bons optimums locaux, voire l’optimum global.

Le premier est l’algorithme glouton. Il consiste à construire de manière incrémentale une seule solution, en suivant ce qui semble être le plus adéquat pour atteindre l’optimum.

La descente de gradient part d’une solution aléatoire. À chaque itération, on regarde le voisinage de celle-ci, et on suit la direction la plus prometteuse. Lorsque plus aucune amélioration n’est disponible dans le voisinage, c’est que l’optimum local a été atteint. Cet algorithme est simple et fonctionne bien, mais il est souvent bloqué dans des optimums locaux et ne trouve donc pas forcément l’optimum global.

La recherche tabou a été créée pour permettre d’améliorer la recherche de gradient. En effet, au lieu de se déplacer de position en position en suivant une progression, on se déplace vers...