Tối ưu số cho bài toán tối ưu một mục tiêu

Baùo Caùo Luaän Vaên Ñeà taøi : Toái öu soá cho baøi toaùn toái öu moät muïc tieâu Gvhd : Ths. Nguyeãn Höõu Thoâng Svth : Kieàu Thoï Khaùnh Lôùp : 98TH03 – Khoùa 98 Noäi dung baùo caùo Giôùi thieäu baøi toaùn toái öu toång quaùt Giôùi thieäu caùc phöông phaùp toaùn hoïc truyeàn thoáng, öu vaø khuyeát ñieåm cuûa phöông phaùp toaùn hoïc truyeàn thoáng. Giôùi thieäu höôùng xöû lyù cuûa giaûi thuaät tìm kieám ngaãu nhieân theo xaùc suaát. Giôùi thieäu giaûi thuaät keát hôïp 3 lôøi giaûi theo xaùc suaát ñoät bieán, öu vaø khuyeát ñieåm cuûa giaûi thuaät naøy. Caùch toå chöùc ñeå löu haøm, bieán, raøng buoäc cuûa chöông trình. Caáu truùc cuûa chöông trình toái öu soá, caùch tính giaù trò cho haøm vaø raøng buoäc. Caùc keát quaû maø chöông trình ñaõ thuïc hieän ñöôïc. Baøi toaùn toái öu toång quaùt f(x) ® max (min) vôùi caùc ñieàu kieän gi(x) (£) bi, i=1, ….,m x Î X Ì Rn gi(x) ñöôïc goïi laø caùc haøm raøng buoäc vôùi taäp hôïp D=í x Î X | gi(x) (£) bi, i=1, ….,mý goïi laø mieàn raøng buoäc x=(x1,x2,….,xn) Î D ñöôïc goïi laø moät phöông aùn. Moät phöông aùn x* Î D ñaït cöïc ñaïi hay cöïc tieåu vôùi: f(x*) ³ f(x) , "x Î D (ñoái vôùi baøi toaùn MAX) f(x*) £ f(x) , "x Î D (ñoái vôùi baøi toaùn MIN) Caùc phöông phaùp toaùn hoïc truyeàn thoáng Phöông phaùp ñôn hình giaûi baøi toaùn quy hoaïch tuyeán tính. Phöông phaùp phaân raõ quy hoaïch tuyeán tính. Phöông phaùp Karmarkar. Thuaät toaùn ñôn hình ñoái ngaãu giaûi baøi toaùn quy hoaïch ñoái ngaãu. Phöông phaùp Gradient cöïc tieåu khoâng raøng buoäc ñeå giaûi baøi toaùn quy hoaïch toaøn phöông. Ngoaøi caùc phöông phaùp neâu treân, coøn coù raát nhieàu phöông phaùp khaùc ñeå giaûi caùc baøi toaùn toái öu. Öu vaø khuyeát ñieåm cuûa caùc phöông phaùp toaùn hoïc truyeàn thoáng Öu vaø Khuyeát Ñieåm Cuûa Phöông Phaùp Toaùn Hoïc Truyeàn Thoáng Öu ñieåm Toát ñoái vôùi baøi toaùn toái öu moät muïc tieâu Khuyeát ñieåm - Ñoøi hoûi tính loài - Gaëp khoù khaên khi phaïm vi tìm kieám roäng Höôùng xöû lyù cuûa giaûi thuaät TKNNTXS Xöû lyù caùc chöõ soá cuûa bieán quyeát ñònh Nhaän xeùt: Trong moãi bieán quyeát ñònh, caùc chöõ soá beân traùi coù vai troø cao hôn caùc chöõ soá beân phaûi trong vieäc ñònh giaù haøm muïc tieâu ÞMoãi chöõ soá coù moät xaùc suaát ñoät bieán khaùc nhau ÞMoãi chöõ soá coù moät thöù baäc ñoät bieán khaùc nhau Giaûi thuaät Tìm Kieám Ngaãu Nhieân Theo Xaùc Suaát Caáu truùc döõ lieäu Lôøi giaûi coù n bieán quyeát ñònh, moãi bieán quyeát ñònh coù m=5 chöõ soá : x[i,j] Î{0,1,...,9} (1 £ I £ n, 1 £ j £ 5) Kyõ thuaät ñoät bieán coù ñònh höôùng 1. Ñoät bieán taïi chöõ soá thöù j theo xaùc suaát pj 2. Thöù töï ñoät bieán: töø traùi qua phaûi P1 < P2 < P3 < P4 < P5 x[i,1] X[i,2] X[i,3] x[i,4] x[i,5] Boä xaùc suaát ñoät bieán taïi moät bieán quyeát ñònh: Neáu bieán quyeát ñònh coù m chöõ soá, xaùc suaát ñoät bieán pj taïi chöõ soá thöù j (1 £ j £ m) Boä xaùc suaát ñoät bieán taïi moät chöõ soá: r1=0.5, r2=r3=0.25 Kyõ thuaät ñoät bieán coù ñònh höôùng for j:=1 to m do if Xaùc_suaát_bieán coá_ngaãu_nhieân_1 = pj then (*ñoät bieán*) if Xaùc_suaát_bieán coá_ngaãu_nhieân_2 = r1 else if Xaùc_suaát_bieán coá_ngaãu_nhieân_2 = r2 (*49->50*) else (*50->49*) else (*khoâng ñoät bieán*) ; Giaûi thuaät keát hôïp 3 lôøi giaûi theo xaùc suaát ñoät bieán Ta khaûo saùt söï lai gheùp giöõa moät lôøi giaûi a vaø n lôøi giaûi b1, b2, . , bn. Baây giôø chuùng ta xem xeùt quaù trình ñoät bieán taïi chöõ soá thöù i cuûa moät bieán quyeát ñònh cuûa lôøi giaûi a. Ta coù caùc tröôøng hôïp sau: Tröôøng hôïp chöõ soá thöù i-1 cuûa bieán quyeát ñònh töông öùng cuûa lôøi giaûi a laø ñuùng Goïi p laø xaùc suaát ñoät bieán laáy giaù trò ngaãu nhieân taïi moät chöõ soá thöù i ñoù. Goïi q laø xaùc suaát ñoät bieán cho pheùp laáy giaù trò cuûa chöõ soá thöù i cuûa moät bieán quyeát ñònh töông öùng trong caùc lôøi giaûi b1, b2, .. , bn. Tröôøng hôïp chöõ soá thöù i-1 cuûa bieán quyeát ñònh töông öùng cuûa lôøi giaûi a laø sai Goïi r laø xaùc suaát ñoät bieán taêng/giaûm moät ñôn vò taïi chöõ soá thöù i cuûa lôøi giaûi a cho tröôøng hôïp chöõ soá tröôùc ñoù (thöù i-1) laø sai. Ta coù caùc coâng thöùc sau: (caùc coâng thöùc p, q, r treân laø keát quaû cuûa thaày Thoâng chöa coâng boá treân caùc taïp chí khoa hoïc) Nhaän xeùt: Khi caùc lôøi giaûi ñaõ ñaït ñöôïc giaù trò gaàn toái öu ta coù baûng so saùnh sau Xaùc suaát 1 lôøi giaûi 2 lôøi giaûi 3 lôøi giaûi 4 lôøi giaûi Ñoät bieán ngaãu nhieân Duy trì giaù trò toát ñaõ coù Ñoät bieán taêng/giaûm moät 33% 33% 33% 20% 60% 20% 11% 78% 11% 6% 88% 6% Khi caùc lôøi giaûi ñaõ ñaït ñöôïc giaù trò gaàn toái öu thì kyõ thuaät lai gheùp ba caù theå cho ta: Xaùc suaát duy trì caùc giaù trò toát ñaõ coù laø 78% Xaùc suaát ñoät bieán ngaãu nhieân laø 11% Xaùc suaát ñoät bieán taêng/giaûm laø 11% Vôùi boä xaùc suaát treân seõ cho chuùng ta duy trì ñöôïc caùc giaù trò toát ñaõ coù ñöôïc cuûa lôøi giaûi vaø ñoät bieán ñuû nhoû ñeå khoâng gaây ra roái loaïn caùc giaù trò maø vaãn coù theå taïo ra caùc giaù trò toát moät caùch baát ngôø. Soá laàn laëp cuûa giaûi thuaät ñeå tìm lôøi giaûi toái öu Xeùt baøi toaùn coù lôøi giaûi goàm n bieán quyeát ñònh vaø moãi bieán quyeát ñònh coù m chöõ soá. Giaû söû vieäc bieán ñoåi cuûa lôøi giaûi khaû thi phuï thuoäc vaøo k (1£k£n) bieán quyeát ñònh, nghóa laø trong moät voøng laëp chæ caàn choïn ra trung bình k bieán quyeát ñònh ñeå gaây taùc ñoäng bieán ñoåi thì ñuû ñeå ñaït ñöôïc lôøi giaûi khaû thi toát hôn lôøi giaûi khaû thi ñang coù. Do ñoù xaùc suaát ñeå moät bieán quyeát ñònh ñöôïc choïn trong moät laàn laëp laø k/n vaø ta coù xaùc suaát ñeå moät bieán quyeát ñònh coù khaû naêng laàn löôït tìm ñöôïc caùc chöõ soá ñuùng töø traùi qua phaûi cuûa lôøi giaûi toái öu laø Chöõ soá thöù 1: Soá laàn laëp laø: Chöõ soá thöù 2: Soá laàn laëp laø: . . . . . . . . . . . . Chöõ soá thöù m: Soá laàn laëp laø: Toång soá laàn laëp ñeå giaûi thuaät coù khaû naêng tìm ñöôïc lôøi giaûi toái öu laàn ñaàu tieân laø Öu vaø khuyeát ñieåm cuûa giaûi thuaät Öu ñieåm Toát ñoái vôùi baøi toaùn toái öu moät muïc tieâu Ñöa ra keát quaû toát hôn caùc phöông phaùp truyeàn thoáng vaø giaûi thuaät di truyeàn. Khuyeát ñieåm Soá laàn laëp raát lôùn. Caùch toå chöùc cuûa chöông trình toái öu soá Xaây döïng caáu truùc trung gian ñeå löu tröõ döõ lieäu Keát hôïp caùc caáu truùc beân döôùi ñeå löu tröõ caùc haøm, bieán, raøng buoäc Node löu bieán value_Var ide_Var Node löu raøng buoäc Value_Rela nNoRe ide_Rela() Node löu haøm, raøng buoäc, bieán Express_Func() nFunc value_Func str_Var() nVar str_Rela() nRela Caáu truùc cuûa chöông trình toái öu soá TRUE BEGIN Entry=HAØM Phaân tích haøm Löu haøm vaøo caáu truùc truùc trung gian Ghi nhaän caùc bieán vaø löu vao caáu truùc trung gian Entry=RAØNG BUOÄC Phaân tích RAØNG BUOÄC Löu RAØNG BUOÄC vaøo caáu truùc truùc trung gian Ghi nhaän caùc bieán vaø löu vao caáu truùc trung gian FALSE Phaùt sinh giaù trò cho bieán vaø toái öu giaù trò ñoù. Gaùn giaù trò vaøo caùc bieán Tính caùc haøm vaø caùc raøng buoäc In keát quaû caùc bieán toái öu Thoûa Raøng buoäc Caùch tính giaù trò cho haøm vaø raøng buoäc Ñoåi sang bieåu thöùc Haäu Toá BEGIN Ñöa giaù trò vaøo caùc phaàn töû cuûa Node Haøm(Raøng Buoäc) Chuoãi=”” Tính giaù trò END False True Chuoãi = Ñoïc giaù trò caùc phaàn töû cuûa Node Haøm(Raøng Buoäc) AÙp duïng vaøo caùc baøi toaùn toái öu soá Baøi toaùn 1 (taøi lieäu cuûa Nguyeãn Troïng Toaøn) Aùp duïng gt cuûa GS. H.Tuïy ñöôc hieäu chænh bôûi N.T. Toaøn Lôøi giaûi toái öu: (6.48079, 21.02378) Giaù trò haøm muïc tieâu: 89.2171143125 Lôøi giaûi vi phaïm nheï raøng buoäc thöù ba: g=0.000035487500>0 Aùp duïng giaûi thuaät TKNNTXS vaøo chöông trình toái öu Giaù trò haøm muïc tieâu: 89.217055385973 Caùc lôøi giaûi toái öu: (6.475902,21.025287) Baøi toaùn 2 (taøi lieäu cuûa Nguyeãn Troïng Toaøn) [] f(x) = (x1-2)^2+(x2-1)^2 ® min vôùi caùc raøng buoäc x1+x2<=5 x1^2-4.4*x1+x2^2-2.4*x2+4.03<=0 4*x1-x1^2-0.36*x2^2-2.56<=0 Aùp duïng gt cuûa GS. H.Tuïy ñöôc hieäu chænh bôûi N.T. Toaøn Lôøi giaûi toái öu: (2.77534,1.526646) Giaù trò haøm muïc tieâu: 0.8785081249 Aùp duïng giaûi thuaät TKNNTXS vaøo chöông trình toái öu Giaù trò haøm muïc tieâu: 0.877508004147348 Caùc lôøi giaûi toái öu: (2.7464411039,1.5659802846) Baøi toaùn 3 veà haøm phi tuyeán Rosenbrock [] f(x) = 100*(x2-x1^2)+(1-x1)^2® min vôùi caùc raøng buoäc x1+x2^2>=0 x1^2+x2>=0 x1<=0.5 x2<=10 Nghieäm toái öu toaøn cuïc Lôøi giaûi toái öu: (0.5,0.25) Giaù trò haøm muïc tieâu: 0.25 Aùp duïng giaûi thuaät TKNNTXS vaøo chöông trình toái öu Giaù trò haøm muïc tieâu: 0.25 Caùc lôøi giaûi toái öu: (0.5,0.250000001) Baøi toaùn 4 (taøi lieäu cuûa Phaïm Hoaøng Vöông) f(x) = x1+2*x2+3*x3+4*x4+5*x5® max vôùi caùc raøng buoäc x1+2*x2+3*x3-4*x4+5*x5<=0 2*x3+x4+3*x5<=4 3*x1+4*x3+x5<=3 x2-x3+2*x5<=2 4*x2+3*x3+x4+2*x5>=1 Nghieäm toái öu toaøn cuïc Lôøi giaûi toái öu: (1,2,0,4,0) Giaù trò haøm muïc tieâu: 21 Aùp duïng giaûi thuaät TKNNTXS vaøo chöông trình toái öu Giaù trò haøm muïc tieâu: 21 Caùc lôøi giaûi toái öu: (1,2,0,4,0) Baøi toaùn 5: Baøi toaùn toái öu phi tuyeán cuûa Himmelblau f(x) = 5.3578547*x3*x3+0.8356891*x1*x5+37.293239*x1-40792.141® min vôùi caùc raøng buoäc 85.334407+0.0056858*x2*x5+0.00026*x1*x4-0.0022053*x3*x5>=0 85.334407+0.0056858*x2*x5+0.00026*x1*x4-0.0022053*x3*x5<=92 80.51249+0.0071317*x2*x5+0.0029955*x1*x2+0.0021813*x3*x3>=90 80.51249+0.0071317*x2*x5+0.0029955*x1*x2+0.0021813*x3*x3<=110 9.300961+0.0047026*x3*x5+0.0012547*x1*x3+0.0019085*x3*x4>=20 9.300961+0.0047026*x3*x5+0.0012547*x1*x3+0.0019085*x3*x4<=25 78<=x1<=102 33<=x2<=45 27<=x3<=45 27<=x4<=45 27<=x5<=45 Himmelblau: phöông phaùp giaûm ñoä doác toång quaùt Homaifar: giaûi thuaät di truyeàn vôùi kích thöôùc quaàn theå laø 400 Gen: giaûi thuaät di truyeàn döïa treân tham khaûo toaøn cuïc vaø cuïc boä Coello: söû duïng kyõ thuaät haøm phaït töï thích nghi döïa cô sôû GTDT Caùc Bieán Lôøi giaûi toát nhaát ñaõ tìm thaáy Chöông trình Coello Gen Hommaifar Himmelblau x1 x2 x3 x4 x5 g1(x) g2(x) g3(x) f(x) 78.000032 33.001783 27.099591 44.999976 44.880584 91.9862825504 100.388288041 20.0000022517 -31023.037906 78.0495 33.0070 27.0810 45.0000 44.9400 91.997635 100.40407857 20.001911 -31020.859 81.4900 34.0900 31.2400 42.2000 34.3700 90.522543 99.318806 20.060410 -30183.576 78.0000 33.0000 29.9950 45.0000 36.7760 90.714681 98.840511 19.999935 -30665.609 78.6200 33.4400 31.0700 44.1800 35.2200 90.520761 98.892933 20.131578 -30373.949 Traân troïng caùm ôn caùc thaày coâ ñaõ theo doõi ñeà taøi naøy. Kyõ thuaät cuûa giaûi thuaät keát hôïp 3 lôøi giaûi theo xaùc suaát ñoät bieán Giaû söû xeùt 3 lôøi giaûi a,b,c. Taïi chöõ soá leû thöù i: if (random(100)<Pi) { d=random(100) if(d else if (d else if (d else if(d else } else