Gmas - 1dmcsp: Hệ thống đa tác tử gen giải bài toán cắt vật tư một chiều với nhiều kích thước vật liệu thô

Bài báo này đề xuất xây dựng một hệ thống đa tác tử để nâng cao hiệu quả giải bài toán cắt vật tư với nhiều kích thước vật liệu thô trên cơ sở thuật toán GA-CG được công bố trong [1]. Với hệ thống này, một mặt các công việc tính toán của thuật toán GA-CG được song song hóa và phân chia cho các tác tử khác nhau đảm nhiệm.
Nội dung trích xuất từ tài liệu:
Gmas - 1dmcsp: Hệ thống đa tác tử gen giải bài toán cắt vật tư một chiều với nhiều kích thước vật liệu thôTẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆTập 48, số 6, 2010Tr.GMAS-1DMCSP: HỆ THỐNG ĐA TÁC TỬ GEN GIẢI BÀI TOÁNCẮT VẬT TƯ MỘT CHIỀU VỚI NHIỀU KÍCH THƯỚCVẬT LIỆU THÔPHAN THỊ HOÀI PHƯƠNG, LƯƠNG CHI MAI1. GIỚI THIỆUBài toán cắt vật tư một chiều với nhiều kích thước vật liệu thô (One-Dimensional CuttingStock Problem with Multiple Stock Sizes) là bài toán tối ưu thuộc lớp bài toán NP-Hard. Trongthời gian gần đây đã có nhiều công trình đề cập tới các giải pháp cho bài toán này, trong đó có[1, 10, 11, 12, 13, 16, 18]. Do bài toán có độ phức tạp tính toán lớn nên việc tăng tốc độ tínhtoán cho các giải pháp mang một ý nghĩa quan trọng khi áp dụng vào thực tế.Bài báo này đề xuất xây dựng một hệ thống đa tác tử để nâng cao hiệu quả giải bài toán cắtvật tư với nhiều kích thước vật liệu thô trên cơ sở thuật toán GA-CG được công bố trong [1].Với hệ thống này, một mặt các công việc tính toán của thuật toán GA-CG được song song hóavà phân chia cho các tác tử khác nhau đảm nhiệm. Điều đó cho phép giảm thiểu một cách đángkể thời gian thực hiện thuật toán; Mặt khác các tác tử được phân bổ trên toàn bộ các tài nguyêntính toán có thể có của mạng cục bộ nên tận dụng được sức mạnh tính toán của tài nguyên và vìvậy thích hợp cho việc giải các bài toán thực tế có kích thước rất lớn.Hệ thống này được thiết kế theo kiến trúc A-Team trên nền tảng JADE (Java AgentDEvelopment Framework) – một phần mềm trung gian (middle-ware) nguồn mở hỗ trợ cho việcphát triển các hệ thống đa tác tử được cài đặt hoàn toàn bằng Java và tuân thủ chặt chẽ các đặctả của FIPA (The Foundation of Intelligent Physical Agents). Phần còn lại của bài được cấu trúcnhư sau. Mục 2 dành cho việc phát biểu bài toán cắt vật tư một chiều mở rộng (nhiều loại vậtliệu thô) và trình bầy tóm tắt các kết quả lí thuyết về mối liên quan ngữ nghĩa của bài toán mởrộng này với bài toán cắt vật tư một chiều kinh điển (một loại vật tư) làm cơ sở đề xuất thuậttoán phân tán giải bài toán cắt vật tư mở rộng. Thiết kế và cài đặt của hệ thống đa tác tử giải bàitoán cắt vật tư mở rộng trên nền tảng JADE dựa trên thuật toán đề xuất trong Mục 2 được trìnhbày trong Mục 3. Mục 4 đưa ra một số đánh giá hệ thống trong môi trường ứng dụng thực tế.Cuối cùng là một số kết luận của bài báo.2. BÀI TOÁN CẮT VẬT TƯ MỘT CHIỀU VỚI NHIỀU KÍCH THƯỚC VẬT TƯ VÀTHUẬT TOÁN GIẢIBài toán cắt vật tư một chiều với một loại vật liệu thô (bài toán kinh điển) được xác địnhbởi các dữ liệu sau: (m, L, l = (l1 ,..., lm ), b = (b1 ,..., bm )) , trong đó L là bề rộng của tấm vật liệu thô,m là số dạng vật liệu thành phẩm được cắt từ vật liệu thô và đối với mỗi dạng vật liệu thànhphẩm j, l j là bề rộng và b j là đơn hàng cho loại vật liệu thành phẩm đó. Bài toán đặt ra là tìmcách cắt sao cho số lượng tấm vật liệu thô sử dụng là ít nhất mà vẫn đáp ứng được đơn hàng.37Gilmore và Gomory [14, 15] lần đầu tiên đưa kĩ thuật tạo sinh cột (Column Generation) doFord và Fulkerson đề xuất và sau đó được Dantzig và Wolfe hoàn thiện vào ứng dụng trong thựctế với việc giải bài toán cắt vật tư kinh điển này. Có thể tóm tắt phương pháp giải bài toán cắt vậttư một chiều của Gilmore và Gomory như sau.Một phương án cắt được biểu diễn bới một vectơ cột a j = (a1 j ,..., amj )∈ Z +m , j = 1,…,n sẽ chobiết số lượng vật tư thành phẩm được cắt từ tấm vật liệu thô. Phương án cắt được chấp nhận nếunó thỏa mãn điểu kiện:m∑l ai ij≤ L.(1)i =1Giả sử x j , j = 1,..., n là số lần phương án cắt chấp nhận được được sử dụng trong nghiệm.Mô hình của Gilmore và Gomory trở thành:n1DCSPG (m, L, l , b) = min ∑ x j = min x(2)j =1Trên miền ràng buộc:n∑a xij≥ bji=1,…,m(3)x j ∈ Z+ ,j=1,…,n(4)jj =1Mô hình (1)-(4) là bài toán quy hoạch nguyên với số lượng biến n tăng theo hàm lũythừa của m. Mô hình này có suy yếu liên tục mạnh với tính chất làm tròn nguyên cải biên(Modified Integer Round-Up Property – MIRUP).Trên cơ sở đó, Gilmore và Gomory đề xuất cách tiếp cận giải bài toán (1)-(4) gồm 2bước: 1/ giải bài toán suy yếu liên tục của (1)-(4); 2/ Làm tròn số nghiệm tối ưu của bài toán suyyếu liên tục để nhận được nghiệm của bài toán (1)-(4).Để giải bài toán suy yếu liên tục của (1)-(4) với số lượng biến n rất lớn, Gilmore vàGomory đề xuất sử dụng kĩ thuật tạo sinh cột (Column Generation) trong đó mỗi biến chỉ đượcsinh ra khi nó thực sự cần thiết cho việc cải thiện nghiệm tìm được trước đó. Sau khi thêm vàocác biến bổ xung (slacks) ta có thể đưa bài toán (1)-(4) về dạng chuẩn:{1DCSPG (m, L, l , b) = min x : Ax = b, x ∈ Z +n}(5)Suy yếu liên tục của (5) nhận được bằng việc loại bỏ ràng buộc nguyên trên các biến vàđược gọi là bài toán chủ (Master Problem - MP) sẽ có dạng:{1DCSPGLP (m, L, l , b) = min x : Ax = b, x ∈ R+n}(6)Xuất phát, kĩ thuật tạo sinh cột sẽ làm việc với một tập con các cột của A được gọi làvariable poo ...