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
ĈҢ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
/Ӟ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
- 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 ÿ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.
- 3 -
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 ÿɉͣ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.
- 4 -
Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn
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
1.2
PHÁT BIӆU BÀI TOÁN------------------------------------------------------------------------9
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
2.2
GIӞI THIӊU ------------------------------------------------------------------------------------ 19
Á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
- 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
3.2
6Ѫ ĈӖ +ӊ THӔNG --------------------------------------------------------------------------- 52
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
NHҰN XÉT ------------------------------------------------------------------------------------- 70
4.1
4.1.1 Nhͷng k͇t qu̫ꢀÿ̩t ÿ˱ͫc-----------------------------------------------------------------------70
4.1.2 Khó khăn và h̩n ch͇ --------------------------------------------------------------------------71
+ѬӞNG PHÁT TRIӆN----------------------------------------------------------------------- 72
4.2
- 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Ѭӥ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
- 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 ÿLӅ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 -
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
Fӫ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 ÿLӅ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 ÿӕi tѭӧ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
Wӕ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 -
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 THǗ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
Fҧ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
VӁ dҫn dҫn bӏꢀÿào thҧi. Nhѭ vұy nhӳng thӃ hӋ sau bao giӡ cNJng 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
Oӡ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Ӈ FNJng ÿѭӧc gӑi là nhiӉm
Vҳ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à
Pӝ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 -
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
Gө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 cNJng 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
Vӕ, 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
Qѭӟc ÿi cӫ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, ÿLӅu khiӇn
Pҥ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.
6ӣ 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 ÿLӇ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әꢀÿLӇn mà xét ÿӃn toàn bӝ các giҧi pháp tѭѫng ÿӕi tӕt
nhҩt.
- 11 -
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Ӄ
YӅ 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
Eѭӟ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
Oӑ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à (ÿLӅu kiӋn dӯng chѭa thoҧ), lһp:
- 12 -
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) Wӯ P(t-1)
o Lai Q(t) tӯ P(t-1)
o Ĉ͡t bi͇n R(t) tӯ P(t-1)
o Ch͕n l͕c P(t) tӯ P(t-1) U Q(t) U R(t) U
P’(t)
· +Ӄt lһp
§ .Ӄt thúc
ĈLӅu kiӋn ÿӇ thuұt giҧi dӯng thѭӡng là khi thӡi gian cho phép ÿã chҩm
Gӭ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 cNJng 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 ÿLӇ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 -
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 ÿLӇ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
Gҩ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
Vҳ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Ӈ cNJ. 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.
§ 7ҥo mӝt sӕ ngүu nhiên F trong ÿRҥn tӯ 0 ÿӃn FN.
§ Chӑn cá thӇ thӭ k ÿҫu tiên thӓa )Ftk ÿѭa vào quҫn thӇ
Fӫa thӃ hӋ mӟi.
- 14 -
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): cNJng 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 ÿRҥn gen cӫa cá thӇ cha mҽ vӟi nhau. Xác suҩt
Fӫ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.
§ 7ҥo mӝt sӕ ngүu nhiên trong khoҧng tӯ 1 ÿӃn m-1 (ta gӑi
là ÿLӇm lai). ĈLӇ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
E̹ng ph˱˯ng pháp nh͓ phân, m͟i nhi͍m s̷c th͋ dài 7 bit
(A): 1001110
(B):0100011
9͓ trí lai ÿ˱ͫc phát sinh ng̳u nhiên là 3, ta có 2 nhi͍m
V̷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.
o Ĉӝt biӃn (Mutation): là hiӋn tѭӧng cá thӇ con mang mӝt sӕ tính
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 -
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Ӈ
§ 7ҥ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
E͓ꢀÿ͡t bi͇n t̩i v͓ trí ng̳u nhiên là 2, ta có nhi͍m
V̷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 cNJng 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]:
§ 6ҳp xӃp các cá thӇ trong quҫn thӇ theo ÿӝ thích nghi giҧm
Gҫ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ѭӟc N Fӕꢀÿӏ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 -
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
Wѭѫ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
Oѭӧ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
Vӱ 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
Kӧ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 -
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ѭӡi sӱ
Gөng.
%ɉ͛c 2: Ngѭӡi dùng chӑn mӝt sӕ kӃt quҧ mà “F̫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
Gӵ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 %ѭӟc 2 QӃ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ѫѩ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:
³0͡t vͭ án x̫y ra, t͡i ph̩m tr͙n thoát ÿ˱ͫc. Nhà chͱc trách có nhu
F̯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).
dung.
+͏ th͙ng t͝ng hͫp l̩i các lͥi khai ÿ͋ phác h͕a chân
Quá trình ÿ˱ͫc ti͇p tͭc cho tͣi khi ṱt c̫ nhân chͱng ÿã th͙ng nh̭t
Yͣ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
Wҧng là Thuұt giҧi di truyӅn tѭѫng tác nhѭ trình bày trong ch˱˯ng 1.
- 19 -
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 ÿӕi tѭӧ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
Pһ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 ÿӕi tѭӧng tѭѫng ӭng vӟi khuôn mһt phác thҧo
Yӯ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 cNJng 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 THǗT GI̺I DI TRUY͘N GI̺I
BÀI TOÁN PHͼC HͪI ̺NH CHÂN DUNG
7 MÔ T̺
2.2.1 Ĉ͏c tŕng và mã hóa ÿ͏c tŕng chân dung
2.2.1.1 Ĉһc trѭng
0ӝt khuôn mһt ÿѭӧc biӇu diӉn trong máy tính bҵng 20 thuӝc tính :
- 20 -
Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn
01.Má – HeadCheek (Kí hiӉu:HChk)
02.&ҳm – HeadChin (HCh)
03.Hình dңng khuôn mҹt – HeadShape (HS)
04.ChiӃu dài lông mày – EyeBrowLength (EBL)
05.Ĉӛꢀÿүm lông mày – EyeBrowStrength (EBStr)
06.9Ӎ trí lông mày – EyebrowPosition (EBP)
07.ChiӃu cao lông mày – EyeBrowHeight (EBH)
08.Hình dңng lông mày – EyeBrowShape (EBS)
09.9Ӎ trí mұt – EyePosition (EP)
10.Kích thѬӝc mұt – EyeSize (ES)
11.Khoҥng cách giӱa 2 mұt – EyeDistance (ED)
12.7Ӌ lӉ chiӃu cao mұt/chiӃu rӛng mұt –
EyeHWRatio (EHWR)
13.Kích thѬӝc ÿӕng tӯ - PupilSize (PS)
14.ChiӅu dài mNJi – NoseLength (NL)
15.ChiӃu rӛng mNJi – NoseWidth (NW)
16.Hình dңng mNJi – NoseShape (NS)
17.ChiӃu rӛng miӉng – MouthWidth (MW)
18.9Ӎ trí miӉng – MouthPosition (MP)
19.Ĉӛ dày môi trên – MouthThicknessOfUpperLip
(MTUL)
- 21 -
Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn
20.Ĉӛ dày môi dѬӝi - MouthThicknessOfLowerLip
(MTLL)
2.2.1.2 MiӅn xác ÿӏnh cӫa các ÿһc trѭng
%ӝ
Ĉһc
Trung bình
(7)
Stt
Min (0)
Max (15)
phұn
trѭng
1. Má
Khuôn
2. &ҵm
1.
Pһt
3. Hình
Gҥng
khuôn
Pһt
2.
4. ChiӅu
Lông
mày
dài
5. Ĉӝꢀÿұm
- 22 -
Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn
6. 9ӏ trí
7. ChiӅu
cao
8. Hình
Gҥng
3.
0ҳt
9. 9ӏ trí
10. Kích
thѭӟc
11. Khoҧng
cách
giӳa hai
Pҳt
- 23 -
Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn
12. 7Ӎ lӋ
cao /
Uӝng
13. Kích
thѭӟc
ÿӗng tӱ
14. ChiӅu
dài
15. ChiӅu
4.
0NJi
Uӝng
16. Hình
Gҥng
17. ChiӅu
MiӋng
Uӝng
5.
18. 9ӏ trí
- 24 -
Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn
19. Ĉӝ dày
môi
trên
20. Ĉӝ dày
môi
Gѭӟi
2.2.1.3 Mã hoá ÿһc trѭng
Trong bài toán này, ta biӇu diӉn nhiӉm sҳc thӇ bҵng chuӛi nhӏ phân 0,1.
Ĉӕi vӟi mӛi thuӝc tính, lҩy miӅn xác ÿӏnh trong khoҧng [0..15], tӭc là
Oҩy 16 giá trӏ khác nhau. Sӣ dƭ chӑn con sӕ 16 vì 16 là mӝt lNJy thӯa cӫa 2,
thuұn lӧi cho viӋc biӇu diӉn, nӃu chӑn 8 thì sӕ giá trӏ biӇu diӉn ÿѭӧc quá ít,
còn 32 thì lҥi quá nhiӅu.
§ BiӇu diӉn 1 gen: Xem mӛi thuӝc tính nhѭ mӝt gen, do có 16 giá trӏ cho
Pӛi thuӝc tính nên ÿӕi vӟi mӛi gen ÿӇ biӇu diӉn ta cҫn 4 bit.
Ví dͭ: Gi̫ s͵ thu͡c tính HeadShape mang giá tr͓ 9, nh˱ v̵y gen bi͋u di͍n sͅ
là 1001.
§ BiӇu diӉn chuӛi nhiӉm sҳc thӇ: Mӝt nhiӉm sҳc thӇ là mӝt chuӛi tuyӃn
tính các gen, mӛi gen có vӏ trí xác ÿӏnh trong chuӛi. Do có tҩt cҧ 20
thuӝc tính, tӭc là có 20 gen nên mӛi nhiӉm sҳc thӇꢀÿѭӧc biӇu diӉn bҵng
chuӛi nhӏ phân có chiӅu dài 20(gen) x 4(bit/gen) = 80 bit.
Qui ѭӟc cho mӛi gen mӝt ví trí cӕꢀÿӏnh trong nhiӉm sҳc thӇ, giҧ sӱ
HeadCheek(HChk) vӏ trí 1, HeadChin(HCh) vӏ trí 2, HeadShape(HS) vӏ
trí 3, …, MouthThicknessOfLowerLip (MTLL) vӏ trí 20, ta có biӇu diӉn
Fӫa mӝt nhiӉm sҳc thӇ nhѭ sau:
- 25 -
Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn
HChk.HCh.HS.EBL.EBStr.EBP.EBH.EBS.EP.ES.ED.EHWR.PS.
NL.NW.NS.MW.MP.MTUL.MTLL.
Ví dͭ: Ta có 4 nhi͍m s̷c th͋ bi͋u di͍n cho 4 khuôn m̿t. Trong ÿó,
khuôn m̿t (A) nhi͍m s̷c th͋ có các gen mang toàn giá tr͓ 0 (giá tr͓ bit
0000), khuôn m̿t (B) mang giá tr͓ trung bình 7 (giá tr͓ bit 1110), khuôn m̿t
(C) toàn giá tr͓ lͣn nh̭t 15 (giá tr͓ bit 1111), còn khuôn m̿t (D) mang giá tr͓
ng̳u nhiên.
(A)Nhi͌m s̶c th͊: 0000.0000...0000
(B) Nhi͌m s̶c th͊: 1000.1000...1000
(C)Nhi͌m s̶c th͊: 1111.1111...1111
- 26 -
Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn
(D)Nhi͌m s̶c th͊:
2.2.2 Hàm thích nghi
Ta xem mӛi khuôn mһt nhѭ mӝt ÿLӇm nguyên trong không gian 20
chiӅu {0, … , 15}20, trong ÿó giá trӏ cӫa thuӝc tính ÿóng vai trò tӑa ÿӝ. Dӵa
trên khoҧng cách giӳa các ÿLӇm trong không gian này, giá trӏ thích nghi
ÿѭӧc tính theo qui tҳc sau :
(1). Ĉӕi vӟi nhӳng khuôn mһt ÿѭӧc chӑn: Giá trӏ thích nghi = Giá trӏ
thích nghi lӟn nhҩt = Khoҧng cách xa nhҩt = 61 (nhѭ tính ӣ dѭӟi).
(2). Ĉӕi vӟi các khuôn mһt còn lҥi: Dӵa trên khoҧng cách ÿӃn khuôn
Pһt trung bình.
Trong trѭӡng hӧp (1), gӑi MaxFace(15, … ,15) là ÿLӇm xa nhҩt trong
KӋ tӑa ÿӝ, O(0, … ,0) là tâm tӑa ÿӝ, vì tҩt cҧ các ÿLӇm ÿӅu có tӑa ÿӝ không
âm, ta có khoҧng cách Euclide giӳa hai khuôn mһt xa nhҩt là:
20
Dmax = MaxFace- O =
(15- 0)2 = 20.152 =15 20 » 61= const
å
1
Do ÿó giá trӏ thích nghi lӟn nhҩt là 61.
Trѭӡng hӧp (2), khuôn mһt trung bình A(a1, …aj ,… am) Fӫa n khuôn
Pһt (F1, F2, …, Fn) Yӟi Fi = ( xi1 ,…, xij ,…, xim) trong ÿó m là sӕ thuӝc tính
(trong luұn văn m = 20), ÿѭӧc xác ÿӏnh nhѭ sau:
- 27 -
Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn
n
xij
å
i =1
a j =
,1 £ j £ m
n
Công thͰc 2-1 T͔a ÿ͠ các ÿL͊m cͮa khuôn m̾t trung
bình A
D
*ӑi
là khoҧng cách tӯ khuôn mһt thӭ i (F ) ÿӃn mһt trung bình A.
F,A
i
i
Công thӭc tính khoҧng cách nhѭ sau:
m
D F , A = Fi - A =
( xij - a j )2
å
i
j =1
Công thͰc 2-2 Kho̪ng cách tͲ khuôn m̾t Fiꢀÿ͆n khuôn
P̾t trung bình A
Ghi chú: Do khoҧng cách Euclide sӱ dөng phép lҩy căn chiӃm nhiӅu
thӡi gian tính toán cӫa máy nên trong luұn văn sӱ dөng ÿӝꢀÿo City-BlockꢀÿӇ
thay thӃ. Ĉӝꢀÿo khoҧng cách City-Block giӳa hai vector ÿһc trѭng cӫa hai
khuôn mһt phác thҧo Fa(xa1,…,xam) và Fb(xb1,…,xbm) ÿѭӧc tính nhѭ sau:
m
D F ,F = F - F =
xaj - xbj
å
a
b
a
b
j =1
Công thͰc 2-3 Ĉ͠ꢀÿo kho̪ng cách City-Block
Theo công thӭc này thì Dmaxꢀÿѭӧc tính lҥi nhѭ sau:
20
Dmax = MaxFace- O = 15 - 0 = 20.15 = 300 = const
å
1
- 28 -
Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn
Khoҧng cách tӯ khuôn mһt trung bình A(a1, …aj ,… am) ÿӃn khuôn
Pһt thӭ i Fi = ( xi1 ,…, xij ,…, xim):
m
D F , A = F - A =
xij - a j
å
i
i
j =1
Công thͰc 2-4 Kho̪ng cách City-Block giͶa Fi và A
Công thͱc tính giá tr͓ thích nghi :
*ӑi eval(Fi) là giá trӏ thích nghi cho khuôn mһt thӭ i. Ta có công thӭc
tính giá trӏ thích nghi nhѭ sau :
DF ,A
Eval (Fi) = IF ( Fiꢀÿѭӧc chӑn , Dmax , Dmax –
)
i
Công thͰc 2-5 Giá tr͒ thích nghi cͮa khuôn m̾t Fi
2.2.3 Thuͅt gi̻i di truy͙n
2.2.3.1 Các phép toán
2.2.3.1.1 Tái sinh
ĈӇ chӑn ra mӝt quҫn thӇ khuôn mһt mӟi tӯ quҫn thӇ hiӋn hành, ta sӱ
Gөng phѭѫng pháp tái sinh nhѭ trong thuұt giҧi di truyӅn thông thѭӡng, dùng
nguyên tҳc quay bánh xe Rulét vӟi các rãnh ÿѭӧc ÿӏnh nghƭa dӵa trên ÿӝ
thích nghi. Cө thӇ gӑi pop_size là kích thѭӟc quҫn thӇ (sӕ khuôn mһt trong
quҫn thӇ), thao tác tái sinh ÿѭӧc thӵc hiӋn nhѭ sau [1]:
§ Tính ÿӝ thích nghi cho mӛi khuôn mһt:
eval(F )," i Î {1,..., pop _ size}
i
§ Tính tәng ÿӝ thích nghi cӫa quҫn thӇ:
- 29 -
Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn
poåp _ size
F =
eval(F )
i
i=1
§ Tính xác suҩt chӑn cho mӛi khuôn mһt:
eval(F )
i
pi =
," i ={1,..., pop_ size}
F
§ Tính vӏ trí xác suҩt:
åi
q i =
p
j
j = 1
§ TiӃn hành chӑn: Mӛi lҫn chӑn mӝt nhi͍m s̷c th͋/khuôn m̿t tӯ quҫn
thӇ hiӋn hành vào quҫn thӇ mӟi theo cách sau:
o Phát sinh ngүu nhiên mӝt sӕ thӵc r Î [0,1]
o 1Ӄu r q1 thì khuôn mһt ÿҫu tiên (f1)ꢀÿѭӧc chӑn, ngѭӧc lҥi chӑn
khuôn mһt thӭ i (fi) sao cho qi-1 < r qi
2.2.3.1.2 Lai
Ĉӕi vӟi mӛi khuôn mһt trong quҫn thӇ mӟi, phát sinh ngүu nhiên mӝt
Vӕ thӵc r Î [0,1], nӃu r nhӓ hѫn xác suҩt lai pc thì chӑn khuôn mһt ÿó ÿӇ lai.
Sau khi ÿã chӑn ÿӫ sӕ khuôn mһt, ta tiӃn hành thao tác lai ghép nhѭ
sau:
§ Ĉӕi vӟi mӛi cһp khuôn mһt ÿѭӧc ghép ÿôi, phát sinh ngүu nhiên mӝt
Vӕ nguyên pos Î {1,…,m-1} (m là tәng sӕ bit ÿӇ biӇu diӉn nhiӉm sҳc
thӇ, m=20 x 4 = 80 bit). Sӕ pos cho biӃt vӏ trí ÿӇ lai.
§ Thay hai khuôn mһt trên:
(a1a2«aposapos+1«am) và
- 30 -
Tải về để xem bản đầy đủ
73 trang
16/06/2025
510
Bạn đang xem 30 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_phuc_hoi_thong_tin_tu_du_lieu_quan_sat_bang_thuat_g.pdf
