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

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ì: ïî ï í ì ¯= £D­= + + 0 )1( )22( min 0)22( k k x k Maxk Yv XYu (2.21) . NӃu ¥®¯+ kkhik ,012q thì: ïî ï í ì ­= ¯= + + XYv XYu k k k Maxk )22( min )22( (2.22) Chͱng minh: . (2.17) và (2.20) là hiӇn nhiên. . Chӭng minh (2.19): Ta có [ ] )1()0(0)1( )0()1(0)1( )2( min 12 )2( min12 )2( min )22( min )2( min 1212 )2( min)2( min )2( )2()22( < - --=- > - >>Û>-- - - =- ++ + ++ + X YXYXYY X YXXY YX XY YY k k k k kk k kk k k k Maxk Max k Max qq qq max0)2( min )2( 12)22( 1 ,0,. )( XukBuA YX XYX XYu kkkk k Maxkk Maxk =³"+=- - +== +++ q , Yӟi: ï ï î ï ï í ì -=-= - -- = = - >Û> - == - = - ++ -+- - ++ )1()1( ])1([ 1,, 12 12 )2( min )2( min12 12 )2( min 12 min 1 12 12 )2( min 12 k k kk k k k k k kk k k k k k XAX YX YXXB X YXA X XX YX X A q qq qqq q qq 13 9ұy vӟi chӍ sӕ chҹn 2k, 02min >kY , ta có: )(),(:)1(1 )(),(:)1(1 )2( min )22( min )2()22( 12 )2( min 12 )2( min )22( min )2()22( 12 )2( min 12 ­>¯<<= - <Û< ¯= - >>Û> ++ -+ ++ -+ k kk k k Max k Maxk k kk k kk k k Max k Maxk k kk vYYuYY X YXA vYYuYY X YXA qq qq XX XX XX XXX BBAuAu k Max k k k j jj k k k j kj k ji i k i ik + - - = -+-+= ++=Þ + - + - = -+ + - + - = +== + å å ÕÕ 12 min 12 12 1 0 1212 12 1 12 max 1 0 1 0 0 1 )1()11( )()( q q q qq q q q . Chӭng minh (2.18): )2()12( kkMAx XY D=+ Do (2.19), (2.20), nên: )0( min )2( min )2( min )2( )2( 1 D=+ - - = - - =D XX XX YX YY Max k kk Maxk Vұy: )0()12( D=+ XY kMax . (2.21) và (2.22) ÿѭӧc suy ra trӵc tiӃp tӯ (2.19), (2.20). Các kӃt quҧ trên cho ta cѫ sӣ, ÿӇ vӟi tӯng bài toán cө thӇ, hiӋu chӍnh xác suҩt chӑn các cá thӇ bҵng cách chӑn C0(t) phù hӧp, nhҵm co hoһc giãn ÿӝ thích nghi quanh trӏ trung bình cuҧ chúng (tùy theo giá trӏ cӫa C0(t) so vӟi A và D) theo tuәi Fӫa thӃ hӋ tiӃn hóa. Ĉó chính là ý tѭӣng cӣ bҧn cӫa phѭѫng pháp hiӋu chӍnh tuyӃn tính ÿӝng cҧi tiӃn. Trong thӵc tӃ, ta thѭӡng không luôn chӑn trong suӕt quá trình tiӃn hóa C0(t) thuӝc chӍ mӝt trong các trѭӡng hӧp cӫa hai mӋnh ÿӅ 3 và 4, nhҵm Yӯa bҧo ÿҧm tính ÿa dҥng cӫa quҫn thӇ mӟi và ÿLӅu chӍnh áp lӵc chӑn lӑc cho cá thӇ theo tuәi cӫa thӃ hӋ tiӃn hóa nhҵm tăng tӕc ÿӝÿӃn lӡi giҧi tӕi ѭu. Chҷng hҥn, ta có thӇ chӑn: ï î ï í ì D-+D -+= ))(op_C_Dong_C-(1*))(p_C_Tinh-(1),)(( )(op_C_Dong_C*))(p_C_Tinh-(1),1)((1)(0 ttAt ttAttC suaátxaùcvôùi suaátxaùcvôùi Tinh(t)suaát p_C_xaùcvôùi2, q q (2.23) trong ÿó: p_C_Tinh(t) = End_p_C_Tinh + q(t)*(Beg_p_C_Tinh - End_p_C_Tinh), p_C_Dong_Co(t) = End_p_C_Dong_Co + q(t)*(Beg_p_C_Dong_Co - End_p_C_Dong_Co), Beg_p_C_Dong_Co, End_p_C_Dong_Co, Beg_p_C_Tinh 14 và End_p_C_Tinh là các hҵng sӕ thuӝc [0; 1], A và D ÿѭӧc xác ÿӏnh theo (2.7); q(t) = gt/T)-(1*rr)g(t, =  ÿѭӧc xác ÿӏnh theo (2.3). Khi Beg_p_C_Tinh = End_p_C_Tinh = 1, ta thu ÿѭӧc phѭѫng pháp HCTT cәÿLӇn cӫa D.E. Goldberg. 3. KӂT QUҦ THӴC NGHIӊM Qua thӵc nghiӋm, chúng tôi ÿã so sánh các thuұt giҧi di truyӅn cәÿLӇn GA Yӟi thuât giҧi di truyӅn ÿӝng DGA cҧi tiӃn trên cho lӟp các bài toán tӕi ѭu toàn Fөc, vӟi ÿһc ÿLӇm có rҩt nhiӅu cӵc trӏÿӏa phѭѫng, trong [PEN]. Sau ÿây là mӝt trong sӕ các bài toán ÿó: * Bài toán 1: Tìm f(x*) = min {f(x), x Î D}, x* Î D = [a, b]n, nÎN, })](sin1[)](sin1[)({sin)( 1 1 1 2 5 2 10 2 5 2 10 2 4 å - = + ++++= n i nnii ylkyylkyylkxf ppp Yӟi: k4 = 0.1, k5 = 1, l0 = 3, l1 = 2, yi = xi - i, i = 1..n, (a < 0 < n < b). (3.1) Khi ÿó, bҵng phѭѫng pháp lý thuyӃt, ta xác ÿӏnh ÿѭӧc: x* = {1, 2, …, n}, f(x*) = 0. Xét bài toán, vӟi n=10, D = [a; b] = [-10; 50]n; N = 50 cá thӇ, các xác xuҩt lai và ÿӝt biӃn: p_Lai = 0.80; p_DotBien = 0.10; Oҩy kӃt quҧ trung bình trong 50 lҫn chҥy thӱ nghiӋm, chѭѫng trình ÿѭӧc viӃt trên ngôn ngӳ VC++, trong 3 trѭӡng hӧp sau ÿӇ so sánh: A. Thu̵t gi̫i di truy͉n c͝ÿL͋n: vӟi hai trѭӡng hӧp: T1 = 1500, T2=1000 thӃ hӋ, kiӇu lai sӕ hӑc thông thѭӡng trên ÿRҥn tiӅn bӕi, phѭѫng pháp hiӋu chӍnh tuyӃn tính cӫa D. E. Goldberg (vӟi C0 = 2). B. Thu̵t gi̫i di truy͉n ÿ͡ng c̫i ti͇n: vӟi T = 1000 thӃ hӋ, kiӇu lai ÿӝng (2.1)-(2.3) vӟi các mút xác suҩt ÿӝng lai ngoài ÿRҥn tiӅn bӕi Beg_pLai_Dong = 0.4, End_pLai_Dong = 0.7, q = gt/T)-(1*rr)g(t, = , g = 4; trong phѭѫng pháp hiӋu chӍnh tuyӃn tính ÿӝng (2.4) - (2.6), chúng tôi chӑn C0 theo (2.23), vӟi: Beg_p_C_Tinh = 0.3 End_p_C_Tinh = 0.6, Beg_p_C_Dong_Co = 0.2, End_p_C_Dong_Co = 0.2, A và D ÿѭӧc xác ÿӏnh theo (2.7); q(t) = gt/T)-(1*rr)g(t, = ÿѭӧc xác ÿӏnh theo (2.3) vӟi g = 4. C. Trong thӵc tӃ, ÿӇ Wăng t͙c ÿ͡ và ÿ͡ chính xác Fӫa lӡi giҧi tӕi ѭu, sau khi thӵc hiӋn thuұt giҧi di truyӅn ÿӝng cҧi tiӃn mӝt lҫn, nӃu dùng thêm ph˱˯ng pháp leo ÿ͛i (chҥy thêm chѭѫng trình vài lҫn, chҷng hҥn 2 lҫn nӳa vӟi bài toán (3.1), nhѭng mӛi lҫn chҥy vӟi T = 700 bé hѫn) ÿ͋ co h́p d̯n mi͉n tr͓ÿ̯u vào D quanh lân c̵n cͯa giá tr͓ t͙i ˱u Fӫa lҫn chҥy trѭӟc Yͣi các bán kính nh͗ d̯n phù hӧp thì ta thu ÿѭӧc Oͥi gi̫i t͙i ˱u x0 có ÿ͡ chính xác r̭t cao Ňx0[i]-iŇ<10-9, i=1..n;f(x0) §2e-19=2*10-19). 15 *ӑi E, D, Tot_f, Xau_f lҫn lѭӧt là giá trӏ trung bình, phѭѫng sai, giá trӏ tӕt nhҩt, xҩu nhҩt cӫa hàm mөc tiêu f trong 50 lҫn thӱ nghiӋm các thuұt toán; T, ET Oҫn lѭӧt là sӕ thӃ hӋ tӕi ÿa cӫa quá trình tiӃn hóa và thӡi gian trung bình mӛi lҫn chҥy tính theo giây trên máy PC Pentium IV, 1.8 GHz, 256Mb RAM. KӃt quҧ thӱ nghiӋm cӫa bài toán trên ÿѭӧc cho trong E̫ng 1 dѭӟi ÿây: Trѭӡng hӧp E D Tӕt_f Xҩu_f T ET(s) Tr͓ chính xác 0 A1 6e-2 7e-3 3e-5 4e-1 1500 38 A2 3e-1 1e-1 5e-4 1.5 1000 24 B 4e-11 1e-16 2e-12 5e-10 1000 24 C 2e-19 1000 50 %̫ng 1 (K͇t qu̫ cho bài toán 3.1) /ѭu ý rҵng, trong trѭӡng hӧp A1, dù ta kéo dài quá trình tiӃn hóa (cho T lӟn Kѫn), thӡi gian thӵc hiӋn chѭѫng trình thұt lâu chăng nӳa, thì các giá trӏ tӕi ѭu cӫa Oӡi giҧi cNJng không cҧi thiӋn ÿѭӧc thêm bao nhiêu ! KӃt quҧ trong trѭӡng hӧp [̭u nh̭t (trong 50 l̯n th͵) khi dùng thu̵t gi̫i di truy͉n ÿ͡ng c̫i ti͇n ÿҥt ÿӝ chính xác cao, trѭӡng hӧp B: 5e-10) W͙t h˯n h̻n tr˱ͥng hͫp t͙t nh̭t khi dùng thu̵t gi̫i di truy͉n c͝ÿL͋n (trѭӡng hӧp A2: 5e-4). Ph˱˯ng sai cͯa f(x*) trong trѭӡng hӧp B Ṷt bé (1e-16), chӭng tӓ thu̵t gi̫i DGA c̫i ti͇n r̭t ͝n ÿ͓nh. Khi n=20, ta cNJng có kӃt quҧ tѭѫng tӵ nhѭ trên. Khi n=50, D = [a; b] = [-10; 80]n; N = 100 cá thӇ, T = 4000 thӃ hӋ, các xác xuҩt lai và ÿӝt biӃn: p_Lai = 0.80; p_DotBien = 0.10; QӃu áp dөng chiӃn lѭӑc co miӅn trӏ mӝt lҫn vӟi bán kính r = 1e-4 quanh nghiӋm tӕi ѭu cӫa thuұt giҧi di truyӅn ÿӝng cҧi tiӃn DGA, sau T = 27 phút, ta thu ÿѭӧc Oͥi gi̫i t͙i ˱u x0 có ÿ͡ chính xác Ṷt cao Ňx0[i]-iŇ<10-10, i=1..n;f(x0) §1e-20=1*10-20). Qua th͵ nghi͏m trên nhi͉u bài toán t͙i ˱u toàn cͭc khác có rҩt nhiӅu cӵc trӏ ÿӏa phѭѫng trong [PEN], chúng tôi FNJng nh̵n th̭y thu̵t gi̫i di truy͉n ÿ͡ng c̫i ti͇n b̹ng toán t͵ lai ÿ͡ng cùng vͣi ph˱˯ng pháp hi͏u ch͑nh tuy͇n tính ÿ͡ng c̫i ti͇n t͙t h˯n h̻n so vͣi thu̵t gi̫i di truy͉n c͝ÿL͋n (c̫ v͉ÿ͡ chính xác cͯa lͥi gi̫i W͙i ˱u cNJng nh˱ thͥi gian ch̩y máy ÿ͋ÿ̩t cùng m͡t ÿ͡ chính xác nh̭t ÿ͓nh). * Bài toán 2 (Lennard Jones)[BAR]: Xét hàm Lennard Jones: å £<£ -= nji ji xxvxf 1 )()( Yӟi: 612 21)( dd dv -= ; x1, …, xn Î R3, · là chuҭn Euclide. 16 Tìm x*: f(x*) = min f(x) trên mi͉n: {xi ¹ xj ,1 £ i <j £n, x1, «, xn Î R3} (3.2) Xét 2 trѭӡng hӧp sau ÿӇ so sánh: C_1: Dùng thuұt giҧi di truyӅn GA cәÿLӇn và chiӃn lѭӧc co miӅn trӏÿҫu vào. C_2: Dùng thuұt giҧi di truyӅn ÿӝng DGA cҧi tiӃn và chiӃn lѭӧc co miӅn trӏ ÿҫu vào. + Khi n = 12, kӃt quҧ thӵc nghiӋm ÿѭӧc cho trong E̫ng 2, vӟi N = 20 cá thӇ, T=1000 thӃ hӋ, các xác xuҩt lai và ÿӝt biӃn: p_Lai= 0.80; p_DotBien= 0.10; Oҩy NӃt quҧ trung bình trong 5 lҫn chҥy thӱ nghiӋm: Tr˱ͥng hͫp C_2 C_1 E -36.131389676596832 -31.430019274588847 D 1.183218505291279 1.691729299528788 7͙t_f -37.967599562356760 -32.983889826764930 ;̭u_f -34.658625781053701 -30.108173710180370 ET(s) 8:12 8:06 %̫ng 2 (K͇t qu̫ cho bài toán 3.2, khi n=12) + Khi n = 13 (tuân theo qui lu̵t: n = 1+(10*i3+15*i2 +11*i)/3, iÎN [XUE]), NӃt quҧ thӵc nghiӋm ÿѭӧc cho trong E̫ng 3, vӟi N = 20 cá thӇ, T=1000 thӃ hӋ, các xác xuҩt lai và ÿӝt biӃn: p_Lai= 0.80; p_DotBien= 0.10; Oҩy kӃt quҧ trung bình trong 10 lҫn chҥy thӱ nghiӋm: Tr˱ͥng hͫp C_2 C_1 E -44.326801419531904 -44.326703511176127 D 0.000000000000000 0.000000027034503 7͙t_f -44.326801419533787 -44.326801312833396 ;̭u_f -44.326801419528799 -44.326319979035588 ET(s) 5:14s 4:16s %̫ng 3 (K͇t qu̫ cho bài toán 3.2, khi n=13) /ѭu ý rҵng, viӋc ÿҥt ÿѭӧc ÿӝ chính xác càng cao cho hàm mөc tiêu f(x*) là càng khó và chiӃm thӡi gian rҩt lӟn ÿӇ chҥy chѭѫng trình. Giá trӏ tӕi ѭu cӫa hàm Pөc tiêu trong tr˱ͥng hͫp x̭u nh̭t cͯa C_2 v̳n t͙t h˯n tr˱ͥng hͫp t͙t nh̭t cͯa C_1; ph˱˯ng sai cͯa f(x*) trong trѭӡng hӧp C_2 bé h˯n h̻n so vͣi trѭӡng hӧp C_1, chͱng t͗ thu̵t gi̫i DGA c̫i ti͇n là t͙t và ͝n ÿ͓nh hѫn hҷn thuұt giҧi GA FӕÿLӇn! 17 4. KӂT LUҰN .Ӄt quҧ thӵc nghiӋm trên mӝt lӟp bài toán tӕi ѭu toàn cөc, vӟi ÿһc ÿLӇm có Uҩt nhiӅu cӵc trӏÿӏa phѭѫng, cho thҩy thuұt giҧi di truyӅn cҧi tiӃn theo xác suҩt ÿӝng tӕt hѫn hҷn thuұt giҧi di truyӅn cәÿLӇn. /ӠI CҦM ѪN Qua bài báo này, các tác giҧ muӕn chuyӇn lӡi cҧm ѫn ÿӃn các bҥn ÿӗng nghiӋp cӫa khoa Toán – Tin và trѭӡng Ĉҥi hӑc Ĉà Lҥt ÿã tҥo ÿLӅu kiӋn ÿӇ chúng tôi hoàn thành bài báo. TÀI LIӊU THAM KHҦO [BAR] C. Barrón, S. Gomez, D. Romero, A. Saavedra, ‘A Genetic algorithm for Lennard-Jones atomic clusters¶, Applied Mathematics Letters, No 12, p. 85-90, 1999. [GOL] D. E. Goldberg, 'Genetic algorithms In search, optimization, and machine learning', Addison Wesley Publishing Company, 1989. [HOL] J. H. Holland, µAdaption in natural and artificial systems¶, The MIT Press, Cambridge, Massachusetts, London, 1975. [LEA] Robert H. Leary, µGlobal optima of Lennard-Jones Clusters¶, Journal of global optimization, 11, 35-53, 1997. [MIC] Z. Michalewicz, µGenetic algorithms + data structures = evolution programs¶, Springer-Verlag, 1994. [PEN] F. A. Pentini, V. Parisi and F. Zirilli, µGlobal optimization and stochastic differential equations¶, Journal of optimization theory and applications, vol. 47, No. 1, september, 1985. [TAO] P. D. Tao, L. T. H. An, µDCA for computing global minima of the Lennard- Jones potential energy Function¶, 2004. [XUE] G.L. Xue, µMinimum inter-partical distance at global minimizers of Lennard-Jones Clusters¶, Journal of global optimization, 11, 83-90, 1997. APPLY DYNAMIC STRATEGY TO SOLVE A CLASS OF GLOBAL OPTIMIZATION PROBLEMS IN GENETIC ALGORITHMS Abstract: In application of classical genetic algorithms for solving global optimization problems, their optimal solutions are often achieved with slow speed and low precision level. To overcome these sistuations, we propose using a dynamic probabilitic strategy with respect to improved-crossover and generalyzed 18 Golberg's adjust linear method. Experiments on a class of optimization problems which have large number of local optimal show that our method has a remarkable advantage: the fast converge speed and high precision level of their optimal solutions. 19 &ҧi thiӋn khҧ năng hӑc cӫa Pҥng nѫ ron truyӅn thҷng nhiӅu lӟp Trҫn Ngӑc Anh, Trѭѫng Chí Tín Khoa Toán ± Tin, Ĉ̩i h͕c Ĉà L̩t E-mail: ngocanhdalat@yahoo.com , chitin@hcm.vnn.vn Tóm t̷t: Khi áp dͭng m̩ng n˯ ron truy͉n th̻ng nhi͉u lͣp vào bài toán tìm quy lu̵t G ÿ͋ x̭p x͑ quy lu̵t F mà ta c̫m giác nó di͍n t̫ m͙i liên h͏ phͭ thu͡c giͷa m͡t s͙ thành ph̯n này vào m͡t s͙ thành ph̯n khác trên m͡t t̵p Gͷ li͏u S lͣn cho tr˱ͣc, ta th˱ͥng g̿p h̩n ch͇ là quy lu̵t G thu ÿ˱ͫc có kh̫ Qăng d͹ báo (trên các th͋ hi͏n mͣi S¶ cͯa F trong t˱˯ng lai) không cao và thͥi gian ÿ͋ cho m̩ng h͕c th˱ͥng r̭t lͣn, ÿ̿c bi͏t là khi mi͉n tr͓ÿ̯u ra lͣn. Ĉ͋ kh̷c phͭc các h̩n ch͇ÿó, chúng tôi ÿ͉ ngh͓ các ph˱˯ng pháp sau ÿ͋ c̫i thi͏n kh̫ năng h͕c cͯa m̩ng n˯ ron: (1) áp dͭng ph˱˯ng pháp h͕c các tham s͙ cͯa hàm nén thông tin (hàm logistic) k͇t hͫp vͣi vi͏c co phi tuy͇n (thay vì co tuy͇n tính nh˱ truy͉n th͙ng) mi͉n tr͓ÿ̯u ra (b̹ng hàm lNJy thͳa); và (2) dùng thu̵t gi̫i di truy͉n vͣi phép lai ÿ͡ng c̫i ti͇n ÿ͋ t͙i ˱u hóa qu̯n th͋ các tham s͙ cͯa m̩ng n˯ ron, sau ÿó ch͕n ra b͡ tham s͙ t͙t nh̭t ÿ͋ cho P̩ng h͕c. K͇t qu̫ th͹c nghi͏m cho th̭y quy lu̵t tìm ÿ˱ͫc khi áp dͭng các ÿ͉ ngh͓ trên t͙t h˯n so vͣi ph˱˯ng pháp truy͉n th͙ng (riêng kͿ thu̵t h͕c tham s͙ cͯa hàm nén thông tin và co phi tuy͇n mi͉n tr͓ ÿ̯u ra còn giúp P̩ng n˯ ron h͕c nhanh h˯n). 1. GIӞI THIӊU Trên thӵc tӃ ta thѭӡng gһp tұp S các mүu dӳ liӋu, mӛi mүu ÿӅu có cùng các thành phҫn. Khi sӕ lѭӧng mүu cӫa tұp này lӟn, ta thѭӡng có cҧm giác mӝt sӕ thành phҫn này (ÿҫu ra) có mӝt P͙i liên h͏ phͭ thu͡c F nào ÿó vào các thành phҫn khác (ÿҫu vào). Ta thѭӡng không biӃt quy luұt F mà chӍ biӃt các thӇ hiӋn cӫa nó thông qua tұp mүu ÿã có. Bài toán ÿһt ra là tìm m͡t quy lu̵t Gÿ͋ x̭p x͑ quy lu̵t F G͹a vào t̵p m̳u S và dùng các tiêu chuҭn phù hӧp ÿӇÿánh giá ÿӝ tӕt, ÿӝ tin cұy Fӫa G. Trong toán hӑc, ngѭӡi ta thѭӡng dùng các phѭѫng pháp nӝi suy hay thӕng kê ÿӇ tìm G. Mӝt ÿһc ÿLӇm chung thѭӡng thҩy trong các phѭѫng pháp này là ta áp ÿһt trѭӟc mӝt dҥng quy luұt nào ÿó (chҷng hҥn hàm ÿa thӭc vӟi phѭѫng pháp nӝi suy ÿa thӭc hay hàm tuyӃn tính vӟi hӗi quy tuyӃn tính, …) ÿӇ xҩp xӍ F Gӵa vào tұp Pүu S. Mһt khác, ý nghƭa th͹c t͇ chính cͯa bài toán trên là ÿ͋ d͹ báo t͙t trên t̵p 20 các th͋ hi͏n mͣi S¶ cͯa F trong t˱˯ng lai chͱ không ch͑ là x̭p x͑ trên t̵p S ÿã bi͇t. Thông thѭӡng xҧy ra tình huӕng dҥng luұt G [ҩp xӍ rҩt tӕt S nhѭng lҥi vҩp phҧi sai sӕ lӟn trên tұp các thӇ hiӋn mӟi S’ cӫa F. Mӝt trong nhӳng lý do gây nên tình huӕng ÿó là dҥng luұt G Eӏ áp ÿһt trѭӟc khác rҩt xa dҥng cӫa F. Trong tin hӑc, Pҥng nѫ ron truyӅn thҷng nhiӅu lӟp (Multilayer Propagation neural Network – MPN) thѭӡng ÿѭӧc sӱ dөng ÿӇ tìm quy luұt G. Ĉӕi vӟi các tұp dӳ liӋu có miӅn trӏ ÿҫu ra vӯa phҧi, quy luұt G tìm ÿѭӧc bҵng MPN thѭӡng có khҧ năng dӵ báo tӕt. Tuy nhiên, ÿӕi vӟi các tұp dӳ liӋu có mi͉n tr͓ÿ̯u ra lͣn, quy luұt tìm ÿѭӧc không có khҧ năng dӵ báo thұt tӕt và thӡi gian hӑc cӫa MPN thѭӡng rҩt lӟn. ĈӇ khҳc phөc hҥn chӃÿó, chúng tôi ÿӅ nghӏ các phѭѫng pháp sau ÿӇ cҧi thiӋn khҧ năng hӑc cӫa mҥng nѫ ron: (1) áp dөng phѭѫng pháp hӑc các tham sӕ Fӫa hàm nén thông tin (hàm logistic) kӃt hӧp vӟi viӋc co phi tuyӃn (thay vì co tuyӃn tính nhѭ truyӅn thӕng) miӅn trӏÿҫu ra bҵng hàm lNJy thӯa; và (2) dùng thuұt giҧi di truyӅn (vӟi phép lai sӕ hӑc truyӅn thӕng và phép lai ÿӝng cҧi tiӃn) tiӃn hóa quҫn thӇ các bӝ tham sӕ cӫa mҥng nѫ ron, sau ÿó chӑn ra bӝ tham sӕ tӕt nhҩt ÿӇ cho mҥng hӑc. Phҫn 2.1 ÿѭa ra mô hình MPN vӟi các hàm tích hӧp thông tin, nén thông tin có G̩ng t͝ng quát. Phҫn 2.2 chӍ ra công thӭc ÿӋ quy tính ÿҥo hàm hàm lӛi theo tham sӕ cӫa hàm tích hӧp thông tin và hàm nén thông tin. Trên cѫ sӣÿó, chúng tôi ÿѭa ra phѭѫng pháp hӑc tham sӕ cӫa hàm nén thông tin. Phҫn 2.3 ÿӅ nghӏ phѭѫng pháp co phi tuyӃn miӅn trӏÿҫu ra bҵng hàm lNJy thӯa. Phҫn 3 áp dөng GA ÿӇ tìm Eӝ tham sӕ ban ÿҫu cho MPN. Phҫn 4 ÿѭa ra kӃt qӫa thӱ nghiӋm. 2. HӐC THAM SӔ CӪA HÀM NÉN THÔNG TIN VÀ CO LljY THӮA MIӄN TRӎĈҪU RA Cho tұp S gӗm m bӝ dӳ liӋu mүu mn nn DimIn n yxx 11 },,...,{ =>< , DimIn là sӕ chiӅu ÿҫu vào cӫa mүu dӳ liӋu. 2.1. Mô hình MPN /ӟp nhұp X(0) nhұn các giá trӏÿҫu vào trên dӳ liӋu (sau khi ÿѭӧc xӱ lý thô Eҵng hàm T_In). Lӟp ҭn X(i) (i = 1, .., N) chӭa H[i] nѫ ron, ký hiӋu ijX là nѫ ron thӭ j cӫa X(i) (hình 1). i jX t͝ng hͫp thông tin ÿӃn tӯ X (i-1) thông qua phép tích hͫp thông tin 1]1[: RRS iHij ® - ( )1, -= iijijij xParSSs . (1) 21 Yӟi ijParS , là tham sӕ cӫa hàm tích hӧp thông tin và giҧ thiӃt hàm ijS cӝng tính ÿӕi vӟi tӯng thành phҫn 1-ikx : )Par_S,(Q)Par_S1]},-..H[i1k;({x 1 1]-H[i 1k i jk 1 i j i k i j i k i j XS - = - å== (2) Hình 1: Mô hình MPN Sau ÿó, ijs ÿѭӧc biӃn ÿәi bҵng hàm nén thông tin 11: RRF ij ® )_,( ij i j i j i j FParsFx = , (3) vӟi ijFPar _ là tham sӕ cӫa hàm nén thông tin /ӟp ҭn X(N+1) chӍ chӭa mӝt nѫ ron tәng hӧp và biӃn ÿәi thông tin ÿӃn tӯ XN ÿӇ cho ra kӃt xuҩt Z cӫa MPN. 9ӟi mүu dӳ liӋu thӭ n cho trѭӟc < nnDimIn n yxx ,,...,1 >, ta tiӃn hành biӃn ÿәi thô ÿҫu ra trên dӳ liӋu ny Eҵng hàm T_Out: )(__ nn yOutTOutZ = . Sai sӕ giӳa Zn và Z_Outn ÿo bӣi hàm lӛi )Z_Out,e(Ze nnn = (chҷng hҥn, có thӇ lҩy e là hàm 2nn Z_Out-Z 2 1 , trong ÿó . là chuҭn Euclide) ÿѭӧc lan truyӅn ngѭӧc lҥi các lӟp ҭn N+1, N, .., 1 ÿӇ cұp nhұt các tham sӕ ( ,_ ijSPar ijFPar _ ) cӫa MPN bҵng phѭѫng pháp hӑc thích nghi [2]. Z Xi-1k X X(0) X(1) X(i-1) X(i) X(N+1) Y T_In T_Out Xöû lyù thoâ döõ lieäu ñaàu vaøo Xöû lyù thoâ döõ lieäu ñaàu ra ParS(i)j,k ParFij F sij T_Out-1 Z_Out S 22 2.2. Công thӭc ÿӋ quy tính ÿҥo hàm hàm lӛi theo tham sӕ cӫa hàm tích hӧp thông tin và hàm nén thông tin có dҥng tәng quát Sau ÿây chúng tôi ÿѭa ra công thӭc ÿӋ quy ÿӇ tính ÿ̩o hàm hàm l͟i trên Pүu thӭ n theo tham s͙ ijkParS , ijkParF tѭѫng ӭng vӟi các hàm tích hͫp thông tin i jS và hàm nén thông tin ijF có d̩ng t͝ng quát chӭa tham sӕ ÿѭӧc nêu ӣ trên: Không giҧm tәng quát, ta có thӇ giҧ sӱ sӕ chiӅu ÿҫu ra cӫa mүu bҵng 1. 2.2.1. Công thͱc tính ÿ̩o hàm hàm l͟i theo tham s͙ Par_F cͯa hàm F 0͏nh ÿ͉ 1: Ta có công thӭc ÿӇ tính ÿҥo hàm hàm lӛi i j n n ji FPar eFd _ _ )(, ¶ ¶ = Fӫa sai sӕ ne trên mүu luyӋn thӭ n theo tham sӕ ijFPar _ , :]1[,..,0],[,..,1,1,..,1 -="="+=" iHkiHjNi _ )_,( __ i j i j i j(n) ji, )( , i j n ji FPar FParsF FFd ¶ ¶ = d , i j (n) ji,_ X eF n ¶ ¶ ºd (4) Gӵa vào K͏ thͱc truy h͛i lùi theo i = N+1..1 ÿӇ tính _ )(, njiFd nhѭ sau: . Khi i = N+1: n j nn )( ,1 Z )Z_Out,e(Z_ ¶ ¶ =+ n jNFd (5) . Khi i = N..1: i j i j i p i p i p i p H p n pi n ji X XS s sF FF ¶ ¶ ¶ ¶ = + + +++ = +å )()( __ 1 1 111][i 1 )( ,1 )( , dd (6) Chͱng minh: Do ne phө thuӝc vào ijFPar _ thông qua: )Par_F,(sF ijijijijX = , nên: 1..1,_, _ _ __ _ i j (n) ji, i j(n) ji, i j i j )( , +=¶ ¶ º ¶ ¶ = ¶ ¶ ¶ ¶ = ¶ ¶ º Ni X eF FPar X F FPar X X e FPar eFd n i j i j n i j n n ji dd Ta sӁÿѭa ra công thͱc truy h͛i lùi theo i =N+1..1 ÿӇ tính )(,_ njiFd . · Khi i =N+1, ta có: n j nn 1 11]H[N 1m n m nn 1 )( ,1 Z )Z_Out,e(Z. Z )Z_Out,e(Z_ ¶ ¶ = ¶ ¶ ¶ ¶ = ¶ ¶ = + ++ = ++ å N j N m N j n n jN X X X eFd · Khi i =N..1, ta thҩy 1+NmX phө thuӝc vào ijX thông qua các 1+ipX ӣ bѭӟc sau: 1]i[1..Hp),Par_F0..H[i]),r;Par_S,(X(S)Par_F,(s 11111111 +==== ++++++++ ip i pr i r i p i p i p i p i p i p FFX . 23 Theo giҧ thiӃt, ..H[i]})0r;{Par_S..H[i]},1r;({ 11 == ++ ipririp XS Fӝng tính ÿӕi vӟi tӯng thành phҫn Xir nên: i j i j i p i p i p i p i j i r i p i p i p i p i j i p X XS s sF X XS s sF X X ¶ ¶ ¶ ¶ = ¶ ¶ ¶ ¶ = ¶ ¶ + + ++ = + + +++ å )()()()( 1 1 11H[i] 1r 1 1 111 Mһt khác: i j N m i j n n ji X X X eF ¶ ¶ ¶ ¶ = ¶ ¶ º ++ = å 11]H[N 1m n m nn )( , .Z )Z_Out,e(Z_d (a) Vì vұy: i j i j i p i p i p i p i p N m i j i p i p N m i j N m X XS s sF XX X XX X ¶ ¶ ¶ ¶ ¶ ¶ = ¶ ¶ ¶ ¶ = ¶ ¶ + + +++ = + +++ = + ++ åå )()(XX 1 1 111]H[i 1p 1 111]H[i 1p 1 11 (b) 7ӯ (a) và (b) ta suy ra: i j i j i p i p i p i p H p n pi n ji X XS s sF FF ¶ ¶ ¶ ¶ = + + +++ = +å )()( __ 1 1 111][i 1 )( ,1 )( , dd 2.2.2. Công thͱc tính ÿ̩o hàm hàm l͟i theo tham s͙ Par_S cͯa hàm S 0͏nh ÿ͉ 2: Ta có công thӭc ÿӇ tính ÿҥo hàm hàm lӛi i jk n n kji SPar eSd _ _ )( ,, ¶ ¶ = Fӫa sai sӕ ne trên mүu luyӋn thӭ n theo tham sӕ ijkSPar _ : _ _ ___ _ i j i j i j(n) ji, i j i j i j i j i j i j )( ,, i jk i jk n i jk n i jk n n kji SPar S s F F SPar S s F X e SPar S s e SPar eSd ¶ ¶ ¶ ¶ = ¶ ¶ ¶ ¶ ¶ ¶ = ¶ ¶ ¶ ¶ = ¶ ¶ º d (7) trong ÿó: (n)ji,_ Fd ÿ˱ͫc tính theo công thͱc truy h͛i lùi (5)-(6). 2.2.3. Các tr˱ͥng hͫp ÿ̿c bi͏t th˱ͥng g̿p · Hàm sai s͙ có d̩ng bình ph˱˯ng: å + =+ == 1]H[N 1j 2n j n j nn )Z_Out-(Z 1]2.H[N 1)Z_Out,e(ZPar_F)(Par_S,ne Khi ÿó: 24 1])/H[NZ_Out-(Z Z )Z_Out,e(Z n j n jn j nn += ¶ ¶ NӃu ÿҫu ra cӫa mүu dӳ liӋu mӝt chiӅu (H[N+1]=1) thì: nn n nn Z_Out-Z Z )Z_Out,e(Z = ¶ ¶ (8) · Hàm t͝ng hͫp thông tin có d̩ng afin: +͏ qu̫ 1: Giҧ sӱ hàm tәng hӧp thông tin có dҥng afin )(1-i 0 ]1[ 0 1-i k ]1[ 1 0 1-i k )()1()()( _,1X ,X.X.)_,( i jk i jk iH k i jk iH k i j i jk i j ii j i j SParW WWWSParXSs ºº =+== åå - = - = - (9) Khi ÿó: 1..1, _ 1 i j +== ¶ ¶ - NiX SPar S i ki jk Ni X XS i pji j ii p ..0, W )( 1 1 == ¶ ¶ + + · Hàm bi͇n ÿ͝i thông tin có d̩ng chͷ S ho̿c tuy͇n tính: a- Hàm logistic (trong m̩ng n˯ ron truy͉n th͙ng): ue1 1)F(u, a a -+ = (10) Khi ÿó: 1..1),X1.(X. )( +="-= ¶ ¶ Ni s sF i j i ji j i j i j a 1..1),X1.(X).,()X1.(X. )( 1 +="-=-= ¶ ¶ - NiXFs sF i j i j i ju i j i j i j i j i j a a vӟi: v-1 vln1)(v,F 1-u a a = b- Hàm logistic t͝ng quát: +͏ qu̫ 2: Giҧ sӱ hàm logistic tәng quát: u ij ij ijijij i j ije a auF ab ba -+ =),,,( (11) Khi ÿó: 1..1),/X1.(X. )(X +="-= ¶ ¶ = ¶ ¶ Nia s sF s ij i jij i jiji j i j i j i j i j ba 25 1..1),/X1.(X).,()()/X1.(X. )( 1 +="-=-= ¶ ¶ - NiaXFas sF ij i jij i jij i ju i jij i jij i j i j ij i j i j bab a 1..1,/]X[ )( 2 +="-= ¶ ¶ Nia sF ij i j ij i j i j b 1..1,/X )( +="= ¶ ¶ Nia a sF ij i j ij i j i j , Yӟi: v-a vln1),()( 1 ijijij iju i j vF ba a =- Thay vì chӑn thӫ công các tham sӕ ijijija ba ,, , ta cho mҥng MPN t͹ÿ͡ng K͕c thêm c̫ các tham s͙ này nh̹m gi̫m nhanh sai s͙ hàm l͟i. .͇t qͯa Fӫa viӋc K͕c t͹ÿ͡ng các tham s͙ này sӁҧnh hѭӣng tәng hӧp ÿӃn các nѫ ron trong các lӟp trѭӟc và sӁ làm cho quá trình h͕c cͯa m̩ng MPN nhanh h˯n. c- Hàm tuy͇n tính ch͑ͣ lͣp cu͙i cͯa m̩ng: Ĉôi khi, ÿӕi vӟi lӟp xuҩt cuӕi (lӟp N+1) cӫa mҥng, ta có thӇ thay ijF bͧi hàm tuy͇n tính ÿ͋ m̩ng có th͋ h͕c hi͏u qu̫ h˯n ÿáng k͋ (gi̫m sai s͙ nhi͉u l̯n so vͣi m̩ng truy͉n th͙ng) trong nhi͉u tr˱ͥng hͫp: 1,.),( +== NiuaauF ijij i j (12) Ni e a auF u ij ij ijijij i j ij ..1,),,,( = + = -ab ba Khi ÿó: Nia s F ij i jij i jiji j i j ..1),/X1.(X. ="-= ¶ ¶ ba }1;0{, +Î= ¶ ¶ Nia s F iji j i j 2.3. Co phi tuyӃn miӅn trӏÿҫu ra bҵng hàm lNJy thӯa Giҧ sӱ miӅn trӏÿҫu ra trên dӳ liӋu là ÿRҥn [min, max] có ÿӝ dài lӟn. Theo truyӅn thӕng, ÿҫu ra trên dӳ liӋu sӁÿѭӧc biӃn ÿәi bҵng phép co tuyӃn tính vӅÿRҥn [0, 1]: yyOutT min)(max 1)(_ - = . (13) Ĉҫu ra cӫa MPN là z cNJng thuӝc [0, 1] (miӅn trӏÿҫu ra cӫa hàm logistic truyӅn thӕng theo (12)). MPN thѭӡng hӑc chұm và có tính dӵ báo không cao. 26 Trong bài báo này, chúng tôi co miӅn [min, max] lӟn vӅ mӝt miӅn trung gian vӯa phҧi [lower, upper] bҵng hàm lNJy thӯa (vӟi k ÿѭӧc chӑn thích hӧp): 0),(.)(_ 1 >= kysignyyOutT k . (14) Dùng hàm logistic tәng quát theo (13) và cho MPN hӑc trӵc tiӃp trên miӅn trung gian [lower, upper]. Trên miӅn này, MPN thѭӡng hӑc chính xác và nhanh Kѫn ÿһc biӋt là khi miӅn trӏÿҫu ra lӟn. 3. Ӭng dөng GA vào viӋc tӕi ѭu hoá các tham sӕ cӫa mҥng nѫron Thuұt giҧi di truyӅn (GA) là mӝt trong nhӳng phѭѫng pháp ngүu nhiên tìm kiӃm tӕi ѭu toàn cөc ÿѭӧc áp dөng rӝng rãi. Trong bài này, chúng tôi áp dөng GA tiӃn hóa quҫn thӇ các bӝ tham sӕ cӫa MPN qua mӝt sӕ thӃ hӋ, sau ÿó chӑn ra bӝ tham sӕ tӕt nhҩt ÿӇ cho MPN hӑc. 0ӝt cá thӇ mã hóa tұp các tham sӕ (ParS trong các nút theo các nhóm sҳp theo thӭ tӵ liên tiӃp các nút trong các lӟp cӫa MPN) bҵng mӝt dãy các sӕ thӵc nhѭ sau: },..,;;..;,..,;..;,..,{ 1 ][,1 1 0,1 1 ],1[ 1 0],1[ 1 ,1 1 0,1 ++ N NH N DimInHHDimIn ParSParSParSParSParSParS . * Lai t̩o: Theo truy͉n th͙ng, viӋc lai ghép giӳa hai cá thӇ p1, p2 diӉn ra theo cѫ chӃ lai sӕ hӑc tҥo ra hai con ch1, ch2 nhѭ sau: chi = p1 + ri *(p2± p1), ri = rand(0; 1), i = 1,2. (15) Trong [3] ÿ͉ xṷt ph˱˯ng pháp lai ÿ͡ng c̫i ti͇n khi lai ghép trên các cá thӇ là các sӕ thӵc. KӃt qӫa lai ghép giӳa hai cá thӇ p1, p2 (gi̫ s͵ p1 thích nghi cao Kѫn p2) Wҥo ra hai con ch1, ch2 nhѭ sau: ch1 = p1 + q(t)*d (16) ch2 = p2 - q(t)*d Yӟi: î í ì - = suaát pxaùcvôùi, p-1suaátxaùcvôùi, ),'min().( ' 021 dd d d ppsign d’ = (p2 – p1), î í ì £- >- = 121 121 0 if, if, pppb ppap d (17) a = (a1, …, an), b = (b1, …, bn), ½d’½ = (½d’1½, …, ½d’n½), q(t) = r*(1 – t/T)g, trong ÿó: p = 0.5, r = rand(0, 1), g = 5.0 (hoһc g = 4.0), t là thӃ hӋ hiӋn tҥi và T là Vӕ thӃ hӋ tiӃn hóa tӕi ÿa; các phép toán “+”, “-”, min và quan hӋ hai ngôi “>” trên 27 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 ÿӝ. Ӣ dây, chúng tôi áp dөng hai mô hình GA khác nhau vào MPN: dùng phép lai sӕ hӑc (GA-SH) và phép lai ÿӝng cҧi tiӃn (GA-LĈ). * Ĉ͡t bi͇n: Ĉ͡t bi͇n thay ÿәi (có hѭӟng: tăng, giҧm; hoһc vô hѭӟng: tăng, giҧm ngүu nhiên) các ÿѫn-vӏ (là tham sӕ hoһc nút tѭѫng ӭng trên MPN) mӝt lѭӧng ngүu nhiên delta = rand [a, b], 0<a<b xác ÿӏnh trѭӟc). Mô hình GA ӣÿây áp dөng phép ÿӝt biӃn: î í ì - + = db db p-1suaátxaùcvôùi suaát pxaùcvôùi , , deltaPar deltaPar Par trong ÿó viӋc áp dөng xác suҩt ÿӝt biӃn pÿb có thӇ tiӃn hành ÿӗng thӡi hay riêng rӁ trên tӯng tӑa ÿӝ Par. 4. KӃt quҧ thӵc nghiӋm Xét bài toán hӑc bҵng mҥng nѫ ron mӝt sӕ dҥng quy luұt (QL) sau: QL1: 323 1002 xxxy +++= , x = rand(-100, 100), 300 mүu, [min, max] = [100.19, 2.01715e+006]. QL2: ),sin( 2122 xxxy += xi = rand(1000, 100000), 400 mүu, [min, max] = [2.49353e+006, 9.99512e+009]. QL3: y = 10x12+x22+x3sin(x4), xi = rand(1000, 10000), 200 mүu, [min, max] = [1.38936e+007, 1.03394e+009]. Chia (theo tӍ lӋ 40% – 30% – 30%) mӛi tұp mүu có ÿѭӧc thành ba tұp con: tұp huҩn luyӋn (HL), tұp kiӇm tra (KT) và tұp kiӇm chӭng (KC). Tұp HL dùng ÿӇ huҩn luyӋn MPN, tұp KT dùng ÿӇ kiӇm tra chéo (dӯng luyӋn), tұp KC dùng ÿӇ ÿánh giá khҧ năng dӵ báo cӫa MPN. *ӑi: zn là ÿҫu ra cӫa MPN, z_outn là ÿҫu ra trên dӳ liӋu ӭng vӟi mүu thӭ n. Cho trѭӟc tұp mүu U, lӛi tѭѫng ÿӕi trung bình cӫa mô hình trên U ÿѭӧc ÿӏnh nghƭa: å = = )( 1 100* _)( 1(%) UCard n U zUCard E n nn out z_out-z (18) Qua thӵc nghiӋm, chúng tôi ÿã so sánh khҧ năng hӑc cӫa các mô hình mҥng nѫ ron sau, vӟi hàm tәng hӧp thông tin có dҥng afin : 28 - MPN truyӅn thӕng: không tӵÿӝng hӑc tham sӕ cӫa hàm logistic ÿѫn giҧn , co tuyӃn tính miӅn trӏÿҫu ra cӫa dӳ liӋu (MPNTT); - MPN cҧi tiӃn có tӵÿӝng hӑc các tham sӕ cӫa hàm logistic tәng quát, kӃt hӧp Yӟi viӋc co bҵng hàm lNJy thӯa miӅn trӏÿҫu ra (MPNHTS); - Mô hình áp dөng GA truyӅn thӕng (vӟi phép lai sӕ hӑc cәÿLӇn) trѭӟc khi cho Pҥng hӑc theo mô hình MPNHTS (GASH-MPNHTS) - Mô hình áp dөng DGA cҧi tiӃn (vӟi phép lai ÿӝng cҧi tiӃn) trѭӟc khi cho Pҥng hӑc theo mô hình MPNHTS (GALĈ-MPNHTS) Khҧ năng hӑc cӫa các mô hình: MPNTT, MPNHTS, GASH-MPNHTS và GALĈ-HTS ÿ˱ͫc ÿánh giá d͹a trên các tiêu chí sai s͙ EKC, EKT, EHL Oҫn lѭӧt trên các tұp kiӇm chӭng, kiӇm tra, huҩn luyӋn và thͥi gian (tính theo giây, trên máy PC Pentium IV, 1.8 GHz, RAM 640Mb). KӃt qӫa so sánh các mô hình cho trong bҧng 1. Quy luұt &ҩu hình MPN Mô hình EKC EKT EHL T(s) MPNTT 14.78 15.75 14.31 2700 MPNHTS (k = 18) 3.23 3.00 2.44 557 GASH-MPNHTS 1.15 0.96 0.68 725 QL1 1 lӟp ҭn chӭa 10 nút GALĈ-MPNHTS (g = 4.0) 0.76 0.70 0.64 598 MPNTT 15.48 11.12 7.16 239 MPNHTS (k = 22) 4.04 2.36 1.64 172 GASH-MPNHTS 1.74 1.08 0.81 1211 QL2 1 lӟp ҭn chӭa 5 nút GALĈ-MPNHTS (g = 4.0) 1.02 0.48 0.31 373 MPNTT 6.19 6.30 2.40 173 MPNHTS (k = 22) 1.73 1.79 0.55 159 GASH-MPNHTS 0.95 1.20 0.42 457 QL3 1 lӟp ҭn chӭa 10nút GALĈ-MPNHTS (g = 5.0) 0.89 1.00 0.32 356 %̫ng 1: K͇t qͯa so sánh kh̫ năng h͕c cͯa các mô hình %̫ng 1 cho thҩy: - Khҧ năng hӑc cӫa MPNHTS t͙t h˯n MPNTT Fҧ Y͉ l͟i trên các t̵p KT, HL, KC l̳n thͥi gian h͕c; 29 - Khi áp dөng vào MPNHTS, mô hình GALĈ t͙t h˯n mô hình GASH Fҧ Y͉ O͟i trên các t̵p KT, HL, KC l̳n thͥi gian h͕c; - L͟i (trên các tұp KT, HL, KC) Fͯa mô hình GALĈ-MPNHTS th̭p h˯n r̭t nhi͉u so vͣi cͯa mô hình MPNTT. .ӂT LUҰN Tóm lҥi, tӯ kӃt quҧ thӵc nghiӋm trên mӝt sӕ dҥng qui luұt, ta có nhұn xét: - So vӟi mô hình MPN truyӅn thӕng, mô hình MPN (c̫i ti͇n) h͕c tham s͙ và co phi tuy͇n mi͉n tr͓ÿ̯u ra (b̹ng hàm lNJy thͳa) h͕c ÿ˱ͫc quy lu̵t chính xác K˯n và nhanh h˯n; - Khi áp dͭng thu̵t gi̫i di truy͉n tìm bӝ tham sӕ ban ÿҫu cho mҥng nѫ ron, sau ÿó dùng mô hình MPN c̫i ti͇n, ta sӁ tìm ra ÿ˱ͫc quy lu̵t chính xác h˯n h̻n so vӟi MPN truyӅn thӕng; - Khi áp dөng thu̵t gi̫i di truy͉n vào MPN cҧi tiӃn, phép lai ÿ͡ng c̫i ti͇n W͙t h˯n phép lai s͙ h͕c truy͉n th͙ng. /ӠI CҦM ѪN Qua bài báo này, các tác giҧ muӕn chuyӇn lӡi cҧm ѫn ÿӃn các bҥn ÿӗng nghiӋp cӫa khoa Toán – Tin và trѭӡng Ĉҥi hӑc Ĉà Lҥt ÿã tҥo ÿLӅu kiӋn ÿӇ chúng tôi hoàn thành bài báo. TÀI LIӊU THAM KHҦO [1] Hoàng KiӃm, Lê Hoàng Thái, ‘Thu̵t gi̫i di truy͉n ± Cách gi̫i t͹ nhiên các bài toán trên máy tính’, NXBGD, 2001. [2] Jacobs Robert A, ‘Increased Rates of Convergence Through Learning Rate Adaption’, Neural Networks 1(4): 295-308, 1988. [3] Trѭѫng Chí Tín, Trҫn Ngӑc Anh; µͰ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ͭF¶; Hӝi nghӏ quӕc gia lҫn thӭ 9 vào tháng 6/2006 vӅ “Mӝt sӕ vҩn ÿӅ chӑn lӑc cӫa CNTT và truyӅn thông”; Hӝi nghӏ toàn quӕc lҫn thӭ 2 vào tháng 12/2005 vӅ “Ӭng dөng Toán hӑc”. 30 PḪN II 0ӝt sӕ kӃt quҧ vӅ nung luyӋn mô phӓng 97 .ӂT LUҰN 1. Các kӃt quҧ chính vӅ lý thuyӃt, ӭng dөng và sҧn phҭm cӫa ÿӅ tài 1.1. Lý thuy͇t A. Thu̵t gi̫i di truy͉n (GA) và m̩ng n˯ron (ANN) - &̫i ti͇n phép lai ÿ͇n biên Fӫa miӅn trӏ theo K˱ͣng xác sṷt ÿ͡ng (phө thuӝc vào tuәi thӃ hӋ cӫa quá trình tiӃn hóa) trong GA nhҵm chͯÿ͡ng ÿL͉u khi͋n viӋc khoanh vùng cӵc trӏ toàn cөc trong giai ÿRҥn ÿҫu và tăng tӕc ÿӝ hӝi tөÿӃn lӡi giҧi tӕi ѭu trong giai ÿRҥn cuӕi cӫa quá trình tiӃn hóa; - 7͝ng quát hoá ph˱˯ng pháp hi͏u ch͑nh tuy͇n tính cͯa D.E. Goldberg, kh̫o sát các tính ch̭t tăng, gi̫m và h͡i tͭ cͯa phân ph͙i xác sṷt ch͕n t̵p con các th͋ theo ÿӝ thích nghi cuҧ chúng, nhҵm chͯÿ͡ng b̫o ÿ̫m tính ÿa d̩ng Fӫa quҫn thӇ trong giai ÿRҥn ÿҫu và Wăng t͙c ÿ͡ h͡i tͭ ÿӃn lӡi giҧi tӕi ѭu trong giai ÿRҥn cuӕi cӫa quá trình tiӃn hóa; - 7͝ng quát hoá ph˱˯ng pháp t͹ ÿ͡ng h͕c các tham s͙ ÿL͉u ch͑nh hi͏u Qăng cͯa m̩ng n˯ ron; dùng phép co phi tuy͇n b̹ng hàm lNJy thͳa ÿ͋ x͵ lý ÿ̯u ra dͷ li͏u cͯa m̩ng, nhҵm gi̫m ÿáng k͋ sai s͙ l͟i trên tұp mүu hӑc trong mҥng Qѫ ron, ÿһc biӋt khi ÿҫu ra cӫa dӳ liӋu có miӅn trӏ lӟn. B. Thu̵t toán nung luy͏n mô ph͗ng (SA) - ChӍ ra ҧ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. Trình bày mӝt sӕ khía cҥnh vӅ tӕc ÿӝ hӝi tөÿӃn trҥng thái cân bҵng cӫa thuұt toán Metropolis và cho mӝt ÿánh giá vӅ 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 bҵng ÿӕi vӟi các xích nung luyӋn thuҫn nhҩt; - 0ӝt sӕ kӃt quҧ liên quan ÿӃn sӵ 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ó dҥng tәng quát; - 0ӣ rӝng kӃt quҧ cӫa D. Mitra, F. Romeo và A. Sangiovanni-Vincentelli YӅ 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 NӃt quҧ vӅ sӵ hӝi tө cӫa thuұt toán không thuҫn nhҩt. 1.2. Ͱng dͭng A. Áp dͭng cͯa thu̵t gi̫i di truy͉n (GA) và m̩ng n˯ron (ANN) - Áp dͭng thuұt giҧi di truyӅn ÿӝng (DGA) cҧi tiӃn vào viӋc: gi̫i m͡t lͣp các bài toán t͙i ˱u toàn cͭc khó vͣi ÿ̿c tr˱ng có nhi͉u c͹c tr͓ÿ͓a ph˱˯ng trong [PEN] và bài toán Lennard-Jones cho Oͥi gi̫i t͙i ˱u có ÿ͡ chính xác cao và W͙c ÿ͡ K͡i tͭ nhanh K˯n h̻n so vͣi thu̵t gi̫i di truy͉n c͝ÿL͋n; khi áp dͭng thêm ph˱˯ng pháp leo ÿ͛i vào giai ÿRҥn cuӕi cӫa quá trình giҧi, ÿ͡ chính xác cͯa lͥi gi̫i sͅ r̭t cao và ÿ̩t ÿ˱ͫc r̭t nhanh; - Áp dͭng thu̵t gi̫i DGA ÿӇ W͙i ˱u hoá s˯ b͡ các tham s͙ trong m̩ng n˯ ron, trѭӟc khi quá trình hӑc cӫa mҥng ÿѭӧc bҳt ÿҫu; 98 Các N͇t qu̫ th͹c nghi͏m cho thҩy các ph˱˯ng pháp c̫i ti͇n và t͝ng quát hoá nêu trong ÿ͉ tài có ˱u ÿL͋m h˯n h̻n so vͣi các ph˱˯ng pháp c͝ÿL͋n trên nhiӅu lӟp bài toán. B. Áp dͭng SA vào lͣp bài toán l̵p l͓ch th͹c hi͏n công vi͏c - JSS - Cho mӝt ÿánh giá vӅ kích thѭӟc cӫa tұp lân cұn theo hàm cҩu trúc lân cұn Fӫa Van Laarhoven sӱ dөng trong các bѭӟc chuyӇn cӫa xích nung luyӋn; - Các kӃt quҧ thӵc nghiӋm cӫa chúng tôi khi áp dөng SA vào bài toán JSS, Vӱ dөng cҩu trúc lân cұn nêu trên và quy trình làm nguӝi thӡi gian ÿa thӭc cӫa Aarts và Van Laarhoven, cho thҩy mô hình nhҥy cҧm mҥnh dѭӟi tác dөng cӫa quy trình nhiӋt ÿӝ. ĈLӅu này là hoàn toàn phù hӧp vӟi ý nghƭa lý thuyӃt cӫa SA và các thӵc nghiӋm cӫa nhiӅu tác giҧ khác; - Vӟi bài toán FT 10, tuy thӵc nghiӋm cӫa chúng tôi có tӗn tҥi mӝt xích nung luyӋn ÿҥt ÿѭӧc trҥng thái năng lѭӧng thҩp nhѭng thӡi ÿLӇm ÿӇ xích nung luyӋn ÿi qua trҥng thái này là không thuӝc giai ÿRҥn hӋ kӃt tinh. Nói khác ÿi, vӟi các thông sӕ cӫa quy trình nung luyӋn ÿѭӧc chúng tôi sӱ dөng khi thӵc nghiӋm mô hình thì hӋ vүn ӣ trҥng thái năng lѭӧng cao khi kӃt thúc quy trình làm nguӝi. 1.3. S̫n pẖm cͯa ÿ͉ tài A. Các kӃt quҧ cӫa ÿӅ tài ÿã ÿ˱ͫc trình bày, công b͙ trong các hӝi nghӏ toàn quӕc vӅ Toán-Ӭng dөng, Công nghӋ thông tin và “Thông báo khoa hӑc” cӫa trѭӡng Ĉҥi hӑc Ĉà Lҥt: - Trѭѫng Chí Tín, Trҫn Ngӑc Anh; µͰ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’; Hӝi nghӏ quӕc gia lҫn thӭ 9 vào tháng 6/2006 vӅ “Mӝt sӕ vҩn ÿӅ chӑn lӑc cӫa CNTT và truyӅn thông”; Hӝi nghӏ toàn quӕc lҫn thӭ 2 vào tháng 12/2005 vӅ “Ӭng dөng Toán hӑc”, Thông báo Khoa hӑc, Ĉҥi Kӑc Ĉà Lҥt, 2006. - Trҫn Ngӑc Anh, Trѭѫng Chí Tín, ‘&̫i thi͏n kh̫ năng h͕c cͯa m̩ng n˯ ron truy͉n th̻ng nhi͉u lͣp’, Thông báo Khoa hӑc, Ĉҥi hӑc Ĉà Lҥt, 2006. B. Các kӃt quҧ ÿã hoһc Vͅ gͧi ÿăng trong các t̩p chí chuyên ngành: - Dang Phuoc Huy, ‘Simulated Annealing: Some Remarks on Convergence of the Metropolis Chains’, ÿã gӱi tҥp chí SOOCHOW JOURNAL OF MATHEMATICS. - Ĉһng Phѭӟc Huy, ‘6͹ h͡i tͭ cͯa thu̵t toán nung luy͏n mô ph͗ng trong tr˱ͥng hͫp rͥi r̩c’, sӁ gӱi ÿăng. - Ĉһng Phѭӟc Huy, ‘Á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’, sӁ gӱi ÿăng tҥp chí Toán Ӭng dөng, ViӋt Nam. C. %͡ ch˱˯ng trình th͵ nghi͏m các kӃt quҧ lý thuyӃt. 99 2. Mӝt sӕ hѭӟng mӣ rӝng cӫa ÿӅ tài - Mӝt sӕ kӃt quҧ vӅ lý thuyӃt cӫa ÿӅ tài chӍ mӟi ÿѭӧc chӭng minh trên mӝt Vӕ tính chҩt, khía cҥnh và chӭng tӓ có hiӋu quҧ qua kӃt quҧ thӵc nghiӋm trên mӝt Vӕ lӟp bài toán. Tuy nhiên, mӝt sӕ khía cҥnh quan trӑng khác vӅ mһt toán hӑc cӫa các phѭѫng pháp lý thuyӃt trong trѭӡng hӧp tәng quát vүn chѭa ÿѭӧc chӭng minh (chҷng hҥn, sӵ hӝi tө chҳc chҳn cӫa thuұt giҧi di truyӅn ÿӝng cҧi tiӃn DGA chѭa chӭng minh ÿѭӧc; lѭu ý rҵng, kӃt quҧ tѭѫng tӵ trong thuұt giҧi di truyӅn GA cә ÿLӇn cho ÿӃn nay vүn chѭa ÿѭӧc chӭng minh trong trѭӡng hӧp tәng quát, mһc dù chúng ÿѭӧc ӭng dөng rӝng rãi trong nhiӅu lƭnh vӵc thӵc tӃ !). Ĉó là mӝt trong các Kѭӟng có ý nghƭa mà các thành viên cӫa ÿӅ tài sӁ tiӃp tөc giҧi quyӃt. - Cҫn tiӃp tөc tìm kiӃm các phѭѫng pháp, thuұt toán trong tin hӑc nói chung và trí tuӋ nhân tҥo nói riêng (chҷng hҥn lƭnh vӵc Khai thác dӳ liӋu – Data Mining) ÿѭӧc ÿLӅu khiӇn hiӋu năng cӫa chúng thông qua các tham sӕ chӑn, thay vì theo cách tìm kiӃm thӫ công hoһc kinh nghiӋm, thì ta có thӇ áp dөng DGA ÿӇ tӕi ѭu hoá tӵÿӝng các tham sӕ chӑn này. - Mӝt sӕ vҩn ÿӅ quan tâm tiӃp theo cӫa chúng tôi ÿӕi vӟi SA là: tìm hiӇu Fұn trên sát nhҩt cho các quy trình làm nguӝi ÿӇ thuұt toán hӝi tө theo nghƭa yӃu, Pҥnh. Khҧo sát tӕc ÿӝ hӝi tө cӫa thuұt toán SA cҧ vӅ lý thuyӃt và thӵc hành. - TiӃp tөc nghiên cӭu lý thuyӃt vӅ sӵ hӝi tө cӫa thuұt toán trong trѭӡng hӧp không gian trҥng thái là liên tөc. - So sánh, kӃt hӧp SA và GA, cNJng nhѭ các phѭѫng pháp khác.