Optimisation combinatoire

I. Alaya

ENSI -ISID

Méthodes exactes Petit aperçu

• Principe Généralement énumérer, souvent de manière implicite, l'ensemble des combinaisons de implicite, l'ensemble des combinaisons de l'espace de recherche

31

I. Alaya

ENSI -ISID

Méthodes exactes Petit aperçu

• Branch and Bound • Une technique qui effectue un parcours en profondeur de

l'arbre de recherche afin de fournir une ou plusieurs solutions optimales à partir d'un ensemble de solutions potentielles • A chaque étape de la recherche, correspondant à un nœud de • A chaque étape de la recherche, correspondant à un nœud de l'arbre de recherche, l'algorithme utilise une fonction Bound pour calculer une borne de l'ensemble des solutions du sous- arbre de ce nœud

• Borne est initialisée à une valeur maximale (en cas de

minimisation)

• Si cette évaluation est moins bonne que la meilleure solution

trouvée jusqu'à ce niveau de recherche, tout le sous-arbre peut être coupé.

• L'efficacité de l'algorithme B&B dépend étroitement du calcul

de la borne utilisée

32

I. Alaya

ENSI -ISID

Méthodes exactes Petit aperçu

• Programmation dynamique • une méthode ascendante : On commence d'habitude par les sous problèmes les plus petits et on remonte vers les sous problèmes de plus en plus difficiles sous problèmes de plus en plus difficiles

• Idée de base : éviter de calculer deux fois la même chose,

généralement en utilisant une table de résultats déjà calculés, remplie au fur et à mesure qu'on résout les sous problèmes.

33

I. Alaya

ENSI -ISID

Algorithme approché VS Algorithme exact

• Les problèmes d'optimisation combinatoires sont en

général NP-difficiles

• Ce problème de l'explosion combinatoire limite

l'utilisation de méthodes exactes pour la résolution à des l'utilisation de méthodes exactes pour la résolution à des problèmes de petites tailles

• Dans les applications réelles (souvent de grande taille), les méthodes incomplètes deviennent une alternative intéressante

• Ces méthodes sacrifient la complétude pour gagner

l'efficacité

34

I. Alaya

ENSI -ISID

Algorithme approché VS Algorithme exact

En résumé • Algorithme exact : garantit une solution optimale • Algorithme approché : pas de garantie d'optimalité • Les méthodes exactes ne sont efficaces que pour les • Les méthodes exactes ne sont efficaces que pour les

instances de problèmes de petite taille

• Les problèmes réels sont en général de (très) grande

taille

• Les méthodes approchées sont plus efficaces pour les

problèmes de grande taille

• On ne s'intéressera ici qu'aux méthodes approchées

35

I. Alaya

ENSI -ISID

36

Notion d’heuristique

Chaque étape de résolution repose sur deux opérations clés: • l’opération de développement des alternatives • L’opération de choix d’une alternative

Existence de plusieurs alternatives (cid:1) choix non Existence de plusieurs alternatives (cid:1) choix non

déterministe

Non déterminisme: Absence d’un moyen de choix

irrévocable

La tâche essentielle d’un algorithme de recherche est de

prendre en charge le non déterminisme: guider la recherche d’une solution en faisant des choix et en gérant les retours sur ces choix tout en évitant l’explosion combinatoire.

36

I. Alaya

ENSI -ISID

37

Notion d’heuristique

• Une heuristique : du grec ancien eurisko, « trouver » • C’est un moyen (un critère, une procédure, un ensemble de règles) destiné à réduire les alternatives et guider les choix non déterministes que doit faire un algorithme de recherche recherche

• indispensable pour les problèmes NP-difficiles car

généralement en temps polynomial

• Une heuristique exploite généralement une information

spécifique au problème posé

• traduit une stratégie, une manière de penser, s'appuyant

sur notre connaissance du problème

37

I. Alaya

ENSI -ISID

38

Notion d’heuristique

• Exemple1: TSP

Soit (u0, u1, …, um) la solution partielle examinée à l’étape

