I H C KHOA H C T
NHIÊN THÀNH PH
KHOA CÔNG NGH
MÔN CÔNG NGH
H
CHÍ MINH
THÔNG TIN
TRI TH C
²²²
Lê Minh – 0012158
Ph m H u Lê Qu c Ph c – 0012169
PH C H I THÔNG TIN T
D
LI U
QUAN SÁT B NG THU T GI I DI
TRUY N
LU N V N C
NHÂN CÔNG NGH
Giáo viên h
ng d n
TS. Nguy n
ình Thúc
Niên khóa 2000-2004
THÔNG TIN
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
I C M
N
Chúng em xin chân thành cám n Khoa Công Ngh Thông Tin,
tr
ng
i H c Khoa H c T
Nhiên Thành ph H Chí Minh
u ki n cho chúng em th c hi n
tài lu n v n t t nghi p này.
Chúng con xin g i l i bi t n sâu s c
ch m sóc, nuôi d y chúng con thành ng
Chúng em xin chân thành cám
n tình h
ã t o
n ông bà, cha m
ã
i.
n th y Nguy n
ình Thúc
ã
ng d n, ch b o chúng em trong su t th i gian th c hi n
tài.
Chúng em xin chân thành cám n các th y cô trong Khoa Công
Ngh Thông Tin ã t n tình gi ng d y, trang b cho chúng em nh ng
ki n th c quí báu trong b n n m h c v a qua.
c dù chúng em ã c g ng hoàn thành lu n v n trong ph m
vi và kh n ng cho phép nh ng ch c ch n s không tránh kh i nh ng
thi u sót. Chúng em kính mong nh n
c s c m thông và t n tình
ch b o c a th y cô và các b n.
Nhóm sinh viên th c hi n:
Lê Minh - Ph m H u Lê Qu c Ph c
-2-
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
I GI I THI U
Máy tính ngày nay ã tr thành m t trong nh ng công c quan
tr ng. Có
c
c
u ó là do máy tính có hai
m m nh ch y u là
x lý và kh n ng l u tr . S phát tri n c a Trí tu Nhân t o
làm cho máy tính càng thông minh h n. K t h p v i nh ng kh n ng
ang ngày càng hoàn thi n c a máy tính, các
Nhân t o có m t
ng d ng c a Trí tu
kh p m i n i và ang d n làm thay
i cu c s ng
a chúng ta.
n thân Trí tu Nhân t o bao g m nhi u l nh v c nghiên c u
nh nh : H chuyên gia, Nh n d ng, X
gi i di truy
ã
t
ã và
, m i l nh v c khi
c áp d ng vào trong th c t
c m t s thành t u nh t
ang là m t công c
lý nh, M ng N ron, Thu t
u
nh. Riêng Thu t gi i di truy n
m nh m
c áp d ng r ng kh p, t
ph c v cho h c t p (s p x p th i khóa bi u, t i
u hóa hàm s
gi i trí (nâng cao tính trí tu
n ng d ng trong
công nghi p
thi t k
cho games ), cho
em l i l i nhu n (nh
),
trong khai thác d u khí, trong
máy móc, trong khai thác h m m , giao thông công c ng,
trong s n xu
) và ngay c trong l nh v c
tài Ph c h i thông tin t
gi i di truy
d
u tra t i ph m.
li u quan sát b ng thu t
nh m tìm hi u v vi c áp d ng Thu t gi i di truy n
trong Trí tu Nhân t o vào l nh v c
u tra t i ph m. M c tiêu là
ph c h i l i thông tin v m t khuôn m t ng
c.
-3-
i t nh ng thông tin r i
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
c c chính c a lu n v n nh sau:
§ Ch
ng 1: Ph c h i thông tin t d li u quan sát b ng thu t gi i
di truy n
Ch
ng này gi i thi u v
tài và trình bày tóm t t v
thu t gi i di truy n, thu t gi i chính
§ Ch
ng 2: D ng nh chân dung t
c s d ng trong
tài.
quan sát b ng thu t gi i di
truy n
Ch
ng 2 trình bày v các thu c tính
c s
d ng cho
bài toán, cách mã hóa các thu c tính này và áp d ng các thu c
tính này vào thu t gi i di truy n.
§ Ch
ng 3: H th ng h tr tìm ki m nh chân dung d a trên mô
Ch
ng 3 trình bày v mô hình cài
a vào lý thuy t
§ Ch
t c th cho bài toán
c kh o sát trong các ch
ng trên.
ng 4: K t lu n
Nh ng k t qu
ã
lai, ó là nh ng n i dung
t
c, h
ng phát tri n cho t
c trình bày trong ch
-4-
ng này.
ng
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
C L C
CH
NG 1
PH C H I THÔNG TIN T
D
LI U QUAN SÁT B NG THU T GI I
DI TRUY N-------------------------------------------------------------------------------------------------------------- 9
1.1
PHÁT BI U BÀI TOÁN------------------------------------------------------------------------9
1.2
THU T GI I DI TRUY N ------------------------------------------------------------------ 10
1.2.1 Thu t gi i di truy n t ng quát ----------------------------------------------------------------10
1.2.1.1 Các b
c trong thu t gi i di truy n---------------------------------------------------------------- 12
1.2.1.2 Cách bi u di n --------------------------------------------------------------------------------------- 13
1.2.1.3 Kh i t o qu n th ------------------------------------------------------------------------------------ 14
1.2.1.4 Các phép toán trên thu t gi i di truy n------------------------------------------------------------ 14
1.2.2 Thu t gi i di truy n t
CH
NG 2
ng tác ----------------------------------------------------------------16
NG NH CHÂN DUNG T
QUAN SÁT B NG THU T GI I DI
TRUY N---------------------------------------------------------------------------------------------- -------------------19
2.1
GI I THI U ------------------------------------------------------------------------------------ 19
2.2
ÁP
DUNG
NG THU T GI I DI TRUY N GI I BÀI TOÁN PH C
MÔ
20
2.2.1
c tr ng và mã hóa
2.2.1.1
I NH CHÂN
c tr ng chân dung -------------------------------------------------20
c tr ng --------------------------------------------------------------------------------------------- 20
2.2.1.2 Mi n xác
2.2.1.3 Mã hoá
nh c a các
c tr ng ------------------------------------------------------------------ 22
c tr ng ------------------------------------------------------------------------------------ 25
2.2.2 Hàm thích nghi ---------------------------------------------------------------------------------27
2.2.3 Thu t gi i di truy n----------------------------------------------------------------------------29
2.2.3.1 Các phép toán ---------------------------------------------------------------------------------------- 29
2.2.3.1.1 Tái sinh ---------------------------------------------------------------------------------------- 29
2.2.3.1.2 Lai ---------------------------------------------------------------------------------------------- 30
2.2.3.1.3
t bi n ---------------------------------------------------------------------------------------- 33
2.2.3.1.4 Ch n l c --------------------------------------------------------------------------------------- 35
2.2.3.2 Thu t gi i --------------------------------------------------------------------------------------------- 36
2.2.3.2.1 Tham s ---------------------------------------------------------------------------------------- 36
2.2.3.2.2 Thu t gi i -------------------------------------------------------------------------------------- 36
2.2.4 Tìm ki m trong c s d li u nh chân dung -----------------------------------------------38
2.2.4.1 Xây d ng CSDL nh chân dung ------------------------------------------------------------------- 39
2.2.4.2 T ch c c s d li u nh chân dung ------------------------------------------------------------- 46
2.2.4.3 Tìm ki m --------------------------------------------------------------------------------------------- 48
CH
NG 3
TH NG H
TR
TÌM KI M NH CHÂN DUNG D A TRÊN MÔ
------------------------------ -------------------------------------------------------------------------------------------52
-5-
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
3.1
TH NG --------------------------------------------------------------------------- 52
3.2
CÁC MÔ UN
3.2.1 S
TH NG ------------------------------------------------------------------ 54
màn hình---------------------------------------------------------------------------------54
3.2.2 Mô un Mã hóa nh ----------------------------------------------------------------------------58
3.2.3 Mô un Ph c h i chân dung-------------------------------------------------------------------59
CH
4.1
NG 4
T LU N ----------------------------------------------------------------------------70
NH N XÉT ------------------------------------------------------------------------------------- 70
4.1.1 Nh ng k t qu
t
c-----------------------------------------------------------------------70
4.1.2 Khó kh n và h n ch --------------------------------------------------------------------------71
4.2
NG PHÁT TRI N ----------------------------------------------------------------------- 72
-6-
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
DANH M C CÁC HÌNH V
Hình 1-1 L
Hình 2-1 S
c
c a m t thu t gi i di truy n t
t ng quát c a bài toán. Trong
ng tác ---17
ó, mã hóa
nh
chân dung là m t trong hai ti n trình quan tr ng. -----39
Hình 3-1 Hai mô un chính c a h
Hình 3-2 S
th ng ---------------------52
màn hình -----------------------------------54
Hình 3-3 Màn hình chính c a ch
Hình 3-4 Màn hình mã hóa
ng trình. -----------------55
nh ------------------------------56
Hình 3-5 Màn hình Ph c h i chân dung ----------------------57
Hình 3-6 Mô un mã hóa
nh ---------------------------------58
Hình 3-7 Mô un Ph c h i chân dung -------------------------59
Hình 3-8 Ti n trình con Ph c h i --------------------------60
Hình 3-9 Ti n trình con Tìm ki m --------------------------61
Hình 3-10 V i k=1, ch
kho ng cách g n nh t
ng trình tìm
c 2
n khuôn m t phác th o
Hình 3-11 k=2, ch
ng trình tìm
Hình 3-12 k=3 ch
ng trình tìm
c 2
c ch n 68
nh ----------------68
c 5
nh có cùng kho ng
cách g n nh t. Khuôn m t c n ph c h i
là khuôn m t
nh có cùng
ã
c tìm th y
gi a -----------------------------------68
Hình 3-13 k=4, k t qu
tìm ki m là 5
Hình 3-14 k = 5, k t qu
là 5
nh ------------------69
nh -------------------------69
-7-
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
DANH M C CÁC CÔNG TH C
Công th c 2-1 T a
các
Công th c 2-2 Kho ng cách t
m c a khuôn m t trung bình A ..28
khuôn m t Fi
n khuôn m t trung
bình A ................................................28
Công th c 2-3
o kho ng cách City-Block ................28
Công th c 2-4 Kho ng cách City-Block gi a Fi và A .........29
Công th c 2-5 Giá tr
thích nghi c a khuôn m t Fi .........29
-8-
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
CH
NG 1
PH C H I THÔNG TIN T
D
LI U QUAN SÁT B NG THU T
GI I DI TRUY N
1.1 PHÁT BI U BÀI TOÁN
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
nh m nghiên c u cách ph c h i thông tin ch d a vào trí nh ch quan c a
con ng
i. Các thông tin quan sát
c th
gian quan sát có khi r t ng n và ch u nh h
a ng
ng r i r c, không ch c ch n, th i
ng c a nhi u y u t ch quan
i quan sát nh là tâm sinh lý, kh n ng quan sát, kh n ng di n
t,
kh n ng miêu t , …
tài này có th áp d ng vào l nh v c
u tra t i ph m: Nhà ch c
trách mu n d ng l i chân dung t i ph m hay tìm nh chân dung trong t p
nh ng
it
ch ng th
ng nghi v n d a vào l i khai c a các nhân ch ng. Các nhân
ng không nh chính xác khuôn m t, nhi u khi các miêu t c a các
nhân ch ng khác nhau l i trái ng
c nhau, do ch quan. Làm sao
chi ti t r i r c ó ta có th t ng h p l i và
a ra m t chân dung phác th o
chính xác nh t có th ? ó chính là m c ích nghiên c u c a
Thu t gi i di truy n là m t trong nh ng ph
t nh ng v n
mà bài toán
t các
tài này.
ng pháp có th gi i quy t
t ra nh vào các phép toán r t m nh mà thu t
-9-
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
gi i s h u nh : ch n l c, lai ghép,
t bi n. Do ó trong lu n v n này chúng
tôi s d ng thu t gi i di truy n nh là m t công c
gi i quy t bài toán này.
1.2 THU T GI I DI TRUY N
1.2.1 Thu t gi i di truy n t ng quát
Thu t gi i di truy n (GA – Genetic Algorithms) do John Holland
xu t vào nh ng n m 1970 c a th k 20. Ý t
ng c a thu t gi i d a trên
thuy t ti n hoá c a Darwin: Nh ng cá th có tính thích nghi cao v i hoàn
nh s ng thì t n t i và ti p t c phát tri n, nh ng cá th có
d nd nb
tr
thích nghi kém
ào th i. Nh v y nh ng th h sau bao gi c ng t t h n th h
c. Xét trên khía c nh m t bài toán trong ó m i cá th
óng vai trò m t
i gi i thì càng v sau ta s càng có nh ng l i gi i t t h n nh ng l i gi i
tr
c ó, và quá trình ti n hóa trên m t qu n th các cá th thì ng v i m t
quá trình tìm ki m l i gi i trong không gian l i gi i.
Thu t gi i di truy n s d ng vay m
n nhi u thu t ng c a sinh h c
nh : nhi m s c th , cá th , qu n th , lai ghép,
t bi n, ch n l c... Cá th
là m t l i gi i c a bài toán, m i cá th trong thu t gi i di truy n
c qui
c
ch có m t nhi m s c th (khác v i các sinh v t trong t nhiên, ví d nh con
ng
i chúng ta có t i 46 nhi m s c th ) nên cá th
c th . Các nhi m s c th là m t chu i tuy n tính các
gen, m i gen bi u di n cho m t
nhi m s c th . M i
ng
c g i là nhi m
n v nh h n là các
c tr ng và có m t v trí nh t
nh trong
c tr ng có th có nhi u giá tr khác nhau. Qu n th là
t t p h p nhi u cá th có s l
ng xác
nh, trong thu t gi i di truy n
qu n th là m t không gian các l i gi i. Còn lai ghép,
là các phép toán th c hi n trên qu n th
- 10 -
t bi n, ch n l c…
t o ra m t qu n th m i.
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
gi l p môi tr
tr
ng và kh n ng thích nghi c a m i cá th v i môi
ng, m t hàm thích nghi (hàm m c tiêu, hàm l
ng giá)
Hàm này t o ra m t h s thích nghi cho m i cá th , thông th
c
nh ra.
ng thì h s
thích nghi càng cao có ngh a là cá th càng thích nghi t t v i môi tr
th càng thích nghi t t v i môi tr
ng. Cá
ng thì kh n ng s ng sót qua các th h
sau càng t ng. Nh vào hàm thích nghi mà thu t gi i di truy n tuy mang tính
ch t ng u nhiên nh ng là ng u nhiên có
trò “ nh h
nh h
ng, hàm thích nghi óng vai
ng” này [2].
Tuy ch m i
c hình thành cách ây ch a
gi i di truy n ã có
y 25 n m nh ng thu t
c c s toán h c v ng ch c v lý thuy t và
c áp
ng vào r t nhi u l nh v c khác nhau, trong ó t p trung vào 3 nhóm chính
sau [2]:
v Tìm ki m và t i u hóa.
ây c ng là th m nh nh t c a thu t gi i di
truy n. Các ng d ng trong l nh v c này có th k ra nh t i u hàm
, t i u trong hóa h c, t i u hóa c s d li u, “h c thích nghi” v i
c ic a
v Ho ch
i th trong các trò ch i…
nh qui trình, l trình. Ví d nh l p th i khóa bi u,
u khi n
ng lu i èn giao thông, ng d ng trong l u thông hàng hóa…
v Ch n l a nhóm hay thành ph n trong m t t ch c.
d
u
c áp d ng r ng rãi nh v y là vì thu t gi i di truy n có nh ng
m sau [1]:
ü Không chú tr ng
ph
ng pháp c
n gi i pháp chung nh t và chính xác nh
n mà xét
n toàn b các gi i pháp t
nh t.
- 11 -
ng
các
it t
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
ü Nh các toán t di truy n, l i gi i
c trao
gi m b t kh n ng k t thúc t i m t c c ti u
i qua l i, nh v y giúp
a ph
ng mà không tìm
th y c c ti u toàn c c.
ü Thích h p cho vi c tìm ki m trong không gian l n nh ng l i h n ch
th i gian và chi phí.
1.2.1.1 Các b
c trong thu t gi i di truy n
Khi gi i m t bài toán b ng thu t gi i di truy n ta c n tuân theo các
c chính sau [1]:
c 1: Ch n mô hình cho gi i pháp c a v n
chúng ta c n xác
nh
y
. Trong b
c này
các tham s :
1) Cách bi u di n nhi m s c th .
2) Xây d ng hàm thích nghi.
3) Xác
nh kích th
c qu n th , xác su t lai, xác su t
4) Ch n cách kh i t o qu n th ban
t bi n,...
u.
5) Xây d ng phép toán di truy n : tái sinh, lai ghép,
t bi n, ch n
c,...
c 2: Th c hi n thu t gi i di truy n:
( V i t là bi n
m, ch giá tr th i gian
P(t) : qu n th
§
th i gian t )
t
u
• t=0
• Trong khi mà (
- 12 -
u ki n d ng ch a tho ), l p:
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
o t=t+1
o Tái sinh P'(t)
P(t-1)
o Lai Q(t) t P(t-1)
t bi n R(t) t P(t-1)
o
o Ch n l c P(t) t
P(t-1) U Q(t) U R(t) U
P’(t)
•
§
tl p
t thúc
u ki n
thu t gi i d ng th
t ho c ã tìm
ng là khi th i gian cho phép ã ch m
c gi i pháp t i u hay t
ng
i khá nh t.
1.2.1.2 Cách bi u di n
Có nhi u ph
nhiên tr
ng pháp
bi u di n m t nhi m s c th - l i gi i, tuy
c khi bi u di n ta c n xem xét
n n i dung, yêu c u, nh ng tri
th c mà bài toán cung c p c ng nh nh ng yêu c u
t ra v t c
, l u tr …
ch n cách bi u di n thích h p nh t.
Thông th
ng có nhi u cách
bi u di n m t nhi m s c th :
§ Bi u di n b ng chu i nh phân 0,1: M i gen c a nhi m s c th
mã hóa nh m t s l
nh
c
m là
ng bit (0,1) nào ó. Cách bi u di n này có
chính xác không cao (các ph n t
các s nguyên), mu n t ng
di n do ó d n
c
c truy nh p là
chính xác ph i t ng s l
ng bit bi u
n làm ch m thu t toán, tính chính xác b m t khi t ng
kích c mi n vì chi u dài nh phân cho tr
c là c
§ Bi u di n b ng s th p phân: M i nhi m s c th
vect s d u ph y
nh [3].
c mã hóa là m t
ng v i cùng chi u dài c a vect l i gi i. Cách
- 13 -
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
bi u di n này kh c ph c
c các nh
c
m c a bi u di n nh phân,
chính xác tùy thu c vào kh n ng c a máy (s ch s th p phân sau
u ph y), có kh n ng bi u di n
c các mi n r ng l n… [3]
§ Bi u di n b ng ch cái
§ Bi u di n b ng k t h p ch và s
§
1.2.1.3 Kh i t o qu n th
kh i t o qu n th
n gi n ch c n kh i t o ng u nhiên t ng nhi m
c th m t. Tuy nhiên d a vào tri th c c a bài toán ho c v n d ng lý thuy t
xác su t mà ta có th ch n các cách kh i t o thích h p. N u l a ch n
ph
c
ng cách kh i t o t t, thu t gi i di truy n s h i t r t nhanh.
1.2.1.4 Các phép toán trên thu t gi i di truy n
o Tái sinh: là quá trình t o nên qu n th m i t qu n th c . D a
vào ch s thích nghi c a m i cá th mà cá th này
có
c xem xét
c chuy n sang qu n th m i hay không. Quá trình này có
th mô ph ng nh sau [1]:
§ Tính
thích nghi c a t ng cá th trong qu n th hi n
hành, l p b ng c ng d n cho các giá tr thích nghi (theo s
th t gán cho t ng cá th ). Gi s qu n th có N cá th .
i
thích nghi c a cá th th i là Fi, t ng d n th i là
Fti, t ng
§
thích nghi toàn qu n th là FN.
o m t s ng u nhiên F trong
§ Ch n cá th th k
a th h m i.
- 14 -
u tiên th a
nt 0
Ftk
n FN.
a vào qu n th
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
o Lai ghép (Crossover): c ng gi ng nh trong t nhiên lai ghép là
quá trình hình thành cá th m i trên c s cá th cha m b ng
cách ghép m t
n gen c a cá th cha m v i nhau. Xác su t
a lai ghép là pc. Có th mô ph ng phép lai nh sau [1]:
§ Ch n ng u nhiên hai (hay nhi u) cá th b t kì trong qu n
th . Gi s các nhi m s c th c a cha-m
§
u có m gen.
o m t s ng u nhiên trong kho ng t 1
là
m lai).
n m-1 (ta g i
m lai chia các chu i cha-m dài m thành
hai nhóm chu i con dài m1 và m2. Hai chu i nhi m s c th
con m i s là m11+m22 và m21+m12.
§
a hai cá th m i này vào qu n th
có th tham gia
quá trình ti n hóa ti p theo.
Ví d : Gi s có 2 nhi m s c th (cá th )
ng ph
c bi u di n
ng pháp nh phân, m i nhi m s c th dài 7 bit
(A): 1001110
trí lai
(B):0100011
c phát sinh ng u nhiên là 3, ta có 2 nhi m
c th sau khi lai:
(A ):1001|011
(B ):0100|110
Phép lai cho phép trao
o
t bi n (Mutation): là hi n t
i thông tin gi a các l i gi i.
ng cá th con mang m t s tính
tr ng không có trong mã di truy n c a cha m .
su t pm r t nh so v i pc. Phép
[1]:
- 15 -
t bi n có xác
t bi n có th mô ph ng nh sau
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
§ Ch n ng u nhiên m t cá th cha-m b t kì trong qu n th
§
o m t s ng u nhiên k trong kho ng t 1
n m, 1
k
m
§ Thay
i gen th k và tr cá th này v qu n th
có th
tham gia quá trình ti n hóa ti p theo.
Ví d : Gi s nhi m s c th :
110011
t bi n t i v trí ng u nhiên là 2, ta có nhi m
c th m i:
110001
Phép
t bi n cho phép t o ra m t l i gi i m i.
o Ch n l c : Là quá trình lo i b các cá th x u trong qu n th
ch gi l i trong qu n th các cá th t t
t
bi n t o ra các cá th m i. Các cá th
ó sinh s n,
t
c ch n c ng d a trên
giá tr thích nghi c a nó. Phép ch n l c có th
c mô ph ng
nh sau [1]:
§
p x p các cá th trong qu n th theo
thích nghi gi m
n.
§ Lo i b các cá th
nh t.
cu i dãy
ch gi l i N cá th t t
ây ta gi s qu n th có kích th
1.2.2 Thu t gi i di truy n t
Thu t gi i di truy n t
cN
nh.
ng tác
ng tác (IGA – Interative Genetic
Algorithms) là Thu t gi i di truy n mà giá tr thích nghi c a các cá th
- 16 -
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
c xác
nh d a trên s tu ng tác v i ng
ng tác
chu n l
c xem là m t công c h u ích
toán liên quan
y
, khi n cho
nh [4], ví d nh nh ng bài
n hình nh, âm thanh, gi l p th gi i th c,… ch
ng b ng c m giác, n t
d ng h th ng [6];
c
c
ng, s thích, c m xúc hay s nh y bén c a ng
i
gi i quy t nh ng bài toán này n u s d ng các
ng pháp t i u hóa truy n th ng s g p r t nhi u khó kh n và
xác th
chính
ng không cao, tuy nhiên do d a vào ch quan nên chúng l i r t thích
p v i Thu t gi i di truy n t
D
th
i v i nh ng bài toán mà tiêu
ng giá r t ph c t p và/ho c thông tin không
không th xây d ng m t hàm thích nghi xác
ph
i s d ng. Thu t gi i di truy n
i
ây là l
c
ng tác.
c a Thu t gi i di truy n t
ng tác thông
ng:
Hình 1-1 L
c
c a m t thu t gi i di truy n t
tác
- 17 -
ng
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
Các b
c c a m t thu t gi i di truy n t
ng tác :
c 1: Kh i t o qu n th (ng u nhiên), th hi n k t qu cho ng
is
ng.
c 2: Ng
i dùng ch n m t s k t qu mà “ m th y” úng.
c 3: Th c hi n ti n hoá v i s th h nh t
a trên nh ng k t qu ng
c ch n th
nh, v i hàm thích nghi
i dùng ch n, trong ó nh ng nhi m s c th
ng có giá tr thích nghi t t nh t.
c 4: Hi n th k t qu sau khi ti n hoá.
c 5: Quay l i
c2
u ng
i dùng ch a ch p nh n k t qu .
- 18 -
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
CH
D NG
NG 2
NH CHÂN DUNG T
QUAN SÁT B NG THU T GI I
DI TRUY N
2.1 GI I THI U
Trong ch
ng này, chúng tôi nghiên c u bài toán ”Ph c h i nh chân
dung t quan sát . Bài toán
c mô t tóm t t qua k ch b n nh sau:
t v án x y ra, t i ph m tr n thoát
c. Nhà ch c trách có nhu
u phác h a l i chân dung t i ph m t nh ng nhân ch ng có m t t i hi n
tr
ng. Quá trình
(1).
c ti n hành nh sau:
y l i khai c a nhân ch ng (mô t l i chân dung t i
ph m).
(2).
th ng t ng h p l i các l i khai
phác h a chân
dung.
Quá trình
c ti p t c cho t i khi t t c nhân ch ng ã th ng nh t
i nhau m t (ho c m t s ) chân dung t i ph m.
K ch b n trên s
c mô ph ng b ng ch
ng là Thu t gi i di truy n t
ng trình máy tính mà n n
ng tác nh trình bày trong ch
- 19 -
ng 1.
Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n
Trong ch
ng trình máy tính, vi c mô t chân dung t i ph m
c
th c hi n trên các khuôn m t phác th o, còn thao tác t ng h p l i khai
c
th c hi n nh vào thu t gi i di truy n. Ho t
Ch
ng c a ch
ng trình nh sau:
ng trình phát sinh các khuôn m t phác th o, ng
i s d ng (nhân
ch ng) tìm trong các khuôn m t này khuôn m t nào gi ng v i
(t i ph m) nh t, nh ng ng
c ch n, ch
thu t gi i di truy n th c hi n ti n hóa
th o h p v i mô t c a ng
Ch
it
ng trình s d ng
cho ra các khuôn m t phác
i s d ng nh t; sau khi ng
c khuôn m t phác th o, ch
a tìm
ng
i s d ng khác nhau có th ch n các khuôn
t khác nhau; t nh ng khuôn m t
chân dung th t nh c a
it
i s d ng ch n
ng trình tìm trong c s d li u nh
ng t
ng ng v i khuôn m t phác th o
c.
ng này s t p trung vào trình bày các thu c tính c a khuôn m t,
cách mã hóa các thu c tính và áp d ng các thu c tính này vào thu t gi i di
truy n s d ng cho bài toán. Chúng tôi c ng qui
phác th o là khuôn m t do ch
c khi nh c
n khuôn m t
ng trình t phát sinh và th hi n d a vào các
thu c tính khuôn m t, còn nh chân dung là nh thông th
ng,
c ch p và
a vào máy tính.
2.2 ÁP D NG THU T GI I DI TRUY N GI I
BÀI TOÁN PH C H I
NH CHÂN DUNG
MÔ T
2.2.1
2.2.1.1
c tr ng và mã hóa
c tr ng chân dung
c tr ng
t khuôn m t
c bi u di n trong máy tính b ng 20 thu c tính :
- 20 -
- Xem thêm -