MỞ ĐẦU Hiện nay, có rất nhiều bài báo, luận văn, luận án hay các công trình nghiên cứu đề cập đến vấn đề giải quyết các bài toán tối ƣu tổ hợp. Đa số các bài toán này thuộc lớp các bài toán NP – khó. Trừ các bài toán cỡ nhỏ có thể tìm lời giải bằng cách tìm kiếm vét cạn, còn lại thì thƣờng không thể tìm đƣợc lời giải tối ƣu. Đối với các bài toán kích thƣớc lớn không có phƣơng pháp giải đúng.
Hiện nay, ngƣời ta thƣờng tìm lời giải gần đúng nhờ các thuật toán mô phỏng tự nhiên nhƣ giải thuật di truyền (Genetic Algorithm - GA), tối ƣu bầy đàn (Particle Swarm Optimization -PSO)… Trong các phƣơng pháp mô phỏng tự nhiên, 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, đƣợc giới thiệu bởi Dorigo năm 1991 đang đƣợc nghiên cứu và ứng dụng rộng rãi cho các bài toán TƢTH - khó. Các thuật toán ACO mô phỏng cách tìm đƣờng đi của các con kiến thực. Trên đƣờng đi, mỗi con kiến thực để lại một vết hoá chất gọi là vết mùi (pheromone trail) và theo vết mùi của các con kiến khác để tìm đƣờng đi. Đƣờng có nồng độ vết mùi càng cao thì càng có nhiều khả năng đƣợc các con kiến chọn.
Nhờ cách giao tiếp gián tiếp này đàn kiến tìm đƣợc đƣờng đi ngắn nhất từ tổ tới nguồn thức ăn. Theo ý tƣởng đó, các thuật toán ACO sử dụng kết hợp thông tin kinh nghiệm (heuristic) và học tăng cƣờng qua các vết mùi của các con kiến nhân tạo để giải các bài toán TƢTH bằng cách đƣa về bài toán tìm đƣờng đi tối ƣu trên đồ thị cấu trúc tƣơng ứng của bài toán. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 2 Bài luận văn này em trình bày phƣơng pháp tối ƣu hóa đàn kiến ACO để giải quyết bài toán tìm tập thống trị nhỏ nhất của một đồ thị vô hƣớng. Em sẽ thử nghiệm trên các đồ thị với kích cỡ khác nhau, mật độ cạnh khác nhau, các chức năng phân phối trọng số trên các đỉnh khác nhau để thấy đƣợc hiệu quả của thuật toán đề xuất so với một số thuật toán đang đƣợc sử dụng.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 3 Chƣơng 1. BÀI TOÁN TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA MỘT ĐỒ THỊ 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, bài toán tìm tập thống trị nhỏ nhất và các cách tiếp cận hiện nay.
Bài toán tối ƣu tổ hợp tổng quát Trong đời sống thực tế ta thƣờng phải giải quyết nhiều bài toán TƢTH 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… Mỗi bài toán TƢTH ứng với một bộ ba ( S , f , ) trong đó: - S là tập hữu hạn trạng thái (lời giải tiềm năng hay phƣơng án); - f là hàm mục tiêu xác định trên ; - là tập các ràng buộc. Mỗi phƣơng án s S thỏa mãn các ràng buộc gọi là phƣơng án trả lời (hay lời giải). Mục đích của ta là tìm phƣơng án chấp nhận đƣợc s* tối ƣu hóa toàn cục hàm mục tiêu , tức là một phƣơng án s* tốt nhất.
Chẳng hạn với bài toán cực tiểu thì ta phải tìm với mọi phƣơng án trả lời. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 4 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 điểm 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. 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. Chú ý: 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 này thỏa mãn các ràng buộc nào đó, thì là tập Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 5 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 . Bài toán tìm tập thống trị nhỏ nhất của một đồ thị (MWDSP) Cho một đồ thị vô hƣớng { } trong đó là tập đỉnh, là tập cạnh của đồ thị.
Với mỗi đỉnh có gắn một trọng số. Một tập thống trị của là một tập sao cho mọi đỉnh thuộc đều kề với ít nhất một đỉnh thuộc tập. Trong các tập thống trị đó, tập thống trị nhỏ nhất là tập thống trị mà tổng trọng số của tất cả các đỉnh thuộc nhỏ nhất. Bài toán tìm tập thống trị nhỏ nhất của đồ thị thuộc lớp bài toán NP- khó và có nhiều ứng dụng trong thực tế.
Đã có nhiều nhà nghiên cứu đƣa ra các phƣơng pháp khác nhau để giải quyết bài toán trên, tuy nhiên các thuật toán này chƣa thực sự hiệu quả. Các cách tiếp cận hiện nay giải quyết bài toán tìm tập thống trị nhỏ nhất của đồ thị 1. Thuật toán tham lam tìm tập phủ đỉnh nhỏ nhất. Trƣớc hết ta xét đồ thị mà chƣa quan tâm đến trọng số của các đỉnh (coi mỗi đỉnh đều có trọng số bằng 1).
Khi đó bài toán trở thành “Tìm tập phủ đỉnh có số lƣợng đỉnh ít nhất”. Để dễ hình dung ta gọi: - Tập các đỉnh đã đƣợc chọn vào làm kết quả là các đỉnh tô màu đen ( ). - Tập các đỉnh không thuộc nhƣng kề với ít nhất một đỉnh thuộc gọi là các đỉnh tô màu xám ( ). Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 6 - Các đỉnh còn lại là các đỉnh chƣa đƣợc phủ gọi là đỉnh tô màu trắng ( ).
Trong tài liệu [4] ngƣời ta đƣa ra ý tƣởng nhƣ sau: Tại mỗi lần lặp ta kết nạp thêm một đỉnh mới thuộc hoặc vào cho đến khi. Việc ƣu tiên chọn đỉnh nào đó kết nạp vào đƣợc xác định bởi giá trị của | |( là những đỉnh trắng kề với ). Thuật toán đƣợc mô ta nhƣ sau: ; ; ; While Do Begin Tìm (| | lớn nhất).1: Thuật toán tham lam tìm tập phủ đỉnh 1. Thuật toán tham lam 1 (Greedy1) Với ý tƣởng trình bày trong tài liệu [12] ngƣời ta biến đổi đồ thị ban đầu thành đồ thị đầy đủ bằng cách thêm các cạnh vào đồ thị.
Khi đó những cạnh ban đầu của đồ thị có trọng số bằng 1 (kí hiệu bằng màu đen), cạnh đƣợc thêm vào có trọng số bằng 0 (kí hiệu bằng màu đỏ). Khi thêm một đỉnh vào tập ta phải cập nhật lại đồ thị, tất cả những cạnh liên thuộc với đỉnh đó sẽ đƣợc tô màu đỏ, những đỉnh kề với nó bằng cạnh màu đen sẽ đƣợc tô thành màu xám. Nhƣ vậy sau khi ta kết nạp đƣợc đỉnh vào thì đồ thị đƣợc biến đổi thành. Khi đó trọng số của cạnh của đồ thị đƣợc biểu diễn nhƣ sau: (1.1) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 7 Lƣu ý chỉ nhận giá trị bằng 0 hoặc bằng 1.
Khi muốn kết nạp một đỉnh nào đó vào thì giải pháp đƣợc chọn để ƣu tiên nhƣ sau: ∑ (1.2) ta thấy thực chất là số lƣợng những đỉnh kề với mà chƣa đƣợc phủ (còn là đỉnh màu trắng). Nhƣ vậy việc chọn một đỉnh để kết nạp vào dựa trên hai tiêu chí: + Số lƣợng đỉnh màu trắng kề với nó càng nhiều càng tốt. + Trọng số của đỉnh đó càng nhỏ càng tốt. Phép cộng 1 vào tử số để đảm bảo đƣợc việc so sánh giữa các đỉnh không còn kết nối nữa, tức là những đỉnh cô lập (khi đó ta sẽ chọn đỉnh nào có trọng số nhỏ hơn).
Theo công thức (1.3) ta thấy rằng khi đồ thị chỉ gồm các đỉnh cô lập thì việc lựa chọn đỉnh nào chỉ phụ thuộc vào trọng số của nó chứ không phân biệt đỉnh đó đã đƣợc phủ hay chƣa. Tức là có thể chọn thêm vào kết quả đỉnh đã đƣợc tô màu xám mà không kề với bất kỳ đỉnh màu trắng nào. A 1 C 6 B 5 Một ví dụ về đồ thị làm cho Greedy1 sai kết quả. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 8 Ta có đỉnh A là đỉnh đã đƣợc chọn, bây giờ xét tiếp đỉnh B và C, ta có: Vì nên theo Greedy1 thì đỉnh tiếp theo đƣợc chọn vào làm kết quả là đỉnh B, sau đó mới chọn đỉnh C.
Kết quả cuối cùng bằng. Ta có thể cải tiến thuật toán này bằng cách thêm vào đồ thị ban đầu những cạnh khuyên với Khi đó nếu một đỉnh màu xám nằm cô lập (đã đƣợc phủ bởi đỉnh khác) thì giá trị của nó sẽ bằng không, trong khi một đỉnh màu trắng nằm cô lập thì giá trị của nó lại bằng 1. Vì vậy ta không cần cộng thêm 1 vào tử số, đồng thời tránh đƣợc sai sót nhƣ trong ví dụ trên (cải tiến này đƣợc minh họa trong chƣơng 3 bằng thuật toán Greedy1_new). Khi đó công thức (1.