courante (liste des villes visitées) et V={V1, …, Vn } courante (liste des villes visitées) et V={V1, …, Vn } l’ensemble des alternatives qui s’offrent à partir de um (villes restantes)

38

I. Alaya

ENSI -ISID

Notion d’heuristique

Exemple1: TSP Heuristiques possibles: • H1(V)=d(um,v)

Manouba

39

Bizerte

Tunis

Ariana

Radès

La Marsa

Soukra

39

I. Alaya

ENSI -ISID

40

Notion d’heuristique

Exemple1: TSP Heuristiques possibles:

H2(V)=d(um,v)+d(v,u0) (cid:1) un cycle doit revenir à u0 : ce H2(V)=d(um,v)+d(v,u0) (cid:1) un cycle doit revenir à u0 : ce qu’il reste à faire (heuristique sur la distance restante)

40

I. Alaya

ENSI -ISID

Notion d’heuristique

Exemple2: KP Heuristiques possibles: • Prendre à chaque fois • Prendre à chaque fois l’objet avec max profit H1(j)= max pj

• Prendre à chaque fois l’objet avec min poids H2(j)= min aj

41

I. Alaya

ENSI -ISID

42

Notion d’heuristique

Résumé • Il s’agit d’un moyen de choisir, parmi plusieurs directions, celle qui semble être la plus indiquée pour résoudre un problème

• Ce moyen peut être très efficace mais quelque fois peut • Ce moyen peut être très efficace mais quelque fois peut

induire en erreur et orienter vers une fausse piste.

• L’heuristique est généralement fondée sur une

simplification du problème initial, une relaxation des contraintes qui font que ce problème est difficile

• La qualité d’une heuristique peut se mesurer en terme de

réduction de la complexité de la recherche: une heuristique h1 est préférable à h2 si dans tous les cas h1 conduit à explorer moins d’alternatives que h2

42

I. Alaya

ENSI -ISID

Métaheuristique

• une heuristique est spécifique à un problème et

ne peut pas être généralisée

• méta + heuristique = au-delà + trouver (cid:1)

trouver avec un plus haut niveau d'abstraction trouver avec un plus haut niveau d'abstraction

