CHƯƠNG 1. TỐI ƯU TỔ HỢP VÀ BÀI TOÁN LẬP LỊCH SẢN XUẤT Bài toán thực tế yêu cầu chúng ta tìm lời giải tối ưu theo tiêu chí nào đó với một loạt các thành phần rời rạc của chúng. Các bài toán loại này luôn có một tập h u hạn các lời giải, chúng ta có thể dùng vét cạn để tìm ra lời giải tối ưu, tuy nhiên khi không gian bài toán lớn thì vét cạn không thể áp dụng. Chương này sẽ giới thiệu về bài toán tối ưu tổ hợp, bài toán lập lịch sản xuất và các cách tiếp cận để giải chúng.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 hai 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 tham lam 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ột vectơ trong. 9 TIEU LUAN MOI download : skknchat@gmail.com 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ự ướ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 .1 Bài toán người giao hàng Bài toán người giao 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. Bà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 10 TIEU LUAN MOI download : skknchat@gmail.com 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.2 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 ự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 cục bộ (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 uát hóa để mô phỏng ưới dạng thuật toán như sau: 11 TIEU LUAN MOI download : skknchat@gmail.com 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 đó Gree yComponent( ) có nghĩa là chọn thành phần bổ sung vào theo quy tắc heuristic đã có. Ký hiệu là kết quả phép toán thêm thành phần vào. Với phương pháp trên ta có thể áp dụng cho bài toán TSP với đồ thị đầy đủ và sử dụng quy tắc heuristic láng giềng gần nhất để chọn đỉnh thêm vào (đỉnh láng giềng nhỏ nhất chưa đi ua để thêm vào). Thuật toán kiểu này có ưu điểm là thời gian tính toán nhanh nhưng lại không có khả năng cải tiến lời giải qua mỗi bước lặp.2 Tìm kiếm cục bộ Kỹ thuật tìm kiếm cục bộ hay còn gọi là tìm kiếm địa phương, thực hiện bằng cách bắt đầu từ một phương án chấp nhận được, lặp lại bước cải tiến lời giải nhờ các thay đổi cục bộ.
Để thực hiện kỹ thuật này, ta cần xác định được cấu trúc lân cận của mỗi phương án (lời giải) đang xét, tức là nh ng phương án chấp nhận được, gần với nó nhất, nhờ thay đổi một số thành phần. Cách thường dùng là lân cận -thay đổi, tức là lân cận bao gồm các phương án chấp nhận được khác với phương án đang xét nhờ thay đổi nhiều nhất thành phần. Lân cận 2-thay đổi của một lời giải trong bài toán TSP bao gồm tất cả các lời giải có thể nhận được từ bằng cách đổi hai cạnh.2 chỉ 12 TIEU LUAN MOI download : skknchat@gmail.com ra một ví dụ một lời giải nhận được bằng cách thay hai cạnh (1,3), (2,6) bằng hai cạnh (2,3), (1,6). Việc cải tiến trong các bước lặp thường chọn theo phương pháp leo đồi dựa theo hai chiến lược: Chiến lược tốt nhất và chiến lược tốt hơn.
Với chiến lược tốt nhất, người ta thực hiện chọn lời giải tốt nhất trong lân cận để làm lời giải cải tiến. Tuy nhiên, khi bài toán cỡ lớn có thể kh ng tìm được lời giải tốt nhất do bị hạn chế về thời gian. Còn với chiến lược tốt hơn, ta chọn phương án đầu tiên trong lân cận, cải thiện được hàm mục tiêu. Nhược điểm của tìm kiếm cục bộ là thường chỉ cho cực trị địa phương.1: Lời giải nhận được thông qua tìm kiếm cục bộ Các kỹ thuật trên thường được kết hợp, tạo thành các hệ lai trong các phương pháp m phỏng tự nhiên dựa trên quần thể, chẳng hạn như thuật toán di truyền (GA) hoặc tối ưu đàn kiến (ACO).3 Phương pháp metaheuristic Phương pháp metaheuristic là một phương pháp heuristic tổng uát được thiết kế, định hướng cho các thuật toán cụ thể (bao gồm cả heuristic cấu trúc và tìm kiếm cục bộ).
Như vậy, một metaheuristic là một lược đồ thuật toán tổng quát ứng dụng cho các bài toán tối ưu khác nhau, với một chút sửa đổi cho phù hợp với từng bài toán. 13 TIEU LUAN MOI download : skknchat@gmail.com Memetic là một m hình theo phương pháp metaheuristic. Trong các thuật toán được thiết kế theo memetic, người ta tạo ra nhiều thế hệ quần thể lời giải chấp nhận được. Trong mỗi quần thể của thế hệ tương ứng, ta chỉ chọn ra một số lời giải (chẳng hạn lời giải tốt nhất) để thực hiện tìm kiếm cục bộ nhằm cải thiện chất lượng.
Quá trình tiến hóa này cho ta tìm được lời giải tốt nhất có thể.3 mô tả một thuật toán memetic sử dụng tính toán tiến hóa (Evolutionary Computing - EC): Proedure Thuật toán memetic-EC; Begin Initialize: Tạo ra quần thể đầu tiên; while điều kiện dừng chưa thỏa mãn do Đánh giá các cá thể trong quần thể; Thực hiện tiến hóa quần thể nhờ các toán tử cho trước; Chọn tập con để cải tiến nhờ thủ tục tìm kiếm cục bộ; for mỗi cá thể trong do Thực hiện tìm kiếm cục bộ; end-for Chọn phần tử tốt nhất; end-while; Đưa ra lời giải tốt nhất; End; Hình 1.2: Thuật toán memetic sử dụng EC Trong ứng dụng thực tế, các thuật toán ACO thường được kết hợp với tìm kiếm cục bộ theo mô hình memetic này.3 Bài toán lập lịch sản xuất Bài toán lập lịch sản xuất JSS thuộc lớp bài toán TƯTH, bài toán này được đánh giá là phức tạp, và là một trong nh ng bài toán khó tính toán nhất cho đến nay. 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 14 TIEU LUAN MOI download : skknchat@gmail.com được đưa ra giải quyết bài toán này, phần này chúng ta sẽ tìm hiểu về bài toán cũng như các cách tiếp cận giải bài toán lập lịch sản xuất.