11.6 Le probl` eme du sac `
a dos
339
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
V 1
. . .
V l−1
U l
U l+1
. . .
U d
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
Transition K
(k+1)
l
− − − − − − − − − −
− − − − − − − − −
− − − − − − − − −
− − − − − − − − − −→
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
V 1
. . .
V l−1
V l
U l+1
. . .
U d
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
avec un point V l ∈ {0, 1} uniform´ ement choisi dans l’ensemble
A
l
m k+1
(V 1 , . . . , V l−1 , U l+1 , . . . , U d )
= {u k ∈ {0, 1} tel que
1≤i
l+1≤i≤d p i U i
≤ p
et
1≤i
l+1≤i≤d w i U i
≥ m k+1
6. Signalons enfin que l’on peut combiner librement toutes les transitions
d´ ecrites dans le catalogue pr´ ec´ edent sur des p´ eriodes de temps choisies de
fa¸ con adaptative ou non.
11.6.3 Quelques variantes
Nous terminerons cette section, par deux remarques importantes conduisant ` a la confection de nouvelles s´ eries d’algorithmes stochastiques.
Les algorithmes g´ en´ etiques d´ ecrits plus haut sont fond´ es sur des mutations/explorations M k (u, v) des espaces de configurations A m k et sur des
s´ elections associ´ ees aux fonctions potentiel indicatrices g k = 1 Am k . Comme
nous l’avons soulign´ e plus haut, tous ces algorithmes de simulation peuvent
s’arrˆ eter d` es lors qu’une exploration-mutation locale dans un ensemble
A m k+1 n’am` ene aucun nouvel individu dans le niveau sup´ erieur A m k+1 .
Pour pallier ` a ces difficult´ es, on peut utiliser les algorithmes g´ en´ etiques
fond´ es sur des
M k -mutations et des
g k -s´ elections d´ ecrits en (11.9) ou au
besoin ceux fond´ es sur les approximations particulaires de ces quantit´ es
( g
N
k ,
M
N
k ) pr´ esent´ ees en (11.10).
Les probl` emes d’optimisation combinatoire d´ ecrits plus haut peuvent
aussi se traduire par un probl` eme de simulation de lois de probabilit´ es se
concentrant sur les extrema globaux du crit` ere `
a optimiser.
a dos
339
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
V 1
. . .
V l−1
U l
U l+1
. . .
U d
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
Transition K
(k+1)
l
− − − − − − − − − −
− − − − − − − − −
− − − − − − − − −
− − − − − − − − − −→
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
V 1
. . .
V l−1
V l
U l+1
. . .
U d
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
avec un point V l ∈ {0, 1} uniform´ ement choisi dans l’ensemble
A
l
m k+1
(V 1 , . . . , V l−1 , U l+1 , . . . , U d )
= {u k ∈ {0, 1} tel que
1≤i
l+1≤i≤d p i U i
≤ p
et
1≤i
l+1≤i≤d w i U i
≥ m k+1
6. Signalons enfin que l’on peut combiner librement toutes les transitions
d´ ecrites dans le catalogue pr´ ec´ edent sur des p´ eriodes de temps choisies de
fa¸ con adaptative ou non.
11.6.3 Quelques variantes
Nous terminerons cette section, par deux remarques importantes conduisant ` a la confection de nouvelles s´ eries d’algorithmes stochastiques.
Les algorithmes g´ en´ etiques d´ ecrits plus haut sont fond´ es sur des mutations/explorations M k (u, v) des espaces de configurations A m k et sur des
s´ elections associ´ ees aux fonctions potentiel indicatrices g k = 1 Am k . Comme
nous l’avons soulign´ e plus haut, tous ces algorithmes de simulation peuvent
s’arrˆ eter d` es lors qu’une exploration-mutation locale dans un ensemble
A m k+1 n’am` ene aucun nouvel individu dans le niveau sup´ erieur A m k+1 .
Pour pallier ` a ces difficult´ es, on peut utiliser les algorithmes g´ en´ etiques
fond´ es sur des
M k -mutations et des
g k -s´ elections d´ ecrits en (11.9) ou au
besoin ceux fond´ es sur les approximations particulaires de ces quantit´ es
( g
N
k ,
M
N
k ) pr´ esent´ ees en (11.10).
Les probl` emes d’optimisation combinatoire d´ ecrits plus haut peuvent
aussi se traduire par un probl` eme de simulation de lois de probabilit´ es se
concentrant sur les extrema globaux du crit` ere `
a optimiser.