intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Nguyen Bao Ngoc | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
139
lượt xem 41
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thuật giải di truyền đã và đang là một công cụ 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ệ” cho games…), cho đến ứng dụng trong công nghiệp đem lại lợi nhuận (như trong khai thác dầu khí, trong thiết kế máy móc, trong khai thác hầm mỏ, giao thông công cộng, trong sản xuất…) và ngay cả trong lĩnh vực điều tra tội phạm. Đề tài “Phục hồi thông tin từ dữ liệu quan sát bằng thuật...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

  1. I H C KHOA H C T NHIÊN THÀNH PH H CHÍ MINH KHOA CÔNG NGH THÔNG TIN MÔN CÔNG NGH 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 THÔNG TIN Giáo viên h ng d n TS. Nguy n ình Thúc Niên khóa 2000-2004
  2. Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n ICM 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 ãto 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 n ông bà, cha m ã ch m sóc, nuôi d y chúng con thành ng i. Chúng em xin chân thành cám n th y Nguy n ình Thúc ã n tình h 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-
  3. 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 u ó là do máy tính có hai m m nh ch y u là c 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 ng d ng c a Trí tu Nhân t o có m t 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 lý nh, M ng N ron, Thu t gi i di truy , m i l nh v c khi c áp d ng vào trong th c t u ã t c m t s thành t u nh t nh. Riêng Thu t gi i di truy n ã và ang là m t công c 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 cho games ), cho n ng d ng trong công nghi p em l i l i nhu n (nh trong khai thác d u khí, trong thi t k 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 u tra t i ph m. tài Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy 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 i t nh ng thông tin r i c. -3-
  4. 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 c s d ng trong tài. § Ch ng 2: D ng nh chân dung t 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 cs 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 t c th cho bài toán a vào lý thuy t c kh o sát trong các ch ng trên. § Ch ng 4: K t lu n Nh ng k t qu ã t c, h ng phát tri n cho t ng lai, ó là nh ng n i dung c trình bày trong ch ng này. -4-
  5. Ph c h i thông tin t d li u quan sát b ng thu t gi i di truy n CLC 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 ng tác ----------------------------------------------------------------16 CH NG 2 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 NG THU T GI I DI TRUY N GI I BÀI TOÁN PH C I NH CHÂN DUNG MÔ 20 2.2.1 c tr ng và mã hóa c tr ng chân dung -------------------------------------------------20 2.2.1.1 c tr ng --------------------------------------------------------------------------------------------- 20 2.2.1.2 Mi n xác nh c a các c tr ng ------------------------------------------------------------------ 22 2.2.1.3 Mã hoá 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-
  6. 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 TH NG ------------------------------------------------------------------ 54 3.2.1 S 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 NG 4 T LU N ----------------------------------------------------------------------------70 4.1 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-
  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 HÌNH V Hình 1-1 L c c a m t thu t gi i di truy n t ng tác ---17 Hình 2-1 S t ng quát c a bài toán. Trong ó, 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 th ng ---------------------52 Hình 3-2 S màn hình -----------------------------------54 Hình 3-3 Màn hình chính c a ch ng trình. -----------------55 Hình 3-4 Màn hình mã hóa 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 ng trình tìm c2 nh có cùng kho ng cách g n nh t n khuôn m t phác th o c ch n 68 Hình 3-11 k=2, ch ng trình tìm c2 nh ----------------68 Hình 3-12 k=3 ch ng trình tìm c5 nh có cùng kho ng cách g n nh t. Khuôn m t c n ph c h i ã c tìm th y là khuôn m t gi a -----------------------------------68 Hình 3-13 k=4, k t qu tìm ki m là 5 nh ------------------69 Hình 3-14 k = 5, k t qu là 5 nh -------------------------69 -7-
  8. 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 m c a khuôn m t trung bình A ..28 Công th c 2-2 Kho ng cách t 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-
  9. 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 ng r i r c, không ch c ch n, th i gian quan sát có khi r t ng n và ch u nh h ng c a nhi u y u t ch quan a ng 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 ng nghi v n d a vào l i khai c a các nhân ch ng. Các nhân ch ng th 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 t các 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 tài này. Thu t gi i di truy n là m t trong nh ng ph ng pháp có th gi i quy t t nh ng v n mà bài toán t ra nh vào các phép toán r t m nh mà thu t -9-
  10. 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ó thích nghi kém d nd nb ào th i. Nh v y nh ng th h sau bao gi c ng t t h n th h tr 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 ng c g i là nhi m c th . Các nhi m s c th là m t chu i tuy n tính các n v nh h n là các gen, m i gen bi u di n cho m t c tr ng và có m t v trí nh t nh trong nhi m s c th . M i 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, t bi n, ch n l c… là các phép toán th c hi n trên qu n th t o ra m t qu n th m i. - 10 -
  11. 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 ng và kh n ng thích nghi c a m i cá th v i môi tr ng, m t hàm thích nghi (hàm m c tiêu, hàm l ng giá) c nh ra. Hàm này t o ra m t h s thích nghi cho m i cá th , thông th 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 ng. Cá th càng thích nghi t t v i môi tr 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ó nh h ng, hàm thích nghi óng vai trò “ nh h ng” này [2]. Tuy ch m i c hình thành cách ây ch a y 25 n m nh ng thu t gi i di truy n ã có 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 i th trong các trò ch i… v Ho ch 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 c áp d ng r ng rãi nh v y là vì thu t gi i di truy n có nh ng u m sau [1]: ü Không chú tr ng n gi i pháp chung nh t và chính xác nh các ph ng pháp c n mà xét n toàn b các gi i pháp t ng it t nh t. - 11 -
  12. 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 i qua l i, nh v y giúp gi m b t kh n ng k t thúc t i m t c c ti u 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 . Trong b c này chúng ta c n xác nh 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 t bi n,... 4) Ch n cách kh i t o qu n th ban 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à ( u ki n d ng ch a tho ), l p: - 12 -
  13. 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 ng là khi th i gian cho phép ã ch m t ho c ã tì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 ng pháp bi u di n m t nhi m s c th - l i gi i, tuy nhiên tr 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 c mã hóa nh m t s l ng bit (0,1) nào ó. Cách bi u di n này có nh c m là chính xác không cao (các ph n t c truy nh p là các s nguyên), mu n t ng chính xác ph i t ng s l ng bit bi u di n do ó d n 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 nh [3]. § Bi u di n b ng s th p phân: M i nhi m s c th c mã hóa là m t vect s d u ph y ng v i cùng chi u dài c a vect l i gi i. Cách - 13 -
  14. 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 c ph 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 xem xét có 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 nt 0 n FN. § Ch n cá th th k u tiên th a Ftk a vào qu n th a th h m i. - 14 -
  15. 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 n m-1 (ta g i là m lai). 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 ) c bi u di n ng ph ng pháp nh phân, m i nhi m s c th dài 7 bit (A): 1001110 (B):0100011 trí lai 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 i thông tin gi a các l i gi i. t bi n (Mutation): là hi n t ng cá th con mang m t s tính o tr ng không có trong mã di truy n c a cha m . t bi n có xác su t pm r t nh so v i pc. Phép t bi n có th mô ph ng nh sau [1]: - 15 -
  16. 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 ó sinh s n, t bi n t o ra các cá th m i. Các cá th 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 cu i dãy ch gi l i N cá th t t nh t. ây ta gi s qu n th có kích th cN nh. 1.2.2 Thu t gi i di truy n t ng tác Thu t gi i di truy n t 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 -
  17. 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 i s d ng. Thu t gi i di truy n ng tác c xem là m t công c h u ích i v i nh ng bài toán mà tiêu chu n l ng giá r t ph c t p và/ho c thông tin không y , khi n cho không th xây d ng m t hàm thích nghi xác nh [4], ví d nh nh ng bài toán liên quan n hình nh, âm thanh, gi l p th gi i th c,… ch c c ng b ng c m giác, n t ng, s thích, c m xúc hay s nh y bén c a ng i d ng h th ng [6]; gi i quy t nh ng bài toán này n u s d ng các ph ng pháp t i u hóa truy n th ng s g p r t nhi u khó kh n và chính xác th 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 ng tác. D i ây là l c c a Thu t gi i di truy n t ng tác thông th ng: Hình 1-1 L c c a m t thu t gi i di truy n t ng tác - 17 -
  18. 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 nh, v i hàm thích nghi a trên nh ng k t qu ng i dùng ch n, trong ó nh ng nhi m s c th c ch n 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 -
  19. 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 2 D NG 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 c ti n hành nh sau: (1). 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 trình máy tính mà n n ng là Thu t gi i di truy n t ng tác nh trình bày trong ch ng 1. - 19 -
  20. 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 ng c a ch ng trình nh sau: Ch 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 it ng (t i ph m) nh t, nh ng 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 c ch n, ch ng trình s d ng thu t gi i di truy n th c hi n ti n hóa cho ra các khuôn m t phác th o h p v i mô t c a ng i s d ng nh t; sau khi ng i s d ng ch n c khuôn m t phác th o, ch ng trình tìm trong c s d li u nh chân dung th t nh c a it ng t ng ng v i khuôn m t phác th o a tìm c. Ch 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 c khi nh c n khuôn m t phác th o là khuôn m t do ch 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 c tr ng và mã hóa c tr ng chân dung 2.2.1.1 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 -
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

TL.01: Bộ Tiểu Luận Triết Học
207 tài liệu
1470 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2