 GIÁO DC VÀ ÀO TO
TRNG I HC À LT
TRNG CHÍ TÍN
T S PHNG PHÁP DÒ TÌM NGU NHIÊN
VÀ NG DNG
 TÀI KHOA HC CP B (B2005-29-34)
À LT, 2006
 GIÁO DC VÀ ÀO TO
TRNG I HC À LT
T S PHNG PHÁP DÒ TÌM NGU NHIÊN
VÀ NG DNG
 TÀI KHOA HC CP B (B2005-29-34)
Ch nhim  tài: Trng Chí Tín
Các thành viên: ng Phc Huy
Trn Ngc Anh
À LT, 2006
C LC
i mu _______________________________________________________ 1
PHN I. Mt s kt qu v thut gii di truyn và mng nron ____________ 4
1. ng dng chin lc ng trong thut gii di truyn gii mt lp bài toán
i u toàn cc …..……………………………………………………… 5
2. Ci thin kh nng hc ca mng n ron truyn thng nhiu lp ……… 19
PHN II. Mt s kt qu v nung luyn mô phng ___________________ 30
1. S hi t ca thut toán nung luyn mô phng trong trng hp ri rc
…………………………………………………………………………. 31
2. Nung luyn mô phng: mt s nhn xét v s hi t ca xích Metropolis
…………………………………………………………………………. 51
3. Áp dng phng pháp nung luyn mô phng vào bài toán lp lch dòng
công vic ………………………………………………………………. 63
t lun _______________________________________________________ 97
1. Các kt qu chính v lý thuyt, ng dng và sn phm ca  tài …………... 97

Genetic Algorithms - DGA) ci tin có tc  hi t và  chính xác ca li gii
cao hn hn thut gii di truyn cn.
Ngoài ra, chúng tôi còn so sánh vic áp dng GA và DGA vào bài toán hc
lut qua mng nron nhân to (Artificial Neural Network - ANN), sau khi i tin
thut toán hc các tham s trong mng n ron. Trên bài toán mi, chúng tôi cng
thu c các kt qu tng t nh trên.
Phng pháp dò tìm ngu nhiên th hai chúng tôi  cp trong  tài này là
nung luyn mô phng - SA. ây là các thut toán ti u toàn cc ngu nhiên c
xây dng t vic bin th ca các thut toán mô phng kiu Metropolis da vào
các tham su khin bin thiên theo chu trình tin hóa ca thut toán. Thut
toán c gii thiu mt cách c lp bi S. Kirkpatrich, C. D. Gellatt, M. P.
Vecchi (1983) và Cerny (1985). Tên gi “simulated annealing” xut phát t s
2
ng t vi quá trình nung luyn ca c th trong mt b nhit ca vt lý cht
n. Các tên gi khác cho thut toán, chng hn là: nung luyn Monte Carlo
(Monte Carlo annealing- Jepsen và Gelatt, 1983), thut toán xác sut leo i
(Probabilistic hill climbing- Romeo và Sangiovanni- Vincentelli, 1985), làm ngui
thng kê (Statistical cooling- Aarts và Van Laarhoven, 1985; Storer, Becker và
Nicas, 1985)...
 nhng nm u ca thp niên 80 ca th k 20 cho n nay, thut toán
SA ã và ang thu hút s quan tâm ca nhiu ngi nghiên cu c v lý thuyt và
ng dng. S phát trin v lý thuyt ca thut toán gn vi các công trình ca các
tác gi nh: B. Gidas (1985), S. Anily và A. Federgruen (1985, 1986), D. Mitra, F.
Romeo và A. Sangiovanni- Vincentelli (1986), B. Hajek (1988), C. R. Hwang và
S. J. Sheu (1987, 1992), R. Holley, S. Kusuoka và D. Stroock (1989), O. Catoni
(1992, 1998), D. Marquez (1997), P.D. Moral và L. Miclo (1999)... . Bên cnh ó
SA cng ã c áp dng  gii nhiu bài toán ti u t hp c ln thuc lp NP
- khó, các bài toán thc trong công ngh và kinh t - xã hi.
Trong các áp dng ca SA vào các bài toán thc tin, có nhng áp dng th
hin tính hiu qu ca phng pháp SA nhng cng có không ít các áp dng SA

