Đề tài Một số phương pháp dò tìm ngẫu nhiên và ứng dụng

%Ӝ GIÁO DӨC VÀ ĈÀO TҤO TRѬӠNG ĈҤI HӐC ĈÀ LҤT TRѬѪNG CHÍ TÍN 0ӜT SӔ PHѬѪNG PHÁP DÒ TÌM NGҮU NHIÊN VÀ ӬNG DӨNG Ĉӄ TÀI KHOA HӐC CҨP BӜ (B2005-29-34) ĈÀ LҤT, 2006 %Ӝ GIÁO DӨC VÀ ĈÀO TҤO TRѬӠNG ĈҤI HӐC ĈÀ LҤT 0ӜT SӔ PHѬѪNG PHÁP DÒ TÌM NGҮU NHIÊN VÀ ӬNG DӨNG Ĉӄ TÀI KHOA HӐC CҨP BӜ (B2005-29-34) Chӫ nhiӋm ÿӅ tài: Trѭѫng Chí Tín Các thành viên: Ĉһng Phѭӟc Huy Trҫn Ngӑc Anh ĈÀ LҤT, 2006 0ӨC LӨC /ͥi mͧÿ̯u _______________________________________________________ 1 PḪN I. M͡t s͙ k͇t qu̫ v͉ thu̵t gi̫i di truy͉n và m̩ng n˯ron ____________ 4 1. Ӭng dөng chiӃn lѭӧc ÿӝng trong thuұt giҧi di truyӅn giҧi mӝt lӟp bài toán Wӕi ѭu toàn cөc …..……………………………………………………… 5 2. Cҧi thiӋn khҧ năng hӑc cӫa mҥng nѫ ron truyӅn thҷng nhiӅu lӟp ……… 19 PḪN II. M͡t s͙ k͇t qu̫ v͉ nung luyӋn mô phӓng ___________________ 30 1. Sӵ hӝi tө cӫa thuұt toán nung luyӋn mô phӓng trong trѭӡng hӧp rӡi rҥc …………………………………………………………………………. 31 2. Nung luyӋn mô phӓng: mӝt sӕ nhұn xét vӅ sӵ hӝi tө cӫa xích Metropolis …………………………………………………………………………. 51 3. Áp dөng phѭѫng pháp nung luyӋn mô phӓng vào bài toán lұp lӏch dòng công viӋc ………………………………………………………………. 63 .͇t lu̵n _______________________________________________________ 97 1. Các kӃt quҧ chính vӅ lý thuyӃt, ӭng dөng và sҧn phҭm cӫa ÿӅ tài …………... 97 2. Các hѭӟng mӣ rӝng cӫa ÿӅ tài ……………………………………………….. 99 1/ͥi MͧĈ̯u Thuұt giҧi di truyӅn (Genetic Algorithms - GA) và nung luyӋn mô phӓng (Simulated Annealing - SA) là hai trong sӕ các phѭѫng pháp tìm kiӃm ngүu nhiên khá hiӋu quҧ và ÿѭӧc ӭng dөng rҩt nhiӅu trong thӵc tӃ. Tӯ nhӳng năm 50, thӃ kӹ XX, A.S. Fraser ÿã ÿѭa ra ý niӋm vӅ thuұt giҧi di truyӅn dӵa trên sӵ tiӃn hóa và di truyӅn cӫa sinh vұt. Nhѭng phҧi ÿӃn nhӳng năm 70, thӃ kӹ XX, J. H. Holland mӟi triӇn khai thành công ý tѭӣng và phѭѫng thӭc giҧi quyӃt vҩn ÿӅ bҵng thuұt giҧi di truyӅn. Sau ÿó, ngày càng nhiӅu kӃt quҧÿһt QӅn tҧng lý thuyӃt cho GA ÿҥt ÿѭӧc bӣi các tác giҧ khác nhѭ Kenneth De Jong, David E. Goldberg, … Cho ÿӃn nay, GA ÿѭӧc áp dөng trong rҩt nhiӅu lƭnh vӵc, ÿһc biӋt là trong khoa hӑc tӵ nhiên và kӻ thuұt. 0ӝt trong nhӳng ӭng dөng cӫa GA là bài toán tӕi ѭu hoá. Khi áp dөng các thuұt giҧi di truyӅn cәÿLӇn vào bài toán tӕi ѭu hoá toàn cөc, ta thѭӡng gһp hҥn chӃ là tӕc ÿӝ hӝi tө và ÿӝ chính xác cӫa lӡi giҧi tӕi ѭu không cao. ViӋc cҧi tiӃn các thuұt giҧi di truyӅn ÿӇ tăng tӕc ÿӝ hӝi tө và ÿӝ chính xác cӫa lӡi giҧi, ÿһc biӋt khi Vӕ chiӅu không gian tìm kiӃm lӟn, là rҩt có ý nghƭa thӵc tӃ. ĈӇ khҳc phөc hҥn chӃ trên, trѭӟc hӃt, chúng tôi F̫i ti͇n ph˱˯ng pháp lai W̩o ÿ͡ng theo xác sṷt và W͝ng quát hóa ph˱˯ng pháp hi͏u ch͑nh tuy͇n tính cͯa D. E. Goldberg trong GA nhҵm nghiên cӭu P͡t s͙ tính ch̭t h͡i tͭ cͯa phân ph͙i xác sṷt ch͕n cá th͋ ÿӇ biӃn hóa (lai hoһc ÿӝt biӃn) hoһc tái tҥo quҫn thӇ mӟi. Trên cѫ Vӣÿó, chúng tôi áp dͭng chi͇n l˱ͫc ÿ͡ng vào GA, nghƭa là viӋc biӃn hoá và chӑn cá thӇ sӁ thӵc hiӋn theo các cách khác nhau tùy thuӝc vào tuәi cӫa thӃ hӋ tiӃn hoá Yӟi các xác suҩt thích hӧp, tùy vào mөc tiêu khoanh vùng cӵc trӏ toàn cөc hay tăng Wӕc ÿӝ hӝi tөÿӃn lӡi giҧi tӕi ѭu toàn cөc ÿó. Cuӕi cùng, ÿӇ tăng hѫn nӳa tӕc ÿӝ hӝi Wө và ÿӝ chính xác cӫa lӡi giҧi tӕi ѭu, chúng tôi áp dͭng ph˱˯ng pháp leo ÿ͛i trên nhӳng lân cұn bé dҫn cӫa lӡi giҧi tӕi ѭu cӫa bѭӟc trѭӟc. Các kӃt quҧ thӵc nghiӋm trên mӝt lӟp các bài toán tӕi ѭu toàn cөc, vӟi ÿһc trѭng có rҩt nhiӅu cӵc trӏÿӏa phѭѫng, cho thҩy thu̵t gi̫i di truy͉n ÿ͡ng (Dynamic Genetic Algorithms - DGA) c̫i ti͇n có t͙c ÿ͡ h͡i tͭ và ÿ͡ chính xác cͯa lͥi gi̫i cao h˯n h̻n thu̵t gi̫i di truy͉n c͝ÿL͋n. Ngoài ra, chúng tôi còn so sánh vi͏c áp dͭng GA và DGA vào bài toán h͕c lu̵t qua m̩ng n˯ron nhân t̩o (Artificial Neural Network - ANN), sau khi F̫i ti͇n thu̵t toán h͕c các tham s͙ trong m̩ng n˯ ron. Trên bài toán mӟi, chúng tôi cNJng thu ÿѭӧc các kӃt quҧ tѭѫng tӵ nhѭ trên. Phѭѫng pháp dò tìm ngүu nhiên thӭ hai chúng tôi ÿӅ cұp trong ÿӅ tài này là nung luyӋn mô phӓng - SA. Ĉây là các thuұt toán tӕi ѭu toàn cөc ngүu nhiên ÿѭӧc xây dӵng tӯ viӋc biӃn thӇ cӫa các thuұt toán mô phӓng kiӇu Metropolis dӵa vào các tham sӕÿLӅu khiӇn biӃn thiên theo chu trình tiӃn hóa cӫa thuұt toán. Thuұt toán ÿѭӧc giӟi thiӋu mӝt cách ÿӝc lұp bӣi S. Kirkpatrich, C. D. Gellatt, M. P. Vecchi (1983) và Cerny (1985). Tên gӑi “simulated annealing” xuҩt phát tӯ sӵ 2Wѭѫng tӵ vӟi quá trình nung luyӋn cӫa cӕ thӇ trong mӝt bӇ nhiӋt cӫa vұt lý chҩt Uҳn. Các tên gӑi khác cho thuұt toán, chҷng hҥn là: nung luyӋn Monte Carlo (Monte Carlo annealing- Jepsen và Gelatt, 1983), thuұt toán xác suҩt leo ÿӗi (Probabilistic hill climbing- Romeo và Sangiovanni- Vincentelli, 1985), làm nguӝi thӕng kê (Statistical cooling- Aarts và Van Laarhoven, 1985; Storer, Becker và Nicas, 1985)... 7ӯ nhӳng năm ÿҫu cӫa thұp niên 80 cӫa thӃ kӹ 20 cho ÿӃn nay, thuұt toán SA ÿã và ÿang thu hút sӵ quan tâm cӫa nhiӅu ngѭӡi nghiên cӭu cҧ vӅ lý thuyӃt và ӭng dөng. Sӵ phát triӇn vӅ lý thuyӃt cӫa thuұt toán gҳn vӟi các công trình cӫa các tác giҧ nhѭ: B. Gidas (1985), S. Anily và A. Federgruen (1985, 1986), D. Mitra, F. Romeo và A. Sangiovanni- Vincentelli (1986), B. Hajek (1988), C. R. Hwang và S. J. Sheu (1987, 1992), R. Holley, S. Kusuoka và D. Stroock (1989), O. Catoni (1992, 1998), D. Marquez (1997), P.D. Moral và L. Miclo (1999)... . Bên cҥnh ÿó SA cNJng ÿã ÿѭӧc áp dөng ÿӇ giҧi nhiӅu bài toán tӕi ѭu tә hӧp cӥ lӟn thuӝc lӟp NP - khó, các bài toán thӵc trong công nghӋ và kinh tӃ - xã hӝi. Trong các áp dөng cӫa SA vào các bài toán thӵc tiӉn, có nhӳng áp dөng thӇ hiӋn tính hiӋu quҧ cӫa phѭѫng pháp SA nhѭng cNJng có không ít các áp dөng SA không ÿem lҥi hiӋu quҧ mӝt cách ÿáng kӇ. Tình huӕng ÿҫu thѭӡng xҧy ra ÿӕi vӟi các thӇ hiӋn bài toán mà ÿLӅu kiӋn áp dөng khҧ thi là phù hӧp vӟi các ÿLӅu kiӋn lý thuyӃt cho sӵ hӝi tө. Tình huӕng sau phҫn lӟn là do ÿһc thù riêng cӫa các bài toán không hӝi ÿӫ các ÿLӅu kiӋn ÿӇ vұn dөng ÿѭӧc các kӃt quҧ hӝi tөÿã biӃt. ViӋc áp Gөng thuұt toán thuҫn túy là dӵa vào các phán ÿoán rút ra tӯ sӵ phân tích dӳ liӋu thӵc nghiӋm mà chѭa ÿӫ bҧo ÿҧm lý thuyӃt cho sӵ hӝi tө cӫa thuұt toán. Qua ÿó cho thҩy nhiӅu vҩn ÿӅ vӅ sӵ hӝi tө cӫa SA cҫn phҧi ÿѭӧc tiӃp tөc nghiên cӭu. Góp phҫn vào các vҩn ÿӅ quan tâm ӣ trên ÿӕi vӟi SA, trong phҥm vi ÿӅ tài này, chúng tôi tұp trung nghiên cӭu V͹ h͡i tͭ cͯa thu̵t toán nung luy͏n mô ph͗ng trong tr˱ͥng hͫp rͥi r̩c. Cө thӇ, chúng tôi trình bày mӝt sӕ kӃt quҧ liên quan ÿӃn Vӵ hӝi tө cӫa thuұt toán SA thuҫn nhҩt vӟi các hàm xác suҩt sinh và chҩp nhұn có Gҥng tәng quát. Nghiên cӭu ҧnh hѭӣng cӫa tham sӕÿóng vai trò nhiӋt ÿӝ trong quy trình nung luyӋn và tác ÿӝng cӫa viӋc giҧm nhanh nhiӋt ÿӝ vào sӵ hӝi tө cӫa thuұt toán SA. Mӝt sӕ khía cҥnh vӅ tӕc ÿӝ hӝi tөÿӃn trҥng thái cân bҵng, xem xét dáng ÿLӋu tiӋm cұn ÿӃn phân bӕ cân bҵng và viӋc xҩp xӍ tùy ý gҫn phân bӕ cân Eҵng ÿӕi vӟi các xích nung luyӋn thuҫn nhҩt. Mӣ rӝng kӃt quҧ cӫa D. Mitra, F. Romeo và A. Sangiovanni-Vincentelli vӅ tính ergodic yӃu cӫa thuұt toán nung luyӋn không thuҫn nhҩt ÿӇ nhұn ÿѭӧc các kӃt quҧ vӅ sӵ hӝi tө cӫa thuұt toán không thuҫn nhҩt. Nhҵm thӇ nghiӋm, chúng tôi ÿã áp dͭng thu̵t toán SA vào m͡t Oͣp bài toán t͙i ˱u t͝ hͫp ÿL͋n hình là lͣp “bài toán l̵p l͓ch th͹c hi͏n công vi͏c- JSS”. 1͡i dung chính cͯa ÿ͉ tài: Phҫn I trình bày mӝt sӕ kӃt quҧ lý thuyӃt và ӭng dөng cӫa thuұt giҧi di truyӅn cҧi tiӃn theo xác suҩt ÿӝng phө thuӝc vào thӃ hӋ tiӃn hoá (DGA) và mҥng Qѫron (ANN). 3 Phҫn II trình bày mӝt sӕ kӃt quҧ lý thuyӃt vӃ phѭѫng pháp nung luyӋn mô phӓng (SA) và ӭng dөng cӫa SA vào bài toán lұp lӏch dòng công viӋc. Nhӳng thiӃu sót vӅ mһt hình thӭc lүn nӝi dung trong tұp báo cáo tәng kӃt ÿӅ tài này sӁ khó tránh khӓi. Nhóm tác giҧ rҩt mong ÿѭӧc sӵ góp ý cӫa ngѭӡi ÿӑc và trân trӑng cҧm ѫn. Chúng tôi cҧm ѫn trѭӡng Ĉҥi hӑc Ĉà Lҥt, Khoa Toán - Tin ÿã tҥo nhiӅu ÿLӅu kiӋn thuұn lӧi ÿӇ chúng tôi tiӃn hành và hoàn thành ÿӅ tài này. Ĉà Lҥt, tháng 3 năm 2007 Nhóm tác giҧ 4PḪN I 0ӝt sӕ kӃt quҧ vӅ thuұt giҧi di truyӅn và mҥng nѫron 5Ӭng dөng chiӃn lѭӧc ÿӝng trong thuұt giҧi di truyӅn giҧi mӝt lӟp bài toán tӕi ѭu toàn cөc Trѭѫng Chí Tín, Trҫn Ngӑc Anh Khoa Toán ± Tin, Ĉ̩i h͕c Ĉà L̩t E-mail:chitin@hcm.vnn.vn Tóm t̷t: Khi áp dͭng các thu̵t gi̫i di truy͉n (GA) c͝ÿL͋n cho bài toán t͙i ˱u toàn cͭc, quá trình tìm ki͇m lͥi gi̫i t͙i ˱u th˱ͥng g̿p h̩n ch͇ là t͙c ÿ͡ h͡i tͭ ch̵m và ÿ͡ chính xác cͯa lͥi gi̫i không cao. Ĉ͋ kh̷c phͭc h̩n ch͇ÿó, chúng tôi ÿ͉ ngh͓ áp dͭng chi͇n l˱ͫc ÿ͡ng theo xác sṷt vào phép lai c̫i ti͇n và ph˱˯ng pháp hi͏u ch͑nh tuy͇n tính Fͯa D.E.. Goldberg ÿ˱ͫc t͝ng quát hóa. K͇t qu̫ th͹c nghi͏m, khi gi̫i P͡t lͣp bài toán t͙i ˱u toàn cͭc vͣi ÿ̿c tr˱ng có r̭t nhi͉u c͹c tr͓ÿ͓a ph˱˯ng, cho th̭y ph˱˯ng pháp mͣi có ˱u ÿL͋m n͝i b̵t là t͙c ÿ͡ h͡i Wͭ nhanh và ÿ͡ chính xác cͯa lͥi gi̫i t͙i ˱u r̭t cao. 7ͳ khóa: Wӕi ѭu toàn cөc, GA, hiӋu chӍnh tuyӃn tính, lai. 1. MӢĈҪU Trong bài này chúng tôi áp dөng chiӃn lѭӧc ÿӝng vào toán tӱ lai và vào phân phӕi xác suҩt chӑn tұp con ÿӇ biӃn hóa và tái tҥo quҫn thӇ mӟi trong thuұt giҧi di truyӅn nhҵm giҧi bài toán tӕi ѭu toàn cөc sau ÿây: Bài toán: Cho hàm sӕ n biӃn thӵc f : D ® R, vӟi Õ = = n i ii baD 1 ],[ Í Rn. Tìm xoptÎD: f(xopt) = min{f(x), x Î D}. Khi áp dөng các phép biӃn hoá (lai, ÿӝt biӃn) và phân phӕi xác suҩt chӑn tұp con ÿӇ biӃn hóa và tái tҥo quҫn thӇ mӟi cәÿLӇn trѭӟc ÿây thѭӡng gһp hҥn chӃ là Wӕc ÿӝ hӝi tөÿӃn lӡi giҧi tӕi ѭu chұm và cho ÿӝ chính xác cӫa lӡi giҧi không cao. ĈӇ khҳc phөc hҥn chӃÿó, chúng tôi áp dөng chiӃn lѭӧc ÿӝng vào phép lai tҥo và phѭѫng pháp hiӋu chӍnh tuyӃn tính cӫa D. E. Goldberg ([GOL]) ÿѭӧc tәng quát hoá cho phân phӕi xác suҩt chӑn tұp con ÿӇ biӃn hóa và tái tҥo quҫn thӇ mӟi, nhҵm Pөc tiêu khoanh vùng cӵc trӏ toàn cөc ӣ giai ÿRҥn ÿҫu tiӃn hoá và tăng tӕc ÿӝ hӝi WөÿӃn lӡi giҧi tӕi ѭu ӣ giai ÿRҥn cuӕi theo tuәi cӫa thӃ hӋ tiӃn hoá. 2. CHIӂN LѬӦC ĈӜNG TRONG THUҰT GIҦI DI TRUYӄN 2.1. Toán tӱ lai tҥo ÿӝng 6*ӑi t, T lҫn lѭӧt là thӃ hӋ hiӋn tҥi và thӃ hӋ cuӕi cùng cӫa quá trình tiӃn hoá; F0: D ® [0; 1] là hàm thích nghi chuҭn hóa cӫa cá thӇ. Cho 2 cá thӇ tiӅn bӕi p1, p2 Î D, không giҧm tәng quát, ta có thӇ gLҧ sӱ p1 là cá thӇ trӝi (p1 có ÿӝ thích nghi F0 cao hѫn p2: F0(p1) ³ F0(p2)). Trong phép lai c͝ÿL͋n theo ki͋u s͙ h͕c thì: ch1 = p1 + Ș*d’, (2.0) ch2 = p1 + (1-Ș)*d’, trong ÿó: d’ = (p2 – p1), Ș = random(0;1) là mӝt sӕ ngүu nhiên thuӝc khoҧng (0; 1). Chúng tôi ÿӅ nghӏ toán t͵ lai ÿ͡ng theo xác sṷt sӁ tҥo ra 2 cá thӇ con ch1, ch2 nhѭ sau: ch1 = p1 + q(t)*d(t) (2.1) ch2 = p2 - q(t)*d(t) Yӟi: î í ì - = )(p,),'min().( )(p-1,' )( 021 tppsign t t suaátxaùcvôùi suaátxaùcvôùi dd d d (2.2) trong ÿó: d’ = (p2 – p1), î í ì £- >- = 121 121 0 if, if, pppb ppap d a = (a1, …, an), b = (b1, …, bn), ½d’½ = (½d’1½, …, ½d’n½), p(t) = End_pLai_Dong + q(t)*(Beg_pLai_Dong - End_pLai_Dong), q(t) = g(t, r), (2.3) Beg_pLai_Dong và End_pLai_Dong thuӝc [0; 1], p(t) là xác suҩt ÿӝng lai ngoài ÿRҥn tiӅn bӕi, r = random(0; 1) là mӝt sӕ ngүu nhiên thuӝc khoҧng (0; 1); các phép toán “+”, “-”, min và quan hӋ hai ngôi “>” trên các vectѫÿѭӧc thӵc hiӋn theo các phép toán và quan hӋ tѭѫng ӭng trên tӯng tӑa ÿӝ. Hàm g: [0; T]x[0; 1] ®[0;1], phө thuӝc tuәi tiӃn hoá t, ÿѭӧc chӑn sao cho: g(t, .) ¯ 0 khi t ® T, chҷng hҥn ta thѭӡng chӑn: g(t, r) = r*(1 – t/T)g hoһc gt/T)-(1r-1r)g(t, = nhѭ trong [2], vӟi g là hҵng Vӕ dѭѫng nào ÿó. Khi ÿó: ch1, ch2 lҫn lѭӧt sӁ gҫn cá thӇ trӝi hoһc lһn tѭѫng ӭng khi t ® T (giai ÿRҥn cuӕi cӫa quá trình tiӃn hóa). 2.2. Phѭѫng pháp hiӋu chӍnh tuyӃn tính ÿӝng Giҧ sӱ quҫn thӇ ban ÿҫu gӗm N cá thӇ. F0 = { }NiiF 1,0 = là ÿӝ thích nghi chuҭn hoá cӫa các cá thӇ thӭ i (i = 1..n): 1 1 .0 =å = N i iF , do ÿó { }NiiF 1,0 = là mӝt phân phӕi xác suҩt (PPXS). *ӑi P là ÿӝ thích nghi chuҭn hoá mӟi (hoһc PPXS mӟi) bҵng cách hi͏u ch͑nh tuy͇n tính (HCTT) ÿӝ thích nghi chuҭn hoá F0: P = a*F0 + b, (2.4) sao cho: E(P) = E(F0): (E là toán tӱ trung bình) (2.5) 7 PMax = C*E(F0), (2.6) Yӟi C Î (1; C0], C0 là mӝt hҵng sӕ lӟn hѫn 1 (trong phѭѫng pháp HCTT truyӅn thӕng, D.E. Goldberg luôn chӑn C0 Eҵng 2), a và b là các hҵng sӕ. Trong phҫn này, chúng tôi sӁ kh̫o sát tính ch̭t co, giãn cͯa PPXS mͣi P so vͣi PPXS cNJ F0 phͭ thu͡c vào tham s͙ C0 t͝ng quát. Giҧ sӱ daõy { }N ii F 1,0 = khoâng ñoàng nhaát laø haèng, gӑi: ., 1 ,1, )1( ,11},..1,min{},..1,{ min2 0 0 ,1 min min 0 min0 1 .0,0min,0 0 0 F C FCF FF FF F FA C FCFTB N F N FNiFFNiFMaxF Max C MaxMaxMax C N i iiiMax -= - - = - - =D£=< -+ = ====== å = bb (2.7) Chӑn ïî ï í ì ³ < = )B(if, )(if, 0 00 2 ,1 caseTBF AcaseTBF C CC b b b . (2.8) 'Ӊ dàng chӭng minh hai khҷng ÿӏnh sau: 0͏nh ÿ͉ 1: Giҧ sӱ daõy { }N ii F 1,0 = khoâng ñoàng nhaát laø haèng. (2.9) NӃu chӑn: )( b+ = F Fa , b = ab, (2.10) thì PPXS mӟi P xác ÿӏnh theo (2.4) sӁ thӓa các ÿLӅu kiӋn (2.5) và (2.6). 9̭n ÿ͉ÿ̿t ra là n͇u áp dͭng liên ti͇p phép HCTT (2.4) qua các th͇ h͏ ti͇n hóa, thì vͣi các ÿL͉u ki͏n xác ÿ͓nh nào, dãy các PPXS mͣi sͅ h͡i tͭÿ͇n PPXS giͣi K̩n ? Ĉһt: î í ì =³"+== ºº -- NimbYaYFY FXY m i m i m i iii ..1,1,.)( )1()1()( ,0 )0( (2.11) 7ӯ nay vӅ sau, ta luôn gi̫ s͵ các gi̫ thi͇t (2.9) và (2.10) cͯa m͏nh ÿ͉ 1 ÿ˱ͫc th͗a mãn. 0Ӌnh ÿӅ 2 dѭӟi ÿây chӍ ra mӕi liên quan giӳa viӋc chӑn các hӋ sӕ a, b vӟi tính chҩt co hoһc giãn cӫa PPXS mӟi. 0͏nh ÿ͉ 2: Vӟi mӑi m > 0, a) NӃu a > 1 Û b < 0 8ï ï î ïï í ì ê ê ë é D³ D< < > Û - -- - caseBC caseAC C X Y Y m mm m : : : 0 )1( 0 )1( 0 0 )1( max )1( min Û )1(max )( max -> mm YY Û )1(min )( min -< mm YY thì: " i = 1..N )()1()1( m i m i m i YYXXY -- )()1()1( m i m i m i YYXXY >>Û< -- Khi ÿó, cách chӑn này sӁ làm tăng (giãn) hoһc giҧm khҧ năng chӑn hѫn nӳa cho các cá thӇ có ÿӝ thích nghi cao hoһc thҩp tѭѫng ӭng. b) NӃu 0 < a < 1 caseA X Y C m m :)(10 )1( )1( max 0 - - D£Û b Û )1(max )( max -< mm YY Û )1(min )( min -> mm YY thì: " i = 1..N )()1()1( m i m i m i YYXY >Û> -- )()1()1( m i m i m i YYXY <Û< -- Khi ÿó, cách chӑn này sӁ làm giҧm (co) hoһc tăng khҧ năng chӑn hѫn nӳa cho các cá thӇ có ÿӝ thích nghi cao hoһc thҩp tѭѫng ӭng. c) a = 1 Û b = 0 ê ê ê ê ê ê ê ê ë é ï î ï í ì D<= > ï î ï í ì D=³ = Û - - - - - - caseA X Y C Y caseB X Y C Y m m m m m m :)( 0 : 0 )1( )1( max 0 )1( min )1( )1( max 0 )1( min Khi ÿó, F là ánh xҥÿӗng nhҩt (các PPXS mӟi và cNJ trùng nhau, cҫn chӑn C0 ÿӇ tránh trѭӡng hӧp này xҧy ra). Hai m͏nh ÿ͉ sau cho th̭y m͡t s͙ tính ch̭t cͯa PPXS mͣi tùy theo cách ch͕n C0: n͇u ch͕n C0 luôn theo m͡t s͙ qui lu̵t xác ÿ͓nh nào ÿó thì dãy PPXS mͣi P sͅ K͡i tͭ v͉ các PPXS xác ÿ͓nh. 90͏nh ÿ͉ 3: Giҧ sӱ 0min)0(min >= XY và luôn chӑn 1,)(0 ³"kC k thӓa mӝt trong hai trѭӡng hӧp sau: 1) ),1( )1( )( 0 X Y C k Maxk - Î : )1(1 )1( )( 0 -+= - X Y C k Maxk q , vӟi )1;0(Îq Fӕÿӏnh. Khi ÿó: a. X kC q q bb - == 1)( 0 1 , a = )1;0(Îq b. ¥®¯-+==-+= - kXXXXYY kMaxkkMaxkMax ,)1(...)1()1()( qqqq (2.12) ¥®­-+==-+= - kXXXXYY kkkk ,)1(...)1( min )1( min )( min qqqq (2.13) c. NikXY ki ..1,,)( ="¥®® . Cө thӇ hѫn, Ni ..1=" NӅu XX i £ thì 1,)( ³"£ kXY ki và ¥®­ kXY ki ,)( NӃu XX i ³ thì 1,)( ³"³ kXY ki và ¥®¯ kXY ki ,)( d. ¥®®D=-ºD kaYY ijkkjkiijk ,00)()( , Nji ..1, =" . Không giҧm tәng quát, ta có thӇ giҧ sӱ rҵng NiiX 1}{ = là dãy tăng, khi ÿó NikiYk 1)( }{,1 =³" cNJng là dãy Wăng và ¥®®-=D=- + - = å kXXaYY Nkiik N i kk N ,0)( 1 ,1 1 1 )( 1 )( e. ,1)(0 ®kC ¥®k 2. ),( )1( )1( )( 0 - - DÎ k k Maxk X Y C : )1( min )1( min )1( )1( - -- - - - =D k kk Maxk YX YY )( )( )( )1( min )1()1( min )1()1( )1( )1( )( 0 - ---- - - - - +=-D+= k k Max kk Max k Maxk k Maxk YXX XYY X Y X Y X Y C ll , vӟi )1;0(Îl Fӕ ÿӏnh. Khi ÿó: a. )1( min )1( min 1 )( )1( )( 0 - - -- - == k k Ck YX YXk l l bb , );1(1 )1( min )1( min )1( min)( -- - - Î - += kk k k YX X YX Ya l b. Ĉһt )1;0(1 Î-= lq , khi ÿó: "i =1..N ¥®=¯== ¥- kYXYY kkk ,0)(minmin )1( min )( min qq (2.14) ¥®- - º® ¥ kXX XX XYY ii k i ),( min min )()( (2.15) 10 Ĉһc biӋt: ¥®D=- - º­ ¥ kXXX XX XYY MaxMax k Max ,)( )0( min min )()( , (2.16) c. Ni ..1=" : )(kiY hӝi tө khi ¥®k ; cө thӇ hѫn: NӃu XX i ³ thì )(kiY Kӝi tөÿѫn ÿLӋu tăng (vӅ mӝt trӏ ³ X ) khi ¥®k . NӃu XX i £ thì )(kiY Kӝi tөÿѫn ÿLӋu giҧm (vӅ mӝt trӏ£ X ) khi ¥®k . d. X Y C Maxk )( )( 0 ¥ ® , 1)( ¯ka , 0)( ®kb , ¥®k Chͱng minh: 1) . Các kӃt luұn 1.a và 1.b là dӉ dàng chӭng minh. . KӃt luұn 1.c ÿѭӧc suy ra tӯ tính chҩt cӫa giӟi hҥn kҽp và phѭѫng pháp chӭng minh phҧn chӭng. . KӃt luұn 1.d là dӉ dàng chӭng minh. . KӃt luұn 1.e ÿѭӧc suy ra tӯÿӏnh nghƭa cӫa )(0kC và kӃt luұn 1.b. 2) . KӃt luұn 2.a là dӉ dàng chӭng minh. . ĈӇ chӭng minh kӃt luұn 2.b, trѭӟc tiên ta nhұn xét rҵng vӟi: )1( min )1( min )( )( )( - - - - = + = k k k k k YX Y X l b b h thì: ¥®¯==== <=-=-+=D+= - ------- kXYYY YYYYXYYY kkkk kkkkkkkkk ,0.... )1()( min )0( min )1( min )( min )1( min )1( min )1( min )1( min )()1( min )1( min )1( min )( min qqq qlh 7ѭѫng tӵ: " i0 = 1..N: k k ik k i kk i k i k i k i BYA YXYYY += -+=D+= +++ )( 0 )( 0 )1()( 0 )1( 0 )( 0 )1( 0 )(h Yӟi: min min)( min )( min min min 1 )( min )( min , XX XX YX YXB XX XX YX YXA k k k k k k k k k k q q l l q qq - -= - -= - - = - - = + 'Ӊ dàng suy ra: ï ï î ï ï í ì - - þ ý ü î í ì - - -= ++= + - = +== + å ÕÕ min minmin min 0 min 1 1 0 1 0 0 )1( 0 ~)( )()( XX XXCXX XX XXX BBAXAY k k kik k j kj k ji ii k i i k i q q llq q Yӟi: 11 ¥®®> - == å Õ - = + = jkhiv XX vvC j k j j ji i j jj k ,0,0 )( ,~ 1 0 1 minq q q Do: ¥®<®+ jkhi v v j j ,11 q nên chuӛi sau hӝi tө : ¥<= å ¥ =0 0 j jvC và do ÿó: ¥®- - =® ¥ kCXX XX XXYY ii k i ),( min min 0)( 0 )( 0 ql 1Ӄu chӑn i0ÿһc biӋt: xi0 = xmin thì: )( 10 min )( 0 XXX CYi - =Þ=¥ lq => (2.15) và (2.16) (CNJng có thӇ suy ra kӃt quҧ trên tӯÿLӅu kiӋn: å = ¥ = N i iY 1 )( 1) . KӃt luұn 2.c ÿѭӧc suy ra tӯ tính chҩt hӝi tөÿѫn ÿLӋu, bӏ chһn. . KӃt luұn 2.d ÿѭӧc suy ra tӯ các kӃt luұn 2.a và 2.b. 0͏nh ÿ͉ 4: Giҧ sӱ 0min0min >= XY và luôn chӑn 0,, )12(0)2(0 ³"+ kCC kk luân phiên nhѭ sau: + 0)2(min >kY , chӑn: )2()2( 0 kkC D= , )1( )2( )2( min )2( min )2( )2( >> - - =D X Y YX YY kMax k kk Maxk )1,0( 2 )2( min2 )2( ><-== k kk aYbb Khi ÿó: ïî ï í ì ³" >D=D= <= + + )182.( )172.( 0, )( )(0 )2()0()2()12( )2( min )12( min k YXXY YY k Max kk Max kk Nghƭa là: các dãy chӍ sӕ lҿӭng vӟi )(min)( , kkMax YY là các dãy hҵng. + TiӃp tөc, chӑn: )1;0(),1(1: 12 )12( 12 )12( 0 )12( )12()12( 0 Î-+==D< + + + + + ++ k k Max k k k Maxkk X Y C X Y C qq 1)12(0 )12( 0 )12( 1 )12( )12(0 - - == + ++ + + k kk MaxCk C XCYk bb . Khi ÿó: 10 1212 <=< ++ kka q Khi ÿó: 12 )202.( )192.( 0),0()1( )1()1( 12 min12 )22( min 12 min 12 )12( 12 )22( ï î ï í ì ³"=>-= + - - =-+= + + + ++ + + + kYXY X XX XXXYY k k k k Max k k Maxk k Max q qqq Xét các dãy chӍ sӕ chҹn ӭng vӟi )(min)( , kkMax YY : )22( += kMaxk Yu tăng, 0,)22(min ³= + kYv kk giҧm: )(),( )(),( )2( min )22( min )2()22( 1212 )2( min )22( min )2()22( 1212 ­>¯<Û< ¯Û> ++ -+ ++ -+ k kk k k Max k Maxkk k kk k k Max k Maxkk vYYuYY vYYuYY qq qq 9ұy nӃu lҩy 012 }{ ³+ kkq là dãy luôn ÿѫn ÿLӋu thì ta luôn có hai dãy chӍ sӕ chҹn 0 2 0 2 min }{,}{ ³³ k k Maxk k YY hӝi tө. . NӃu ¥®­+ kkhik ,112q thì: ïî ï í