Chapitre 7 · Semestre 5

Heuristiques et métaheuristiques : l'IA au service de l'optimisation

Intelligence Artificielle et Recherche Opérationnelle

Cours Exercices Résumé QCM

Objectifs du chapitre — À la fin de ce chapitre, vous saurez :

expliquer l'explosion combinatoire et pourquoi certains problèmes ne se résolvent pas exactement ;

appliquer une heuristique gloutonne (sac à dos, plus proche voisin) et une recherche locale ;

distinguer optimum local et optimum global ;

décrire le principe du recuit simulé, de la recherche tabou et des algorithmes génétiques ;

présenter la recherche heuristique en intelligence artificielle (algorithme A*).

7.1 L'explosion combinatoire

Les problèmes des chapitres 2 à 6 se résolvent par des algorithmes exacts et rapides. D'autres problèmes, d'apparence simple, sont beaucoup plus difficiles parce que leurs solutions sont des combinaisons dont le nombre explose avec la taille.

Définition — Problème du voyageur de commerce : trouver la tournée la plus courte qui passe une fois et une seule par chacune de $n$ villes et revient au point de départ. Le nombre de tournées distinctes est $(n - 1)!/2$.

Avec 5 villes, il y a 12 tournées ; avec 10 villes, 181 440 ; avec 20 villes, environ $6 \times 10^{16}$ : un ordinateur qui évalue un milliard de tournées par seconde mettrait près de deux ans. Ces problèmes sont dits NP-difficiles : on ne connaît pas d'algorithme qui les résolve exactement en un temps raisonnable dans tous les cas.

Définition — Problème du sac à dos : choisir, parmi $n$ objets ayant chacun un poids (ou un coût) et une valeur, le sous-ensemble de valeur maximale dont le poids total ne dépasse pas une capacité. Il y a $2^n$ sous-ensembles.

On le rencontre en sélection de projets d'investissement sous contrainte de budget, en chargement de conteneurs ou en composition d'un portefeuille.

7.2 Les heuristiques

Définition — Heuristique : méthode de résolution approchée, rapide, fondée sur une règle de bon sens, qui fournit une bonne solution sans garantir l'optimum.

Heuristiques constructives : elles construisent une solution pas à pas.

Glouton pour le sac à dos : classer les objets par rapport valeur/poids décroissant et les prendre dans cet ordre tant qu'ils tiennent.
Plus proche voisin pour le voyageur de commerce : partir du dépôt et aller à chaque étape à la ville non visitée la plus proche.

Ces méthodes sont myopes : un bon choix local peut obliger, plus tard, à de mauvais choix (le dernier retour au dépôt est souvent très long).

