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

ĈҢ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

Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn

- 2 -

/Ӟ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 ÿã tɞo

ÿLɾ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 ÿã

Wɪ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.

0ɴ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

Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn

- 3 -

/Ӟ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 ÿLɾu ÿó là do máy tính có hai ÿLʀm mɞnh chͧ yɼu là

W͑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

Fͧ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ɾQ«, 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ɢW«) và ngay cɠ trong lśnh vͱc ÿLɾ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ɾQ´ 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 ÿLɾ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

Uɞc.

Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn

- 4 -

%͑ 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 ÿɉͣ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ô

Wҧ

Chɉɇng 3 trình bày vɾ mô hình cài ÿɴt cͥ thʀ cho bài toán

Gͱ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.

Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn

- 5 -

0Ӧ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˱˯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 7Ӯ MÔ 7Ҧ 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Ô

7Ҧ------------------------------ -------------------------------------------------------------------------------------------52

Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn

- 6 -

3.1 6Ѫ ĈӖ +ӊ 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

Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn

- 7 -

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 ÿѬӥc 2 ҥ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 ÿѬӥc 2 ҥnh ----------------68

Hình 3-12 k=3 chѬѪng trình tìm ÿѬӥc 5 ҥ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