• une métaheuristique est un ensemble de concepts : voisinage (modification d'une solution), utilisation de la mémoire...

• une méta-heuristique est une heuristique

généraliste, pouvant s'appliquer à plusieurs problèmes d'optimisation

43

I. Alaya

ENSI -ISID

Métaheuristique

Source d’inspiration biologique ou physique

• Algorithmes génétiques • Algorithmes génétiques • Recuit simulé • Optimisation par essaim de particules • Optimisation par colonies de fourmis (ACO) • …

44

I. Alaya

ENSI -ISID

Métaheuristique

45

I. Alaya

ENSI -ISID

Espace de recherche

L’espace de recherche est une collection de solutions

potentielles à un problème

• Comment chercher de bonnes solutions dans cet • Comment chercher de bonnes solutions dans cet

espace ?

• Il est important de connaitre les propriétés de cet

espace, e.g.,: ▫ Taille : liée à la représentation que l'on se fait des

solutions

▫ Structure : liée à la façon avec laquelle on se

ballade/cherche dans cet espace (paysage de recherche)

46

I. Alaya

ENSI -ISID

Taille de l'espace de recherche (SAT) • Pour n=100 variables, la taille de l'espace de recherche

est : 2100

• Avec 1000 solutions évaluées / sec : il faudrait 15

billions d'années pour évaluer moins de 1% de l'espace de recherche

• Pour k>2, k-SAT est NP-difficile ; k=2, Polynomial

47

I. Alaya

ENSI -ISID

Taille de l'espace de recherche (TSP) TSP de taille n (villes) • TSP symétrique : dist(x,y) = dist(y,x) • |S| = n!/2n = (n-1)! / 2 ; n>6 TSP > SAT • |S| = n!/2n = (n-1)! / 2 ; n>6 TSP > SAT • 10 villes = 181 000 solutions • 20 villes = 10 000 . 000000 . 000000 solutions • 50 villes = 100 000000000000000000000000000000 000000000000000000000000000000 solutions • Il y a 1 000 . 000000 . 000000 . 000000 litres d'eau

dans la planète !!

48

I. Alaya

ENSI -ISID

Paradigmes de recherche

• Construction solution construite par une suite de choix • Recherche locale (ou voisinage) une solution initiale

modifiée itérativement

• Évolution une population de solutions évolue par des

opérateurs génétiques (sélection, croisement, mutation)

• Hybridation mélange des approches précédantes

49

I. Alaya

ENSI -ISID

Approches constructives Approches constructives

•Définition •Les algorithmes gloutons •Optimisation par colonie de fourmis

Approches constructives

• Les approches constructives commencent à

partir d'une solution vide qu'elles construisent par incréments au fur et à mesure de la par incréments au fur et à mesure de la recherche

• Méthode de base: les algorithmes gloutons

51

I. Alaya

ENSI -ISID

Approches constructives

Algorithmes gloutons (greedy algorithm) • Principe : partir d'une solution initiale vide et

ajouter, d'une manière incrémentale, des composants de solutions sans remettre en cause les composants de solutions sans remettre en cause les choix antérieurs jusqu'à obtenir une solution complète.

• Deux questions essentielles :

– Définir l'ensemble des composants (les éléments) – Comment sélectionner les composants qui donnent

le profit optimal à chaque itération

52

I. Alaya

ENSI -ISID

Approches constructives

53

I. Alaya

ENSI -ISID

Approches constructives

Choix de l’élément (composant de solution) à

ajouter:

• Dans le cas le plus simple, de manière aléatoire. • Dans le cas le plus simple, de manière aléatoire. • De meilleurs résultats sont généralement

obtenus en utilisant une heuristique du bénéfice qu'apporte le composant à ajouter, c'est le critère gradient.

54

I. Alaya

ENSI -ISID

Approches constructives

Exemple 1: TSP

• Des algorithmes simples qui construisent des tournées de

qualité raisonnable

• Souvent utilisés pour construire une solution initiale pour • Souvent utilisés pour construire une solution initiale pour

d'autres heuristiques

• Plusieurs types d'algorithmes

– Itérativement étendre une tournée partielle connexe – Itérativement, construire des fragments de tournée et les connecter entre eux pour finalement former une tournée complète – Algorithmes plus complexes basés sur les arbres recouvrants de

poids minimums

55

I. Alaya

ENSI -ISID

Approches constructives (TSP)

Heuristique du Plus Proche Voisin • Commencer avec un sommet initial (choisi aléatoirement) • À chaque étape, prendre l'arête de poids minimum vers un

sommet non encore visité sommet non encore visité

• Étendre (v1, … , vk ) avec un sommet u non visité tel que

d(vk,u) soit minimale

• Compléter pour obtenir un cycle hamiltonien: relier la

dernière ville à la première (fermer la tournée)

56

I. Alaya

ENSI -ISID

Plus Proche Voisin (TSP)

Exemple

57

I. Alaya

ENSI 2012-2013

Approches constructives (TSP)

Heuristique d’Insertion

• Idée de construction : 1. initialisation : choisir aléatoirement une première ville 2. à chaque étape, un cycle de villes a été construit 2. à chaque étape, un cycle de villes a été construit y insérer LA ville qui minimise un critère donné • insertion du plus proche voisin (nearest insertion) : insérer la ville la plus proche des villes déjà visitées

• moindre coût (cheapest insertion) : insérer la ville ayant le moindre coût d'insertion (engeandrant la plus petite augmentation de la longueur du cycle)

58

I. Alaya

ENSI -ISID

Approches constructives (TSP)

Heuristique d’Insertion du PPV

Exemple

59

I. Alaya

ENSI 2012-2013

Approches constructives (TSP)

Plus Proche Voisin

Heuristique d’insertion

60

I. Alaya

ENSI -ISID

Approches constructives

Exemple 2: Knapsack Problem

• Heuristique possible: rajouter en priorité les objets ayant le meilleur rapport valeur/poids, jusqu'à ce que le sac soit rempli sac soit rempli

61

I. Alaya

ENSI -ISID

Approches constructives

Knapsack Problem

62

I. Alaya

ENSI -ISID

Approches constructives

Knapsack Problem

63

I. Alaya

ENSI -ISID

Approches constructives

Knapsack Problem

64

I. Alaya

ENSI -ISID

Approches constructives

Knapsack Problem

65

I. Alaya

Approches constructives

Knapsack Problem

66

I. Alaya

Approches constructives

Knapsack Problem

67

I. Alaya

ENSI -ISID

Approches constructives

Exemple 2: Knapsack Problem

Solution

Or on peut avoir

68

I. Alaya

ENSI -ISID

Approches constructives

Exemple 3: Bin Packing

• D'une façon générale, un problème de packing a pour objectif de

générer la meilleure allocation d'objets, sans qu'il y ait chevauchement

• Le problème du packing en deux dimensions intervient dans la • Le problème du packing en deux dimensions intervient dans la modélisation de nombreux problèmes principalement ceux liés aux placements et à la découpe fréquemment rencontré dans l'industrie du papier, du verre et du textile

• Dans le secteur informatique, on peut trouver des applications aux problèmes de bin packing lorsque l'on cherche à ranger des fichiers sur des supports informatiques, ou lorsqu'on cherche à affecter des tâches à des processeurs parallèles.

69

M. Bellalouna

ENSI -ISID

Problème du Bin Packing (BP)

• n objets , l’objet i est de taille xi inférieur à 1.

▫ Ln={ xi} 1≤ i ≤ n

• Une infinité de boîtes de même taille 1 • Un ensemble fini de solutions S : partition possible

de Ln

• Nombre de boîte de la solution G est m

G=B1

¨ B2

¨ …¨ Bm

• Objectif : chercher la répartition qui utilise le

minimum de boîtes.

70

M. Bellalouna

ENSI -ISID

Résolution du Bin Packing

• BP : Problème NP-Complet

• Résolution exacte pour les problèmes de petites tailles:

Branch&Bound, Programmation dynamique. Branch&Bound, Programmation dynamique.

• Résolution approchée : heuristiques gloutonnes très performantes surtout en moyenne

71

M. Bellalouna

ENSI -ISID

Heuristiques gloutonnes pour le BP

(cid:2) Next Fit (N.F) et Next Fit Decreasing (cid:2) First Fit (F.F) et First Fit Decreasing (cid:2) Best Fit (B.F) et Best Fit Decreasing

72

M. Bellalouna

ENSI -ISID

Heuristique Next Fit

Algorithme N.F : mettre le ième objet dans la dernière

boîte ouverte

j=1 Pour i allant de 1 à n faire

si xi peut être mis dans Bj, Bj sinon j ‹ Bj

{xi}

j+1

‹

‹ Bj

{xi}

73

M. Bellalouna

ENSI -ISID

¨ Heuristique Next Fit

x1

x2

x3

x5

x4

x6

74

M. Bellalouna

ENSI -ISID

First-Fit Algorithme F.F : mettre le ième objet dans la première boîte

qui peut le contenir

1. k=1

2. Pour i=1 à n faire 2. Pour i=1 à n faire Pour j=1à k faire

si xi peut être mis dans Bj, Bj

‹ Bj

{xi}

Si j ‹

k alors k‹

k+1 et Bk

‹

{xi}

75

M. Bellalouna

ENSI -ISID

¨ Best -Fit Algorithme B.F : mettre le ième objet dans la boîte qui minimise

l’espace perdu sur l’ensemble des boîtes ouvertes

1. k=1

2. pour i=1 à n faire

le niveau de la boîte j) le niveau de la boîte j)