Recherche locale (heuristique d'amélioration) : partir d'une solution et la modifier légèrement (on définit un voisinage) tant que cela l'améliore. Pour le voyageur de commerce, le mouvement 2-opt supprime deux arêtes de la tournée et reconnecte les deux morceaux dans l'autre sens.

Définition — Optimum local : solution meilleure que toutes ses voisines, mais pas forcément meilleure que toutes les solutions (optimum global).

La recherche locale s'arrête au premier optimum local rencontré, comme un randonneur qui monte toujours et s'arrête au sommet de la première colline, sans voir la montagne voisine.

7.3 Les métaheuristiques

Les métaheuristiques sont des stratégies générales qui guident une recherche locale pour lui permettre de sortir des optima locaux. Beaucoup s'inspirent de la nature.

Le recuit simulé (Kirkpatrick, 1983), inspiré de la métallurgie : on accepte toujours un mouvement qui améliore la solution, et l'on accepte un mouvement qui la dégrade de $\Delta > 0$ avec la probabilité :

$$P = e^{-\Delta / T}$$

où $T$ est un paramètre appelé température. Au début, $T$ est élevée et l'algorithme explore largement ; puis $T$ diminue progressivement (refroidissement) et l'algorithme se stabilise près d'une bonne solution.

La recherche tabou (Glover, 1986) : à chaque étape, on prend le meilleur voisin, même s'il est moins bon que la solution courante, mais on interdit (on rend « tabou ») pendant quelques itérations les mouvements récents, pour ne pas revenir en arrière.

Les algorithmes génétiques (Holland, 1975), inspirés de l'évolution : on fait évoluer une population de solutions codées comme des chromosomes (par exemple une suite de 0 et de 1 pour le sac à dos). À chaque génération :

sélection : les meilleures solutions ont plus de chances de se reproduire ;
croisement : deux parents échangent des morceaux de chromosome ;
mutation : un gène change au hasard, ce qui maintient la diversité.

Les colonies de fourmis (Dorigo, 1992) : des agents construisent des solutions en déposant une « phéromone » sur les bons choix, qui attire les suivants ; elles sont efficaces pour les problèmes de tournées.

Ces méthodes sont utilisées par les logiciels d'optimisation des tournées de livraison, de planification des équipages aériens ou de conception de réseaux.

7.4 La recherche heuristique en intelligence artificielle

En IA, de nombreux problèmes se formulent comme la recherche d'un chemin dans un espace d'états : un état initial, des actions, un état but (jeu, planification, navigation d'un robot). Les recherches aveugles (en largeur, en profondeur) explorent systématiquement ; les recherches informées utilisent une estimation de la distance au but.

L'algorithme A* (Hart, Nilsson et Raphael, 1968) développe en priorité le nœud qui minimise :

$$f(n) = g(n) + h(n)$$

où $g(n)$ est le coût déjà parcouru depuis le départ et $h(n)$ une heuristique qui estime le coût restant (par exemple la distance à vol d'oiseau jusqu'à la destination). Si $h$ ne surestime jamais le coût réel (heuristique admissible), A* trouve le chemin optimal en explorant bien moins de nœuds que Dijkstra. Avec $h = 0$, on retrouve Dijkstra (chapitre 6).

7.5 Méthode : traiter un problème combinatoire

Identifier la structure (sac à dos, voyageur de commerce, affectation…) et compter les solutions possibles.
Si leur nombre est faible, énumérer ; sinon, construire une solution par une heuristique gloutonne.
L'améliorer par recherche locale (échanges, 2-opt) jusqu'à un optimum local.
Pour aller plus loin : métaheuristique (recuit, tabou, génétique) ; comparer plusieurs exécutions.
Évaluer la qualité : écart à une borne (par exemple la solution du programme linéaire continu) ou à l'optimum quand il est connu.

Les pièges à éviter

Présenter le résultat d'une heuristique comme l'optimum.
Oublier le retour au dépôt dans la longueur d'une tournée.
Confondre optimum local et optimum global.
Dans le recuit simulé, refuser systématiquement les dégradations (on retombe dans la recherche locale simple).
Croire qu'une métaheuristique garantit l'optimum : elle augmente les chances de bien faire, sans preuve.

Exercice 1 — Sélectionner des projets d'investissement

Une société d'investissement régionale dispose d'un budget de 10 millions de DH. Cinq projets sont à l'étude :

Projet	Coût (M DH)	Valeur actuelle nette attendue (M DH)
P1	5	10
P2	4	8,5
P3	3	6
P4	6	11
P5	2	3

Chaque projet est indivisible : on le réalise entièrement ou pas du tout.

Travail à faire :

Formulez le problème. Combien de sélections possibles existe-t-il ?
Appliquez l'heuristique gloutonne fondée sur le rapport valeur/coût. Quelle valeur obtenez-vous ?
Trouvez la sélection optimale. Que concluez-vous sur l'heuristique ?
Dans un recuit simulé, on envisage de passer d'une sélection de valeur 19,5 à une sélection de valeur 18,5. Calculez la probabilité d'accepter ce mouvement pour une température $T = 2$, puis $T = 0{,}25$. Commentez.

Voir le corrigé

1) Variables binaires $x_i = 1$ si le projet $P_i$ est retenu :

$$\max Z = 10x_1 + 8{,}5x_2 + 6x_3 + 11x_4 + 3x_5 \quad \text{s.c.} \quad 5x_1 + 4x_2 + 3x_3 + 6x_4 + 2x_5 \le 10,\;\; x_i \in \{0 ; 1\}$$

C'est un problème de sac à dos, avec $2^5 = \mathbf{32}$ sélections possibles.

2) Rapports valeur/coût : P2 : 2,125 ; P1 : 2 ; P3 : 2 ; P4 : 1,83 ; P5 : 1,5.

P2 (coût 4) : retenu, budget restant 6 ;
P1 (coût 5) : retenu, budget restant 1 ;
P3, P4, P5 : trop chers pour le budget restant.

Sélection gloutonne : {P2, P1}, coût 9, valeur 18,5 M DH (1 M DH du budget reste inutilisé).

3) En comparant les sélections qui épuisent presque tout le budget :

{P2, P4} : coût 10, valeur $8{,}5 + 11 = \mathbf{19{,}5}$ ;
{P1, P3, P5} : coût 10, valeur 19 ;
{P1, P2} : coût 9, valeur 18,5 ;
{P2, P3, P5} : coût 9, valeur 17,5 ; {P3, P4} : coût 9, valeur 17.

L'optimum est {P2, P4}, de valeur 19,5 M DH (confirmé par l'énumération des 32 sélections). L'heuristique gloutonne donne une bonne solution (à 5 % de l'optimum) mais pas l'optimum : en prenant P1, elle laisse un reliquat de budget inutilisable. Avec des objets indivisibles, le meilleur rapport unitaire ne suffit pas.

4) Le mouvement dégrade la valeur de $\Delta = 1$ :

$T = 2$ : $P = e^{-1/2} \approx \mathbf{0{,}61}$ ;
$T = 0{,}25$ : $P = e^{-4} \approx \mathbf{0{,}018}$.

À haute température, l'algorithme accepte souvent les dégradations et explore l'espace des solutions ; à basse température, il les refuse presque toujours et se comporte comme une recherche locale. C'est ce passage progressif de l'exploration à la stabilisation qui permet au recuit simulé d'échapper aux optima locaux.

Exercice 2 — Tournée d'un livreur

Un livreur part d'un dépôt D et doit visiter quatre clients A, B, C, E avant de revenir. Distances (km) : D-A 10, D-B 15, D-C 20, D-E 12, A-B 8, A-C 25, A-E 9, B-C 6, B-E 9, C-E 30.

Combien de tournées distinctes existe-t-il ?
Construisez la tournée du plus proche voisin depuis D et calculez sa longueur.
Améliorez-la par des mouvements 2-opt.

Voir le corrigé

1) $(5 - 1)!/2 = \mathbf{12}$ tournées.

2) Depuis D : A (10) ; depuis A : B (8) ; depuis B : C (6) ; depuis C : E (30, seule ville restante) ; retour E-D (12). Tournée D-A-B-C-E-D : $10 + 8 + 6 + 30 + 12 = \mathbf{66}$ km. Les bons choix du début imposent l'arête C-E, très longue.

3) On supprime D-A et C-E, et l'on reconnecte D-C et A-E (on parcourt A-B-C à l'envers) : D-C-B-A-E-D $= 20 + 6 + 8 + 9 + 12 = \mathbf{55}$ km. Puis on supprime B-A et E-D, et l'on reconnecte B-E et A-D : D-C-B-E-A-D $= 20 + 6 + 9 + 9 + 10 = \mathbf{54}$ km. L'énumération des 12 tournées confirme que 54 km est l'optimum (tournée D-A-E-B-C-D, la même dans l'autre sens).

Exercice 3 — Un croisement génétique

On code une sélection de projets de l'exercice 7 (P1 à P5) par cinq gènes (1 = projet retenu). Deux parents : $A = 01001$ et $B = 00110$.

Décodez les parents (coût et valeur).
Effectuez un croisement en un point, après le troisième gène. Évaluez les enfants.
On applique une mutation au premier gène du second enfant. Évaluez le résultat.
Comment traiter un enfant qui dépasse le budget ?

Voir le corrigé

1) $A$ = {P2, P5} : coût 6, valeur 11,5. $B$ = {P3, P4} : coût 9, valeur 17.

2) Enfant 1 = début de $A$ + fin de $B$ $= 010\,|\,10$ = {P2, P4} : coût 10, valeur 19,5 (c'est l'optimum). Enfant 2 = début de $B$ + fin de $A$ $= 001\,|\,01$ = {P3, P5} : coût 5, valeur 9.

3) $10101$ = {P1, P3, P5} : coût 10, valeur 19 : la mutation a fortement amélioré l'enfant 2.

4) On peut le réparer (retirer des projets jusqu'à respecter le budget), le pénaliser dans la fonction d'évaluation (valeur moins une pénalité proportionnelle au dépassement) ou l'éliminer de la population.

L'essentiel — Heuristiques et métaheuristiques

Explosion combinatoire : voyageur de commerce $(n - 1)!/2$ tournées ; sac à dos $2^n$ sélections ; problèmes NP-difficiles.
Heuristique : méthode rapide et approchée, sans garantie d'optimum.
Constructives : glouton (rapport valeur/coût décroissant), plus proche voisin.
Recherche locale : améliorer par petits mouvements (échange, 2-opt) jusqu'à un optimum local.
Recuit simulé : dégradation $\Delta$ acceptée avec $P = e^{-\Delta/T}$ ; température décroissante.
Tabou : meilleur voisin même moins bon, mouvements récents interdits.
Algorithme génétique : population, sélection, croisement, mutation.
IA : A* minimise $f = g + h$ ; heuristique admissible ⇒ chemin optimal ; $h = 0$ ⇒ Dijkstra.

S'entraîner sur des sujets réels

Des sujets réels de concours (master, licence d'excellence) avec une épreuve de Intelligence Artificielle et Recherche Opérationnelle : énoncé complet et corrigé indicatif.

Voir les 13 sujets de concours en Intelligence Artificielle et Recherche Opérationnelle →