Optimisation Combinatoire : Méthodes Approchées
Optimisation Combinatoire : Méthodes Approchées
Programming, Combinatorial Optimization · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
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.
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.
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.
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 :
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.
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.
Un algorithme glouton classique consiste à :
Supposons les activités suivantes (d_i, f_i) :
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 :
Activités choisies : 1, 4, 5
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.
Le principe est de partir d'un sommet de départ et à chaque étape de choisir le point non visité le plus proche.
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.
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)