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

- 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.
- Tác giả luận văn: Nguyễn Ngọc Quang.
- Nội dung tóm tắt: a) Lý do chọn đề tài Bài toán cây khung truyền thông tối ưu (Optimal Communication Spanning Tree - OCST) là một bài toán có nhiều ứng dụng trong thực tế như trong thiết kế mạng đơn giản, thiết kế mạng/vận tải … Tuy nhiên, OCST là một bài toán thuộc lớp NP-khó nên chưa có một thuật toán chính xác nào có thể tìm được lời giải 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ỉ.
- Ý tưởng của thuật toán di truyền xuất phát từ nguyên lý “chọn lọc tự nhiên” trong học thuyết về sự tiến hóa của Darwin.
- Thuật toán này đã được áp dụng cho các bài toán tối ưu tổ hợp và tối ưu số như: bài toán người du lịch, bài toán cái túi, bài toán vận tải,… Thuật toán di truyền thường mang lại những lời giải tốt trong thời gian chấp nhận được.
- 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ể.
- c) Tóm tắt cô đọng các nội dung chính và đóng góp mới của tác giả Với mục đích tìm hiểu về thuật toán di truyền nói chung và thuật toán di truyền áp dụng cho bài toán OCST nói riêng, luận văn được chia làm 4 phần: phần đầu nói đến các khái niệm liên quan như đồ thị, cây khung, bài toán tối ưu và phát biểu bài toán.
- phần hai, nêu về thuật toán di truyền: từ tổng quan một thuật toán di truyền đến các thao tác, chiến thuật lựa chọn, các thông số cho thuật toán di truyền.
- 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á.
- Trong quá trình nghiên cứu lý thuyết và phân tích, luận văn thực hiện phân tích diễn dịch: tìm hiểu thuật toán di truyền nói chung, tìm hiểu bài toán OCST và áp dụng thuật toán di truyền giải bài toán OCST.
- e) Kết luận Luận văn đã trình bày về bài toán cây khung truyền thông tối ưu.
- 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.
- Nó quyết định không gian của thuật toán di truyền, ảnh hưởng tính cục bộ và tính đa dạng của quần thể.
- 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.
- Nếu giá trị 1P và 2P nhỏ (121, 1PP thì cây thiên kiến trở thành cây khung nhỏ nhất MST.
- Phương pháp mã hóa LB là mã hóa dư thừa đồng nhất và thiên kiến (11P.
- nên cây thiên kiến trở thành cây khung nhỏ nhất MST.
- 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.

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