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Ệ<br /> <br /> Tập 48, số 6, 2010<br /> <br /> Tr.<br /> <br /> GMAS-1DMCSP: HỆ THỐNG ĐA TÁC TỬ GEN GIẢI BÀI TOÁN<br /> CẮT VẬT TƯ MỘT CHIỀU VỚI NHIỀU KÍCH THƯỚC<br /> VẬT LIỆU THÔ<br /> PHAN THỊ HOÀI PHƯƠNG, LƯƠNG CHI MAI<br /> <br /> 1. GIỚI THIỆU<br /> 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ô (One-Dimensional Cutting<br /> Stock Problem with Multiple Stock Sizes) là bài toán tối ưu thuộc lớp bài toán NP-Hard. Trong<br /> thờ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ó<br /> [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ính<br /> toá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ế.<br /> 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<br /> 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].<br /> 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<br /> và 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 đáng<br /> kể 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ên<br /> tí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ì<br /> 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.<br /> Hệ thống này được thiết kế theo kiến trúc A-Team trên nền tảng JADE (Java Agent<br /> DEvelopment Framework) – một phần mềm trung gian (middle-ware) nguồn mở hỗ trợ cho việc<br /> phá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 đặc<br /> tả của FIPA (The Foundation of Intelligent Physical Agents). Phần còn lại của bài được cấu trúc<br /> như 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ật<br /> liệ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ở<br /> 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ật<br /> toá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ài<br /> toá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ình<br /> bà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ế.<br /> Cuối cùng là một số kết luận của bài báo.<br /> 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À<br /> THUẬT TOÁN GIẢI<br /> Bà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 định<br /> bở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ô,<br /> 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ành<br /> phẩ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ìm<br /> cá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.<br /> <br /> 37<br /> <br /> Gilmore và Gomory [14, 15] lần đầu tiên đưa kĩ thuật tạo sinh cột (Column Generation) do<br /> Ford và Fulkerson đề xuất và sau đó được Dantzig và Wolfe hoàn thiện vào ứng dụng trong thực<br /> tế 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ật<br /> tư một chiều của Gilmore và Gomory như sau.<br /> 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ẽ cho<br /> biế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ếu<br /> nó thỏa mãn điểu kiện:<br /> m<br /> <br /> ∑l a<br /> <br /> i ij<br /> <br /> ≤ L.<br /> <br /> (1)<br /> <br /> i =1<br /> <br /> Giả 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.<br /> Mô hình của Gilmore và Gomory trở thành:<br /> n<br /> <br /> 1DCSPG (m, L, l , b) = min ∑ x j = min x<br /> <br /> (2)<br /> <br /> j =1<br /> <br /> Trên miền ràng buộc:<br /> n<br /> <br /> ∑a x<br /> ij<br /> <br /> ≥ bj<br /> <br /> i=1,…,m<br /> <br /> (3)<br /> <br /> x j ∈ Z+ ,<br /> <br /> j=1,…,n<br /> <br /> (4)<br /> <br /> j<br /> <br /> j =1<br /> <br /> Mô 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ũy<br /> thừ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<br /> (Modified Integer Round-Up Property – MIRUP).<br /> 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 2<br /> bướ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 suy<br /> yếu liên tục để nhận được nghiệm của bài toán (1)-(4).<br /> Để 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à<br /> Gomory đề xuất sử dụng kĩ thuật tạo sinh cột (Column Generation) trong đó mỗi biến chỉ được<br /> sinh 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ào<br /> các biến bổ xung (slacks) ta có thể đưa bài toán (1)-(4) về dạng chuẩn:<br /> <br /> {<br /> <br /> 1DCSPG (m, L, l , b) = min x : Ax = b, x ∈ Z +n<br /> <br /> }<br /> <br /> (5)<br /> <br /> 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à<br /> được gọi là bài toán chủ (Master Problem - MP) sẽ có dạng:<br /> <br /> {<br /> <br /> 1DCSPGLP (m, L, l , b) = min x : Ax = b, x ∈ R+n<br /> <br /> }<br /> <br /> (6)<br /> 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à<br /> variable pool hoặc Restricted Master Problem (RMP). RMP có thể được khởi tạo dễ dàng, ví dụ<br /> bởi cơ sở kiến thiết ban đầu của phương pháp đơn hình. Giả sử A' là các cột trong A được lựa<br /> chọn. Khi đó RMP có dạng:<br /> <br /> {<br /> <br /> }<br /> <br /> 1DCSPGLP (m, L, l , b) = min x : A' x = b, x ∈ R+n .<br /> 38<br /> <br /> (7)<br /> <br /> Nhận xét rằng giá suy giảm của một biến ứng với phương án cắt chấp nhận được a trong<br /> (7) được xác định bởi công thức 1 − ua , với u ∈ R+m là các giá trị biến đối ngẫu tối ưu của (7).<br /> Do vậy nghiệm tối ưu của bài toán xác định giá (Pricing Problem):<br /> <br /> {<br /> <br /> max ua : al ≤ L, a ∈ Z +m<br /> <br /> }<br /> <br /> (8)<br /> <br /> sẽ lần lượt được thêm vào RMP nếu nếu giá trị tối ưu của (8) lớn hơn 1. Nếu (8) không có<br /> nghiệm tối ưu như vậy thì nghiệm tối ưu của bài toán RMP (7) chính là nghiệm tối ưu của bài<br /> toán MP (6).<br /> Sau khi đã giải được bài toán 1DCSPGLP (m, L, l , b) , bước tiếp theo trong cách tiếp cận của<br /> Gilmore và Gomory là việc thực hiện thủ tục làn tròn số để nhận được nghiệm nguyên cho bài<br /> toán 1DCSPG ( m, L, l , b) . Nhiều tác giả đã đưa ra các heuristics khác nhau để giải quyết vấn đề<br /> này. Một số thủ tục có thể tra cứu trong [10, 17].<br /> Việc mở rộng bài toán cắt vật tư một chiều kinh điển trong trường hợp có nhiều kích thước<br /> vật liệu thô đã được một số tác giả đề cập đến [1, 10, 11, 12, 13, 16, 18]. Các tác giả đều thống<br /> nhất rằng việc xây dựng giải thuật heuristic cho bài toán là cần thiết vì các cách tiếp cận chính<br /> xác là không phù hợp trong trường hợp này.<br /> Sau đây chúng ta sẽ trình bày tóm tắt một đề xuất lai ghép giữa thuật toán gen với phương<br /> pháp của Gilmore và Gomory để giải lớp bài toán cắt vật tư một chiều với nhiều kích thước vật<br /> liệu thô đã được công bố trong [1].<br /> 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ô (One-Dimensional Cutting<br /> Stock Problem with Multiple Stock Sizes – 1DMCSP) là mở rộng tự nhiên của bài toán 1DCSP<br /> trong đó các tấm vật liệu thô có thể có kích thước khác nhau. Bài toán 1DMCSP có thể được đặc<br /> trưng bằng các dữ liệu sau:<br /> <br /> (m, M , l = (l1 ,..., lm ), b = (b1 ,..., bm ), L = (L1,..., LM ), c = (c1 ,..., cM ))<br /> <br /> (9)<br /> <br /> trong đó m, l và b mang ý nghĩa như trong bài toán 1DCSP; M là số các loại vật liệu thô sẽ được<br /> sử dụng và tham số L trong 1DCSP được thay thế bởi vectơ L = (L1 ,..., LM ) , với Li là bề rộng<br /> và ci là giá của vật liệu thô thứ i, i = 1,…,M. Trong bài này ta giả thiết rằng giá của vật liệu thô<br /> tỉ lệ thuận với bề rộng của vật liệu.<br /> Mô hình của bài toán trên (Machine Balance Model) được Gilmore và Gomory xây dựng<br /> trong [15]. Mô hình có thể được phát biểu như sau:<br /> Đặt m' = m + M . Một vectơ a = (a1 ,..., am ' ) ∈ Z +m ' là biểu diễn của một phương án cắt<br /> nếu<br /> m<br /> <br /> M<br /> <br /> ∑l a ≤ ∑ L a<br /> i i<br /> <br /> i =1<br /> <br /> i i+m<br /> <br /> i =1<br /> <br /> M<br /> <br /> và<br /> <br /> ∑a<br /> <br /> i+m<br /> <br /> =1<br /> <br /> (10)<br /> <br /> i =1<br /> <br /> Các thành phần ai , i=1,…,m, xác định có bao nhiêu vật tư thành phẩm loại i được cắt.<br /> Thành phần ak + m sẽ bằng 1 nếu loại vật liệu thô thứ k được sử dụng còn các thành phần ai + m<br /> với i ∈ {1,..., M } \ k bằng 0.<br /> Giả sử ai , i=1,…,n,<br /> <br /> là tất cả các phương án cắt và mỗi thành phần xi của vectơ<br /> <br /> x = ( x1 ,..., xn ) là số lần sử dụng phương án cắt ai . Nhận xét rằng n có thể rất lớn. Ta xây dựng<br /> 39<br /> <br /> một vectơ n chiều c ' từ c theo cách sau. Nếu phương án cắt ai được thực hiện trên tấm thép loại<br /> k thì ci' = ck , i=1,…,n và k=1,…,M. Khi đó ta có mô hình:<br /> <br /> 1DMCSP(m, M , l , b, L, c ) = min c' x<br /> <br /> (11)<br /> <br /> Trên miền ràng buộc:<br /> n<br /> <br /> ∑a x<br /> <br /> ij i<br /> <br /> ≥ bj ,<br /> <br /> j=1,…,m<br /> <br /> (12)<br /> <br /> i =1<br /> <br /> m<br /> <br /> M<br /> <br /> j =1<br /> <br /> j =1<br /> <br /> ∑ l j aij ≤∑ L j ai ( j + m)<br /> <br /> (13)<br /> <br /> M<br /> <br /> ∑a<br /> <br /> i ( j + m)<br /> <br /> =1<br /> <br /> (14)<br /> <br /> j =1<br /> <br /> x ∈ Z +n<br /> <br /> (15)<br /> <br /> ai ∈ Z +m '<br /> <br /> i=1,…,n<br /> <br /> (16)<br /> <br /> Từ các phát biểu (1)-(4) và (11)-(16) ta có mối liên hệ giữa hai bài toán như sau:<br /> <br /> Định lí 1. [1] 1DMCSP (m, M , l , b, L, c) ≤ 1DCSPG (m, Lk , l , b) với mọi k ∈ {1,..., M } . Nói<br /> cách khác, bài toán cắt vật tư với nhiều kích thước vật liệu thô sẽ tốt hơn việc cắt chỉ trên một<br /> loại vật liệu.<br /> Định lí 1 khẳng định ý nghĩa của việc xây dựng các giải pháp cho bài toán cắt vật tư với<br /> nhiều kích thước vật liệu thô.<br /> Giả sử x* là nghiệm tối ưu của (11)-(16). Ta ký hiệu:<br /> - Ω(k ) , k=1,…,M, là tập tất cả các phương án cắt trên vật liệu thô thứ k được sử dụng<br /> trong (11)-(16) tương ứng x* ;<br /> - x * / Ω( k ) là thu hẹp của x* trên Ω(k ) ;<br /> - b k là vectơ vật tư thành phẩm nhận được từ (11)-(16) với việc sử dụng số lần cắt theo<br /> các phương án cắt trong Ω(k ) được xác định bằng các thành phần tương ứng của x * / Ω( k ) .<br /> Định lí 2. [1] Nếu x* là nghiệm tối ưu của bài toán 1DMCSP( m, M , l , b, L, c) (11)-(16) thì<br /> <br /> x * / Ω( k ) là nghiệm tối ưu của bài toán 1DCSPG ( m, Lk , l , b k ) (1)-(4), k = 1,…,M.<br /> Trên cơ sở của Định lí 2, chúng ta có thể mô hình hóa bài toán 1DMCSP dưới dạng phát<br /> biểu mới như sau.<br /> M<br /> <br /> 1DMCSP( m, M , l , b, L, c) = min ∑1DCSPG (m, Lk , l , b k )ck .<br /> k =1<br /> <br /> 40<br /> <br /> (17)<br /> <br /> Trên miền ràng buộc:<br /> M<br /> <br /> ∑b<br /> <br /> k<br /> <br /> (18)<br /> <br /> ≥b<br /> <br /> k =1<br /> <br /> b k ∈ Z +m .<br /> <br /> (19)<br /> <br /> Định lí 3. [1] Nghiệm tối ưu của bài toán (17) - (19) sẽ xác định trên tập các vectơ b k thỏa<br /> M<br /> <br /> mãn<br /> <br /> ∑b<br /> <br /> k<br /> <br /> = b . Tập các vectơ b k như vậy được gọi là phân hoạch của b. Nói cách khác<br /> <br /> k =1<br /> <br /> nghiệm tối ưu của (17) - (19) được xác định trên tập các phân hoạch của vectơ b.<br /> Các định lí 2, 3 và phát biểu mới của bài toán 1DMCSP trong (17) - (19) gợi cho chúng ta ý<br /> tưởng phân rã bài toán 1DMCSP thành các bài toán cơ sở là bài toán 1DCSPG ( m, Lk , l , b k ) để<br /> có thể áp dụng được phương pháp giải sử dụng kĩ thuật tạo sinh cột của Gilmore và Gomory.<br /> Các nghiệm tối ưu của từng bài toán cơ sở sẽ được kết hợp lại để tạo nên nghiệm chấp nhận<br /> được của bài toán 1DMCSP. Việc tìm nghiệm tối ưu cho bài toán 1DMCSP sẽ do thuật toán gen<br /> đảm nhiệm với không gian tìm kiếm là tập các phân hoạch của vectơ đơn hàng.<br /> Sau đây chúng ta sẽ lần lượt hình thức hóa ý tưởng đó trên ngôn ngữ của thuật toán gen và<br /> kĩ thuật tạo sinh cột.<br /> <br /> (<br /> <br /> )<br /> <br /> Biểu diễn bài toán. Chúng ta sử dụng nhiễn sắc thể có cấu trúc b1 ,..., b M , b k ∈ Z +m để biểu<br /> diễn các cá thể (các điểm) trong không gian tìm kiếm. Mỗi quần thể là một tập bao gồm một số<br /> cố định các cá thể.<br /> <br /> (<br /> <br /> Độ đo thích nghi. Với mỗi cá thể s = b1 ,..., b M<br /> thể, f (s ) , bằng công thức sau:<br /> <br /> f ( s) =<br /> <br /> )<br /> <br /> ta xác định mức độ thích nghi của cá<br /> <br /> 1<br /> <br /> (20)<br /> <br /> M<br /> <br /> ∑1DCSP (m, L , l , b<br /> G<br /> <br /> k<br /> <br /> k<br /> <br /> ) ck<br /> <br /> k =1<br /> <br /> (<br /> <br /> )<br /> <br /> (<br /> <br /> Toán tử hôn phối. Giả sử s1 = b11 ,..., b1M và s2 = b21 ,..., b2M<br /> <br /> ) là 2 cá thể bất kì, k<br /> '<br /> 1 và<br /> <br /> được lựa chọn ngẫu nhiên, 1 < k ≤ m . Từ hai cá thể trên ta tạo ra hai hậu duệ s<br /> vectơ cột tương ứng của chúng được xác định như sau:<br /> <br /> là một số<br /> <br /> s2' với các<br /> <br /> b1' j [i ] = b1j [i ], i = 1,..., k − 1;<br /> <br /> b1' j [i ] = b2j [i ], i = k ,..., m ; j=1,…,M<br /> <br /> (21)<br /> <br /> b2' j [i ] = b2j [i ], i = 1,..., k − 1 ;<br /> <br /> b2' j [i ] = b1j [i ], i = k ,..., m;<br /> <br /> (22)<br /> <br /> j=1,…,M<br /> <br /> Toán tử đột biến. Chọn ngẫn nhiên một bộ 3 các số nguyên (p,q,r), 1 ≤ p, q ≤ M<br /> 1 ≤ r ≤ m , với xác suất:<br /> <br /> p0 = 1<br /> <br /> (<br /> <br /> mM 2<br /> <br /> )<br /> <br /> .<br /> <br /> Toán tử đột biến tác động lên cá thể s = b1 ,..., b M để tạo nên cá thể<br /> bộ (p,q,r) đã chọn như sau:<br /> <br /> và<br /> (23)<br /> <br /> (<br /> <br /> )<br /> <br /> s1 = b11 ,..., b1M với<br /> <br /> 41<br /> <br />