Luận án 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 công cụ toán học để hạn chế cực trị địa phương - Phương pháp tạo sinh cột của Gilmore&Gomory - Mô hình arc-flow của Carvalho - Các thuật toán cải biên (Belov,…) - First-Fit Decreasing - Next-Fit Decreasing - Best-Fit Decreasing - Worst-Fit Decreasing - Giải thuật di truyền - Lập trình tiến hóa - Thuật toán tiến hóa - Giải thuật đàn kiến - Mô phỏng tôi luyện - Tabu Search Thuật toán GA-AF 7Theo hiểu biết của tác giả, cho đến nay chưa có một công trình nào liên quan đến giải bài toán OneDCSP_M thuộc lớp thứ nhất (không có hạn chế về số lượng vật liệu thô) được công bố. Bài toán này cũng chính là đối tượng nghiên cứu đặt ra cho bản luận án này. Luận án này nhằm đóng góp một phương pháp hiệu quả để giải bài toán OneDCSP_M xuất phát từ mô hình của Gilmore và Gomory, với điều kiện nguồn nguyên liệu không bị giới hạn. Những đóng góp chính của tác giả trong luận án này bao gồm: - Tiến hành phân tích mối liên quan ngữ nghĩa của bài toán OneDCSP_M với bài toán cắt trên một loại vật liệu thô (One Dimensional Cutting Stock Problem with Single Stock Sizes - OneDCSP_S). Từ đó đưa ra một cách phát biểu mới của bài toán cắt vật tư với nhiều kích cỡ vật liệu thô OneDCSP_M - Trên cơ sở phát biểu mới của bài toán OneDCSP_M và những mối liên quan ngữ nghĩa với bài toán OneDCSP_S, đề xuất lai ghép giải thuật di truyền với kỹ thuật phân nhánh và định giá theo mô hình Arc-Flow tạo nên thuật toán GA-AF giải hiệu quả bài toán OneDCSP_M. Tính đúng đắn của thuật toán được chứng minh bằng lý thuyết. Tính hiệu quả được kiểm chứng trên một số lượng tương đối lớn các bài toán mẫu. - Để nâng cao hiệu quả khi giải các bài toán thực tế, thuật toán GA-AF được cài đặt dưới dạng một hệ thống đa tác tử thực hiện các tính toán song song và phân tán nhằm tận dụng tài nguyên tính toán của mạng cục bộ (LAN). Tính đúng đắn của hệ thống được chứng minh chặt chẽ. Tính hiệu quả của hệ thống được phân tích bằng toán học cũng như trong môi trường triển khai thực tiễn. Các kết quả được chính được trình bày trong 4 công trình công bố trên tạp chí chuyên ngành và hội thảo quốc tế. Cấu trúc của Luận án như sau: 8Ngoài phần Mở đầu và Kết luận chung, luận án được chia làm 3 chương. Chương 1 trình bày các công cụ toán học cơ sở nhằm giải quyết bài toán đặt ra ở chương sau. Phần thứ nhất của chương trình bày các mô hình và thuật giải chính xác cho bài toán cắt vật tư với một loại vật liệu thô. Phần thứ hai trình bày tóm tắt một số vấn đề cơ bản của giải thuật di truyền. Trong chương 2, tác giả phân tích mối liên quan ngữ nghĩa giữa bài toán OneDCSP_M và bài toán OneDCSP_S. Kết quả cho thấy việc cắt vật tư với nhiều kích thước vật liệu thô sẽ mang lại hiệu quả hơn so với trường hợp chỉ có một loại vật liệu thô và từ đó đề xuất một mô hình mới cho bài toán OneDCSP_M. Các phân tích đó cũng làm cơ sở cho việc lai ghép giải thuật di truyền (GA) với thuật toán phân nhánh và định giá theo mô hình Arc-Flow (AF) của Carvalho để tạo nên thuật toán mới GA-AF giải bài toán OneDCSP_M. Tính đúng đắn của thuật toán GA-AF được chứng minh chặt chẽ. Tính hiệu quả của thuật toán cũng được kiểm chứng trên tập các bài toán mẫu do Belov [11] đưa ra. Phát biểu mới của bài toán OneDCSP_M trong chương 2 đã phân rã bài toán thành nhiều bài toán con có thể giải quyết một cách độc lập bằng thuật toán phân nhánh và định giá theo mô hình AF. Từ đó, trong chương 3, tác giả đã cài đặt thuật toán dưới dạng một hệ thống đa tác tử GMAS-OneDCSP_M nhằm nâng cao hiệu quả trong ứng dụng thực tiễn. Tính đúng đắn của hệ thống được chứng minh ; hiệu quả của nó được phân tích chặt chẽ và được kiểm chứng bằng việc triển khai thử nghiệm trong môi trường công nghiệp. 9Chương 1. CÁC KIẾN THỨC CƠ SỞ LIÊN QUAN Chương này trình bày tóm tắt những công cụ toán học liên quan làm cơ sở cho việc xây dựng giải pháp cho bài toán OneDCSP_M được đưa ra trong các Chương tiếp theo. Phần thứ nhất giới thiệu bài toán cắt vật tư một chiều với một loại vật liệu thô OneDCSP_S với hai mô hình giải bài toán: mô hình của Gilmore-Gomory và mô hình Arc-Flow của Carvalho. Phần tiếp theo của chương đề cập những nội dung cơ bản của thuật toán di truyền. 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 Bài toán cắt vật tư một chiều kinh điển (bài toán cắt vật tư một chiều với một loại vật liệu thô – One Dimensional Cutting Stock Problem with Single Stock Length OneDCSP_S) được xác định bởi các dữ liệu sau: (m,L,l=(l1,…,lm),b=(b1,…,bm)), trong đó : - m là số dạng vật liệu thành phẩm được cắt từ vật liệu thô - L là bề rộng của tấm vật liệu thô - Đối với mỗi dạng vật liệu thành phẩm j : + lj là bề rộng + bj là đơn hàng cho loại vật liệu thành phẩm đó. Bài toán đặt ra là tìm 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 yêu cầu của đơn hàng. Ở đây, các khái niệm vật liệu thô, vật tư, nguyên liệu đầu vào của bài toán được hiểu với nghĩa tương đương. Tương tự, hai thuật ngữ thành phẩm và sản phẩm cũng mang ý nghĩa tương đương. 10 Hình 1-1 Các phương án cắt trong bài toán OneDCSP_S Bài toán OneDCSP lần đầu tiên được Kantorovich [35] phát biểu dưới dạng bài toán quy hoạch nguyên và được chứng minh thuộc lớp bài toán NP-Hard. Sau đó nhiều tác giả đã xây dựng các mô hình khác như mô hình của Gilmore -Gomory [26], mô hình Arc-flow của Valerio de Carvalho [55], mô hình Node-flow của Belov [14]…nhằm khắc phục tính nới lỏng liên tục yếu cũng như tính đối xứng của mô hình Kantorovich, đồng thời tận dụng các thông tin cấu trúc của không gian nghiệm nhằm xây dựng các thuật toán giải chính xác cho bài toán. Sau đây là hai mô hình gốc thường được sử dụng khi nghiên cứu bài toán. 1.1.1. Mô hình Gilmore-Gomory Định nghĩa 1.1 Một phương án cắt là một véc tơ cột  1 ,...,j mj mja a a   , j=1,…,n với aij là số lần thành phẩm thứ i được cắt theo phương án cắt j từ tấm vật liệu thô. Phương án cắt gọi là chấp nhận được nếu nó thỏa mãn điều kiện:    m i iji Lal 1 (1.1) Giả sử njx j ,...,1,  là số lần phương án cắt chấp nhận được thứ j được sử dụng trong nghiệm. Khi đó mô hình bài toán cắt vật tư một chiều với một loại vật liệu thô của Gilmore và Gomory được phát biểu như sau: xxblLmSOneDCSP n j j minmin),,,(_ 1    (1.2) L liPhương án cắt j aij L li ai1 . . . . . . Phương án cắt 1 11 trên miền ràng buộc: 1 n ij j i j a x b   i=1,…,m (1.3) jx  , j=1,…,n (1.4) Mô hình (1.1)-(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 mũ của m. Mô hình này khắc phục được tính đối xứng của mô hình Kantorovich và có nới lỏng liên tục mạnh với dự đoán về tính chất làm tròn nguyên cải biên (Modified Integer Round-Up Property – MIRUP) như sau: “Sự sai khác giữa giá trị tối ưu của bài toán ),,,(_ blLmSOneDCSP và giá trị tối ưu của bài toán nới lỏng liên tục của nó luôn luôn nhỏ hơn 2” Trong thực tế người ta chưa chỉ ra được các ví dụ có sự sai khác lớn hơn 7/6 [44]. Hơn nữa, những ví dụ có sai khác nhỏ hơn 1 chiếm đa số. Những bài toán như vậy được gọi là các bài toán có tính chất làm tròn nguyên (Integer Round-Up Property – IRUP). Những bài toán có sai khác lớn hơn hoặc bằng 1 được gọi là những bài toán non-IRUP. Trên cơ sở dự đoán đó, Gilmore và Gomory đề xuất cách tiếp cận giải bài toán (1.1)-(1.4) gồm 2 bước: 1/ giải bài toán nới lỏng liên tục của (1.1)-(1.4); 2/ Làm tròn số nghiệm tối ưu của bài toán nới lỏng liên tục để nhận được nghiệm của bài toán (1.1)-(1.4). Để giải bài toán nới lỏng liên tục của (1.1)-(1.4) với số lượng biến n rất lớn, Gilmore và Gomory lần đầu tiên đề xuất sử dụng kỹ thuật tạo sinh cột , trong đó mỗi biến chỉ được 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 các biến phụ (slacks) ta có thể đưa bài toán (1.1)-(1.4) về dạng chuẩn:  _ ( , , , ) min : , nOneDCSP S m L l b x Ax b x    (1.5) 12 Nới lỏng liên tục của (1.5) nhận được bằng cách 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:  _ ( , , , ) min : ,LP nOneDCSP S m L l b x Ax b x    (1.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à bài toán chủ hạn chế (Restricted Master Problem - RMP). RMP có thể được khởi tạo dễ dàng, ví dụ 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 chọn. Khi đó RMP có dạng:  _ ( , , , ) min : ' ,LP nOneDCSP S m L l b x A x b x    (1.7) 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 (1.7) được xác định bởi công thức ua1 , với mu  là các giá trị biến đối ngẫu tối ưu của (1.7). Do vậy việc tìm kiếm cột có thể đóng góp cải thiện giá trị hàm mục tiêu chính là việc tìm nghiệm tối ưu của bài toán con định giá ( hay là bài toán xếp ba lô):  max : , mua al L a   (1.8) Nghiệm tối ưu của (1.8) sẽ lần lượt được thêm vào RMP nếu giá trị tối ưu tương ứng của (1.8) lớn hơn 1. Nếu (1.8) không có nghiệm tối ưu như vậy thì nghiệm tối ưu của bài toán RMP (1.7) chính là nghiệm tối ưu của bài toán MP (1.6). Trên cơ sở ý tưởng vừa trình bày, phương pháp tạo sinh cột giải bài toán quy hoạch tuyến tính cỡ lớn được Gilmore-Gomory nhúng vào lược đồ nhánh cận (Brand and Bound) để tạo nên lược đồ phân nhánh và định giá (Branch and Price) cho việc giải bài toán quy hoạch nguyên OneDCSP_S. Đã có nhiều chiến lược phân nhánh heuristic khác nhau được đề xuất. Một số chiến lược đó có thể tra cứu trong [44,58]. 13 1.1.2. Mô hình Arc-flow của Valerio de Carvalho Valerio de Carvalho [55] lần đầu tiên đề xuất phát biểu lại bài toán (1.1)-(1.4) dưới dạng một mô hình dựa trên mạng lưới (network -based model) rất sáng sủa với tên gọi Arc-Flow Model như sau. Chúng ta xây dựng một mạng lưới không chu trình G=(N,A) Trong đó: - N={0,1,…,L} là tập các nút; -     LNuvumiluvNNvuA i \/),(,..,1,/),(  là tập các cung. Các cung nối mỗi cặp nút liên tiếp từ 0 tới L không phủ bất cứ một thành phẩm nào. Một sản phẩm thứ i được biểu diễn một số lần trên mạng lưới bởi các cung có độ dài v-u=li, i=1,…,m. Ta ký hiệu các biến quyết định xuv là số lượng các cung thành phẩm có kích thước v-u được cắt từ bất cứ tấm vật liệu thô nào tại nút cách biên trái của tấm vật tư u đơn vị. Một đường đi từ nút khởi đầu 0 tới nút kết thúc L chứa ít nhất một cung có độ dài li (i=1,…,m) sẽ mã hóa một phương án cắt chấp nhận được. 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} 0 1 2 3 4 5 6 7 8 9 4 2 2 14 Với cách xác định mạng lưới như vậy , bài toán OneDCSP_S sẽ có độ phức tạp tính toán giả đa thức (Pseudo-polynomial) O(mL) và trở thành bài toán tìm luồng cực tiểu sau: Min z (1.9) trên miền ràng buộc: i Aluu luu bx i i  ),( , với i {1,…,m} (1.10) zx Avo v  ),( ,0 (1.11) 0 ),(),(    Atv vt Avu uv xx v {1,…,L-1} (1.12) zx ALu uL  ),( (1.13) uvx  (u,v)A (1.14) Nếu ta áp dụng phân rã Dantzig-Wolfe (biểu diễn một điểm trong đa diện bằng tổ hợp lồi của các điểm cực cộng với một tổ hợp tuyến tính không âm của các tia cực) vào bài toán (1.9)-(1.14) và giữ ràng buộc (1.10) trong bài toán chủ thì bài toán con xác định bởi (1.11)-(1.14) là bài toán luồng với không gian nghiệm tương ứng với các luồng chấp nhận được giữa nút khởi đầu 0 và nút kết thúc L. Bài toán con này thể hiện ràng buộc bảo toàn luồng (flow conservation constrain) với lượng cung cấp vật tư chưa biết z từ điểm khởi đầu và đáp ứng yêu cầu tại điểm kết thúc. Cho các nhân tử đối ngẫu i, i=1,…,m gán với ràng buộc (1.10), bài toán con định giá trở thành:    Aluu luui i ixzMin ),( , (1.15) trên miền ràng buộc (1.11)-(1.14) Thực chất, biến z có thể được coi như cung phản hồi từ nút kết thúc L tới nút khởi đầu 0 (cũng có thể ký hiệu là xw0) và các nghiệm của bài toán con như là luồng 15 chu trình được tạo nên bởi đường đi từ nút khởi đầu 0 tới nút kết thúc L và cung xw0. Như vậy có một tương ứng 1-1 giữa các chu trình và các đường đi. Nếu chúng ta coi các nghiệm của bài toán con như các chu trình, các ràng buộc của bài toán con xác định một hệ thuần nhất và không giới nội. Do đó, đa diện tương ứng có một điểm cực duy nhất là nghiệm 0 và một số hữu hạn các tia cực là các chu trình có hướng, mỗi chu trình tương ứng với một phương án cắt chấp nhận được. Bài toán con chỉ sinh ra các tia cực và việc thay thế chúng vào (1.9) và (1.10) sẽ tạo nên mô hình Gilmore-Gomory (1.2)-(1.4) gồm tổ hợp tuyến tính không âm của các phương án cắt và không có ràng buộc lồi. Do hai mô hình là tương đương nên các cận dưới của các nới lỏng tuyến tính liên tục của chúng là bằng nhau, tức là mô hình arc flow cũng có nới lỏng tuyến tính mạnh sau khi áp dụng phân rã Dantzig-Wolfe. Bài toán con định giá (1.15) với miền ràng buộc (1.11)-(1.14) là bài toán tìm đường đi ngắn nhất trên một mạng lưới có kích thước giả đa thức và có thể được giải bởi thuật toán quy hoạch động và nghiệm tối ưu của nó cũng là nghiệm tối ưu của bài toán xếp ba lô (1.8) [55]. Ưu điểm của mô hình này là hoàn toàn không làm thay đổi cấu trúc của bài toán chủ và các bài toán con khi tạo nới lỏng tuyến tính liên tục cũng như trong quá trình thực hiện chiến lược phân nhánh và định giá. Ta nhận thấy rằng, mô hình trên có nhược điểm là tính đối xứng. Để loại bỏ điều đó, Valerio de Carvalho đề xuất các thành phẩm được cắt theo chiều giảm của kích thước, tức là các cung tương ứng với các thành phẩm có kích thước lớn hơn sẽ được xếp ở gần nút 0 hơn và phế thải được dồn về phía nút L. Từ đó, Valerio de Carvalho đã đề xuất thuật toán giải chính xác bài toán OneDCSP_S với ý tưởng chính như sau: Chiến lược phân nhánh: Giả sử xpq là một biến luồng trong mô hình arc flow. Như vậy, một phương án cắt trong mô hình Gilmore-Gomory tương ứng sẽ đóng góp cho biến luồng xpq nếu nó có một thành phẩm kích thước q-p được cắt từ điểm bắt đầu là p. Nếu ta ký hiệu 16 A(p,q) là tập tất cả các phương án cắt trong mô hình của Gilmore-Gomory chứa thành phẩm có độ dài q-p tại điểm có khoảng cách p từ biên trái của vật liệu và các xj là các biến quyết định của mô hình này, ta có thể xác định giá trị của biến luồng xpq như sau:    ),( qpAj jpq xx  (1.16) Nếu  không nguyên, ta tạo 2 nhánh tương ứng với các bất đẳng thức xpq≤  và xpq≥  đối với một cung đơn tại vị trí ( p,q). Nói cách khác các ràng buộc phân nhánh chỉ tác động tớ i các phương án cắt có cung tại vị trí (p,q). Khi đó ta có bài toán OneDCSP_S trên nút w bất kỳ có dạng sau:  Jj jxMin (1.17) trên miền ràng buộc:    Jj ijij bxa , i=1,…,m (1.18)     Jj wl ijj l j Glxx , (1.19)     Jj wl ijj l j Hlxx , (1.20) xj≥0, jJ (1.21) ở đây Gw và Hw là các tập hợp chỉ số của các ràng buộc phân nhánh có dạng ≤ và ≥ tương ứng; lijx là các giá trị không nguyên của luồng 0< lijx <bi; lj =1 nếu cung (i,i+li) thuộc phương án cắt j và bằng 0 nếu ngược lại; J là tập tất cả các phương án cắt chấp nhận được. Ta thấy (1.17)-(1.18) chính là mô hình của Gilmore-Gomory; (1.19)-(1.20) là các ràng buộc phân nhánh. Như vậy, mỗi nút của cây sẽ tương ứng với cùng một mô hình Gilmore -Gomory (phân rã Dantzig-Wolfe của mô hình Arc flow) (1.17)-(1.18) với việc bổ sung các ràng buộc phân nhánh dựa trên các biến luồng (1.19)-(1.20). 17 Giả sử d , d=1,…,m, là các biến đối ngẫu của (1.17) -(1.18);  và  là các véc tơ các biến đối ngẫu tương ứng các ràng buộc rẽ nhánh (1.19) -(1.20); ww ji GG ),( và ww ji HH ),( là tập các ràng buộc rẽ nhánh áp đặt cho một cung xác định ( i,j) tại nút w cho trước trên cây phân nhánh và định giá. Khi đó giá suy giảm của biến xij tại nút w được tính bằng công thức:    w jiw ji Hl l Gl ldijc ),(),(  (1.22) với d là thành phẩm tương ứng với cung ( i,j). Ta nhận thấy rằng chỉ có giá của các biến là thay đổi còn cấu trúc của bài toán con được giữ nguyên. Bài toán con này có thể giải bằng phương pháp quy hoạch động giống như giải bài toán xếp ba lô và chỉ cho các phương án cắt chấp nhận được với các thành phẩm được xếp theo thứ tự kích thước giảm. Các phương trình đệ quy được cho như sau: 0)0(0 F ,)(max)( 1 0 ,)1(10: max         l k kwxwkxddlllvalidd ddd clwxFxF x=0,1,…,L, d=1,…,m với  )/,min(max ddd lLbl  là cận trên của số lượng thành phẩm d trong một phương án cắt giới hạn bởi kế hoạch sản xuất của thành phẩm đó và kích thước của vật liệu thô. Để đưa ra giả mã thuật toán phân nhánh và định giá AF (theo mô hình Arc-Flow) giải chính xác bài toán OneDCSP_S theo đề xuất của Carvalho, chúng ta sử dụng những ký hiệu sau: - W: tập các nút trên cây phân nhánh. Mỗi nút cụ thể được ký hiệu là w - Aw là tập các cung của mô hình arc-flow tại nút w 18 - Gw là tập chỉ số các bất đẳng thức rẽ nhánh có dấu  đối với các biến luồng tại nút w - Hw là tập chỉ số các bất đẳng thức rẽ nhánh có dấu  đối với các biến luồng tại nút w Như vậy, mỗi nút trên cây phân nhánh sẽ được đặc trưng bởi bộ ba w=(Aw,Gw,Hw). Từ đó ta có thể phát biểu thuật toán AF như sau: THUẬT TOÁN AF: Start: Khởi tạo tập các nút W ban đầu chỉ chứa một nút gốc w=(A w,Gw,Hw) với Aw là một tập các cung tương ứng với nghiệm chấp nhận được tùy chọ n X* với giá trị hàm mục tiêu là z*; Gw =Hw= ; w*w; // (Bài toán chủ hạn chế RMP) while W  do Chọn một nút w trong W Tìm nghiệm tối ưu X LP và giá trị tối ưu của hàm mục tiêu tương ứng z LP cho nới lỏng tuyến tính của RMP nhận được từ phân rã Dantzig -Wolfe của w. Giải bài toán định giá với các nghiệm đối ngẫu tối ưu tương ứng của w if Có cung mới (u,v) nằm trong đường đi tương ứng với cột có giá âm then Aw=Aw   ,u v // (Bổ sung cột) else if zLP ≥ z* then W=W \{w} else if Nghiệm nhận được X LP là nguyên then Cập nhật nghiệm tối ưu mới: X*XLP , z* zLP, w*w else Phân nhánh: Giả xử xij= không nguyên. W=W{w’,w”} trong đó 19 w’=(Aw,Gw’ ,Hw ) w”=(Aw,Gw,Hw’’) Gw’=Gw  ijx      Hw’’=Hw  ijx      end while Return (X*, nút chứa nó w* ) 1.2. Giải thuật di truyền Ý tưởng áp dụng các nguyên lý của Darwin để tự động giải bài toán xuất hiện từ những năm 40 của thế kỷ 20, rất lâu trước khi máy tính ra đời [22]. Từ những năm đó Turing đã đề xuất “phép tìm kiếm tiến hóa hay tìm kiếm g en” (Genetical or evolutionary search). Trong những năm 1960, ba khuynh hướng phát triển của ý tưởng cơ sở này đã diễn ra ở các nơi khác nhau. Tại Mỹ, Fogel, Owens và Walsh đề xuất hướng nghiên cứu lập trình tiến hóa (Evolutionary programming) [23,24] cùng thời điểm với phương pháp của Holland có tên gọi là giải thuật di truyền (Genetic Algorithm) [17,28,29]. Trong khi đó tại Đức, Rechenberg và Schwefel đặt nền móng cho chiến lược tiến hóa (Evolution Strategies) [47]. Trong khoảng 15 năm sau đó, các hướng nghiên cứu này được phát triển một cách riêng biệt. Cho đến những năm 1990, các hướng nghiên cứu này được nhìn nhận lại như những thể hiện khác nhau của một công nghệ chung là tính toán tiến hóa (Evolutionary Computing) [4, 5, 6, 18, 40]. Cũng trong thời điểm này, một nhánh thứ tư dựa trên ý tưởng chung ra đời với tên gọi lập trình gen (genetic programming) do Koza đi tiên phong [7,37,38]. Trong thuật ngữ hiện đại, toàn bộ lĩnh vực nghiên cứu này được coi là ngành tính toán tiến hóa, các thuật toán trong đó được gọi là các thuật toán tiến hóa. Lập trình tiến hóa, chiến lược tiến hóa, giải thuật di truyền và lập trình gen được xem như các lĩnh vực nhỏ thuộc về các biến thể của thuật toán tương ứng. 20 Giải thuật di truyền là một họ các mô hình tính toán dựa trên ý tưởng tiến hóa. Các giải thuật này mã hóa nghiệm tiềm năng của một bài toán cụ thể bằng một cấu trúc dữ liệu giống như các nhiễm sắc thể (chromosome) và áp dụng các toán tử tái tổ hợp (recombination operators) lên các cấu trúc dữ liệu đó sao cho có thể g iữ được các thông tin chính. Giải thuật di truyền thường được xem như những bộ tối ưu hàm số mặc dù chúng có thể được áp dụng vào nhiều lĩnh vực rộng hơn. Một cài đặt của giải thuật di truyền bắt đầu với một quần thể các nhiễm sắc thể (thường được tạo ngẫu nhiên). Người ta đánh giá các cấu trúc này và phân bổ cơ hội tái sinh cho chúng theo cách những nhiễm sắc thể biểu diễn nghiệm tốt hơn của bài toán sẽ được ưu tiên hơn các nhiễm sắc thể khác để tái sinh. Mức độ “tốt” của một nghiệm thường được xác định tư ơng ứng với quần thể hiện thời. Mô tả của giải thuật di truyền như trên là khá trừu tượng và có hai cách hiểu về thuật ngữ “giải thuật di truyền”. Theo nghĩa chặt, “giải thuật di truyền” được coi là một mô hình tính toán do Holland đề xuất và nghiên cứu từ năm 1975. Hầu hết các lý thuyết về giải thuật di truyền đang tồn tại cho đến hiện nay đều dùng thuật ngữ theo nghĩa này và khi đó mô hình được gọi là giải thuật di truyền chính tắc. Theo nghĩa rộng hơn, giải thuật di truyền được coi là bất cứ một mô hình nào dựa trên quần thể (population-based model) nào có sử dụng các toán tử tái tổ hợp và lựa chọn để sinh ra các điểm mẫu mới trong không gian tìm kiếm. Nhiều mô hình giải thuật di truyền đã được các nhà nghiên cứu thực nghiệm đưa ra trên quan điểm hướng ứng dụng và xem giải thuật di truyền như công cụ tối ưu hóa. Trong mục này, chúng ta sẽ trình bày những khái niệm cơ bản liên quan tới giải thuật di truyền. Trong hầu hết các giải thuật di truyền thông thường có hai thành phần phụ thuộc vào bài toán: mã hóa bài toán và hàm đánh giá. Bước đầu tiên trong bất kỳ một giải thuật di truyền nào là bước tạo sinh quần thể xuất phát. Trong giải thuật di truyền chính tắc, mỗi thành viên của quần thể này là một chuỗi nhị phân độ dài l tương ứng với mã hóa nghiệm của bài toán. Mỗi chuỗi 21 như vậy được xem như một nhiễm sắc thể. Trong hầu hết các trường hợp, quần thể này được sinh ra một cách ngẫu nhiên. Sau khi sinh ra quần thể xuất phát, mỗi cá thể của quần thể được đánh giá và được gán cho một giá trị thích nghi (fitness value). Khái niệm đánh giá (evaluation) và thích nghi (fitness) đôi khi được sử dụng như cặp từ đồng nghĩa. Tuy nhiên, người ta thường phân biệt giữa hàm đánh giá (evaluation function) và hàm thích nghi (fitness function) được sử dụng trong các giải thuật di truyền. Trong mục này, hàm đánh giá (hay hàm mục tiêu) cung cấp độ đo hiệu quả của việc thiết lập giá trị các tham số cụ thể. Hàm thích nghi biến đổi độ đo hiệu quả này thành việc phân bổ cơ hội tái tạo cho các cá thể. Việc đánh giá một chuỗi biểu diễn tập các tham số là hoàn toàn độc lập với việc đánh giá các chuỗi khác. Tuy nhiên, mức độ thích nghi (fitness) của một chuỗi luôn luôn được xác định trong mối tương quan với các thành viên khác trong quần thể hiện tại. Trong giải thuật di truyền, mức độ thích nghi có thể được xác định bằng /if f với if là đánh giá của chuỗi i và f là đánh giá trung bình của tất cả các chuỗi trong quần thể. Mức độ thích nghi cũng có thể được gán dựa trên thứ hạng của cá thể trong quần thể hoặc bằng các phương pháp lấy mẫu như phương pháp lựa chọn theo đấu loại. Việc thực hiện giải thuật di truyền có thể được xem như một quá trình hai giai đoạn. Thuật toán bắt đầu với quần thể hiện thời. Việc lựa chọn được áp dụng vào quần thể này để tạo ra một quần thể trung gian. Sau đó việc lai ghép và đột biến được áp dụng cho quần thể trung gian để tạo nên quần thể tiếp theo. Quá trình chuyển từ quần thể hiện thời tới quần thể tiếp theo tạo nên một thế hệ trong tiến trình thực hiện giải thuật di truyền. Cách thực hiện như vậy được gọi là cài đặt của giải thuật di truyền đơn giản (Simple Genetic Algorithm – SGA). Hình 1.3 minh họa việc hình thành một thế hệ mới theo hai pha: pha chọn lọc và pha tái tổ hợp. Việc đột biến có thể thực hiện ngay sau lai ghép. 22 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. Đầu tiên chúng ta xem xét việc xây dựng quần thể trung gian từ quần thể hiện thời. Trong thế hệ đầu tiên, quần thể hiện thời cũng đồng thời là quần thể xuất phát. Sau khi tính /if f cho tất cả các chuỗi trong quần thể hiện thời, chúng ta thực hiện việc lựa chọn. Trong giải thuật di truyền chính tắc, xác suất để một chuỗi trong quần thể hiện thời được sao chép lại và được đưa vào thế hệ trung gian tỷ lệ thuận với mức độ thích nghi của chúng. Có nhiều cách thực hiện việc lựa chọn. Chúng ta có thể ánh xạ quần thể lên một bánh xe roulette, mỗi cá thể chiếm một không gian tỷ lệ thuận với mức độ thích nghi của nó trên bánh xe. Quần thể trung gian được tạo nên nhờ việc quay liên tiếp bánh xe để chọn ra các cá thể theo cơ chế “lấy mẫu ngẫu nhiên có thay thế” (stochastic sampling with replacement). Cơ chế lựa chọn như vậy được gọi là lựa chọn tỷ lệ (proportional selection) và xác suất để một phần tử b được lựa chọn xác định bởi công thức sau:    n i ibfbfbp 1 0))(/)(()( Tái tổ hợp (Lai ghép, đột biến) Chọn lọc (Nhân đôi) Chuỗi 1 Chuỗi 2 Chuỗi 3 Chuỗi 4 … … Thế hệ hiện tại t Chuỗi 1 Chuỗi 2 Chuỗi 2 Chuỗi 4 … … Thế hệ trung gian t Con-A (1 x 2) Con-B (2 x 1) Con-A (2 x 4) Con-B (2 x 4) … … Thế hệ tiếp theo t+1 23 với b và các ib là các cá thể nằm trong quần thể hiện tại. Quá trình lựa chọn cũng có thể thực hiện bằng cơ chế “remainder stochastic sampling”. Khi đó mỗi chuỗi i với /if f lớn hơn 1 sẽ được sao chép vào quần thể trung gian với số lần bằng phần nguyên của /if f . Sau đó tất cả các chuỗi (kể cả các chuỗi có /if f nhỏ hơn 1) sẽ được sao chép thêm vào quần thể trung gian với xác suất tỷ lệ thuận với phần thập phân của chúng. Sau khi lựa chọn, việc tái tổ hợp được thực hiện trên quần thể trung gian. Việc này có thể được coi như việc tạo ra quần thể tiếp theo từ quần thể trung gian. Việc lai ghép (crossover) được áp dụng cho các chuỗi được ghép cặp một cách ngẫu nhiên với xác suất pc: Lấy ra một cặp chuỗi; tái tổ hợp hai chuỗi này với xác suất pc để tạo nên hai chuỗi mới và đặt chúng vào quần thể tiếp theo. Bước tiếp theo là việc áp dụng toán tử đột biến (mutation operator). Mỗi bit trong quần thể có thể chịu hiện tượng đột biến với xác suất pm. Thông thường, tần xuất đột biến được thực hiện với xác suất nhỏ hơn 1%. Trong một số trường hợp, đột biến được giải thích như việc tạo ngẫu nhiên một bit mới. Trong các trường hợp khác, đột biến được xem là phép lật bit. Sự khác nhau giữa hai cách giải thích thực chất chỉ là chi tiết cài đặt và mỗi kiểu đột biến đều có thể chuyển đ ổi để nhận được kiểu còn lại. Khi quá trình lựa chọn, tái tổ hợp và đột biến hoàn thành, quần thể tiếp theo lại được đưa vào chu trình lặp với các bước như trên. Như vậy một thế hệ mới đã được sinh ra khi thực hiện giải thuật di truyền. Giải thuật di truyền như mô tả trên có thể được viết dưới dạng giả mã như sau: 24 GIẢI THUẬT DI TRUYỀN Khởi tạo quần thể ban đầu  1,..., kX x x While (điều kiện kết thúc chưa thỏa mãn) do Đánh giá mức độ thích nghi của các cá thể trong X (evaluation) Lựa chọn một số cặp nghiệm (gọi là cha-mẹ) 2P X dựa trên mức độ thích nghi của chúng (Parent selection) Tổ hợp các cặp được lựa chọn để sinh ra các cá thể mới (crossover) Biến đổi ngẫu nhiên một số cá thể (mutation) Tạo quần thể mới bằng việc thay thế một số hoặc toàn bộ cá thể của X bởi các cá thể mới được sinh ra dựa trên mức độ thích nghi của chúng (population selection) End while Đã có nhiều công trình nghiên cứu nhằm mô hình hóa toán học giải thuật di truyền, các ảnh hưởng của các toán tử di truyền lên hành vi của giải thuật, đặc biệt là hành vi hội tụ tới nghiệm tối ưu. Các kết quả lý thuyết có ý nghĩa nhất theo hướng này được tổng kết một cách cô đọng trong công trình của Rudolph [ 45]: Việc mô hình hóa giải thuật di truyền bằng một xích Markov hữu hạn trên không gian các trạng thái là tập tất cả các quần thể có thể được sinh ra trong quá trình thực hiện của giải thuật và các toán tử di truyền là các ma trận chuyển trạng thái được xác định bởi các tham số như xác xuất đột biến pm , xác suất lựa chọn cha-mẹ pc … Trên cơ sở mô hình hóa giải thuật di truyền như vậy, người ta đã tiến hành phân tích hành vi của giải thuật bằng việc chỉ ra rằng với xác suất đột biến pm>0 giải thuật di truyền chính tắc là một xích Markov ergodic và vì vậy phân phối xác suất tới hạn của mọi trạng thái trong không gian trạng thái là dương chặt. Điều đó có nghĩa rằng , xuất phát từ một trạng thái ban đầu bất kỳ, tại mọi thời điểm, giải thuật có thể rơi vào trạng thái tương ứng với quần thể không chứa nghiệm tối ưu với một xác suất dương. Nói cách khác, giải thuật không hội tụ hoàn toàn. Để khắc phục nhược điểm 25 trên của giải thuật di truyền chính tắc, người ta đã cải biên giải thuật bằng cách thêm vào một toán tử sao chép (copy operator) cho phép cá thể có độ thích nghi cao nhất của từng quần thể được giữ lại cho quần thể tiếp theo. Phiên bản cải biên như vậy được gọi là giải thuật di truyền chính tắc với phần tử tinh hoa và được chứng minh là hội tụ hoàn toàn. Các kết quả chi tiết nghiên cứu về tính hội tụ của thuật toán di truyền có thể tham khảo tại [41,45,46]. 1.3. Kết luận Chương này tập trung giới thiệu hai vấn đề chính làm cơ sở cho việc trình bày các nội dung của Chương 2. 1. Bài toán cắt vật tư một chiều với một loại nguyên liệu OneDCSP_S và hai mô hình cùng giải thuật giải chính xác cho bài toán: mô hình của Gilmore – Gomory và mô hình Arc-Flow của Carvalho. Các giải thuật đều được xây dựng dựa trên việc nhúng kỹ thuật tạo sinh cột vào lược đồ nhánh cận B&B để tạo nên lược đồ phân nhánh và định giá B&P, đây là một phương pháp hiệu quả đề giải các bài toán quy hoạch nguyên cỡ lớn . 2. Phần tiếp theo của chương dành cho việc trình bày những khái niệm cơ bản về giải thuật di truyền: mã hóa nghiệm của bài toán, các toán tử di truyền và các sơ đồ thuật toán di truyền. Tính hội tụ của giải thuật di truyền chính tắc và biến thể của nó được tóm tắt ở cuối chương dựa trên kết quả nghiên cứu của Ruldoph [45]. 26 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 Chương này trình bày nội dung liên quan đến bài toán OneDCSP_M. Phần đầu của chương giới thiệu phát biểu bài toán OneDCSP_M của Gilmore và Gomory. Trên cơ sở phân tích mối liên quan giữa bài toán OneDCSP_S và bài toán OneDCSP_M, tác giả đã đưa ra phát biểu mới của bài toán OneDCSP_M trong phần thứ hai. Giải thuật di truyền lai ghép với kỹ thuật phân nhánh và định giá tạo nên thuật toán GA-AF giải quyết bài toán. Về mặt lý thuyết, thuật toán GA-AF được chứng minh đảm bảo tính hội tụ hầu chắc chắn. Những nội dung này được đề cập trong phần ba của chương. Phần thứ tư trình bày hiệu quả thực nghiệm của thuật toán. 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 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 OneDCSP, trong đó các tấm vật liệu thô có thể có kích thước khác nhau. Bài toán OneDCSP_M có thể được biểu diễn bằng các dữ liệu sau: (m,M,l=(l1,…,lm), b=(b1,…,bm),L=(L1,…,LM), c=(c1,…,cM)) trong đó: - m là số dạng vật liệu thành phẩm, - M là số các loại vật liệu thô sẽ được sử dụng, - Với mỗi dạng vật liệu thành phẩm j:  lj là chiều rộng thành phẩm  bj là đơn hàng cho loại vật liệu thành phẩm thứ j - Véc tơ L=( L1,…,LM), với Li là bề rộng loại vật liệu thô thứ i, 27 - ci là đơn giá của vật liệu thô thứ i, i=1,…,M. Trong bài này ta giả thiết rằng đơn giá của vật liệu thô tỷ lệ thuận với chiều rộng của vật liệu. Hình 2.1 minh họa các lát cắt trong mỗi phương án cắt với những loại vật liệu thô khác nhau của bài toán OneDCSP_M. Hình 2-1 Các phương án cắt trong bài toán OneDCSP_M Mô hình của bài toán trên (Machine Balance Model) được Gilmore và Gomory xây dựng trong [27]. Mô hình có thể được phát biểu như sau: Đặt m’=m+M. Một véc tơ   '1 ',..., mma a a   là biểu diễn của một phương án cắt nếu 1 1 m M j j j j m j j l a L a      và 1 1 M j m j a    (2.1) Các thành phần aj, j=1,…,m của véc tơ a xác định có bao nhiêu vật tư thành phẩm loại j được cắt. Thành phần mka  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 aj+m với j{1,…,M}\k bằng 0. Li liPhương án cắt j aij L1 li LM . . . . . . . . . 28 Gọi n là số lượng tất cả các phương án cắt. Giả sử ai với i=1,…,n là tất cả các phương án cắt và mỗi thành phần xi của véc tơ x=(x1,…,xn) là số lần sử dụng phương án cắt ai. Ta nhận xét rằng, n có thể rất lớn. Ta xây dựng một véc tơ 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 vật liệu loại k thì ki cc ' , i=1,…,n và k=1,…,M. Khi đó ta có mô hình: OneDCSP_M(m,M,l,b,L,c) = min c’x (2.2) trên miền ràng buộc: ji n i ij bxa  1 , j=1,…,m (2.3) )( 11 mji M j j m j ijj aLal     i=1,…,n (2.4) 1 1 )(    M j mjia i=1,…,n (2.5) nx  (2.6) 'm ia  i=1,…,n (2.7) Trong mô hình trên, aij (i=1,…,n; j=1,…,m) là số lượng thành phẩm thứ j được cắt theo phương án thứ i. 2.2. Phát biểu mới của bài toán OneDCSP_M Trong mục này chúng ta sẽ tiến hành phân tích mối quan hệ ngữ nghĩa giữa hai bài toán OneDCSP_S và OneDCSP_M và đưa ra một cách phát biểu mới cho bài toán OneDCSP_M. Định lý 2.1. [2] OneDCSP_M(m,M,l,b,L,c) OneDCSP_S(m,Lk,l,b)ck với mọi k{1,…,M}. Nói 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 loại vật liệu. Chứng minh 29 Do giả thiết giá của vật tư tỷ lệ thuận với bề rộng của nguyên liệu nên giá trị hàm mục tiêu chỉ phụ thuộc vào các phương án cắt. Các phương án cắt tối ưu cho (1.2) -(1.4) thỏa mãn (1.1) đối với chỉ số k nào đó thì cũng thỏa mãn (2.4) và do vậy chúng trở thành phương án chấp nhận được của (2.2)- (2.7). Điều này chứng minh khẳng định của định lý.  Định lý 2.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 nhiều kích thước vật liệu thô. Giả sử x* là nghiệm tối ưu của (2.2)-(2.7). Ta ký hiệu: - (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 trong (2.2)-(2.7) tương ứng x* ; - x* /(k) là thu hẹp của x* trên (k); - bk là véc tơ vật tư thành phẩm nhận được từ (2.2)-(2.7) với việc sử dụng số lần cắt theo 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). Định lý 2.2. [2] Nếu x* là nghiệm tối ưu của bài toán OneDCSP_M(m,M,l,b,L,c) (2.2)-(2.7) thì x* /(k) là nghiệm tối ưu của bài toán ),,,(_ kk blLmSOneDCSP (1.1)-(1.4), k=1,…,M. Chứng minh Giả sử x* là nghiệm tối ưu của (2.2)-(2.7). Rõ ràng rằng, nếu ta khởi tạo bài toán (1.1)-(1.4) với các phương án cắt được xác định trong )(k thì )(/* kx  chính là một nghiệm chấp nhận được của ),,,(_ kk blLmSOneDCSP . Vì vậy ta có )(/*),,,(_ kxblLmSOneDCSP kk  . Ta cần chỉ ra trong trường hợp này thực sự xảy ra dấu đẳng thức. Giả sử )(/* kx  không phải là nghiệm tối ưu của bài toán. Khi đó tồn tại x’ là nghiệm của nó và thỏa mãn: 30 )(/*'),,,(_ kxxblLmSOneDCSP kk  Vì việc cắt nguyên liệu thô thứ k hoàn toàn độc lập với việc cắt các nguyên liệu thô khác nên nếu ta thay tập các biến của x* nằm trong )(/* kx  bằng tập các biến tương ứng của x’ để nhận được tập biến mới x" và đưa các phương án cắt tạo nên x’ trong bài toán ),,,(_ kk blLmSOneDCSP vào (2.3) và (2.4) thì x" chính là một nghiệm chấp nhận được của (2.2)-(2.7). Tuy nhiên giá của hàm mục tiêu của bài toán (2.2)-(2.7) xác định trên x" sẽ nhỏ hơn giá của hàm mục tiêu xác định trên x*. Điều này mâu thuẫn với giả thiết x* là nghiệm tối ưu của (2.2)-(2.7). Như vậy )(/* kx  là nghiệm tối ưu của bài toán ),,,(_ kk blLmSOneDCSP . Định lý được chứng minh.  Trên cơ sở của Định lý 2.2, chúng ta có thể mô hình hóa bài toán OneDCSP_M dưới dạng phát biểu mới bởi Định lý sau. Định lý 2.3. Bài toán OneDCSP_M(m,M,l,b,L,c) tương đương với bài toán   M k k k k cblLmSOneDCSP 1 ),,,(_min (2.8) trên miền ràng buộc: bbM k k  1 (2.9) k mb  (2.10) Chứng minh. Giả sử nghiệm tối ưu của bài toán OneDCSP_M(m,M,l,b,L,c) là x* và các véc tơ nghiệm tối ưu của bài toán (2.8) -(2.10) là b**k. Đặt b*k là véc tơ sản phẩm được cắt trên loại vật liệu thứ k tương ứng với )(/* kx  . Khi đó ma trận B* được tạo thành từ các véc tơ cột b*k sẽ phải thỏa mãn (2.9)-(2.10) và theo Định lý 2.2 ta có : 31 k M k k k cblLmSOneDCSPcLblMmMOneDCSP ),,,(_),,,,,(_ 1 *   Nói cách khác, nghiệm của bài toán OneDCSP_M(m,M,l,b,L,c) là một nghiệm chấp nhận được của bài toán (2.8) -(2.10). Từ đó ta có bất đẳng thức: k M k k k cblLmSOneDCSPcLblMmMOneDCSP ),,,(_),,,,,(_ 1 **   Ngược lại, các véc tơ nghiệm tối ưu b**k của bài toán (2.8)-(2.10) bảo đảm đáp ứng yêu cầu kế hoạch b. Tức là việc thực hiện cắt vật tư theo nghiệm tối ưu đó sẽ là nghiệm chấp nhận được của bài toán OneDCSP_M(m,M,l,b,L,c). Từ đó ta có : k M k k k cblLmSOneDCSPcLblMmMOneDCSP ),,,(_),,,,,(_ 1 **   Hai bất đẳng thức trên khẳng định tính đúng đắn của định lý.  Định lý 2.4. [2] Nghiệm tối ưu của bài toán (2.8)-(2.10) sẽ xác định trên tập các véc tơ bk thỏa mãn bbM k k  1 . Tập các véc tơ bk như vậy được gọi là phân hoạch của b. Nói cách khác nghiệm tối ưu của (2.8)-(2.10) được xác định trên tập các phân hoạch của véc tơ b. Chứng minh Giả sử các kb thỏa mãn bbM k k  1 . Khi đó ta có thể chọn các véc tơ k mt  thỏa mãn: kk bt  k=1,…,M; bt M k k  1 . Rõ ràng rằng nếu x* là nghiệm tối ưu của ),,,(_ kk blLmSOneDCSP thì x* cũng là một nghiệm chấp nhận được của bài toán ),,,(_ kk tlLmSOneDCSP . Do đó ),,,(_),,,(_ kkkk blLmSOneDCSPtlLmSOneDCSP  k=1,…,M. Thay các bất đẳng thức này vào (2.8), định lý được chứng minh .  32 Các kết quả trên cho phép chúng ta phát biểu lại mô hình bài toán OneDCSP_M thông qua bài toán OneDCSP_S như sau : k M k k k cblLmSOneDCSPcLblMmMOneDCSP ),,,(_min),,,,,(_ 1    (2.11) trên miền ràng buộc: 1 M k k b b   (2.12) k mb  (2.13) 2.3. Giải thuật di truyền lai ghép giải bài toán OneDCSP_M Các định lý 2.2, 2.3, 2.4 và phát biểu mới của bài toán OneDCSP_M (2.11)- (2.13) gợi cho chúng ta ý tưởng phân rã bài toán OneDCSP_M thành các bài toán cơ sở là bài toán ),,,(_ kk blLmSOneDCSP để có thể áp dụng thuật toán AF giải nó. 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 được của bài toán OneDCSP_M. Việc tìm nghiệm tối ưu cho bài toán OneDCSP_M sẽ là việc tìm kiếm trong không gian các phân hoạch của véc tơ đơn hàng (2.12)-(2.13) những phân hoạch bảo đảm tối ưu (2.11). Ý tưởng trên là cơ sở để xây dựng một thuật toán lai ghép giữa giải thuật di truyền và thuật toán AF để giải bài toán OneDCSP_M. 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 giải thuật di truyền và thuật toán AF. Biểu diễn bài toán. Chúng ta sử dụng nhiễm sắc thể có cấu trúc (b1,...,bM), k mb  để biểu diễn các cá thể (các điểm) trong không gian tìm k iếm. Mỗi quần thể là một tập bao gồm một số cố định các cá thể. Độ đo thích nghi . Với mỗi cá thể s=(b1,...,bM) ta xác định mức độ thích nghi của cá thể, f(s), bằng công thức sau: 33    M k k k k cblLmSOneDCSP sf 1 ),,,(_ 1)( (2.14) Toán tử lai ghép . Giả sử  Mbbs 1111 ,..., và  Mbbs 2122 ,..., là 2 cá thể bất kỳ. Chúng ta đưa ra một số dạng toán tử lai ghép sau đây: Toán tử Lai ghép một điểm . Giả sử k là một số được lựa chọn ngẫu nhiên, mk 1 . Từ hai cá thể trên ta tạo ra hai hậu duệ '1s và '2s với các véc tơ cột tương ứng của chúng được xác định như sau:     ;1,...,1,1'1  kiibib jj     mkiibib jj ,...,,2'1  ; j=1,…,M (2.15)     1,...,1,2'2  kiibib jj ;     ;,...,,1'2 mkiibib jj  j=1,…,M (2.16) Toán tử lai ghép chọn lọc. Toán tử này nhằm trao đổi các thành phần mã hóa khác nhau nhất trong biểu diễn của hai cá thể. Chúng ta tính toán khoảng cách giữa các hàng theo công thức :    1 2 1 2 1 ( , ) M i i j i d s s b j b j    j=1,...,m (2.17) Giả sử t là tham số làm cực đại (2.17), tức là dt(s1,s2)= maxj=1,..,m{dj(s1,s2)} (2.18) Khi đó ta chọn điểm lai ghép là t và tạo ra hai hậu duệ '1s và '2s với các véc tơ cột tương ứng của chúng được xác định như sau:    '1 1 , 1,..., , ;j jb i b i i m i t      '1 2 ,j jb t b t j=1,…,M (2.19)    '2 2 , 1,... ,j jb i b i i m i t   ;    '2 1 ,j jb t b t j=1,…,M (2.20) Ta cũng có thể mở rộng toán tử lai ghép (2.19)-(2.20) để cho phép nhiều thành phần mã hóa được trao đổi giữa biểu diễn của hai cá thể t heo cách lựa chọn r hàng 34 có khoảng cách lớn nhất sau khi sắp xếp các khoảng cách (2.18) theo thứ tự giảm dần (1<r<m). Toán tử lai ghép ngẫu nhiên. Toán tử này sẽ lựa chọn điểm lai ghép t một cách ngẫu nhiên theo phân bố xác suất được xác định như sau :     1 2 1 2 1 ,( ) , t m i i d s sp t d s s    , t=1,...,m (2.21) Sau khi đã chọn điểm lai ghép, ta thực hiện việc lai ghép như trong (2.19)- (2.20) Toán tử đột biến. Cho cá thể  Mbbs ,...,1 . Toán tử đột biến địa phương . Chọn ngẫu nhiên một bộ 3 các số nguyên (p,q,r), Mqp  ,1 và mr 1 , với xác suất: 20 1mMp  (2.22) Toán tử đột biến địa phương tác động lên cá thể  Mbbs ,...,1 để tạo nên cá thể  Mbbs 1111 ,..., với bộ (p,q,r) đã chọn như sau: ii bb 1 khi qipi  & i=1,…,M (2.23)    jbjb pp 1 ,    jbjb qq 1 khi j=1,…,m và rj  (2.24)     11  rbrb pp ,     11  rbrb qq nếu   0rb p (2.25)    rbrb pp 1 ,    rbrb qq 1 nếu   0rb p (2.26) Toán tử đột biến phân phối đều . Chọn ngẫu nhiên một bộ 3 các số nguyên (p,q,r), Mqp  ,1 và mr 1 , với xác suất được xác định nh ư trong (2.22). Đặt    p qQ b r b r  . Khi đó ta chọn ngẫu nhiên một số t{0,1,...,Q}theo phân phối đều:  ( ) 1/ 1p t Q  (2.27) 35 và toán tử đột biến phân phối đều được xác định bởi công thức:  pb r t ;  qb r Q t  (2.28) Toán tử chọn lọc. Toán tử chọn lọc được xác định theo luật tỷ lệ thuận với mức độ thích nghi:    Gs s sf sfp )( )( (2.29) Trong đó s là cá thể và G là quần thể đang xem xét có chứa s. Định lý 2.5. [2] Giả sử hai cá thể cha-mẹ là các phân hoạch của cùng một véc tơ. Khi đó các toán tử lai ghép và toán tử đột biến xác định như trên sẽ bảo đảm các hậu duệ cũng là những phân hoạch của véc tơ đó. Chứng minh Ta chứng minh khẳng định này cho toán tử lai ghép (2.15)-(2.16) và toán tử đột biến (2.23) -(2.26). Đối với các toán tử khác việc chứng minh hoàn toán tương tự. Nếu ta biểu diễn các cá thể dưới dạng bảng có kích thước m.M, trong đó cột i của bảng chứa véc tơ bi của cá thể, i=1,…,M. Khi đó toán tử lai ghép sẽ thực hiện việc trao đổi M-k hàng cuối cùng của 2 bảng tương ứng với 2 phần tử cha-mẹ cho nhau để tạo nên 2 hậu duệ. Còn đối với toán tử đột biến, hậu duệ sẽ hoặc là bản sao của cha-mẹ theo (2.23),(2.24)-(2.26), hoặc chỉ thay đổi tại hàng r theo (2.23),(2.24)-(2.25). Vì vậy tổng các cột của hậu duệ luôn bằng tổng các cột của cha-mẹ. Định lý được chứng minh.  Dựa trên các Định lý 2.1, 2.2, 2.3, 2.4, 2.5 chúng ta có thể xây dựng thuật toán lai ghép như sau: THUẬT TOÁN GA-AF Input: m, M , l, L, b, c 36 Output: Nghiệm tối ưu của bài toán OneDCSP_M(m,M,l,b,L,c) và các phương án cắt tương ứng với nghiệm tối ưu đó Bước 0. Khởi tạo quần thể gồm K cá thể  0010 ,..., KssG  . Việc khởi tạo này có thể thực hiện dễ dàng bằng việc tạo ra K phân hoạch khác nhau của b, mỗi phân hoạch sẽ tương ứng với một đối tượng của quần thể. Các cá thể được biểu diễn như sau:  0010 ,..., iMii bbs  , 0 mijb  ,    M j ij bb 1 0 , i=1,…,K Bước 1. Giải các bài toán ),,,(_ tikk blLmSOneDCSP bằng thuật toán AF, i=1,…,K, k=1,…,M, t là thứ tự bước lặp (thứ tự của quần thể). Tính mức độ thích nghi )( tisf cho từng cá thể của Gt theo (2.14). Bước 2. Lựa chọn các cha-mẹ trong Gt theo mức độ thích nghi để ghép cặp theo toán tử lai ghép (2.15)-(2.16) để tạo nên tập các hậu thế 'tG với K1 phần tử. Bước 3. Tác động toán tử đột biến (2.23)-(2.26) vào 'tt GG  để nhận được ''tG . Bước 4. Thực hiện tính toán giống như trong Bước 1 cho các cá thể của ''tG . Bước 5. Áp dụng toán tử chọn lọc (2.29) lên ''tt GG  để chọn ra K cá thể có mức độ thích nghi lớn nhất tạo quần thể mới 1tG . Bước 6. Nếu điều kiện dừng chưa thỏa mãn quay lại Bước 2. Ngược lại thuật toán dừng và cho nghiệm tối ưu cùng tập các phương án cắt tương ứng với nghiệm tối ưu. Để khảo sát tính chất của thuật toán GA-AF với giả thiết giá của vật liệu thô tỷ lệ thuận với chiều rộng của vật liệu, ta có thể chỉ ra một số tính chất sau. Bổ đề 2.6. [2] Nghiệm tối ưu của bài toán OneDCSP_M nằm trong khoảng sau: 37   ObccLblMmMOneDCSPco m j jkkkk      1 max),,,,,(_min (2.30) Và xác suất chọn lọc trở thành cá thể thuộc quần thể tiếp theo của từng cá thể s thỏa mãn: 0/)2( /1 1 1  poKK Ops (2.31) Chứng minh Thật vậy, trong (2.30) bất đẳng thức đầu tiên xảy ra do có ít nhất một loại vật liệu thô được đưa vào sản xuất để đáp ứng đơn hàng. Đẳng thức sẽ đạt được trong trường hợp chỉ cần dùng 1 tấm vật liệu thô nhỏ nhất là đủ để sản xuất. Nói cách khác nếu ký hiệu  kk LL min*  thì đẳng thức xảy ra khi thỏa mãn:    m j jjblL 1 * Bất đẳng thức thứ hai là hiển nhiên khi ta sử dụng mỗi vật liệu thô có chiều rộng lớn nhất chỉ để cắt 1 vật tư thành phẩm. Bất đẳng thức (2.31) được suy ra trực tiếp từ (2.29), (2.30) và cơ chế hoạt động của thuật toán GA-AF.  Sau đây chúng ta sẽ sử dụng các ký hiệu sau: Partition(b) là tập tất cả các phân hoạch của b thành M phân hoạch;  tt GssfF  :)(max : mức độ thích nghi lớn nhất của quần thể tG ;  )(:)(max* bPartitionssfF  : mức độ thích nghi lớn nhất của tất cả không gian nghiệm. Mức độ thích nghi lớn nhất này chính là nghịch đảo của nghiệm tối ưu toàn cục của bài toán OneDCSP_M;  ** )(:)( FsfbPartitionsS  : tập tất cả các cá thể tương ứng với nghiệm tối ưu toàn cục của bài toán OneDCSP_M. 38 Ta nhận xét rằng, mỗi khi *FFt  thì quần thể tG sẽ chứa một cá thể biểu diễn nghiệm tối ưu toàn cục của bài toán OneDCSP_M. Định nghĩa 2.1. Ký hiệu biến ngẫu nhiên  *:0min FFtF t  là lần đầu tiên trong quần thể tG chứa cá thể biểu diễn nghiệm tối ưu toàn cục của bài toán OneDCSP_M. Khi đó ta nói rằng thuật toán GA-AF hội tụ hầu chắc chắn nếu nó đạt được nghiệm tối ưu toàn cục trong khoảng thời gian hữu hạn với xác suất P{F<}=1 không phụ thuộc vào quần thể khởi đầu. Định nghĩa 2.2. Giả sử s và s’ là hai cá thể khác nhau trong Partition(b). Cá thể s’ được gọi là có thể đạt được từ s nếu tồn tại một dãy hữu hạn các cá thể rsss ,...,, 21 đôi một khác nhau của Partition(b) sao cho 1ss  , rss ' và 1is nhận được từ is với xác suất dương bằng việc áp dụng toán tử đột biến vào is , i=2,…,r. Bổ đề 2.7. [2] Mọi cá thể trong Partition(b) đều có thể đạt được từ cá thể bất kỳ của Partition(b). Chứng minh Giả sử s, s’ là hai cá thể khác nhau bất kỳ trong Partition(b). Nếu ta biểu diễn hai cá thể đó bằng hai ma trận A và A’ kích thước m.M, ta có thể định nghĩa khoảng cách giữa hai cá thể này là:     m i M j ijij aassd 1 1 ' 2 1)',( Do s và s’ là các phân hoạch khác nhau của véc tơ b nên nếu tại một dòng r nào đó của ma trận A tồn tại một chỉ số p sao cho 'rprp aa  thì cũng sẽ tồn tại một chỉ số q mà tại đó thỏa mãn 'rqrq aa  . Khi đó ta có thể thực hiện phép đột biến trên bộ 3 (p,q,r) với xác suất 0p vào s để nhận được cá thể mới s” cũng là phần tử của Partition(b). Khi đó d(s”,s’)=d(s,s’)-1. Thực hiện lên tiếp thủ tục này d(s,s’) lần ta sẽ nhận được s’. 39 Theo giả thiết ban đầu, s và s’ là hai cá thể bất kỳ nên Bổ đề được chứ ng minh.  Định lý 2.8. [2] Thuật toán GA-AF là hội tụ hầu chắc chắn. Chứng minh Giả sử s, s’ là hai cá thể của Partition(b) sao cho *Ss và *' Ss  . Theo Bổ đề 2.7 , s’ có thể đạt được từ s, tức là tồn tại một nhánh hữu hạn đi từ s đến s’ mà mỗi cá thể trên đó nhận được bằng việc tác động toán tử đột biến vào cá thể đứng trước nó. Dễ dàng chỉ ra rằng độ dài của nhánh ngắn nhất đi từ s tới s’ bằng các toán tử đột biến chính là d(s,s’). Đặt  *'' :),(max Ssssdks  và  *:max Sskk s  . Xét một cá thể tùy ý s của một quần thể nào đó. Theo thuật toán GA-AF, Bước 3 bảo đảm rằng cá thể này chắc chắn được tác động bởi toán tử đột biến và xác suất để ảnh của nó qua toán tử đột biến trở thành điểm tiếp theo trên đường đi ngắn nhất từ s đến *S sẽ không nhỏ hơn 0p . Theo (2.29) và ước lượng (2.31), ta có xác suất để một cá thể bất kỳ được lựa chọn làm cá thể thuộc quần thể thế hệ sau không nhỏ hơn 1p . Như vậy xác suất để ảnh của s qua phép đột biến đồng thời là điểm tiếp theo trên đường đi ngắn nhất từ s tới *S và được lựa chọn làm cá thể của quần thể thế hệ sau sẽ không nhỏ hơn 0. 10 pp . Lặp liên tiếp sk lần lập luận như trên, ta thấy xác suất chuyển từ *Ss vào thành cá thể nào đó thuộc *S tại bước lặp thứ sk sẽ không nhỏ hơn 0. 110 ss kk pp . Vì vậy ta có thể đánh giá xác suất để một cá thể tối ưu toàn cục được xét đến trong thuật toán sau k vòng lặp sẽ không nhỏ hơn 0. 110 kk pp và không phụ thuộc vào sự khởi đầu thực sự của *Ss . Từ đây suy ra rằng, xác suất để thuật toán không xét đến bất kỳ một nghiệm tối ưu nào sau t vòng lặp sẽ lớn nhất là   ktkk pp /110 .1  (2.32) 40 Dễ thấy rằng đại lượng trong (2.32) sẽ hội tụ rất nhanh theo tốc độ lũy thừa tới 0 khi t . Điều này có nghĩa 1)( FP (hay là nghiệm tối ưu toàn cục được thuật toán xét đến lần đầu tiên sau hữu hạn bước lặp với xác suất bằng 1). Do s là cá thể tùy ý nên Định lý được chứng minh.  Các kết quả lý thuyết trong mục này sẽ được dùng làm cơ sở cho việc xây dựng hệ thống đa tác tử với tên gọi GMAS -OneDCSP_M được trình bày trong Chương 3. 2.4. Kết quả tính toán Thuật toán GA-AF đã được t riển khai tại Nhà máy ống thép Việt-Đức. Việc khai thác phần mềm phụ thuộc vào những tác động sau: - Kế hoạch sản xuất phụ thuộc hoàn toàn vào thị trường tiêu thụ. Có những thời điểm nhà máy hoạt động ba ca, có những thời điểm chỉ hoạt động hai ca và thậm chí hoạt động cầm chừng. Vì vậy kế hoạch luôn thay đổi cho phù hợp với biến động của thị trường. - Nguồn vật liệu thô cũng thường xuyên biến động. Điều này cũng ảnh hưởng tới quá trình khai thác phần mềm. Mỗi khi có loại vật liệu mới được nhập về, mặc dù kế hoạch cũ (nghiệm cũ) chưa thực hiện xong thì phần tồn tại được tính vào dự báo biến động thị trường để có kế hoạch mới và lặp lại việc khai thác phần mềm với các tham số được thiết lập phù hợp nên các kế hoạch luôn có sự gối đầu và chồng lấn lên nhau. Chính và vậy, việc thu thập dữ liệu chính xác để đánh giá hiệu quả của GA -AF gặp nhiều khó khăn (sự giao nhau giữa các kế hoạch và tham số đầu vào của thuật toán). - Cũng trong quá trình quan sát thực tế sản xuất tác giả có nhận thấy rằng, các loại sản phẩm đáp ứng yêu cầu thị trường của nhà máy khá ổn định (ít chủng loại) nên dữ liệu có được cũng rất đơn điệu, khó phản ánh một cách khách quan các khía cạnh khác nhau của thuật toán. 41 Tuy nhiên, kết quả phản ánh chung nhất từ nhà sản xuất là từ khi khai thác phần mềm này, lượng phế thải giảm đi một cách đáng kể [1]. Sau một năm sử dụng phần mềm, số liệu thống kê chung cho thấy: - Lượng phế liệu trên tổng khối lượng thép thành phẩm giảm từ 3% xuống còn 1%. - Tổng sản phẩm tồn kho từng kỳ trên tổng sản phẩm được sản xuất t heo kế hoạch định kỳ giảm từ 9% xuống còn 4%. Với năng lực sản xuất của nhà máy tại thời điểm triển khai thử nghiệm là 70.000 tấn/năm, khối lượng vật tư đã tiết kiệm được khoảng hơn 1000 tấn. Theo phân loại của Waescher [57], các bài toán OneDCSP_M được phân làm hai lớp. Lớp đầu tiên chính là bài toán đặt ra cho Luận án và được gọi là lớp OneDCSP_M với số lượng vật liệu thô không hạn chế (unlimited stock quantity). Lớp thứ hai là lớp các bài toán nhận được từ lớp thứ nhất với việc bổ sung ràng buộc về số lượng vật liệu thô của mỗi loại và được gọi là lớp bài toán OneDCSP_M với số lượng vật liệu thô hạn chế (limited stock quantity). Theo sự hiểu biết của tác giả, cho tới thời điểm hiện tại chưa có công trình nghiên cứu thực nghiệm nào về bài toán của lớp thứ nhất được công bố [ 14]. Đối với lớp bài toán thứ hai cũng có rất ít công trình đề cập đến. Belov và Scheithauer [11] đã mở rộng thuật toán mặt phẳng cắt cho trường hợp một loại vật liệu thô để giải bài toán OneDCSP_M với số lượng vật liệu thô hạn chế. Alves và Carvalho [56] xây dựng mô hình Arc-flow để giải quyết chính xác bài toán thuộc lớp hai. Mới đây nhất, Silvio A. Araujo và đồng sự [ 48] đề xuất giải pháp heuristic trên cơ sở thuật toán tiến hóa (Evolutionary Algorithm) cho lớp bài toán này đồng thời tiến hành nghiên cứu so sánh các kết quả đạt được với kết quả của Belov và Scheithauer [11]. Như đã phân tích ở trên, bài toán đặt ra trong Luận án có điểm khác biệt với các bài toán do các tác giả trên giải quyết bởi sự có mặt hoặc không có mặt của ràng 42 buộc về số lượng vật liệu thô. Do đó việc nghiên cứu so sánh giữa đề xuất của tác giả Luận án với những kết quả trên sẽ không phản ánh được đầy đủ các ưu, nhược điểm giữa các giải pháp. Tuy nhiên, để có một đánh giá ban đầu về hiệu quả của phương pháp được đề xuất trong Luận án, tác giả đã tiến hành lựa chọn các tham số chung giữa hai bài toán và thử nghiệm phương pháp của mình trên các dữ liệu được lọc ra theo các tham số này từ các bài toán được Belov và Scheithauer công bố tại địa chỉ: Dữ liệu này gồm 3100 bài toán được tạo sinh một cách ngẫu nhiên và chia làm 31 nhóm, mỗi nhóm 100 bài toán. Sau khi loại bỏ các ràng buộc về số lượng vật liệu thô, các bài toán trở thành các bài toán thuộc lớp thứ nhất với các tham số đặc trưng sau đây: - Số loại vật liệu thô M=5 - Số loại sản phẩm m=40 - Kích thước từng loại vật liệu thô: L1=10000, Li thuộc tập {5000,5100,…,9900} i=2,…5 - Giá của từng loại vật liệu thô ci=Li, i=1,…,5 - Kích thước sản phẩm li được sinh ngẫu nhiên và nằm trong khoảng [v1Lmax,v2Lmax], với Lmax=max{Li}, i=1,…,M; v1={0.001; 0.01; 0.15; 0.25} và v2={0.2; 0.3;…;0.9} - Yêu cầu đối với mỗi loại sản phẩm: b i, i=1,…,M được sinh ngẫu nhiên và nằm trong khoảng [200,300] Nhận xét. Với cách tạo dữ liệu mẫu như vậy, nghiệm tối ưu của các bài toán nhận được là hoàn toàn chưa biết. Tuy nhiên có một nhận xét rằng, các nghiệm tối ưu của bài toán được Belov giải quyết luôn là nghiệm chấp nhận được của bài toán tương ứng đặt ra trong Luận án. Bởi vậy, ta hoàn toàn có thể coi nghiệm tối ưu của 43 Belov là nghiệm “tốt nhất” được biết tới cho đến thời điểm hiện tại đối với các bài toán tương ứng của Luận án. Từ đó để có thể đánh giá chất lượng của giải thuật, chúng ta sẽ tiến hành sử dụng nó giải các bài toán trên bộ dữ tham số chung giữa hai bài toán và so sánh các kết quả nhận được với các nghiệm “tốt nhất” đó của Belov-Scheithauer [11] và kết quả xấp xỉ của Silvio A. Araujo và đồng sự. Để có thể đánh giá chất lượng nghiệm cũng như hiệu quả về thời gian của thuật toán GA-AF, tác giả đã tiến hành chạy thử nghiệm trên toàn bộ số liệu được lọc ra từ 31 lớp với các tham số được lựa chọn như sau: - Kích thước quần thể: 10 - Tiêu chuẩn dừng: sau 1500 vòng lặp hoặc có 10 vòng lặp liên tiếp cho giá trị hàm mục tiêu như nhau - Hàm mục tiêu: chính là hàm mục tiêu của bài toán OneDCSP_M() Các tiêu chí để đánh giá bao gồm: - Chất lượng nghiệm được tính bằng độ lệch của nghiệm từ thuật toán GA - AF và nghiệm của Belov và Scheithauer theo công thức do Silvio A. Araujo và đồng sự đưa ra: ( _ ) ( & ) 100 & GA AF solution Belov Scheithauer solutionGAP Belov Scheithauer solution   - Thời gian: thời gian tối thiểu, thời gian trung bình và thời gian tối đa để giải từng lớp bài toán. Về chất lượng nghiệm: - Chất lượng nghiệm của thuật toán GA-AF được tổng kết trong bảng 2.1 [42] và bảng 2.3. Bảng 2.1 mô tả độ lệch trung bình, nhỏ nhất và lớn nhất của từng lớp bài toán và độ lệch trung bình chung, độ lệch nhỏ nhất và lớn nhất của 31 lớp. Độ lệch trung bình chung của 31 lớp bài toán là -0.06%, độ lệch tối đa là 2.05% và tối thiểu là -6.18% [42]. Trong rất nhiều bài toán thuộc các lớp bài toán như lớp bài toán C7, C14, C16, C22-C25, 44 C26-C31 nghiệm nhận được của Luận án tốt hơn nghiệm của Belov - Scheithauer và như vậy cũng tốt hơn nghiệm của Silvio A. Araujo và đồng sự. Điều này khẳng định nhận xét của chúng ta ở trên là nghiệm của Belov-Scheithauer luôn là nghiệm chấp nhận được của bài toán tương ứng thuộc lớp thứ nhất. Cũng tại các lớp này nghiệm của các bài toán còn lại cũng rất gần với nghiệm của Belov-Scheithauer và tốt hơn hẳn nghiệm của Silvio A. Araujo và đồng sự. GAP GAP Lớp v1 v2 Trung bình Nhỏ nhất Lớn nhất Lớp v1 v2 Trung bình Nhỏ nhất Lớn nhất C1 0.001 0.2 1.18 0.70 1.88 C17 0.15 0.2 0.35 0.14 0.60 C2 0.001 0.3 0.61 0.23 1.04 C18 0.15 0.3 0.25 0.10 0.40 C3 0.001 0.4 0.35 0.10 0.62 C19 0.15 0.4 0.14 0.07 0.27 C4 0.001 0.5 0.17 0.05 0.43 C20 0.15 0.5 0.10 -0.23 0.19 C5 0.001 0.6 0.10 -2.02 0.37 C21 0.15 0.6 0.05 -0.17 0.16 C6 0.001 0.7 0.08 -0.07 0.29 C22 0.15 0.7 -0.07 -2.60 0.15 C7 0.001 0.8 -0.01 -6.00 0.14 C23 0.15 0.8 -0.23 -3.18 0.07 C8 0.001 0.9 0.04 -1.76 0.20 C24 0.15 0.9 -0.32 -2.76 0.10 C9 0.01 0.2 1.14 0.73 2.05 C25 0.25 0.3 -0.96 -5.80 0.48 C10 0.01 0.3 0.59 0.30 1.04 C26 0.25 0.4 0.01 -3.08 0.18 C11 0.01 0.4 0.32 0.10 0.64 C27 0.25 0.5 -0.03 -5.15 0.22 C12 0.01 0.5 0.18 0.06 0.45 C28 0.25 0.6 -0.11 -1.85 0.16 C13 0.01 0.6 0.12 0.02 0.32 C29 0.25 0.7 -0.36 -1.98 0.05 C14 0.01 0.7 -0.02 -5.01 0.41 C30 0.25 0.8 -0.48 -3.45 0.05 C15 0.01 0.8 0.03 -1.22 0.27 C31 0.25 0.9 -0.82 -6.18 0.02 C16 0.01 0.9 -0.14 -5.74 0.15 -0.06 -6.18 2.05 Bảng 2.1 Tổng kết chất lượng nghiệm so với kết quả của Belov -Scheithauer[42] 45 - Tại các lớp còn lại kết quả đạt được cũng rất gần với kết quả của Belov - Scheithauer với độ lệnh nhỏ nhất xấp xỉ 0.01% và độ lệch lớn nhất xấp xỉ 2.05%. Kết quả này tốt hơn hẳn nghiệm của Silvio A. Araujo và đồng sự với các độ lệch tương ứng là 0.17% và 2.37%. Bảng 2.2 trích dẫn kết quả tính toán so sánh của Silvio A. Araujo và đồng sự với kết quả tính của Belov theo [48]. GAP GAP Lớp v2 v2 1500 vòng lặp 3000 vòng lặp Lớp v1 v2 1500 vòng lặp 3000 vòng lặp C1 0.001 0.2 0.175285 0.162389 C17 1.5 0.2 1.660874 1.647265 C2 0.001 0.3 0.338222 0.334772 C18 1.5 0.3 1.204246 1.157270 C3 0.001 0.4 0.501230 0.485200 C19 1.5 0.4 1.157579 1.145566 C4 0.001 0.5 0.785177 0.723195 C20 1.5 0.5 1.481326 1.351702 C5 0.001 0.6 0.986865 0.888302 C21 1.5 0.6 1.431382 1.365700 C6 0.001 0.7 1.330716 1.163220 C22 1.5 0.7 1.684004 1.513348 C7 0.001 0.8 1.843849 1.640934 C23 1.5 0.8 2.254709 1.799656 C8 0.001 0.9 1.362868 1.003978 C24 1.5 0.9 1.904421 1.660200 C9 0.01 0.2 0.221194 0.220295 C25 2.5 0.3 1.213631 1.162781 C10 0.01 0.3 0.366215 0.356794 C26 2.5 0.4 2.375498 2.220528 C11 0.01 0.4 0.553312 0.541084 C27 2.5 0.5 2.164348 2.013975 C12 0.01 0.5 0.779770 0.758054 C28 2.5 0.6 1.535495 1.373492 C13 0.01 0.6 1.044311 0.938163 C29 2.5 0.7 2.044762 1.730710 C14 0.01 0.7 1.317463 1.192335 C30 2.5 0.8 2.138915 0.735370 C15 0.01 0.8 1.869427 1.598234 C31 2.5 0.9 1.553659 1.314085 C16 0.01 0.9 1.283639 1.019884 Trung bình ------------ 1.308529 1.13608 Bảng 2.2 Kết quả tính toán của Silvio A. Araujo và đồng sự - Bảng 2.3 thống kê trên mỗi lớp số lượng bài toán có độ chênh lệch so với nghiệm của Belov và Scheithauer là nhỏ hơn 0%, từ 0% đến 1%, từ 1% đến 2%, từ 2% đến 3% và lớn hơn 3%. Kết quả cho thấy số lượng bài toán có nghiệm tốt hơn (độ lệch âm) là hơn 17%, trong số các bài toán có độ lệch dương, số lượng tập trung nhiều nhất trong khoảng từ 1% đến 2% (chiếm hơn 77%). Chỉ có 1 bài toán nghiệm có độ lệch lớn hơn 2%. 46 Lớp 3% C1 0 21 79 0 0 C2 0 99 1 0 0 C3 0 100 0 0 0 C4 0 100 0 0 0 C5 1 99 0 0 0 C6 5 95 0 0 0 C7 7 93 0 0 0 C8 9 91 0 0 0 C9 0 28 71 1 0 C10 0 98 2 0 0 C11 0 100 0 0 0 C12 0 100 0 0 0 C13 0 100 0 0 0 C14 10 90 0 0 0 C15 12 88 0 0 0 C16 12 88 0 0 0 C17 0 100 0 0 0 C18 0 100 0 0 0 C19 0 100 0 0 0 C20 1 99 0 0 0 C21 12 88 0 0 0 C22 27 73 0 0 0 C23 53 47 0 0 0 C24 57 43 0 0 0 C25 67 33 0 0 0 C26 12 88 0 0 0 C27 13 87 0 0 0 C28 26 74 0 0 0 C29 65 35 0 0 0 C30 74 26 0 0 0 C31 74 26 0 0 0 Tổng 537 2409 153 1 0 Trung bình 17.32% 77.71% 4.94% 0.03% 0.00% Bảng 2.3 Phân bố độ chênh lệch nghiệm so với kết quả của Belov -Scheithauer 47 <0% 0%-1% 1%-2% <0% 0%-1% 1%-2% 17,32% 77,71% 4,94% Hình 2-2 Biểu đồ thống kê độ chênh lệch so với kết quả của Belov -Scheithauer Về thời gian: Thuật toán GA-AF của tác giả được cài đặt chạy trên máy tính Core 2 Duo (1.5GHz/1.5GHz) và 1GB RAM. Bảng 2.4 và bảng 2.5 tổng hợp thời gian tính toán trên 31 lớp bài toán. Thống kê kết quả đạt được trong Luận án cho thấy: - Khoảng 45% tổng số bài toán được giải trong vòng 30 giây. - Thời gian tối thiểu: 1 giây - Thời gian trung bình: 1 phút 6 giây - Thời gian tối đa: 6 phút 39 giây 48 Thời gian Thời gianLớp Trung bình Nhỏ nhất Lớn nhất Lớp Trung bình Nhỏ nhất Lớn nhất C1 00:01:17 00:00:33 00:03:18 C17 00:00:29 00:00:13 00:01:03 C2 00:01:50 00:00:43 00:06:06 C18 00:00:31 00:00:19 00:01:25 C3 00:02:08 00:00:47 00:06:25 C19 00:00:35 00:00:18 00:01:24 C4 00:02:17 00:00:41 00:06:37 C20 00:00:28 00:00:13 00:00:59 C5 00:01:42 00:00:24 00:06:35 C21 00:00:21 00:00:11 00:01:34 C6 00:01:25 00:00:14 00:05:32 C22 00:00:13 00:00:07 00:00:24 C7 00:01:04 00:00:04 00:06:39 C23 00:00:10 00:00:05 00:00:21 C8 00:00:52 00:00:08 00:02:01 C24 00:00:12 00:00:04 00:02:01 C9 00:02:03 00:01:07 00:03:54 C25 00:00:18 00:00:01 00:00:52 C10 00:02:53 00:01:15 00:06:24 C26 00:00:36 00:00:13 00:01:30 C11 00:03:25 00:01:19 00:06:06 C27 00:00:21 00:00:07 00:00:44 C12 00:03:34 00:01:53 00:06:18 C28 00:00:19 00:00:09 00:00:33 C13 00:01:24 00:00:27 00:04:36 C29 00:00:12 00:00:06 00:00:18 C14 00:01:02 00:00:21 00:04:16 C30 00:00:10 00:00:06 00:00:15 C15 00:00:54 00:00:12 00:05:12 C31 00:00:08 00:00:04 00:00:12 C16 00:01:02 00:00:08 00:05:50 00:01:06 00:00:01 00:06:39 Bảng 2.4 Thống kê thời gian tính toán 49 Lớp 5' C1 0 0 44 43 12 1 0 0 C2 0 0 16 48 27 6 1 2 C3 0 0 6 50 23 17 2 2 C4 0 0 6 48 24 12 5 5 C5 1 3 24 46 15 5 2 4 C6 0 9 34 35 16 2 2 2 C7 1 22 39 26 7 1 2 2 C8 7 19 43 29 2 0 0 0 C9 0 0 0 54 38 8 0 0 C10 0 0 0 20 42 26 11 1 C11 0 0 0 10 25 37 20 8 C12 0 0 0 1 26 47 22 4 C13 0 1 27 59 9 3 1 0 C14 2 12 51 28 5 0 2 0 C15 1 37 32 21 8 0 0 1 C16 8 32 26 29 3 0 1 1 C17 0 73 25 2 0 0 0 0 C18 0 53 46 1 0 0 0 0 C19 0 34 65 1 0 0 0 0 C20 0 73 27 0 0 0 0 0 C21 0 94 5 1 0 0 0 0 C22 25 75 0 0 0 0 0 0 C23 56 44 0 0 0 0 0 0 C24 81 19 0 0 0 0 0 0 C25 28 57 15 0 0 0 0 0 C26 0 28 69 3 0 0 0 0 C27 2 93 5 0 0 0 0 0 C28 2 97 1 0 0 0 0 0 C29 22 78 0 0 0 0 0 0 C30 72 28 0 0 0 0 0 0 C31 93 7 0 0 0 0 0 0 Tổng 401 988 606 555 282 165 71 32 Trung bình 13% 32% 20% 18% 9% 5% 2% 1% Bảng 2.5 Thống kê phân bố thời gian tính toán 50 <10s 11s-30s 31s-60s 1'-2' 3'-4' 4'-5' >5' 2'-3' <10s 11s-30s 31s-60s 1'-2' 2'-3' 3'-4' 4'-5' >5' 18% 20% 32% 13% 9% 5% Hình 2-3 Biểu đồ thống kê phân bổ thời gian tính toán Hiệu quả về thời gian thực hiện của thuật toán đề xuất trong Luận án như vậy là chấp nhận được. Tuy nhiên, để cải thiện tốc độ tính toán của thuật toán, chúng tôi đề xuất cài đặt thuật toán dưới dạng một hệ đa tác tử được trình bày trong Chương tiếp theo. 2.5. Kết luận Trong chương 2, tác giả đã chỉ ra tính hiệu quả của việc cắt trên nhiều loại vật tư so với cắt trên một loại vật tư. Mối liên quan ngữ nghĩa của bài toán OneDCSP_M so với bài toán cắt vật tư kinh điển OneDCSP_S được chỉ ra trong các Định lý 2.1, 2.2, 2.3, 2.4. Từ đó bài toán OneDCSP_M được phát biểu lại theo cách mô hình hóa mới. Trên cơ sở mối quan hệ ngữ nghĩa giữa hai bài toán OneDCSP_M và OneDCSP_S, tác giả đề xuất thuật toán giải GA-AF trên cơ sở lai ghép giữa giải thuật di truyền với thuật toán AF giải bài toán OneDCSP_S của Carvalho. Thuật toán đưa ra cách mã hóa nghiệm của bài toán và xây dựng các toán tử di truyền 51 đóng trên phân hoạch của véc tơ kế hoạch sản phẩm. Tính đúng đắn của thuật toán mới được trình bày trong các định lý 2.5 và 2.8. Thuật toán GA-AF được cài đặt, chạy thử nghiệm và so sánh với các kết quả của các tác giả khác được xem như nghiệm ‘tốt nhất’ của bài toán có được cho đến nay trên một số lượng đáng kể các bài toán mẫu. Các so sánh bước đầu cho thấy tính hiệu quả của thuật toán. 52 Chương 3. HỆ THỐNG ĐA TÁC TỬ GMAS-OneDCSP_M GIẢI BÀI TOÁN OneDCSP_M . Từ cuối thế kỷ trước, các nhà nghiên cứu trí tuệ nhân tạo đã đề xuất xây dựng các hệ thống phần mềm cộng tác (collaborating software systems) dựa trên cách tiếp cận “chia để trị”. Trong mỗi hệ thống, một số module nhỏ được phát triển một cách độc lập và kết hợp với nhau để tạo nên toàn bộ hệ thống. Những năm gần đây đã xuất hiện một số hướng nghiên cứu đề cập đến tới các hệ thống phần mềm cộng tác như các hệ thống bảng đen (Blackboard Systems) [16, 19, 31], các hệ thống đa tác tử (Multi-agent Systems), lập trình theo nghĩa rộng (Programming in the large hay Megaprogramming), các hệ thống đối tượng phân tán (Dis tributed-object Systems), công nghệ phần mềm dựa trên thành phần (Component-based software engineering)…. Hiện nay, hướng nghiên cứu về hệ đa tác tử đang thu hút nhiều sự quan tâm nhằm giải quyết các dạng bài toán tối ưu phức tạp khác nhau [8,15,36]. Các tác tử được coi như các modul có một số đặc trưng riêng như tính tự trị (autonomy), tính xã hội (social ability), tính phản ứng (reactivity), tính chủ động (pro-activeness). Các tác tử làm việc cộng tác với nhau để giải bài toán. Những nghiên cứu về các hệ đa tác tử thường nhấn mạnh đến việc giải quyết các vấn đề nảy sinh từ những tính chất đặc trưng của tác tử như vấn đề tương tác (interaction), phối hợp (cooperation), điều khiển phân tán (distributed control)… giữa các tác tử trong hệ thống. Các giải pháp được đưa ra thường mô phỏng các hành vi của đám đông và được gọi chung là các thuật toán dựa trên quần thể (Population-Based Algorithms). Để giải quyết các vấn đề nêu trên, Talukdar và cộng sự đã đề xuất một kiến trúc cơ sở cho phép xây dựng các hệ thống trong đó một nhóm các tác tử tự trị hoạt động một cách song song, không đồng bộ trong khuôn khổ cộng tác với nhau để giải các bài toán tối ưu với tên gọi A-Teams (Asynchronous Teams) [49,50]. Trong kiến trúc cơ sở này, mỗi tác tử sẽ đảm trách một số kỹ nă ng nào đó trong việc giải quyết 53 bài toán toàn cục và hoạt động hoàn toàn độc lập với các tác tử khác. Kiến trúc điển hình của A-Team được cho trong Hình 3.1. Hình 3-1 Kiến trúc của A-Team Một trong những tiện ích được sử dụng rộng rãi để phát triển các hệ đa tác tử là JADE [9,10,54]. JADE được xây dựng dựa hoàn toàn vào các đặc tả của FIPA (Foundation for Intelligent Physical Agents), vì vậy bản thân JADE thường được đồng nhất với các đặc tả này [25]. Kiến trúc A-Team dựa trên nền tảng JADE là công cụ hiệu quả để cài đặt các thuật toán dựa trên quần thể [34]. Trong phần tiếp theo, hệ thống đa tác tử gen GMAS -OneDCSP_M sẽ được xây dựng trên nền tảng JADE với kiến trúc A-Team nhằm nâng cao hiệu quả của thuật toán GA-AF giải bài toán OneDCSP_M. Hệ GMAS-OneDCSP_M thiết kế cho phép sử dụng tối ưu tài nguyên tính toán của hệ thống và chịu được sự cố . Memory A7 A3 A1A5 A6 A8 A4 A2 54 3.1. Yêu cầu của hệ thống GMAS-OneDCSP_M GMAS-OneDCSP_M là hệ thống đa tác tử được thiết kế d ùng để giải quyết các bài toán cắt vật tư một chiều được cài đặt bằng ngôn ngữ Java trên nền JADE và có các đặc trưng sau đây : - Hệ thống có thể giải quyết nhiều bài toán cắt vật tư khác nhau tại cùng một thời điểm. - Quá trình giải từng bài toán có thể được thực hiện trên nhiều máy tính. Người dùng có thể tự do kết nối hoặc loại bỏ một máy tính bất kỳ khỏi hệ thống. Trong trường hợp này, hệ thống tự thích nghi với những thay đổi bằng việc chỉ thị cho các tác tử đang làm việc trong hệ thống di trú tới nơi cho phép. - Hệ thống thực hiện việc giải các bài toán theo mẻ (batch mode). Các bài toán mới sẽ được lưu trữ và giải quyết khi hệ thống có đủ tài nguyên cho phép thực hiện giải bài toán. Các Định lý 2.2, 2.3 và 2.4 phản ánh mối quan hệ ngữ nghĩa giữa bài toán OneDCSP_M(m,M,l,b,L,c) và bài toán ),,,(_ kk blLmSOneDCSP . Việc giải bài toán OneDCSP_M(m,M,l,b,L,c) theo thuật toán GA-AF chính là việc áp dụng giải thuật di truyền trên không gian tìm kiếm được tạo thành từ các tổ hợp nghiệm của các bài toán ),,,(_ kk blLmSOneDCSP với các bk thỏa mãn ràng buộc bb M k k  1 . Từ quan sát này, chúng ta có thể xây dựng một hệ thống đa tác tử di động theo kiến trúc A - Team để giải bài toán OneDCSP_M(m,M,l,b,L,c) với hai kiểu tác tử chính. Kiểu tác tử đầu tiên thực hiện thuật toán GA-AF và đóng vai trò khởi tạo, quản lý, lựa chọn nghiệm của bài toán OneDCSP_M(m,M,l,b,L,c) trên cơ sở nghiệm của các bài toán thành phần ),,,(_ kk blLmSOneDCSP . Kiểu tác tử thứ hai nhận nhiệm vụ giải bài toán ),,,(_ kk blLmSOneDCSP bằng thuật toán AF. Ngoài ra, hệ thống cũng bao gồm một số tác tử đặc biệt cung cấp các dịnh vụ khác như quản lý tài nguyên, quản 55 lý và báo cáo công việc... Các tác tử hoạt động phân tán, song song, không đồng bộ và có thể di trú một cách linh hoạt phụ thuộc vào tài nguyên được cấp phát. Việc tương tác giữa người dùng với hệ thống trong quá trình giải bài toán được thể hiện bằng biểu đồ trong Hình 3.2. Determine instances and other paramenters Manage resources Search solution for the given instances Report solution Delete resources > Add resources > User > >> Hình 3-2 Biểu đồ tương tác giữa người dùng và hệ thống GMAS-OneDCSP_M 3.2. Thiết kế hệ thống GMAS-OneDCSP_M 3.2.1. Kiến trúc hệ thống GMAS-OneDCSP_M Kiến trúc của hệ thống được xây dựng dựa trên JADE platform như minh họa trong hình 3.3. Mỗi platform bao gồm nhiều container được cài đặt phân tán trên mạng. Các tác tử nằm trên các container, trong đó container là tiến trình Java, cung cấp môi trường chạy JADE và tất cả các dịch vụ cần thiết cho việc lưu trú (hosting) và thực thi các tác tử. Main container là một container đặc biệt được khởi tạo đầu tiên khi một platform được thiết lập. Tất cả các container khác đều phải đăng ký với main container. GMAS-OneDCSP_M 56 Hình 3-3 Kiến trúc hệ thống GMAS-OneDCSP_M Main container có nhiệm vụ: - Quản lý Bảng Container (Container Table-CT), nơi đăng ký các tham chiếu đối tượng và địa chỉ của tất cả các container trong platform. - Quản lý Bảng mô tả tác tử toàn cục (Global Agent Descriptor Table- GADT), chứa thông tin của tất cả các tác tử có mặt trong platform cùng với trạng thái hiện thời và vị trí của các tác tử. JAVA JAVA LADT Main container GADT CT DFAMS Task Manager Resource Manager OneDCSP_M Solver OneDCSP_S Solver JAVA LADT Container-2 GADT cache LADT Container-1 GADT cache OneDCSP_S SolverOneDCSP_SSolver PLATFORM IMTP IMTP 57 - Hosting hai tác tử đặc biệt là AMS có nhiệm vụ quản lý tác tử, cung cấp dịch vụ trang trắng (white page service), và tác tử DF cung cấp dịch vụ trang vàng (yellow page service) của platform. Trên mỗi container đều có Bảng mô tả tác tử địa phương (Local Agent Descriptor Table-LADT). Các container khác ngoài main container còn chứa thêm Bảng lưu trữ mô tả tác tử toàn cục (GADT cache) phục vụ cho việc tìm kiếm nơi nhận các thông điệp. Ngoài hai tác tử ngầm định là AMS và DF, Main container của hệ thống GMAS- OneDCSP_M còn chứa: - Tác tử TaskManager có nhiệm vụ khởi tạo, quản lý trạng thái của các bài toán và trả kết quả cho người dùng khi bài toán được giải xong . - Tác tử ResourceManager có nhiệm vụ quản lý platform. - Các tác tử OneDCSP_M-Solver Mỗi bài toán OneDCSP_M sẽ do một tác tử OneDCSP_M-Solver chịu trách nhiệm xử lý. Tác tử này phối hợp với các tác tử OneDCSP_S-Solver thực hiện thuật toán GA-AF để giải các 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ô. - Các tác tử OneDCSP_S-Solver thực hiện giải thuật AF để giải bài toán cắt vật tư một chiều với một loại vật liệu thô. Tập các tác tử OneDCSP_S- Solver được sử dụng chung và tham gia giải quyết mọi bài toán được khởi tạo trong bộ nhớ. Các container khác (Container-1, Container-2…) không phải là Main container chứa các tác tử OneDCSP_S-Solver khi hệ thống có yêu cầu giải bài toán OneDCSP_S. Các tác tử của hệ thống được phân bố động trên các nút tính toán của mạng LAN và hoạt động hoàn toàn độc lập với nhau theo cơ chế không đồng bộ. Số lượng các 58 tác tử của hai loại OneDCSP_M-Solver và OneDCSP_S-Solver được sinh ra phụ thuộc số lượng bài toán cần giải quyết và tài nguyên của hệ thống. 3.2.2. Thiết kế chi tiết hệ thống GMAS-OneDCSP_M Chức năng chính của hệ thống GMAS -OneDCSP_M là tổ chức và thực hiện việc tìm kiếm nghiệm cho 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ô với các bước như sau: Đối với từng bài toán cụ thể - Tạo sinh quần thể nghiệm khởi đầu và lưu chúng trong bộ nhớ chung (common memory) - Cải thiện chất lượng quần thể nghiệm bằng các tác tử có nhiệm vụ giải các bài toán ),,,,,(_ cLblMmMOneDCSP , ),,,(_ kk blLmSOneDCSP và lưu trữ quần thể nghiệm đã được cải thiện vào bộ nhớ chung. Quá trình cải thiện chất lượng này lặp lại cho tới khi điều kiện d ừng được thỏa mãn. 3.2.2.1. Cấu trúc bộ nhớ chung của hệ thống GMAS-OneDCSP_M Trong hệ thống, việc lưu trữ thông tin trong bộ nhớ chung được tổ chức như sau. Mỗi bài toán cụ thể được xác định bởi một định danh duy nhất do người dùng đặt ra và được cấp phát một vùng nhớ trong bộ nhớ chung có cấu trúc gồm 3 miền. Miền đầu tiên, Par, chứa các tham số đặc trưng của bài toán: m, M, l, b, L, c. Miền thứ hai, Feasible Solution – FS, chứa quần thể nghiệm chấp nhận được gồm K nghiệm (K phân hoạch nào đó của véc tơ b, với K là kích thước quần thể nghiệm trong GA-AF) của bài toán ),,,,,(_ cLblMmMOneDCSP . Mỗi nghiệm chấp nhận được có cấu trúc bao gồm một biến trạng thái nghiệm, một phân hoạch của véc tơ kế hoạch b, một véc tơ trạng thái của các bài toán ),,,(_ kk blLmSOneDCSP tương ứng với từng lớp của phân hoạch, các véc tơ nghiệm tối ưu x và các ma trận phương án cắt tương ứng của từng bài toán ),,,(_ kk blLmSOneDCSP . Mỗi biến trạng thái có thể nhận 3 giá trị: chưa được xử lý (Np), đang xử lý (P) và hoàn thành 59 (F) tương ứng với việc bài toán chưa được xem xét, bài toán đang được xử lý và bài toán đã được giải quyết xong. Ban đầu tất cả các biến trạng thái đều nhận giá trị Np. Các biến trạng thái có mối quan hệ phân cấp. Biến trạng thái ở mức trên sẽ có giá trị Np nếu tất cả các biến trạng thái ở mức dưới đều có giá trị Np; có giá trị P nếu ít nhất một biến trạng thái ở mức dưới có giá trị P hoặc F và ít nhất một trong các biến còn lại không có giá trị F; khi tất cả các biến trạng thái ở mức dưới có giá trị F thì biến trạng thái trực tiếp ở mức trên sẽ được gán giá tr ị F. Miền thứ ba, Offspring, chứa các nghiệm chấp nhận được của bài toán ),,,,,(_ cLblMmMOneDCSP được sinh ra từ các nghiệm chấp nhận được trong miền FS bằng tác động của các toán tử gen (2.15)-(2.16), (2.23)-(2.26) và (2.29). Ta có thể mô tả phần bộ nhớ chung tương ứng với mỗi bài toán OneDCSP_M trong hình 3.4 sau. Par FS – Feasible Solution Offspring K phân hoạch véc tơ b Các nghiệm sau lai ghép Biến trạng thái 1 Phân hoạch 1 Nghiệm tối ưu x Phương án cắt … … … … Các nghiệm sau đột biến… … … … … … … … … … … … Các nghiệm sau chọn lọc m, M, l, b, L, c Biến trạng thái chung (Np, P, F) Biến trạng thái K Phân hoạch K Nghiệm tối ưu x Phương án cắt … … … … Các tham số đặc trưng của bài toán Quần thể nghiệm chấp nhận được của OneDCSP_M Các nghiệm của OneDCSP_M sinh ra từ FS bằng tác động các toán tử gen Hình 3-4 Cấu trúc bộ nhớ chung tương ứng với mỗi bài toán OneDCSP_M 3.2.2.2. Hoạt động của hệ thống GMAS-OneDCSP_M Hoạt động của hệ thống có thể được mô tả tóm tắt như sau. 60 Khi khởi động hệ thống, người dùng thông qua TaskManager chỉ ra các tài nguyên có thể sử dụng (các nút tính toán trên mạng LAN). TaskManager truyền các thông tin này cho ResourceManager. ResourceManager sẽ khởi tạo platform, tổ chức một bộ nhớ chung, tạo sinh một số bản copy của tác tử OneDCSP_S-Solver (số bản copy phụ thuộc vào độ lớn của các container) đồng thời phân bố chúng trên các container khác nhau. Ban đầu, dữ liệu của bài toán được người dùng soạn thảo dưới định dạng XML như trên và được lưu thành các file trong một folder ở bộ nhớ ngoài. Tại mỗi thời điểm bắt đầu hoạt động của hệ thống, người dùng sẽ cung cấp đường dẫn folder dữ liệu này và tác tử TaskManager sẽ đọc các tham số của từng bài toán, tính toán không gian nhớ cần thiết để lưu trữ dữ liệu của bài toán tại bộ nhớ chung và yêu cầu tác tử ResourceManager cung cấp bộ nhớ có kích thước phù hợp. ResourceManager nhận yêu cầu từ TaskManager, kiểm tra không gian nhớ còn chưa sử dụng của bộ nhớ chung. Nếu không gian nhớ chưa sử dụng của bộ nhớ chung đủ để lưu trữ dữ liệu của bài toán mới, ResourceManager sẽ thông báo hoạt động thành công, và cung cấp địa chỉ đầu của không gian nhớ còn chưa sử dụng cho TaskManager. TaskManager sẽ lưu các dữ liệu của bài toán vào các miền tương ứng và gửi thông báo yêu cầu ResourceManager tạo sinh một bản copy tác tử OneDCSP_M-Solver dành riêng để thực hiện giải bài toán mới bằng việc cung cấp cho tác tử này problemID của bài toán do TaskManager khởi tạo. Trong trường hợp hệ thống đang hoạt động, nếu TaskManager nhận được yêu cầu dừng từ người dùng nó sẽ thay các đổi các biến trạng thái đang có giá trị P của các bài toán ),,,(_ kk blLmSOneDCSP thành giá trị Np và chuyển đổi toàn bộ dữ liệu trong bộ nhớ chung thành định dạng XML như trên và lưu ra thiết bị ngoại vi. Hành vi trên của TaskManager cũng được đặt lịch định kỳ (thời gian do người dùng lựa chọn) nếu không có tác động của người dùng. Cách tổ chức như vậy bảo đảm cho việc hệ thống có thể khôi phục lại trạng thái giải quyết bài toán gần nhất khi có sự cố xảy ra. 61 Trong quá trình hệ thống đang hoạt động, người dùng có thể chỉ thị thêm hoặc bớt tài nguyên. Khi đó TaskManager sẽ yêu cầu Re sourceManager phân bố lại các tác tử đang hoạt động của hệ thống bằng việc chỉ thị cho các tác tử di trú từ một container sang một container khác (các tác tử trong hệ thống là các tác tử di động - Mobile Agent) để bảo đảm hệ thống hoạt động một cách hiệu quả. Khi có thông báo thành công từ tác tử OneDCSP_M-Solver nào đó, TaskManager trả kết quả bài toán tương ứng cho người dùng và thông báo yêu cầu ResourceManager giải phóng miền nhớ trong bộ nhớ chung ứng với bài toán đã được xử lý xong. Phụ thuộc vào không gian nhớ chưa sử dụng trong bộ nhớ chung do mình quản lý, ResourceManager ước lượng khả năng phân phối không gian nhớ cho bài toán mới. Nếu không gian nhớ chưa sử dụng vượt qua giá trị trung bình không gian nhớ của tất cả các bài toán đang lưu trữ trong bộ nhớ chung, ResourceManager gửi thông báo cho TaskManager. Trong trường hợp này, TaskManager kiểm tra folder lưu trữ dữ liệu của người dùng. Nếu có bài toán chưa được khởi động TaskManager sẽ hoạt động như tại thời điểm xuất phát của hệ thống. Việc giải bài toán được thực hiện chủ yếu nhờ hai loạ i tác tử : OneDCSP_S- Solver và OneDCSP_M-Solver. Mỗi tác tử loại OneDCSP_S-Solver có nhiệm vụ giải 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ằng thuật toán AF của Carvalho. Các tác tử này định kỳ theo thời gian duyệt nội dung các miền FS và Offspring của bộ nhớ chung để tìm các thể hiện chưa được xử lý của bài toán ),,,(_ kk blLmSOneDCSP thông qua định danh của bài toán, số thứ tự của nghiệm chấp nhận được, số thứ tự của bài toán ),,,(_ kk blLmSOneDCSP trong thành phần của nghiệm chấp nhận được và giá trị của biến trạng thái gắn với nó. Nếu có bài toán chưa được xử lý trong bộ nhớ chung (giá trị biến trạng thái là Np), OneDCSP_S-Solver sẽ đọc dữ liệu của bài toán, gắn giá trị của biến trạng thái thành P, giải bài t