Pour j=1 à k faire ( lj Pour j=1 à k faire ( l mettre xi , si possible , dans la boîte, Bu , qui minimise l’espace ( l

perdu

)

=

+

+

1

x

x

l

u

i

j

i

max 1 j

k

‹

alors Bu sinon k=k+1 Bk

Bu

{xi},

‹

{xi}, lk = xi

76

M. Bellalouna

ENSI -ISID

¨ £ £ £ Best –Fit-Decreasing

Algorithme B.F.D : Ordonner la liste ensuite appliquer l’algorithme

BF.

1. Ordonner la liste (on note yi le ième objet dans la liste triée) 2. k=k+1

3. Pour i=1 à n faire

le niveau de la boîte j)

Pour j=1à k faire ( lj mettre xi dans la boîte, Bu , qui minimise l’espace perdu alors Bu sinon k=k+1 Bk

{yi}, lk = yi

{yi} ‹

‹ Bu

77

M. Bellalouna

ENSI -ISID

¨ Heuristique Best Fit Decreasing

x1

x5

x3

x6

x2

NF

x1

x2

x3

78

M. Bellalouna

x4

x5

x4

x6

ENSI -ISID

79

Exercice : Heuristiques pour le BP

(cid:3) NF, FF , BF. Pour 10 objets de tailles :

Ln = {0,5;0,1;0,3;0,4;0,7;0,2; 0,6;0,6;0,1;0,5}

(cid:3) NFD, FFD, BFD. Pour 10 objets de tailles :

Ln = { 0,5; 0,7; 0,8;1; 0,1; 0,4; 0,3; 0,6; 0,2; 0,9}

79

M. Bellalouna

ENSI -ISID

Approches constructives

Avantages/ Inconvénient • en O(n) (ou polynomial) • une succession de choix localement optimaux ne garantit

pas une solution optimale

• l'utilisation du critère gradient dans les premières étapes

peut mener à des déplacements très faibles dans les peut mener à des déplacements très faibles dans les dernières phases de construction de solutions et engendrer des solutions de qualité médiocre.

• La performance des algorithmes gloutons dépend

étroitement de la pertinence de l'heuristique utilisée, i.e. leur capacité à exploiter les connaissances du problème.

(cid:1) Les métaheuristiques

80

I. Alaya

ENSI -ISID

Optimisation par colonie de fourmis Ant Colony Optimization (ACO)

• Approche constructive • Métaheuristique • Métaheuristique • Méthode stochastique • Méthode à base de population

81

I. Alaya

ENSI -ISID

Source d’inspiration

Les fourmis Réelles

Traces de phéromone: une substance chimique que les fourmis arrivent à détecter

Aptitude des fourmis à découvrir le plus court chemin

82

I. Alaya

ENSI -ISID

Source d’inspiration

• En se déplaçant, une fourmi dépose de la phéromone marquant le chemin par une trace de cette substance.

• En absence de traces une fourmi se déplace

aléatoirement

• Par contre, une fourmi qui rencontre une trace de

phéromone déjà déposée peut la détecter et décider de la suivre avec une probabilité proportionnelle à l'intensité de la trace

• Elle renforce ensuite cette trace avec sa propre

phéromone.

83

I. Alaya

ENSI -ISID

Source d’inspiration

?

50%

50%

84

I. Alaya

ENSI -ISID

Analogie

Fourmis réelles

ACO

l'environnement dans lequel les fourmis cherchent de la les fourmis cherchent de la nourriture

l'espace de recherche du problème problème

la quantité ou la qualité de la nourriture

la fonction objectif à optimiser

les traces de phéromone

une mémoire adaptative

85

I. Alaya

ENSI -ISID

Analogie

- Coopération : Traces de phéromones artificielles

- L’évaporation

- Politique de transition probabiliste

- MAJ de phéromone guidée par la qualité des solutions générées

Problème à résoudre

- Mémoire Privée

-Vivent dans monde discret

- Dépôt de phéromone

Solutions

86

I. Alaya

ENSI -ISID

8 6

Métaheuristique ACO

(cid:4) Modéliser le problème (cid:5) Recherche d’un chemin optimal dans un graphe appelé graphe de construction

(cid:4) Utiliser les fourmis artificielles (cid:5) Recherche des ‘bons’ chemins (cid:4) Utiliser les fourmis artificielles (cid:5) Recherche des ‘bons’ chemins (cid:5) Construction stochastique de solutions guidée par les traces de phéromone (cid:4) Mise à jour de phéromone

87

I. Alaya

ENSI -ISID

Ant System Dorigo 1991

Application au problème de voyageur de commerce

(cid:4) Phase Construction de solutions

(cid:5) Choisir une ville de départ (cid:5) Choisir la prochaine ville relativement à: - Information heuristique (h ) - Traces de phéromone (t )

( ) = tp k ij

b

a

[ ( ) t t [ ∑ ∑ t

] [ ] h ij ] [ ( ) a h t

ik

ik

b

]

(cid:4) Phase Mise à jour de phéromone

k k

( ) (cid:215)=+ t tr nt ij r = persistance m ∑

=

t

ij

k

=

1

( ) D+ t

ij

t

ij

m: nbr de fourmi Q: constante

Q L

k

Si l’arête (i,j)˛ Lk

88

I. Alaya

ENSI -ISID

(cid:215) (cid:215) D Phéromone

Information heuristique

( ) ( ) = = tp tp k k ij

b

[ [ ( ) ( ) t t t t [ [ ∑ t

] [ ] ] ] [ a h h ij ij ] [ ] [ ( ) a h t

ik

ik

b

] ]

k

Ville courante

Ville candidate

89

I. Alaya

ENSI -ISID

(cid:215) (cid:215) (cid:215) Ant System

Pour chaque cycle

Pour chaque fourmi

Choisir un noeud de départ

Pour chaque noeud

M. Dorigo, 1991

Choisir un noeud suivant probabilité:

Fin Pour

Fin Pour

Mettre à jour la phéromone sur les chemins construits par les fourmis

Mettre à jour la meilleure solution trouvée S*

Fin Pour

90

I. Alaya

ENSI -ISID

Variantes

Stratégie Élitiste Stratégie Élitiste

Donner à la meilleure solution un poids additionnel

ASrank ASrank

Tri les fourmis selon les coûts des solutions générées les w meilleures fourmis sont autorisées à màj la phéromone

ACSACS ACSACS

Seule la fourmi qui a produit la meilleure solution peut màj la trace de phéromone Probabilité de transition pseudo-proportionnelle

MMASMMAS

-Introduction des limites supérieures et inférieures aux valeurs de phéromone t - Seule la meilleure fourmi peut ajouter de la phéromone

min<=t

ij <=t

max

91

I. Alaya

ENSI -ISID

Optimisation par colonie de fourmis

Avantages / Inconvénients

++ L’utilisation des traces de phéromone permet d’exploiter l’expérience de recherche acquise par les fourmis et renforcer l’apprentissage pour la construction des solutions.

++ L’ACO peut être appliquée à n’importe quel problème ++ L’ACO peut être appliquée à n’importe quel problème d’optimisation combinatoire qui peut être formalisé comme une recherche de chemin optimal dans un graphe.

-- Un paramétrage non étudié de l’algorithme fourmi peut mener à des solutions sous-optimales.

-- Des travaux de preuve de la convergence à la solution optimale ont été proposés.

92

I. Alaya

ENSI -ISID

Intensification/ Diversification

Lors de la résolution d’un POC avec une approche heuristique, il s'agit de trouver un bon compromis entre deux objectifs relativement duaux : • Intensification de la recherche autour des zones de l'espace • Intensification de la recherche autour des zones de l'espace de recherche les plus prometteuses, qui sont généralement proches des meilleures solutions trouvées ; • Diversification de la recherche : favoriser l'exploration afin de découvrir de nouvelles et si possible meilleures zones de l'espace de recherche.

93

I. Alaya

ENSI -ISID

Optimisation par colonie de fourmis

Intensification/ Diversification

Dans ACO, la diversification peut être augmentée • soit en diminuant la valeur du poids du facteur phéromonal a (de sorte que les fourmis deviennent moins sensibles aux traces phéromonales), aux traces phéromonales), • soit en diminuant le taux d'évaporation r la phéromone s'évapore plus doucement et les écarts d'une trace à l'autre évoluent plus doucement). Lorsque l'on augmente ainsi la capacité exploratoire des fourmis, on trouve généralement de meilleures solutions, mais en contrepartie ces solutions sont plus longues à trouver.

