Optimisation combinatoire

" D finition

Complexit d'un probl me: une estimation dans le

pire des cas du nombre d'instructions ex cuter

pire des cas du nombre d'instructions ex cuter

pour r soudre les instances de ce probl me.

cette estimation tant un ordre de grandeur par

rapport la taille de l'instance et consid rant

son instance la plus difficile.

21

I. Alaya

ENSI -ISID

Probl me de d cision / optimisation

" D cision : j existe-t-il une solution qui satisfait

j

k

une certaine propri t ? k

R sultat: oui ou non

R sultat: oui ou non

" Optimisation : j parmi les solutions qui

j

satisfont une certaine propri t , trouver celle qui

optimise une certaine fonction de co t. k

R sultat: une solution r alisable optimale

22

I. Alaya

ENSI -ISID

Probl mes de d cision

Classes de Probl mes

" La classe P contient l'ensemble des probl mes

polynomiaux, i.e., pouvant tre r solus par un

algorithme de complexit polynomiale

(cid:1)Cette classe caract rise l'ensemble des probl mes que l'on peut

(cid:1)Cette classe caract rise l'ensemble des probl mes que l'on peut

r soudre efficacement

r soudre efficacement

" La classe NP contient l'ensemble des probl mes

polynomiaux non d terministes, i.e., pouvant tre

r solus par un algorithme de complexit polynomiale

(cid:1)La r solution des probl mes de NP peut n cessiter l'examen d'un

grand nombre ( ventuellement exponentiel) de cas, mais que

l'examen de chaque cas doit pouvoir tre fait en un temps

polynomial

NP-complets : les probl mes les plus difficiles de NP

23

I. Alaya

ENSI -ISID

Lien entre d cision/optimisation

" A chaque probl me d'optimisation on peut

associer un probl me de d cision : d terminer

s'il existe une solution pour laquelle la fonction

s'il existe une solution pour laquelle la fonction

objectif soit meilleure quune valeur donn e?

" La complexit d'un probl me d'optimisation est

li e celle du probl me de d cision qui lui est

associ .

" Si le probl me de d cision est NP-complet, alors

le probl me d'optimisation est dit NP-difficile.

24

I. Alaya

ENSI -ISID

Classes de Probl mes

Diagramme dEuler pour les classes P, NP, NP-complet, et NP-difficile (NP-hard)

25

I. Alaya

ENSI -ISID

Cas du TSP

" Probl me de d cision: tant donn un entier L,

existe-t-il un cycle hamiltonien de longueur

inf rieure ou gale L?

inf rieure ou gale L?

(cid:1)NP-Complet

" Probl me doptimisation: trouver un cycle

hamiltonien de longueur minimale.

(cid:1)NP-Difficile

26

I. Alaya

ENSI -ISID

Chapitre 2

M thodes de r solution

M thodes de r solution

Optimisation = mod lisation + r solution

1. mod lisation d'un probl me : espace de recherche,

solutions

2. formulation math matique : fonction objectif,

contraintes

3. application d'une m thode d'optimisation

4. obtention d'une solution

28

I. Alaya

ENSI -ISID

D finitions

" m thode compl te : trouve toujours une solution, si

elle existe

" m thode exacte: trouve toujours la meilleure

solution (optimum global)

solution (optimum global)

" m thode approch e (approximative) :explore une

sous-partie de l'espace de recherche

" m thode d terministe: ex cute toujours la m me

suite d'op rations

" m thode probabiliste (ou stochastique) : fait des

choix probabilistes guid s par des tirages al atoires

29

I. Alaya

ENSI -ISID

Classification des m thodes d'optimisation

combinatoire

30

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 nSud de

" A chaque tape de la recherche, correspondant un nSud 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 nSud

" 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 dheuristique

Chaque tape de r solution repose sur deux op rations cl s:

" lop ration de d veloppement des alternatives

" Lop ration de choix dune alternative

Existence de plusieurs alternatives (cid:1) choix non

Existence de plusieurs alternatives (cid:1) choix non

d terministe

Non d terminisme: Absence dun moyen de choix

irr vocable

La t che essentielle dun algorithme de recherche est de

prendre en charge le non d terminisme: guider la

recherche dune solution en faisant des choix et en g rant

les retours sur ces choix tout en vitant lexplosion

combinatoire.

36

I. Alaya

ENSI -ISID

37

Notion dheuristique

" Une heuristique : du grec ancien eurisko, trouver

" Cest 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 dheuristique

" 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 }

lensemble des alternatives qui soffrent partir de um

(villes restantes)

38

I. Alaya

ENSI -ISID

Notion dheuristique

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 dheuristique

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

quil reste faire (heuristique sur la distance restante)

40

I. Alaya

ENSI -ISID

Notion dheuristique

Exemple2: KP

Heuristiques possibles:

" Prendre chaque fois

" Prendre chaque fois

lobjet avec max profit

H1(j)= max pj

" Prendre chaque fois

lobjet avec min poids

H2(j)= min aj

41

I. Alaya

ENSI -ISID

42

Notion dheuristique

R sum

" Il sagit dun 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.

" Lheuristique 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 dune 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 dalternatives 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 dinspiration 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

Lespace 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 dInsertion

" 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 dInsertion du PPV

Exemple

59

I. Alaya

ENSI 2012-2013

Approches constructives (TSP)

Plus Proche Voisin

Heuristique dinsertion

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 , lobjet i est de taille xi inf rieur 1.

Ln={ xi} 1d i d 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 9

Bj

{xi}

j+1

9

9 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

9 Bj

{xi}

Si j 9

k alors k9

k+1 et Bk

9

{xi}

75

M. Bellalouna

ENSI -ISID

Best -Fit

Algorithme B.F : mettre le i me objet dans la bo te qui minimise

lespace perdu sur lensemble 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 lespace

(

l

perdu

)

=

+

+

1

x

x

l

u

i

j

i

max

1

j

k

9

alors Bu

sinon k=k+1 Bk

Bu

{xi},

9

{xi}, lk = xi

76

M. Bellalouna

ENSI -ISID

Best Fit-Decreasing

Algorithme B.F.D : Ordonner la liste ensuite appliquer lalgorithme

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 lespace perdu

alors Bu

sinon k=k+1 Bk

{yi}, lk = yi

{yi}

9

9 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 dinspiration

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 dinspiration

" 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 dinspiration

?

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 dun 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 lar 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

++ Lutilisation des traces de ph romone permet dexploiter

lexp rience de recherche acquise par les fourmis et renforcer

lapprentissage pour la construction des solutions.

++ LACO peut tre appliqu e nimporte quel probl me

++ LACO peut tre appliqu e nimporte quel probl me

doptimisation combinatoire qui peut tre formalis comme une

recherche de chemin optimal dans un graphe.

-- Un param trage non tudi de lalgorithme 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 dun 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...