Đánh Giá Chất Lượng Lời Giải Của Thuật Toán 26900

7. Pnew Tạo cá thể mới bằng Lévy Flight (GS)

8. Pi Lấy ngẫu nhiên một cá thể từ Pall

9. 𝑃𝑖

= { 𝑃𝑛𝑒𝑤 𝑖𝑓 𝑓(𝑃𝑛𝑒𝑤) < 𝑓(𝑃𝑖)

𝑃𝑖 𝑖𝑓 𝑓(𝑃𝑛𝑒𝑤) ≥ 𝑓(𝑃𝑖 )

10. Ppa pa% tổ kém nhất từ Pall

11. For j = 1 to size(Ppa)

12. Pnew Tạo cá thể mới bằng Lévy Flight (LS)

𝑃𝑛𝑒𝑤 𝑖𝑓 𝑓(𝑃𝑛𝑒𝑤) < 𝑓(𝑃𝑝𝑎)

13. 𝑃𝑝𝑎 = { 𝑗

𝑗 𝑃𝑝𝑎 𝑖𝑓 𝑓(𝑃𝑛𝑒𝑤) ≥ 𝑓(𝑃𝑝𝑎)

𝑗 𝑗

14. End For

15. Pall Thay thế Ppa vào Pall

16. f Calculate the fitness, makespan, bestnest

17. bestnest = Reallocate(bestnest)

18. bestnest = Rotate(bestnest)

19. makespan = f(bestnest)

20. t = t+1

21. End while

22. return {bestnest, makespan}

23. End

Có thể bạn quan tâm!

• Ý Tưởng Của Phương Pháp Thích Nghi
• Đánh Giá Chất Lượng Lời Giải Của Thuật Toán
• Đánh Giá Chất Lượng Lời Giải Của Thuật Toán
• 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 - 18
• 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 - 19

Xem toàn bộ 156 trang tài liệu này.

Các dòng 18 là các lời gọi đến hàm hàm Rotate để cải tiến kết quả của cá thể tốt nhất bestnest, sau đó sẽ tính toán lại makespan của cả quần thể bằng lời gọi ở dòng 19.

4.4.3. Kết quả thực nghiệm

Để kiểm chứng thuật toán RR-CSM, luận án tiến hành thực nghiệm trên 02 bộ dữ liệu: iMOPSE hiệu chỉnh và bộ dữ liệu của TNG[54]. Các thông số cấu hình thực nghiệm tương tự như trong mục 2.4.3.2. Kết quả thực nghiệm được trình bày trong bảng 4.12 và bảng 4.13 dưới đây.

Bảng 4.12: Kết quả thực nghiệm RR-CSM với bộ dữ liệu iMOPSE

Dataset

Dataset

Bảng 4.13: Kết quả thực nghiệm RR-CSM với bộ dữ liệu TNG

Dataset

4.4.4. Đánh giá chất lượng lời giải của thuật toán

Các thực nghiệm được triển khai trên RR-CSM sử dụng bộ dữ liệu iMOPSE và bộ dữ liệu TNG. Kết quả thực nghiệm được trình bày trong bảng 4.12 và bảng 4.13 chỉ ra thuật toán RR-CSM có chất lượng lời giải luôn tốt hơn thuật toán GA-M.

Với bộ dữ liệu iMOPSE, giá trị tốt nhất của RR-CSM tốt hơn R-CSM từ 0.2% đến 4,67 %, so sánh chi tiết được thể hiện trong hình 4.16. Tổng độ lệch chuẩn của R-CSM là 122,1, của RR-CSM là 82,3, điều này cho thấy độ ổn định của thuật toán RR-CSM tốt hơn, hình 4.17 cho so sánh độ lệch chuẩn giữa RR- CSM, R-CSM và GA-M.

Với bộ dữ liệu TNG, giá trị tốt nhất của RR-CSM tốt hơn R-CSM từ 0,75% đến 3,12%, so sánh chi tiết được thể hiện trong hình 4.18. Tổng độ lệch chuẩn của R-CSM là 40,8, của RR-CSM là 32,2, điều này cho thấy độ ổn định của thuật toán RR-CSM tốt hơn, hình 4.19 cho so sánh độ lệch chuẩn giữa RR- CSM và R-CSM.

122

4.4.5. Hình ảnh so sánh RR-CSM với thuật toán GA-M

Hình 4.16. So sánh giá trị BEST giữa R-CSM, RR-CSM, GA-M

Hình 4.17. So sánh giá trị STD giữa R-CSM, RR-CSM, GA-M trên iMOPSE

Hình 4.18. So sánh giá trị BEST giữa R-CSM, RR-CSM và TNG

Hình 4.19. So sánh giá trị STD giữa RR-CSM với R-CSM

Kết luận chương 4

Trong chương này, luận án đã trình bày về cách mã hóa cá thể của bài toán Real-RCPSP. Để phục vụ cho việc thực nghiệm theo mô hình sản xuất thực tế, luận án sử dụng bộ dữ liệu thực tế của công ty may TNG sau khi số hóa. Để giải bài toán Real-RCPSP, 03 giải thuật metaheuristic đã được đề xuất.

Thuật toán 1: A-DEM, là thuật toán được phát triển từ thuật toán DE. Cải tiến mới, quan trọng của A-DEM là việc thay thế giá trị lai ghép thích nghi theo từng thế hệ. Giá trị này được tính toán dựa trên các cá thể lân cận, số cá thể lân cận cũng thay đổi theo quá trình tính toán dựa trên các cá thể tiến hóa thành công.

Thuật toán 2: R-CSM, là thuật toán được phát triển từ thuật toán Cuckoo Search. R-CSM áp dụng bổ sung thêm hai phương pháp nhằm nâng cao chất lượng lời giải: phương pháp tái thiết lập (Reallocate). Thuật toán này đã được công bố trong công trình [CT9].

Thuật toán 3: RR-CSM, là thuật toán được phát triển từ thuật toán R-CSM bằng cách áp dụng bổ sung thêm hai phương pháp Rotate, kết quả cho thấy RR- CSM hiệu quả tốt hơn so với R-CSM trước đó.

Để kiểm chứng tính hiệu quả của R-CSM, RR-CSM và A-DEM, luận án đã triển khai thực nghiệm với bộ dữ liệu iMOPSE và TNG, có đánh giá so sánh cụ thể sau mỗi phần thực nghiệm.

Kết quả nghiên cứu của chương này được công bố tại:

- Hội thảo quốc tế ICCC lần thứ 2 Nagoya, Japan, 2020. DOI: 10.1109/ICCCI49374.2020.9145982 [CT7]

- Tạp chí Thông tin và Truyền thông, tập 2, pp. 93-101, 12-2019, DOI: 10.32913/mic-ict-research-vn.v2019.n2.865 [CT6];

- Tạp chí Journal of Advanced Transportation (IF: 1.67, Q2), Volume 2020, Article ID 8897710, 11 pages, 2020 [CT9].

KẾT LUẬN

Bài toán lập lịch với tài nguyên giới hạn và đa kỹ năng MS-RCPSP có nhiều ứng dụng trong thực tế. Luận án đã phát biểu tường minh bài toán MS-RCPSP (mục 1.1.1), chỉ ra các ứng dụng của bài toán này (mục 1.1.2) và các phương pháp giải (mục 1.2). Để xác định nội dung nghiên cứu, các công trình nghiên cứu liên quan đến bài toán đã được tổng hợp, phân tích, từ đó chỉ ra các hướng mở sẽ làm trong luận án (mục 1.1.3).

Trong chương 2 của luận án đề đề xuất 2 thuật toán mới để giải bài toán MS-RCPSP phát triển từ các thuật toán mới, hiệu quả hơn. Các thuật toán gồm: M-PSO dựa trên cơ sở là thuật toán PSO và DEM phát triển từ thuật toán DE.

Chương 3 luận án phát biểu tường minh bài toán mới Real-RCPSP (mục 3.1.1.) và xếp loại bằng ký pháp Graham (3.1.3). Đây là bài toán mở rộng từ bài toán MS-RCPSP và có khả năng ứng dụng cao trong thực tế sản xuất. Đề giải bài toán này, luận án đề xuất 3 thuật toán mới là A-DEM mở rộng từ DE, R-CSM cải tiến từ thuật toán CS và RR-CSM cải tiến thêm từ thuật toán R- CSM. Các thực nghiệm được chạy trên bộ dữ liệu iMOPSE và bộ dữ liệu thực tế TNG.

Các kết quả nghiên cứu của luận án được công bố trong 9 công trình, trong đó 06 bài báo trên tạp chí, trong đó có 02 bài báo SCIE, 01 bài scopus, 03 bài tạp chí trong nước; 02 hội thảo kỷ yếu hội thảo quốc tế, kỷ yếu được đăng trên IEEE và 01 hội thảo quốc gia.

Đóng góp mới của luận án bao gồm:

- Đề xuất 02 thuật toán mới để giải bài toán MS-RCPSP là: M-PSO và DEM [CT7], [CT8].

- Đề xuất 03 thuật toán để giải bài toán Real-RCPSP là: A-DEM, R-CSM [CT9] và RR-CSM.