-i- MC LC TRANG PH BèA LI CAM OAN MC LC i 52 iv 52 iv 53 iv 54 iv 56 iv 57 iv DANH MC CC HèNH iv 14 iv 14 iv 16 iv 16 .v 17 .v 19 .v 21 .v 25 .v 31 .v 35 .v 36 .v 37 .v - ii - 42 .v 44 .v 55 .v CHNG I .9 GII THIU S LC V CC BI TON NP-C .9 1.1 Gii thiu chung v bi toỏn NP-C .9 1.2 Cỏch tip cn gii bi toỏn NP-C 10 1.2.1 Mt s khỏi nim 10 1.2.2 Gii thiu mt s thut toỏn xp x gii bi toỏn NP-C .11 1.2.3 Cỏc thut toỏn gn ỳng .12 1.2.4 Tụ mu th vi bi toỏn mu .19 1.2.5 Bi toỏn phng húa th 21 1.3 Kt lun 23 2.1 Gii thiu v mng n-ron 24 2.1.1 Lch s phỏt trin 24 2.1.2 Mụ hỡnh mng n-ron nhõn to 25 2.2 Phm vi ng dng ca mng n-ron 29 2.2.1 Nhng bi toỏn thớch hp 29 2.2.2 Cỏc lnh vc ng dng mng n-ron 29 2.2.3 u v nhc im ca mng n-ron 30 2.3 Mng Hopfield 30 2.3.1 Mng Hopfield ri rc 32 2.4 Gii thiu thut gii di truyn .34 2.4.2 Cỏc bc quan trng vic ỏp dng thut gii di truyn 36 2.4.3 Vớ d minh 37 2.4.4 Cỏc phng thc bin húa ca gii thut di truyn 40 CHNG 51 - iii - NG DNG THUT GII DI TRUYN 51 GII BI TON PHN CễNG NHIM V 51 3.1 Gii thiờu .52 3.2 inh nghia bai toan 53 3.3 ng dng Thut gii di truyn vo bi toỏn 55 3.3.1 Ma hoa: 56 3.3.2 Toan t chn cỏ th .56 3.3.3 Toan t lai ghộp v toỏn t t bin 57 3.3.4 Sa cha giai phap .59 3.3.5 Tim kiờm cuc bụ 60 3.4 Thi nghiờm va nhn xột 61 3.4.1 Thi nghiờm 61 mụ ta qua trinh tiờp cõn xem xet cỏc trng hp ASLGP sinh vi sụ sinh viờn va nhom la khac Xem xet cac trng hp t 75 ờn 400 sinh viờn, c phõn vao cac nhom thc hanh khac Cac trng hp c ky hiờu M/N/Cg (tng ng la tụng sụ sinh viờn, sụ nhom, va kha nng cha tụi a cua tng nhom) .61 3.4.2 Nhn xột 62 3.5 Kờt luõn 63 Gii thiu s lc cỏc bi toỏn NP-C, gii thiu mt s thut toỏn, gii thut v mt s cỏch tip cn ti vic gii cỏc bi toỏn NP-C 64 ó h thng c s lý thuyt ca mng nron, n ron nhõn to, mng n ron hopfiled, thut gii di truyn 64 KT LUN .58 TI LIU THAM KHO.. 59 DANH MC BNG - iv - Bng 3.1: Cỏc ng dng toỏn t lai ghộp thc hin GGA Bng 3.2: Cỏc ng dng toỏn t t bin thc hin GGA Bng 3.3: Vớ d v cỏc s thớch ca sinh viờn Bng 3.4: Vớ d v cỏc s thớch ca sinh viờn Bng 3.5: S sinh viờn nhúm th i nhng gii phỏp c tỡm thy bi GGA Bng 3.6: So sỏnh cỏc kt qu thu c bng GGA v thut toỏn tham lam GRAH 52 52 53 54 56 57 DANH MC CC HèNH Hỡnh 1.1: Bn d nc cha tụ mu Hỡnh 1.2: Bn d nc tụ bi mu Hỡnh 1.3: th cnh 14 14 16 -v- Hỡnh 1.4: Hỡnh (a) v (b) l th phng Hỡnh 1.5: th trờn mt hng n Hỡnh 2.1: Mụ hỡnh n ron sinh hc Hỡnh 2.2 : Mụ hỡnh mt N-ron Hỡnh 2.3: Mụ hỡnh mng Hopfield Hỡnh 2.4: Lu mụ t cu trỳc ca gii thut di truyn Hỡnh 2.5: Lu thut toỏn ca quỏ trỡnh chn lc Hỡnh 2.6: Lu thut toỏn quỏ trỡnh lai ghộp Hỡnh 2.7: Lu thut toỏn ca quỏ trỡnh t bin Hỡnh 2.8: Lu thut toỏn ca gii thut lai Hỡnh 2.9: Vớ d v biu din n ron ca bi toỏn vi N = Hỡnh 3.1: Vớ d v s thớch ca cỏc sinh viờn nhúm 16 17 19 21 25 31 35 36 37 42 44 55 -7- LI NểI U Trong thc t cú rt nhiu bi toỏn phc thuc lp bi toỏn NP- C v bi toỏn ti u cú rng buc, cng cú nhiu cụng trỡnh nghiờn cu gii quyt cỏc bi toỏn ú Vớ d nh: Bi toỏn tỡm ng i ngn nht, bi toỏn tụ mu bn , bi toỏn ti Xong cỏc gii thut a thng phc m cha cú thut toỏn n gin v hp lý Nhng nm gn õy trờn th gii ó a phng phỏp li mng N ron Hopfield v thut gii di truyn nhm gii quyt cỏc bi toỏn ti u thuc lp NP-C v c ỏp dng rng rói lnh vc Cụng ngh thụng tin Vic nghiờn cu v ỏp dng nhng thnh tu mi vo vic phõn tớch, thit k, phõn cụng nhim v l mt nhng núng ang rt c quan tõm Nhn thc c ú v cú s gi ý, nh hng ca PGS TS ng Quang em ó mnh dn nghiờn cu ti " Phng phỏp lai mng n ron - gii thut di truyn gii bi toỏn NP-C v ng dng" Ni dung c bn ca lun gm cú ba chng: Chng mt gii thiu s lc v mt s bi toỏn NP-C, cỏch tip cn gii cỏc bi toỏn NP-C nh: bi toỏn tụ mu th, bi toỏn phng húa th, bi toỏn chn ng tin, trỡnh by cỏc cỏch tip cn ti vic gii quyt cỏc bi toỏn nờu trờn Chng hai gii thiu s lc v mng n ron, mng n ron Hopfield, gii thut di truyn c bit trỡnh by phng phỏp lai mng Hopfield v gii thut di truyn gii bi toỏn ti u Chng ba ng dng gii thut di truyn gii bi toỏn phõn lch thc hnh ti cỏc trng i hc õy l bi toỏn cú tớnh ng dng thc t cao nhiu lnh vc nh phõn cụng nhim v cỏc n v, xp sp lch biu Bi toỏn thuc lp NP-C Vỡ vy, ng dng gii thut di truyn -8- bi toỏn phõn cụng nhim v h thng tớnh toỏn hn s hn l mt gi phỏp kh thi gúp phn nõng cao hiu qu cụng vic phõn cụng, iu hnh ca ngi Qua lun ny em xin chõn thnh cm n: PGS TS ng Quang Vin Cụng ngh thụng tin ó tn tỡnh giỳp , ng viờn, nh hng, hng dn em nghiờn cu v hon thnh lun Em xin cm n cỏc thy cụ giỏo vin Cụng ngh thụng tin, cỏc thy cụ giỏo khoa Cụng ngh thụng tin H Thỏi nguyờn, ó ging dy v giỳp em hai nm hc va qua, cm n s giỳp nhit tỡnh ca cỏc bn ng nghip Xin chõn thnh cm n! Thỏi Nguyờn, thỏng 11 nm 2010 Ngi vit lun Lờ Thanh Bỡnh -9- CHNG I GII THIU S LC V CC BI TON NP-C 1.1 Gii thiu chung v bi toỏn NP-C Quỏ trỡnh khỏm phỏ cỏc bi toỏn thuc loi NP-C cho ta bit rng cú rt ớt c hi phỏt trin c mt thut toỏn hiu qu gii nú iu ú khuyn khớch ta tỡm kim cỏc heuristic, cỏc li gii tng phn, cỏc xp x v nhng cỏch khỏc nhm trỏnh gii trc din bi toỏn Mi ln a thờm mt bi toỏn vo danh sỏch cỏc bi toỏn NP-C chỳng ta li cng c thờm ý tng rng tt c mi bi toỏn NP-C u ũi hi thi gian m nh ngha 1.1: Ta núi L l bi toỏn thuc loi NP-complete nu cỏc khng nh sau u ỳng: 1) L thuc NP 2) Vi mi ngụn ng L' NP cú mt phộp thu thi gian a thc L' v L Bi toỏn NP-complete u tiờn chỳng ta s xột l bi toỏn tha SAT (Boolean satisfiability) Chỳng ta s chng t rng ngụn ng ca mi mỏy Turing khụng n nh (NTM) thi gian a thc u cú mt phộp thu thi gian a thc v SAT Khi ó cú c mt s bi toỏn thuc NP-complete (NP-C) chỳng ta cú th chng minh mt bi toỏn mi thuc NP-C bng cỏch thu mt bi toỏn ó bit l NP-C v bi toỏn ú nh mt phộp thu thi gian a thc [ 1] nh lý di õy cho bit vỡ mt phộp thu nh th chng minh c bi toỏn ớch l NP-C nh lý 1.1: Nu bi toỏn P1 l NP-C, P2 l NP v cú mt phộp thu thi gian a thc t P1 v P2 thỡ P2 cng l NP-C - 10 - Chng minh: Ta cn chng t rng mi ngụn ng L thuc NP u thu c P2 thi gian a thc Khi ú theo nh ngha P2 s thuc NP-C Tht vy vỡ P1 l NP-C nờn cú mt phộp thu a thc L v P1 Gi s thi gian ca phộp thu ny l P(n) Vỡ th mt chui W biến đổi thành chuỗi x L có chiều dài n đợc P1 cú chiu di ti a l P(n) Ta cng bit rng cú mt phộp thu a thc t P1 v P2 Gi s thi gian ca phộp thu ny l q(m) Th thỡ phộp thu ny bin i chui x P1 v mt chui y no ú thuc P2 vi thi gian ti a l q(p(n)) Vỡ th phộp bin i W L v y P2 mt thi gian ti a l p(n) + q(p(n)) õy cng l mt a thc Nh vy, ta kt lun rng L cú th thu v P2 thi gian a thc nh lý 1.2 Nu cú mt bi toỏn no ú l NP-C m li thuc lp P thỡ ta cú P = NP Chng minh: Gi s cú bi toỏn Q NP-C v Q P Th thỡ mi ngụn ng L NP u thu c v Q thi gian a thc Nu Q P Nh vy NP P Kt hp vi iu hin nhiờn l P P thỡ L NP ta c P = NP Nhn xột: Chỳng ta tin tng rng nhiu bi toỏn thuc NP nhng khụng thuc P nờn chỳng ta s xem vic chng minh mt bi toỏn l NP-C cú giỏ tr ngang vi vic chng minh rng nú khụng th gii c thi gian a thc, v vỡ th khụng cú li gii ỳng no bng mỏy tớnh (v ta s ch i tỡm li gii gn ỳng) 1.2 Cỏch tip cn gii bi toỏn NP-C 1.2.1 Mt s khỏi nim Nh ó trỡnh by phn trờn vic tỡm nghim ca cỏc bi toỏn NP-C vi kớch c u vo n tng i ln l rt khú khn, thng l khụng kh thi vỡ phc cú th núi l hm m õy l nhng bi toỏn nan gii hay cũn gi l - 52 - 3.1 Gii thiờu Phõn lich ly thuyờt va thc hanh tai cac trng hoc luụn la võn ma cac trng i hc phai ụi mt hang nm Võn bao gụm viờc phõn cụng xen ke gia cac mụn hoc bt buục va cac ki thi sinh viờn co thờ tham gia õy u Trong nhng nm trc õy, khụi lng cụng viờc vụ cung ln va mụi trng i hc lai co nhng c thu riờng biờt (thng mụi trng lai co nhng mụn hoc bt buục, cac k thi va lp hoc khac nhau), võy mụi trng co cỏc cỏch phõn cụng riờng Mụt c iờm thu vi khac cua cụng viờc phõn cụng la co rõt nhiờu võn phu phat sinh, xung quanh viờc phõn lich s phu thuục vao tng trng va ia iờm cua trng o Xem xet vi du vờ cac nhom thc hanh Tai a sụ cac trng, mụt viờc sp lich ly thuyờt va thc hanh a hoan tõt, thi se sinh la chn sinh viờn nh thờ nao vao cac nhom thc hanh c ho la chon trc o/ u tiờn (trong trng hp co vai nhom thc hanh cho mụt mụn hoc) Co võn sinh viờc phõn cụng va cac võn khac liờn quan: th nhõt la ap lc anh hng ti tinh kha thi cua lich lờn lp sau xõy dng, th hai la võn khụng anh hng ti tinh kha thi cua giai phap nhng ap ng mụt sụ chi tiờu inh sn se lam tng tinh kha thi (thng c goi la ap lc mờm) Trong vi du vờ viờc la chon sinh viờn vao cac nhom thc hanh: cụng suõt tụi a cua phong thi nghiờm la ap lc cng, khụng anh hng ti cac giai phap kh thi Mt khac, s thich cua sinh viờn hay ca giao viờn la ap lc mờm, vi no co thờ lam tng hiờu qua cua giai phap Ni dung trung nghiờn cu vờ viờc phõn cụng sinh viờn vao cac nhom thc hanh (sau õy goi la ASLGP), nhng cung xem xet ti yờu tụ ngoai vi la s la chon cua chinh sinh viờn va ging viờn Sụ lng cac nhom thc hanh mụt mụn hoc c quyờt inh theo s phõn cụng cua nha - 53 - trng, cua khoa hay s la chon cua chinh sinh viờn luụn phai phu hp vi iờu kiờn cua phong thi nghiờm, giam tụi a anh hng cua cac yờu tụ khach quan, c anh gia hiờu qua thụng qua kờt qua hoan cụng viờc cung nh s hng cua sinh viờn va giang viờn [8] Do cac phong thi nghiờm (thc hanh) luụn c trang bi tụi a thiờt bi va may tinh, nờn sụ lng sinh viờn mụi nhom chi nờn bng hoc it hn cụng suõt cua mụi phong õy la nguyờn tc cng khụng thờ vi pham c Vỡ thờ chi xem xet trng hp tõt ca cac nhom thc hanh ờu co sụ lng sinh viờn nh (theo s phõn cụng cua giao viờn) 3.2 inh nghia bai toan Xem xet trng hp phụ biờn thc tờ la cac mụn hoc tai cac trng i hc luụn co phõn li thuyờt va thc hanh Phõn thc hanh hoc tai cac phong thc hnh, khac thi gian va gi vi phõn li thuyờt Viờc phõn cụng sinh viờn cac nhom thc hanh theo thi khoa biờu cua khoa hoc va sụ buụi hoc cụ inh c phep tai cac phong thc hnh Bi vi a sụ cac trng hp, sụ nhom thc hanh tai cac buụi hoc khac c nha trng va khoa quyờt inh da trờn cụng suõt tụi a cua phong thi nghiờm ú Phn nghiờn cu cụng suõt cua phong thi nghiờm vi s la chn cua sinh viờn va giao viờn Trc tiờn nghiờn cu võn c ban la s la chon cua sinh viờn: Xột G = {g1, g2, , gN} ú N l cỏc nhom thc hanh mụt mụn hoc Mụi nhom gk se c phõn cụng theo thi khoa biờu (c va gi tuõn phong thc hnh hoat ụng) va kha nng tụi a cua phũng thc hnh l Cg Goi S = {s1, s2,.,sM} ú M l cỏc sinh viờn c thc hanh phong thi nghiờm Mụi sinh viờn lai co mong muụn vao mụt nhom - 54 - khac phu thuục vao mụn hoc va quan iờm cua sinh viờn Gia tri cua s thich la Psg cho mụi sinh viờn s va nhom g, cho co nghia la mụi sinh viờn phai at ụ thich thu tụi a P vao mụt nhom hoc vai nhom ma ho c phõn cụng, gia tri nho cho cac nhom ma ho khụng thich Vi du: Co nhom thc hanh, mụt hc sinh thich vao nhom va nhom (nhom thich hn nhom mụt chut), nhng khụng thich nhom vi no trung v gi vi mụn khac, va nhom thi thi gian vao buụi sang sm Do võy thich thu cua sinh viờn P s = {10, 50, 0, 40} inh nghia c võn nay, chung ta cõn mụt ma trõn nhi phõn X = M x N, o mụi gia tri xsg= la sinh viờn s c phõn vao nhom g (x sg = la sinh viờn khụng c phõn cụng) Tõt nhiờn la mụi sinh viờn phai c phõn vao mụt hoc nhõt mụt nhom ( nhom ( ) va tõt ca cac sinh viờn ờu c phõn ) Vi cỏc nh ngha nh trờn, viờc phõn cụng sinh viờn vao nhom c phỏt biu nh sau (p1): Tỡm X cho: ) (3.1) vi rng buc (3.2) Mụt b sung nho na la s la chon cua giao viờn bờn canh s thich cua sinh viờn Xem xet biờn th trng hp sụ lng sinh viờn cac - 55 - nhom la nh ch khụng phai nhom it nhom nhiờu hoc nhom khụng co sinh viờn Trong trng hp nay, inh nghia ASLPG nh sau (P2): )), (3.3) vi (3.4) (3.5) Chu y rng P1 ch danh cho s thich cua sinh viờn, nờn mụt nhom co thờ nhiờu sinh viờn nhom khac chi co sinh viờn P1 khụng co s can thiờp cua giao viờn, võy P2 ny c iờu chinh theo hm s thớch nghi lam cõn bng sụ sinh viờn mụi nhom iu ny c thc hin bi bin Biờn tol la dung th cua phng sai lm cho thnh phn th hai úng gúp vo phự hp 3.3 ng dng Thut gii di truyn vo bi toỏn Thut gii di truyn la mụt dang thuõt toan c cai tiờn giai quyờt cac võn vờ lõp nhom o sụ lng sinh viờn c õn inh mụt nhom Thuõt toan c Falkenauer (1992) xuõt, ụng cho rng cac thuõt toan truyờn thụng co mụt sụ han chờ chung c ng dung cac võn phõn nhom Do võy, thuõt toan nay, viờc s dng cỏc toỏn t nh ma hoa, lai ghộp va t bin cua cac thuõt toan truyờn thụng cõn c sa ụi at c mụt thuõt toan cht che, ng dung tụt viờc giai quyờt cac võn vờ tụ hp (nhom) Thuõt gii di truyn c ng dung cụng nhiờu linh vc nh viờn thụng, san xuõt, c cụng nghiờp , Trong phõn tiờp theo nhm chi nhng c iờm chinh cua thut gii di truyn, o tõp trung vao viờc ma hoa, toỏn t di truyn, vao viờc ng dung thc tiờn nõng cao tinh hiờu qua cho cac giai phap - 56 - 3.3.1 Ma hoa: Viờc ma hoa c tiờn hanh bng viờc tach cac nhiờm sc thờ nhom: õu tiờn la ma hoa cac viờn va nhom phõn cụng, sau o la phõn phõn nhom Noi chung, nờu nh sụ lng cac nhom khụng c xac inh trc, thi se dờ dang nhõn thõy õy la thuõt toan chuụi biờn ụi Phõn tụ hp biờn ụi t nhiờm sc thờ sang nhiờm sc thờ khac Tuy võy, phõn nhúm cac nhom thc hanh c cụ inh trc, võy trng hp ny, GGA c ma hoa chuụi cụ inh o mụi nhom ờu co chuụi N n vi Nhng phõn nhom c s dung toan t lai gộp va ụt biờn no thờ hiờn nhiờm sc thờ Vi du: Vờ ma hoa nhiờm sc thờ, gia s co nhom va 15 sinh viờn c phõn cụng cu thờ nh sau: 3 1 3 1 3| Chu y rng trng hp nhom thc hanh co nhng sinh viờn nh sau {1, 3, 6, 7, 12, 13}, nhom {2, 8, 10, 14}, va nhom {4, 5, 9, 11, 15} iu quan trng l thy rng mt phn phõn loi ca nhim sc th cỏc thut toỏn di truyn liờn quan trc tiờp ờn ma trõn X, a c inh nghia phõn trờn Trong thc tờ, cho mụt nhiờm sc thờ c = [a| g], o a diờn cho phõn phõn loai nhiờm sc thờ va g cho phõn phõn nhom, cac n vi cua ma trõn X c xac inh nh sau: (3.6) 3.3.2 Toan t chn cỏ th Trong mc s dung c chờ chon la xờp hang khep kin (hinh banh xe) James et al gii thiờu nm 2007 Trc tiờn cac ca thờ se c sp xờp da trờn hoc lc (chõt lng), va trao cho gia tri E q (3.1) trng hp P1 hoc (3.3) trng hp P2 Vi tri cua cac ca thờ (sinh viờn) danh - 57 - sach se c goi la xờp hang cua ca thờ, va ky hiờu R i, vi i=1,, , sp xờp danh sach theo o sinh viờn kha nhõt se dc gan R x = , sau o se la Ry = -1, Gia tri thớch nghi se c gan cho tng sinh viờn theo cụng thc sau õy: (3.7) Lu y rng cac gia tri chi nhõn gia tri gia va 1, phu thuục vao vi tri cua ca thờ danh sach, vi c chờ sp xờp theo th hang la cụ inh, võy xac suõt cua mụi ca thờ thich nghi (gan gia tri f i) khụng phu thuục vao thờ hờ, ma lai phu thuục vao vi tri cua ca thờ danh sach Xem xet vi du sau õy, mụt quõn thờ gụm ca thờ, ca thờ gioi nhõt la R = 5, ca thờ gioi th la R = 4, v v , trng hp gia tri thớch nghi se la (0.33, 0.26, 0.2, 0.13, 0.06) va khoang cach liờn kờt vong Roulette {0-0.33, 0.34-0.6, 0.61-0.8, 0.81-0.93, 0.94-1} Qua trinh thc hin thuõt toan cú s la chon cha me cho toan t lai ghộp Qua trinh c thc hiờn co thay thờ tc la mụt ca thờ cụ inh co thờ c la chon vai lõn mụt cp bụ me, nhiờn, cac ca thờ mụt cp phai khac Qua o ca thờ tụt nhõt c tim thõy se c chuyờn trc tiờp lờn thờ hờ tip theo 3.3.3 Toan t lai ghộp v toỏn t t bin Toan t lai ghộp v toỏn t t bin da trờn mụt thuõt toan Falkenauer xuõt nm 1998, va c James et al s dung nm 2007 Tuy nhiờn co mụt sụ khac biờt o la sụ lng cac nhom la cụ dinh va viờc thc hiờn thuõt toan co chiờu dai cụ inh Qua trinh thc hiờn toỏn t lai ghộp c thc hin nh sau: - 58 - õu tiờn, ca thờ c la chon, mụt se c t tờn la bụ, va mụt se c t tờn la me Chi nhõt mụt ca thờ c sinh t ca thờ Lam cõn bng sụ vi me Chon nhom cac nhom cua bụ Chen cac ca thờ bụ nhom c chon vao Sa cha ca thờ tranh giai phap kho thc hiờn minh hoa cho qua trinh nay, bang 3.1 cho thõy vi du vi 15 sinh viờn va nhom thc hanh Trong trng hp nay, nhom va nhom c la chn Sau o, ca thờ c sinh bng viờc cõn bng no vi ca thờ me va ca thờ bụ c la chon t nhom va Viờc sa cha chi xay mụt nhom co nhiờu sinh viờn hn kha nng cua no Toan t lai ghộp c la chon cho cp ca thờ vi kha nng Pc Bng 3.1: Vớ d: v cỏc ng dng toỏn t lai ghộp thc hin GGA Cỏ th b Cỏ th m 4 3 4 2 4 3 2 4 4 Con cỏi 3 2 2 2 Bng 3.2: Vớ d: v cỏc ng dng toỏn t t bin thc hin GGA 3 2 2 2 - 59 - 2 3 2 2 Vờ toan t t bin s dung thuõt toan nay, no c da trờn c chờ hoan ụi gia sinh viờn Bang 3.2 va vi du vờ toan t nay, o sinh viờn th va th 10 hoan ụi tng ng Viờc la chon sinh viờn ụi chụ cac nhom c thc hiờn vi mụt xac suõt hoan ụi cho trc Ap toan t cho mụt ca thờ nhõt inh vi mụt xac suõt cho trc Pm 3.3.4 Sa cha giai phap Mụt tụ hp cac ca thờ c hinh thanh, viờc sa cha c thc hiờn trờn mụi ca thờ tụ hp mi Bc la cõn thiờt loai bo ca thờ khụng ap ng kha nng Qua trinh diờn nh sau: Sp xờp cac nhom co kha nng vt qua La chon ngõu nhiờn mụt sinh viờn vao mụt cac nhom trờn La chon sinh viờn vao nhom ma sinh viờn thich nhõt co u kha nng Tiờp tuc qua trinh ờn tõt ca cac nhom ờu at kha nng tụi a Cung cõn xem xet ờn s a thich cua sinh viờn ho c sp xờp vao nhom khac nhom ban õu vi kha nng vt qua minh hoa, chung ta xem xet vi du 15 sinh viờn phõn vao nhom o mụi nhom co thờ co tụi a sinh viờn, s dung inh nghia P1 cua ASLGP Xem xet mụt ca thờ n le (nhiờm sc thờ) c = [1 1 2 1 1 2| 3], va s thich cua sinh viờn bang 3.3 Trong vi du nay, nhom co sinh viờn, nhom co va nhom co sinh viờn Vỡ thờ chung ta cõn giam sụ sinh viờn nhom i sinh viờn Chung ta õu tiờn la chon ngõu nhiờn mụt sinh viờn vao nhom Trc tiờn kiờm tra sinh viờn phõn vao nhom 1, xem xet mụt sinh viờn gia s sinh viờn sụ S thich cua sinh viờn sụ (bang 3.4) la 59 cho nhom 1, 25 cho nhom 2, va 16 cho nhom 3, võy chung ta xờp sinh viờn sụ vao nhom 2, sinh viờn co thờ chõp nhõn viờc di chuyờn Tiờp tuc xem xet viờc di chuyờn sinh viờn sụ 10 co s thich vao tng nhom 1,2,3 tng ng la 78, 8, va 14 Trong trng hp nay, sinh viờn - 60 - sụ 10 se c chuyờn sang nhom sinh viờn co thờ chõp nhõn viờc di chuyờn Vi viờc phõn cụng lai nay, ca thờ cuụi cung la c = [1 1 2 3 1 |1 3] Bng 3.3: Vớ d v cỏc s thớch ca sinh viờn Sinh viờn 10 11 12 13 14 15 Nhúm 76 59 61 78 12 23 44 21 91 72 36 54 82 51 21 Nhúm 20 25 21 23 48 42 52 19 33 45 10 61 Nhúm 16 18 14 65 29 14 27 31 16 39 18 3.3.5 Tim kiờm cuc bụ Quỏ trỡnh nghiờn cu tỡm kim cuc bụ tim hiờu iờu kiờn tụt nhõt cua cac ca nhõn lõn cõn Tim kiờm da trờn s sa ụi nho cua ca thờ hiờn tai nhm tng cng chc nng liờn kờt cua no Qua trinh tim kiờm ap dung cho moi ca thờ cua quõn thờ theo thuõt toan lai Lamac co nghia la nhiờm sc thờ c iờu chinh theo chc nng muc tiờu liờn kờt Qua trinh tiờn hanh nh sau: Sinh viờn õu tiờn c xờp mụt cach t nhiờn Vi mụi sinh viờn, tinh toan chc nng muc tiờu at c chuyờn sinh viờn sang nhom khac, nờu nh iờu kiờn cua nhom khụng bi vi pham Nờu viờc phõn nhom lai lam tng chc nng muc tiờu cua nhiờm sc thờ thi viờc phõn cụng c gi lai nờu khụng viờc phõn cụng lai bi huy bo va nhiờm sc thờ gi nguyờn nh trc nhom cuụi cung c phõn lai Qua trinh tiờp tuc ờn khụng at c s tiờn triờn - 61 - Bng 3.4: Vớ d v cỏc s thớch ca sinh viờn Sinh viờn 10 11 12 13 14 15 Nhúm 72 36 54 82 51 21 76 59 61 78 12 23 44 21 91 Nhúm 19 33 45 10 61 20 25 21 23 48 42 52 Nhúm 31 16 39 18 16 18 14 65 29 14 27 3.4 Thi nghiờm va nhn xột 3.4.1 Thi nghiờm mụ ta qua trinh tiờp cõn xem xet cỏc trng hp ASLGP sinh vi sụ sinh viờn va nhom la khac Xem xet cac trng hp t 75 ờn 400 sinh viờn, c phõn vao cac nhom thc hanh khac Cac trng hp c ky hiờu M/N/Cg (tng ng la tụng sụ sinh viờn, sụ nhom, va kha nng cha tụi a cua tng nhom) Xõy dng ngõu nhiờn s thich cua sinh viờn s dung mụ hinh phõn bụ ụng bụ U (0, x) vi x la gia tri s thich cua sinh viờn ụi vi cac nhom lai Hỡnh 3.1 cho thõy vi du vờ xõy dng s thich cua mụt sinh viờn ụi vi nhom Trong trng hp nhom u co gia tri 64, nhom la 17, 12, va cho cac nhom 3, 4, va U(0, 36) =17 U(0,19)=12 100-U(0,X)=4 U(0,7)=3 Hỡnh 3.1: Vớ d s thớch ca cỏc sinh viờn vi nhúm - 62 - Bang 3.5: Cho biờt sụ lng sinh viờn mụi nhom t c theo GGA cỏc vớ d xem xột V cỏc nhúm c a thớch nht luụn y (25 sinh viờn) Chu y rng theo yờu cõu sụ lng sinh viờn mụi nhom la cõn bng Bng 3.5: S sinh viờn nhúm th i nhng gii phỏp tt nht c tỡm thy bi GGA Vớ d 75/4/25 100/6/25 150/8/25 200/10/25 250/12/25 300/14/25 400/18/25 S sinh viờn nhúm th i 22, 18, 18, 17 22, 19, 16, 15, 14, 14 23, 21, 20, 18, 17, 17, 16, 18 25, 24, 22, 21, 20, 18, 18, 17, 17, 18 24, 22, 22, 22, 20, 20, 20, 20, 19, 18, 18, 25 25, 25, 25, 23, 22, 21, 20, 20 ,20, 19, 18, 19, 18, 25 25, 25, 25, 25, 25, 24, 23, 22, 22, 21, 20, 20, 20, 20, 20, 19, 19, 25 3.4.2 Nhn xột So sanh kờt qua vi phng phap inh hng thich nghi ngõu nhiờn a c ap dung trc õy giai quyờt phõn cụng Bai toan phõn cụng tụng quat (GAP) cõn nhc chi phi thõp nhõt cua n cụng viờc cho m nhom o mụi mụt cụng viờc c phõn cụng cho mụt va chi mụt n vi phu thuục vao nng lc cua nhom Chu y rng ASLGP co thờ coi la trng hp c biờt cua viờc phõn cụng tụng quat, ma sinh viờn chinh la cụng viờc, n vi la phong thi nghiờm, chi phi cho viờc phõn cụng liờn quan ờn s thich cua sinh - 63 - viờn, nng lc cua n vi c quyờt inh bi cụng suõt tụi a cua phong thi nghiờm Vi mụi vi du vờ ASLGP, xem xet 10 vong thuõt toan so sanh Bang 3.6 cho thõy kờt qua so sanh gia GGA va GRAH cua võn P1 va P2 Kờt qua cho thõy GGA cua P1 khụng khac GRAH tõt ca cac vi du ASLGP, nhng trng hp co 300 dờn 400 sinh viờn thi GGA cho kờt qua tụt hn GRAH Kờt qua thi nghiờm GGA cua P2 tụt hn nhiờu GRAH Trng hp cac nhom co sụ lng viờn nh nhau, thi thuõt toan xuõt cho kờt qua tụt hn trng hp GRAH Bng 3.6: So sỏnh cỏc kt thu c bng cỏc GGA v thut toỏn tham lam GRAH Bi toỏn 75/4/25 100/6/25 150/8/25 200/10/25 250/12/25 300/14/25 400/18/25 Hybrid GGA (P1) 4080 5028 6196 7187 8446 9379 11081 GRAH (P1) 4080 5028 6196 7187 8446 9376 11059 Hybrid GGA (P2) 4719 5259 6703 7743 9148 10046 11815 GRAH (P2) 4719 5207 6660 7715 9135 10002 11783 3.5 Kờt luõn Trong chng ny trung nghiờn cu thut gii di truyn giai quyờt võn phõn nhom sinh viờn thc hanh cac mụn hoc tai trng H õy la võn phụ biờn tai cac trng H sau cac mụn hoc c phõn lich Co mụt vai võn phat sinh t cụng viờc nay, th nhõt, chi co lng tụi a sinh viờn c phep cho phong thi nghiờm, han chờ vờ thiờt bi hoc khụng gian Th 2, la s thich cua sinh viờn tham gia vao cac buụi hoc thc hanh va yờu cõu vờ sụ lng cõn bng sinh viờn mụt nhom cua giao viờn Ni dung a mụ ta c iờm c ban va s mụ phong ca thuõt toan, va a at c kờt qua kha quan a sụ sinh viờn c la chon theo u tiờn sụ cua minh, ni dung nghiờn cu cú tớnh ng dng thc t cao tai trng H Chu y - 64 - rng thuõt toỏn co thờ ng dung nhiờu cụng viờc phõn cụng nhiờm vu khac thc t KT LUN Trong lun Phng phỏp lai mng n ron-gii thut di truyn gii cỏc bi toỏn NP-C v ng dng em ó hon thnh nhng nhim v sau: Gii thiu s lc cỏc bi toỏn NP-C, gii thiu mt s thut toỏn, gii thut v mt s cỏch tip cn ti vic gii cỏc bi toỏn NP-C ó h thng c s lý thuyt ca mng nron, n ron nhõn to, mng n ron hopfiled, thut gii di truyn ó trỡnh by cỏc tớnh cht c thự ca thut gii di truyn, cỏc bc quan trng vic ỏp dng thut gii di truyn 4.Trỡnh by cỏc phng thc bin húa ca gii thut di truyn, gii bi toỏn ti u theo phng phỏp thut gii di truyn, c bit l phng phỏp lai hng Hopfield v gii thut di truyn gii cỏc bi toỏn ti u thuc lp bi toỏn NP-C Kt hp c s lý thuyt nờu trờn vo gii quyt bi toỏn phõn cụng nhim v h thng tớnh toỏn hn ó ci t th nghim bi toỏn phõn lch thc hnh trng i hc trờn mỏy tớnh, kt qu t c phn ỏnh chớnh xỏc nhng kt qu ó nghiờn cu Cỏc nh hng nghiờn cu tip theo - 65 - gii quyt tt cỏc bi toỏn thuc lp NP-C thỡ em d nh mt s hng nghiờn cu tip theo l: Nghiờn cu phng phỏp lai mng Hopfiled-thut gii di truyn gii cỏc bi toỏn phc cao, khụng xỏc nh Nghiờn cu ỏp dng mng Hopfield vi c ch phn hi cho lp bi toỏn tha rng buc v ti u cú rng buc TI LIU THAM KHO [1] ng Quang , Bi ging lý thuyt phc tớnh toỏn, ti liu ni b khoa CNTT, i hc Thỏi Nguyờn, H ni, 2009 [2] ng Quang , ng dng ca mng n ron tớnh toỏn, Sỏch H m, mng n ron v ng dng, Ch biờn: Bựi cụng Cng, Nguyn Doón Phc, Nh XBKH-KT, H ni, 2001, 199-211 [3] Hon Kim, Lờ Hong Thỏi, Gii thut di truyn, cỏch gii t nhiờn cỏc bi toỏn trờn mỏy tớnh, NXB Giỏo dc, 2000 [4] Trn Th Thu Tr, ng Quang , Huy ng ngun in ti u bng mng Hopfield ri rc, Tp Khoa hc v Cụng ngh, Tp 43, S 1, 2005, 125-131 [5] Falkenauer, E (1992) The grouping genetic algorithmwidening the scope of the GAs In Proceedings of the Belgian journal of operations research, statistics and computer science (Vol 33, pp 79102) [6] LiMin Fu, Neural Network in Computer Intelligence, Mc Graw Hill, 1994 - 66 - [7] Y.Takefuji, Neural Network Parallel Computing, Kluwer Acad Publ, 1992 [8] Falkenauer, E (1998) Genetic algorithms for grouping problems New York: Wiley [9] Fan, Z P., Chen, Y., Mab, J., & Zhu, Y (2009) Decision support for proposal grouping: A hybrid approach using knowledge rules and genetic algorithms Expert Systems with Applications, 36, 10041013 ... x n cỏc khong cỏch [d ij ], dij > Nh thng l ta gi thit dij = dji v dii = Ta núi ma trn (dij) tha bt ng thc tam giỏc nu dij + djk dik i, j, k n Bt ng thc ny tha nu dij l khong cỏch thụng thng... " Phng phỏp lai mng n ron - gii thut di truyn gii bi toỏn NP-C v ng dng" Ni dung c bn ca lun gm cú ba chng: Chng mt gii thiu s lc v mt s bi toỏn NP-C, cỏch tip cn gii cỏc bi toỏn NP-C nh: bi... gii thiu s lc v mng n ron, mng n ron Hopfield, gii thut di truyn c bit trỡnh by phng phỏp lai mng Hopfield v gii thut di truyn gii bi toỏn ti u Chng ba ng dng gii thut di truyn gii bi toỏn phõn