(de sorte que

94

I. Alaya

ENSI -ISID

Évaluation des heuristiques

• les heuristiques n’offrent aucune garantie

d’optimalité : elles peuvent trouver l’optimum pour certaines données, ou en être très éloignées pour certaines données, ou en être très éloignées (cid:1) Le problème de l’évaluation de la performance

des heuristiques est crucial.

95

I. Alaya

ENSI -ISID

Évaluation des heuristiques Performance relative

• Définition • Soit un POC pour lequel on connait déjà la solution optimale. • Pour une heuristique H et une donnée d, on note H(d) le coût

de la solution heuristique et OPT(d) le coût optimal. On appelle performance relative de H sur d le quotient : appelle performance relative de H sur d le quotient :

• Pour un problème de minimisation, RH (d) ≥ 1

P. Lacomme et al, « Algorithmes de graphes » 2e édition 2003, Eyrolles.

96

I. Alaya

ENSI -ISID

Évaluation des heuristiques Performance relative

• Définition

Distance à l’optimum en % : 100 × (RH (d) −1)

La performance relative peut être calculée : • à priori: avant exécution de l’heuristique • à posteriori: si elle est imprévisible et ne peut être

calculée qu’après exécution de l’algorithme.

97

I. Alaya

ENSI -ISID

Évaluation des heuristiques Performance relative

• Évaluation à priori • Performance relative au pire On appelle performance relative au pire (worst case performance ratio) P d’une heuristique H sa plus performance ratio) PH d’une heuristique H sa plus mauvaise performance relative sur l’ensemble des données possibles :

