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

  • Số trang: 73 |
  • Loại file: PDF |
  • Lượt xem: 9 |
  • Lượt tải: 0
nganguyen

Đã đăng 34173 tài liệu

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 -