Giải thuật di truyền bài toán cây steiner (Nguyễn Thanh Tùng) Full

Bài toán cây Steiner trong đồ thị là một bài toán NP-khó trong nhóm các bài toán thiết kế mạng (network designed problem). Bài toán tìm cây Steiner nhỏ nhất trên đồ thị được ứng dụng trong nhiều lĩnh vực thực tế như thiết kế mạng viễn thông, thiết kế vi mạch hay nghiên cứu sự tiến hóa trong sinh học…. Do tầm quan trọng của bài toán, rất nhiều hướng tiếp cận để giải xấp xỉ bài toán đã được đề xuất với mục đích đưa ra lời giải xấp xỉ tốt nhất với thời gian chấp nhận được.

Trong đồ án này trình bày cách giải quyết bài toán theo thuật toán di truyền, đây là một hướng giải quyết khá thành công. Cấu trúc đồ án gồm có năm chương như sau:

• Chương 1. Trình bày lý thuyết cơ sở về đồ thị và bài toán Cây Steiner.

• Chương 2. Trình bày lý thuyết cơ bản về giải thuật di truyền.

• Chương 3. Trình bày thuật toán di truyền giải bài toán Cây Steiner trên đồ thị.

• Chương 4. Các kết quả thực nghiệm.

• Chương 5. Hướng dẫn sử dụng chương trình.

NỘI DUNG:

DANH MỤC HÌNH 4

DANH MỤC BẢNG 6

LỜI MỞ ĐẦU 7

CHƯƠNG 1 8

GIỚI THIỆU BÀI TOÁN 8

1. Một số các khái niệm cơ sở 8

1.1. Đồ thị 8

1.2. Cấu trúc dữ liệu biểu diễn đồ thị 10

2.3 Danh sách kề 12

1.3. Các thuật toán trên đồ thị 13

1.4. Bài toán tối ưu 19

2. Bài toán cây Steiner 22

2.1. Lịch sử bài toán cây Steiner 22

2.2. Lời giải cho bài toán 3 điểm của Fermat 23

2.3. Hệ số Steiner cho trường hợp ba điểm 26

2.4. Mô tả bài toán cây Steiner trên đồ thị 27

2.5. Một số ứng dụng của bài toán 28

2.6. Các thuật toán giải đúng 31

CHƯƠNG 2 34

GIẢI THUẬT DI TRUYỀN 34

1. Giới thiệu và lịch sử phát triển 34

2. Các khái niệm cơ bản 34

2.1. Nhiễm sắc thể (Chromosome) 34

2.2. Quần thể (Population) 34

2.3. Chọn lọc (Selection) 35

2.4. Lai ghép (CrossOver) 35

2.5. Đột biến (Mutation) 35

2.6. Hàm thích nghi (Fitness Function) 35

3. Không gian tìm kiếm (Search Space) 35

4. Mô tả GA 35

5. Các tham số của GA 37

5.1. Kích thước quần thể 37

5.2. Xác suất lai ghép 37

5.3. Xác suất đột biến 37

6. Khởi tạo quần thể ban đầu và chọn lọc cá thể 37

6.1. Khởi tạo quần thể 37

6.2. Hàm tính độ thích nghi 38

6.3. Chọn lọc 38

7. Các toán tử di truyền 40

7.1. Mã hóa nhiễm sắc thể 40

7.2. Lai ghép (CrossOver) 42

7.3. Đột biến (Mutation) 45

8. Chiến lược nạp lại quần thể 46

8.1. Nạp lại hoàn toàn. 46

8.2. Nạp lại ngẫu nhiên 46

8.3. Nạp lại theo mô hình cá thể ưu tú 46

9. Điều kiện dừng của GA 47

10. Đặc điểm và ứng dụng của GA 47

10.1. Đặc điểm 47

10.2. Ứng dụng 48

CHƯƠNG 3 49

GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN CÂY STEINER 49

1. Mã hóa lời giải 49

2. Phương pháp khởi tạo quần thể ban đầu 50

3. Chọn lọc 51

3.1. Chọn lọc xếp hạng tuyến tính 51

3.2. Chọn lọc xếp hạng phi tuyến 51

3.3. Chọn lọc cạnh tranh 51

4. Lai ghép 51

4.1. Lai ghép hai cha mẹ 51

4.2. Lai ghép nhiều cha mẹ 52

5. Đột biến 52

5.1. Đột biến chuẩn 52

5.2. Đột biến đổi chỗ 53

5.3. Phép đột biến đảo đoạn 54

5.4. Phép đột biến thêm đỉnh 54

5.5. Phép đột biến xóa đỉnh 54

6. Tối ưu cây 54

CHƯƠNG 4 56

KẾT QUẢ THỰC NGHIỆM 56

1. Dữ liệu thử nghiệm 56

1.1. Nguồn dữ liệu 56

1.2. Đặc điểm dữ liệu 56

1.3. Định dạng file dữ liệu vào 57

2. Môi trường thử nghiệm 58

3. Cài đặt thử nghiệm 59

3.1. Các tham số 59

3.2.Các hàm chính trong chương trình 62

4. Kết quả thử nghiệm 63

4.1.Các bảng kết quả 63

4.2.So sánh các kết quả 70

CHƯƠNG 5 73

HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH 73

1.Chương trình 73

2. Chạy chương trình giải bài toán cho một file dữ liệu vào 73

3. Chạy chương trình giải bài toán cho nhiều file dữ liệu vào 73

KẾT LUẬN 74

TÀI LIỆU THAM KHẢO 75

LINK 1 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 2 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 3 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 4 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK DOWNLOAD (TÀI LIỆU VIP MEMBER)