CHƯƠNG 1 GIỚI THIỆU BÀI TOÁN Chương này phát biểu bài toán cực tiểu hoá độ trễ (MLP), một số ứng dụng của bài toán trong thực tế, cách biểu diễn bài toán trên cơ sở lý thuyết đồ thị, cũng như các giải thuật giải bài toán. Trên cơ sở đó đề xuất việc áp dụng giải thuật di truyền giải bài toán MLP.1 Phát biểu bài toán Bài toán cực tiểu hoá độ trễ (minimum latency problem) cũng được biết như một dạng khác của bài toán người giao hàng, bài toán người bán hàng (Traveling Salesman Problem) [4, 5]. Cho một tập n điểm p 1, …, p n, mỗi điểm đều có cạnh nối với các điểm còn lại. Tìm một đường đi đơn bắt đầu từ một điểm xuất phát đến thăm tất cả các điểm còn lại, sao cho tổng độ trễ của đường đi đó là cực tiểu.
Với l(pi) là độ trễ của điểm thứ i. 1 i Trong đó, độ trễ đường đi là tổng độ trễ của tất cả các điểm có trong đường đi đó và độ trễ của một điểm bất kỳ là tổng độ dài cạnh nối các điểm liền nhau trong đường đi trước khi điểm đó được thăm lần đầu. Một số ứng dụng của bài toán cực tiều hoá độ trễ [2]: • Một máy chủ có một tập các yêu cầu. Máy chủ đó phải lập lịch sao cho cực tiểu hoá thời gian trung bình mà mỗi yêu cầu phải đợi.
• Một ứng dụng khác của bài toán MLP được sử dụng để cực tiểu hoá thời gian tìm kiếm thông tin trên mạng.2 Mô hình đồ thị của bài toán Trong trường hợp tổng quát, coi mỗi điểm của đường đi là một đỉnh của đồ thị đầy đủ có trọng số. Khi đó, đường đi giữa hai điểm là cạnh nối giữa hai đỉnh. Bài toán được phát biểu: Cho một đồ thị đầy đủ có trọng số K n với tập đỉnh V = {v i | i = 1, 2, …, n} và ma trận trọng số đối xứng C = {c ij ≥ 0 | i, j = 1, 2, …, n}. Tìm một đường đi đơn bắt đầu từ một đỉnh xuất phát bất kỳ trong đồ thị đến thăm tất cả các đỉnh còn lại, sao cho độ trễ của đường đi đó là cực tiểu.
Trong đó, độ trễ đường đi là tổng độ trễ của tất cả các đỉnh có trong đường đi đó và độ trễ của một đỉnh bất kỳ là tổng độ dài cạnh nối các đỉnh liền nhau trong đường đi trước khi đỉnh đó được thăm lần đầu. Nếu dãy đỉnh v1 v2…vn là đường đi trên K n, thì độ trễ của đường đi đó được tính n i −1 như sau: ∑∑ c jj+1 i = 2 j=1 Một số ví dụ: • Ví dụ 1 [5]: Xét đồ thị đầy đủ có trọng số K 6 với ma trận trọng số đối xứng 0 12 40 10 9 16 12 0 19 12 70 15 40 19 0 21 60 17 Cij = 10 12 21 0 10 16 9 70 60 10 0 10 10 15 17 16 10 0 Đường đi T = 1 – 5 – 4 – 2 – 3 – 6 có tổng độ trễ nhỏ nhất: (9 + (9 + 10) + (9 + 10 + 12) + (9 + 10 + 12 + 19) + (9 + 10 + 12 + 19 + 17)) = 192. - 17 - • Ví dụ 2 [6]: Trong trường hợp các điểm là các đỉnh của đồ thị đầy đủ trong file dữ liệu Berlin52 Hình 1.1 Đường đi tối ưu MLP trong file dữ liệu Berlin 52 Hình 1.2 Đường đi tối ưu TSP trong file dữ liệu Berlin 52 - 18 - 1.3 Các giải thuật giải bài toán MLP là bài toán NP- khó trong trường hợp tổng quát [1, 2, 3, 4], thậm chí là bài toán NP- khó trong trường hợp các đỉnh của nó là các đỉnh của cây có trọng lượng [7]. Do đó, trong trường hợp tổng quát, không tồn tại một giải thuật có độ phức tạp đa thức để giải bài toán trên.
Nếu giải bằng phương pháp quy hoạch động trong trường hợp tổng quát, độ phức tạp của giải thuật sẽ là hàm số mũ O(n 2 2 n ) [8]. Bang Ye Wu, ZhengNan Huang, Fu-Jie Zhan đề xuất giải thuật kết hợp phương pháp quy hoạch động và phương pháp nhánh cận có độ phức tạp hàm số mũ giải bài toán MLP trong trường hợp các đỉnh của bài toán là các đỉnh của đồ thị vô hướng có trọng lượng [9]. Các giải thuật có độ phức tạp đa thức giải bài toán MLP trong một số trường hợp đặc biệt: • Cây không trọng lượng - độ phức tạp giải thuật trong trường hợp này là đa thức [9]. • Các đỉnh p i nằm trên một đường thẳng - phương pháp giải quy hoạch động - O(n 2 ) [1].
• Các đỉnh p i là các đỉnh của cây có số lượng lá là hằng số (trees of constant number of leaves) [10]. Một số giải thuật giải bài toán MLP trong trường hợp tổng quát: • Các giải thuật gần đúng: Trong trường hợp tổng quát, Blum đưa ra giải thuật gần đúng với hệ số gần đúng là 144, Geomans và Klein-berg đưa ra hệ số gần đúng là 21.55, còn Grag đưa ra hệ số là 10. Aaron Archer, Asaf Levin, David Williamson đề xuất giải thuật gần đúng tốt nhất với hệ số gần đúng sấp sỉ 3. • Một số giải thuật tìm kiếm địa phương: 2-opt, 3-opt, giải thuật luyện kim, giải thuật Tabu Reasearch, một số giải thuật Heuristic.
- 19 - • Giải thuật di truyền: Giải thuật di truyền thường áp dụng tốt cho những bài toán tối ưu hoá tổ hợp như bài toán TSP và MLP. Ngoài ra, có thể kết hợp giải thuật di truyền với giải thuật tìm kiếm địa phương. Trong đó, giải thuật di truyền đóng vai trò trong việc tìm các cực trị, còn giải thuật địa phương sẽ “leo” lên các đỉnh đó để tìm cực đại (cực tiểu) toàn cục.4 Đề xuất hướng áp dụng giải thuật di truyền Giải thuật gần đúng mà Aaron Archer, Asaf Levin, David Williamson đề xuất giải bài toán MLP có hệ số gần đúng nhỏ nhất, song kết quả đạt được vẫn chưa cao. Với mục đích nâng cao chất lượng lời giải, hướng áp dụng giải thuật di truyền giải bài toán MLP là có cơ sở khoa học vì: Thứ nhất, hướng áp dụng giải thuật di truyền giải bài toán người bán hàng (bài toán cũng thuộc lớp bài toán tối ưu tổ hợp) đạt được nhiều kết quả khả quan cả về lý thuyết lẫn thực nghiệm [13, 14].
Điều này chứng tỏ giải thuật di truyền có thể áp dụng tốt cho bài toán MLP. Thứ hai, giải thuật di truyền có nhiều ưu điểm so với các phương pháp tối ưu truyền thống [11, 15]: • Giải thuật di truyền tác động vào mã biểu diễn lời giải thay vì trực tiếp vào lời giải đó. Do đó, miền xác định và miền giá trị của mã biểu diễn là rời rạc. Như vậy, giải thuật di truyền có thể khắc phục được các hạn chế về vấn đề liên tục, về sự tồn tại đạo hàm, … • Các phương pháp tối ưu truyền thống tác động trực tiếp lên từng lời giải thông qua một vài bước lặp để biến đổi thành lời giải khác.
Tuy nhiên, các phương pháp này thường gặp phải vấn đề khi đạt đến trạng thái cực trị địa phương. Trong khi đó, giải thuật di truyền tác động lên quần thể các lời giải. Nhờ vậy, nhược điểm trên được hạn chế thông qua tính đa dạng của các lời giải. - 20 - • Các phương pháp tối ưu truyền thống thường yêu cầu tập các rằng buộc hoặc các giá trị đạo hàm, ….
Trong khi đó, giải thuật di truyền chỉ cần quan tâm đến giá trị hàm mục tiêu. • Các phương pháp truyền thống biến đổi lời giải ban đầu thành lời giải khác thông qua các luật cố định. Do vậy, các phương pháp này chỉ áp dụng cho một lớp các bài toán xác định, mà không thể áp dụng rộng rãi cho các lớp bài toán khác nhau. Ngược lại, giải thuật di truyền sử dụng các luật xác suất để tìm kiếm lời giải; dẫn đến việc tìm kiếm có thể diễn ra theo nhiều hướng khác nhau và hội tụ ở những lời giải gần tối ưu.
Với những ưu điểm này, tác giả tập trung hướng nghiên cứu áp dụng giải thuật di truyền vào giải bài toán MLP.5 Nhiệm vụ của luận văn Từ những yêu cầu đặt ra, nhiệm vụ của luận văn là: • Tìm hiểu và nghiên cứu bài toán cực tiểu hoá độ trễ, các ứng dụng thực tế của bài toán, các giải thuật giải bài toán và kết quả đạt được. Đồng thời nghiên cứu hướng áp dụng giải thuật di truyền giải bài toán MLP. • Nghiên cứu tổng quan về các vấn đề cơ bản của giải thuật di truyền, đồng thời nghiên cứu các phương pháp, kỹ thuật nâng cao kết quả của giải thuật. • Từ các cở sở lý thuyết trên, tiến hành thiết kế giải thuật di truyền giải bài toán MLP.
• Cài đặt mô hình và tiến hành thử nghiệm giải thuật đã đề xuất. - 22 - KẾT LUẬN CHƯƠNG Chương này tập trung giới thiệu bài toán MLP, các ứng dụng thực tế, mô hình đồ thị của bài toán, cũng như các giải thuật giải bài toán. MLP là bài toán NP-khó trong trường hợp tổng quát, kể cả trong trường hợp các đỉnh của nó là các đỉnh của cây có trọng lượng. Ngoài một số trường hợp đặc biệt của bài toán có thể giải được bằng giải thuật có độ phức tạp đa thức; còn trong trường hợp tổng quát không tồn tại những giải thuật tương tự.
Một số hướng giải bài toán MLP trong trường hợp tổng quát: • Giải thuật gần đúng • Giải thuật tìm kiếm địa phương • Giải thuật di truyền Giải thuật di truyền có nhiều ưu điểm so với các phương pháp truyền thống: • Giải thuật di truyền có thể khắc phục các hạn chế về vấn đề liên tục, về sự tồn tại đạo hàm. • Khắc phục hạn chế của giải thuật tìm kiếm địa phương khi giải thuật đạt đến trạng thái cực trị địa phương thông qua tính đa dạng của các cá thể lời giải. • Giải thuật di truyền chỉ quan tâm đến giá trị hàm mục tiêu. Do đó, làm đơn giản hoá quá trình tìm kiếm.
• Thứ tư, giải thuật di truyền có thể áp dụng rộng rãi cho nhiều lớp bài toán khác nhau. Với những ưu điểm có được, đồng thời trên cơ sở nghiên cứu các kết quả lý thuyết và thực nghiệm đạt được khi áp dụng giải thuật di truyền giải bài toán người bán hàng (TSP), tác giả tập trung hướng nghiên cứu áp dụng giải thuật di truyền để giải bài toán MLP.