Ecole Nationale des Sciences de l'Informatique *tÉ*
A.U.2013-2014
OptimisationCombinatoire : MéthodesApprochées . : :,
TD NO2
Exercice I : Recherche Tabou
'^
On considère I'ensemble S des 16 premiers entiers naturels càd de 0 à 15 écrit* en binaire sur 4 bits. On adopte coflrme transformation élémentaire le .changement dbn bit en son cornplémentaire. On définit sur S une fonction f dont les valeus sont précisées par le tableau suivant :
't,
/(, )
ü I
II ,
.]
I
)
3
'i
1
,)
0
$
6
i 4
r,
lq I
I I
1ü
i,
11 6
1.) I
t? rj { 3
15 ,
La valeur portée en gras est la valeur prise par f pour I'entier associé. On considere le graphe dont les sommets sont les entiers de 0 à 15 et deux sommets bont reliés par une arête si les deux entiers qu'ils re'présentent ne différent dans leur écriture en binaiie que d'un seul bit; la valeur associé au sommet est la valeur prise par f pour I'entier. Représenter le:graphe. Notons, pour I < i < 4, tior (respectivement tiro) la transformation consistant à chaager le.i*bit d:e,0 en 1 (respectivement t 'en 0)
1,.-i
1. En partant de llll, appliquer la méthode Tabou avec la liste de taille I et.en
supposailt que le nombre d'itérations fixé par ltrtilisateur est assez grgde.
tz Il.sfe fcbuue
++(10
llll -* 11It)
-t-è4--+
---+_t,-+_+
-l---+---++
..j+Jld
--+ ---r ----+ --i
--+---+--+--+
-r--+---+5+
-+ --+ *--+ ---+-*+
--+-+---+*,
2. En partant de 1111, appliquer la méthode Tabou avec la liste de taille 2.
fr list*'fLtbuut'
II11 -r tll0 +---+---+--l
*To
--+---+r+--+
Publicité
+JJé
--+-'-+-i---+
JJJJ
3. En
de 11 11, appliquer la méthode Tabou avec la liste de taille 3
t1 lislc f ttbu ue
4.Jtl0
lIlI -'il10 ----+--+-+.."+
--+---+--+--+
14--+--+rr
-+€-.+-+
---+--+--+---+
4. En partant de I 111, appliquer la méthode Tabou avec la liste de taille 4. llll -+ ltf0 --+--+--+--+ rJ{ro
f /,islc fttâ{rue
-+--+-+--+
--+---+-+---+
JJJJ
5. Est-il utile dnenvisager des tailles supérieures à 4?
+r( /i-çfc /aüutit
llll ---* lIIt) JJtrft
---+rr---+
fiJ..j
JfJJ
Exercice 2 : Optimisation par colonies de fourmis
Reprenons l'exemple du TSP de I'exercice 3 du TD1, dont voici la matrice de coûts ;
n
I .-t b {-'
L) E
I BC T} E T' -l 10 ll x;t lU .$ \ , ll i i +Jx15lU lUirlxli llJi2)c:l trU tl
.tü -l
:1 )c
Nous 4llons appliquer la version Max-Min Ant System (MMAS) pour résoudre ce problème. Dans cette version les traces de phéromone sont initialisées à une bome maximale ro,"* , , ,doivent êlre bomees entre rr*,, et. -"*o (borne inférieure), et seuleument la meilleure fourmi
dépose la phéromone. , Ncius supposons'que les valeurs des paramètrqs de MMAS sont les suivants : Les cogfficients de pondération dans la probabilité de transition o:l et B :1
: Le,coe,ffioient d'évaporation p:0.01 .
T-a* :6 lrnin:0. 1
;
: l
1,. Proposer une information heqislique. 2. Qug peut refléter les traces de pheromone à deposer sur les chemins visités par les
, ,,ir
fourmis ?
3. En partant de la ville A, quelle est la probabilité de choisir la ville C? 4. Après au moins combien de cycles latrace de phéromone vâ atteindre t*i,,? 5. Sppposgns que la meilleure solution trouvé pendant ce cycle est la suivante:
ABCDEF, donner la matrice de phéromone après inise à jour.
TÔA,
M' 4/ Urh l" labvu À, -t-"lk -"w
hL
LrL "[eLe'
.l/ /i
a
Jÿ'/Y- ,^l ' 3' l-f+
,r.*€al^fl^Mr
+-
,t 1" ,/ Trn"Æ2,., \r, oo--s9 !, Aoûo,-sÇ O4AO..-)e
Publicité
a44" -4atrl/q 4o -s 4444 /)144 -, ü14A ,th <7o\i' ,+!^ 'i âo- rvvt
L*cL
aT^,l
.6
Àv4rsc- ü4o-r3 446 4 46U .4 44§
-tt .n)
/-,^§)
(
è ô-Lü\adt
l.e ^»n -eh no^ p.,-l )q \r'r1\. îa,to"
o^ Je.l,' /W/ l" ,rrrm
§
*C
rt
At ->/t
)-^ L L(,
NAo -J I rtt .Ë, -t:"
onlfi *6Y1o1
01ot->o0oo
3 kno
Urb TâLa,p À'tàflt-tr f" '"{ff-i'
w ntutttu'to"l-e{ n*' 6t:
à144àltt l,i;"
Lo4^1oml16Ao4-" o4I {,,e*Fi4.,'" 1
O [oo-ol
,-.*...*
-"*,4J,".
!:"q*.. t-
I--.'.**]--."- ioar.5e{oa i6 fi4-:,w4 L. -h',' r:"1 À: *^ /ê Sgl*1.r"
l
L
_t jr& î.e)oP., 3/ x'f -- --t I'r--l l^g\r I îsfrw" I
vDn 5) c,
a J-!dâ â Lh
(^ -ü ùr^ilt - ü
! z'
r{ m UX
rf , \)fik r{a; n*r
,C;,
' e St
,l-,r^\ ; ''' (+)^ (6)' +. t"
= :a_ ,.d 'ô'
\.Ç" +"
6_*
(I*"rt*lt ü.k'#" r;-"7 ) r,n; bA;"
\
(r,',' ( *aSv
-t
9 61' u%tu 3) , yroL (c) = t) pr; -. k q[ t nti, G,t \-* §( '7ç
o( _É
^à
/
Publicité
6rç'
*C*,^
,
)\
-q
Zi;'(L-P)(;ù*AG
0\
p".lt; ( 'e tioCI J- /^a^*- y'^ &\
nho
{r*,";. Z
AJ
cfi&'
^o,i -'fu ut'M î? #îY*' fi,,w Ace€ pr*^'*y^ lS; ^ii;i*rn s#'"rr z) *{,s,x *- Ç1AT Êk *'{'oin*'8{'"ÿ z-/ [ ,' ,)6;t ÿri V'i' (^ - t t 6; , 7-À' te ''û eÇ =;ffæÛ ^7,-A*
.ilÿ,,^^ ,*!a
'
f--- é,a1% * L Q o,13 ,rrl|
Wri 5)
/:a- ( /\ , \_iz
'A,4ü ôn fÉ^d 6 . (,4u > Too*,
1* tr&
àr. ÇûQarA
ft.P srll
5ÿi
I
:
i i
l
Ç1ÿ
t1
ç,,1ü
Ç28
i
q
..t} ü
r:
i
Ç,§.&
§§
ç$,x
\ i
t
i I
i
I \
H
s
,_â r** t""Lé r-.I
Trj-g% â'0" *t , Çr18 A} =(n-f) Ç* - ( 4-(ÿ O.,4: iA,19n' fl : lrCX
Cn*" 6t
e,i