Phục hồi thông tin từ dữ liệu quan sát: Luận văn về thuật giải di truyền

(cid:264)(cid:1186)I H(cid:1230)C KHOA H(cid:1230)C T(cid:1266) NHIÊN THÀNH PH(cid:1234) H(cid:1236) CHÍ MINH

KHOA CÔNG NGH(cid:1224) THÔNG TIN

†††

(cid:37)(cid:1242) MÔN CÔNG NGH(cid:1224) TRI TH(cid:1258)C

Lê Minh – 0012158

Ph(cid:1187)m H(cid:1265)u Lê Qu(cid:1235)c Ph(cid:1255)c – 0012169

PPPHHH(cid:1254)(cid:1254)(cid:1254)CCC HHH(cid:1236)(cid:1236)(cid:1236)III TTTHHHÔÔÔNNNGGG TTTIIINNN TTT(cid:1260)(cid:1260)(cid:1260) DDD(cid:1264)(cid:1264)(cid:1264) LLLIII(cid:1224)(cid:1224)(cid:1224)UUU

QQQUUUAAANNN SSSÁÁÁTTT BBB(cid:1202)(cid:1202)(cid:1202)NNNGGG TTTHHHUUU(cid:1198)(cid:1198)(cid:1198)TTT GGGIII(cid:1188)(cid:1188)(cid:1188)III DDDIII

TTTRRRUUUYYY(cid:1218)(cid:1218)(cid:1218)NNN

LU(cid:819)N V(cid:258)N C(cid:883) NHÂN CÔNG NGH(cid:845) THÔNG TIN

Giáo viên h(cid:1132)(cid:1245)ng d(cid:1197)n

TS. Nguy(cid:1223)n (cid:264)ình Thúc

Niên khóa 2000-2004

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:47)(cid:1246)I C(cid:1188)M (cid:1129)N

Chúng em xin chân thành cám (cid:583)n Khoa Công Ngh(cid:644) Thông Tin,

tr(cid:585)(cid:861)ng (cid:264)(cid:606)i H(cid:845)c Khoa H(cid:845)c T(cid:881) Nhiên Thành ph(cid:849) H(cid:851) Chí Minh (cid:255)ã t(cid:606)o

(cid:255)(cid:76)(cid:638)u ki(cid:644)n cho chúng em th(cid:881)c hi(cid:644)n (cid:255)(cid:638) tài lu(cid:618)n v(cid:259)n t(cid:849)t nghi(cid:644)p này.

Chúng con xin g(cid:877)i l(cid:861)i bi(cid:636)t (cid:583)n sâu s(cid:620)c (cid:255)(cid:636)n ông bà, cha m(cid:630)(cid:3) (cid:255)ã

ch(cid:259)m sóc, nuôi d(cid:606)y chúng con thành ng(cid:585)(cid:861)i.

Chúng em xin chân thành cám (cid:583)n th(cid:612)y Nguy(cid:642)n (cid:264)ình Thúc (cid:255)ã

(cid:87)(cid:618)n tình h(cid:585)(cid:859)ng d(cid:616)n, ch(cid:646) b(cid:608)o chúng em trong su(cid:849)t th(cid:861)i gian th(cid:881)c hi(cid:644)n

(cid:255)(cid:638) tài.

Chúng em xin chân thành cám (cid:583)n các th(cid:612)y cô trong Khoa Công

Ngh(cid:644) Thông Tin (cid:255)ã t(cid:618)n tình gi(cid:608)ng d(cid:606)y, trang b(cid:648) cho chúng em nh(cid:879)ng

ki(cid:636)n th(cid:873)c quí báu trong b(cid:849)n n(cid:259)m h(cid:845)c v(cid:875)a qua.

(cid:48)(cid:628)c dù chúng em (cid:255)ã c(cid:849) g(cid:620)ng hoàn thành lu(cid:618)n v(cid:259)n trong ph(cid:606)m

vi và kh(cid:608) n(cid:259)ng cho phép nh(cid:585)ng ch(cid:620)c ch(cid:620)n s(cid:634) không tránh kh(cid:847)i nh(cid:879)ng

thi(cid:636)u sót. Chúng em kính mong nh(cid:618)n (cid:255)(cid:585)(cid:867)c s(cid:881) c(cid:608)m thông và t(cid:618)n tình

ch(cid:646) b(cid:608)o c(cid:871)a th(cid:612)y cô và các b(cid:606)n.

Nhóm sinh viên th(cid:881)c hi(cid:644)n:

Lê Minh - Ph(cid:606)m H(cid:879)u Lê Qu(cid:849)c Ph(cid:869)c

- 2 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:47)(cid:1246)I GI(cid:1244)I THI(cid:1224)U

Máy tính ngày nay (cid:255)ã tr(cid:863) thành m(cid:857)t trong nh(cid:879)ng công c(cid:869) quan

tr(cid:845)ng. Có (cid:255)(cid:585)(cid:867)c (cid:255)(cid:76)(cid:638)u (cid:255)ó là do máy tính có hai (cid:255)(cid:76)(cid:640)m m(cid:606)nh ch(cid:871) y(cid:636)u là

(cid:87)(cid:849)c (cid:255)(cid:857) x(cid:877) lý và kh(cid:608) n(cid:259)ng l(cid:585)u tr(cid:879). S(cid:881) phát tri(cid:640)n c(cid:871)a Trí tu(cid:644) Nhân t(cid:606)o

làm cho máy tính càng thông minh h(cid:583)n. K(cid:636)t h(cid:867)p v(cid:859)i nh(cid:879)ng kh(cid:608) n(cid:259)ng

(cid:255)ang ngày càng hoàn thi(cid:644)n c(cid:871)a máy tính, các (cid:873)ng d(cid:869)ng c(cid:871)a Trí tu(cid:644)

Nhân t(cid:606)o có m(cid:628)t (cid:863) kh(cid:620)p m(cid:845)i n(cid:583)i và (cid:255)ang d(cid:612)n làm thay (cid:255)(cid:853)i cu(cid:857)c s(cid:849)ng

(cid:70)(cid:871)a chúng ta.

(cid:37)(cid:608)n thân Trí tu(cid:644) Nhân t(cid:606)o bao g(cid:851)m nhi(cid:638)u l(cid:347)nh v(cid:881)c nghiên c(cid:873)u

nh(cid:847) nh(cid:585): H(cid:644) chuyên gia, Nh(cid:618)n d(cid:606)ng, X(cid:877) lý (cid:608)nh, M(cid:606)ng N(cid:583)ron, Thu(cid:618)t

gi(cid:608)i di truy(cid:638)(cid:81)(cid:171), m(cid:855)i l(cid:347)nh v(cid:881)c khi (cid:255)(cid:585)(cid:867)c áp d(cid:869)ng vào trong th(cid:881)c t(cid:636)(cid:3)(cid:255)(cid:638)u

(cid:255)ã (cid:255)(cid:606)t (cid:255)(cid:585)(cid:867)c m(cid:857)t s(cid:849) thành t(cid:881)u nh(cid:610)t (cid:255)(cid:648)nh. Riêng Thu(cid:618)t gi(cid:608)i di truy(cid:638)n

(cid:255)ã và (cid:255)ang là m(cid:857)t công c(cid:869) m(cid:606)nh m(cid:634)(cid:3) (cid:255)(cid:585)(cid:867)c áp d(cid:869)ng r(cid:857)ng kh(cid:620)p, t(cid:875)

ph(cid:869)c v(cid:869) cho h(cid:845)c t(cid:618)p (s(cid:620)p x(cid:636)p th(cid:861)i khóa bi(cid:640)u, t(cid:849)i (cid:585)u hóa hàm s(cid:849)(cid:171)),

gi(cid:608)i trí (nâng cao tính (cid:179)trí tu(cid:644)(cid:180) cho games(cid:171)), cho (cid:255)(cid:636)n (cid:873)ng d(cid:869)ng trong

công nghi(cid:644)p (cid:255)em l(cid:606)i l(cid:867)i nhu(cid:618)n (nh(cid:585) trong khai thác d(cid:612)u khí, trong

thi(cid:636)t k(cid:636) máy móc, trong khai thác h(cid:612)m m(cid:847), giao thông công c(cid:857)ng,

trong s(cid:608)n xu(cid:610)(cid:87)(cid:171)) và ngay c(cid:608) trong l(cid:347)nh v(cid:881)c (cid:255)(cid:76)(cid:638)u tra t(cid:857)i ph(cid:606)m.

(cid:264)(cid:638) tài (cid:179)Ph(cid:869)c h(cid:851)i thông tin t(cid:875) d(cid:879) li(cid:644)u quan sát b(cid:622)ng thu(cid:618)t

gi(cid:608)i di truy(cid:638)(cid:81)(cid:180) nh(cid:622)m tìm hi(cid:640)u v(cid:638) vi(cid:644)c áp d(cid:869)ng Thu(cid:618)t gi(cid:608)i di truy(cid:638)n

trong Trí tu(cid:644) Nhân t(cid:606)o vào l(cid:347)nh v(cid:881)c (cid:255)(cid:76)(cid:638)u tra t(cid:857)i ph(cid:606)m. M(cid:869)c tiêu là

ph(cid:869)c h(cid:851)i l(cid:606)i thông tin v(cid:638) m(cid:857)t khuôn m(cid:628)t ng(cid:585)(cid:861)i t(cid:875) nh(cid:879)ng thông tin r(cid:861)i

(cid:85)(cid:606)c.

- 3 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:37)(cid:849) c(cid:869)c chính c(cid:871)a lu(cid:618)n v(cid:259)n nh(cid:585) sau:

§ Ch(cid:1133)(cid:1131)ng 1: Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i

di truy(cid:1221)n

Ch(cid:585)(cid:583)ng này gi(cid:859)i thi(cid:644)u v(cid:638)(cid:3) (cid:255)(cid:638) tài và trình bày tóm t(cid:620)t v(cid:638)

thu(cid:618)t gi(cid:608)i di truy(cid:638)n, thu(cid:618)t gi(cid:608)i chính (cid:255)(cid:585)(cid:867)c s(cid:877) d(cid:869)ng trong (cid:255)(cid:638) tài.

§ Ch(cid:1133)(cid:1131)ng 2: D(cid:1269)ng (cid:1191)nh chân dung t(cid:1263) quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di

truy(cid:1221)n

Ch(cid:585)(cid:583)ng 2 trình bày v(cid:638) các thu(cid:857)c tính (cid:255)(cid:585)(cid:867)c s(cid:877) d(cid:869)ng cho

bài toán, cách mã hóa các thu(cid:857)c tính này và áp d(cid:869)ng các thu(cid:857)c

tính này vào thu(cid:618)t gi(cid:608)i di truy(cid:638)n.

§ Ch(cid:1133)(cid:1131)ng 3: H(cid:1227) th(cid:1237)ng h(cid:1243) tr(cid:1255) tìm ki(cid:1219)m (cid:1191)nh chân dung d(cid:1269)a trên mô

(cid:87)(cid:1191)

Ch(cid:585)(cid:583)ng 3 trình bày v(cid:638) mô hình cài (cid:255)(cid:628)t c(cid:869) th(cid:640) cho bài toán

(cid:71)(cid:881)a vào lý thuy(cid:636)t (cid:255)(cid:585)(cid:867)c kh(cid:608)o sát trong các ch(cid:585)(cid:583)ng trên.

§ Ch(cid:1133)(cid:1131)ng 4: K(cid:1219)t lu(cid:1201)n

Nh(cid:879)ng k(cid:636)t qu(cid:608)(cid:3)(cid:255)ã (cid:255)(cid:606)t (cid:255)(cid:585)(cid:867)c, h(cid:585)(cid:859)ng phát tri(cid:640)n cho t(cid:585)(cid:583)ng

lai, (cid:255)ó là nh(cid:879)ng n(cid:857)i dung (cid:255)(cid:585)(cid:867)c trình bày trong ch(cid:585)(cid:583)ng này.

- 4 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:48)(cid:1254)C L(cid:1254)C

CH(cid:1132)(cid:1130)NG 1

PH(cid:1256)C H(cid:1238)I THÔNG TIN T(cid:1262) D(cid:1266) LI(cid:1226)U QUAN SÁT B(cid:1204)NG THU(cid:1200)T GI(cid:1190)I

DI TRUY(cid:1220)N-------------------------------------------------------------------------------------------------------------- 9

PHÁT BI(cid:1222)U BÀI TOÁN------------------------------------------------------------------------9

1.1

THU(cid:1200)T GI(cid:1190)I DI TRUY(cid:1220)N ------------------------------------------------------------------ 10

1.2

1.2.1 Thu(cid:821)t gi(cid:811)i di truy(cid:841)n t(cid:861)ng quát ----------------------------------------------------------------10

1.2.1.1 Các b(cid:1133)(cid:1247)c trong thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n---------------------------------------------------------------- 12

1.2.1.2 Cách bi(cid:1223)u di(cid:1225)n --------------------------------------------------------------------------------------- 13

1.2.1.3 Kh(cid:1251)i t(cid:1189)o qu(cid:1195)n th(cid:1223)------------------------------------------------------------------------------------ 14

1.2.1.4 Các phép toán trên thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n------------------------------------------------------------ 14

1.2.2 Thu(cid:821)t gi(cid:811)i di truy(cid:841)n t(cid:753)(cid:751)ng tác ----------------------------------------------------------------16

CH(cid:1132)(cid:1130)NG 2

(cid:39)(cid:1268)NG (cid:1190)NH CHÂN DUNG T(cid:1262) QUAN SÁT B(cid:1204)NG THU(cid:1200)T GI(cid:1190)I DI

TRUY(cid:1220)N---------------------------------------------------------------------------------------------- -------------------19

GI(cid:1246)I THI(cid:1226)U ------------------------------------------------------------------------------------ 19

2.1

ÁP (cid:39)(cid:1256)NG THU(cid:1200)T GI(cid:1190)I DI TRUY(cid:1220)N GI(cid:1190)I BÀI TOÁN PH(cid:1256)C (cid:43)(cid:1238)I (cid:1190)NH CHÂN

2.2

DUNG (cid:55)(cid:1262) MÔ (cid:55)(cid:1190) 20

2.2.1 (cid:264)(cid:831)c tr(cid:753)ng và mã hóa (cid:255)(cid:831)c tr(cid:753)ng chân dung -------------------------------------------------20

2.2.1.1 (cid:264)(cid:1211)c tr(cid:1133)ng --------------------------------------------------------------------------------------------- 20

2.2.1.2 Mi(cid:1221)n xác (cid:255)(cid:1231)nh c(cid:1259)a các (cid:255)(cid:1211)c tr(cid:1133)ng ------------------------------------------------------------------ 22

2.2.1.3 Mã hoá (cid:255)(cid:1211)c tr(cid:1133)ng ------------------------------------------------------------------------------------ 25

2.2.2 Hàm thích nghi ---------------------------------------------------------------------------------27

2.2.3 Thu(cid:821)t gi(cid:811)i di truy(cid:841)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 (cid:264)(cid:1245)t bi(cid:1219)n ---------------------------------------------------------------------------------------- 33

2.2.3.1.4 Ch(cid:1233)n l(cid:1233)c --------------------------------------------------------------------------------------- 35

2.2.3.2 Thu(cid:1201)t gi(cid:1191)i --------------------------------------------------------------------------------------------- 36

2.2.3.2.1 Tham s(cid:1237) ---------------------------------------------------------------------------------------- 36

2.2.3.2.2 Thu(cid:1201)t gi(cid:1191)i -------------------------------------------------------------------------------------- 36

2.2.4 Tìm ki(cid:839)m trong c(cid:751) s(cid:871) d(cid:887) li(cid:847)u (cid:811)nh chân dung -----------------------------------------------38

2.2.4.1 Xây d(cid:1269)ng CSDL (cid:1191)nh chân dung ------------------------------------------------------------------- 39

2.2.4.2 T(cid:1241) ch(cid:1261)c c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u (cid:1191)nh chân dung ------------------------------------------------------------- 46

2.2.4.3 Tìm ki(cid:1219)m --------------------------------------------------------------------------------------------- 48

CH(cid:1132)(cid:1130)NG 3

(cid:43)(cid:1226) TH(cid:1236)NG H(cid:1242) TR(cid:1254) TÌM KI(cid:1218)M (cid:1190)NH CHÂN DUNG D(cid:1268)A TRÊN MÔ

(cid:55)(cid:1190)------------------------------ -------------------------------------------------------------------------------------------52

- 5 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

3.1

(cid:54)(cid:1130) (cid:264)(cid:1238) (cid:43)(cid:1226) TH(cid:1236)NG --------------------------------------------------------------------------- 52

3.2

CÁC MÔ(cid:264)UN (cid:43)(cid:1226) TH(cid:1236)NG ------------------------------------------------------------------ 54

3.2.1 S(cid:751)(cid:3)(cid:255)(cid:859) màn hình---------------------------------------------------------------------------------54

3.2.2 Mô(cid:255)un Mã hóa (cid:811)nh ----------------------------------------------------------------------------58

3.2.3 Mô(cid:255)un Ph(cid:877)c h(cid:859)i chân dung-------------------------------------------------------------------59

CH(cid:1132)(cid:1130)NG 4

(cid:46)(cid:1218)T LU(cid:1200)N ----------------------------------------------------------------------------70

4.1

NH(cid:1200)N XÉT ------------------------------------------------------------------------------------- 70

4.1.1 Nh(cid:887)ng k(cid:839)t qu(cid:811)(cid:3)(cid:255)(cid:809)t (cid:255)(cid:753)(cid:875)c-----------------------------------------------------------------------70

4.1.2 Khó kh(cid:259)n và h(cid:809)n ch(cid:839) --------------------------------------------------------------------------71

4.2

(cid:43)(cid:1132)(cid:1246)NG PHÁT TRI(cid:1222)N ----------------------------------------------------------------------- 72

- 6 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

DANH M(cid:1254)C CÁC HÌNH V(cid:1214)

Hình 1-1 L(cid:1132)(cid:1253)c (cid:255)(cid:1237) c(cid:1257)a m(cid:1243)t thu(cid:1199)t gi(cid:1189)i di truy(cid:1219)n t(cid:1132)(cid:1130)ng tác ---17

Hình 2-1 S(cid:1130)(cid:3)(cid:255)(cid:1237) t(cid:1239)ng quát c(cid:1257)a bài toán. Trong (cid:255)ó, mã hóa (cid:1189)nh

chân dung là m(cid:1243)t trong hai ti(cid:1217)n trình quan tr(cid:1231)ng. -----39

Hình 3-1 Hai mô(cid:255)un chính c(cid:1257)a h(cid:1225) th(cid:1235)ng ---------------------52

Hình 3-2 S(cid:1130)(cid:3)(cid:255)(cid:1237) màn hình -----------------------------------54

Hình 3-3 Màn hình chính c(cid:1257)a ch(cid:1132)(cid:1130)ng trình. -----------------55

Hình 3-4 Màn hình mã hóa (cid:1189)nh ------------------------------56

Hình 3-5 Màn hình Ph(cid:1255)c h(cid:1237)i chân dung ----------------------57

Hình 3-6 Mô(cid:255)un mã hóa (cid:1189)nh ---------------------------------58

Hình 3-7 Mô(cid:255)un Ph(cid:1255)c h(cid:1237)i chân dung -------------------------59

Hình 3-8 Ti(cid:1217)n trình con Ph(cid:1255)c h(cid:1237)i --------------------------60

Hình 3-9 Ti(cid:1217)n trình con Tìm ki(cid:1217)m --------------------------61

Hình 3-10 V(cid:1245)i k=1, ch(cid:1132)(cid:1130)ng trình tìm (cid:255)(cid:1132)(cid:1253)c 2 (cid:1189)nh có cùng

kho(cid:1189)ng cách g(cid:1193)n nh(cid:1191)t (cid:255)(cid:1217)n khuôn m(cid:1209)t phác th(cid:1189)o (cid:255)(cid:1132)(cid:1253)c ch(cid:1231)n 68

Hình 3-11 k=2, ch(cid:1132)(cid:1130)ng trình tìm (cid:255)(cid:1132)(cid:1253)c 2 (cid:1189)nh ----------------68

Hình 3-12 k=3 ch(cid:1132)(cid:1130)ng trình tìm (cid:255)(cid:1132)(cid:1253)c 5 (cid:1189)nh có cùng kho(cid:1189)ng

cách g(cid:1193)n nh(cid:1191)t. Khuôn m(cid:1209)t c(cid:1193)n ph(cid:1255)c h(cid:1237)i (cid:255)ã (cid:255)(cid:1132)(cid:1253)c tìm th(cid:1191)y

là khuôn m(cid:1209)t (cid:1249) gi(cid:1265)a -----------------------------------68

Hình 3-13 k=4, k(cid:1217)t qu(cid:1189) tìm ki(cid:1217)m là 5 (cid:1189)nh ------------------69

Hình 3-14 k = 5, k(cid:1217)t qu(cid:1189) là 5 (cid:1189)nh -------------------------69

- 7 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

DANH M(cid:1254)C CÁC CÔNG TH(cid:1258)C

Công th(cid:1259)c 2-1 T(cid:1231)a (cid:255)(cid:1243) các (cid:255)(cid:76)(cid:1221)m c(cid:1257)a khuôn m(cid:1209)t trung bình A ..28

Công th(cid:1259)c 2-2 Kho(cid:1189)ng cách t(cid:1261) khuôn m(cid:1209)t Fi(cid:3)(cid:255)(cid:1217)n khuôn m(cid:1209)t trung

bình A ................................................28

