Đề tài 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 Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn - 8 - 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 Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn - 9 - 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 Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn - 10 - 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. Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn - 11 - ĈӇ 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. Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn - 12 - ü 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: Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn - 13 - 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 Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn - 14 - 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. Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn - 15 - 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]: Phөc hӗi thông tin tӯ dӳ liӋu quan sát bҵng thuұt giҧi di truyӅn - 16 - § 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.