và trân trng cm n.
Chúng tôi cm n trng i hc à Lt, Khoa Toán - Tin ã to nhiu
u kin thun li  chúng tôi tin hành và hoàn thành  tài này.
à Lt, tháng 3 nm 2007
Nhóm tác gi
4
PHN I
t s kt qu v thut gii di truyn và mng nron
5
ng dng chin lc ng trong thut gii di truyn
gii mt lp bài toán ti u toàn cc
Trng Chí Tín, Trn Ngc Anh
Khoa Toán  Tin, i hc à Lt
E-mail:
Tóm tt: Khi áp dng các thut gii di truyn (GA) cn cho bài
toán ti u toàn cc, quá trình tìm kim li gii ti u thng gp hn
ch là tc  hi t chm và  chính xác ca li gii không cao. 
khc phc hn chó, chúng tôi  ngh áp dng chin lc ng theo
xác sut vào phép lai ci tin và phng pháp hiu chnh tuyn tính
a D.E.. Goldberg c tng quát hóa. Kt qu thc nghim, khi gii
t lp bài toán ti u toàn cc vi c trng có rt nhiu cc tra
phng, cho thy phng pháp mi có u m ni bt là tc  hi
 nhanh và  chính xác ca li gii ti u rt cao.
 khóa: i u toàn cc, GA, hiu chnh tuyn tính, lai.
1. MU
Trong bài này chúng tôi áp dng chin lc ng vào toán t lai và vào phân
phi xác sut chn tp con  bin hóa và tái to qun th mi trong thut gii di
truyn nhm gii bài toán ti u toàn cc sau ây:
Bài toán: Cho hàm s n bin thc f : D → R, vi
∏

1
, p
2
∈ D, không gim tng quát, ta có th g s p
1
là cá th tri (p
1
có  thích nghi F
0
cao hn p
2
: F
0
(p
1
) ≥ F
0
(p
2
)).
Trong phép lai cn theo kiu s hc thì:
ch
1
= p
1
+ *δ’, (2.0)
ch
2
= p
1

)(
021
tppsign
t
t
suaátxaùcvôùi
suaátxaùcvôùi
δδ
δ
δ
(2.2)
trong ó: δ’ = (p
2
– p
1
),



≤−
>−
=
121
121
0
if,
if,
pppb
ppap
δ

ln lt s gn cá th tri hoc ln tng ng
khi t → T (giai n cui ca quá trình tin hóa).
2.2. Phng pháp hiu chnh tuyn tính ng
Gi s qun th ban u gm N cá th. F
0
=
{ }
N
i
i
F
1
,0
=
là  thích nghi chun
hoá ca các cá th th i (i = 1..n): 1
1
.0
=
∑
=
N
i
i
F , do ó
{ }
N
i
i
F

0
ph
thuc vào tham s C
0
tng qt.
Gi s dãy
{ }
N
i
i
F
1
,0
=
không đồng nhất là hằng, gi:
.,
1
,1,
)1(
,
11
},..1,min{},..1,{
min2
0
0
,1
min
min
0
min0

−
−
=∆≤=<
−+
=
======
∑
=
ββ
(2.7)
Chn





≥
<
=
)B(if,
)(if,
0
00
2
,1
caseTBF
AcaseTBF
C
CC
β

−−
NimbYaYFY
FXY
m
i
m
i
m
i
iii
..1,1,.)(
)1()1()(
,0
)0(
(2.11)
 nay v sau, ta ln gi s các gi thit (2.9) và (2.10) ca mnh  1 c
tha mãn.
nh  2 di ây ch ra mi liên quan gia vic chn các h s a, β vi
tính cht co hoc giãn ca PPXS mi.
nh  2: Vi mi m > 0,
a) Nu a > 1 ⇔ β < 0
8









