Chương 1. TỐI ƯU TỔ HỢP Trong các bài toán thực tế cũng như trong lý thuyết, ta thường phải tìm các giá trị cho các biến rời rạc để cực trị hàm mục tiêu nào đó. Các bài toán này thường dễ phát biểu nhưng lại khó giải do chúng thuộc loại tối ưu tổ hợp (TƯTH) NP-khó. Chương này giới thiệu các bài toán tối ưu tổ hợp dưới dạng tổng quát, sẽ sử dụng trong phương pháp tối ưu đàn kiến, các ví dụ minh họa và những vấn đề liên quan cần dùng về sau.
Bài toán tối ưu tổ hợp tổng quát Trong đời sống và trong các hệ thông tin, ta thường phải giải nhiều bài toán tối ưu tổ hợp quan trọng. Chẳng hạn như: tìm đường đi ngắn nhất nối hai điểm trên một đồ thị đã cho, lập kế hoạch phân phối nguồn hàng tới nơi tiêu thụ với chi phí cực tiểu, lập thời khóa biểu cho giáo viên và học sinh thuận lợi nhất, định tuyến cho các gói dữ liệu trong Internet, lập lịch hợp lý cho các hệ thống sản xuất, đối sánh các chuỗi gen trong sinh học phân tử v.v… Về mặt hình thức, mỗi bài toán TƯTH ứng với một bộ ba , trong đó là tập hữu hạn trạng thái (lời giải tiềm năng hay phương án), là hàm mục tiêu xác định trên , còn là tập các ràng buộc (xem [31]). Mỗi phương án thỏa mãn các ràng buộc gọi là phương án (hay lời giải) chấp nhận được. Mục đích của ta là tìm phương án chấp nhận được tối ưu hóa toàn cục hàm mục tiêu.
Chẳng hạn với bài toán cực tiểu thì với mọi phương án chấp nhận được. Đối với mỗi bài toán, đều có thể chỉ ra một tập hữu hạn gồm thành phần { } sao cho mỗi phương án trong đều biễu diễn được nhờ liên kết các thành phần trong nó. Cụ thể hơn, các tập và có các đặc tính sau: 20 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 như ở điểm 2).
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á trị trong tập hữu hạn kể cả giá trị rỗng. Nói một cách khác, nó là bài toán tìm kiếm trong không gian vectơ độ dài không quá trên đồ thị đầy đủ có các đỉnh có nhãn trong tập. 1) Trong bài toán suy diễn haplotype ở chương 4, mỗi lời giải được biễu diễn qua xâu độ dài. Cách biễu diễn này không mâu thuẫn với phát biểu bài toán ở trên vì xâu này ứng với một vectơ có độ dài , trong đó mỗi thành phần của vectơ tương ứng với một ký tự trong các xâu con của xâu kết hợp.
2) Với các bài toán TƯTH có dạng giải tích: Tìm cực trị hàm trong đó mỗi biến nhận giá trị trong tập hữu hạn tương ứng và các biến 21 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com này thỏa mãn các ràng buộc nào đó, thì là tập ⋃ và là các vectơ -chiều , trong đó thành phần nhận giá trị trong tập , là tập còn là tập các vectơ thỏa mãn các ràng buộc. Các ví dụ Để thuận tiện trong các trình bày về sau, mục này giới thiệu hai bài toán TƯTH điển hình: Bài toán người chào hàng (Traveling Salesman Problem - TSP) và bài toán Quy hoạch toàn phương nhị phân không ràng buộc (Unconstrained Binary Quadratic Programming - UBQP). Bài toán người chào hàng Bà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 nhiều và được xem là bài toán chuẩn để đánh giá hiệu quả các lược đồ giải bài toán TƯTH mới (xem [30,31]). 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. Như vậy, bài toán này chính là bài toán tìm chu trình Hamilton có độ dài ngắn nhất trên đồ thị đầy đủ có trọng số , trong đó là tập đỉnh với nhãn là các thành phố trong là các cạnh nối các thành phố tương ứng, độ dài các cạnh chính là độ dài đường đi giữa các thành phố. Trong trường hợp này, tập sẽ là 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 22 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com (trùng với ), 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.1) ở đây là khoảng cách từ đến.
Bài toán TSP được xem là bài toán chuẩn để kiểm định hiệu quả của các phương pháp giải bài toán TƯTH mới với thư viện dữ liệu chuẩn TSPLIB (Reinelt, 1991) tại địa chỉ [77] (Dữ liệu trong nó sẽ được sử dụng trong luận án này). Bài toán này có nhiều ứng dụng thực tiễn, chẳng hạn như: khoan các lỗ trên bảng mạch in (Reinelt, 1994) hay định vị các thiết bị X-quang (Bland & Shallcross, 1989)… [31]. Bài toán quy hoạch toàn phương nhị phân không ràng buộc Bài toán quy hoạch toàn phương nhị phân không ràng buộc (Unconstrained Binary Quadratic Programming - UBQP) được phát biểu như sau: Cho ma trận là ma trận đối xứng kích thước. Cần tìm vectơ nhị phân gồm thành phần, , trong đó hoặc 1 sao cho hàm đạt giá trị lớn nhất: ∑ ∑ (1.2) Trong bài toán này, tập là tập các vectơ nhị phân độ dài , hàm đã xác định như trên, tập ràng buộc là rỗng.
{ }, trùng với , tập là vectơ độ dài : với , còn trùng với. 23 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Các cách tiếp cận Trên đây cho 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ị. Các bài toán này có thể giải đúng hoặc gần đúng.
Với những bài toán cỡ nhỏ hoặc có dạng đặc biệt người ta có thể tìm lời giải tối ưu nhờ tìm kiếm vét cạn hoặc bằng một thuật toán với thời gian đa thức, được xây dựng dựa trên các phân tích toán học. Nhiều bài toán trong số đó là 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 giải gần đúng 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). Heuristic cấu trúc Khi không thể tìm được lời giải tối ưu của bài toán, trong thực hành người ta tìm lời giải gần đúng.
Một kỹ thuật hay được dùng là heuristic cấu trúc, trong đó lời giải của bài toán TƯTH được xây dựng theo cách mở rộng tuần tự. Từ thành phần khởi tạo trong tập ở mục 1.1, từng bước mở rộng không quay lui, bằng cách 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 các quy tắc heuristic đã chọn. Các quy tắc heuristic này thường được xây dựng dựa trên các kết quả phân tích toán học hoặc kinh nghiệm. Phương pháp heuristic cấu trúc tham ăn sau đây cho ta hình dung được cách tiếp cận này (Hình 1.
Procedure Heuristic cấu trúc tham ăn; 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 tham ăn 24 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com trong đó GreedyComponent( ) 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. Dễ dàng hình dung phương pháp này khi áp dụng thuật toán 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 (tức là chọn đỉnh gần nhất chưa đi qua để thêm vào hành trình). Các thuật toán này có ưu điểm là tốn ít thời gian chạy nhưng nhược điểm chính là không cải tiến lời giải được.
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ỉ ra một ví dụ một lời giải nhận được bằng cách thay hai cạnh (2,3), (1,6) bằng hai cạnh (1,3), (2,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 25 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com đượ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.