- NGUYỄN DUY HIỆP ỨNG DỤNG THUẬT TOÁN LAI GIẢI BÀI TOÁN CÂY KHUNG TRUYỀN THÔNG TỐI ƯU LUẬN VĂN THẠC SĨ KHOA HỌC NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS.
- Email:
[email protected] hoặc
[email protected] Hà Nội, ngày 31 tháng 10 năm 2010 Nguyễn Duy Hiệp Học viên cao học Lớp Công nghệ thông tin Trường Đại học Bách Khoa Hà Nội ~ 2 ~ Lời mở đầu Việc phát triển các thuật toán hiệu quả để giải các bài toán NP – khó (NP – hard) là một vấn đề được quan tâm của nhiều nhà khoa học nghiên cứu về máy tính.
- Bởi vì chúng thường có rất nhiều ứng dụng trong thực tiễn, ví dụ như bài toán người du lịch, bài toán đóng thùng, bài toán cây Steiner, bài toán người đưa thư Trung Hoa.
- Đối với các bài toán này các thuật toán giải chính xác thường có thời gian tính lớn do độ phức tăng rất nhanh khi kích thước bài toán tăng.
- Các phương pháp giải gần đúng thường dùng là: các thuật toán xấp xỉ (approximation schemes), tìm kiếm cục bộ (local search), các phương pháp xác xuất (probabilistic methods), tính toán tiến hóa (evolutionary computation), thuật toán di truyền (genetic algorithm.
- Luận văn này tập trung vào xây dựng thuật toán di truyền lai để giải bài toán cây khung truyền thông tối ưu (Optimal Communication Spanning Tree - OCST).
- Đây là một trong những bài toán trên đồ thị thuộc lớp NP-khó, và có ứng dụng trong nhiều lĩnh vực thực tế như thiết kế vi mạch và các mô hình mạng.
- Thuật toán đề xuất đã được chạy thử nghiệm trên các bộ dữ liệu thường dùng bởi các nhà khoa học để đánh giá các thuật toán giải bài toán OCST, và một số bộ dữ liệu có kích thước lớn được sinh ngẫu nhiên.
- Kết quả thực nghiệm cho thấy thuật toán cho kết quả là tốt hơn so với một số một số thuật toán di truyền tốt nhất hiện biết.
- Luận văn được bố cục như sau : Chƣơng 1 trình bày một số kiến thức cơ sở trong lý thuyết về độ phức tạp tính toán, lớp bài toán NP-khó làm nền tảng cho các chương tiếp theo.
- 3 ~ Chƣơng 2 trình bày tổng quan về bài toán cây khung truyền thông tối ưu và các hướng tiếp cận đã được đề xuất để giải quyết bài toán.
- Chƣơng 3 trình bày sơ đồ của hai giải thuật meta-heuristic gồm giải thuật di truyền và giải thuật tối ưu hóa bày đàn.
- Chƣơng 4 đề xuất giải thuật di truyền lai dựa trên giải thuật di truyền chuẩn kết hợp với giải thuật tối ưu hóa bày đàn để giải bài toán cây khung truyền thông tối ưu.
- Chƣơng 5 trình bày kết quả thực nghiệm của giải thuật di truyền lai đề xuất trong chương 4.
- Giải thuật được thực hiện với sáu loại mã hóa cây khung và hai phương pháp lai ghép nhằm so sánh hiệu quả so với các giải thuật hiện biết.
- Thuật toán và đánh giá độ phức tạp của thuật toán.
- 13 1.1.1 Khái niệm thuật toán.
- Đánh giá thuật toán.
- Độ phức tạp tính toán của bài toán.
- Khái niệm về độ phức tạp của bài toán.
- 24 1.2.2 Các bài toán NP.
- Một số cách tiếp cận giải các bài toán NP-khó.
- Bài toán cây khung truyền thông tối ưu.
- 46 2.2 Một số tính chất của các trường hợp đặc biệt của bài toán OCST.
- 49 2.2.1 Bài toán MRCT.
- Bài toán cây khung truyền thông tối ưu tích nhu cầu (PROCT.
- Bài toán cây khung truyền thông tối ưu tổng nhu cầu (SROCT.
- Bài toán nhiều nguồn (Multiple Source.
- Một số ứng dụng của bài toán cây khung truyền thông.
- Các phương pháp tiếp cận để giải bài toán OCST.
- 57 CHƢƠNG 3 THUẬT TOÁN DI TRUYỀN VÀ TỐI ƢU HÓA BẦY ĐÀN.
- 67 3.2 Giải thuật di truyền.
- 69 3.3 Giải thuật tối ưu hóa bầy đàn.
- 74 CHƢƠNG 4 GIẢI THUẬT DI TRUYỀN LAI GIẢI BÀI TOÁN OCST.
- Sơ đồ giải thuật đề xuất.
- Mã hóa cá thể.
- Mã hóa Prufer.
- Mã hóa CB-TCR.
- Kết quả thực nghiệm.
- Kết quả trên các bộ test chuẩn .
- So sánh với các thuật toán khác.
- So sánh với giải thuật tiến hóa (Sang-moon .
- So sánh với giải thuật di truyền, mô phỏng tôi luyện, tìm kiếm cục bộ (Rothlauf .
- So sánh với giải thuật tối ưu hóa bầy đàn KẾT LUẬN.
- 117 ~ 7 ~ Danh mục hình vẽ Hình 1-1 Minh họa thuật toán.
- 15 Hình 1-2 Minh họa bài toán chọn lịch xem phim.
- 17 Hình 1-3 Phản ví dụ của thuật toán 1.
- 17 Hình 1-4 Phản ví dụ của thuật toán 2.
- 24 Hình 1-11 Mối quan hệ giữa 3 lớp bài toán P, NP và Co-NP.
- 32 Hình 1-13 Minh họa mối quan hệ giữa các lớp bài toán.
- 35 Hình 1-14 Danh sách một số bài toán NP-khó và sơ đồ quy dẫn giữa chúng.
- 44 Hình 2-1 Minh họa cách tính giá cây khung trong bài toán OCST.
- 47 Hình 2-2 Minh họa bài toán SROCT và PROCT.
- 48 Hình 2-3 Các biến thể của bài toán cây khung truyền thông tối ưu tổng quát.
- 50 Hình 2-5 Một cây khung 3-star, trong đó B,C,E là các nút trong và A,D,E,F,G,H,I là các nút lá.
- 51 Hình 2-6 Cây khung 1-star, với B là nút trong và các nút còn lại là nút lá.
- 61 Hình 2-10 Cấu trúc của thuật toán Memetic.
- 64 Hình 3-1 Mô hình một thuật toán tiến hóa.
- 69 Hình 3-3 Sơ đồ chung của thuật toán di truyền.
- 71 Hình 3-4 Bài toán tối ưu có thể có rất nhiều cực trị.
- 73 Hình 3-5 Mô tả giải thuật PSO.
- 76 Hình 3-6 Mô tả giải thuật PSO.
- 78 Hình 4-1 Sơ đồ giải thuật di truyền lai đề xuất.
- 82 Hình 4-2 Giải thuật mã hóa cây khung thành chuỗi Prufer.
- 83 Hình 4-3 Cây khung được mã hóa bởi chuỗi Prufer 2565.
- 84 Hình 4-4 Giải thuật giải mã cây khung từ một chuỗi Prufer.
- 85 Hình 4-5 Giải thuật xây dựng cây khung từ chuỗi NetKeys.
- 87 Hình 4-7 Giải thuật xây dựng cây khung từ một chuỗi CB-TCR.
- 89 Hình 4-9 Cây khung sinh ra từ chuỗi CB-TCR .
- 90 Hình 4-10 Giải thuật Prim.
- 91 Hình 4-11 Cây khung thu được từ mã hóa LNB.
- 106 ~ 9 ~ Hình 5-3 So sánh tốc độ hội tụ của giải thuật với hai loại lai ghép trên bộ Raidl100.
- 106 Hình 5-4 So sánh tốc độ hội tụ của giải thuật trên bộ test NE-RAND-200.
- 107 Hình 5-5 So sánh tốc độ hội tụ của giải thuật trên bộ test E-RAND-200.
- 40 Bảng 2-1 Các bài toán OCT và tỉ lệ xấp xỉ tốt nhất hiện biết của nó.
- 98 Bảng 5-2 Kết quả chạy các bộ test chuẩn sử dụng mã hóa Prufer và CB-TCR ......101 Bảng 5-3 Kết quả chạy các bộ test chuẩn sử dụng mã hóa NetKeys và NB Bảng 5-4 Kết quả chạy trên các bộ test chuẩn sử dụng mã hóa LNB và LB Bảng 5-5 So sánh về độ lệch của kết quả tìm được so với kết quả đã biết Bảng 5-6 So sánh thời gian tìm ra kết quả tốt nhất Bảng 5-7 So sánh số lượng thế hệ tối thiểu để tìm ra kết quả tốt nhất Bảng 5-8 So sánh với một số giải thuật meta-heuristic Bảng 5-9 So sánh với giải thuật tối ưu hóa bầy đàn Danh mục thuật ngữ tiếng Anh STT Thuật ngữ Viết tắt Đề nghị dịch tiếng Việt 1 Approximation scheme Mô hình xấp xỉ 2 Probabilistic method Phương pháp xác xuất 3 Evolutionary computation Tính toán tiến hóa 4 Local search Tìm kiếm cục bộ 5 Genetic algorithm GA Thuật toán di truyền 6 Hybrid GA Thuật toán di truyền lai 7 Bin packing problem BPP Bài toán đóng thùng 8 Relative performance ration Đảm bảo về tỷ số chênh lệch tương đối 9 Absolute performance guarantee Đảm bảo về sai số tuyệt đối 10 Polynomial time approximation schemes PTAS Sơ đồ xấp xỉ trong thời gian đa thức 11 Population Quần thể 12 Chromosomes Nhiễm sắc thể 13 Individual Cá thể 14 Genetic-inspired operators Toán tử di truyền 15 Selection Chọn lọc tự nhiên 16 Crossover Lai ghép 17 Mutation đột biến 18 Inversion Đảo chỗ 19 Fitness Độ thích nghi 20 Object function Hàm mục tiêu ~ 12 ~ 21 Generation Thế hệ 22 Roulette wheel selection Cơ chế lựa chọn theo bánh xe Roulette 23 K-point crossover Lai ghép k-điểm cắt 24 Uniform crossover Lai ghép đồng bộ 25 Order-based crossover Lai ghép theo thứ tự 26 Uniform order-based crossover Lai ghép đồng bộ theo thứ tự 27 Optimal Communication Spanning Tree OCST Cây khung truyền thông tối ưu 28 Minimum Routing Cost Spanning Tree MRCT Cây khung định tuyến tối thiểu 29 Optimal Product Requirement Communication Spanning Tree PROCT Cây khung truyền thông tích nhu cầu 30 Optimal Sum Requirement Communication Spanning Tree SROCT Cây khung truyền thông tổng nhu cầu 31 p-Source OCT p-Source OCT Cây khung truyền thông tối ưu p nguồn 32 Minimum Average Stretch Spanning Tree MAST Cây khung tối thiểu khoảng giãn 33 Particle Swarm Optimization PSO Tối ưu hóa bầy đàn 34 Swarm Intelligence SI Bầy đàn thông minh ~ 13 ~ CHƢƠNG 1 CÁC KHÁI NIỆM CƠ BẢN Chương này trình bày tổng quan về các khái niệm và các thuật ngữ cơ sở được sử dụng trong luận văn.
- Thuật toán và đánh giá độ phức tạp của thuật toán 1.1.1 Khái niệm thuật toán Ngày nay máy tính đã trở thành một công cụ sản xuất quan trọng, một thiết bị không thể thiếu trong bất cứ lĩnh vực nào.
- Do vậy việc nghiên cứu lý thuyết về khoa học máy tính và các vấn đề về giải quyết bài toán bằng máy tính ngày càng quan trọng và được phát triển mạnh mẽ.
- Nhưng cho dù vấn đề là gì đi nữa để giải quyết nó bao giờ cũng vậy, trước hết chúng ta cần phát biểu lại vấn đề đó một cách chính xác dưới dạng các bài toán.
- Dưới dạng một bài toán thì một vấn đề sẽ gồm có đầu vào và đầu ra, trong đó đầu vào mô tả không gian các giá trị có thể có của bài toán và đầu ra là giá trị mong muốn tương ứng với đầu vào đó.
- Ví dụ: bài toán sắp xếp được định nghĩa như sau Đầu vào: một dãy gồm khóa.
- 14 ~ Như vậy dãy đầu vào có thể là dãy số bất kỳ, hoặc có thể là dãy các xâu ký tự, hoặc là dãy các đối tượng… Ở đây chúng ta chỉ đề cập đến việc giải quyết bài toán bằng máy tính.
- Để giải quyết bài toán bằng máy tính trước hết chúng ta phải biểu diễn được bài toán đó trên máy tính, tức là biểu diễn được đầu vào và đầu ra của nó.
- Trong máy tính tất cả các dữ liệu và câu lệnh đều được biểu diễn dưới dạng mã nhị phân (biểu diễn bằng các chuỗi nhị phân gồm bit 1 và 0).
- Một số thực được biểu diễn trong máy tính dưới dạng chuỗi bit nhị phân sử dụng chuẩn IEEE-754.
- Một xâu kí tự được biểu diễn là ghép nối biểu diễn của các kí tự thành phần của xâu đó.
- Một vector được biểu diễn là ghép nối biểu diễn nhị phân (mảng – array) của các thành phần tọa độ của các chiều.
- có thể biểu diễn dưới dạng nhị phân là ghép nối của các xâu biểu diễn nhị phân của các thành phần trong ma trận A và vector b.
- Do đó có thể dùng các xâu nhị phân ~ 15 ~ biểu diễn dãy hệ số.
- và xâu nhị phân biểu diễn là ta có thể tạo thành một biểu diễn hợp lệ cho P(x.
- Đồ thị có thể được biểu diễn bằng ma trận kề, hoặc danh sách kề Các dữ liệu phức hợp được tổ chức dưới dạng tổ hợp cấu trúc của các dữ liệu cơ bản, ví dụ như mảng, bản ghi, cây … Như vậy chúng ta có thể định nghĩa một cách hình thức bài toán tính toán như sau: Định nghĩa 1.1.
- Bài toán tính toán F là ánh xạ từ các xâu nhị phân độ dài hữu hạn vào tập các xâu nhị phân độ dài hữu hạn: F: {0,1.
- Các dữ liệu trong bài toán tổng quát có thể không hữu hạn, tuy nhiên khi đã chuyển vào trong máy tính thì chúng ta phải chuyển nó thành hữu hạn, bởi vì không gian của máy tính là hữu hạn.
- Nói một cách khác các xâu nhị phân biểu diễn bài toán có độ dài là hữu hạn.
- Để giải quyết bài toán (vấn đề trong thực tế) chúng ta phải đề xuất ra một phương án.
- Trong giải quyết bài toán bằng máy tính phương án được gọi là thuật toán (algorithm).
- Một thuật toán để giải quyết bài toán có thể được định nghĩa như sau.
- Thuật toán giải bài toán đặt ra là một thủ tục xác định bao gồm một dãy hữu hạn các bước cần thực hiện để thu được đầu ra cho một đầu vào cho trước của bài toán.
- Thuật toán(Algorithm)Đầu vào(Input)Đầu ra(Output) Hình 1-1 Minh họa thuật toán Thuật toán có những đặc trưng sau đây.
- Có đầu vào (Input): là tập các dữ liệu cần cung cấp cho thuật toán để xử lý.