MỞ ĐẦU Trong quá trình sản xuất ra sản ph m thì việc lập kế hoạch sản xuất là cực kỳ quan trọng, nó ảnh hƣởng trực tiếp tới hiệu suất của hệ thống máy móc và qua đó ảnh hƣởng đến chất lƣợng của toàn bộ quá trình sản xuất. Đặc biệt ngày nay khi mà quy mô sản xuất lớn, việc đƣa ra lịch sản xuất hợp lý càng có ý nghĩa quan trọng, thực tế việc lập kế hoạch sản xuất là không hề đơn giản và không thể chỉ đơn thuần dựa trên kinh nghiệm. Chính vì lý do đó lĩnh vực tối ƣu hóa đã tiến hành nghiên cứu bài toán trình tự xe từ năm 1986 nhằm mục đích số hóa bài toán và xây dựng lời giải trên máy tính nhằm giảm thiểu thời gian sản xuất và đảm bảo đƣợc dung lƣợng làm việc của các trạm sản xuất không tốn quá nhiều chi phí (ràng buộc về dung lƣợng) để mang lại hiệu quả về kinh tế và năng suất. Bài toán đã thu hút đƣợc sự chú ý quan tâm của đông đảo giới chuyên môn và đƣợc đầu tƣ nghiên cứu môt cách thích đáng.
Đây là bài toán NP-khó trong lớp bài toán tối ƣu tổ hợp có nhiều ràng buộc nên chỉ có thể tìm ra lời giải gần đúng trong thời gian đa thức. Trƣớc đây ngƣời ta từng sử dụng các thuật toán xấp xỉ và mô phỏng tự nhiên nhƣ thuật toán di truyền, thuật toán leo đồi, thuật toán tìm kiếm địa phƣơng, … để giải bài toán, gần đây nổi lên một phƣơng pháp mới là phƣơng pháp tối ƣu đàn kiến (Ant Colony Optimization) với kết quả thực nghiệm nổi trội đƣợc đánh giá cao. Tối ƣu hóa đàn kiến (Ant Colony Optimization - ACO) là cách tiếp cận metaheuristic tƣơng đối mới, do Dorigo giới thiệu vào năm 1991 và liên tục đƣợc phát triển cho đến nay. Thành công đầu tiên của các thuật toán ACO là giải quyết bài toán Ngƣời chào hàng nổi tiếng với số đỉnh lên tới hơn 2000 với kết quả thu đƣợc là tốt, hiệu quả của nó đƣợc chứng minh bằng thực nghiệm.
Trƣớc tiên, luận văn đã hệ thống hóa các nội dung lý thuyết và thuật toán liên quan đến vấn đề nghiên cứu: bài toán sắp xếp lập lịch sản xuất xe (gọi tắt là bài toán trình tự xe) và các phƣơng pháp tiếp cận, phƣơng pháp ACO và các phƣơng pháp biến thể mới áp dụng cho bài toán nêu trên. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 Sau đó, luận văn đã sử dụng quy tắc cập nhật mùi do Christin Solon [2] đề xuất để xây dựng thuật toán giải bài toán nêu trên, đó là thuật toán ACO1, ACO2 và kết hợp ACO1+ACO2 (gọi là ACO1+2). Đồng thời tôi cũng sử dụng quy tắc cập nhật mùi do Zhaojun Zhang và Zuren Feng [10] đề xuất trong bái toán ngƣời chào hàng để giải bài toán trình tự xe (CarSP), đó là thuật toán TSIACO. Luận văn đề xuất thuật toán mới TSIACOLS là thuật toán thêm kỹ thuật tìm kiếm địa phƣơng vào giai đoạn 2 của thuật toán TSIACO.
Tôi đã tiến hành cài đặt các thuật toán ACO1+2, TSIACO, TSIACOLS. Sau đó, tôi chạy thực nghiệm và so sánh kết quả giữa các thuật toán trên. Thực nghiệm cho thấy, thuật toán mới TSIACOLS có những ƣu điểm nhất định, số lƣợng vi phạm ràng buộc của các xe đƣa ra trung bình tìm đƣợc thấp hơn so với các thuật toán đã có, tuy thời gian thực hiện lâu hơn khi phải xử lý tìm kiếm địa phƣơng. Thực nghiệm cũng cho thấy, nếu thời gian và số lƣợng vòng lặp hạn chế thì thuật toán cho chất lƣợng lời giải tốt nhất và hội tụ nhanh nhất là ACO1+2, nếu thời gian không hạn chế thì thuật toán cho chất lƣợng lời giải tốt nhất là TSIACOLS.
Nội dung chính trong bài luận văn của tôi gồm 4 chƣơng nhƣ sau: Chƣơng 1:Giới thiệu về bài toán tối ƣu tổ hợp tổng quát và bài toán trình tự xe, các cách tiếp cận giải bài toán. Chƣơng 2:Giới thiệu phƣơng pháp tối ƣu đàn kiến, lịch sử và phát triển.Phƣơng pháp tối ƣu đàn kiến và bài toán ngƣời chào hàng. Chƣơng 3:Trình bày các phƣơng pháp ACO giải bài toán trình tự xe. Chƣơng 4: Tiến hành chạy thực nghiệm chƣơng trình trên bộ dữ liệu chu n, thống kê, đánh giá kết quả thu đƣợc và so sánh giữa các thuật toán ACO.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 CHƢƠNG 1. TỐI ƢU TỔ HỢP VÀ BÀI TOÁN TRÌNH TỰ XE Bài toán trình tự xe thuộc lớp bài toán TƢTH, bài toán này đƣợc đánh giá là phức tạp, yêu cầu ta tìm lời giải tối ƣu theo tiêu trí nào đó kèm theo là các ràng buộc với một loạt các thành phần rời rạc của nó. Tuy nhiên do tính ứng dụng cao nên nó đƣợc sự quan tâm nghiên cứu rất nhiều, là một mô hình điển hình về lý thuyết lập lịch. Đã có nhiều thuật toán đƣợc đƣa ra giải quyết bài toán này, chƣơng này sẽ giới thiệu về bài toán tối ƣu tổ hợp, tìm hiểu về bài toán trình tự xe cũng nhƣ các cách tiếp cận giải bài toán lập trình tự xe.1 Giới thiệu bài toán tối ƣu tổ hợp Chúng ta có thể kể ra các bài toán tiêu biểu của lớp bài toán tối ƣu tổ hợp nhƣ: bài toán giao hàng với chi phỉ nhỏ nhất giữa 2 thành phố, bài toán lập thời khóa biểu, bài toán lập lịch sản xuất… Đây là các bài toán trong thực tế để giải các bài toán dạng này ta cần khái quát hóa chúng để có mô phỏng trên máy tính, tính toán thông qua các mô phỏng đó để tìm ra lời giải tối ƣu.
Chung nhất với mỗi bài toán đều chứa n thành phần { } và hàm mục tiêu. Các bài toán ứng với bộ , trong đó là tập hữu hạn các trạng thái (phƣơn án), là hàm mục tiêu xác định trên và là tập các ràng buộc. Mỗi phƣơng án thỏa mãn các ràng buộc gọi là phƣơng án chấp nhận đƣợc. Mục tiêu của chúng là tìm ra phƣơng án tối ƣu hóa toàn cục đối với hàm mục tiêu , nói cách khác chính là tìm phƣơng án sao cho với mọi.
Đối với bài toán này ta có 3 cách giải quyết đó là: vét cạn, kỹ thuật ăn tham hoặc phƣơng pháp tối ƣu trong lĩnh vực NP-khó. Các thuộc tính của tập và nhƣ sau: 1) Ký hiệu là tập các vectơ trên có độ dài không quá { }.Khi đó, mỗi phƣơng án trong đƣợc xác định nhờ ít nhất mộtvectơ trong. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 2) Tồn tại tập con của và ánh xạ từ lên sao cho không rỗng với mọi ,trong đó tập có thể xây dựng đƣợc từ tập con nào đó của nhờ thủ tục mở rộng tuần tự dƣới đây. 3) Từ ta mở rộng tuần tự thành nhƣ sau: i) Ta xem là mở rộng đƣợc với mọi ii) Giả sử là mở rộng đƣợc và chƣa thuộc .Từ tập ràng buộc , xác định tập con của , sao cho với mọi thì là mở rộng đƣợc.
iii) Áp dụng thủ tục mở rộng từ các phần tử cho phép ta xây dựng đƣợc mọi phần tử của. Nhƣ vậy mỗi bài toán TƢTH đƣợc xem là một bài toán cực trị hàm có biến, trong đó mỗi biến nhận giá tri trong tập hữu hạn kể cả giátrị rỗng. Nói một cách khác là bài toán tìm kiếm trong không gian vectơ độ dài không quá trong đồ thị đầy đủ có các đỉnh có nhãn trong tập .2 Giới thiệu bài toán ngƣời chào hàng ài toán ngƣời chào hàng (Traveling Salesman Problem - TSP) là bài toán TƢTH điển hình, đƣợc nghiên cứu và xem nhƣ là bài toán chu n để đánh giá về hiệu quả lời giải các bài toán TƢTH. ài toán đƣợc phát biểu nhƣ sau: Có một tập gồm thành phố (hoặc điểm tiêu thụ) { } độ dài đường đi trực tiếp từ ci đến cj là di,j.
Một người chào hàng muốn tìm một hành trình ngắn nhất từ nơi ở, đi qua mỗi thành phố đúng một lần để giới thiệu sản phẩm cho khách hàng, sau đó trở về thành phố xuất phát. Có thể thấy đây chính là bài toán tìm chu trình Hamilton với đồ thị đầy đủ có trọng số , với là tập các đỉnh với nhãn là các thành phố trong , là tập các cạnh nối các thành phố tƣơng ứng, độ dài mỗi cạnh chính là độ dài đƣờng đi giữa hai thành phố tƣơng ứng. Trong trƣờng hợp này, tập sẽ là tập LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 các chu trình Hamilton trên , là độ dài của chu trình, là ràng buộc đòi hỏi chu trình là chu trình Hamilton (qua tất cả các đỉnh, mỗi đỉnh đúng một lần), là tập thành phố đƣợc xét, trùng với , tập là vectơ độ dài : với còn là các vectơ trong đó khác đối với mọi cặp. Do đó, lời giải tối ƣu của bài toán TSP là một hoán vị của tập đỉnh { } sao cho hàm độ dài là nhỏ nhất, trong đó đƣợc tính theo (1.3 Các cách tiếp cận giải quyết bài toán tối ƣu tổ hợp Nhƣ phần trên ta đã thấy các bài toán TƢTH có thể đƣa về bài toán tìm kiếm trên đồ thị.
Với những bài toán cỡ nhỏ hoặc những bài toán đặc biệt thì ta hoàn toàn có thể tìm lời giải tối ƣu nhờ tìm kiếm vét cạn cũng nhƣ xây dựng những lời giải đặc thù riêng. Tuy nhiên hầu hết các bài toán trong số đó là bài toán NP-khó, nên với các bài toán cỡ lớn ngƣời ta phải tìm lời giải gần đúng. Các thuật toán gần đúng đối với các bài toán TƢTH khó thƣờng dựa trên 2 kỹ thuật cơ bản: heuristic cấu trúc (construction heuristic) và tìm kiếm địa phƣơng (local search).1 Heuristic cấu trúc Khi không thể tìm lời giải tối ƣu của bài toán với thời gian đa thức, chúng ta hƣớng đến việc tìm lời giải gần đúng. Kỹ thuật hay dùng trong việc tìm lời giải gần đúng là heuristic cấu trúc, lời giải của bài toán đƣợc xây dựng thông qua việc mở rộng tuần tự.
Từ thành phố khởi tạo trong tập , từng bƣớc mở rộng không quay lui, thêm vào các thành phần mới theo phƣơng thức ngẫu nhiên hay tất định dựa trên những quy tắc heuristic. Các quy tắc heuristic này khác nhau tùy vào thuật toán cụ thể đƣợc xây dựng dựa trên toán học kết hợp với kinh nghiệm. Chúng ta có thể khái quát hóa để mô phỏng dƣới dạng thuật toán nhƣ sau: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 Procedure Heuristic cấu trúc; Begin chọn thành phần trong ; While (chƣa xây dựng xong lời giải) do GreedyComponent( ); ; end-while ; Đƣa ra lời giải ; End; Hình 1.1: Phƣơng pháp heuristic cấu trúc Trong đó GreedyComponent( ) có nghĩa là chọn thành phần bổ sung vào theo quy tắc heuristic đã có.