Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây
![Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 1 Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 1](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/238/luan-an-mot-so-thuat-toan-metaheuristic-giai-bai-toan-bao-ph-trang-1_76FVmDC0DT.jpg)
Trang 1
![Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 2 Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 2](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/238/luan-an-mot-so-thuat-toan-metaheuristic-giai-bai-toan-bao-ph-trang-2_kbzbpCqwzc.jpg)
Trang 2
![Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 3 Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 3](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/238/luan-an-mot-so-thuat-toan-metaheuristic-giai-bai-toan-bao-ph-trang-3_uJ6uMSWtxZ.jpg)
Trang 3
![Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 4 Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 4](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/238/luan-an-mot-so-thuat-toan-metaheuristic-giai-bai-toan-bao-ph-trang-4_qsHUSMLtiz.jpg)
Trang 4
![Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 5 Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 5](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/238/luan-an-mot-so-thuat-toan-metaheuristic-giai-bai-toan-bao-ph-trang-5_oVgByFLTn5.jpg)
Trang 5
![Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 6 Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 6](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/238/luan-an-mot-so-thuat-toan-metaheuristic-giai-bai-toan-bao-ph-trang-6_MMK92dznua.jpg)
Trang 6
![Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 7 Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 7](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/238/luan-an-mot-so-thuat-toan-metaheuristic-giai-bai-toan-bao-ph-trang-7_B6tDPTZbIv.jpg)
Trang 7
![Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 8 Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 8](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/238/luan-an-mot-so-thuat-toan-metaheuristic-giai-bai-toan-bao-ph-trang-8_B5G0NHY95q.jpg)
Trang 8
![Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 9 Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 9](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/238/luan-an-mot-so-thuat-toan-metaheuristic-giai-bai-toan-bao-ph-trang-9_rIz344h2su.jpg)
Trang 9
![Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 10 Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây trang 10](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/238/luan-an-mot-so-thuat-toan-metaheuristic-giai-bai-toan-bao-ph-trang-10_oyYPDYTRUr.jpg)
Trang 10
Tải về để xem bản đầy đủ
Bạn đang xem 10 trang mẫu của tài liệu "Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
Tóm tắt nội dung tài liệu: Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây
![Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây](https://s1.thuvienluanvan.org/d2fndtiye73ondva/thumb/2024/03/02/luan-an-mot-so-thuat-toan-metaheuristic-giai-bai-toan-bao-ph_XY5E8EBMEO.jpg)
ửc ẵch cừa bữợc n y º tẵnh toĂn chẵnh xĂc diằn tẵch cừa tĐt cÊ phƯn cừa cĂc cÊm bián trong mởt khe. Xem x²t mội phƯn tỷ cừa mÊng xi cừa tĐt cÊ cĂc giao iºm  tẳm ữủc sau bữợc 1; Náu xi < xi+1, tẵnh diằn tẵch Si ữủc bao phừ tứ cĂc phƯn cừa cÊm bián nơm trong vũng chựa hai ữớng th¯ng song song vợi trửc tung l x = xi v x = xi+1. Nõi cĂch khĂc vũng õ chẵnh l mởt khe. GiÊ sỷ cõ m khe (Si; i = 1; m). Sau khi tẵnh toĂn tĐt cÊ cĂc diằn tẵch cừa mội th nh phƯn Si, bữợc tiáp theo s³ tẵnh tờng diằn tẵch bao phừ cừa tĐt cÊ cĂc cÊm bián ữủc triºn khai trản miãn A bơng cổng thực (2.30). 57 Hẳnh 2.5: Mổ tÊ quĂ trẳnh tẵnh toĂn cừa bữợc 1: Chia miãn A th nh cĂc phƯn nhọ bði cĂc ữớng th¯ng song song vợi trửc tung v ữớng th¯ng n y phÊi tiáp xúc vợi hẳnh trỏn v cĂc giao iºm cừa cĂc hẳnh trỏn. m X S = Si: (2.30) i=1 º tẵnh toĂn ữủc chẵnh xĂc diằn tẵch trản miãn A, tĂc giÊ chia nhọ º tẵnh chẵnh xĂc diằn tẵch bao phừ cừa cĂc cÊm bián trong tứng khe. Mội khe ữủc thº hiằn bði hai ữớng th¯ng song song vợi trửc tung v cưt trửc ho nh tÔi x = a v x = b. Vũng khổng gian bà giợi hÔn bði hai ữớng thơng n y tĂc giÊ gồi l miãn D. X²t mởt cÊm bián Ci ữủc triºn khai trong miãn D náu v ch¿ náu xi − ri ≤ a ≤ xi + ri v xi − ri ≤ b ≤ xi + ri; trong õ, (xi; yi) l tồa ở tƠm cừa cÊm bián cõ bĂn kẵnh cÊm bián . Ci rsi Sau Ơy, tĂc giÊ s³ trẳnh b y cĂc trữớng hủp tẵnh diằn tẵch bao phừ cừa cÊm bián Ci trản miãn D nhữ sau: Trữớng hủp 1: Khi ch¿ cõ mởt cÊm bián Ci, m mởt phƯn cừa diằn tẵch bao phừ cừa cÊm bián Ci nơm trong miãn D °t tản l Areai ữủc tẵnh toĂn dỹa v o 58 cổng thực tứ (2.31), (2.32) án (2.33) v mổ tÊ trong hẳnh 2.6. Z b Z b (2.31) Areai = gi (x)dx − fi (x)dx a a Z b q Z b q 2 2 2 2 (2.32) = yi + ri − (x − xi) dx − yi − ri − (x − xi) dx a a Z b q 2 2 (2.33) =2 ri − (x − xi) dx a Hẳnh 2.6: Trữớng hủp mởt cÊm bián ữủc triºn khai trong miãn D. Trữớng hủp 2: Khi cõ nhiãu cÊm bián ữủc triºn khai trong miãn D v cĂc cÊm bián cõ thº chỗng lản nhau. º cung cĐp kát quÊ chẵnh xĂc cừa diằn tẵch bao phừ cừa cĂc cÊm bián trản miãn D trong trữớng hủp n y, tĂc giÊ sưp xáp tĐt cÊ cĂc cung ữủc tÔo ra tứ phƯn giao nhau cừa cĂc cÊm bián vợi hai ữớng th¯ng song song vợi trửc tung (biản cừa miãn D). QuĂ trẳnh tẵnh toĂn ữủc mổ tÊ nhữ sau: GiÊ sỷ cõ t cÊm bián triºn khai trong miãn D (kỵ hiằu: Ci; i = 1; t). º tẵnh toĂn diằn tẵch bao phừ cừa t cÊm bián trong miãn D ta chia nhọ th nh viằc x²t hai cÊm bián trản miãn D cử thº ữủc trẳnh b y nhữ sau: X²t cÊm bián Ci v Cj; 1 ≤ i; j ≤ t cũng triºn khai trong miãn D. S³ cõ hai trữớng hủp xÊy ra l hai cÊm bián n y khổng giao nhau (Trữớng hủp 2.1) v hai cÊm bián giao nhau (Trữớng hủp 2.2). ữủc mổ tÊ bði hẳnh 2.7 v hẳnh 2.8. Chi tiát cừa tứng trữớng hủp ữủc trẳnh b y nhữ sau: 59 Trữớng hủp 2.1 : Hai cÊm bián Ci v Cj khổng giao nhau trản miãn D ữủc thº hiằn trong hẳnh 2.7 v ữủc tẵnh toĂn theo cổng thực (2.34): Areaij = Areai + Areaj; (2.34) trong õ Areai v Areaj l cổng thực ữủc tẵnh toĂn giống nhữ cổng thực (2.31), (2.32) v (2.33). Trữớng hủp 2.2 : Hai cÊm bián Ci v Cj giao nhau trong miãn D ữủc thº hiằn Hẳnh 2.7: Mổ tÊ trữớng hủp hai cÊm bián khổng giao nhau trản miãn D. bði hẳnh 2.8 v ữủc tẵnh toĂn theo cổng thực (2.35), (2.36) v (2.37): Z b Z b (2.35) Areaij = gi (x)dx − fj (x)dx a a Z b q Z b q 2 2 2 2 (2.36) = yi + ri − (x − xi) dx − yj − rj − (x − xj) dx a a Z b q Z b q 2 2 2 2 (2.37) = (yi − yj)(b − a) + ri − (x − xi) dx + rj − (x − xj) dx a a TĐt cÊ cĂc cổng thực tẵnh tẵch phƠn ữủc ữa ra º tẵnh h m thẵch nghi tẵnh toĂn dỹa trản phữỡng trẳnh (2.38): p Z p x a2 − x2 a2 x a2 − x2dx = + arcsin + c (2.38) 2 2 a 60 Hẳnh 2.8: Mổ tÊ trữớng hủp hai cÊm bián giao nhau trản miãn D. TĐt cÊ quĂ trẳnh tẵnh toĂn chẵnh xĂc h m thẵch nghi ữủc trẳnh b y trong giÊ m cừa thuêt toĂn7. Mằnh ã 4. ở phực tÔp tẵnh toĂn h m thẵch nghi (thuêt toĂn7) l O n3logn. Chựng minh. ở phực tÔp tẵnh toĂn cừa h m thẵch nghi trong thuêt toĂn 7 ữủc tẵnh nhữ sau: Ưu tiản, tẵnh toĂn tĐt cÊ cĂc cĂc giao iºm n ữủc tÔo ra tứ cÊm bián. ở phực tÔp tẵnh toĂn cừa giai oÔn n y l O n2. Do õ, ở phực tÔp tẵnh toĂn cừa tĐt cÊ cĂc khe l O(n2). Ngo i ra, trong mội mởt khe, cƯn tẵnh số lữủng cĂc giao iºm cừa n cÊm bián v sưp xáp lÔi cĂc giao iºm õ. Vẳ vêy, ở phực tÔp tẵnh toĂn l O (nlogn). Do õ, tờng thới gian tẵnh toĂn cừa h m thẵch nghi trong thuêt toĂn7 l O n3logn. f. p dửng VFA nƠng cao chĐt lữủng lới giÊi Sau mởt số thá hằ giÊi thuêt ã xuĐt MIGA khổng cÊi tián ữủc chĐt lữủng lới giÊi. º nƠng cao chĐt lữủng lới giÊi bữợc tiáp theo tĂc giÊ Ăp dửng mởt thuêt toĂn lỹc ây Êo (Virtual Force Algorithm-VFA)  ữủc giợi thiằu trong [96]. Mửc ẵch cừa VFA º hiằu ch¿nh và trẵ °t cĂc cÊm bián trản miãn A sao cho cĂc cÊm bián chỗng nhau s³ ữủc ây ra khọi nhau v cĂc cÊm bián ữủc triºn khai vữủt ra ngo i biản trong miãn A s³ ữủc ây v o trong miãn A. Chi tiát cừa thuêt toĂn VFA  ữủc trẳnh b y trong [34]. 61 Mằnh ã 5. ở phực tÔp tẵnh toĂn cừa thuêt toĂn MIGA (Thuêt toĂn8) l O((NlogN + Nn3logn) ì MAXGEN). Chựng minh. ở phực tÔp tẵnh toĂn cừa thuêt toĂn MIGA= (Thới gian khði tÔo)+(Thới gian tián hõa tÔi mội thá hằ)ì(Số thá hằ). Cử thº nhữ sau: • Thới gian khði tÔo quƯn thº l O(Nn3logn). Trong õ, O(n3logn) l thới gian tẵnh giĂ trà h m fitness cho mội cĂ thº trong quƯn thº bơng thuêt toĂn7 v N l số lữủng cĂ thº trong quƯn thº. • Thới gian tẵnh toĂn hai toĂn tỷ lai gh²p (AMXO v LX) l O(n). • Thới gian tẵnh toĂn cừa toĂn tỷ ởt bián cừa Gauss ởng l O(n). • Thới gian cừa bữợc chồn lồc l O(NlogN). Do õ, thới gian tẵnh toĂn cừa thuêt toĂn MIGA l : O((NlogN + Nn3logn) ì MAXGEN). 62 Algorithm 7: Tẵnh chẵnh xĂc h m thẵch nghi - exactF itness Input : CĂ thº S Output : Tờng diằn tẵch bao phừ cừa cĂc cÊm bián ữủc triºn khai trản miãn A vợi lới giÊi S 1 Function area (c); 2 a ứ; 3 index 0; 4 // Tẵnh số lữủng khe 5 for i=1 to n do 6 a (index) xi − ri; 7 index index + 1; 8 a (index) xi + ri; 9 index index + 1; 10 for i=1 to n do 11 if ci giao nhau cj then 12 ponits iºm giao cừa ci v cj; 13 end 14 for p in points do 15 a (index) p:x; 16 index index + 1; 17 end 18 end 19 end 20 Sort(a); 21 k kẵch thữợc cừa mÊng a; 22 s 0; 23 for i=1 to k-1 do 24 intersection ứ; 25 index 0; 26 // Tẵnh số giao iºm trong mởt khe 27 for j to n do 28 if cj giao vợi khe thự i then 29 points iºm giao cừa cj vợi biản cừa khe thự i; 30 for p in points do 31 intersection(index) p:y; 32 index index + 1; 33 end 34 end 35 end 36 Sort(intersection); 37 Tẵnh diằn tẵch bao phừ cừa cĂc cÊm bián trong khe thự i (Areai); 38 s s + Areai; 39 end 40 return s 63 Algorithm 8: MIGA Input : n: số lữủng cÊm bián k: số loÔi cÊm bián ni: số cÊm bián loÔi i; i = 1::k ri: bĂn kẵnh cÊm bián loÔi i; i = 1::k W; H: kẵch thữợc cừa mián quan tƠm A = W ì H Output : Tờng diằn tẵch bao phừ S cừa tĐt cÊ cĂc cÊm bián trản miãn A Và trẵ triºn khai cừa n cÊm bián trản miãn A 1 Khði tÔo quƯn thº gỗm N cĂ thº Si; i = 1::N; 2 Gbest l cĂ thº tốt nhĐt trong quƯn thº; 3 while (t < MAXGEN) v (Gbest văn ữủc cÊi thiằn) do 4 for i=1 to N do 5 Sinh ngău nhiản số random1 2 [0; 1]; 6 if random1 < p then 7 Sinh ngău nhiản số nguyản j trong [1,N] vợi j 6= i; 8 Thỹc hiằn lai gh²p AMXO; 9 Zi1;Zi2 = AMXO(Si;Sj) ; 10 end 11 if random1 ≥ p then 12 Sinh ngău nhiản số nguyản j trong [1,N] vợi j 6= i; 13 Thỹc hiằn lai gh²p LX; 14 Zi1;Zi2 = LX(Si;Sj); 15 end 16 Sinh ngău nhiản số random2 2 [0; 1]; 17 if 1 then random2 ≤ N 18 Thỹc hiằn ởt bián Gauss ởng; 19 Zi1;Zi2 = Gauss(Zi1;Zi2); 20 end 21 p dửng giÊi thuêt VFA [26] lản Zi1;Zi2; 22 fitness(Zi1), fitness(Zi2) = exactF itness(Zi1), exactF itness(Zi2); 23 end 24 Q = S [ Z; 25 Sưp xáp cĂc cĂ thº trong Q thổng qua h m fitness; 26 S= têp N cĂ thº tốt nhĐt trong Q; 27 Cêp nhêt Gbest; 28 t = t + 1; 29 end 30 // Kát quÊ thu ữủc sau cĂc bữợc l°p l và trẵ tốt nhĐt tẳm ữủc º triºn khai cĂc cÊm bián trản miãn A (Gbest). 31 return Gbest v fitness(Gbest) 64 2.3 Kát quÊ thỹc nghiằm 2.3.1 Dỳ liằu thỹc nghiằm TĂc giÊ tián h nh thỹc nghiằm trản 15 bở dỳ liằu  ữủc xƠy dỹng bði [32]. Chi tiát cừa tứng bở dỳ liằu thỹc nghiằm ữủc trẳnh b y trong bÊng 2.1 • Vũng cƯn bao phừ cõ kẵch thữợc A: 100 x 100. • Cõ ba loÔi cÊm bián vợi mội loÔi cõ mởt bĂn kẵnh cÊm bián r1, r2, r3 cử thº r2 = 0.8 x r1 v r3 = 0.8 x r2. • Số cÊm bián mội loÔi (n1; n2; n3) ữủc xĂc ành phử thuởc v o tờng diằn tẵch bao phừ ữủc cừa n (n = n1 + n2 + n3) cÊm bián ữủc triºn khai trản miãn A (Upper Bound). Tờng diằn tẵch n y ữủc tẵnh vợi giÊ sỷ miãn bao phừ ữủc cừa n cÊm bián khổng bà chỗng lản nhau. BÊng 2.1: Dỳ liằu thỹc nghiằm. Dataset r1 n1 r2 n2 r3 n3 n Upper Bound s1-07 14.00 5 11.20 5 8.96 7 17 6841.7 s2-07 12.00 6 9.60 8 7.68 10 24 6883.6 s3-07 10.00 8 8.00 12 6.40 16 36 6984.9 s4-07 8.00 12 6.40 18 5.12 27 57 6952.6 s5-07 6.00 22 4.80 32 3.84 47 101 6981.6 s1-08 14.00 5 11.20 6 8.96 10 21 7965.4 s2-08 12.00 6 9.60 9 7.68 14 29 7914.3 s3-08 10.00 9 8.00 13 6.40 19 41 7886.2 s4-08 8.00 14 6.40 20 5.12 29 63 7776.8 s5-08 6.00 25 4.80 36 3.84 55 116 7981.1 s1-09 14.00 6 11.20 7 8.96 10 23 8975.2 s2-09 12.00 7 9.60 11 7.68 14 32 8945.7 s3-09 10.00 11 8.00 14 6.40 21 46 8972.9 s4-09 8.00 16 6.40 23 5.12 34 73 8976.7 s5-09 6.00 28 4.80 41 3.84 61 130 8960.2 2.3.2 Tham số thỹc nghiằm º tián h nh thỹc nghiằm cĂc giÊi thuêt ã xuĐt, tĂc giÊ Â mổ phọng lÔi cĂc giÊi thuêt bơng ngổn ngỳ lêp trẳnh Java, chÔy trản mổi trữớng hằ iãu h nh Windows 10 Professional, vợi cĂc thổng số phƯn cựng: Intel Core i5-2.4 GHz, RAM 8GB 1600 MHz DDR3. 65 BÊng 2.2: BÊng tham số thỹc nghiằm cừa cĂc giÊi thuêt DPSO Tham số thỹc nghiằm GiĂ trà Số lƯn chÔy mội bở dỳ liằu 30 Kẵch thữợc quƯn thº 50 Số thá hằ tối a 1000 ∆ trong DPSO 10−6 Trồng số quĂn tẵnh ! GiÊm tuyán tẵnh tứ 0.9 án 0.4 Tham số c1, c2 v c3 0.5 Số iºm gieo theo Monte Carlo (L) 1000000 GiÊi thuêt ã xuĐt s³ ữủc tián h nh thỹc nghiằm vợi 15 bở dỳ liằu  ữủc mổ tÊ ð trản. º kiºm chựng sỹ ờn ành cừa thuêt toĂn, tĂc giÊ cho chÔy giÊi thuêt ã xuĐt 30 lƯn vợi mội bở dỳ liằu. Diằn tẵch bao phừ cừa cĂ thº tốt nhĐt sau 30 lƯn chÔy s³ ữủc tẵnh trung bẳnh v so sĂnh vợi giÊi thuêt IGA trong [34]. Mửc ẵch º Ănh giĂ hiằu quÊ cừa giÊi thuêt ã xuĐt. Sỹ ờn ành cừa giÊi thuêt s³ ữủc thº hiằn qua giĂ trà ở lằch chuân theo phữỡng phĂp thống kả. CĂc tham số cừa DPSO, ICS, CFPA v MIGA ữủc thiát lêp nhữ mổ tÊ trong bÊng 2.2, 2.3, 2.4 v bÊng 2.5. BÊng 2.3: BÊng tham số thỹc nghiằm cừa giÊi thuêt ICS Tham số GiĂ trà Số lƯn chÔy mội bở dỳ liằu 30 Kẵch thữợc quƯn thº 20 Số cĂ thº khði tÔo heuristic 10 Số cĂ thº Cuckoo 10 Số thá hằ tối a 1000 XĂc suĐt phĂt hiằn trựng Cuckoo tối a ( ) 0.5 pamax XĂc suĐt phĂt hiằn trựng Cuckoo tối thiºu ( ) 0.05 pamin αmax 0.5 αmin 0.01 XĂc suĐt rới bọ tờ khi phĂt hiằn trựng Cuckoo 0.5 Số iºm giao Monte Carlo (L) 1000000 66 BÊng 2.4: BÊng tham số thỹc nghiằm cừa giÊi thuêt CFPA Tham số GiĂ trà Số lƯn chÔy mội bở dỳ liằu 30 Kẵch thữợc quƯn thº 50 Số cĂ thº khði tÔo heuristic 25 Số thá hằ tối a 1000 XĂc suĐt thử phĐn to n cửc tối a (pmax) 80% XĂc suĐt thử phĐn to n cửc tối thiºu (pmin) 50% αmax 0.5 αmin 0.01 βmax 0.5 βmax 0.01 Số iºm giao Monte Carlo (L) 1000000 BÊng 2.5: Tham số thỹc nghiằm cừa giÊi thuêt MIGA. Tham số GiĂ trà Số lƯn chÔy cừa mội bở dỳ liằu 30 Kẵch thữợc quƯn thº 50 Số cĂ thº khði tÔo heuristic 50 Số thá hằ tối a 1000 T lằ lai gh²p AMXO 0.9 T lằ lai gh²p LX 0.1 T lằ ởt bián 1/n 67 2.3.3 So sĂnh Ănh giĂ kát quÊ thỹc nghiằm º tẵnh diằn tẵch cừa cĂc cÊm bián ữủc triºn khai trản miãn A. TĂc giÊ sỷ dửng phữỡng phĂp Monter Carlo. ị tữðng cừa phữỡng phĂp n y l sinh ngău nhiản L iºm. T lằ diằn tẵch bao phừ cừa tĐt cÊ cĂc cÊm bián ữủc triºn khai trản miãn A s³ xĐp x¿ vợi số lữủng cĂc iºm gieo thuởc vũng bao phừ cừa cĂc cÊm bián trản L iºm gieo. º ữa ra mởt Ănh giĂ khĂch quan v tờng quĂt hiằu quÊ cừa cĂc giÊi thuêt ã xuĐt v th nh phƯn n o trong mội giÊi thuêt ã xuĐt quyát ành chĐt lữủng cừa lới giÊi. TĂc giÊ ữa ra hai thỹc nghiằm Ănh giĂ. • Thỹc nghiằm 1. Ănh giĂ hiằu quÊ cừa cĂc giÊi thuêt ã xuĐt khi sỷ dửng cũng mởt h m thẵch nghi l ở chỗng Olap() ữủc ã xuĐt bði [34]. • Thỹc nghiằm 2. Ănh giĂ hiằu quÊ cừa tĐt cÊ cĂc giÊi thuêt ã xuĐt v so sĂnh vợi giÊi thuêt IGA l giÊi thuêt tốt nhĐt tẵnh án thới iºm hiằn tÔi º giÊi quyát b i toĂn cỹc Ôi diằn tẵch bao phừ trong mÔng cÊm bián khổng dƠy khổng ỗng nhĐt ữủc ữa ra bði Y.Yoon v cĂc cởng sỹ trong [32]. Thỹc nghiằm 1 Mửc ẵch cừa thỹc nghiằm n y º Ănh giĂ hiằu quÊ cừa cĂc giÊi thuêt ã xuĐt khi cũng sỷ dửng mởt h m thẵch nghi l ở chỗng Olap()  ữủc ã xuĐt trong [34]. Cử thº kát quÊ cừa cĂc giÊi thuêt ã xuĐt DPSO, ICS v CFPA ữủc so sĂnh vợi IGA [34] trản 15 bở dỳ liằu  trẳnh b y trong bÊng 2.1. BÊng 2.6 minh hồa hiằu quÊ cừa cĂc thuêt toĂn, cĂc số liằu ữa ra gỗm ở bao phừ trung bẳnh, thới gian tẵnh toĂn trung bẳnh sau 30 lƯn chÔy mội bở dỳ liằu. Kát quÊ thỹc nghiằm cho thĐy, DPSO, CFPA v ICS ữa ra chĐt lữủng lới giÊi v thới gian tẵnh toĂn tốt hỡn giÊi thuêt IGA [34]. Mởt trong nhỳng cÊi tián Ăng chú ỵ nhĐt cừa ICS l thới gian tẵnh toĂn. Kát quÊ ữủc thº hiằn trong hẳnh 2.9. ICS thu ữủc thới gian thỹc hiằn tốt nhĐt 8/15 bở dỳ liằu vợi nhỳng bở dỳ liằu cõ số lữủng cÊm bián nhọ (n < 50) khi so sĂnh vợi ba giÊi thuêt IGA, DPSO v CFPA. M°t khĂc, CFPA ữa ra ữu thá vã thới gian chÔy vợi nhỳng bở cõ số lữủng cÊm bián lợn (n > 50). CFPA tốt hỡn 7/15 bở dỳ liằu khi so sĂnh vã thới gian tẵnh vợi ba giÊi thuêt IGA, DPSO v ICS. Cử thº, khi so sĂnh vã thới gian tẵnh giỳa DPSO, ICS v CFPA nhên thĐy CFPA tốt hỡn ICS tứ 47% - 69.05% vã thới gian tẵnh toĂn vợi nhỳng bở dỳ liằu cõ số cÊm bián lợn (n > 50). Lỵ do cÊi tián rĐt lợn thới gian tẵnh cừa 3 giÊi thuêt DPSO, ICS v CFPA l nơm trong bÊn thƠn thuởc tẵnh riảng cừa tứng 68 BÊng 2.6: Trung bẳnh diằn tẵch bao phừ v thới gian tẵnh cừa cĂc giÊi thuêt IGA, DPSO, ICS v CFPA trản 15 bở dỳ liằu v mội bở dỳ liằu ữủc chÔy 30 lƯn lĐy trung bẳnh (Avg: Trung bẳnh diằn tẵch bao phừ, Time: Trung bẳnh thới gian tẵnh (ms) v Upper Bound: diằn tẵch lợn nhĐt cừa tứng bở dỳ liằu Ôt ữủc.) IGA DPSO CFPA ICS Dataset Upper Bound Avg Time Avg Time Avg Time Avg Time s1-07 6814.66 2641.23 6815.27 906.07 6813.34 668.10 6815.01 462.2 6814.65 s2-07 6882.98 4789.27 6884.79 1554.47 6884.72 1009.43 6883.26 743.20 6883.56 s3-07 6984.39 9897.80 6985.52 3377.47 6986.14 1652.73 6984.89 1505.90 6984.89 s4-07 6952.54 22181.47 6953.53 8056.63 6952.38 3234.07 6952.82 5519.80 6952.56 s5-07 6981.65 69896.93 6984.34 24556.77 6981.11 7638.47 6981.43 14699.30 6981.63 s1-08 7923.84 4138.27 7915.18 1455.20 7925.37 975.67 7902.49 694.6 7965.37 s2-08 7892.72 7089.73 7882.57 2773.33 7886.59 1497.67 7888.70 1090.3 7914.28 s3-08 7869.23 13330.17 7872.44 4946.57 7875.14 2353.60 7876.51 1806.80 7886.15 s4-08 7773.61 29358.00 7776.98 10306.30 7776.96 4363.70 7776.32 6322.80 7776.75 s5-08 7975.01 96051.30 7978.79 38679.10 7979.04 11865.07 7981.85 19118.90 7981.05 s1-09 8661.06 5124.13 8616.99 1708.83 8637.19 1178.43 8595.54 829.10 8975.20 s2-09 8648.65 8910.23 8645.71 3315.07 8623.44 1727.30 8629.43 1277.83 8945.73 s3-09 8681.20 17092.63 8688.13 6457.20 8675.48 2375.03 8704.35 2387.33 8972.89 s4-09 8730.00 38431.87 8725.22 14424.97 8707.50 4660.73 8742.22 8566.93 8976.69 s5-09 8755.44 112652.73 8741.31 42720.23 8722.98 11833.67 8774.14 24922.86 8960.20 Hẳnh 2.9: Thới gian tẵnh toĂn cừa cĂc thuêt toĂn IGA, DPSO, ICS, CFPA 69 giÊi thuêt. GiÊi thuêt ICS sỷ dửng nhỳng bữợc i ngău nhiản v nhỳng cÊi tián vã tham số sỷ dửng dăn án tốc ở hởi tử cao ngay ð thá hằ thự 300 ữủc thº hiằn ð hẳnh 2.10. M°t khĂc, CFPA tên dửng sỹ ờn ành cừa hoa, cho ph²p nhỳng bổng hoa tữỡng ựng trao ời phĐn hoa trong mội lƯn thử phĐn º cõ ở hởi tử cao. Hẳnh 2.10: ở hởi tử cừa cĂc thuêt toĂn IGA, PSO, ICS, CFPA vợi bở dỳ liằu s5-07 Vã m°t ở bao phừ, CFPA v ICS ữa ra cĂc giÊi phĂp tữỡng ối tốt khi so sĂnh vợi IGA. Cử thº, CFPA mang lÔi kát quÊ tốt nhĐt vợi cĂc bở dỳ liằu s1-08, s4-08. ICS mang lÔi kát quÊ tốt nhĐt vợi cĂc bở dỳ liằu s3-08, s5-08, s3-09, s4-09 v °c biằt tốt vợi bở dỳ liằu s5-09. Ngo i ra, cĂc giÊi phĂp m DPSO ữa ra chĐt lữủng lới giÊi cõ t¿ lằ thĐp hỡn khổng Ăng kº so vợi ICS, CFPA v IGA. Thỹc nghiằm 2 Mửc ẵch cừa thỹc nghiằm n y º so sĂnh vã diằn tẵch bao phừ, thới gian tẵnh v ở lằch chuân cừa cĂc giÊi thuêt ã xuĐt (MIGA, DPSO, ICS v CFPA) vợi giÊi thuêt IGA trong [34] cho b i toĂn cỹc Ôi diằn tẵch bao phừ trong mÔng cÊm bián khổng dƠy khổng ỗng nhĐt. Mội bở dỳ liằu thỹc nghiằm 30 lƯn v tẵnh trung bẳnh cĂc giÊi phĂp vã diằn tẵch bao phừ, thới gian tẵnh v ở lằch chuân. Chi tiát cừa tứng giÊi phĂp ữủc trẳnh b y dữợi Ơy. Ưu tiản, tĂc giÊ Ănh giĂ vã trung bẳnh diằn tẵch bao phừ cừa 5 giÊi thuêt (IGA, MIGA, DPSO, ICS v CFPA). º Ănh giĂ tiảu chẵ n y tĂc giÊ thống kả kát quÊ cừa 5 giÊi thuêt theo cĂc tiảu chẵ bao phừ 70%, 80% v 90% diằn tẵch trản miãn A. Kát quÊ lƯn lữủt ữủc thº hiằn trong cĂc hẳnh 2.11, hẳnh 2.12, hẳnh 2.13 v trong bÊng 2.7. Ta cõ thº nhên thĐy, MIGA ữa ra kát quÊ tốt 14/15 bở dỳ liằu khi so sĂnh vợi 4 giÊi thuêt IGA, DPSO, CFPA v ICS. °c biằt vợi bở 70 dỳ liằu bao phừ 70% (bở dỳ liằu tứ s1-07 án s5-07) diằn tẵch trản miãn A thẳ MIGA cho kát quÊ bơng cên trản (Upper bound) v MIGA tốt hỡn ICS khoÊng 1.5% vã diằn tẵch bao phừ (ICS l thuêt toĂn tốt nhĐt hiằn tÔi khi sỷ dửng h m thẵch nghi l ở chỗng Olap()). Hẳnh 2.11: Trung bẳnh diằn tẵch bao phừ cừa cĂc giÊi thuêt IGA, DPSO, ICS, CFPA v MIGA trản cĂc bở dỳ liằu bao phừ 70% diằn tẵch trản miãn A. Thự hai, tĂc giÊ Ănh giĂ vã ở lằch chuân cừa 5 giÊi thuêt (IGA, DPSO, CFPA, ICS v MIGA). Tứ bÊng 2.7 v hẳnh 2.14 cõ thº nhên x²t rơng MIGA thu ữủc ở lằch chuân thĐp nhĐt khi so vợi 4 giÊi thuêt cỏn lÔi trản tĐt cÊ 15 bở dỳ liằu. Cõ ữủc kát quÊ n y l do MIGA sỷ dửng h m thẵch nghi tẵnh chẵnh xĂc diằn tẵch bao phừ cừa cĂc cÊm bián ữủc triºn khai trản miãn A cỏn 4 giÊi thuêt IGA, DPSO, CFPA v ICS sỷ dửng lÔi h m thẵch nghi tẵnh gƯn úng. Do õ, sai số vã trung bẳnh diằn tẵch bao phừ cừa cĂc thuêt toĂn IGA, DPSO, CFPA v ICS cao hỡn MIGA. Thự ba, tĂc giÊ Ănh giĂ vã thới gian tẵnh toĂn cừa 5 giÊi thuêt (IGA, DPSO, CFPA, ICS v MIGA) ữủc thº hiằn trong hẳnh 2.15. Kát quÊ thỷ nghiằm thỹc sỹ cho thĐy thới gian tẵnh toĂn cừa MIGA trung bẳnh cao gĐp 3 lƯn so vợi ICS Ôt ữủc. iãu n y l cõ thº giÊi thẵch l do ICS khĂm phĂ khổng gian tẳm kiám hiằu quÊ hỡn nhớ Ăp dửng nhỳng bữợc nhÊy ngău nhiản v sỹ cÊi tián cừa viằc lỹa chồn tham số cho b i toĂn dăn án tốc ở hởi tử cao ngay ð thá hằ thự 300 ữủc thº hiằn ð hẳnh 2.10. Tuy nhiản, tứ tứng ựng dửng cừa b i toĂn º cƠn nhưc trong viằc lỹa chồn giỳa ở ờn ành cừa cĂc giÊi phĂp ã xuĐt hay thới gian tẵnh toĂn. 71 Hẳnh 2.12: Trung bẳnh diằn tẵch bao phừ cừa cĂc giÊi thuêt IGA, DPSO, ICS, CFPA v MIGA trản cĂc bở dỳ liằu bao phừ 80% diằn tẵch trản miãn A. Hẳnh 2.13: Trung bẳnh diằn tẵch bao phừ cừa cĂc giÊi thuêt IGA, DPSO, ICS, CFPA v MIGA trản cĂc bở dỳ liằu bao phừ 90% diằn tẵch trản miãn A. 72 BÊng 2.7: Trung bẳnh diằn tẵch bao phừ v ở lằch chuân cừa cĂc giÊi thuêt IGA, DPSO, ICS, CFPA v MIGA trản 15 bở dỳ liằu v mội bở dỳ liằu chÔy thỹc nghiằm 30 lƯn lĐy trung bẳnh (Avg: Trung bẳnh diằn tẵch bao phừ, ở lằch chuân (SD) v Upper Bound: diằn tẵch lợn nhĐt cừa tứng bở dỳ liằu Ôt ữủc.) IGA DPSO CFPA ICS MIGA Upper Dataset Avg SD Avg SD Avg SD Avg SD Avg SD Bound s1_07 6814.2 2.43 6
File đính kèm:
luan_an_mot_so_thuat_toan_metaheuristic_giai_bai_toan_bao_ph.pdf
thông tin tóm tắt về những kết luận mới của luận án.pdf
Tóm tắt luận án.pdf