98

I. Alaya

ENSI -ISID

Évaluation des heuristiques Performance relative

• Évaluation à priori • Performance relative au pire • Il s’agit d’une garantie de performance, qu’on obtient

mathématiquement par analyse théorique de H, et non par mathématiquement par analyse théorique de H, et non par des statistiques ou par énumération des données possibles. • Les démonstrations se font souvent en deux temps : on borne RH (d) pour toute donnée d, puis on construit une donnée montrant que ce pire cas peut être effectivement atteint.

• Ce genre de résultat est en général difficile à obtenir, et on n’en

connaît que pour quelques heuristiques

P. Lacomme et al, « Algorithmes de graphes » 2e édition 2003, Eyrolles.

99

I. Alaya

ENSI -ISID

Évaluation des heuristiques Performance relative

Évaluation à posteriori Bornes inférieures de l’optimum • Le plus souvent, on ne sait pas établir mathématiquement le

comportement au pire.

• On ne peut alors évaluer les résultats qu’après exécution de • On ne peut alors évaluer les résultats qu’après exécution de

l’heuristique H.

• Pour évaluer le résultat pour une donnée d, on peut calculer la

performance relative RH (d) à condition de connaître l’optimum. • Mais il n’existe pas de méthode exacte de complexité polynomiale

pour les problèmes NP-difficiles, à moins que P = NP.

• La valeur exacte de l’optimum n’est donc pas calculable en une

durée acceptable pour les problèmes de grande taille.

100

I. Alaya

ENSI -ISID

Évaluation des heuristiques Performance relative

Évaluation à posteriori Bornes inférieures de l’optimum (cid:1) Solution: si on dispose d’une évaluation par défaut

(minorant) B(d) pour l’optimum OPT(d). Dans ce cas :

• En particulier, si H(d) = B(d), alors on sait à posteriori qu’on a atteint l’optimum. On peut toujours trouver des bornes inférieures, même grossières, de l’optimum OPT(d).

101

I. Alaya

ENSI -ISID

Évaluation à posteriori Bornes inférieures de l’optimum

Exemples pour le TSP Soit un TSP à N villes, C la matrice des distances B1 : borne inférieure naïve • On fait la somme des N plus petits éléments de C.

• Critique : ils peuvent être sur la même ligne, et les arcs

correspondants, partant d’un même sommet, ne peuvent pas être sur un circuit hamiltonien.

102

I. Alaya

ENSI -ISID

Évaluation à posteriori Bornes inférieures de l’optimum

Exemples pour le TSP B2 : borne moins naïve • Le