Thuật toán di truyền giải bài toán cây khung truyền thông tối ưu

- Học viên Nguyễn Ngọc Quang 1 TÓM TẮT LUẬN VĂN THẠC SĨ Đề tài: Thuật toán di truyền giải bài toán cây khung truyền thông tối ưu.
- Ngay từ khi mới được đưa ra vào năm 1974 bởi HU cho đến nay, đã có rất nhiều phương pháp được đề xuất với bài toán này: phương pháp tìm kiếm có hoặc không có heuristic, thuật toán leo đồi… Một trong các hướng tiếp cận đang được quan tâm là sử dụng thuật toán di truyền (Genetic Algorithm – GA) để tìm lời giải xấp xỉ.
- Thuật toán này cho kết quả khá khả quan, và đối với bài toán OCST, thuật toán này cũng cho lời giải tương đối tốt so với một số phương pháp khác.
- Do đó, tôi lựa chọn luận văn với đề tài: Thuật toán di truyền giải bài toán cây khung truyền thông tối ưu.
- Luận văn tập trung nghiên cứu mô hình thuật toán di truyền và áp dụng thuật toán di truyền giải bài toán OCST.
- Bên cạnh đó, luận văn trình bày một sồ phương pháp mã hóa cá thể cụ thể của giải thuật di truyền khi áp dụng cho bài toán OCST.
- Thông qua kết 2 quả thực nghiệm, luận văn đưa ra đánh giá về việc áp dụng thuật toán di truyền giải bài toán OCST và hiệu quả của các phương pháp mã hóa cá thể.
- phần ba, nêu các phương pháp mã hoá cây khung để áp dụng thuật toán di truyền: đó là phương pháp mã hoá Prufer, mã hóa vectơ đặc trưng, mã hóa thiên kiến cạnh, mã hóa thiên kiến nút, mã hóa thiên kiến cạnh và nút, mã hóa NetKey, mã hóa tập cạnh.
- Mỗi phương pháp đều có nhận xét về ưu, nhược điểm của cách mã hoá đó.
- Trên cơ sở lý thuyết và kết quả thực nghiệm, luận văn đã chỉ ra sự ảnh hưởng của các phương pháp mã hóa đối với sự hội tụ, đa dạng và thiên kiến của thuật toán di truyền.
- d) Phương pháp nghiên cứu.
- Luận văn sử dụng phương pháp nghiên cứu: tìm hiểu lý thuyết, phân tích, xây dựng thực nghiệm và rút ra đánh giá.
- các hướng tiếp cận giải quyết bài toán và đi sâu nghiên cứu sử dụng thuật toán di truyền để giải quyết bài toán cây khung truyền thông tối ưu.
- Trong các toán tử di truyền, phương pháp mã hóa cá thể ảnh hưởng tính hiệu quả của thuật toán di truyền.
- Luận văn đã trình bày hai phương pháp mã hóa cây: biểu diễn trực tiếp cây và biểu diễn gián tiếp cây.
- Các phương pháp biểu diễn gián tiếp cây trong luận văn bao gồm: mã hóa vectơ đặc trưng, mã hóa số Prufer, mã hóa thiên kiến cạnh, mã hóa thiên kiến nút, mã 3 hóa thiên kiến cạnh và nút và mã hóa NetKey.
- phương pháp mã hóa tập cạnh là phương pháp biểu diễn trực tiếp tập cạnh của cây khung.
- Các phương pháp mã hóa gián tiếp cây khung sử dụng hai không gian: không gian kiểu gen (không gian cá thể mã hóa), không gian kiểu hình (không gian cây khung) và cách ánh xạ giữa hai không gian này.
- Trong trường hợp không gian kiểu gen lớn hơn không gian kiểu hình thì đó là các phương pháp mã hóa dư thừa (mã hóa CV, mã hóa LB, mã hóa LNB, mã hóa NetKey).
- nếu không gian kiểu gen bằng kiểu hình thì sẽ không tạo ra sự dư thừa như mã hóa Prufer.
- Phương pháp mã hóa trực tiếp chỉ có một không gian cây khung nên không cần sự ánh xạ và không tạo ra sự dư thừa trong mã hóa.
- Thông qua lý thuyết và kết quả thực nghiệm cho thấy tính chất của các phương pháp mã hóa cá thể như sau.
- Giải thuật di truyền giải bài toán OCST với các mã hóa cá thể: mã hóa CV, mã hóa Prufer, mã hóa NB, mã hóa LB, mã hóa LNB, mã hóa NetKey cho kết quả tương đối tốt so với phương pháp khác giải bài toán OCST.
- GA sử dụng mã hóa Prufer không dư thừa nhưng có tính hội tụ thấp.
- Phương pháp mã hóa véctơ đặc trưng là mã hóa dư thừa và thiên kiến nên không đảm bảo tính hội tụ của GA.
- Phương pháp mã hóa LNB phụ thuộc vào giá trị 1P và 2P.
- Phương pháp mã hóa LB là mã hóa dư thừa đồng nhất và thiên kiến (11P.
- Phương pháp Mã hóa NB là mã hóa dư thừa đồng nhất và thiên kiến.
- Mặt khác, mã hóa NB không thể biểu diễn tất cả các cây khung mà chỉ biểu diễn một phần nhỏ của không gian lời giải và có thiên kiến trở thành cây hình sao hoặc cây khung nhỏ nhất MST.
- 4  Phương pháp mã hóa NetKey là mã hóa dư thừa đồng nhất, không thiên kiến nên các cá thể của GA sử dụng mã hóa NetKey không phụ thuộc vào cấu trúc của cây khung tối ưu.
- Phương pháp mã hóa EgdeSet không heuristic là mã hóa không dư thừa, không thiên kiến và có tính cục bộ cao nên các thao tác di truyền có xu hướng tạo ra các cá thể giống nhau hoặc gần giống nhau.
- Đối với các bộ dữ liệu thực nghiệm được đề cập trong luận văn thì GA sử dụng mã hóa NetKey và mã hóa LNB cho kết quả khá tốt so với các các phương pháp mã hóa còn lại.
- 14 1.2 Bài toán tối ưu.
- Các lớp bài toán tối ưu.
- Bài toán cây khung truyền thông tối ưu.
- 24 1.4.1 Phát biểu bài toán cây khung truyền thông tối ưu.
- 30 2.1.2 Các phương pháp khác.
- 31 2.2 Các thành phần chính trong giải thuật di truyền.
- 35 2.2.4 Các toán tử di truyền.
- 35 2.2.5 Các thông số khác của giải thuật di truyền.
- 36 2.2.6 Giải thuật di truyền đơn giản.
- 38 2.2.7 Không gian tìm kiếm của giải thuật di truyền.
- 38 2.2.8 Đặc điểm của giải thuật di truyền.
- 39 2.2.9 Ứng dụng của giải thuật di truyền.
- 46 2.5 Các phương pháp lai ghép NST.
- 46 2.5.1 Lai ghép cho NST mã hóa nhị phân.
- 47 2.5.2 Lai ghép NST theo mã hóa hoán vị.
- 48 2.6 Các phương pháp đột biến NST.
- 49 2.6.1 Đột biến theo NST mã hóa nhị phân.
- 49 2.6.2 Đột biến theo NST mã hóa hoán vị.
- THUẬT TOÁN DI TRUYỀN GIẢI.
- 53 3.1 Các phương pháp mã hóa cây.
- 53 3.1.1 Phương pháp mã hoá Prufer.
- 54 3.1.2 Phương pháp mã hoá vectơ đặc trưng (Characteristic Vector Encoding – CV.
- 62 3 3.1.3 Phương pháp mã hoá thiên kiến cạnh và nút (Link and Node Biased - LNB.
- 64 3.1.4 Phương pháp mã hoá NetKey (Network Random Key Encoding – NetKey.
- 70 3.1.5 Phương pháp mã hoá tập cạnh.
- 74 3.2 Giải thuật di truyền sử dụng mã hóa số Prufer.
- 80 3.2.4 Mô tả giải thuật di truyền theo phương pháp mã hóa số Prufer.
- 80 3.3 Giải thuật di truyền sử dụng mã hóa vectơ đặc trưng.
- 81 3.3.4 Mô tả giải thuật di truyền theo phương pháp mã hóa vectơ đặc trưng.
- 82 3.4 Giải thuật di truyền sử dụng mã hóa thiên kiến cạnh và nút.
- 83 3.4.4 Mô tả giải thuật di truyền theo mã hóa thiên kiến cạnh và nút.
- 83 3.5 Giải thuật di truyền sử dụng mã hóa NetKey.
- 84 3.5.4 Mô tả giải thuật di truyền theo mã hóa NetKey.
- 84 3.6 Giải thuật di truyền sử dụng mã hóa tập cạnh.
- 85 3.6.4 Mô tả giải thuật di truyền theo mã hóa tập cạnh.
- 86 3.7 So sánh các phương pháp mã hóa cá thể.
- 109 5 DANH SÁCH CÁC KÝ HIỆU, CHỮ VIẾT TẮT Chữ viết tắt Viết đầy đủ Ý nghĩa CV Characteristic Vector Encoding Mã hóa vectơ đặc trưng EA Evolutionary Algorithm Giải thuật tiến hóa EC Evolutionary Computation Tính toán tiến hóa GA Genetic Algorithm Giải thuật di truyền LB Link-Biased Encoding Mã hóa thiên kiến cạnh LNB Link-Node Biased Encoding Mã hóa thiên kiến cạnh và nút MRCT Minimum Routing-Cost Spanning Tree Cây khung giá định tuyến cực tiểu NB Node-Biased Encoding Mã hóa thiên kiến nút NetKey Network Random Key Encoding Mã hóa khóa ngẫu nhiên NST Nhiễm Sắc Thể OCST Optimal Communication Spanning Tree Cây khung truyền thông tối ưu PROCT Product-Requirement Optimal Communication Spanning Tree Cây khung truyền thông với hàm yêu cầu tích tối ưu SROCT Sum-Requirement Communication Optimal Spanning Tree Cây khung truyền thông với hàm yêu cầu tổng tối ưu 6 DANH MỤC HÌNH Hình 1.1.
- Bài toán cir-SAT.
- Cây mã hóa biểu thức a * ((b – 9.
- Lai ghép một điểm cắt mã hóa nhị phân.
- Lai ghép hai điểm cắt mã hóa nhị phân.
- Lai ghép đồng nhất mã hóa nhị phân.
- Lai ghép số học mã hóa nhị phân.
- 51 Hình 2.10.
- 51 Hình 2.11.
- Minh họa tính cục bộ thấp của mã hóa Prufer.
- Cây khung, mã hóa Prufer, mã hóa nhị phân tương ứng.
- Tỷ lệ xác suất khoảng cách thay đổi giữa cá thể cha mẹ và cá thể con được mã hóa nhị phân khi thực hiện thay đổi một cạnh bất kỳ.
- Tỷ lệ xác suất khoảng cách thay đổi giữa cá thể cha mẹ và cá thể con được mã hóa Prufer khi thực hiện thay đổi một cạnh bất kỳ.
- Tỷ lệ xác suất khoảng cách thay đổi giữa cá thể cha mẹ và cá thể con khi thực hiện thay đổi một thành phần bất kỳ trong mã hóa nhị phân.
- Tỷ lệ xác suất khoảng cách thay đổi giữa cá thể cha mẹ và cá thể con khi thực hiện thay đổi một thành phần bất kỳ trong mã hóa số Prufer.
- Mã hóa vectơ đặc trưng của cây khung trong hình 3.8.
- 63 Hình 3.10.
- Cây khung tìm thấy trong trường hợp mã hóa thiên kiến cạnh.
- 66 Hình 3.11.
- Cây khung với các cạnh được đánh thứ tự tương ứng trong mã hóa thiên kiến cạnh.
- 67 Hình 3.12.
- 69 Hình 3.13.
- 73 Hình 3.14.
- Cây thu được theo mã hoá NetKey trong hình 3.13.
- 73 Hình 3.15.
- Minh họa lai ghép cá thể của phương pháp mã hóa tập cạnh.
- 76 Hình 3.16.Minh họa đột biến sử dụng mã hóa tập cạnh.
- 76 Hình 3.17.
- 79 Hình 3.18.
- Biểu đồ giá trị tốt nhất đạt được của các phương pháp mã hóa.
- Biểu đồ giá trị trung bình đạt được của các phương pháp mã hóa.
- Biểu đồ giá trị GAP qua các thế hệ của các phương pháp mã hóa

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt