Optimisation Combinatoire : Méthodes Approchées

Ce document présente des méthodes approchées en optimisation combinatoire à travers plusieurs exercices classiques. Il s'adresse aux étudiants en informatique ou en mathématiques appliquées souhaitant comprendre et appliquer des algorithmes gloutons, des techniques d'amélioration locale et le recuit simulé pour résoudre des problèmes d'optimisation.

Rendre la monnaie avec un algorithme glouton

Le problème consiste à rendre une somme N donnée avec le moins de pièces possible, en choisissant parmi des pièces de valeurs fixes. Le commerçant dispose d'une infinité de pièces de valeurs 10, 20, 50, 100, 1000 et 5000 millimes.

Algorithme glouton

L'algorithme glouton consiste à toujours prendre la pièce de plus grande valeur possible sans dépasser la somme restante à rendre. On répète cette opération jusqu'à ce que la somme soit exactement rendue.

Exemple

Un client effectue un achat de 8 dt 200 et donne 10 dt. La monnaie à rendre est donc :

10 000 - 8 200 = 1 800 millimes

Application de l'algorithme :

• On prend la plus grande pièce ≤ 1800, soit 1000. Il reste 800.
• On prend la plus grande pièce ≤ 800, soit 500. Il reste 300.
• On prend la plus grande pièce ≤ 300, soit 100. Il reste 200.
• On prend la plus grande pièce ≤ 200, soit 100. Il reste 100.
• On prend la plus grande pièce ≤ 100, soit 100. Il reste 0.

Le rendu de monnaie est donc 1 pièce de 1000, 1 pièce de 500, et 3 pièces de 100, soit 5 pièces au total.

Problème de choix d'activités

On dispose d'un ensemble S = {1, ..., n} d'activités concurrentes, chacune avec un horaire de début d_i et un horaire de fin f_i, avec d_i ≤ f_i. La ressource ne peut supporter qu'une activité à la fois. Deux activités i et j sont compatibles si leurs intervalles ne se chevauchent pas, c'est-à-dire si d_i ≥ f_j ou d_j ≥ f_i.

Le but est de choisir le plus grand nombre d'activités compatibles entre elles.

Algorithme glouton

Un algorithme glouton classique consiste à :

1. Trier les activités par ordre croissant de leur heure de fin f_i.
2. Choisir la première activité dans la liste.
3. Pour chaque activité suivante, la sélectionner si elle est compatible avec toutes celles déjà choisies (c'est-à-dire si son début est supérieur ou égal à la fin de la dernière activité sélectionnée).

Exemple

Supposons les activités suivantes (d_i, f_i) :

• Activité 1 : (1, 4)
• Activité 2 : (3, 5)
• Activité 3 : (0, 6)
• Activité 4 : (5, 7)
• Activité 5 : (8, 9)
• Activité 6 : (5, 9)

Tri par heure de fin :

1 (1,4), 2 (3,5), 3 (0,6), 4 (5,7), 6 (5,9), 5 (8,9)

Choix glouton :

• Prendre activité 1 (1,4)
• Activité 2 commence à 3, chevauche avec activité 1, on la saute
• Activité 3 commence à 0, chevauche, on la saute
• Activité 4 commence à 5 ≥ 4, on la prend
• Activité 6 commence à 5, chevauche avec activité 4, on la saute
• Activité 5 commence à 8 ≥ 7, on la prend

Activités choisies : 1, 4, 5

Problème du voyageur de commerce (TSP) et méthodes approchées

Un autocar doit partir de l'école A et visiter les points d'arrêt B, C, D, E, F en minimisant la durée totale du trajet. On dispose d'une matrice D = (d_ij) représentant la durée des trajets entre chaque paire de points.

Algorithme glouton

Le principe est de partir d'un sommet de départ et à chaque étape de choisir le point non visité le plus proche.

Questions

1. Appliquer l'algorithme glouton sur la matrice D donnée (non reproduite ici).
2. La solution dépend-elle du sommet de départ ?

Amélioration par méthode de descente

Soit le tour s : ABCDEF. On considère la transformation élémentaire 2-opt qui consiste à supprimer deux arêtes et reconnecter les chemins différemment pour obtenir un nouveau tour.

• Donner toutes les solutions voisines de s obtenues par 2-opt.
• Peut-on améliorer le tour par la méthode de descente ?

Recuit simulé

Le recuit simulé est une méthode d'optimisation stochastique qui permet d'échapper aux minima locaux en acceptant parfois des solutions moins bonnes avec une certaine probabilité dépendant de la température.

Considérons la transformation consistant à remplacer les arêtes (E,F) et (B,C) par (B,E) et (F,C). On cherche la température T telle que cette transformation ait une probabilité d'acceptation de 0,5.

La probabilité d'acceptation est donnée par :

p = exp(-ΔE / T)

où ΔE est la différence de coût entre la nouvelle solution et l'ancienne.

Pour p = 0,5, on a :

T = -ΔE / ln(0,5)

Ensuite, en adoptant cette température initiale et une décroissance géométrique de raison z, on calcule le nombre de changements nécessaires pour que la probabilité d'acceptation de la même transformation soit environ 0,001 :

p_final = exp(-ΔE / (T * z^k)) ≈ 0,001

où k est le nombre d'étapes. On résout pour k :

k = ln(p_final) / ln(z)

Glossaire des termes clés

• Algorithme glouton : méthode qui construit une solution en faisant à chaque étape le choix localement optimal.
• Activités compatibles : activités dont les intervalles de temps ne se chevauchent pas.
• 2-opt : transformation élémentaire dans le TSP qui échange deux arêtes pour améliorer un tour.
• Recuit simulé : méthode d'optimisation stochastique inspirée du refroidissement des métaux, qui accepte parfois des solutions moins bonnes pour éviter les minima locaux.
• Probabilité d'acceptation : dans le recuit simulé, probabilité d'accepter une solution moins bonne selon la température et la différence de coût.
• Tour hamiltonien : chemin passant une seule fois par chaque sommet dans un graphe.

Points clés à retenir

• L'algorithme glouton est simple et efficace pour certains problèmes comme rendre la monnaie ou le choix d'activités, mais ne garantit pas toujours la solution optimale.
• Le problème de choix d'activités peut être résolu efficacement en triant par heure de fin et en sélectionnant les activités compatibles.
• Le problème du voyageur de commerce est complexe et nécessite souvent des méthodes approchées comme le glouton, la descente locale (2-opt) et le recuit simulé.
• Le recuit simulé utilise une température contrôlant la probabilité d'accepter des solutions moins bonnes pour échapper aux minima locaux.
• Le choix de la température initiale et de la décroissance est crucial pour l'efficacité du recuit simulé.