Một giải thuật di truyền giải bài toán cắt vật tư một chiều với nhiều kích cỡ vật liệu thô

BỘ GIÁO DỤC & ĐÀO TẠO VIỆN KH & CN VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN PHAN THỊ HOÀI PHƯƠNG MỘT GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN CẮT VẬT TƯ MỘT CHIỀU VỚI NHIỀU KÍCH CỠ VẬT LIỆU THÔ LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2011 BỘ GIÁO DỤC & ĐÀO TẠO VIỆN KH & CN VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN PHAN THỊ HOÀI PHƯƠNG MỘT GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN CẮT VẬT TƯ MỘT CHIỀU VỚI NHIỀU KÍCH CỠ VẬT LIỆU THÔ Chuyên ngành: Đảm bảo toán học cho máy tính và hệ thống tính toán Mã số: 62 46 35 01 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC : 1. PGS.TS. LƯƠNG CHI MAI 2. TS. NGUYỄN VĂN HÙNG Hà Nội – 2011 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các tác giả khác đã được sự nhất trí của đồng tác giả khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào. Tác giả Phan Thị Hoài Phương LỜI CẢM ƠN Luận án được thực hiện và hoàn thành dưới sự hướng dẫn của PGS.TS Lương Chi Mai và TS. Nguyễn Văn Hùng. Trước hết, tôi xin bày tỏ lòng biết ơn sâu sắc đến cô Lương Chi Mai và thầy Nguyễn Văn Hùng, những ng ười thầy đã tận tình hướng dẫn, chỉ bảo, giúp đỡ tôi học tập và nghiên cứu. Xin trân trọng cảm ơn Ban lãnh đạo Viện Công nghệ thông tin và bộ phận quản lý nghiên cứu sinh đã nhiệt tình giúp đỡ và tạo điều kiện thuận lợi để tôi hoàn thành luận án này. Tôi xin trân trọng cảm ơn Ban lãnh đạo Học Viện Công nghệ Bưu chính viễn th ông đã tạo điều kiện cho tôi học tập, nghiên cứu và thực hiện luận án. Tôi cũng xin cảm ơn Bộ phận kỹ thuật Nhà máy ống thép Việt -Đức đã cho phép tôi thu thập số liệu và triển khai mô hình thử nghiệm ứng dụng giải bài toán cắt vật tư. Cuối cùng tôi xin dành tặng luận án này cho những người thân yêu: bố mẹ, chồng, con gái và con trai của tôi như muốn nói một lời cảm ơn chân thành nhất vì sự giúp đỡ, sự động viên không giới hạn đối với tôi. Họ chính là nơi khơi nguồn và cũng là đích hướng tới trong học tập và nghiên cứu của tôi. iMỤC LỤC MỞ ĐẦU ........................................................................................................................1 Chương 1. CÁC KIẾN THỨC CƠ SỞ LIÊN QUAN ...............................................9 1.1. Bài toán cắt vật tư một chiều với một loại vật liệu thô và thuật giải ..............9 1.1.1. Mô hình Gilmore-Gomory.....................................................................10 1.1.2. Mô hình Arc-flow của Valerio de Carvalho ..........................................13 1.2. Giải thuật di truyền........................................................................................19 1.3. Kết luận .........................................................................................................25 Chương 2. 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Ô: MÔ HÌNH VÀ GIẢI PHÁP ...........................................................26 2.1. Phát biểu 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ô theo Gilmore và Gomory..................................................................................................26 2.2. Phát biểu mới của bài toán OneDCSP_M .....................................................28 2.3. Giải thuật di truyền lai ghép giải bài toán OneDCSP_M ..............................32 2.4. Kết quả tính toán ...........................................................................................40 2.5. Kết luận .........................................................................................................50 Chương 3. HỆ THỐNG ĐA TÁC TỬ GMAS-OneDCSP_M GIẢI BÀI TOÁN OneDCSP_M . .........................................................................................................52 3.1. Yêu cầu của hệ thống GMAS-OneDCSP_M ................................................54 3.2. Thiết kế hệ thống GMAS-OneDCSP_M .......................................................55 3.2.1. Kiến trúc hệ thống GMAS-OneDCSP_M .............................................55 3.2.2. Thiết kế chi tiết hệ thống GMAS-OneDCSP_M ...................................58 3.3. Đánh giá tính hiệu quả của hệ thống GMAS-OneDCSP_M .........................65 3.4. Kết luận .........................................................................................................67 KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU TIẾP THEO ............................................68 DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ...................................................70 TÀI LIỆU THAM KHẢO............................................................................................71 PHỤ LỤC .....................................................................................................................78 ii DANH MỤC THUẬT NGỮ Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh Bài toán chủ Master Problem – MP Bài toán chủ giới hạn Restricted Master Problem – RMP Bài toán con định giá Subproblem – pricing problem Điểm cực Extreme point Giải thuật di truyền Genetic Algorithm – GA Giá suy giảm Reduced cost Lập trình tiến hóa Evolutionary Programming-EP Nới lỏng tuyến tính liên tục Linear continuous relaxation Nới lỏng tuyến tính liên tục mạnh Strong linear continuous relaxation Nới lỏng tuyến tính liên tục yếu Weak linear continuous relaxation Phương pháp nhánh cận Branch and Bound – B&B Phương pháp phân nhánh và định giá Branch and Price – B&P Phương pháp phân nhánh, định giá và cắt Branch and Price and Cut Phương pháp tạo sinh cột Column Generation Tia cực Extreme ray Tính chất làm tròn nguyên Integer Round-Up Property – IRUP Tính chất làm tròn nguyên cải biên Modified Integer Round-Up Property – MIRUP Tính toán tiến hóa Evolutionary Computation Thuật toán tiến hóa Evolutionary Algorithm- EA iii DANH MỤC CÁC KÝ HIỆU, CỤM TỪ VIẾT TẮT Ký hiệu Thuật ngữ AF Thuật toán dựa trên mô hình luồng cung (Arc-Flow model) của Carvalho giải bài toán OneDCSP_S A-Team Asynchronous Team- Kiến trúc không đồng bộ sử dụng trong hệ đa tác tử C&P Cutting and Packing – Cắt vật tư và đóng hàng CSP Cutting Stock Problem -Bài toán cắt vật tư FIPA Foundation for Intelligent Physical Agents GA-AF Genetic Algorithm- Arc-Flow Model – Thuật toán lai ghép giải thuật di truyền và thuật toán AF GMAS- OneDCSP_M Genetic Multi Agent System- Hệ thống gen đa tác tử giải bài toán OneDCSP_M JADE Java Agent DEvelopment Framework LP Linear Programming – Quy hoạch tuyến tính OneDCSP One Dimension Cutting Stock Problem-Bài toán cắt vật tư một chiều OneDCSP_M One Dimensional Cutting Stock Problem with Multiple Stock Sizes -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ô OneDCSP_M- Solver Tác tử giải bài toán OneDCSP_M OneDCSP_S One Dimensional Cutting Stock Problem with Single Stock Sizes -Bài toán cắt vật tư một chiều với một loại kích thước vật liệu thô OneDCSP_SLP Nới lỏng tuyến tính của bài toán OneDCSP_S OneDCSP_S- Solver Tác tử giải bài toán OneDCSP_S iv DANH MỤC CÁC BẢNG BIỂU Bảng 2.1 Tổng kết chất lượng nghiệm so với kết quả của Belov -Scheithauer ............ 44 Bảng 2.2 Kết quả tính toán của Silvio A. Araujo và đồng sự ...................................... 45 Bảng 2.3 Phân bố độ chênh lệch nghiệm so với kết quả của Belov -Scheithauer ........ 46 Bảng 2.4 Thống kê thời gian tính toán ......................................................................... 48 Bảng 2.5 Thống kê phân bố thời gian tính toán ........................................................... 49 vDANH MỤC CÁC HÌNH VẼ Hình 0.1 Sơ đồ các cách tiếp cận giải bài toán cắt vật tư một chiều…………………. 6 Hình 1-1 Các phương án cắt trong bài toán OneDCSP_S ........................................... 10 Hình 1-2 Ví dụ về mạng lưới và phương án cắt với L=9 và các li {4,3,2} ............... 13 Hình 1-3 Một thế hệ mới được hình thành qua pha chọn lọc và pha tái tổ hợp. ......... 22 Hình 2-1 Các phương án cắt trong bài toán OneDCSP_M .......................................... 27 Hình 2-2 Biểu đồ thống kê độ chênh lệch so với kết quả của Belov -Scheithauer....... 47 Hình 2-3 Biểu đồ thống kê phân bổ thời gian tính toán ............................................... 50 Hình 3-1 Kiến trúc của A-Team................................................................................... 53 Hình 3-2 Biểu đồ tương tác giữa người dùng và hệ thống GMAS -OneDCSP_M....... 55 Hình 3-3 Kiến trúc hệ thống GMAS-OneDCSP_M..................................................... 56 Hình 3-4 Cấu trúc bộ nhớ chung tương ứng với mỗi bài toán OneDCSP_M .............. 59 Hình 3-5 Biểu đồ Use Case của hệ thống GMAS-OneDCSP_M ................................ 63 1MỞ ĐẦU Dân số thế giới tăng nhanh và đời sống vật chất của con người không ngừng nâng cao. Điều đó dẫn tới nhu cầu về tài nguyên thiên nhiên ngày càng lớn. Chúng ta đã và đang chứng kiến sự cạn kiệt của tài nguyên thiên nhiên, nhất là những nguồn tài nguyên không tái tạo được như khoáng sản. Để phát triển bền vững, việc sử dụng tài nguyên một cách hiệu quả luôn là vấn đề thời sự của toàn nhân loại. Trong các ngành kinh tế như chế tạo máy, xây dựng, dệt may… việc sử dụng hiệu quả tài nguyên thể hiện bởi việc sử dụng hiệu quả các loại vật liệu thô phục vụ cho mục đích kinh tế. Lĩnh vực cắt vật tư và đóng hàng (Cutting & Packing-C&P) bao gồm nhiều bài toán tổ hợp, hình học, các mô hình và thuật toán lý thuyết cũng như thực tiễn liên kết với nhau. Mục tiêu chính của lĩnh vực này là sắp xếp một cách hiệu quả các đối tượng được mô tả bằng ngôn ngữ hình học trong một miền lớn hơn. Các bài toán sau đây là các bài toán điển hình cho chủ đề này: Cắt vật tư và bài toán phế thải, xếp thùng (bin packing), bài toán sắp ba lô (knapsack), cân bằng luồng (line balancing), bài toán phân phối bộ nhớ và lập lịch cho bộ đa xử lý (memory allocation and multiprocessor scheduling problem)… Các bài toán cắt vật tư và đóng hàng được phát biểu và xử lý trong nhiều ngành khoa học khác nhau như khoa học quản lý, khoa học kỹ thuật, khoa học máy tính và công nghệ thông tin, toán học và vận trù học. Chúng là các bài toán thực tế đặt ra cho các ngành công nghiệp như công nghiệp kính, thép, giấy, da, may mặc, vận tải và hậu cần. Từ giữa thế kỷ trước đã có nhiều cá ch tiếp cận giải các bài toán cắt vật tư và đóng hàng được đề xuất. Công trình khởi nguồn cho chủ đề này do L.V.Kantorovich đưa ra năm 1939 khi ông đề xuất áp dụng các mô hình toán học để 2tổ chức và lập kế hoạch sản xuất. Các mô hình này được phát biểu dướ i dạng các bài toán Quy hoạch nguyên và được chỉ ra thuộc lớp các bài toán NP-hard. Mô hình có một số nhược điểm như có nới lỏng liên tục yếu và tính đối xứng nên việc áp dụng nó trong các bài toán thực tiễn tỏ ra không hiệu quả. Để khắc phục nhược điểm củ a mô hình trên, một mô hình khác cùng với kỹ thuật giải hiệu quả bài toán cắt vật tư một chiều được Gilmore và Gomory đề xuất vào những năm 60 thế k ỷ trước. Trong kỹ thuật này, các tác giả sử dụng công cụ quy hoạch tuyến tính để giải bài toán nới lỏng liên tục dẫn xuất từ bài toán quy hoạch nguyên. Nghiệm của bài toán quy hoạch nguyên ban đầu sẽ nhận được bằng các kỹ thuật làm tròn nghiệm của bài toán nới lỏng liên tục khi bài toán đảm bảo tính chất làm tròn nguyên (Integer Round-Up Property-IRUP). Đề xuất của Gilmore và Gomory đặc biệt hiệu quả khi giải các bài toán cắt vật tư nhờ kỹ thuật tạo sinh cột với việc giải Bài toán xếp ba lô như một bài toán con. Sau này kỹ thuật tạo sinh cột trở thành kỹ thuật được ưa chuộng nhất khi người ta đề cập tới việc giải các bài toán quy hoạch cỡ lớn. Do tính khoa học cũng như thực tiễn cao của chủ đề c ắt vật tư và đóng hàng nên vào năm 1988 H. Dyckhoff và G. Waescher đã thành lập Special Interest Group on Cutting and Packing (SICUP), bước quan trọng để hỗ trợ nghiên cứu quốc tế về chủ đề này. Một trong những đóng góp nổi bật của H.Dyckhoff vào năm 1990 cho việc phát triển các nghiên cứu lý thuyết cũng như ứng dụng trong lĩnh vực này là việc đưa ra phân loại (Typology) các bài toán cắt vật tư và đóng hàng dựa trên điều t ra các đặc tính của cấu trúc hình học, cấu trúc logic và ngữ cảnh xuất hiện của chúng trong thực tế. Sự phân loại này được G. Waescher và các đồng nghiệp tiếp tục hoàn thiện vào năm 2007. Việc phân loại được thực hiện dựa trên bốn tiêu chí: 31. Số chiều của bài toán: có thể là 1, 2, 3 hoặc lớn hơn 2. Kiểu gán (Kind of assignment): Có hai kiểu gán là cực đại hóa đầu ra (Output Maximization) hoặc cực tiểu hóa đầu vào (Input Minimization) 3. Phân loại các đối tượng nhỏ (Assortment of small items): đồng nhất, tương đối không thuần nhất (weakly heterogeneous assortment), hoàn toàn không thuần nhất (Strongly heterogeneous assortment) 4. Phân loại các đối tượng lớn (Assortment of large objects): - Một đối tượng lớn (có thể được xem xét chi tiết hơn phụ thuộc vào các chiều của đối tượng được cố định hay có thể biến đổi ) - Một số đối tượng lớn với các chiều cố định. Trường hợp này có thể được chia thành các bài toán với các đối tượng lớn đồng nhất , tương đối đồng nhất và hoàn toàn không đồng nhất. Trong các kiểu bài toán cắt vật tư thì Bài toán cắt vật tư một chiều (One Dimensional Cutting Stock Problem – OneDCSP) giữ một vị trí quan trọng và chiếm gần một nửa tổng số công trình đã được công bố về chủ đề này. Có nhiều lý do giải thích về mối quan tâm của cộng đồng nghiên cứu dành cho bài toán này trong đó có thể dẫn ra nhận xét của Gilmore và Gomory khi nói rằng, nhiều bài toán cắt vật tư nhiều chiều có thể được xử lý bằng một quy trình nhiều công đoạn dựa trên nền tảng bài toán cắt vật tư một chiều. Từ công trình khởi đầu của Gilmor e và Gomory, hàng loạt các biến thể khác nhau của bài toán OneDCSP đã được phát biểu và giải quyết bằng các cách tiếp cận khác nhau. 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 Stock Problem with Multiple Stock sizes – OneDCSP_M) là mở rộng tự nhiên của bài toán cắt vật tư một chiều với một loại vật tư OneDCSP. Cho đến nay có rất ít công trình nghiên cứu về bài toán này được công bố. Theo phân loại của Waescher, bài toán OneDCSP_M được chia thành hai lớp con: lớp không ràng buộc số lượng của từng loại vật tư đầu vào và lớp có ràng buộc này. 4Có thể thấy hầu hết các công trình liên quan đến bài toán OneDCSP_M đều hướng tới giải các bài toán thuộc lớp thứ hai . Chúng ta có thể khái quát các cách tiếp cận được đề xuấ t để giải bài toán này như sau. Bài toán cắt vật tư OneDCSP_M là bài toán quy hoạch nguyên và thuộc lớp NP- khó vì vậy không tồn tại thuật toán bảo đảm cho nghiệm tối ưu trong thời gian đa thức. Cho đến nay các phương pháp giải chính xác bài toán quy hoạch nguyên này và các biến thể của nó đều được xây dựng theo lược đồ phân nhánh và định giá (Branch and Price – B&P) dựa trên nới lỏng tuyến tính liên tục của mô hình do Gilmore-Gomory đề xuất vào năm 1963 [26,27] và sau này là mô hình arc-flow của Valerio de Carvalho [55]. Gần đây, Belov [11], Carvalho và đồng nghiệp [56] đã đưa vào sử dụng các lát cắt trong lược đồ trên để tạo nên lược đồ phân nhánh định giá và cắt nhằm cải thiện tốc độ tính toán khi giải bài toán. Việc cải biên các lược đồ trên áp dụng giải các biến thể khác nhau của bài toán cũng đã được đề xuất [12,13,14,30,44,58]. Do các phương pháp chính xác giải bài toán cắt vật tư đòi hỏi chi phí thời gian khá tốn kém đối với các bài toán có kích thước trung bình hoặc lớn nên nhiều tác giả đã đề xuất các giải thuật heuristic khác nhau nhằm tìm kiếm nghiệm có chất lượng tốt trong khoảng thời gian chấp nhận được. Các giải thuật heuristic không sử dụng nới lỏng tuyến tính liên tục của bài toán mà dựa vào cấu trúc của bài toán để điều khiển quá trình tìm kiếm. Các giải thuật heuristic đầu tiên được đề xuất để giải các bài toán cắt vật tư thường dựa trên các phương pháp tìm kiếm cục bộ như First -Fit, Next-Fit, Best-Fit và Worst-Fit Decreasing để xây dựng các phương án cắt [52]. Ý tưởng chính của những phương pháp này là sau khi sắp xếp danh sách các thành phẩm theo thứ tự kích thước giảm dần, các phương án cắt được xây dựng theo các chiến lược khác nhau. Phương pháp First-Fit Decreasing tìm thành phẩm phù hợp để xếp vào phương án cắt, còn phương pháp Next-Fit tìm chỗ trống trên các phương án cắt để đặt thành phẩm. Phương pháp Best-Fit hạn chế phần dư thừa của mỗi phương án cắt 5bằng cách tìm không gian nhỏ nhất có thể để đặt các thành phẩm, trong khi phương pháp Worst-Fit thì lại đặt thành phẩm vào không g ian lớn nhất tìm được nhằm để lại nguyên liệu nhiều nhất cho các bước lặp tiếp theo. Một vấn đề nảy sinh là các phương pháp dựa trên tìm kiếm cục bộ như vậy thường rất nhanh chóng rơi vào các cực trị địa phương. Để hạn chế khả năng không mong muốn này, một số tác giả đề xuất áp dụng các Metaheuristic vào việc giải bài toán. Yang dùng giải thuật tham lam trong đó sử dụng một hàm mục tiêu phụ thuộc vào một số lượng nhỏ các điều kiện cắt để hỗ tr ợ phát hiện nghiệm tốt nhất trong quá trình tìm kiếm cục bộ tại từng bước của quá trình giải bài toán [60]. Trong [20], Eshghi và cộng sự sử dụng giải thuật đàn kiến với các quy tắc xác suất định nghĩa trước dựa trên đó đàn kiến có thể lựa chọn các phương án cắt để tìm ra phương án cắt tốt nhất. Giải thuật tôi luyện mô phỏng được sử dụng trong các công trình [33,32]. Một lớp đặc biệt các giải thuật metaheuristic giải bài toán cắt vật tư là lớp các giải thuật di truyền (Genetic Algorithm-GA). Các giải thuật này được xây dựng theo hai cách tiếp cận: cách tiếp cận đơn hàng và cách tiếp cận dựa trên nhóm. Trong cách tiếp cận đơn hàng, các thành phẩm được sử dụng một cách độc lập khi tạo ra các phương án cắt. Cách tiếp cận này khá gần gũi với định nghĩa của bài toán nhưng ít được áp dụng trong thực tiễn vì các gen mã hóa nghiệm của bài toán thường bị phá vỡ dưới tác động của các toán tử lai ghép. Toyoda và đồng nghiệp [51,53] đề xuất các toán tử lai ghép khác nhau trong giải thuật di truyền của mình để giải bài toán cắt vật tư. Falkenauer đã đề xuất mô hình dựa trên nhóm [21], trong đó các phương án cắt được xây dựng dựa trên các nhóm thành phẩm đã được phân chia nhằm khắc phục sự ảnh hưởng của các toán tử di truyền đến cấu trúc nghiệm. Yakawa và đồng nghiệp cũng đưa ra toán tử lai ghép đặc biệt gắn vào mô hình giải thuật di truyền dựa trên nhóm do Falkenauer đề xuất [ 59]. Một đề xuất sử dụng ý tưởng lập trình tiến hóa (Evolutionary Programming-EP) giải bài toán cắt vật tư cũng được đề xuất [39]. Trong lập trình tiến hóa, phép tìm kiếm được thực hiện nhờ các toán tử đột biến mà không sử dụng toán tử lai ghép. 6Liang đã đưa ra hai toán tử đột biến mới và chỉ ra tính ưu việt của các toán tử này. Khác với lập trình tiến hóa, giải thuật di truyền sử dụng cả toán tử lai ghép trong quá trình tìm kiếm. Raymond Chiong và đồng nghiệp [43] đã tiến hành so sánh hai cách tiếp cận EP và GA và kết hợp tính ưu việt của cả hai cách tiếp cận để xây dựng một giải thuật di truyền cho bài toán cắt vật tư. Trong [48], Araujo và đồng nghiệp sử dụng giải thuật heuistic First-Fit decreasing để xây dựng các phương án cắt tạo ra các cá thể (nghiệm chấp nhận được) ở mức thấp. Ở mức cao, các tác giả đề xuất thuật toán tiến hóa (Evolutionary Algorithm-EA) với toán tử lựa chọn tham lam ngẫu nhiên. Việc tạo ra các cá thể mới được thực hiện nhờ quá trình trao đổi các phương án cắt giữa các cá thể trong một pha được đặt tên là co -operation. Mới đây, việc lai ghép giải thuật di truyền với các phương pháp sử dụng nới lỏng tuyến tính liên tục cũng được tác giả luận án đề xuất trong [1,2]. Các cách tiếp cận giải bài toán cắt vật tư có thể mô tả theo sơ đồ sau. Hình 0.1 Sơ đồ các cách tiếp cận giải bài toán cắt vật tư một chiều Các cách tiếp cận giải bài toán OneDCSP Cách tiếp cận chính xác Dựa trên mô hình nới lỏng liên tục Kỹ thuật B&P Cách tiếp cận heuristic Cách tiếp cận lai ghépDựa trên Metaheuristic và tiếp cận chính xác Pure-heuristic Dựa trên tìm kiếm cục bộ Metaheuristic Sử dụng