Công th(cid:1259)c 2-3 (cid:264)(cid:1243)(cid:3)(cid:255)o kho(cid:1189)ng cách City-Block ................28

Công th(cid:1259)c 2-4 Kho(cid:1189)ng cách City-Block gi(cid:1265)a Fi và A .........29

Công th(cid:1259)c 2-5 Giá tr(cid:1229) thích nghi c(cid:1257)a khuôn m(cid:1209)t Fi .........29

- 8 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

CCCHHH(cid:1131)(cid:1131)(cid:1131)(cid:1129)(cid:1129)(cid:1129)NNNGGG 111

PPPHHH(cid:1254)(cid:1254)(cid:1254)CCC HHH(cid:1236)(cid:1236)(cid:1236)III TTTHHHÔÔÔNNNGGG TTTIIINNN TTT(cid:1260)(cid:1260)(cid:1260) DDD(cid:1264)(cid:1264)(cid:1264)

LLLIII(cid:1224)(cid:1224)(cid:1224)UUU QQQUUUAAANNN SSSÁÁÁTTT BBB(cid:1202)(cid:1202)(cid:1202)NNNGGG TTTHHHUUU(cid:1198)(cid:1198)(cid:1198)TTT

GGGIII(cid:1188)(cid:1188)(cid:1188)III DDDIII TTTRRRUUUYYY(cid:1218)(cid:1218)(cid:1218)NNN

1.1 PHÁT BI(cid:858)U BÀI TOÁN

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

nh(cid:1205)m nghiên c(cid:1261)u cách ph(cid:1257)c h(cid:1239)i thông tin ch(cid:1229) d(cid:1269)a vào trí nh(cid:1247) ch(cid:1259) quan c(cid:1259)a

con ng(cid:1133)(cid:1249)i. Các thông tin quan sát (cid:255)(cid:1133)(cid:1255)c th(cid:1133)(cid:1249)ng r(cid:1249)i r(cid:1189)c, không ch(cid:1203)c ch(cid:1203)n, th(cid:1249)i

gian quan sát có khi r(cid:1193)t ng(cid:1203)n và ch(cid:1231)u (cid:1191)nh h(cid:1133)(cid:1251)ng c(cid:1259)a nhi(cid:1221)u y(cid:1219)u t(cid:1237) ch(cid:1259) quan

(cid:70)(cid:1259)a ng(cid:1133)(cid:1249)i quan sát nh(cid:1133) là tâm sinh lý, kh(cid:1191) n(cid:259)ng quan sát, kh(cid:1191) n(cid:259)ng di(cid:1225)n (cid:255)(cid:1189)t,

kh(cid:1191) n(cid:259)ng miêu t(cid:1191), …

(cid:264)(cid:1221) tài này có th(cid:1223) áp d(cid:1257)ng vào l(cid:429)nh v(cid:1269)c (cid:255)(cid:76)(cid:1221)u tra t(cid:1245)i ph(cid:1189)m: Nhà ch(cid:1261)c

trách mu(cid:1237)n d(cid:1269)ng l(cid:1189)i chân dung t(cid:1245)i ph(cid:1189)m hay tìm (cid:1191)nh chân dung trong t(cid:1201)p

nh(cid:1267)ng (cid:255)(cid:1237)i t(cid:1133)(cid:1255)ng nghi v(cid:1193)n d(cid:1269)a vào l(cid:1249)i khai c(cid:1259)a các nhân ch(cid:1261)ng. Các nhân

ch(cid:1261)ng th(cid:1133)(cid:1249)ng không nh(cid:1247) chính xác khuôn m(cid:1211)t, nhi(cid:1221)u khi các miêu t(cid:1191) c(cid:1259)a các

nhân ch(cid:1261)ng khác nhau l(cid:1189)i trái ng(cid:1133)(cid:1255)c nhau, do ch(cid:1259) quan. Làm sao (cid:255)(cid:1223) t(cid:1263) các

chi ti(cid:1219)t r(cid:1249)i r(cid:1189)c (cid:255)ó ta có th(cid:1223) t(cid:1241)ng h(cid:1255)p l(cid:1189)i và (cid:255)(cid:1133)a ra m(cid:1245)t chân dung phác th(cid:1191)o

chính xác nh(cid:1193)t có th(cid:1223)? (cid:264)ó chính là m(cid:1257)c (cid:255)ích nghiên c(cid:1261)u c(cid:1259)a (cid:255)(cid:1221) tài này.

Thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n là m(cid:1245)t trong nh(cid:1267)ng ph(cid:1133)(cid:1131)ng pháp có th(cid:1223) gi(cid:1191)i quy(cid:1219)t

(cid:87)(cid:1237)t nh(cid:1267)ng v(cid:1193)n (cid:255)(cid:1221) mà bài toán (cid:255)(cid:1211)t ra nh(cid:1249) vào các phép toán r(cid:1193)t m(cid:1189)nh mà thu(cid:1201)t

- 9 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

gi(cid:1191)i s(cid:1251) h(cid:1267)u nh(cid:1133): ch(cid:853)n l(cid:853)c, lai ghép, (cid:255)(cid:865)t bi(cid:839)n. Do (cid:255)ó trong lu(cid:1201)n v(cid:259)n này chúng

tôi s(cid:1265) d(cid:1257)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n nh(cid:1133) là m(cid:1245)t công c(cid:1257)(cid:3)(cid:255)(cid:1223) gi(cid:1191)i quy(cid:1219)t bài toán này.

1.2 THU(cid:836)T GI(cid:826)I DI TRUY(cid:856)N

1.2.1 Thu(cid:837)t gi(cid:827)i di truy(cid:857)n t(cid:877)ng quát

Thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n (GA – Genetic Algorithms) do John Holland (cid:255)(cid:1221)

xu(cid:1193)t vào nh(cid:1267)ng n(cid:259)m 1970 c(cid:1259)a th(cid:1219) k(cid:1273) 20. Ý t(cid:1133)(cid:1251)ng c(cid:1259)a thu(cid:1201)t gi(cid:1191)i d(cid:1269)a trên

thuy(cid:1219)t ti(cid:1219)n hoá c(cid:1259)a Darwin: Nh(cid:1267)ng cá th(cid:1223) có tính thích nghi cao v(cid:1247)i hoàn

(cid:70)(cid:1191)nh s(cid:1237)ng thì t(cid:1239)n t(cid:1189)i và ti(cid:1219)p t(cid:1257)c phát tri(cid:1223)n, nh(cid:1267)ng cá th(cid:1223) có (cid:255)(cid:1245) thích nghi kém

(cid:86)(cid:1217) d(cid:1195)n d(cid:1195)n b(cid:1231)(cid:3)(cid:255)ào th(cid:1191)i. Nh(cid:1133) v(cid:1201)y nh(cid:1267)ng th(cid:1219) h(cid:1227) sau bao gi(cid:1249) c(cid:458)ng t(cid:1237)t h(cid:1131)n th(cid:1219) h(cid:1227)

tr(cid:1133)(cid:1247)c. Xét trên khía c(cid:1189)nh m(cid:1245)t bài toán trong (cid:255)ó m(cid:1243)i cá th(cid:1223)(cid:3)(cid:255)óng vai trò m(cid:1245)t

(cid:79)(cid:1249)i gi(cid:1191)i thì càng v(cid:1221) sau ta s(cid:1217) càng có nh(cid:1267)ng l(cid:1249)i gi(cid:1191)i t(cid:1237)t h(cid:1131)n nh(cid:1267)ng l(cid:1249)i gi(cid:1191)i

tr(cid:1133)(cid:1247)c (cid:255)ó, và quá trình ti(cid:1219)n hóa trên m(cid:1245)t qu(cid:1195)n th(cid:1223) các cá th(cid:1223) thì (cid:1261)ng v(cid:1247)i m(cid:1245)t

quá trình tìm ki(cid:1219)m l(cid:1249)i gi(cid:1191)i trong không gian l(cid:1249)i gi(cid:1191)i.

Thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n s(cid:1265) d(cid:1257)ng vay m(cid:1133)(cid:1255)n nhi(cid:1221)u thu(cid:1201)t ng(cid:1267) c(cid:1259)a sinh h(cid:1233)c

nh(cid:1133): nhi(cid:1225)m s(cid:1203)c th(cid:1223), cá th(cid:1223), qu(cid:1195)n th(cid:1223), lai ghép, (cid:255)(cid:1245)t bi(cid:1219)n, ch(cid:1233)n l(cid:1233)c... Cá th(cid:1223)

là m(cid:1245)t l(cid:1249)i gi(cid:1191)i c(cid:1259)a bài toán, m(cid:1243)i cá th(cid:1223) trong thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n (cid:255)(cid:1133)(cid:1255)c qui (cid:1133)(cid:1247)c

ch(cid:1229) có m(cid:1245)t nhi(cid:1225)m s(cid:1203)c th(cid:1223) (khác v(cid:1247)i các sinh v(cid:1201)t trong t(cid:1269) nhiên, ví d(cid:1257) nh(cid:1133) con

ng(cid:1133)(cid:1249)i chúng ta có t(cid:1247)i 46 nhi(cid:1225)m s(cid:1203)c th(cid:1223)) nên cá th(cid:1223) (cid:70)(cid:458)ng (cid:255)(cid:1133)(cid:1255)c g(cid:1233)i là nhi(cid:1225)m

(cid:86)(cid:1203)c th(cid:1223). Các nhi(cid:1225)m s(cid:1203)c th(cid:1223) là m(cid:1245)t chu(cid:1243)i tuy(cid:1219)n tính các (cid:255)(cid:1131)n v(cid:1231) nh(cid:1235) h(cid:1131)n là các

gen, m(cid:1243)i gen bi(cid:1223)u di(cid:1225)n cho m(cid:1245)t (cid:255)(cid:1211)c tr(cid:1133)ng và có m(cid:1245)t v(cid:1231) trí nh(cid:1193)t (cid:255)(cid:1231)nh trong

nhi(cid:1225)m s(cid:1203)c th(cid:1223). M(cid:1243)i (cid:255)(cid:1211)c tr(cid:1133)ng có th(cid:1223) có nhi(cid:1221)u giá tr(cid:1231) khác nhau. Qu(cid:1195)n th(cid:1223) là

(cid:80)(cid:1245)t t(cid:1201)p h(cid:1255)p nhi(cid:1221)u cá th(cid:1223) có s(cid:1237) l(cid:1133)(cid:1255)ng xác (cid:255)(cid:1231)nh, trong thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

qu(cid:1195)n th(cid:1223) là m(cid:1245)t không gian các l(cid:1249)i gi(cid:1191)i. Còn lai ghép, (cid:255)(cid:1245)t bi(cid:1219)n, ch(cid:1233)n l(cid:1233)c…

là các phép toán th(cid:1269)c hi(cid:1227)n trên qu(cid:1195)n th(cid:1223)(cid:3)(cid:255)(cid:1223) t(cid:1189)o ra m(cid:1245)t qu(cid:1195)n th(cid:1223) m(cid:1247)i.

- 10 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:264)(cid:1223) gi(cid:1191) l(cid:1201)p môi tr(cid:1133)(cid:1249)ng và kh(cid:1191) n(cid:259)ng thích nghi c(cid:1259)a m(cid:1243)i cá th(cid:1223) v(cid:1247)i môi

tr(cid:1133)(cid:1249)ng, m(cid:1245)t hàm thích nghi (hàm m(cid:1257)c tiêu, hàm l(cid:1133)(cid:1255)ng giá) (cid:255)(cid:1133)(cid:1255)c (cid:255)(cid:1231)nh ra.

Hàm này t(cid:1189)o ra m(cid:1245)t h(cid:1227) s(cid:1237) thích nghi cho m(cid:1243)i cá th(cid:1223), thông th(cid:1133)(cid:1249)ng thì h(cid:1227) s(cid:1237)

thích nghi càng cao có ngh(cid:429)a là cá th(cid:1223) càng thích nghi t(cid:1237)t v(cid:1247)i môi tr(cid:1133)(cid:1249)ng. Cá

th(cid:1223) càng thích nghi t(cid:1237)t v(cid:1247)i môi tr(cid:1133)(cid:1249)ng thì kh(cid:1191) n(cid:259)ng s(cid:1237)ng sót qua các th(cid:1219) h(cid:1227)

sau càng t(cid:259)ng. Nh(cid:1249) vào hàm thích nghi mà thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n tuy mang tính

ch(cid:1193)t ng(cid:1199)u nhiên nh(cid:1133)ng là ng(cid:1199)u nhiên có (cid:255)(cid:1231)nh h(cid:1133)(cid:1247)ng, hàm thích nghi (cid:255)óng vai

trò “(cid:255)(cid:1231)nh h(cid:1133)(cid:1247)ng” này [2].

Tuy ch(cid:1229) m(cid:1247)i (cid:255)(cid:1133)(cid:1255)c hình thành cách (cid:255)ây ch(cid:1133)a (cid:255)(cid:1195)y 25 n(cid:259)m nh(cid:1133)ng thu(cid:1201)t

gi(cid:1191)i di truy(cid:1221)n (cid:255)ã có (cid:255)(cid:1133)(cid:1255)c c(cid:1131) s(cid:1251) toán h(cid:1233)c v(cid:1267)ng ch(cid:1203)c v(cid:1221) lý thuy(cid:1219)t và (cid:255)(cid:1133)(cid:1255)c áp

(cid:71)(cid:1257)ng vào r(cid:1193)t nhi(cid:1221)u l(cid:429)nh v(cid:1269)c khác nhau, trong (cid:255)ó t(cid:1201)p trung vào 3 nhóm chính

sau [2]:

v Tìm ki(cid:1219)m và t(cid:1237)i (cid:1133)u hóa. (cid:264)ây c(cid:458)ng là th(cid:1219) m(cid:1189)nh nh(cid:1193)t c(cid:1259)a thu(cid:1201)t gi(cid:1191)i di

truy(cid:1221)n. Các (cid:1261)ng d(cid:1257)ng trong l(cid:429)nh v(cid:1269)c này có th(cid:1223) k(cid:1223) ra nh(cid:1133) t(cid:1237)i (cid:1133)u hàm

(cid:86)(cid:1237), t(cid:1237)i (cid:1133)u trong hóa h(cid:1233)c, t(cid:1237)i (cid:1133)u hóa c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u, “h(cid:1233)c thích nghi” v(cid:1247)i

(cid:81)(cid:1133)(cid:1247)c (cid:255)i c(cid:1259)a (cid:255)(cid:1237)i th(cid:1259) trong các trò ch(cid:1131)i…

v Ho(cid:1189)ch (cid:255)(cid:1231)nh qui trình, l(cid:1245) trình. Ví d(cid:1257) nh(cid:1133) l(cid:1201)p th(cid:1249)i khóa bi(cid:1223)u, (cid:255)(cid:76)(cid:1221)u khi(cid:1223)n

(cid:80)(cid:1189)ng lu(cid:1247)i (cid:255)èn giao thông, (cid:1261)ng d(cid:1257)ng trong l(cid:1133)u thông hàng hóa…

v Ch(cid:1233)n l(cid:1269)a nhóm hay thành ph(cid:1195)n trong m(cid:1245)t t(cid:1241) ch(cid:1261)c.

(cid:54)(cid:1251) d(cid:429)(cid:3)(cid:255)(cid:1133)(cid:1255)c áp d(cid:1257)ng r(cid:1245)ng rãi nh(cid:1133) v(cid:1201)y là vì thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n có nh(cid:1267)ng

(cid:1133)u (cid:255)(cid:76)(cid:1223)m sau [1]:

(cid:252) Không chú tr(cid:1233)ng (cid:255)(cid:1219)n gi(cid:1191)i pháp chung nh(cid:1193)t và chính xác nh(cid:1133) các

ph(cid:1133)(cid:1131)ng pháp c(cid:1241)(cid:3) (cid:255)(cid:76)(cid:1223)n mà xét (cid:255)(cid:1219)n toàn b(cid:1245) các gi(cid:1191)i pháp t(cid:1133)(cid:1131)ng (cid:255)(cid:1237)i t(cid:1237)t

nh(cid:1193)t.

- 11 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:252) Nh(cid:1249) các toán t(cid:1265) di truy(cid:1221)n, l(cid:1249)i gi(cid:1191)i (cid:255)(cid:1133)(cid:1255)c trao (cid:255)(cid:1241)i qua l(cid:1189)i, nh(cid:1133) v(cid:1201)y giúp

gi(cid:1191)m b(cid:1247)t kh(cid:1191) n(cid:259)ng k(cid:1219)t thúc t(cid:1189)i m(cid:1245)t c(cid:1269)c ti(cid:1223)u (cid:255)(cid:1231)a ph(cid:1133)(cid:1131)ng mà không tìm

th(cid:1193)y c(cid:1269)c ti(cid:1223)u toàn c(cid:1257)c.

(cid:252) Thích h(cid:1255)p cho vi(cid:1227)c tìm ki(cid:1219)m trong không gian l(cid:1247)n nh(cid:1133)ng l(cid:1189)i h(cid:1189)n ch(cid:1219)

(cid:89)(cid:1221) th(cid:1249)i gian và chi phí.

1.2.1.1 Các b(cid:1133)(cid:1247)c trong thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

Khi gi(cid:1191)i m(cid:1245)t bài toán b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n ta c(cid:1195)n tuân theo các

(cid:69)(cid:1133)(cid:1247)c chính sau [1]:

(cid:37)(cid:585)(cid:859)c 1: Ch(cid:1233)n mô hình cho gi(cid:1191)i pháp c(cid:1259)a v(cid:1193)n (cid:255)(cid:1221). Trong b(cid:1133)(cid:1247)c này

chúng ta c(cid:1195)n xác (cid:255)(cid:1231)nh (cid:255)(cid:1195)y (cid:255)(cid:1259) các tham s(cid:1237) :

1) Cách bi(cid:1223)u di(cid:1225)n nhi(cid:1225)m s(cid:1203)c th(cid:1223).

2) Xây d(cid:1269)ng hàm thích nghi.

3) Xác (cid:255)(cid:1231)nh kích th(cid:1133)(cid:1247)c qu(cid:1195)n th(cid:1223), xác su(cid:1193)t lai, xác su(cid:1193)t (cid:255)(cid:1245)t bi(cid:1219)n,...

4) Ch(cid:1233)n cách kh(cid:1251)i t(cid:1189)o qu(cid:1195)n th(cid:1223) ban (cid:255)(cid:1195)u.

5) Xây d(cid:1269)ng phép toán di truy(cid:1221)n : tái sinh, lai ghép, (cid:255)(cid:1245)t bi(cid:1219)n, ch(cid:1233)n

(cid:79)(cid:1233)c,...

(cid:37)(cid:585)(cid:859)c 2: Th(cid:1269)c hi(cid:1227)n thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n:

( V(cid:1247)i t là bi(cid:1219)n (cid:255)(cid:1219)m, ch(cid:1229) giá tr(cid:1231) th(cid:1249)i gian

P(t) : qu(cid:1195)n th(cid:1223)(cid:3)(cid:1251) th(cid:1249)i gian t )

§ (cid:37)(cid:1203)t (cid:255)(cid:1195)u

• t = 0

• Trong khi mà ((cid:255)(cid:76)(cid:1221)u ki(cid:1227)n d(cid:1263)ng ch(cid:1133)a tho(cid:1191)), l(cid:1211)p:

- 12 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

o t = t + 1

o Tái sinh P'(t) (cid:87)(cid:1263) P(t-1)

o Lai Q(t) t(cid:1263) P(t-1)

o (cid:264)(cid:865)t bi(cid:839)n R(t) t(cid:1263) P(t-1)

o Ch(cid:853)n l(cid:853)c P(t) t(cid:1263) P(t-1) U Q(t) U R(t) U

P’(t)

• (cid:43)(cid:1219)t l(cid:1211)p

§ (cid:46)(cid:1219)t thúc

(cid:264)(cid:76)(cid:1221)u ki(cid:1227)n (cid:255)(cid:1223) thu(cid:1201)t gi(cid:1191)i d(cid:1263)ng th(cid:1133)(cid:1249)ng là khi th(cid:1249)i gian cho phép (cid:255)ã ch(cid:1193)m

(cid:71)(cid:1261)t ho(cid:1211)c (cid:255)ã tìm (cid:255)(cid:1133)(cid:1255)c gi(cid:1191)i pháp t(cid:1237)i (cid:1133)u hay t(cid:1133)(cid:1131)ng (cid:255)(cid:1237)i khá nh(cid:1193)t.

1.2.1.2 Cách bi(cid:1223)u di(cid:1225)n

Có nhi(cid:1221)u ph(cid:1133)(cid:1131)ng pháp (cid:255)(cid:1223) bi(cid:1223)u di(cid:1225)n m(cid:1245)t nhi(cid:1225)m s(cid:1203)c th(cid:1223) - l(cid:1249)i gi(cid:1191)i, tuy

nhiên tr(cid:1133)(cid:1247)c khi bi(cid:1223)u di(cid:1225)n ta c(cid:1195)n xem xét (cid:255)(cid:1219)n n(cid:1245)i dung, yêu c(cid:1195)u, nh(cid:1267)ng tri

th(cid:1261)c mà bài toán cung c(cid:1193)p c(cid:458)ng nh(cid:1133) nh(cid:1267)ng yêu c(cid:1195)u (cid:255)(cid:1211)t ra v(cid:1221) t(cid:1237)c (cid:255)(cid:1245), l(cid:1133)u tr(cid:1267)…

(cid:255)(cid:1223) ch(cid:1233)n cách bi(cid:1223)u di(cid:1225)n thích h(cid:1255)p nh(cid:1193)t.

Thông th(cid:1133)(cid:1249)ng có nhi(cid:1221)u cách (cid:255)(cid:1223) bi(cid:1223)u di(cid:1225)n m(cid:1245)t nhi(cid:1225)m s(cid:1203)c th(cid:1223):

§ Bi(cid:843)u di(cid:845)n b(cid:825)ng chu(cid:863)i nh(cid:851) phân 0,1: M(cid:1243)i gen c(cid:1259)a nhi(cid:1225)m s(cid:1203)c th(cid:1223)(cid:3) (cid:255)(cid:1133)(cid:1255)c

mã hóa nh(cid:1249) m(cid:1245)t s(cid:1237) l(cid:1133)(cid:1255)ng bit (0,1) nào (cid:255)ó. Cách bi(cid:1223)u di(cid:1225)n này có

nh(cid:1133)(cid:1255)c (cid:255)(cid:76)(cid:1223)m là (cid:255)(cid:1245) chính xác không cao (các ph(cid:1195)n t(cid:1265)(cid:3)(cid:255)(cid:1133)(cid:1255)c truy nh(cid:1201)p là

các s(cid:1237) nguyên), mu(cid:1237)n t(cid:259)ng (cid:255)(cid:1245) chính xác ph(cid:1191)i t(cid:259)ng s(cid:1237) l(cid:1133)(cid:1255)ng bit bi(cid:1223)u

di(cid:1225)n do (cid:255)ó d(cid:1199)n (cid:255)(cid:1219)n làm ch(cid:1201)m thu(cid:1201)t toán, tính chính xác b(cid:1231) m(cid:1193)t khi t(cid:259)ng

kích c(cid:1253) mi(cid:1221)n vì chi(cid:1221)u dài nh(cid:1231) phân cho tr(cid:1133)(cid:1247)c là c(cid:1237)(cid:3)(cid:255)(cid:1231)nh [3].

§ Bi(cid:843)u di(cid:845)n b(cid:825)ng s(cid:857) th(cid:821)p phân: M(cid:1243)i nhi(cid:1225)m s(cid:1203)c th(cid:1223)(cid:3)(cid:255)(cid:1133)(cid:1255)c mã hóa là m(cid:1245)t

vect(cid:1131) s(cid:1237) d(cid:1193)u ph(cid:1197)y (cid:255)(cid:1245)ng v(cid:1247)i cùng chi(cid:1221)u dài c(cid:1259)a vect(cid:1131) l(cid:1249)i gi(cid:1191)i. Cách

- 13 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

bi(cid:1223)u di(cid:1225)n này kh(cid:1203)c ph(cid:1257)c (cid:255)(cid:1133)(cid:1255)c các nh(cid:1133)(cid:1255)c (cid:255)(cid:76)(cid:1223)m c(cid:1259)a bi(cid:1223)u di(cid:1225)n nh(cid:1231) phân,

(cid:255)(cid:1245) chính xác tùy thu(cid:1245)c vào kh(cid:1191) n(cid:259)ng c(cid:1259)a máy (s(cid:1237) ch(cid:1267) s(cid:1237) th(cid:1201)p phân sau

(cid:71)(cid:1193)u ph(cid:1197)y), có kh(cid:1191) n(cid:259)ng bi(cid:1223)u di(cid:1225)n (cid:255)(cid:1133)(cid:1255)c các mi(cid:1221)n r(cid:1245)ng l(cid:1247)n… [3]

§ Bi(cid:843)u di(cid:845)n b(cid:825)ng ch(cid:887) cái

§ Bi(cid:843)u di(cid:845)n b(cid:825)ng k(cid:839)t h(cid:875)p ch(cid:887) và s(cid:857)

§ (cid:171)

1.2.1.3 Kh(cid:1251)i t(cid:1189)o qu(cid:1195)n th(cid:1223)

(cid:264)(cid:1223) kh(cid:1251)i t(cid:1189)o qu(cid:1195)n th(cid:1223)(cid:3)(cid:255)(cid:1131)n gi(cid:1191)n ch(cid:1229) c(cid:1195)n kh(cid:1251)i t(cid:1189)o ng(cid:1199)u nhiên t(cid:1263)ng nhi(cid:1225)m

(cid:86)(cid:1203)c th(cid:1223) m(cid:1245)t. Tuy nhiên d(cid:1269)a vào tri th(cid:1261)c c(cid:1259)a bài toán ho(cid:1211)c v(cid:1201)n d(cid:1257)ng lý thuy(cid:1219)t

xác su(cid:1193)t mà ta có th(cid:1223) ch(cid:1233)n các cách kh(cid:1251)i t(cid:1189)o thích h(cid:1255)p. N(cid:1219)u l(cid:1269)a ch(cid:1233)n (cid:255)(cid:1133)(cid:1255)c

ph(cid:1133)(cid:1131)ng cách kh(cid:1251)i t(cid:1189)o t(cid:1237)t, thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n s(cid:1217) h(cid:1245)i t(cid:1257) r(cid:1193)t nhanh.

1.2.1.4 Các phép toán trên thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

o Tái sinh: là quá trình t(cid:1189)o nên qu(cid:1195)n th(cid:1223) m(cid:1247)i t(cid:1263) qu(cid:1195)n th(cid:1223) c(cid:458). D(cid:1269)a

vào ch(cid:1229) s(cid:1237) thích nghi c(cid:1259)a m(cid:1243)i cá th(cid:1223) mà cá th(cid:1223) này (cid:255)(cid:1133)(cid:1255)c xem xét

có (cid:255)(cid:1133)(cid:1255)c chuy(cid:1223)n sang qu(cid:1195)n th(cid:1223) m(cid:1247)i hay không. Quá trình này có

th(cid:1223) mô ph(cid:1235)ng nh(cid:1133) sau [1]:

§ Tính (cid:255)(cid:1245) thích nghi c(cid:1259)a t(cid:1263)ng cá th(cid:1223) trong qu(cid:1195)n th(cid:1223) hi(cid:1227)n

hành, l(cid:1201)p b(cid:1191)ng c(cid:1245)ng d(cid:1239)n cho các giá tr(cid:1231) thích nghi (theo s(cid:1237)

th(cid:1261) t(cid:1269) gán cho t(cid:1263)ng cá th(cid:1223)). Gi(cid:1191) s(cid:1265) qu(cid:1195)n th(cid:1223) có N cá th(cid:1223).

(cid:42)(cid:1233)i (cid:255)(cid:1245) thích nghi c(cid:1259)a cá th(cid:1223) th(cid:1261) i là Fi, t(cid:1241)ng d(cid:1239)n th(cid:1261) i là

Fti, t(cid:1241)ng (cid:255)(cid:1245) thích nghi toàn qu(cid:1195)n th(cid:1223) là FN.

§ (cid:55)(cid:1189)o m(cid:1245)t s(cid:1237) ng(cid:1199)u nhiên F trong (cid:255)(cid:82)(cid:1189)n t(cid:1263) 0 (cid:255)(cid:1219)n FN.

§ Ch(cid:1233)n cá th(cid:1223) th(cid:1261) k (cid:255)(cid:1195)u tiên th(cid:1235)a (cid:41)(cid:149)Ftk (cid:255)(cid:1133)a vào qu(cid:1195)n th(cid:1223)

(cid:70)(cid:1259)a th(cid:1219) h(cid:1227) m(cid:1247)i.

- 14 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

o Lai ghép (Crossover): c(cid:458)ng gi(cid:1237)ng nh(cid:1133) trong t(cid:1269) nhiên lai ghép là

quá trình hình thành cá th(cid:1223) m(cid:1247)i trên c(cid:1131) s(cid:1251) cá th(cid:1223) cha m(cid:1213) b(cid:1205)ng

cách ghép m(cid:1245)t (cid:255)(cid:82)(cid:1189)n gen c(cid:1259)a cá th(cid:1223) cha m(cid:1213) v(cid:1247)i nhau. Xác su(cid:1193)t

(cid:70)(cid:1259)a lai ghép là pc. Có th(cid:1223) mô ph(cid:1235)ng phép lai nh(cid:1133) sau [1]:

§ Ch(cid:1233)n ng(cid:1199)u nhiên hai (hay nhi(cid:1221)u) cá th(cid:1223) b(cid:1193)t kì trong qu(cid:1195)n

th(cid:1223). Gi(cid:1191) s(cid:1265) các nhi(cid:1225)m s(cid:1203)c th(cid:1223) c(cid:1259)a cha-m(cid:1213)(cid:3)(cid:255)(cid:1221)u có m gen.

§ (cid:55)(cid:1189)o m(cid:1245)t s(cid:1237) ng(cid:1199)u nhiên trong kho(cid:1191)ng t(cid:1263) 1 (cid:255)(cid:1219)n m-1 (ta g(cid:1233)i

là (cid:255)(cid:76)(cid:1223)m lai). (cid:264)(cid:76)(cid:1223)m lai chia các chu(cid:1243)i cha-m(cid:1213) dài m thành

hai nhóm chu(cid:1243)i con dài m1 và m2. Hai chu(cid:1243)i nhi(cid:1225)m s(cid:1203)c th(cid:1223)

con m(cid:1247)i s(cid:1217) là m11+m22 và m21+m12.

§ (cid:264)(cid:1133)a hai cá th(cid:1223) m(cid:1247)i này vào qu(cid:1197)n th(cid:1223)(cid:3)(cid:255)(cid:1223) có th(cid:1223) tham gia

quá trình ti(cid:1219)n hóa ti(cid:1219)p theo.

Ví d(cid:877): Gi(cid:811) s(cid:885) có 2 nhi(cid:845)m s(cid:823)c th(cid:843) (cá th(cid:843)) (cid:255)(cid:753)(cid:875)c bi(cid:843)u di(cid:845)n

(cid:69)(cid:825)ng ph(cid:753)(cid:751)ng pháp nh(cid:851) phân, m(cid:863)i nhi(cid:845)m s(cid:823)c th(cid:843) dài 7 bit

(A): 1001110 (B):0100011

(cid:57)(cid:851) trí lai (cid:255)(cid:753)(cid:875)c phát sinh ng(cid:819)u nhiên là 3, ta có 2 nhi(cid:845)m

(cid:86)(cid:823)c th(cid:843) sau khi lai:

(A(cid:182)):1001|011

(B(cid:182)):0100|110

Phép lai cho phép trao (cid:255)(cid:1241)i thông tin gi(cid:1267)a các l(cid:1249)i gi(cid:1191)i.

o (cid:264)(cid:1245)t bi(cid:1219)n (Mutation): là hi(cid:1227)n t(cid:1133)(cid:1255)ng cá th(cid:1223) con mang m(cid:1245)t s(cid:1237) tính

tr(cid:1189)ng không có trong mã di truy(cid:1221)n c(cid:1259)a cha m(cid:1213). (cid:264)(cid:1245)t bi(cid:1219)n có xác

su(cid:1193)t pm r(cid:1193)t nh(cid:1235) so v(cid:1247)i pc. Phép (cid:255)(cid:1245)t bi(cid:1219)n có th(cid:1223) mô ph(cid:1235)ng nh(cid:1133) sau

[1]:

- 15 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

§ Ch(cid:1233)n ng(cid:1199)u nhiên m(cid:1245)t cá th(cid:1223) cha-m(cid:1213) b(cid:1193)t kì trong qu(cid:1195)n th(cid:1223)

§ (cid:55)(cid:1189)o m(cid:1245)t s(cid:1237) ng(cid:1199)u nhiên k trong kho(cid:1191)ng t(cid:1263) 1 (cid:255)(cid:839)n m, 1 (cid:148) k (cid:148)

§ Thay (cid:255)(cid:1241)i gen th(cid:1261) k và tr(cid:1191) cá th(cid:1223) này v(cid:1221) qu(cid:1195)n th(cid:1223)(cid:3)(cid:255)(cid:1223) có th(cid:1223)

tham gia quá trình ti(cid:1219)n hóa ti(cid:1219)p theo.

Ví d(cid:877): Gi(cid:811) s(cid:885) nhi(cid:845)m s(cid:823)c th(cid:843) :

110011

(cid:69)(cid:851)(cid:3)(cid:255)(cid:865)t bi(cid:839)n t(cid:809)i v(cid:851) trí ng(cid:819)u nhiên là 2, ta có nhi(cid:845)m

(cid:86)(cid:823)c th(cid:843) m(cid:867)i:

110001

Phép (cid:255)(cid:1245)t bi(cid:1219)n cho phép t(cid:1189)o ra m(cid:1245)t l(cid:1249)i gi(cid:1191)i m(cid:1247)i.

o Ch(cid:1233)n l(cid:1233)c : Là quá trình lo(cid:1189)i b(cid:1235) các cá th(cid:1223) x(cid:1193)u trong qu(cid:1195)n th(cid:1223)(cid:3)(cid:255)(cid:1223)

ch(cid:1229) gi(cid:1267) l(cid:1189)i trong qu(cid:1195)n th(cid:1223) các cá th(cid:1223) t(cid:1237)t (cid:255)(cid:1223) t(cid:1263)(cid:3) (cid:255)ó sinh s(cid:1191)n, (cid:255)(cid:1245)t

bi(cid:1219)n t(cid:1189)o ra các cá th(cid:1223) m(cid:1247)i. Các cá th(cid:1223)(cid:3)(cid:255)(cid:1133)(cid:1255)c ch(cid:1233)n c(cid:458)ng d(cid:1269)a trên

giá tr(cid:1231) thích nghi c(cid:1259)a nó. Phép ch(cid:1233)n l(cid:1233)c có th(cid:1223)(cid:3) (cid:255)(cid:1133)(cid:1255)c mô ph(cid:1235)ng

nh(cid:1133) sau [1]:

§ (cid:54)(cid:1203)p x(cid:1219)p các cá th(cid:1223) trong qu(cid:1195)n th(cid:1223) theo (cid:255)(cid:1245) thích nghi gi(cid:1191)m

(cid:71)(cid:1195)n.

§ Lo(cid:1189)i b(cid:1235) các cá th(cid:1223)(cid:3)(cid:1251) cu(cid:1237)i dãy (cid:255)(cid:1223) ch(cid:1229) gi(cid:1267) l(cid:1189)i N cá th(cid:1223) t(cid:1237)t

nh(cid:1193)t. (cid:1250)(cid:3)(cid:255)ây ta gi(cid:1191) s(cid:1265) qu(cid:1195)n th(cid:1223) có kích th(cid:1133)(cid:1247)c N (cid:70)(cid:1237)(cid:3)(cid:255)(cid:1231)nh.

1.2.2 Thu(cid:837)t gi(cid:827)i di truy(cid:857)n t(cid:769)(cid:767)ng tác

Thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n t(cid:1133)(cid:1131)ng tác (IGA – Interative Genetic

Algorithms) là Thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n mà giá tr(cid:1231) thích nghi c(cid:1259)a các cá th(cid:1223)

- 16 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:255)(cid:1133)(cid:1255)c xác (cid:255)(cid:1231)nh d(cid:1269)a trên s(cid:1269) tu(cid:1131)ng tác v(cid:1247)i ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng. Thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:87)(cid:1133)(cid:1131)ng tác (cid:255)(cid:1133)(cid:1255)c xem là m(cid:1245)t công c(cid:1257) h(cid:1267)u ích (cid:255)(cid:1237)i v(cid:1247)i nh(cid:1267)ng bài toán mà tiêu

chu(cid:1197)n l(cid:1133)(cid:1255)ng giá r(cid:1193)t ph(cid:1261)c t(cid:1189)p và/ho(cid:1211)c thông tin không (cid:255)(cid:1195)y (cid:255)(cid:1259), khi(cid:1219)n cho

không th(cid:1223) xây d(cid:1269)ng m(cid:1245)t hàm thích nghi xác (cid:255)(cid:1231)nh [4], ví d(cid:1257) nh(cid:1133) nh(cid:1267)ng bài

toán liên quan (cid:255)(cid:1219)n hình (cid:1191)nh, âm thanh, gi(cid:1191) l(cid:1201)p th(cid:1219) gi(cid:1247)i th(cid:1269)c,… ch(cid:1229)(cid:3)(cid:255)(cid:1133)(cid:1255)c (cid:1133)(cid:1247)c

(cid:79)(cid:1133)(cid:1255)ng b(cid:1205)ng c(cid:1191)m giác, (cid:1193)n t(cid:1133)(cid:1255)ng, s(cid:1251) thích, c(cid:1191)m xúc hay s(cid:1269) nh(cid:1189)y bén c(cid:1259)a ng(cid:1133)(cid:1249)i

(cid:86)(cid:1265) d(cid:1257)ng h(cid:1227) th(cid:1237)ng [6]; (cid:255)(cid:1223) gi(cid:1191)i quy(cid:1219)t nh(cid:1267)ng bài toán này n(cid:1219)u s(cid:1265) d(cid:1257)ng các

ph(cid:1133)(cid:1131)ng pháp t(cid:1237)i (cid:1133)u hóa truy(cid:1221)n th(cid:1237)ng s(cid:1217) g(cid:1211)p r(cid:1193)t nhi(cid:1221)u khó kh(cid:259)n và (cid:255)(cid:1245) chính

xác th(cid:1133)(cid:1249)ng không cao, tuy nhiên do d(cid:1269)a vào ch(cid:1259) quan nên chúng l(cid:1189)i r(cid:1193)t thích

(cid:75)(cid:1255)p v(cid:1247)i Thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n t(cid:1133)(cid:1131)ng tác.

D(cid:1133)(cid:1247)i (cid:255)ây là l(cid:1133)(cid:1255)c (cid:255)(cid:1239) c(cid:1259)a Thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n t(cid:1133)(cid:1131)ng tác thông

th(cid:1133)(cid:1249)ng:

Hình 1-1 L(cid:753)(cid:874)c (cid:255)(cid:858) c(cid:878)a m(cid:864)t thu(cid:820)t gi(cid:810)i di truy(cid:840)n t(cid:753)(cid:751)ng

tác

- 17 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

Các b(cid:1133)(cid:1247)c c(cid:1259)a m(cid:1245)t thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n t(cid:1133)(cid:1131)ng tác :

(cid:37)(cid:585)(cid:859)c 1: Kh(cid:1251)i t(cid:1189)o qu(cid:1195)n th(cid:1223) (ng(cid:1199)u nhiên), th(cid:1223) hi(cid:1227)n k(cid:1219)t qu(cid:1191) cho ng(cid:1133)(cid:1249)i s(cid:1265)

(cid:71)(cid:1257)ng.

(cid:37)(cid:585)(cid:859)c 2: Ng(cid:1133)(cid:1249)i dùng ch(cid:1233)n m(cid:1245)t s(cid:1237) k(cid:1219)t qu(cid:1191) mà “(cid:70)(cid:811)m th(cid:813)y” (cid:255)úng.

(cid:37)(cid:585)(cid:859)c 3: Th(cid:1269)c hi(cid:1227)n ti(cid:1219)n hoá v(cid:1247)i s(cid:1237) th(cid:1219) h(cid:1227) nh(cid:1193)t (cid:255)(cid:1231)nh, v(cid:1247)i hàm thích nghi

(cid:71)(cid:1269)a trên nh(cid:1267)ng k(cid:1219)t qu(cid:1191) ng(cid:1133)(cid:1249)i dùng ch(cid:1233)n, trong (cid:255)ó nh(cid:1267)ng nhi(cid:1225)m s(cid:1203)c th(cid:1223)

(cid:255)(cid:1133)(cid:1255)c ch(cid:1233)n th(cid:1133)(cid:1249)ng có giá tr(cid:1231) thích nghi t(cid:1237)t nh(cid:1193)t.

(cid:37)(cid:585)(cid:859)c 4: Hi(cid:1223)n th(cid:1231) k(cid:1219)t qu(cid:1191) sau khi ti(cid:1219)n hoá.

(cid:37)(cid:585)(cid:859)c 5: Quay l(cid:1189)i (cid:37)(cid:1133)(cid:1247)c 2 (cid:81)(cid:1219)u ng(cid:1133)(cid:1249)i dùng ch(cid:1133)a ch(cid:1193)p nh(cid:1201)n k(cid:1219)t qu(cid:1191).

- 18 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

CCCHHH(cid:1131)(cid:1131)(cid:1131)(cid:1129)(cid:1129)(cid:1129)NNNGGG 222

DDD(cid:1266)(cid:1266)(cid:1266)NNNGGG (cid:1188)(cid:1188)(cid:1188)NNNHHH CCCHHHÂÂÂNNN DDDUUUNNNGGG TTT(cid:1260)(cid:1260)(cid:1260)

QQQUUUAAANNN SSSÁÁÁTTT BBB(cid:1202)(cid:1202)(cid:1202)NNNGGG TTTHHHUUU(cid:1198)(cid:1198)(cid:1198)TTT GGGIII(cid:1188)(cid:1188)(cid:1188)III

DDDIII TTTRRRUUUYYY(cid:1218)(cid:1218)(cid:1218)NNN

2.1 GI(cid:882)I THI(cid:862)U

Trong ch(cid:1133)(cid:1131)ng này, chúng tôi nghiên c(cid:1261)u bài toán ”Ph(cid:877)c h(cid:859)i (cid:811)nh chân

dung t(cid:883) quan sát(cid:180). Bài toán (cid:255)(cid:1133)(cid:1255)c mô t(cid:1191) tóm t(cid:1203)t qua k(cid:1231)ch b(cid:1191)n nh(cid:1133) sau:

(cid:179)(cid:48)(cid:865)t v(cid:877) án x(cid:811)y ra, t(cid:865)i ph(cid:809)m tr(cid:857)n thoát (cid:255)(cid:753)(cid:875)c. Nhà ch(cid:881)c trách có nhu

(cid:70)(cid:815)u phác h(cid:853)a l(cid:809)i chân dung t(cid:865)i ph(cid:809)m t(cid:883) nh(cid:887)ng nhân ch(cid:881)ng có m(cid:831)t t(cid:809)i hi(cid:847)n

tr(cid:753)(cid:869)ng. Quá trình (cid:255)(cid:753)(cid:875)c ti(cid:839)n hành nh(cid:753) sau:

(1). (cid:47)(cid:813)y l(cid:869)i khai c(cid:879)a nhân ch(cid:881)ng (mô t(cid:811) l(cid:809)i chân dung t(cid:865)i

ph(cid:809)m).

(2). (cid:43)(cid:847) th(cid:857)ng t(cid:861)ng h(cid:875)p l(cid:809)i các l(cid:869)i khai (cid:255)(cid:843) phác h(cid:853)a chân

dung.

Quá trình (cid:255)(cid:753)(cid:875)c ti(cid:839)p t(cid:877)c cho t(cid:867)i khi t(cid:813)t c(cid:811) nhân ch(cid:881)ng (cid:255)ã th(cid:857)ng nh(cid:813)t

(cid:89)(cid:867)i nhau m(cid:865)t (ho(cid:831)c m(cid:865)t s(cid:857)) chân dung t(cid:865)i ph(cid:809)m.

K(cid:1231)ch b(cid:1191)n trên s(cid:1217)(cid:3)(cid:255)(cid:1133)(cid:1255)c mô ph(cid:1235)ng b(cid:1205)ng ch(cid:1133)(cid:1131)ng trình máy tính mà n(cid:1221)n

(cid:87)(cid:1191)ng là Thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n t(cid:1133)(cid:1131)ng tác nh(cid:1133) trình bày trong ch(cid:753)(cid:751)ng 1.

- 19 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

Trong ch(cid:1133)(cid:1131)ng trình máy tính, vi(cid:1227)c mô t(cid:1191) chân dung t(cid:1245)i ph(cid:1189)m (cid:255)(cid:1133)(cid:1255)c

th(cid:1269)c hi(cid:1227)n trên các khuôn m(cid:1211)t phác th(cid:1191)o, còn thao tác t(cid:1241)ng h(cid:1255)p l(cid:1249)i khai (cid:255)(cid:1133)(cid:1255)c

th(cid:1269)c hi(cid:1227)n nh(cid:1249) vào thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n. Ho(cid:1189)t (cid:255)(cid:1245)ng c(cid:1259)a ch(cid:1133)(cid:1131)ng trình nh(cid:1133) sau:

Ch(cid:1133)(cid:1131)ng trình phát sinh các khuôn m(cid:1211)t phác th(cid:1191)o, ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng (nhân

ch(cid:1261)ng) tìm trong các khuôn m(cid:1211)t này khuôn m(cid:1211)t nào gi(cid:1237)ng v(cid:1247)i (cid:255)(cid:1237)i t(cid:1133)(cid:1255)ng

(t(cid:1245)i ph(cid:1189)m) nh(cid:1193)t, nh(cid:1267)ng ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng khác nhau có th(cid:1223) ch(cid:1233)n các khuôn

(cid:80)(cid:1211)t khác nhau; t(cid:1263) nh(cid:1267)ng khuôn m(cid:1211)t (cid:255)(cid:1133)(cid:1255)c ch(cid:1233)n, ch(cid:1133)(cid:1131)ng trình s(cid:1265) d(cid:1257)ng

thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n th(cid:1269)c hi(cid:1227)n ti(cid:1219)n hóa (cid:255)(cid:1223) cho ra các khuôn m(cid:1211)t phác

th(cid:1191)o h(cid:1255)p v(cid:1247)i mô t(cid:1191) c(cid:1259)a ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng nh(cid:1193)t; sau khi ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ch(cid:1233)n

(cid:255)(cid:1133)(cid:1255)c khuôn m(cid:1211)t phác th(cid:1191)o, ch(cid:1133)(cid:1131)ng trình tìm trong c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u (cid:1191)nh

chân dung th(cid:1201)t (cid:1191)nh c(cid:1259)a (cid:255)(cid:1237)i t(cid:1133)(cid:1255)ng t(cid:1133)(cid:1131)ng (cid:1261)ng v(cid:1247)i khuôn m(cid:1211)t phác th(cid:1191)o

(cid:89)(cid:1263)a tìm (cid:255)(cid:1133)(cid:1255)c.

Ch(cid:1133)(cid:1131)ng này s(cid:1217) t(cid:1201)p trung vào trình bày các thu(cid:1245)c tính c(cid:1259)a khuôn m(cid:1211)t,

cách mã hóa các thu(cid:1245)c tính và áp d(cid:1257)ng các thu(cid:1245)c tính này vào thu(cid:1201)t gi(cid:1191)i di

truy(cid:1221)n s(cid:1265) d(cid:1257)ng cho bài toán. Chúng tôi c(cid:458)ng qui (cid:1133)(cid:1247)c khi nh(cid:1203)c (cid:255)(cid:1219)n khuôn m(cid:831)t

phác th(cid:811)o là khuôn m(cid:1211)t do ch(cid:1133)(cid:1131)ng trình t(cid:1269) phát sinh và th(cid:1223) hi(cid:1227)n d(cid:1269)a vào các

thu(cid:1245)c tính khuôn m(cid:1211)t, còn (cid:811)nh chân dung là (cid:1191)nh thông th(cid:1133)(cid:1249)ng, (cid:255)(cid:1133)(cid:1255)c ch(cid:1257)p và

(cid:255)(cid:1133)a vào máy tính.

2.2 ÁP D(cid:892)NG THU(cid:836)T GI(cid:826)I DI TRUY(cid:856)N GI(cid:826)I

BÀI TOÁN PH(cid:892)C H(cid:874)I (cid:826)NH CHÂN DUNG

(cid:55)(cid:898) MÔ T(cid:826)

2.2.1 (cid:264)(cid:847)c tr(cid:769)ng và mã hóa (cid:255)(cid:847)c tr(cid:769)ng chân dung

2.2.1.1 (cid:264)(cid:1211)c tr(cid:1133)ng

(cid:48)(cid:1245)t khuôn m(cid:1211)t (cid:255)(cid:1133)(cid:1255)c bi(cid:1223)u di(cid:1225)n trong máy tính b(cid:1205)ng 20 thu(cid:1245)c tính :

- 20 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

01. Má – HeadCheek (Kí hi(cid:1225)u:HChk)

02. (cid:38)(cid:1203)m – HeadChin (HCh)

03. Hình d(cid:1187)ng khuôn m(cid:1209)t – HeadShape (HS)

04. Chi(cid:1219)u dài lông mày – EyeBrowLength (EBL)

05. (cid:264)(cid:1243)(cid:3)(cid:255)(cid:1199)m lông mày – EyeBrowStrength (EBStr)

06. (cid:57)(cid:1229) trí lông mày – EyebrowPosition (EBP)

07. Chi(cid:1219)u cao lông mày – EyeBrowHeight (EBH)

08. Hình d(cid:1187)ng lông mày – EyeBrowShape (EBS)

09. (cid:57)(cid:1229) trí m(cid:1201)t – EyePosition (EP)

10. Kích th(cid:1132)(cid:1245)c m(cid:1201)t – EyeSize (ES)

11. Kho(cid:1189)ng cách gi(cid:1265)a 2 m(cid:1201)t – EyeDistance (ED)

12. (cid:55)(cid:1227) l(cid:1225) chi(cid:1219)u cao m(cid:1201)t/chi(cid:1219)u r(cid:1243)ng m(cid:1201)t –

EyeHWRatio (EHWR)

13. Kích th(cid:1132)(cid:1245)c (cid:255)(cid:1237)ng t(cid:1263) - PupilSize (PS)

14. Chi(cid:1221)u dài m(cid:458)i – NoseLength (NL)

15. Chi(cid:1219)u r(cid:1243)ng m(cid:458)i – NoseWidth (NW)

16. Hình d(cid:1187)ng m(cid:458)i – NoseShape (NS)

17. Chi(cid:1219)u r(cid:1243)ng mi(cid:1225)ng – MouthWidth (MW)

18. (cid:57)(cid:1229) trí mi(cid:1225)ng – MouthPosition (MP)

19. (cid:264)(cid:1243) dày môi trên – MouthThicknessOfUpperLip

(MTUL)

- 21 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

20. (cid:264)(cid:1243) dày môi d(cid:1132)(cid:1245)i - MouthThicknessOfLowerLip

(MTLL)

2.2.1.2 Mi(cid:1221)n xác (cid:255)(cid:1231)nh c(cid:1259)a các (cid:255)(cid:1211)c tr(cid:1133)ng

1. Má

(cid:37)(cid:1245) (cid:264)(cid:1211)c Trung bình Stt Min (0) Max (15) ph(cid:1201)n tr(cid:1133)ng (7)

Khuôn

2. (cid:38)(cid:1205)m

1. (cid:80)(cid:1211)t

3. Hình

(cid:71)(cid:1189)ng

khuôn

(cid:80)(cid:1211)t

2.

4. Chi(cid:1221)u

Lông

dài

mày

5. (cid:264)(cid:1245)(cid:3)(cid:255)(cid:1201)m

- 22 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

6. (cid:57)(cid:1231) trí

7. Chi(cid:1221)u

cao

8. Hình

(cid:71)(cid:1189)ng

3. (cid:48)(cid:1203)t

9. (cid:57)(cid:1231) trí

10. Kích

th(cid:1133)(cid:1247)c

11. Kho(cid:1191)ng

cách

gi(cid:1267)a hai

(cid:80)(cid:1203)t

- 23 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

12. (cid:55)(cid:1229) l(cid:1227)

cao /

(cid:85)(cid:1245)ng

13. Kích

th(cid:1133)(cid:1247)c

(cid:255)(cid:1239)ng t(cid:1265)

14. Chi(cid:1221)u

dài

15. Chi(cid:1221)u

4. (cid:48)(cid:458)i

(cid:85)(cid:1245)ng

16. Hình

(cid:71)(cid:1189)ng

17. Chi(cid:1221)u

5. Mi(cid:1227)ng

(cid:85)(cid:1245)ng

18. (cid:57)(cid:1231) trí

- 24 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

19. (cid:264)(cid:1245) dày

môi

trên

20. (cid:264)(cid:1245) dày

môi

(cid:71)(cid:1133)(cid:1247)i

2.2.1.3 Mã hoá (cid:255)(cid:1211)c tr(cid:1133)ng

Trong bài toán này, ta bi(cid:1223)u di(cid:1225)n nhi(cid:1225)m s(cid:1203)c th(cid:1223) b(cid:1205)ng chu(cid:1243)i nh(cid:1231) phân 0,1.

(cid:264)(cid:1237)i v(cid:1247)i m(cid:1243)i thu(cid:1245)c tính, l(cid:1193)y mi(cid:1221)n xác (cid:255)(cid:1231)nh trong kho(cid:1191)ng [0..15], t(cid:1261)c là

(cid:79)(cid:1193)y 16 giá tr(cid:1231) khác nhau. S(cid:1251) d(cid:429) ch(cid:1233)n con s(cid:1237) 16 vì 16 là m(cid:1245)t l(cid:458)y th(cid:1263)a c(cid:1259)a 2,

thu(cid:1201)n l(cid:1255)i cho vi(cid:1227)c bi(cid:1223)u di(cid:1225)n, n(cid:1219)u ch(cid:1233)n 8 thì s(cid:1237) giá tr(cid:1231) bi(cid:1223)u di(cid:1225)n (cid:255)(cid:1133)(cid:1255)c quá ít,

còn 32 thì l(cid:1189)i quá nhi(cid:1221)u.

§ Bi(cid:1223)u di(cid:1225)n 1 gen: Xem m(cid:1243)i thu(cid:1245)c tính nh(cid:1133) m(cid:1245)t gen, do có 16 giá tr(cid:1231) cho

(cid:80)(cid:1243)i thu(cid:1245)c tính nên (cid:255)(cid:1237)i v(cid:1247)i m(cid:1243)i gen (cid:255)(cid:1223) bi(cid:1223)u di(cid:1225)n ta c(cid:1195)n 4 bit.

Ví d(cid:877): Gi(cid:811) s(cid:885) thu(cid:865)c tính HeadShape mang giá tr(cid:851) 9, nh(cid:753) v(cid:821)y gen bi(cid:843)u di(cid:845)n s(cid:837)

là 1001.

§ Bi(cid:1223)u di(cid:1225)n chu(cid:1243)i nhi(cid:1225)m s(cid:1203)c th(cid:1223): M(cid:1245)t nhi(cid:1225)m s(cid:1203)c th(cid:1223) là m(cid:1245)t chu(cid:1243)i tuy(cid:1219)n

tính các gen, m(cid:1243)i gen có v(cid:1231) trí xác (cid:255)(cid:1231)nh trong chu(cid:1243)i. Do có t(cid:1193)t c(cid:1191) 20

thu(cid:1245)c tính, t(cid:1261)c là có 20 gen nên m(cid:1243)i nhi(cid:1225)m s(cid:1203)c th(cid:1223)(cid:3)(cid:255)(cid:1133)(cid:1255)c bi(cid:1223)u di(cid:1225)n b(cid:1205)ng

chu(cid:1243)i nh(cid:1231) phân có chi(cid:1221)u dài 20(gen) x 4(bit/gen) = 80 bit.

Qui (cid:1133)(cid:1247)c cho m(cid:1243)i gen m(cid:1245)t ví trí c(cid:1237)(cid:3) (cid:255)(cid:1231)nh trong nhi(cid:1225)m s(cid:1203)c th(cid:1223), gi(cid:1191) s(cid:1265)

HeadCheek(HChk) v(cid:1231) trí 1, HeadChin(HCh) v(cid:1231) trí 2, HeadShape(HS) v(cid:1231)

trí 3, …, MouthThicknessOfLowerLip (MTLL) v(cid:1231) trí 20, ta có bi(cid:1223)u di(cid:1225)n

(cid:70)(cid:1259)a m(cid:1245)t nhi(cid:1225)m s(cid:1203)c th(cid:1223) nh(cid:1133) sau:

- 25 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

HChk.HCh.HS.EBL.EBStr.EBP.EBH.EBS.EP.ES.ED.EHWR.PS.

NL.NW.NS.MW.MP.MTUL.MTLL.

Ví d(cid:877): Ta có 4 nhi(cid:845)m s(cid:823)c th(cid:843) bi(cid:843)u di(cid:845)n cho 4 khuôn m(cid:831)t. Trong (cid:255)ó,

khuôn m(cid:831)t (A) nhi(cid:845)m s(cid:823)c th(cid:843) có các gen mang toàn giá tr(cid:851) 0 (giá tr(cid:851) bit

0000), khuôn m(cid:831)t (B) mang giá tr(cid:851) trung bình 7 (giá tr(cid:851) bit 1110), khuôn m(cid:831)t

(C) toàn giá tr(cid:851) l(cid:867)n nh(cid:813)t 15 (giá tr(cid:851) bit 1111), còn khuôn m(cid:831)t (D) mang giá tr(cid:851)

ng(cid:819)u nhiên.

(A)Nhi(cid:844)m s(cid:822)c th(cid:842): 0000.0000...0000

(B) Nhi(cid:844)m s(cid:822)c th(cid:842): 1000.1000...1000

(C)Nhi(cid:844)m s(cid:822)c th(cid:842): 1111.1111...1111

- 26 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(D)Nhi(cid:844)m s(cid:822)c th(cid:842):

2.2.2 Hàm thích nghi

Ta xem m(cid:1243)i khuôn m(cid:1211)t nh(cid:1133) m(cid:1245)t (cid:255)(cid:76)(cid:1223)m nguyên trong không gian 20 chi(cid:1221)u {0, … , 15}20, trong (cid:255)ó giá tr(cid:1231) c(cid:1259)a thu(cid:1245)c tính (cid:255)óng vai trò t(cid:1233)a (cid:255)(cid:1245). D(cid:1269)a

trên kho(cid:1191)ng cách gi(cid:1267)a các (cid:255)(cid:76)(cid:1223)m trong không gian này, giá tr(cid:1231) thích nghi

(cid:255)(cid:1133)(cid:1255)c tính theo qui t(cid:1203)c sau :

(1). (cid:264)(cid:1237)i v(cid:1247)i nh(cid:1267)ng khuôn m(cid:1211)t (cid:255)(cid:1133)(cid:1255)c ch(cid:1233)n: Giá tr(cid:1231) thích nghi = Giá tr(cid:1231)

thích nghi l(cid:1247)n nh(cid:1193)t = Kho(cid:1191)ng cách xa nh(cid:1193)t = 61 (nh(cid:1133) tính (cid:1251) d(cid:1133)(cid:1247)i).

(2). (cid:264)(cid:1237)i v(cid:1247)i các khuôn m(cid:1211)t còn l(cid:1189)i: D(cid:1269)a trên kho(cid:1191)ng cách (cid:255)(cid:1219)n khuôn

(cid:80)(cid:1211)t trung bình.

Trong tr(cid:1133)(cid:1249)ng h(cid:1255)p (1), g(cid:1233)i MaxFace(15, … ,15) là (cid:255)(cid:76)(cid:1223)m xa nh(cid:1193)t trong

(cid:75)(cid:1227) t(cid:1233)a (cid:255)(cid:1245), O(0, … ,0) là tâm t(cid:1233)a (cid:255)(cid:1245), vì t(cid:1193)t c(cid:1191) các (cid:255)(cid:76)(cid:1223)m (cid:255)(cid:1221)u có t(cid:1233)a (cid:255)(cid:1245) không

âm, ta có kho(cid:1191)ng cách Euclide gi(cid:1267)a hai khuôn m(cid:1211)t xa nh(cid:1193)t là:

Dmax

MaxFace

O-

15(

15.20

const

» - (cid:229)

Do (cid:255)ó giá tr(cid:1231) thích nghi l(cid:1247)n nh(cid:1193)t là 61.

Tr(cid:1133)(cid:1249)ng h(cid:1255)p (2), khuôn m(cid:1211)t trung bình A(a1, …aj ,… am) (cid:70)(cid:1259)a n khuôn

(cid:80)(cid:1211)t (F1, F2, …, Fn) (cid:89)(cid:1247)i Fi = ( xi1 ,…, xij ,…, xim) trong (cid:255)ó m là s(cid:1237) thu(cid:1245)c tính

(trong lu(cid:1201)n v(cid:259)n m = 20), (cid:255)(cid:1133)(cid:1255)c xác (cid:255)(cid:1231)nh nh(cid:1133) sau:

- 27 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:229)

1 n

£ £

Công th(cid:880)c 2-1 T(cid:852)a (cid:255)(cid:864) các (cid:255)(cid:76)(cid:842)m c(cid:878)a khuôn m(cid:830)t trung

bình A

D , AFi

(cid:42)(cid:1233)i là kho(cid:1191)ng cách t(cid:1263) khuôn m(cid:1211)t th(cid:1261) i (Fi) (cid:255)(cid:1219)n m(cid:1211)t trung bình A.

Công th(cid:1261)c tính kho(cid:1191)ng cách nh(cid:1133) sau:

=

- -

D

AF

(

x

a

)

AF , i

(cid:229)

Công th(cid:880)c 2-2 Kho(cid:810)ng cách t(cid:882) khuôn m(cid:830)t Fi(cid:3)(cid:255)(cid:838)n khuôn

(cid:80)(cid:830)t trung bình A

Ghi chú: Do kho(cid:1191)ng cách Euclide s(cid:1265) d(cid:1257)ng phép l(cid:1193)y c(cid:259)n chi(cid:1219)m nhi(cid:1221)u

th(cid:1249)i gian tính toán c(cid:1259)a máy nên trong lu(cid:1201)n v(cid:259)n s(cid:1265) d(cid:1257)ng (cid:255)(cid:1245)(cid:3)(cid:255)o City-Block(cid:3)(cid:255)(cid:1223)

thay th(cid:1219). (cid:264)(cid:1245)(cid:3) (cid:255)o kho(cid:1191)ng cách City-Block gi(cid:1267)a hai vector (cid:255)(cid:1211)c tr(cid:1133)ng c(cid:1259)a hai

khuôn m(cid:1211)t phác th(cid:1191)o Fa(xa1,…,xam) và Fb(xb1,…,xbm) (cid:255)(cid:1133)(cid:1255)c tính nh(cid:1133) sau:

=

- -

D

x

F

(cid:229)

F a

FF , a

Công th(cid:880)c 2-3 (cid:264)(cid:864)(cid:3)(cid:255)o kho(cid:810)ng cách City-Block

Theo công th(cid:1261)c này thì Dmax(cid:3)(cid:255)(cid:1133)(cid:1255)c tính l(cid:1189)i nh(cid:1133) sau:

Dmax

MaxFace

O-

15.20

300

const

- (cid:229)

- 28 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

Kho(cid:1191)ng cách t(cid:1263) khuôn m(cid:1211)t trung bình A(a1, …aj ,… am) (cid:255)(cid:1219)n khuôn

(cid:80)(cid:1211)t th(cid:1261) i Fi = ( xi1 ,…, xij ,…, xim):

=

- -

D

x

a

AF

AF , i

(cid:229)

Công th(cid:880)c 2-4 Kho(cid:810)ng cách City-Block gi(cid:886)a Fi và A

Công th(cid:881)c tính giá tr(cid:851) thích nghi :

(cid:42)(cid:1233)i eval(Fi) là giá tr(cid:1231) thích nghi cho khuôn m(cid:1211)t th(cid:1261) i. Ta có công th(cid:1261)c

tính giá tr(cid:1231) thích nghi nh(cid:1133) sau :

D , ) AFi

Eval (Fi) = IF ( Fi(cid:3)(cid:255)(cid:1133)(cid:1255)c ch(cid:1233)n , Dmax , Dmax –

Công th(cid:880)c 2-5 Giá tr(cid:850) thích nghi c(cid:878)a khuôn m(cid:830)t Fi

2.2.3 Thu(cid:837)t gi(cid:827)i di truy(cid:857)n

2.2.3.1 Các phép toán

2.2.3.1.1 Tái sinh

(cid:264)(cid:1223) ch(cid:1233)n ra m(cid:1245)t qu(cid:1195)n th(cid:1223) khuôn m(cid:1211)t m(cid:1247)i t(cid:1263) qu(cid:1195)n th(cid:1223) hi(cid:1227)n hành, ta s(cid:1265)

(cid:71)(cid:1257)ng ph(cid:1133)(cid:1131)ng pháp tái sinh nh(cid:1133) trong thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n thông th(cid:1133)(cid:1249)ng, dùng

nguyên t(cid:1203)c quay bánh xe Rulét v(cid:1247)i các rãnh (cid:255)(cid:1133)(cid:1255)c (cid:255)(cid:1231)nh ngh(cid:429)a d(cid:1269)a trên (cid:255)(cid:1245)

thích nghi. C(cid:1257) th(cid:1223) g(cid:1233)i pop_size là kích th(cid:1133)(cid:1247)c qu(cid:1195)n th(cid:1223) (s(cid:1237) khuôn m(cid:1211)t trong

qu(cid:1195)n th(cid:1223)), thao tác tái sinh (cid:255)(cid:1133)(cid:1255)c th(cid:1269)c hi(cid:1227)n nh(cid:1133) sau [1]:

§ Tính (cid:255)(cid:1245) thích nghi cho m(cid:1243)i khuôn m(cid:1211)t:

eval

(

,...,1{

pop

size

}

F i

˛ "

§ Tính t(cid:1241)ng (cid:255)(cid:1245) thích nghi c(cid:1259)a qu(cid:1195)n th(cid:1223):

- 29 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

pop

size eval

(

)

= 1

(cid:229)

)

F i

§ Tính xác su(cid:1193)t ch(cid:1233)n cho m(cid:1243)i khuôn m(cid:1211)t:

,...,1{

pop

size }

p i

eval ( F

§ Tính v(cid:1231) trí xác su(cid:1193)t:

(cid:229)

§ Ti(cid:1219)n hành ch(cid:1233)n: M(cid:1243)i l(cid:1195)n ch(cid:1233)n m(cid:1245)t nhi(cid:845)m s(cid:823)c th(cid:843)/khuôn m(cid:831)t t(cid:1263) qu(cid:1195)n

th(cid:1223) hi(cid:1227)n hành vào qu(cid:1195)n th(cid:1223) m(cid:1247)i theo cách sau:

[0,1] o Phát sinh ng(cid:1199)u nhiên m(cid:1245)t s(cid:1237) th(cid:1269)c r ˛

o (cid:49)(cid:1219)u r (cid:148) q1 thì khuôn m(cid:1211)t (cid:255)(cid:1195)u tiên (f1)(cid:3)(cid:255)(cid:1133)(cid:1255)c ch(cid:1233)n, ng(cid:1133)(cid:1255)c l(cid:1189)i ch(cid:1233)n

khuôn m(cid:1211)t th(cid:1261) i (fi) sao cho qi-1 < r (cid:148) qi

2.2.3.1.2 Lai

(cid:264)(cid:1237)i v(cid:1247)i m(cid:1243)i khuôn m(cid:1211)t trong qu(cid:1195)n th(cid:1223) m(cid:1247)i, phát sinh ng(cid:1199)u nhiên m(cid:1245)t

(cid:86)(cid:1237) th(cid:1269)c r ˛ [0,1], n(cid:1219)u r nh(cid:1235) h(cid:1131)n xác su(cid:1193)t lai pc thì ch(cid:1233)n khuôn m(cid:1211)t (cid:255)ó (cid:255)(cid:1223) lai.

Sau khi (cid:255)ã ch(cid:1233)n (cid:255)(cid:1259) s(cid:1237) khuôn m(cid:1211)t, ta ti(cid:1219)n hành thao tác lai ghép nh(cid:1133)

§ (cid:264)(cid:1237)i v(cid:1247)i m(cid:1243)i c(cid:1211)p khuôn m(cid:1211)t (cid:255)(cid:1133)(cid:1255)c ghép (cid:255)ôi, phát sinh ng(cid:1199)u nhiên m(cid:1245)t

(cid:86)(cid:1237) nguyên pos ˛ {1,…,m-1} (m là t(cid:1241)ng s(cid:1237) bit (cid:255)(cid:1223) bi(cid:1223)u di(cid:1225)n nhi(cid:1225)m s(cid:1203)c

th(cid:1223), m=20 x 4 = 80 bit). S(cid:1237) pos cho bi(cid:1219)t v(cid:1231) trí (cid:255)(cid:1223) lai.

§ Thay hai khuôn m(cid:1211)t trên:

(a1a2(cid:171)aposapos+1(cid:171)am) và

- 30 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(b1b2(cid:171)bposbpos+1(cid:171)bm)

(cid:69)(cid:1205)ng hai khuôn m(cid:1211)t m(cid:1247)i:

(a1a2(cid:171)aposbpos+1(cid:171)bm) và

(b1b2(cid:171)bposapos+1(cid:171)am)

Vì s(cid:1237) khuôn m(cid:1211)t ch(cid:1233)n cho lai c(cid:1195)n là m(cid:1245)t s(cid:1237) ch(cid:1209)n nên n(cid:1219)u sau thao tác

ch(cid:1233)n lai s(cid:1237) khuôn m(cid:1211)t (cid:255)(cid:1133)(cid:1255)c ch(cid:1233)n là s(cid:1237) l(cid:1215), ta c(cid:1245)ng thêm b(cid:1205)ng ch(cid:1233)n ng(cid:1199)u nhiên

(cid:80)(cid:1245)t khuôn m(cid:1211)t trong s(cid:1237) các khuôn m(cid:1211)t còn l(cid:1189)i.

Trong cài (cid:255)(cid:1211)t c(cid:1259)a chúng tôi, (cid:255)(cid:1237)i v(cid:1247)i m(cid:1243)i c(cid:1211)p khuôn m(cid:1211)t, thao tác lai

ghép trên (cid:255)(cid:1133)(cid:1255)c ti(cid:1219)n hành theo cách sau: 1. Phát sinh ng(cid:819)u nhiên m(cid:865)t s(cid:857) k˛ {1,..,5} 2.Ti(cid:839)n hành k l(cid:815)n lai ghép (pos(cid:3)(cid:255)(cid:753)(cid:875)c phát sinh ng(cid:819)u nhiên k l(cid:815)n).

Ví d(cid:877) : Lai 2 khuôn m(cid:831)t (A) và (B) v(cid:867)i s(cid:857) l(cid:815)n lai k = 3; v(cid:851) trí lai pos

(cid:255)(cid:753)(cid:875)c phát sinh l(cid:815)n l(cid:753)(cid:875)t là 17, 8, 15; xác su(cid:813)t lai pc=0.5; ta (cid:255)(cid:753)(cid:875)c 2 khuôn m(cid:831)t

(A(cid:182)) và (B(cid:182)). Có th(cid:843) th(cid:813)y (A(cid:182)) và (B(cid:182)) v(cid:883)a mang nh(cid:887)ng (cid:255)(cid:831)c tr(cid:753)ng c(cid:879)a cha v(cid:883)a

mang (cid:255)(cid:831)c tr(cid:753)ng c(cid:879)a m(cid:833): (A(cid:182)) mang (cid:39)(cid:809)ng m(cid:831)t, M(cid:458)i, Lông mày(cid:171) c(cid:879)a (B) và

(cid:48)(cid:823)t, Mi(cid:847)ng(cid:171) (cid:70)(cid:879)a (A); (cid:87)(cid:753)(cid:751)ng t(cid:889) (B(cid:182)) mang (cid:39)(cid:809)ng m(cid:831)t, M(cid:458)i, Lông mày(cid:171)

(cid:70)(cid:879)a (A), (cid:48)(cid:823)t, Mi(cid:847)ng(cid:171) (cid:70)(cid:879)a (B)

- 31 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

Lai 2 khuôn m(cid:831)t (C) và (D) v(cid:867)i k = 2 và pos (cid:255)(cid:753)(cid:875)c phát sinh l(cid:815)n l(cid:753)(cid:875)t là

10, 17; pc v(cid:819)n là 0.5:

- 32 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

)

) (cid:182)

(

p é h g

i a L

) (cid:182)

)

(

2.2.3.1.3 (cid:264)(cid:881)t bi(cid:855)n

(cid:264)(cid:1245)t bi(cid:1219)n trên c(cid:1131) s(cid:1251) t(cid:1263)ng bít. G(cid:1233)i pm là xác su(cid:1193)t (cid:255)(cid:1245)t bi(cid:1219)n, v(cid:1247)i m(cid:1233)i

khuôn m(cid:1211)t Fi trong qu(cid:1195)n th(cid:1223):

§ (cid:57)(cid:1247)i m(cid:1243)i bit trong nhi(cid:1225)m s(cid:1203)c th(cid:1223) bi(cid:1223)u di(cid:1225)n Fi, phát sinh ng(cid:1199)u nhiên m(cid:1245)t

(cid:86)(cid:1237) r ˛ [0,1].

- 33 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

§ (cid:49)(cid:1219)u r < pm thì ti(cid:1219)n hành (cid:255)(cid:1245)t bi(cid:1219)n: N(cid:1219)u bit có giá tr(cid:1231) 0 thì gán nó thành

1 và ng(cid:1133)(cid:1255)c l(cid:1189)i, n(cid:1219)u bit có giá tr(cid:1231) 1 thì (cid:255)(cid:1241)i nó thành 0.

Ví d(cid:877) : Sau khi (cid:255)(cid:865)t bi(cid:839)n khuôn m(cid:831)t (E) (cid:89)(cid:867)i pm=0.005, ta (cid:255)(cid:753)(cid:875)c khuôn m(cid:831)t m(cid:867)i

(E(cid:182)), v(cid:851) trí (cid:255)(cid:865)t bi(cid:839)n (cid:871) gen s(cid:857) 16, bit 1 và gen s(cid:857) 18, bit 1. (cid:264)ây là 2 gen bi(cid:843)u

di(cid:845)n cho (cid:255)(cid:831)c tr(cid:753)ng Hình d(cid:809)ng m(cid:458)i và (cid:57)(cid:851) trí mi(cid:847)ng, quan sát hai khuôn m(cid:831)t

(E) và (E(cid:182)) có th(cid:843) th(cid:813)y s(cid:889) khác bi(cid:847)t này: m(cid:458)i c(cid:879)a khuôn m(cid:831)t (E) và c(cid:879)a

khuôn m(cid:831)t (E(cid:182)) có hình d(cid:809)ng khác nhau; v(cid:851) trí mi(cid:847)ng c(cid:458)ng có s(cid:889) khác nhau

(E)

((cid:40)(cid:182))

tuy không nhi(cid:841)u do (cid:255)(cid:865) chênh l(cid:847)ch không l(cid:867)n (1001 và 1000)

- 34 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:264)(cid:865)t bi(cid:839)n khuôn m(cid:831)t (F) (cid:89)(cid:867)i pm=0.001, ta (cid:255)(cid:753)(cid:875)c khuôn m(cid:831)t m(cid:867)i (F(cid:182)), v(cid:851) trí (cid:255)(cid:865)t

bi(cid:839)n (cid:871) gen s(cid:857) 20, bit 3. (cid:264)ây là 2 gen bi(cid:843)u di(cid:845)n cho (cid:255)(cid:831)c tr(cid:753)ng (cid:264)(cid:865) d(cid:811)y môi

(cid:71)(cid:753)(cid:867)i, ta có th(cid:843) th(cid:813)y s(cid:889) khác bi(cid:847)t này khi quan sát mi(cid:847)ng c(cid:879)a hai khuôn m(cid:831)t:

(F)

n (cid:1219) b t (cid:1245) (cid:264)

((cid:41)(cid:182))

môi d(cid:753)(cid:867)i c(cid:879)a khuôn m(cid:831)t (F) dày h(cid:751)n khuôn m(cid:831)t (F(cid:182))

2.2.3.1.4 Ch(cid:869)n l(cid:869)c

Thao tác này nh(cid:1205)m lo(cid:1189)i b(cid:1235) kh(cid:1235)i qu(cid:1195)n th(cid:1223) nh(cid:1267)ng khuôn m(cid:1211)t có (cid:255)(cid:1245) thích

nghi kém, ta th(cid:1269)c hi(cid:1227)n nh(cid:1133) sau:

§ (cid:54)(cid:1203)p x(cid:1219)p qu(cid:1195)n th(cid:1223) theo (cid:255)(cid:1245) thích nghi gi(cid:1191)m d(cid:1195)n.

- 35 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

§ Gi(cid:1267) l(cid:1189)i trong qu(cid:1195)n th(cid:1223) 90% khuôn m(cid:1211)t (cid:255)(cid:1195)u tiên, 10% khuôn m(cid:1211)t còn l(cid:1189)i

(cid:255)(cid:1133)(cid:1255)c phát sinh ng(cid:1199)u nhiên (cid:255)(cid:1223)(cid:3)(cid:255)(cid:1191)m b(cid:1191)o tính (cid:255)a d(cid:1189)ng c(cid:1259)a qu(cid:1195)n th(cid:1223)

2.2.3.2 Thu(cid:1201)t gi(cid:1191)i

2.2.3.2.1 Tham s(cid:873)

Các tham s(cid:1237) cho thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n (cid:255)(cid:1133)(cid:1255)c áp d(cid:1257)ng trong cài (cid:255)(cid:1211)t:

Stt Tên Giá tr(cid:1231) ch(cid:1233)n

1 (cid:54)(cid:857)(cid:3)(cid:255)(cid:831)c tr(cid:753)ng (gen) 20

2 (cid:54)(cid:857) bit / gen 4

3 (cid:54)(cid:857) th(cid:839) h(cid:847) m(cid:863)i l(cid:815)n ti(cid:839)n hoá 10

4 Kích th(cid:753)(cid:867)c qu(cid:815)n th(cid:843) 150

5 (cid:54)(cid:857) cá th(cid:843)(cid:3)(cid:255)(cid:753)(cid:875)c th(cid:843) hi(cid:847)n 20

6 Xác su(cid:813)t (cid:255)(cid:865)t bi(cid:839)n 0,001

7 Xác su(cid:813)t lai 0,5

Trong (cid:255)ó (cid:54)(cid:857) cá th(cid:843)(cid:3) (cid:255)(cid:753)(cid:875)c th(cid:843) hi(cid:847)n là s(cid:1237) khuôn m(cid:1211)t (cid:255)(cid:1133)(cid:1255)c (cid:255)(cid:1133)a ra (cid:255)(cid:1223)

ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ch(cid:1233)n.

2.2.3.2.2 Thu(cid:837)t gi(cid:827)i

(cid:1250)(cid:3)(cid:255)ây ch(cid:1229) trình bày b(cid:1133)(cid:1247)c ti(cid:1219)n hóa c(cid:1259)a thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n sau khi ng(cid:1133)(cid:1249)i

(cid:86)(cid:1265) d(cid:1257)ng ch(cid:1233)n nh(cid:1267)ng khuôn m(cid:1211)t thích h(cid:1255)p nh(cid:1193)t (theo ý ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng) t(cid:1263)

nh(cid:1267)ng khuôn m(cid:1211)t (cid:255)(cid:1133)(cid:1255)c th(cid:1223) hi(cid:1227)n, chi ti(cid:1219)t toàn b(cid:1245) thu(cid:1201)t gi(cid:1191)i áp d(cid:1257)ng (cid:255)(cid:1223) gi(cid:1191)i

quy(cid:1219)t bài toán s(cid:1217)(cid:3)(cid:255)(cid:1133)(cid:1255)c trình bày (cid:1251) ch(cid:1133)(cid:1131)ng sau.

- 36 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:42)(cid:1233)i t là bi(cid:1219)n (cid:255)(cid:1219)m, ch(cid:1229) th(cid:1219) h(cid:1227) ti(cid:1219)n hóa hi(cid:1227)n t(cid:1189)i; P(t) là qu(cid:1195)n th(cid:1223)(cid:3)(cid:1251) th(cid:1219) h(cid:1227) t, t

(cid:149) 0 (cid:89)(cid:1247)i P(0) (cid:255)(cid:1133)(cid:1255)c kh(cid:1251)i t(cid:1189)o ng(cid:1199)u nhiên. Thao tác ti(cid:1219)n hóa (cid:255)(cid:1133)(cid:1255)c th(cid:1269)c hi(cid:1227)n

theo các b(cid:1133)(cid:1247)c sau:

(cid:37)(cid:585)(cid:859)c 1:

o t = 0

o Tính khuôn m(cid:1209)t trung bình A t(cid:1261) các khuôn

(cid:80)(cid:1209)t trong qu(cid:1193)n th(cid:1221) P(0) theo công th(cid:882)c 2-1:

o (cid:55)(cid:1261) khuôn m(cid:1209)t trung bình, tính giá tr(cid:1229) thích

nghi c(cid:1257)a t(cid:1191)t c(cid:1189) các khuôn m(cid:1209)t trong P(0)

theo công th(cid:882)c 2-5:

eval (Fi) = IF ( Fi(cid:3)(cid:255)(cid:1132)(cid:1253)c ch(cid:1231)n , Dmax ,

D , ) AFi

Dmax –

(cid:49)(cid:1217)u khuôn m(cid:1209)t (cid:255)(cid:1132)(cid:1253)c ch(cid:1231)n, giá tr(cid:1229) thích nghi

(cid:86)(cid:1215) là giá tr(cid:1229) l(cid:1245)n nh(cid:1191)t, b(cid:1203)ng Dmax (b(cid:1203)ng

D , AFi

300); ng(cid:1132)(cid:1253)c l(cid:1187)i tính kho(cid:1189)ng cách (cid:87)(cid:1261) Fi

(cid:255)(cid:1217)n A theo công th(cid:882)c 2-4, giá tr(cid:1229) thích

D , . AFi

nghi b(cid:1203)ng Dmax -

(cid:37)(cid:585)(cid:859)c 2:

o t = t + 1

o Tái sinh P(t-1) theo ph(cid:1132)(cid:1130)ng pháp (cid:255)(cid:1132)(cid:1253)c trình

bày trong 2.2.3.1.1 ta (cid:255)(cid:1132)(cid:1253)c P’(t).

- 37 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

o Lai ghép: C(cid:1259) m(cid:1241)i cá th(cid:1221) trong P’(t), phát

sinh m(cid:1243)t s(cid:1235) ng(cid:1197)u nhiên r, n(cid:1217)u r < pc thì

(cid:255)em cá th(cid:1221)(cid:3) (cid:255)ó lai (t(cid:1132)(cid:1130)ng t(cid:1267) nh(cid:1132) trong

2.2.3.1.2). Sau khi th(cid:1267)c hi(cid:1225)n lai, ta có

(cid:255)(cid:1132)(cid:1253)c t(cid:1199)p Q(t).

o (cid:264)(cid:1243)t bi(cid:1217)n: Th(cid:1267)c hi(cid:1225)n (cid:255)(cid:1243)t bi(cid:1217)n các cá th(cid:1221)

trong P’(t), ta (cid:255)(cid:1132)(cid:1253)c t(cid:1199)p R(t) (theo ph(cid:1132)(cid:1130)ng

pháp (cid:255)(cid:1132)(cid:1253)c trình bày trong 2.2.3.1.3).

o Ch(cid:1231)n l(cid:1231)c: S(cid:1201)p x(cid:1217)p theo (cid:255)(cid:1243) thích nghi gi(cid:1189)m

(cid:71)(cid:1193)n và ch(cid:1231)n các cá th(cid:1221) t(cid:1235)t nh(cid:1191)t t(cid:1261) t(cid:1199)p P(t- 1) ¨ R(t) (nh(cid:1132) trong 2.2.3.1.4) (cid:255)(cid:1221) Q(t) ¨

có P(t).

(cid:37)(cid:585)(cid:859)c 3:

(cid:49)(cid:1217)u (t < (cid:54)(cid:856) th(cid:838) h(cid:846) ti(cid:838)n hóa) Thì l(cid:1209)p l(cid:1187)i

(cid:69)(cid:1132)(cid:1245)c 2, Ng(cid:1132)(cid:1253)c l(cid:1187)i k(cid:1217)t thúc và th(cid:1221) hi(cid:1225)n theo cách

• 2/3 khuôn m(cid:1209)t (cid:255)(cid:1132)(cid:1253)c th(cid:1221) hi(cid:1225)n là nh(cid:1265)ng

khuôn m(cid:1209)t t(cid:1235)t nh(cid:1191)t trong P(t) sau ti(cid:1217)n

• 1/3 (cid:255)(cid:1132)(cid:1253)c phát sinh ng(cid:1197)u nhiên nh(cid:1203)m giúp

hóa.

ng(cid:1132)(cid:1247)i s(cid:1263) d(cid:1255)ng có thêm nhi(cid:1219)u l(cid:1267)a ch(cid:1231)n.

2.2.4 Tìm ki(cid:855)m trong c(cid:767) s(cid:887) d(cid:903) li(cid:863)u (cid:827)nh chân dung

(cid:39)(cid:1269)a vào khuôn m(cid:1211)t phác th(cid:1191)o có (cid:255)(cid:1133)(cid:1255)c, ta s(cid:1217) tìm các (cid:1191)nh chân dung

(cid:87)(cid:1133)(cid:1131)ng (cid:1261)ng trong c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u (cid:1191)nh chân dung. C(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u này g(cid:1239)m các

vector (cid:255)(cid:1211)c tr(cid:1133)ng (cid:255)(cid:1133)(cid:1255)c mã hóa t(cid:1263)(cid:3)(cid:1191)nh chân dung thông th(cid:1133)(cid:1249)ng, (cid:1191)nh (cid:255)(cid:1133)(cid:1255)c mã

hoá có các thu(cid:1245)c tính nh(cid:1133) chân dung phác th(cid:1191)o. Trong bài toán này, c(cid:1131) s(cid:1251) d(cid:1267)

- 38 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

li(cid:1227)u (cid:1191)nh có th(cid:1223) là m(cid:1245)t t(cid:1201)p (cid:1191)nh các t(cid:1245)i ph(cid:1189)m tr(cid:1133)(cid:1247)c (cid:255)ây; nhà ch(cid:1261)c trách mu(cid:1237)n

qu(cid:1191)n lí và theo dõi các (cid:255)(cid:1237)i t(cid:1133)(cid:1255)ng này.

Ph(cid:1195)n này trình bày vi(cid:1227)c xây d(cid:1269)ng c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u; c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u (cid:1191)nh này

(cid:255)óng m(cid:1245)t vai trò r(cid:1193)t quan tr(cid:1233)ng trong quá trình ph(cid:1257)c h(cid:1239)i chân dung vì nó giúp

ánh x(cid:1189) t(cid:1263) khuôn m(cid:1211)t phác th(cid:1191)o sang m(cid:1245)t (ho(cid:1211)c nhi(cid:1221)u) (cid:1191)nh chân dung thông

th(cid:1133)(cid:1249)ng.

Hình 2-1 S(cid:751)(cid:3)(cid:255)(cid:858) t(cid:860)ng quát c(cid:878)a bài toán. Trong (cid:255)ó, mã

hóa (cid:810)nh chân dung là m(cid:864)t trong hai ti(cid:838)n trình quan

tr(cid:852)ng.

2.2.4.1 Xây d(cid:1269)ng CSDL (cid:1191)nh chân dung

Xây d(cid:1269)ng c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u (cid:1191)nh g(cid:1239)m các b(cid:1133)(cid:1247)c sau:

- 39 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

1) Mã hoá (cid:1191)nh: Xây d(cid:1269)ng công c(cid:1257)(cid:3)(cid:255)(cid:1223) th(cid:1269)c hi(cid:1227)n vi(cid:1227)c mã hoá (cid:1191)nh chân

dung thành (cid:1191)nh phác th(cid:1191)o. T(cid:1263) m(cid:1243)i (cid:1191)nh chân dung ta ph(cid:1191)i rút trích ra

(cid:255)(cid:1133)(cid:1255)c các (cid:255)(cid:1211)c tr(cid:1133)ng và t(cid:1201)p h(cid:1255)p l(cid:1189)i thành m(cid:1245)t vect(cid:1131)(cid:3) (cid:255)(cid:1211)c tr(cid:1133)ng cho

(cid:1191)nh v(cid:1263)a mã hóa.

2) (cid:47)(cid:1133)u tr(cid:1267): L(cid:1133)u tr(cid:1267) vect(cid:1131)(cid:3)(cid:255)(cid:1211)c tr(cid:1133)ng c(cid:1259)a (cid:1191)nh v(cid:1263)a mã hóa xu(cid:1237)ng c(cid:1131) s(cid:1251)

(cid:71)(cid:1267) li(cid:1227)u (cid:255)(cid:1223) ph(cid:1257)c v(cid:1257) cho thao tác tìm ki(cid:1219)m.

(cid:48)(cid:1257)c này s(cid:1217) trình bày vi(cid:1227)c xây d(cid:1269)ng công c(cid:1257) bán t(cid:1269)(cid:3)(cid:255)(cid:1245)ng (cid:255)(cid:1223) th(cid:1269)c hi(cid:1227)n

mã hoá (cid:1191)nh:(cid:3)(cid:1190)nh chân dung (cid:255)(cid:1133)(cid:1255)c hi(cid:1227)n lên màn hình, ng(cid:1133)(cid:1249)i dùng s(cid:1217) xác (cid:255)(cid:1231)nh

(cid:80)(cid:1245)t s(cid:1237)(cid:3)(cid:255)(cid:76)(cid:1223)m c(cid:1259)a các b(cid:1245) ph(cid:1201)n trên khuôn m(cid:1211)t hay miêu t(cid:1191) d(cid:1269)a trên các m(cid:1199)u có

(cid:86)(cid:1209)n, t(cid:1263)(cid:3)(cid:255)ó ta s(cid:1217) mã hóa thành các giá tr(cid:1231) trong kho(cid:1191)ng {0,..,15}

Công th(cid:1261)c chuy(cid:1223)n (cid:255)(cid:1241)i:

(cid:264)(cid:1133)a ra m(cid:1245)t s(cid:1237) khái

ni(cid:1227)m:

1. Má ph(cid:1227)

(cid:37)(cid:1245) Stt (cid:264)(cid:1211)c tr(cid:1133)ng Cách mã hóa Công th(cid:1261)c ph(cid:1201)n

Khuôn

2. Má h(cid:1131)i ph(cid:1227)

1. Má

Miêu t(cid:1191)

1. (cid:80)(cid:1211)t

3. Má bình th(cid:1133)(cid:1249)ng

4. Má h(cid:1131)i táp

5. Má táp

- 40 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:264)(cid:1133)a ra m(cid:1245)t s(cid:1237) khái

ni(cid:1227)m sau:

1. C(cid:1205)m ng(cid:1203)n

2. (cid:38)(cid:1205)m

Miêu t(cid:1191)

2. C(cid:1205)m v(cid:1263)a

3. C(cid:1205)m dài

1. Tính chi(cid:1221)u cao c(cid:1259)a

Xác (cid:255)(cid:1231)nh 4 (cid:255)(cid:76)(cid:1223)m:

khuôn m(cid:1211)t:

1. (cid:264)(cid:76)(cid:1223)m cao nh(cid:1193)t

H 1

3. Hình d(cid:1189)ng khuôn

2. (cid:264)(cid:76)(cid:1223)m ph(cid:1191)i nh(cid:1193)t

(cid:80)(cid:1211)t

2. Tính chi(cid:1221)u r(cid:1245)ng c(cid:1259)a

3. (cid:264)(cid:76)(cid:1223)m d(cid:1133)(cid:1247)i cùng

khuôn m(cid:1211)t:

(T(cid:849) l(cid:847) gi(cid:887)a chi(cid:841)u cao

4. (cid:264)(cid:76)(cid:1223)m trái nh(cid:1193)t

và chi(cid:841)u r(cid:865)ng c(cid:879)a

= xW H

khuôn m(cid:831)t)

3. (cid:39)(cid:1189)ng khuôn m(cid:1211)t:

HS =

H H W H

Xác (cid:255)(cid:1231)nh các (cid:255)(cid:76)(cid:1223)m:

B1: (cid:264)(cid:76)(cid:1223)m (cid:255)(cid:1195)u bên

trái c(cid:1259)a lông mày

4. Chi(cid:1221)u dài

trái.

2. Lông

(T(cid:849) l(cid:847) gi(cid:887)a chi(cid:841)u dài

B 1

B 3

B2: (cid:264)(cid:76)(cid:1223)m cao nh(cid:1193)t

mày

lông mày v(cid:867)i chi(cid:841)u

(cid:70)(cid:1259)a lông mày trái.

(cid:85)(cid:865)ng khuôn m(cid:831)t)

B3: (cid:264)(cid:76)(cid:1223)m (cid:255)(cid:1195)u bên

ph(cid:1191)i c(cid:1259)a lôngmày

trái.

- 41 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

5. (cid:264)(cid:1245)(cid:3)(cid:255)(cid:1201)m

Ch(cid:1233)n t(cid:1263) m(cid:1199)u

6. (cid:57)(cid:1231) trí

(T(cid:849) l(cid:847) kho(cid:811)ng cách

EBP

(cid:255)(cid:849)nh (cid:255)(cid:815)u (cid:255)(cid:839)n lông

mày v(cid:867)i chi(cid:841)u cao

khuôn m(cid:831)t)

max

min

EBH

7. Chi(cid:1221)u cao

(Kho(cid:811)ng cách gi(cid:887)a

(cid:255)(cid:76)(cid:843)m th(cid:813)p nh(cid:813)t và cao

yMin

(

)

min

B 3

B 2

B 1

nh(cid:813)t c(cid:879)a lông mày t(cid:849)

(cid:79)(cid:847) v(cid:867)i chi(cid:841)u cao c(cid:879)a

khuôn m(cid:831)t)

yMax

(

)

max

B 3

B 1

Trong (cid:255)ó

- 42 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

8. Hình d(cid:1189)ng

Ch(cid:1233)n t(cid:1263) m(cid:1199)u

Tính ytb c(cid:1259)a m(cid:1203)t:

9. (cid:57)(cid:1231) trí

E 1

E 3

(V(cid:851) trí c(cid:879)a m(cid:823)t theo

ph(cid:753)(cid:751)ng th(cid:827)ng (cid:255)(cid:881)ng.

3. (cid:48)(cid:1203)t

(cid:55)(cid:849) l(cid:847) gi(cid:887)a kho(cid:811)ng

(cid:57)(cid:1231) trí m(cid:1203)t:

cách t(cid:883)(cid:3)(cid:255)(cid:849)nh (cid:255)(cid:815)u (cid:255)(cid:839)n

(cid:80)(cid:823)t v(cid:867)i chi(cid:841)u cao

H 1

khuôn m(cid:831)t)

Xác (cid:255)(cid:1231)nh các (cid:255)(cid:76)(cid:1223)m: E1: (cid:264)(cid:76)(cid:1223)m cao nh(cid:1193)t (cid:70)(cid:1259)a m(cid:1203)t trái. E2: (cid:264)(cid:76)(cid:1223)m ph(cid:1191)i nh(cid:1193)t (cid:70)(cid:1259)a m(cid:1203)t trái. E3; (cid:264)(cid:76)(cid:1223)m d(cid:1133)(cid:1247)i cùng c(cid:1259)a m(cid:1203)t trái. E4: (cid:264)(cid:76)(cid:1223)m trái nh(cid:1193)t (cid:70)(cid:1259)a m(cid:1203)t trái. E5: (cid:264)(cid:76)(cid:1223)m trái nh(cid:1193)t (cid:70)(cid:1259)a m(cid:1203)t ph(cid:1191)i.

10. Kích th(cid:1133)(cid:1247)c

((cid:55)(cid:849) l(cid:847) gi(cid:887)a chi(cid:841)u cao,

(cid:85)(cid:865)ng c(cid:879)a m(cid:823)t so v(cid:867)i

H H

W W

chi(cid:841)u cao, r(cid:865)ng c(cid:879)a

khuôn m(cid:831)t)

- 43 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

1. Chi(cid:1221)u cao c(cid:1259)a m(cid:1203)t

2. Chi(cid:1221)u r(cid:1245)ng c(cid:1259)a m(cid:1203)t

11. Kho(cid:1191)ng cách gi(cid:1267)a

= xW E

hai m(cid:1203)t

Kho(cid:1191)ng cách

(T(cid:849) l(cid:847) kho(cid:811)ng cách

gi(cid:1267)a hai m(cid:1203)t (Eye

gi(cid:887)a hai m(cid:823)t v(cid:867)i chi(cid:841)u

Distance)

(cid:85)(cid:865)ng khuôn m(cid:831)t)

W H

12. (cid:55)(cid:1229) l(cid:1227) cao/r(cid:1245)ng

HWR =

((cid:55)(cid:849) l(cid:847) gi(cid:887)a hai chi(cid:841)u

H E W E

cao và r(cid:865)ng c(cid:879)a m(cid:823)t)

13. Kích th(cid:1133)(cid:1247)c (cid:255)(cid:1239)ng

(cid:54)(cid:1265) d(cid:1257)ng m(cid:1245)t hình

(cid:87)(cid:1265)

tròn có bán kính rp

thay (cid:255)(cid:1241)i (cid:255)(cid:1133)(cid:1255)c sao

(T(cid:849) l(cid:847) gi(cid:887)a bán kính

r P H

r P W H

cho kh(cid:1247)p v(cid:1247)i (cid:255)(cid:1239)ng

(cid:255)(cid:859)ng t(cid:883) so v(cid:867)i kích

(cid:87)(cid:1265)

th(cid:753)(cid:867)c c(cid:879)a khuôn m(cid:831)t)

Xác (cid:255)(cid:1231)nh 3 (cid:255)(cid:76)(cid:1223)m:

1. (cid:264)(cid:76)(cid:1223)m trái nh(cid:1193)t

4. (cid:48)(cid:458)i

14. Chi(cid:1221)u dài

tb H

2. (cid:264)(cid:76)(cid:1223)m th(cid:1193)p nh(cid:1193)t

((cid:55)(cid:849) l(cid:847) chi(cid:841)u dài c(cid:879)a

(cid:80)(cid:458)i so v(cid:867)i khuôn m(cid:831)t)

- 44 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

3. (cid:264)(cid:76)(cid:1223)m ph(cid:1191)i nh(cid:1193)t

15. Chi(cid:1221)u r(cid:1245)ng

(T(cid:849) l(cid:847) gi(cid:887)a chi(cid:841)u r(cid:865)ng

1Nx W

(cid:70)(cid:879)a m(cid:458)i so v(cid:867)i chi(cid:841)u

(cid:85)(cid:865)ng khuôn m(cid:831)t)

16. Hình d(cid:1189)ng

Ch(cid:1233)n t(cid:1263) m(cid:1199)u

Xác (cid:255)(cid:1231)nh các (cid:255)(cid:76)(cid:1223)m:

M1: (cid:264)(cid:76)(cid:1223)m cao nh(cid:1193)t

(cid:70)(cid:1259)a mi(cid:1227)ng.

M2: (cid:264)(cid:76)(cid:1223)m ph(cid:1191)i nh(cid:1193)t

(cid:70)(cid:1259)a mi(cid:1227)ng.

5. Mi(cid:1227)ng

17. Chi(cid:1221)u r(cid:1245)ng

M3: (cid:264)(cid:76)(cid:1223)m d(cid:1133)(cid:1247)i

W H

cùng c(cid:1259)a mi(cid:1227)ng.

M4: (cid:264)(cid:76)(cid:1223)m trái nh(cid:1193)t

(cid:70)(cid:1259)a mi(cid:1227)ng

M5: (cid:264)(cid:76)(cid:1223)m chính

gi(cid:1267)a c(cid:1259)a mi(cid:1227)ng

- 45 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

18. (cid:57)(cid:1231) trí

((cid:57)(cid:851) trí theo ph(cid:753)(cid:751)ng

th(cid:827)ng (cid:255)(cid:881)ng. T(cid:849) l(cid:847) gi(cid:887)a

kho(cid:811)ng cách (cid:255)(cid:849)nh (cid:255)(cid:815)u

(cid:255)(cid:839)n mi(cid:847)ng v(cid:867)i chi(cid:841)u

cao khuôn m(cid:831)t)

19. (cid:264)(cid:1245) dày môi trên

MTUL

MTLL

20. (cid:264)(cid:1245) dày môi d(cid:1133)(cid:1247)i

(cid:57)(cid:1247)i các thu(cid:1245)c tính d(cid:1269)a trên (cid:255)(cid:1245)(cid:3)(cid:255)o kho(cid:1191)ng cách, ta xác (cid:255)(cid:1231)nh giá tr(cid:1231) l(cid:1247)n

nh(cid:1193)t (Max) và nh(cid:1235) nh(cid:1193)t (Min) t(cid:1133)(cid:1131)ng (cid:1261)ng. Th(cid:1269)c hi(cid:1227)n ánh x(cid:1189) tuy(cid:1219)n tính t(cid:1263)

mi(cid:1221)n giá tr(cid:1231) [Min, Max] vào {0,...,15}.

2.2.4.2 (cid:55)(cid:1241) ch(cid:1261)c c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u (cid:1191)nh chân dung

Khi (cid:255)ã có (cid:255)(cid:1133)(cid:1255)c vector (cid:255)(cid:1211)c tr(cid:1133)ng c(cid:1259)a khuôn m(cid:1211)t, v(cid:1193)n (cid:255)(cid:1221) ti(cid:1219)p theo là l(cid:1133)u

tr(cid:1267) vector này vào c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u. M(cid:1245)t ph(cid:1133)(cid:1131)ng pháp (cid:255)(cid:1131)n gi(cid:1191)n là (cid:255)(cid:1237)i v(cid:1247)i m(cid:1243)i

(cid:1191)nh chân dung, ta l(cid:1133)u duy nh(cid:1193)t vector v(cid:1263)a mã hóa. Tuy nhiên do công c(cid:1257)(cid:3)(cid:255)(cid:1223)

mã hóa (cid:1191)nh là bán t(cid:1269)(cid:3)(cid:255)(cid:1245)ng nên có nhi(cid:1221)u sai s(cid:1237), ph(cid:1257) thu(cid:1245)c vào ch(cid:1259) quan c(cid:1259)a

ng(cid:1133)(cid:1249)i mã hóa; ví d(cid:1257) nh(cid:1133) hai ng(cid:1133)(cid:1249)i khác nhau cùng mã hóa m(cid:1245)t (cid:1191)nh k(cid:1219)t qu(cid:1191)

mã hóa (th(cid:1133)(cid:1249)ng) là khác nhau, hay ngay c(cid:1191) m(cid:1245)t ng(cid:1133)(cid:1249)i t(cid:1189)i các th(cid:1249)i (cid:255)(cid:76)(cid:1223)m khác

nhau khi mã hóa cùng m(cid:1245)t t(cid:1193)m (cid:1191)nh thì cách mã hóa (ch(cid:1193)m (cid:255)(cid:76)(cid:1223)m, ch(cid:1233)n

(cid:80)(cid:1199)u…) c(cid:458)ng không gi(cid:1237)ng nhau.

Cách gi(cid:1191)i quy(cid:1219)t là ta s(cid:1265) d(cid:1257)ng 2 b(cid:1191)ng d(cid:1267) li(cid:1227)u có c(cid:1193)u trúc gi(cid:1237)ng nhau,

gi(cid:1191) s(cid:1265) g(cid:1233)i 2 b(cid:1191)ng này là A và B. M(cid:1243)i l(cid:1195)n mã hóa m(cid:1245)t (cid:1191)nh ta l(cid:1133)u vào b(cid:1191)ng A.

Nh(cid:1133) v(cid:1201)y trong b(cid:1191)ng A m(cid:1245)t (cid:1191)nh có th(cid:1223) có nhi(cid:1221)u vector (cid:255)(cid:1211)c tr(cid:1133)ng. Ng(cid:1133)(cid:1255)c l(cid:1189)i,

- 46 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

trong b(cid:1191)ng B m(cid:1243)i (cid:1191)nh ch(cid:1229) có duy nh(cid:1193)t m(cid:1245)t vector (cid:255)(cid:1211)c tr(cid:1133)ng và vector (cid:255)(cid:1211)c

tr(cid:1133)ng này là trung bình c(cid:1245)ng c(cid:1259)a t(cid:1193)t c(cid:1191) các vector (cid:255)(cid:1211)c tr(cid:1133)ng c(cid:1259)a (cid:1191)nh t(cid:1133)(cid:1131)ng

(cid:1261)ng trong b(cid:1191)ng A. Vector trong b(cid:1191)ng B c(cid:458)ng chính là vector mà ta s(cid:1217) s(cid:1265) d(cid:1257)ng

(cid:255)(cid:1223) so kh(cid:1247)p khi ti(cid:1219)n hành thao tác tìm ki(cid:1219)m (cid:1191)nh chân dung.

(cid:37)(cid:1191)ng A:

L(cid:814)n

(cid:810)NH (cid:264)(cid:831)c tr(cid:753)ng 1 (cid:264)(cid:831)c tr(cid:753)ng 2 (cid:264)(cid:831)c tr(cid:753)ng n (cid:171) mã

hóa

1. X x1n x11 x1i x12

… ... … ... … …

p. X xpn xp1 xpi xp2

1. Y y1n y11 y1i y12

… … … … … …

q. Y yqn yq1 yqi yq2

… … … … … …

- 47 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:37)(cid:1191)ng B:

(cid:810)NH (cid:264)(cid:831)c tr(cid:753)ng 1 (cid:264)(cid:831)c tr(cid:753)ng 2 (cid:264)(cid:831)c tr(cid:753)ng n (cid:171)

jix

jnx

1 p

X (cid:229) (cid:229) (cid:229) (cid:229)

jiy

jny

1 q

Y (cid:229) (cid:229) (cid:229) (cid:229)

… … … … …

Vì c(cid:1193)u trúc c(cid:1259)a hai b(cid:1191)ng t(cid:1133)(cid:1131)ng (cid:255)(cid:1237)i gi(cid:1237)ng nhau nên có th(cid:1223) g(cid:1245)p chung c(cid:1191)

hai b(cid:1191)ng vào làm m(cid:1245)t (trong b(cid:1191)ng chung ch(cid:1229) c(cid:1195)n thêm m(cid:1245)t tr(cid:1133)(cid:1249)ng cho bi(cid:1219)t là

vector trung bình hay vector mã hóa). Tuy nhiên chúng tôi ch(cid:1233)n t(cid:1241) ch(cid:1261)c theo

hai b(cid:1191)ng d(cid:1267) li(cid:1227)u vì cách t(cid:1241) ch(cid:1261)c này (cid:255)(cid:1131)n gi(cid:1191)n, rõ ràng, thu(cid:1201)n l(cid:1255)i cho tính

toán; vi(cid:1227)c truy v(cid:1193)n tìm ki(cid:1219)m c(cid:458)ng (cid:255)(cid:1133)(cid:1255)c th(cid:1269)c hi(cid:1227)n d(cid:1225) dàng và nhanh chóng.

2.2.4.3 Tìm ki(cid:1219)m

(cid:264)(cid:1223) ph(cid:1257)c h(cid:1239)i (cid:1191)nh chân dung t(cid:1263) quan sát, ta có các b(cid:1133)(cid:1247)c sau:

(cid:37)(cid:585)(cid:859)c 1: Mô t(cid:1191) chân dung c(cid:1195)n tìm ki(cid:1219)m trên các khuôn m(cid:1211)t phác th(cid:1191)o,

(cid:255)(cid:1195)u ra c(cid:1259)a thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n. K(cid:1219)t qu(cid:1191) c(cid:1259)a b(cid:1133)(cid:1247)c này là m(cid:1245)t vector

(cid:255)(cid:1211)c tr(cid:1133)ng c(cid:1259)a khuôn m(cid:1211)t phác th(cid:1191)o mà ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ch(cid:1233)n (t(cid:1261)c là

khuôn m(cid:1211)t “h(cid:1255)p” v(cid:1247)i ý c(cid:1259)a ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng nh(cid:1193)t). Thu(cid:1201)t gi(cid:1191)i di

truy(cid:1221)n áp d(cid:1257)ng cho b(cid:1133)(cid:1247)c này (cid:255)ã (cid:255)(cid:1133)(cid:1255)c trình bày (cid:1251) nh(cid:1267)ng ph(cid:1195)n tr(cid:1133)(cid:1247)c,

trong m(cid:1257)c 2.2.

(cid:37)(cid:585)(cid:859)c 2: (cid:55)(cid:1263) vector (cid:255)(cid:1211)c tr(cid:1133)ng có (cid:255)(cid:1133)(cid:1255)c, ti(cid:1219)n hành tìm ki(cid:1219)m (cid:1191)nh chân

dung “gi(cid:1237)ng” v(cid:1247)i khuôn m(cid:1211)t phác th(cid:1191)o mà vector (cid:255)(cid:1211)c tr(cid:1133)ng này (cid:255)(cid:1189)i

di(cid:1227)n nh(cid:1193)t. Các (cid:1191)nh chân dung (cid:255)ã (cid:255)(cid:1133)(cid:1255)c mã hóa thành các vector m(cid:1199)u

- 48 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:79)(cid:1133)u trong c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u nên thao tác tìm ki(cid:1219)m (cid:255)(cid:1133)(cid:1255)c th(cid:1269)c hi(cid:1227)n b(cid:1205)ng

cách so kh(cid:1247)p vector (cid:255)(cid:1211)c tr(cid:1133)ng có (cid:255)(cid:1133)(cid:1255)c v(cid:1247)i các vector trong c(cid:1131) s(cid:1251)

(cid:71)(cid:1267) li(cid:1227)u. Thao tác so kh(cid:1247)p d(cid:1269)a vào (cid:255)(cid:1245)(cid:3) (cid:255)o kho(cid:1191)ng cách Euclide và

(cid:1191)nh (cid:255)(cid:1133)(cid:1255)c ch(cid:1233)n là (cid:1191)nh có (cid:255)(cid:1245)(cid:3)(cid:255)o kho(cid:1191)ng cách t(cid:1247)i vector (cid:255)(cid:1211)c tr(cid:1133)ng nh(cid:1235)

nh(cid:1193)t. Sau khi so kh(cid:1247)p, có th(cid:1223) tìm th(cid:1193)y nhi(cid:1221)u (cid:1191)nh k(cid:1219)t qu(cid:1191) khác nhau

do có cùng kho(cid:1191)ng cách nh(cid:1235) nh(cid:1193)t. Có (cid:255)(cid:1133)(cid:1255)c k(cid:1219)t qu(cid:1191), ta th(cid:1223) hi(cid:1227)n (cid:1191)nh

tìm (cid:255)(cid:1133)(cid:1255)c cho ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ki(cid:1223)m tra, n(cid:1219)u không ph(cid:1191)i là (cid:1191)nh c(cid:1195)n

tìm, ta có th(cid:1223) ti(cid:1219)n hành l(cid:1189)i t(cid:1263) (cid:69)(cid:1133)(cid:1247)c 1.

(cid:39)(cid:1133)(cid:1247)i (cid:255)ây là thu(cid:1201)t gi(cid:1191)i c(cid:1259)a thao tác tìm ki(cid:1219)m (cid:1251) b(cid:1133)(cid:1247)c 2. Thu(cid:1201)t gi(cid:1191)i này

tìm k (cid:1191)nh chân dung theo ý ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng, tuy tìm k (cid:1191)nh nh(cid:1133)ng n(cid:1219)u có nhi(cid:1221)u

(cid:75)(cid:1131)n k (cid:1191)nh có cùng kho(cid:1191)ng cách g(cid:1195)n nh(cid:1193)t (ví d(cid:1257) t>k), thu(cid:1201)t gi(cid:1191)i s(cid:1217) tr(cid:1191) v(cid:1221) t

(cid:1191)nh:

(cid:264)(cid:1195)u vào: Vector (cid:255)(cid:1211)c tr(cid:1133)ng c(cid:1259)a khuôn m(cid:1211)t phác th(cid:1191)o: F(x1,…,xm) (xi là

giá tr(cid:1231) các (cid:255)(cid:1211)c tr(cid:1133)ng, m là s(cid:1237)(cid:3)(cid:255)(cid:1211)c tr(cid:1133)ng), s(cid:1237) khuôn m(cid:1211)t mu(cid:1237)n tìm k.

(cid:264)(cid:1195)u ra: Các (cid:1191)nh chân dung c(cid:1195)n tìm, l(cid:1133)u trong m(cid:1191)ng A.

o (cid:48)(cid:1249) CSDL

o (cid:48)(cid:1249) b(cid:1189)ng B

o (cid:264)(cid:1235)i v(cid:1245)i m(cid:1241)i Record R˛ B, l(cid:1209)p:

• (cid:49)(cid:1217)u (A ch(cid:1132)a có ph(cid:1193)n t(cid:1263))

§ Thêm R vào A

• Ng(cid:1132)(cid:1253)c l(cid:1187)i

§ (cid:49)(cid:1217)u (S(cid:1235) ph(cid:1193)n t(cid:1263) c(cid:1257)a A < k)

• Thêm R vào A mà v(cid:1197)n (cid:255)(cid:1189)m

- 49 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:69)(cid:1189)o th(cid:1259) t(cid:1267) (th(cid:1259) t(cid:1267) s(cid:1201)p

(cid:91)(cid:1217)p trong A: Record nào

có kho(cid:1189)ng cách

(Record.vector,F) nh(cid:1233)

(cid:75)(cid:1130)n thì (cid:255)(cid:1259)ng tr(cid:1132)(cid:1245)c)

§ Ng(cid:1132)(cid:1253)c l(cid:1187)i N(cid:1217)u (cid:11)(cid:264)(cid:1132)a R vào A (cid:255)(cid:1132)(cid:1253)c)

{R(cid:3)(cid:255)(cid:1132)a (cid:255)(cid:1132)(cid:1253)c vào A khi trong A t(cid:1237)n

(cid:87)(cid:1187)i m(cid:1243)t Record r sao cho kho(cid:1189)ng

cách (r.vector,F(cid:12)(cid:149) kho(cid:1189)ng cách

(R.vector,F) }

• Thêm R vào A mà v(cid:1197)n (cid:255)(cid:1189)m

(cid:69)(cid:1189)o th(cid:1259) t(cid:1267)

(cid:75)(cid:1253)p cùng kho(cid:1189)ng cách nh(cid:1233)

nh(cid:1191)t}

• Xuly(A,R,k) {X(cid:1263) lý tr(cid:1132)(cid:1247)ng

o (cid:43)(cid:1217)t l(cid:1209)p

o (cid:264)óng b(cid:1189)ng B

o (cid:264)óng CSDL

Th(cid:1257) t(cid:1255)c Xuly:

(cid:264)(cid:1193)u vào: M(cid:1189)ng A, vector F, s(cid:1235)(cid:3)(cid:1189)nh k

Thu(cid:1199)t gi(cid:1189)i:

o (cid:264)(cid:1235)i v(cid:1245)i m(cid:1241)i Record r trong A

• vi = A[i].vector {i: b(cid:1132)(cid:1245)c l(cid:1209)p}

- 50 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

• vk = A[k].vector

• (cid:49)(cid:1217)u kho(cid:1189)ng cách (vi,F) != kho(cid:1189)ng cách

(vk,F)

§ Lo(cid:1187)i kh(cid:1233)i A t(cid:1261) i (cid:255)(cid:1217)n cu(cid:1235)i

(cid:80)(cid:1189)ng

o (cid:43)(cid:1217)t l(cid:1209)p

- 51 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

CCCHHH(cid:1131)(cid:1131)(cid:1131)(cid:1129)(cid:1129)(cid:1129)NNNGGG 333

HHH(cid:1224)(cid:1224)(cid:1224) TTTHHH(cid:1234)(cid:1234)(cid:1234)NNNGGG HHH(cid:1240)(cid:1240)(cid:1240) TTTRRR(cid:1252)(cid:1252)(cid:1252) TTTÌÌÌMMM KKKIII(cid:1216)(cid:1216)(cid:1216)MMM

(cid:1188)(cid:1188)(cid:1188)NNNHHH CCCHHHÂÂÂNNN DDDUUUNNNGGG DDD(cid:1266)(cid:1266)(cid:1266)AAA TTTRRRÊÊÊNNN MMMÔÔÔ

TTT(cid:1188)(cid:1188)(cid:1188)

3.1 S(cid:766)(cid:3)(cid:264)(cid:874) H(cid:862) TH(cid:872)NG

Hình 3-1 Hai mô(cid:255)un chính c(cid:878)a h(cid:846) th(cid:856)ng

- 52 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:43)(cid:1227) th(cid:1237)ng g(cid:1239)m 2 mô(cid:255)un chính:

1. Mô(cid:255)un Mã hóa (cid:1191)nh: Mã hóa (cid:1191)nh chân dung thành vector (cid:255)(cid:1211)c

tr(cid:1133)ng và l(cid:1133)u vào c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u. Do có nhi(cid:1221)u sai s(cid:1237) nên (cid:255)(cid:1237)i v(cid:1247)i m(cid:1245)t

(cid:1191)nh có th(cid:1223) th(cid:1269)c hi(cid:1227)n mã hóa nhi(cid:1221)u l(cid:1195)n. (cid:264)(cid:1195)u vào c(cid:1259)a mô(cid:255)un này là

(cid:80)(cid:1245)t (cid:1191)nh chân dung (ví d(cid:1257)(cid:3)(cid:1191)nh chân dung t(cid:1245)i ph(cid:1189)m), (cid:255)(cid:1195)u ra là vector

(cid:255)(cid:1211)c tr(cid:1133)ng c(cid:1259)a (cid:1191)nh.

2. Mo(cid:255)un Ph(cid:1257)c h(cid:1239)i chân dung: M(cid:1257)c (cid:255)ích c(cid:1259)a mô(cid:255)un này là ph(cid:1257)c h(cid:1239)i

(cid:79)(cid:1189)i chân dung c(cid:1259)a (cid:255)(cid:1237)i t(cid:1133)(cid:1255)ng (t(cid:1245)i ph(cid:1189)m) thông qua mô t(cid:1191) c(cid:1259)a ng(cid:1133)(cid:1249)i

(cid:86)(cid:1265) d(cid:1257)ng (nhân ch(cid:1261)ng) trên các khuôn m(cid:1211)t phác th(cid:1191)o. Ho(cid:1189)t (cid:255)(cid:1245)ng c(cid:1259)a

mô(cid:255)un này nh(cid:1133) sau: h(cid:1227) th(cid:1237)ng gi(cid:1247)i thi(cid:1227)u các khuôn m(cid:1211)t phác th(cid:1191)o,

(nhi(cid:1221)u) ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng tìm trong các khuôn m(cid:1211)t này khuôn m(cid:1211)t nào

gi(cid:1237)ng v(cid:1247)i (cid:255)(cid:1237)i t(cid:1133)(cid:1255)ng nh(cid:1193)t, nhi(cid:1221)u ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng khác nhau có th(cid:1223)

ch(cid:1233)n nhi(cid:1221)u khuôn m(cid:1211)t khác nhau; t(cid:1263) nh(cid:1267)ng khuôn m(cid:1211)t (cid:255)(cid:1133)(cid:1255)c ch(cid:1233)n,

thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n th(cid:1269)c hi(cid:1227)n ti(cid:1219)n hóa trên qu(cid:1195)n th(cid:1223) khuôn m(cid:1211)t hi(cid:1227)n

hành v(cid:1247)i (cid:255)(cid:1245) thích nghi ph(cid:1257) thu(cid:1245)c vào các khuôn m(cid:1211)t (cid:255)(cid:1133)(cid:1255)c ch(cid:1233)n

(thu(cid:1201)t gi(cid:1191)i (cid:255)(cid:1223) ti(cid:1219)n hóa (cid:255)ã (cid:255)(cid:1133)(cid:1255)c trình bày trong ch(cid:1133)(cid:1131)ng 2); sau khi

ti(cid:1219)n hóa, các khuôn m(cid:1211)t t(cid:1237)t nh(cid:1193)t (có (cid:255)(cid:1245) thích nghi cao nh(cid:1193)t) (cid:255)(cid:1133)(cid:1255)c

th(cid:1223) hi(cid:1227)n cho ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ch(cid:1233)n l(cid:1189)i, các thao tác này (cid:255)(cid:1133)(cid:1255)c l(cid:1211)p l(cid:1189)i

cho (cid:255)(cid:1219)n khi các ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ch(cid:1233)n (cid:255)(cid:1133)(cid:1255)c khuôn m(cid:1211)t chung nh(cid:1193)t; có

(cid:255)(cid:1133)(cid:1255)c khuôn m(cid:1211)t phác th(cid:1191)o, h(cid:1227) th(cid:1237)ng tìm trong c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u vect(cid:1131)

(cid:255)(cid:1211)c tr(cid:1133)ng ((cid:255)(cid:1133)(cid:1255)c t(cid:1189)o ra b(cid:1251)i mô(cid:255)un mã hóa) (cid:1191)nh chân dung g(cid:1195)n v(cid:1247)i

khuôn m(cid:1211)t phác th(cid:1191)o nh(cid:1193)t. (cid:264)(cid:1195)u vào c(cid:1259)a mô(cid:255)un này là nh(cid:1267)ng mô t(cid:811)

(cid:70)(cid:1259)a ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng, còn (cid:255)(cid:1195)u ra là (cid:1191)nh chân dung “gi(cid:1237)ng” v(cid:1247)i mô t(cid:811)

(cid:70)(cid:1259)a nhi(cid:1221)u ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng nh(cid:1193)t.

Ch(cid:1133)(cid:1131)ng trình Demo cho h(cid:1227) th(cid:1237)ng (cid:255)(cid:1133)(cid:1255)c cài (cid:255)(cid:1211)t b(cid:1205)ng ngôn ng(cid:1267) C# trên

môi tr(cid:1133)(cid:1249)ng Visual Studio .NET 2003, c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u Access 2000 g(cid:1239)m 300

- 53 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

khuôn m(cid:1211)t (cid:255)(cid:1133)(cid:1255)c mã hóa. (cid:264)(cid:1223) thi hành ch(cid:1133)(cid:1131)ng trình c(cid:1195)n ph(cid:1191)i cài (cid:255)(cid:1211)t b(cid:1245) .NET

Framework phiên b(cid:1191)n 1.1.

Ch(cid:1133)(cid:1131)ng này trình bày v(cid:1221) cài (cid:255)(cid:1211)t c(cid:1257) th(cid:1223) c(cid:1259)a h(cid:1227) th(cid:1237)ng d(cid:1269)a trên lý thuy(cid:1219)t

(cid:255)(cid:1133)(cid:1255)c kh(cid:1191)o sát trong các ch(cid:1133)(cid:1131)ng trên.

3.2 CÁC MÔ(cid:264)UN H(cid:862) TH(cid:872)NG

3.2.1 S(cid:767)(cid:3)(cid:255)(cid:875) màn hình

Hình 3-2 S(cid:751)(cid:3)(cid:255)(cid:858) màn hình

- 54 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

Màn hình ch(cid:1133)(cid:1131)ng trình:

v Màn hình chính:

Hình 3-3 Màn hình chính c(cid:1259)a ch(cid:1133)(cid:1131)ng trình.

- 55 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

v Màn hình mã hóa (cid:1191)nh:

Hình 3-4 Màn hình mã hóa (cid:810)nh

- 56 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

v Màn hình Ph(cid:1257)c h(cid:1239)i chân dung:

Hình 3-5 Màn hình Ph(cid:876)c h(cid:858)i chân dung

- 57 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

3.2.2 Mô(cid:255)un Mã hóa (cid:827)nh

Hình 3-6 Mô(cid:255)un mã hóa (cid:810)nh

(cid:264)(cid:1195)u vào c(cid:1259)a mô(cid:255)un này là m(cid:1245)t (cid:1191)nh chân dung, (cid:255)(cid:1195)u ra là vector (cid:255)(cid:1211)c

tr(cid:1133)ng c(cid:1259)a (cid:1191)nh. Do có nhi(cid:1221)u sai s(cid:1237) nên (cid:255)(cid:1237)i v(cid:1247)i m(cid:1245)t (cid:1191)nh có th(cid:1223) ph(cid:1191)i th(cid:1269)c hi(cid:1227)n

mã hóa nhi(cid:1221)u l(cid:1195)n.

- 58 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

3.2.3 Mô(cid:255)un Ph(cid:893)c h(cid:875)i chân dung

Hình 3-7 Mô(cid:255)un Ph(cid:876)c h(cid:858)i chân dung

Mô(cid:255)un này g(cid:1239)m 2 ti(cid:1219)n trình con: Ph(cid:877)c h(cid:859)i và Tìm ki(cid:839)m

- 59 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

K h ô n g

Hình 3-8 Ti(cid:838)n trình con Ph(cid:878)c h(cid:860)i

Ti(cid:1219)n trình con Ph(cid:877)c h(cid:859)i ti(cid:1219)n hành ph(cid:1257)c h(cid:1239)i chân dung (cid:255)(cid:1237)i t(cid:1133)(cid:1255)ng d(cid:1269)a

trên mô t(cid:1191) c(cid:1259)a ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng trên các khuôn m(cid:1211)t phác th(cid:1191)o. Ti(cid:1219)n trình này

(cid:78)(cid:1219)t thúc khi ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ch(cid:1233)n (cid:255)(cid:1133)(cid:1255)c khuôn m(cid:1211)t phác th(cid:1191)o c(cid:1195)n tìm. (cid:264)(cid:1195)u ra

(cid:70)(cid:1259)a ti(cid:1219)n trình này là khuôn m(cid:1211)t phác th(cid:1191)o mà ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ch(cid:1233)n, c(cid:458)ng là

(cid:255)(cid:1195)u vào cho ti(cid:1219)n trình con Tìm ki(cid:839)m th(cid:1269)c hi(cid:1227)n ánh x(cid:1189) t(cid:1263) khuôn m(cid:1211)t phác th(cid:1191)o

sang (cid:1191)nh chân dung b(cid:1205)ng cách tìm trong c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u (cid:1191)nh chân dung.

- 60 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

Hình 3-9 Ti(cid:838)n trình con Tìm ki(cid:840)m

- 61 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

Minh h(cid:1233)a:

Gi(cid:1191) s(cid:1265) c(cid:1195)n ph(cid:1257)c h(cid:1239)i chân dung sau:

- 62 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

Ta có các b(cid:1133)(cid:1247)c sau:

• (cid:37)(cid:1133)(cid:1247)c 1: Ch(cid:1133)(cid:1131)ng trình phát sinh ng(cid:1199)u nhiên các khuôn m(cid:1211)t phác

th(cid:1191)o, d(cid:1269)a vào trí nh(cid:1247), ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ch(cid:1233)n 3 khuôn m(cid:1211)t nh(cid:1133) hình

(cid:71)(cid:1133)(cid:1247)i và ch(cid:1133)(cid:1131)ng trình sau (cid:255)ó th(cid:1269)c hi(cid:1227)n ti(cid:1219)n hoá.

- 63 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

• (cid:37)(cid:1133)(cid:1247)c 2: Ch(cid:1133)(cid:1131)ng trình th(cid:1223) hi(cid:1227)n các khuôn m(cid:1211)t t(cid:1237)t nh(cid:1193)t sau khi

ti(cid:1219)n hoá, ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ti(cid:1219)p t(cid:1257)c ch(cid:1233)n, nh(cid:1133) bên d(cid:1133)(cid:1247)i là 5 khuôn

(cid:80)(cid:1211)t.

- 64 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

• (cid:37)(cid:1133)(cid:1247)c 3: (cid:55)(cid:1133)(cid:1131)ng t(cid:1269) b(cid:1133)(cid:1247)c 2, l(cid:1195)n này ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ch(cid:1233)n 3 khuôn

(cid:80)(cid:1211)t.

- 65 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

• (cid:37)(cid:1133)(cid:1247)c 4: L(cid:1195)n này ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng ch(cid:1233)n 2 khuôn m(cid:1211)t

- 66 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

• (cid:37)(cid:1133)(cid:1247)c 5: Ng(cid:1133)(cid:1249)i s(cid:1265) d(cid:1257)ng (cid:255)ã ch(cid:1233)n (cid:255)(cid:1133)(cid:1255)c khuôn m(cid:1211)t “v(cid:1263)a ý” (khuôn

(cid:80)(cid:1211)t (cid:255)ánh d(cid:1193)u)

- 67 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

Sau khi ch(cid:1233)n (cid:255)(cid:1133)(cid:1255)c khuôn m(cid:1211)t phác th(cid:1191)o, ta ti(cid:1219)n hành tìm trong c(cid:1131) s(cid:1251)

(cid:71)(cid:1267) li(cid:1227)u (cid:811)nh chân dung, sau (cid:255)ây là k(cid:1219)t qu(cid:1191) tìm ki(cid:1219)m v(cid:1247)i s(cid:1237)(cid:3)(cid:1191)nh k(cid:3)(cid:255)(cid:1133)(cid:1255)c

ch(cid:1233)n khác nhau:

Hình 3-10 V(cid:866)i k=1, ch(cid:753)(cid:751)ng trình tìm (cid:255)(cid:753)(cid:874)c 2 (cid:810)nh có

cùng kho(cid:810)ng cách g(cid:814)n nh(cid:812)t (cid:255)(cid:838)n khuôn m(cid:830)t phác th(cid:810)o

(cid:255)(cid:753)(cid:874)c ch(cid:852)n

Hình 3-11 k=2, ch(cid:753)(cid:751)ng trình tìm (cid:255)(cid:753)(cid:874)c 2 (cid:810)nh

Hình 3-12 k=3 ch(cid:753)(cid:751)ng trình tìm (cid:255)(cid:753)(cid:874)c 5 (cid:810)nh có cùng

kho(cid:810)ng cách g(cid:814)n nh(cid:812)t. Khuôn m(cid:830)t c(cid:814)n ph(cid:876)c h(cid:858)i (cid:255)ã (cid:255)(cid:753)(cid:874)c

tìm th(cid:812)y là khuôn m(cid:830)t (cid:870) gi(cid:886)a

- 68 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

Hình 3-13 k=4, k(cid:838)t qu(cid:810) tìm ki(cid:838)m là 5 (cid:810)nh

Hình 3-14 k = 5, k(cid:838)t qu(cid:810) là 5 (cid:810)nh

- 69 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

CCCHHH(cid:1131)(cid:1131)(cid:1131)(cid:1129)(cid:1129)(cid:1129)NNNGGG 444

KKK(cid:1216)(cid:1216)(cid:1216)TTT LLLUUU(cid:1198)(cid:1198)(cid:1198)NNN

4.1 NH(cid:836)N XÉT

4.1.1 Nh(cid:903)ng k(cid:855)t qu(cid:827)(cid:3)(cid:255)(cid:825)t (cid:255)(cid:769)(cid:891)c

Trong quá trình nghiên cúu và cài (cid:255)(cid:1211)t lu(cid:1201)n v(cid:259)n, chúng tôi (cid:255)ã (cid:255)(cid:1189)t (cid:255)(cid:1133)(cid:1255)c

nh(cid:1267)ng k(cid:1219)t qu(cid:1191) sau:

v (cid:57)(cid:1221) lý thuy(cid:1219)t:

(cid:49)(cid:1203)m v(cid:1267)ng h(cid:1131)n v(cid:1221) c(cid:1131) ch(cid:1219) c(cid:1259)a thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n, thu(cid:1201)t

gi(cid:1191)i di truy(cid:1221)n t(cid:1133)(cid:1131)ng tác.

Cách áp d(cid:1257)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n vào bài toán ph(cid:1257)c h(cid:1239)i

thông tin.

Hi(cid:1223)u bi(cid:1219)t thêm v(cid:1221) ngôn ng(cid:1267) l(cid:1201)p trình C# và n(cid:1221)n t(cid:1191)ng

(cid:70)(cid:1259)a .NET Framework.

v (cid:57)(cid:1221)(cid:3)(cid:1261)ng d(cid:1257)ng:

(cid:264)áp (cid:1261)ng (cid:255)(cid:1133)(cid:1255)c nh(cid:1267)ng yêu c(cid:1195)u mà bài toán (cid:255)(cid:1211)t ra, xây

(cid:71)(cid:1269)ng (cid:255)(cid:1133)(cid:1255)c 2 mô(cid:255)un chính c(cid:1259)a h(cid:1227) th(cid:1237)ng.

Vì áp d(cid:1257)ng trên khuôn m(cid:1211)t 2 chi(cid:1221)u nên t(cid:1237)c (cid:255)(cid:1245) ch(cid:1133)(cid:1131)ng

trình t(cid:1133)(cid:1131)ng (cid:255)(cid:1237)i nhanh (v(cid:1247)i các tham s(cid:1237): S(cid:1237) th(cid:1219) h(cid:1227) ti(cid:1219)n

hóa: 10 (th(cid:1219) h(cid:1227)), chi(cid:1221)u dài m(cid:1245)t nhi(cid:1225)m s(cid:1203)c th(cid:1223): (bit),

- 70 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

kích th(cid:1133)(cid:1247)c qu(cid:1195)n th(cid:1223): 100 (cá th(cid:1223)); th(cid:1265) nghi(cid:1227)m trên máy

Pentium III 500 MHz, b(cid:1245) nh(cid:1247) 160MB)

(cid:1260)ng d(cid:1257)ng có giao di(cid:1227)n thân thi(cid:1227)n và d(cid:1225) s(cid:1265) d(cid:1257)ng.

4.1.2 Khó kh(cid:259)n và h(cid:825)n ch(cid:855)

v Vì h(cid:1227) th(cid:1237)ng phát tri(cid:1223)n trên các thu(cid:1245)c tính và khuôn m(cid:1211)t phác

th(cid:1191)o 2 chi(cid:1221)u nên m(cid:1261)c (cid:255)(cid:1245) chi ti(cid:1219)t c(cid:1259)a mô t(cid:1191) không cao, ch(cid:1133)a mô

hình hóa (cid:255)(cid:1133)(cid:1255)c chân dung trong th(cid:1219) gi(cid:1247)i th(cid:1269)c, khi(cid:1219)n cho ng(cid:1133)(cid:1249)i s(cid:1265)

(cid:71)(cid:1257)ng còn g(cid:1211)p nhi(cid:1221)u khó kh(cid:259)n khi mô t(cid:1191); n(cid:1219)u phát tri(cid:1223)n trên các

thu(cid:1245)c tính và khuôn m(cid:1211)t 3 chi(cid:1221)u (cid:255)(cid:1245) chính xác s(cid:1217) cao h(cid:1131)n, nh(cid:1133)ng

vì th(cid:1249)i gian có h(cid:1189)n nên trong lu(cid:1201)n v(cid:259)n nhóm m(cid:1247)i ch(cid:1229) d(cid:1263)ng l(cid:1189)i (cid:1251)

chân dung 2 chi(cid:1221)u.

v Công c(cid:1257) mã hóa (cid:1191)nh chân dung là m(cid:1245)t công c(cid:1257) bán t(cid:1269)(cid:3)(cid:255)(cid:1245)ng nên

ch(cid:1133)a mã hóa chính xác các thu(cid:1245)c tính c(cid:1259)a chân dung, thao tác

mã hóa ph(cid:1191)i th(cid:1269)c hi(cid:1227)n nhi(cid:1221)u l(cid:1195)n l(cid:1211)p l(cid:1189)i trên cùng m(cid:1245)t (cid:1191)nh, do (cid:255)ó

khi(cid:1219)n cho d(cid:1267) li(cid:1227)u b(cid:1231) “phình” to c(cid:458)ng nh(cid:1133) ph(cid:1191)i có nh(cid:1267)ng tính

toán thêm không c(cid:1195)n thi(cid:1219)t (tính trung bình c(cid:1245)ng c(cid:1259)a các vector

mã hóa (cid:255)(cid:1223) ra (cid:255)(cid:1133)(cid:1255)c vector (cid:255)(cid:1211)c tr(cid:1133)ng); luôn c(cid:1195)n có (ít nh(cid:1193)t m(cid:1245)t)

ng(cid:1133)(cid:1249)i (cid:255)(cid:1223) th(cid:1269)c hi(cid:1227)n mã hóa (cid:1191)nh.

v Do h(cid:1189)n ch(cid:1219) v(cid:1221) th(cid:1249)i gian và gi(cid:1247)i h(cid:1189)n v(cid:1221) s(cid:1237)(cid:3) (cid:1191)nh chân dung thu

(cid:255)(cid:1133)(cid:1255)c nên s(cid:1237)(cid:3)(cid:1191)nh mã hóa trong c(cid:1131) s(cid:1251) d(cid:1267) li(cid:1227)u còn ít, t(cid:1263)(cid:3)(cid:255)ó d(cid:1199)n (cid:255)(cid:1219)n

(cid:78)(cid:1219)t qu(cid:1191) ánh x(cid:1189) t(cid:1263) khuôn m(cid:1211)t phác th(cid:1191)o sang (cid:1191)nh chân dung ch(cid:1133)a

cao.

- 71 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

4.2 H(cid:768)(cid:882)NG PHÁT TRI(cid:858)N

v Phát tri(cid:1223)n t(cid:1263) các thu(cid:1245)c tính, chân dung 2 chi(cid:1221)u sang các thu(cid:1245)c

tính và chân dung 3 chi(cid:1221)u (cid:255)(cid:1223) có th(cid:1223) mô hình hóa chính xác

khuôn m(cid:1211)t trong th(cid:1219) gi(cid:1247)i th(cid:1269)c.

v Xây d(cid:1269)ng công c(cid:1257) mã hóa (cid:1191)nh chân dung thành vector (cid:255)(cid:1211)c tr(cid:1133)ng

(cid:89)(cid:1247)i các thu(cid:1245)c tính 3 chi(cid:1221)u m(cid:1245)t cách t(cid:1269)(cid:3) (cid:255)(cid:1245)ng (cid:255)(cid:1223) t(cid:259)ng (cid:255)(cid:1245) chính

xác, gi(cid:1191)m b(cid:1247)t nh(cid:1267)ng d(cid:1267) li(cid:1227)u th(cid:1263)a không c(cid:1195)n thi(cid:1219)t, ti(cid:1219)t ki(cid:1227)m công

(cid:86)(cid:1261)c và th(cid:1249)i gian.

v (cid:55)(cid:259)ng s(cid:1237)(cid:3)(cid:1191)nh (cid:255)(cid:1133)(cid:1255)c mã hóa trong (cid:70)(cid:751) s(cid:871) d(cid:887) li(cid:847)u (cid:811)nh chân dung.

v Thêm m(cid:1245)t s(cid:1237) thu(cid:1245)c tính nh(cid:1133): tu(cid:1241)i, gi(cid:1247)i tính, ch(cid:1259)ng t(cid:1245)c,…

- 72 -

Ph(cid:1257)c h(cid:1239)i thông tin t(cid:1263) d(cid:1267) li(cid:1227)u quan sát b(cid:1205)ng thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

TÀI LI(cid:1224)U THAM KH(cid:1188)O

[1]. Nguy(cid:642)n (cid:264)ình Thúc, (cid:179)Trí tu(cid:644) nhân t(cid:606)o (cid:177) L(cid:618)p trình ti(cid:636)n hóa(cid:180),

Nhà xu(cid:610)t b(cid:608)n Giáo d(cid:869)c, 2001.

[2]. Hoàng Ki(cid:636)m (cid:177) Lê Hoàng Thái, (cid:179)Thu(cid:618)t gi(cid:608)i di truy(cid:638)n, Cách

gi(cid:608)i t(cid:881) nhiên các bài toán trên máy tính(cid:180), Nhà xu(cid:610)t b(cid:608)n Giáo d(cid:869)c,

2001.

[3]. Lê Hoàng Thái, (cid:179)Gi(cid:608)i thu(cid:618)t di truy(cid:638)n, K(cid:347) thu(cid:618)t và (cid:873)ng d(cid:869)ng(cid:180),

tháng 12-1997.

[4]. Kenichi Nishio, Masayzuki Murakami, Eiji Mizutani,

Nakaji Honda,(cid:3)(cid:179)Fuzzy fitness assignment in an interactive genetic algorithm for a cartoon face search(cid:180), 2000.

[5]. Christian Jacob, (cid:179)Illustrating Evolutionary Computation with

Mathematica(cid:180), Morgan Kauphann Publishers, 2001.

[6]. Hideyuki TAKAGI, (cid:179)Interactive Evolutionary Computation:

Fusion of the Capabilities of EC Optimization and Human

Evulation(cid:180), 2001.

- 73 -

Luận văn:Phục hồi thông tin từ dữ liệu quan sát bằng thuật giải di truyền

Chủ đề:

(cid:264)(cid:1186)I H(cid:1230)C KHOA H(cid:1230)C T(cid:1266) NHIÊN THÀNH PH(cid:1234) H(cid:1236) CHÍ MINH

PPPHHH(cid:1254)(cid:1254)(cid:1254)CCC HHH(cid:1236)(cid:1236)(cid:1236)III TTTHHHÔÔÔNNNGGG TTTIIINNN TTT(cid:1260)(cid:1260)(cid:1260) DDD(cid:1264)(cid:1264)(cid:1264) LLLIII(cid:1224)(cid:1224)(cid:1224)UUU

QQQUUUAAANNN SSSÁÁÁTTT BBB(cid:1202)(cid:1202)(cid:1202)NNNGGG TTTHHHUUU(cid:1198)(cid:1198)(cid:1198)TTT GGGIII(cid:1188)(cid:1188)(cid:1188)III DDDIII

TTTRRRUUUYYY(cid:1218)(cid:1218)(cid:1218)NNN

LU(cid:819)N V(cid:258)N C(cid:883) NHÂN CÔNG NGH(cid:845) THÔNG TIN

(cid:47)(cid:1246)I C(cid:1188)M (cid:1129)N

(cid:47)(cid:1246)I GI(cid:1244)I THI(cid:1224)U

(cid:48)(cid:1254)C L(cid:1254)C

CH(cid:1132)(cid:1130)NG 1

PH(cid:1256)C H(cid:1238)I THÔNG TIN T(cid:1262) D(cid:1266) LI(cid:1226)U QUAN SÁT B(cid:1204)NG THU(cid:1200)T GI(cid:1190)I

DI TRUY(cid:1220)N-------------------------------------------------------------------------------------------------------------- 9

CH(cid:1132)(cid:1130)NG 2

(cid:39)(cid:1268)NG (cid:1190)NH CHÂN DUNG T(cid:1262) QUAN SÁT B(cid:1204)NG THU(cid:1200)T GI(cid:1190)I DI

TRUY(cid:1220)N---------------------------------------------------------------------------------------------- -------------------19

CH(cid:1132)(cid:1130)NG 3

(cid:43)(cid:1226) TH(cid:1236)NG H(cid:1242) TR(cid:1254) TÌM KI(cid:1218)M (cid:1190)NH CHÂN DUNG D(cid:1268)A TRÊN MÔ

(cid:55)(cid:1190)------------------------------ -------------------------------------------------------------------------------------------52

CH(cid:1132)(cid:1130)NG 4

(cid:46)(cid:1218)T LU(cid:1200)N ----------------------------------------------------------------------------70

DANH M(cid:1254)C CÁC HÌNH V(cid:1214)

DANH M(cid:1254)C CÁC CÔNG TH(cid:1258)C

CCCHHH(cid:1131)(cid:1131)(cid:1131)(cid:1129)(cid:1129)(cid:1129)NNNGGG 111

PPPHHH(cid:1254)(cid:1254)(cid:1254)CCC HHH(cid:1236)(cid:1236)(cid:1236)III TTTHHHÔÔÔNNNGGG TTTIIINNN TTT(cid:1260)(cid:1260)(cid:1260) DDD(cid:1264)(cid:1264)(cid:1264)

LLLIII(cid:1224)(cid:1224)(cid:1224)UUU QQQUUUAAANNN SSSÁÁÁTTT BBB(cid:1202)(cid:1202)(cid:1202)NNNGGG TTTHHHUUU(cid:1198)(cid:1198)(cid:1198)TTT

GGGIII(cid:1188)(cid:1188)(cid:1188)III DDDIII TTTRRRUUUYYY(cid:1218)(cid:1218)(cid:1218)NNN

1.1 PHÁT BI(cid:858)U BÀI TOÁN

1.2 THU(cid:836)T GI(cid:826)I DI TRUY(cid:856)N

1.2.1 Thu(cid:837)t gi(cid:827)i di truy(cid:857)n t(cid:877)ng quát

1.2.1.1 Các b(cid:1133)(cid:1247)c trong thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

(cid:37)(cid:585)(cid:859)c 1: Ch(cid:1233)n mô hình cho gi(cid:1191)i pháp c(cid:1259)a v(cid:1193)n (cid:255)(cid:1221). Trong b(cid:1133)(cid:1247)c này

(cid:37)(cid:585)(cid:859)c 2: Th(cid:1269)c hi(cid:1227)n thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n:

1.2.1.2 Cách bi(cid:1223)u di(cid:1225)n

1.2.1.3 Kh(cid:1251)i t(cid:1189)o qu(cid:1195)n th(cid:1223)

1.2.1.4 Các phép toán trên thu(cid:1201)t gi(cid:1191)i di truy(cid:1221)n

1.2.2 Thu(cid:837)t gi(cid:827)i di truy(cid:857)n t(cid:769)(cid:767)ng tác

(cid:37)(cid:585)(cid:859)c 1: Kh(cid:1251)i t(cid:1189)o qu(cid:1195)n th(cid:1223) (ng(cid:1199)u nhiên), th(cid:1223) hi(cid:1227)n k(cid:1219)t qu(cid:1191) cho ng(cid:1133)(cid:1249)i s(cid:1265)

(cid:37)(cid:585)(cid:859)c 2: Ng(cid:1133)(cid:1249)i dùng ch(cid:1233)n m(cid:1245)t s(cid:1237) k(cid:1219)t qu(cid:1191) mà “(cid:70)(cid:811)m th(cid:813)y” (cid:255)úng.

(cid:37)(cid:585)(cid:859)c 3: Th(cid:1269)c hi(cid:1227)n ti(cid:1219)n hoá v(cid:1247)i s(cid:1237) th(cid:1219) h(cid:1227) nh(cid:1193)t (cid:255)(cid:1231)nh, v(cid:1247)i hàm thích nghi

(cid:37)(cid:585)(cid:859)c 4: Hi(cid:1223)n th(cid:1231) k(cid:1219)t qu(cid:1191) sau khi ti(cid:1219)n hoá.

(cid:37)(cid:585)(cid:859)c 5: Quay l(cid:1189)i (cid:37)(cid:1133)(cid:1247)c 2 (cid:81)(cid:1219)u ng(cid:1133)(cid:1249)i dùng ch(cid:1133)a ch(cid:1193)p nh(cid:1201)n k(cid:1219)t qu(cid:1191).

CCCHHH(cid:1131)(cid:1131)(cid:1131)(cid:1129)(cid:1129)(cid:1129)NNNGGG 222

DDD(cid:1266)(cid:1266)(cid:1266)NNNGGG (cid:1188)(cid:1188)(cid:1188)NNNHHH CCCHHHÂÂÂNNN DDDUUUNNNGGG TTT(cid:1260)(cid:1260)(cid:1260)

QQQUUUAAANNN SSSÁÁÁTTT BBB(cid:1202)(cid:1202)(cid:1202)NNNGGG TTTHHHUUU(cid:1198)(cid:1198)(cid:1198)TTT GGGIII(cid:1188)(cid:1188)(cid:1188)III

DDDIII TTTRRRUUUYYY(cid:1218)(cid:1218)(cid:1218)NNN

2.1 GI(cid:882)I THI(cid:862)U

2.2 ÁP D(cid:892)NG THU(cid:836)T GI(cid:826)I DI TRUY(cid:856)N GI(cid:826)I

BÀI TOÁN PH(cid:892)C H(cid:874)I (cid:826)NH CHÂN DUNG

(cid:55)(cid:898) MÔ T(cid:826)

2.2.1 (cid:264)(cid:847)c tr(cid:769)ng và mã hóa (cid:255)(cid:847)c tr(cid:769)ng chân dung

2.2.1.1 (cid:264)(cid:1211)c tr(cid:1133)ng

2.2.1.2 Mi(cid:1221)n xác (cid:255)(cid:1231)nh c(cid:1259)a các (cid:255)(cid:1211)c tr(cid:1133)ng

Khuôn

1.

(cid:80)(cid:1211)t

2.

Lông

mày

3.

(cid:48)(cid:1203)t

4.

(cid:48)(cid:458)i

5. Mi(cid:1227)ng

2.2.1.3 Mã hoá (cid:255)(cid:1211)c tr(cid:1133)ng

2.2.2 Hàm thích nghi

=

=

D

AF

(

x

a

)

=

=

D

x

x

F