Đăng ký Đăng nhập
Trang chủ Phục hồi thông tin từ dữ liệu quan sát bằng thuật giải di truyền...

Tài liệu Phục hồi thông tin từ dữ liệu quan sát bằng thuật giải di truyền

.PDF
73
90
97

Mô tả:

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

Tài liệu liên quan