2.4.2. Thuật toán
Các cải tiến của DEM được trình bày trong Algorithm 2.6 dưới đây.
Algorithm 2.6. Thuật toán DEM
Input : tmax - số thế hệ tối đa, dataset
Output : cá thể tốt nhất và thời gian thực hiện dự án
1. Begin
2. Load and Valid iMOPSE dataset 3. t = 0
4. Pall = Initial population
5. {Pbest, makespan} = fbest(Pall)
6. while( t< tmax)
7. for (int i = 0; i< Size; i++)
8. P1 P2 P3 Pi = Lấy ngẫu nhiên cá thể từ Pall 9. F = rand(0,1)
10. Vi = P1 + F (P2 - P3) // parameter of the mutation operator
11. for(j=0; j 12. randi,j = rand(0,1) 13. if (rani,j <= CR or i < Irand) 14. Ui,j = Vi,j 15. else 16. Ui,j = Pi,j 17. end if 18. end for 19. if(f(Ui)f(Pi)) 20. Pi = Ui 21. end if 22. end for 23. {Pbest, makespan} = fbest(Pall) 24. Pbest = Reallocate(Pbest) 25. {Pbest, makespan} = fbest(Pall) 26. t = t+1 27. end while 29. End Trong đó: f: hàm mục tiêu fbest: hàm trả lại cá thể tốt nhất Có thể bạn quan tâm! Xem toàn bộ 156 trang tài liệu này. 2.4.3. Kết quả thực nghiệm Để thực nghiệm thuật toán DEM, luận án sử dụng bộ dữ liệu iMOPSE trong bảng 2.11, các thông số thực nghiệm được thiết lập tương tự như trong mục 2.3.3.2. Kết quả thực nghiệm được trình bày như trong bảng 2.17 sau đây. Bảng 2.17: Kết quả thực nghiệm DEM với bộ dữ liệu iMOPSE TT Dataeset GA-M HAntCO GRASP DEM BEST AVG STD BEST AVG STD BEST AVG STD BEST AVG STD 1 100_5_22_15 517 524 5.3 504 505 0.8 503 504 0.5 484 486 1.8 2 100_5_46_15 584 587 4.7 604 604 0 552 556 2.6 528 529 2.1 3 100_5_48_9 528 535 9.7 521 523 1.6 510 510 0.8 489 491.7 1.3 4 100_5_64_15 527 530 2.5 516 523 2.9 501 502 0.8 495 499 1.5 5 100_5_64_9 508 521 9.9 507 515 3.9 494 494 0.6 485 488.7 0.6 6 100_10_26_15 292 292 0.0 266 270 2.2 251 258 3.2 232 235 3.8 7 100_10_47_9 296 296 0.0 297 302 4 263 264 0.7 252 254.7 1 8 100_10_48_15 279 282 2.9 278 286 4.4 256 257 1.2 243 245.2 0.5 9 100_10_64_9 296 305 6.6 287 296 5.1 255 257 1.9 251 253 1.9 10 100_10_65_15 286 290 5.0 281 287 3.5 256 260 1.9 249 252.1 1.2 11 100_20_22_15 163 169 5.8 161 170 3.6 134 137 1.6 128 131.4 0.5 12 100_20_46_15 197 207 6.9 194 199 2.6 170 174 3.1 161 163.1 1.6 13 100_20_47_9 185 186 0.5 180 187 3.7 133 140 2.2 123 125.2 2.7 14 100_20_65_15 240 240 0.5 218 220 2.7 213 213 0 210 213.3 0.8 TT Dataeset GA-M HAntCO GRASP DEM BEST AVG STD BEST AVG STD BEST AVG STD BEST AVG STD 15 100_20_65_9 181 187 4.5 180 185 3.1 135 135 1.4 125 126.7 1.4 16 200_10_128_15 577 583 4.9 522 528 3.1 491 496 4.2 460 463.8 1.1 17 200_10_50_15 553 577 17.5 529 543 8 524 528 3.8 484 486.2 0.4 18 200_10_50_9 585 589 5.0 546 556 4.8 506 508 1.4 484 486.7 0.9 19 200_10_84_9 567 583 11.4 571 581 6.9 526 527 0.8 521 523 1.6 20 200_10_85_15 549 555 4.9 526 538 6.5 496 498 1.1 481 483.3 2.3 21 200_20_145_15 326 328 2.0 309 314 4.4 262 271 4.2 242 244.9 0.3 22 200_20_54_15 363 385 20.8 336 349 6.6 304 308 3.7 257 259.3 2.3 23 200_20_55_9 312 318 4.2 313 317 3.1 257 258 0.6 248 250 5.7 24 200_20_97_15 424 438 9.7 356 368 4.8 347 347 0 330 332.3 3.5 25 200_20_97_9 321 326 6.2 326 332 4.1 253 256 1.6 240 245.6 4.1 26 200_40_133_15 215 222 6.2 214 221 3.4 163 170 4.1 139 144.1 3.9 27 200_40_45_15 201 210 6.3 206 212 2.6 164 164 0 162 163.9 0.6 28 200_40_45_9 209 213 2.9 209 215 3.8 144 147 1.6 151 163 12.5 29 200_40_90_9 211 215 3.1 211 214 1.8 148 153 4.5 146 154 7.7 30 200_40_91_15 200 205 3.4 207 212 2.9 153 159 2.6 131 137 5.3 Bảng 2.18: So sánh kết quả thực nghiệm DEM với các thuật toán Thuật toán BEST AVG Tổng STD Số lượng Tỉ lệ (%) Số lượng Tỉ lệ (%) Từ Đến Từ Đến DEM 74.9 GA-M 30/30 4.53 33.51 30/30 5.79 32.71 173.3 HAntCO 30/30 3.67 36.71 30/30 3.05 35.38 173.32 GRASP 29/30 -4.86 15.46 27/30 -10.88 15.81 56.7 Trong bảng 2.18: - Cột “Số lượng” thể hiện số bộ dữ liệu (trên tổng số 30 bộ) mà thuật toán DEM có kết quả tốt hơn thuật toán ở hàng tương ứng. - Tỉ lệ (%) cho biết kết quả của DEM tốt hơn/kém hơn các thuật toán còn lại. Giá trị âm thể hiện một vài trường hợp mà DEM cho kết quả kém hơn. Bảng 2.19: So sánh kết quả thực nghiệm DEM với M-PSO Dataset DEM M-PSO BEST AVG STD BEST AVG STD 100_5_22_15 484 486 1.8 485 486 1.7 100_5_46_15 528 529 2.1 530 531 0.5 100_5_48_9 489 491.7 1.3 490 492 1.6 100_5_64_15 495 499 1.5 478 479 1.3 100_5_64_9 485 488.7 0.6 471 474 2.5 100_10_26_15 232 235 3.8 233 233 0.4 100_10_47_9 252 254.7 1 257 261 3.7 100_10_48_15 243 245.2 0.5 244 245 0.6 100_10_64_9 251 253 1.9 240 246 5.9 100_10_65_15 249 252.1 1.2 244 245 1.3 100_20_22_15 128 131.4 0.5 128 131 3.1 100_20_46_15 161 163.1 1.6 162 165 2.9 Dataset DEM M-PSO BEST AVG STD BEST AVG STD 100_20_47_9 123 125.2 2.7 124 128 3.6 100_20_65_15 210 213.3 0.8 228 230 1.8 100_20_65_9 125 126.7 1.4 125 125 0.3 200_10_128_15 460 463.8 1.1 461 464 2.7 200_10_50_15 484 486.2 0.4 489 490 0.7 200_10_50_9 484 486.7 0.9 487 491 3.7 200_10_84_9 521 523 1.6 508 510 2.1 200_10_85_15 481 483.3 2.3 473 476 2.5 200_20_145_15 242 244.9 0.3 236 237 1.4 200_20_54_15 257 259.3 2.3 256 256 0.3 200_20_55_9 248 250 5.7 251 255 3.5 200_20_97_15 330 332.3 3.5 334 337 3.3 200_20_97_9 240 245.6 4.1 255 256 0.9 200_40_133_15 139 144.1 3.9 147 151 4.1 200_40_45_15 162 163.9 0.6 163 167 4 200_40_45_9 151 163 12.5 152 162 9.5 200_40_90_9 146 154 7.7 145 152 7.1 200_40_91_15 131 137 5.3 135 143 8.3 2.4.4. Đánh giá chất lượng lời giải của thuật toán Luận án đã tiến hành thực nghiệm thuật toán DEM áp dụng cho bài toán MS-RCPSP. Thực nghiệm được chạy trên 30 bộ dữ liệu iMOPSE, với số lần chạy thực nghiệm là 50 lần, số thế hệ tiến hóa là 100.000, thuật toán được cài đặt trên môi trường thử nghiệm Matlab 2014. Kết quả thực nghiệm được trình bày trong bảng 2.17. Kết quả thực nghiệm được tổng hợp và so sánh trong bảng 2.18. So sánh với GA-M cải tiến của nhóm Myszkowski, ta thấy: - Về giá trị BEST và AVG: DEM tốt hơn GA-M trong tất cả các trường hợp, trong đó giá trị BEST tốt hơn GA-M từ 4.53% đến 33.51% (chi tiết trong hình 2.12)., giá trị AVG tốt hơn GA-M từ 5.79% đến 32.71% (chi tiết trong hình 2.14). - Về giá trị độ lệch chuẩn STD, tổng độ lệch chuẩn của GA-M là 173.3, của DEM là 74.9 (chi tiết trong hình 2.13).. Từ kết quả này, có thể thấy, thuật toán DEM mang lại hiệu quả cao hơn thuật toán GA-M và tính ổn định của DEM cũng tốt hơn. So sánh với các thuật toán lai (hybrid) khác - Bảng 2.18 cho thấy, kết quả của DEM có kết quả tốt hơn các thuật toán lai ở hầu hết các trường hợp, cụ thể: tốt hơn HAntCO với tất cả các bộ dữ liệu (30/30), tốt hơn GRASP 26/30 bộ dữ liệu với giá trị BEST. Một số trường hợp DEM kém hơn các thuật toán lai, tuy nhiên, giá trị kém hơn không nhiều. Xét về tổng số các bộ dữ liệu, DEM tốt hơn các thuật toán lai ở hầu hết các trường hợp. Bảng 2.19 so sánh kết quả thực nghiệm của thuật toán M-PSO và thuật toán DEM trên bộ dữ liệu iMOPSE. Các phương kết quả áp dụng với bài toán MS- RCPSP của 2 thuật toán này cho thấy: - Với giá trị BEST, DEM tốt hơn M-PSO ở 19/30 bộ dữ liệu, DEM có giá trị bằng M-PSO ở 2 trường hợp và DEM có giá kém hơn M-PSO ở 9/30 bộ dữ liệu. Tuy nhiên, giá trị STD của DEM là 74.9, tốt hơn so với M- PSO là 85.3, điều này cho thấy DEM có độ ổn định hơn M-PSO. - Cũng qua kết quả trong bảng 2.19 cho thấy, DEM tốt hơn M-PSO trong các trường hợp dự án có cùng số tác vụ nhưng số lượng tài nguyên lớn hơn. Các kết quả của DEM có được nhờ việc ứng dụng thuật toán tiến hóa vi phân (DE) kết hợp với cải tiến quan trọng là việc áp dụng hàm Reallocate. DE có đặc tính định hướng cao dựa trên kinh nghiệm của quần thể và cá thể qua các thế hệ, hàm Reallocate sẽ giúp tính toán lại các thể tốt nhất tìm được sau mỗi thế hệ bằng việc thay thế tài nguyên thực hiện các tác vụ, việc này giúp thuật toán mở rộng được không gian tìm kiếm và nâng cao khả năng hội tụ. 2.4.5. Hình ảnh so sánh DEM với thuật toán GA-M Hình 2.12. So sánh giá trị BEST giữa DEM với GA-M Hình 2.13. So sánh giá trị STD giữa DEM với GA-M28. return {Pbest, makespan}
Một số phương pháp gần đúng giải bài toán lập lịch với tài nguyên giới hạn - 8
Đánh Giá Chất Lượng Lời Giải Của Thuật Toán
Phương Pháp Tái Thiết Lập Tài Nguyên Thực Hiện
Xếp Loại Bài Toán Real-Rcpsp Thông Qua Phân Loại Graham
Một số phương pháp gần đúng giải bài toán lập lịch với tài nguyên giới hạn - 13
Ý Tưởng Của Phương Pháp Thích Nghi