0
)1(
max
)1(
min
⇔
)1(
max
)(
max
−
>
mm
YY ⇔
)1(
min
)(
min
−
<
mm
YY
thì: ∀ i = 1..N
)()1()1( m
i
m
i
m
i
YYXXY <<⇔>

max
−
<
mm
YY ⇔
)1(
min
)(
min
−
>
mm
YY
thì: ∀ i = 1..N
)()1()1( m
i
m
i
m
i
YYXY >⇔>
−−
)()1()1( m
i
m
i
m
i
YYXY <⇔<
−−

−
−
−
−
caseA
X
Y
C
Y
caseB
X
Y
C
Y
m
m
m
m
m
m
:)(
0
:
0
)1(
)1(
max
0
)1(
min

)1(
)(
0
X
Y
C
k
Max
k
−
∈ : )1(1
)1(
)(
0
−+=
−
X
Y
C
k
Max
k
θ , vi )1;0(
∈θ nh. Khi ó:
a.
X
k
C
θ
θ

min
θθθθ (2.13)
c.
NikXY
k
i
..1,,
)(
=∀∞→→ . C th hn,
Ni ..1=∀
Nu XX
i
≤ thì 1,
)(
≥∀≤ kXY
k
i
và ∞→↑ kXY
k
i
,
)(
Nu XX
i
≥ thì 1,
)(
≥∀≥ kXY
k
i
và ∞→↓ kXY

}{,1
=
≥∀ cng là dãy
ng và
∞→→−=∆=−
+
−
=
∑
kXXaYY
N
kii
k
N
i
kk
N
,0)(
1
,1
1
1
)(
1
)(
e. ,1
)(
0
→
k

kk
Max
k
YX
YY
)(
)(
)(
)1(
min
)1()1(
min
)1()1(
)1(
)1(
)(
0
−
−−−−
−
−
−
−
+=−∆+=
k
k
Max
kk
Max
k

−−
−
==
k
k
C
k
YX
YX
k
λ
λ
ββ
,
);1(1
)1(
min
)1(
min
)1(
min
)(
−−
−
−
∈
−
+=
kk
k

i
),(
min
min
)()(
(2.15)
10
c bit:
∞→∆=−
−
≡↑
∞
kXXX
XX
X
YY
MaxMax
k
Max
,)(
)0(
min
min
)()(
, (2.16)
c.
Ni ..1=∀
:
)(k
i

∞
→ , 1
)(
↓
k
a , 0
)(
→
k
β ,
∞→k
Chng minh:
1) . Các kt lun 1.a và 1.b là d dàng chng minh.
. Kt lun 1.c c suy ra t tính cht ca gii hn kp và phng pháp chng
minh phn chng.
. Kt lun 1.d là d dàng chng minh.
. Kt lun 1.e c suy ra tnh ngha ca
)(
0
k
C và kt lun 1.b.
2) . Kt lun 2.a là d dàng chng minh.
.  chng minh kt lun 2.b, trc tiên ta nhn xét rng vi:
)1(
min
)1(
min
)(
)(
)(

)0(
min
)1(
min
)(
min
)1(
min
)1(
min
)1(
min
)1(
min
)()1(
min
)1(
min
)1(
min
)(
min
θθθ
θλη
ng t: ∀ i
0
= 1..N:
k
k
ik

min
)(
min
)(
min
min
min
1
)(
min
)(
min
,
XX
XX
YX
YX
B
XX
XX
YX
YX
A
k
k
k
k
k
k
k







−
−
−=
++=
+
−
=
+==
+
∑
∏∏
min
minmin
min
0
min
1
1
0
1
0
0
)1(
0

11
∞→→>
−
==
∑
∏
−
=
+
=
jkhiv
XX
vvC
j
k
j
j
ji
i
j
jj
k
,0,0
)(
,
~
1
0
1
min

i
i
k
i
),(
min
min
0
)(
0
)(
0 θ
λ
u chn i
0
c bit: x
i0
= x
min
thì:
)(
1
0
min
)(
0
XXX
CY
i
−

kCC
kk
luân phiên nh
sau:
+ 0
)2(
min
>
k
Y , chn:
)2()2(
0
kk
C ∆= ,
)1(
)2(
)2(
min
)2(
min
)2(
)2(
>>
−
−
=∆
X
Y
YX
YY

)(0
)2()0()2()12(
)2(
min
)12(
min
k
YXXY
YY
k
Max
kk
Max
kk
Ngha là: các dãy ch s lng vi
)(
min
)(
,
kk
Max
YY là các dãy hng.
+ Tip tc, chn:
)1;0(),1(1:
12
)12(
12
)12(
0
)12(

)12(
)12(
0
−
−
==
+
++
+
+
k
kk
Max
C
k
C
XCY
k
ββ
. Khi ó: 10
1212
<=<
++ kk
a θ
Khi ó: