11.6 Le probl` eme du sac `
a dos
335
simulation autour des configurations visit´ ees x ∈ A k d’un nombre N
de variables auxiliaires/pr´ edictives (Y
i
k (x)) 1≤i≤N selon les distributions M k (x, y).
M k (x, y) N ↑∞ M
N
k (x, y) :=
1
N
N
i=1
1 Y i
k (x) (y)
Les approximations correspondantes sont alors donn´ ees par les formules suivantes :
M k (x, y) N ↑∞
M
N
k (x, y) :=
M
N
k (x, y)1 A k+1 (y)
M N
k (1 A k+1 )(x)
g k (x) N ↑∞
g
N
k (x) := M
N
k+1 (1 A k+2 )(x)
(11.10)
Le nombre de variables auxiliaires N
peut varier avec le temps. En pratique,
on choisira la taille N
suffisamment grande de sorte ` a avoir M
N
k (1 A k+1 )(x) >
0 sur chaque site visit´ e lors de l’exploration g´ en´ etique.
11.6 Le probl` eme du sac ` a dos
11.6.1 Description du probl` eme combinatoire
Reprenons le probl` eme du sac ` a dos pr´ esent´ e dans la section 6.5.5. Dans
cette situation, on choisit des sous ensembles (A m k ) ∀0≤k≤n associ´ es ` a des
valeurs minimales croissantes (m k ) k≥0 et d´ efinis par la formule suivante
A m k :=
(u 1 , . . . , u d ) ∈ {0, 1}
d :
d
i=1
w i u i ≥ m k
et
d
i=1
p i u i ≤ p
(11.11)
On rappelle que p
(≥ min i p i ) d´ esigne un poids maximal autoris´ e fix´ e qui
d´ epend de la capacit´ e de transport du sac ; les couples (p i , w i ) repr´ esentent
le poids de l’objet i et sa valeur. Lorsque m k >
d
i=1 w i , la valeur minimale
requise est sup´ erieure `
a celle que l’on peut r´ ealiser ; dans ce cas, l’ensemble A k
est vide (et vise versa). On conviendra donc par la suite que (m k ) 0≤k≤n d´ esigne
une suite croissante de niveaux de qualit´ e recherch´ ees avec m n ≤
d
i=1 w i .
Dans cet exemple du sac ` a dos, l’objectif est double. Tout d’abord, il
convient de calculer le nombre de sacs ` a dos r´ ealisables ayant une valeur minimale fix´ ee. Le second objectif est d’explorer al´ eatoirement et uniform´ ement chacun de ces espaces.
a dos
335
simulation autour des configurations visit´ ees x ∈ A k d’un nombre N
de variables auxiliaires/pr´ edictives (Y
i
k (x)) 1≤i≤N selon les distributions M k (x, y).
M k (x, y) N ↑∞ M
N
k (x, y) :=
1
N
N
i=1
1 Y i
k (x) (y)
Les approximations correspondantes sont alors donn´ ees par les formules suivantes :
M k (x, y) N ↑∞
M
N
k (x, y) :=
M
N
k (x, y)1 A k+1 (y)
M N
k (1 A k+1 )(x)
g k (x) N ↑∞
g
N
k (x) := M
N
k+1 (1 A k+2 )(x)
(11.10)
Le nombre de variables auxiliaires N
peut varier avec le temps. En pratique,
on choisira la taille N
suffisamment grande de sorte ` a avoir M
N
k (1 A k+1 )(x) >
0 sur chaque site visit´ e lors de l’exploration g´ en´ etique.
11.6 Le probl` eme du sac ` a dos
11.6.1 Description du probl` eme combinatoire
Reprenons le probl` eme du sac ` a dos pr´ esent´ e dans la section 6.5.5. Dans
cette situation, on choisit des sous ensembles (A m k ) ∀0≤k≤n associ´ es ` a des
valeurs minimales croissantes (m k ) k≥0 et d´ efinis par la formule suivante
A m k :=
(u 1 , . . . , u d ) ∈ {0, 1}
d :
d
i=1
w i u i ≥ m k
et
d
i=1
p i u i ≤ p
(11.11)
On rappelle que p
(≥ min i p i ) d´ esigne un poids maximal autoris´ e fix´ e qui
d´ epend de la capacit´ e de transport du sac ; les couples (p i , w i ) repr´ esentent
le poids de l’objet i et sa valeur. Lorsque m k >
d
i=1 w i , la valeur minimale
requise est sup´ erieure `
a celle que l’on peut r´ ealiser ; dans ce cas, l’ensemble A k
est vide (et vise versa). On conviendra donc par la suite que (m k ) 0≤k≤n d´ esigne
une suite croissante de niveaux de qualit´ e recherch´ ees avec m n ≤
d
i=1 w i .
Dans cet exemple du sac ` a dos, l’objectif est double. Tout d’abord, il
convient de calculer le nombre de sacs ` a dos r´ ealisables ayant une valeur minimale fix´ ee. Le second objectif est d’explorer al´ eatoirement et uniform´ ement chacun de ces espaces.