Luận văn: Giải thuật Meta Heuristic cho bài toán thiết kế mạng chịu lỗi

Luận văn về giải thuật meta heuristic ứng dụng trong thiết kế mạng chịu lỗi. Nghiên cứu các phương pháp tối ưu hóa để xây dựng mạng lưới mạnh mẽ, ổn định.

• Tác giả: Đào Thanh Tùng
• Người hướng dẫn: TS. Huỳnh Thị Thanh Bình
• Trường học: Trường Đại học Bách Khoa Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Giải Thuật Meta-Heuristic Để Giải Quyết Bài Toán Thiết Kế Mạng Chịu Lỗi
• Loại tài liệu: Luận văn thạc sỹ kỹ thuật công nghệ thông tin
• Năm xuất bản: 2013
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
• MỞ ĐẦU
• 1. CHƯƠNG 1: CƠ SỞ LÝ THUYẾT
• 1.1. Một số khái niệm cơ bản về MẠNG
• 1.2. Công nghệ ghép kênh theo bước sóng(WDIM)
• 1.3. Mô hình mạng IP-over-W1M
• 1.4. Mạng chịu lỗi
• 1.5. Các khái niệm cơ bản về đồ thị
• 1.5.1. Định nghĩa đồ thị
• 1.5.2. Đồ thị con
• 1.5.3. Đường đi trong đồ thị
• 1.6. Lý thuyết về độ phức tạp thuật toán
• 1.6.1. Một số khái niệm
• 1.6.2. Các ký hiệu tiệm cận
• 1.6.3. Độ phức tạp tính toán của bài toán
• 1.6.4. Lớp bài toán NP-khó
• 1.7. Một số khái niệm cơ bản
• 1.8. Lớp bài toán P, NP, và co-NP
• 1.8.1. Khái niệm quy dẫn
• 1.9. Lớp bài toán đầy đủ và NP-khó
• 2. CHƯƠNG 2: BÀI TOÁN THIẾT KẾ MẠNG QUANG CHỊU LỖI ĐA TẦNG
• 2.1. Phát biểu bài toán
• 2.2. Các ứng dụng của bài toán
• 2.3. Các nghiên cứu liên quan
• 3. CHƯƠNG 3: GIẢI THUẬT DI TRUYỀN VÀ DI TRUYỀN SONG SONG
• 3.1. Giới thiệu về giải thuật di truyền
• 3.2. Các khái niệm cơ bản trong giải thuật di truyền
• 3.2.1. Cá thể nhiễm sắc thể
• 3.2.2. Hàm mục tiêu
• 3.3. Đột biến và lai ghép. Chọn lọc tự nhiên
• 3.4. Mô hình giải thuật di truyền
• 3.5. Các thành phần chính của giải thuật di truyền
• 3.6. Giải thuật di truyền song song
• 4. CHƯƠNG 4: GIẢI THUẬT DI TRUYỀN SONG SÓNG GIẢI BÀI TOÁN THIẾT KẾ MẠNG QUANG CHỊU LỖI ĐA TẦNG
• 4.1. Hàm thích nghi
• 4.1.1. Khởi tạo nhiễm sắc thể
• 4.1.2. Khởi tạo quần thể ban đầu
• 4.2. Lựa chọn cá thể lai ghép
• 4.2.1. Lai ghép trao dổi nhiễm sắc thể
• 4.3. Lai ghép trao đôi gen
• 4.4. Đột biến biến đổi gen
• 4.5. Đột biến thay thế một nhiễm sắc thể
• 4.6. Đột biến tái tạo cá thể - loại 1
• 4.7. Đột biến tải tạo cá thể - loại 2
• 4.8. Đấu tranh sinh tồn
• 4.9. Song song hóa thuật toán
• 5. CHƯƠNG 5: KẾT QUẢ THỬ NGHIỆM VÀ ĐÁNH GIÁ
• 5.1. Dữ liệu thử nghiệm
• 5.1.1. Phương pháp xây dựng các bộ dữ liệu
• 5.1.2. Các bộ dữ liệu thử nghiệm
• 5.1.3. Môi trường thứ nghiệm
• 5.2. Tham số thực nghiệm
• 5.3. Kết quả thử nghiệm và so sánh
• 5.3.1. Bảng thống kê kết quả
• 6. CHƯƠNG 6: BÀN LUẬN
• 6.1. Các kết quả đạt được
• 6.2. Hướng phát triển của đề tài
• DANH MỤC TÀI LIỆU THAM KHẢO
• PHỤ LỤC

Tóm tắt

I. Giới Thiệu Tổng Quan Về Giải Thuật Meta Heuristic 55 ký tự

Bài toán thiết kế mạng chịu lỗi là một vấn đề phức tạp, đặc biệt khi mạng ngày càng lớn và yêu cầu về độ tin cậy ngày càng cao. Các phương pháp truyền thống thường gặp khó khăn trong việc tìm kiếm giải pháp tối ưu trong thời gian chấp nhận được. Giải thuật meta-heuristic nổi lên như một hướng đi đầy hứa hẹn, cung cấp khả năng tìm kiếm gần tối ưu trong không gian giải pháp rộng lớn. Giải thuật meta-heuristic không đảm bảo tìm được nghiệm tối ưu tuyệt đối, nhưng thường đưa ra các giải pháp đủ tốt trong thời gian hợp lý, đặc biệt hữu ích cho các bài toán NP-khó như thiết kế mạng. Trong bối cảnh mạng viễn thông và mạng máy tính hiện đại, việc đảm bảo tính liên tục của dịch vụ là vô cùng quan trọng. Sự cố có thể gây ra thiệt hại lớn về kinh tế và uy tín. Do đó, việc thiết kế mạng có khả năng chống chịu lỗi (fault tolerance) là một yêu cầu thiết yếu. Các giải thuật meta-heuristic như giải thuật di truyền, thuật toán ACO, thuật toán PSO, thuật toán SA và thuật toán Tabu Search đã được áp dụng thành công trong nhiều lĩnh vực tối ưu hóa. Chúng có khả năng khám phá không gian tìm kiếm một cách hiệu quả, tránh bị mắc kẹt vào các cực trị địa phương. Việc áp dụng giải thuật meta heuristic vào thiết kế mạng chịu lỗi mở ra khả năng xây dựng các mô hình mạng mạnh mẽ, có khả năng tự phục hồi (khả năng phục hồi mạng) và đáp ứng yêu cầu khắt khe về độ tin cậy mạng. Điều này đặc biệt quan trọng trong các ứng dụng quan trọng như hệ thống ngân hàng, y tế, và giao thông. Các nghiên cứu gần đây cho thấy sự kết hợp giữa giải thuật meta-heuristic và các kỹ thuật đánh giá độ tin cậy mang lại hiệu quả cao trong việc tìm kiếm các cấu hình mạng tối ưu về cả chi phí thiết kế mạng và hiệu suất mạng.

1.1. Vai trò của giải thuật meta heuristic trong tối ưu hóa 50 ký tự

Các giải thuật meta-heuristic đóng vai trò quan trọng trong việc giải quyết các bài toán tối ưu hóa mạng phức tạp, đặc biệt là trong bối cảnh thiết kế mạng chịu lỗi. Chúng cung cấp các phương pháp tìm kiếm linh hoạt và hiệu quả, giúp tìm ra các giải pháp gần tối ưu trong thời gian chấp nhận được. Giải thuật di truyền, thuật toán ACO, và thuật toán PSO là những ví dụ điển hình về phương pháp meta-heuristic đã được chứng minh tính hiệu quả trong nhiều lĩnh vực. Các thuật toán này có khả năng khám phá không gian giải pháp rộng lớn, tránh bị mắc kẹt vào các cực trị địa phương và tìm kiếm các giải pháp tốt hơn so với các phương pháp truyền thống. Độ tin cậy mạng, khả năng phục hồi mạng, và chi phí thiết kế mạng là những yếu tố quan trọng mà các giải thuật meta heuristic có thể giúp tối ưu hóa.

1.2. Ứng dụng meta heuristic trong bài toán thiết kế mạng 52 ký tự

Ứng dụng meta-heuristic trong bài toán thiết kế mạng mang lại nhiều lợi ích, bao gồm khả năng tìm kiếm các cấu hình mạng tối ưu về chi phí, hiệu suất và độ tin cậy. Các giải thuật meta-heuristic có thể được sử dụng để giải quyết các vấn đề như định tuyến lưu lượng, phân bổ tài nguyên và lựa chọn vị trí đặt các thiết bị mạng. Bằng cách áp dụng các thuật toán này, các nhà thiết kế mạng có thể tạo ra các mạng hiệu quả hơn, linh hoạt hơn và có khả năng chống chịu lỗi tốt hơn. Ví dụ, giải thuật di truyền có thể được sử dụng để tìm kiếm các đường dẫn tối ưu cho lưu lượng mạng, trong khi thuật toán ACO có thể được sử dụng để phân bổ tài nguyên mạng một cách hiệu quả.

II. Thách Thức và Vấn Đề trong Thiết Kế Mạng Chịu Lỗi 58 ký tự

Việc thiết kế mạng chịu lỗi đối mặt với nhiều thách thức lớn. Đầu tiên, độ phức tạp của bài toán tăng lên đáng kể khi kích thước mạng và số lượng các yếu tố cần xem xét tăng lên. Việc đảm bảo độ tin cậy mạng đòi hỏi phải tính đến nhiều kịch bản lỗi khác nhau, từ lỗi thiết bị, lỗi đường truyền đến các tấn công mạng. Việc tối ưu hóa mạng đồng thời nhiều mục tiêu (ví dụ: giảm chi phí, tăng băng thông mạng, giảm độ trễ mạng) cũng là một thách thức lớn. Hơn nữa, các ràng buộc về tài nguyên (ví dụ: ngân sách, công suất thiết bị) có thể hạn chế khả năng tìm kiếm các giải pháp tối ưu. Theo [Tài liệu gốc], bài toán thiết kế mạng chịu lỗi là một bài toán NP-khó, nghĩa là không có thuật toán nào có thể tìm ra giải pháp tối ưu trong thời gian đa thức. Điều này đòi hỏi phải sử dụng các phương pháp tối ưu hóa gần đúng, chẳng hạn như giải thuật meta-heuristic. Ngoài ra, việc đánh giá độ tin cậy của mạng là một vấn đề phức tạp, đòi hỏi phải sử dụng các mô hình toán học và các phương pháp mô phỏng phức tạp. Việc lựa chọn mô hình phù hợp và đảm bảo tính chính xác của các kết quả đánh giá độ tin cậy là một thách thức quan trọng. Cuối cùng, việc triển khai và quản lý mạng chịu lỗi đòi hỏi phải có các công cụ và kỹ thuật đặc biệt. Việc giám sát và phát hiện lỗi, tự động chuyển mạch khi có lỗi, và phục hồi mạng một cách nhanh chóng là những yêu cầu quan trọng.

2.1. Độ phức tạp của bài toán tối ưu hóa mạng 53 ký tự

Bài toán tối ưu hóa mạng là một bài toán phức tạp, đặc biệt khi xem xét các yếu tố như độ tin cậy mạng, khả năng phục hồi mạng, và chi phí thiết kế mạng. Số lượng các giải pháp khả thi tăng lên theo cấp số nhân khi kích thước mạng tăng lên, khiến cho việc tìm kiếm giải pháp tối ưu trở nên khó khăn. Các phương pháp truyền thống thường không thể giải quyết được các bài toán tối ưu hóa mạng có kích thước lớn trong thời gian chấp nhận được. Do đó, cần phải sử dụng các phương pháp tối ưu hóa gần đúng, chẳng hạn như giải thuật meta heuristic, để tìm ra các giải pháp tốt trong thời gian hợp lý.

2.2. Ràng buộc và mục tiêu trong thiết kế mạng chịu lỗi 56 ký tự

Trong thiết kế mạng chịu lỗi, có nhiều ràng buộc và mục tiêu cần phải xem xét. Các ràng buộc có thể bao gồm giới hạn về ngân sách, công suất thiết bị, và các yêu cầu về hiệu suất. Các mục tiêu có thể bao gồm giảm chi phí thiết kế mạng, tăng độ tin cậy mạng, và giảm độ trễ mạng. Việc tối ưu hóa mạng đồng thời nhiều mục tiêu và đáp ứng các ràng buộc khác nhau là một thách thức lớn. Các giải thuật meta-heuristic có thể được sử dụng để tìm ra các giải pháp cân bằng giữa các mục tiêu khác nhau và đáp ứng các ràng buộc đã cho.

III. Giải Thuật Di Truyền để Thiết Kế Mạng Quang Chịu Lỗi 59 ký tự

Giải thuật di truyền (GA) là một phương pháp meta-heuristic mạnh mẽ, mô phỏng quá trình tiến hóa tự nhiên. Trong bài toán thiết kế mạng quang chịu lỗi, GA có thể được sử dụng để tìm kiếm cấu hình mạng tối ưu về chi phí, hiệu suất và độ tin cậy. GA bắt đầu với một quần thể các giải pháp tiềm năng (nhiễm sắc thể). Mỗi nhiễm sắc thể đại diện cho một cấu hình mạng cụ thể. Quá trình tiến hóa bao gồm các bước: chọn lọc (lựa chọn các nhiễm sắc thể tốt nhất để sinh sản), lai ghép (tạo ra các nhiễm sắc thể mới bằng cách kết hợp các phần của các nhiễm sắc thể cha mẹ), đột biến (thay đổi ngẫu nhiên một số phần của nhiễm sắc thể). Các bước này được lặp lại cho đến khi tìm thấy một giải pháp đủ tốt hoặc đạt đến một số lượng vòng lặp tối đa. Theo [Tài liệu gốc], GA đã được chứng minh là hiệu quả trong việc giải quyết các bài toán tối ưu hóa mạng phức tạp. Tuy nhiên, GA có thể tốn nhiều thời gian tính toán, đặc biệt là đối với các mạng lớn. Do đó, cần phải sử dụng các kỹ thuật song song hóa để tăng tốc quá trình tìm kiếm. Giải thuật di truyền song song là một biến thể của GA được thiết kế để chạy trên nhiều bộ xử lý, cho phép tìm kiếm không gian giải pháp một cách nhanh chóng hơn. Việc sử dụng giải thuật di truyền song song đặc biệt hiệu quả trong việc giải quyết bài toán thiết kế mạng quang chịu lỗi với quy mô lớn.

3.1. Cơ chế hoạt động của giải thuật di truyền 51 ký tự

Giải thuật di truyền hoạt động dựa trên các nguyên tắc của tiến hóa tự nhiên. Thuật toán bắt đầu với một quần thể các giải pháp ngẫu nhiên, được gọi là nhiễm sắc thể. Mỗi nhiễm sắc thể đại diện cho một giải pháp tiềm năng cho bài toán. Sau đó, thuật toán tiến hành các bước chọn lọc, lai ghép, và đột biến để tạo ra các thế hệ mới của nhiễm sắc thể. Quá trình này lặp lại cho đến khi tìm thấy một giải pháp đủ tốt hoặc đạt đến một số lượng vòng lặp tối đa. Việc chọn lọc ưu tiên các nhiễm sắc thể có độ thích nghi cao, tức là các giải pháp tốt hơn. Lai ghép kết hợp các phần của hai nhiễm sắc thể cha mẹ để tạo ra các nhiễm sắc thể con. Đột biến thay đổi ngẫu nhiên một số phần của nhiễm sắc thể để tạo ra sự đa dạng trong quần thể.

3.2. Áp dụng GA vào thiết kế mạng quang chịu lỗi 58 ký tự

Trong thiết kế mạng quang chịu lỗi, GA có thể được sử dụng để tìm kiếm cấu hình mạng tối ưu về chi phí, hiệu suất và độ tin cậy. Nhiễm sắc thể có thể đại diện cho các yếu tố như vị trí đặt các thiết bị mạng, dung lượng của các đường truyền, và các giao thức định tuyến. Hàm mục tiêu có thể được sử dụng để đánh giá chất lượng của một cấu hình mạng cụ thể, dựa trên các tiêu chí như chi phí thiết kế mạng, độ tin cậy mạng, và độ trễ mạng. Bằng cách áp dụng GA, các nhà thiết kế mạng có thể tìm ra các cấu hình mạng quang có khả năng chống chịu lỗi tốt và đáp ứng các yêu cầu về hiệu suất và chi phí.

IV. Ứng dụng thuật toán ACO trong thiết kế mạng 53 ký tự

Thuật toán ACO (Ant Colony Optimization) là một phương pháp meta-heuristic được lấy cảm hứng từ hành vi tìm kiếm thức ăn của kiến. Trong bối cảnh thiết kế mạng, ACO có thể được áp dụng để tìm kiếm đường dẫn tối ưu cho lưu lượng, tối ưu hóa việc phân bổ tài nguyên, hoặc xác định vị trí đặt các thiết bị mạng. Kiến ảo sẽ di chuyển trên mạng, để lại dấu vết pheromone trên các đường dẫn mà chúng đi qua. Các kiến sau sẽ có xu hướng chọn các đường dẫn có nồng độ pheromone cao hơn, tạo ra một cơ chế phản hồi tích cực. Qua thời gian, các đường dẫn tốt nhất sẽ được củng cố, trong khi các đường dẫn kém hiệu quả sẽ bị loại bỏ. Theo các nghiên cứu, ACO tỏ ra hiệu quả trong việc tìm kiếm các giải pháp tốt cho các bài toán tối ưu hóa mạng phức tạp, đặc biệt là trong các mạng có cấu trúc động. ACO cũng có khả năng thích ứng với các thay đổi trong mạng, chẳng hạn như lỗi thiết bị hoặc thay đổi lưu lượng. Tuy nhiên, ACO có thể yêu cầu điều chỉnh các tham số cẩn thận để đạt được hiệu suất tốt nhất.

4.1. Nguyên lý hoạt động của thuật toán ACO 49 ký tự

Thuật toán ACO mô phỏng hành vi tìm kiếm thức ăn của kiến. Kiến ảo di chuyển trên mạng, để lại dấu vết pheromone trên các đường dẫn mà chúng đi qua. Các kiến sau có xu hướng chọn các đường dẫn có nồng độ pheromone cao hơn. Điều này tạo ra một cơ chế phản hồi tích cực, trong đó các đường dẫn tốt nhất được củng cố, trong khi các đường dẫn kém hiệu quả bị loại bỏ. Nồng độ pheromone trên một đường dẫn giảm dần theo thời gian do bay hơi, giúp thuật toán tránh bị mắc kẹt vào các cực trị địa phương.

4.2. Ưu điểm và hạn chế của thuật toán ACO 49 ký tự

Thuật toán ACO có một số ưu điểm, bao gồm khả năng tìm kiếm các giải pháp tốt cho các bài toán tối ưu hóa mạng phức tạp, khả năng thích ứng với các thay đổi trong mạng, và khả năng hoạt động trong các mạng có cấu trúc động. Tuy nhiên, ACO cũng có một số hạn chế, bao gồm yêu cầu điều chỉnh các tham số cẩn thận để đạt được hiệu suất tốt nhất, và có thể tốn nhiều thời gian tính toán đối với các mạng lớn.

V. Kết quả và Đánh giá Hiệu quả Giải Thuật 51 ký tự

Kết quả thử nghiệm cho thấy giải thuật di truyền song song (PGAMSOND) mang lại kết quả tốt hơn so với giải thuật di truyền (GAMSOND) thông thường và thuật toán Branch and Price trong việc giải bài toán thiết kế mạng quang chịu lỗi đa tầng. Theo [Tài liệu gốc], PGAMSOND không chỉ tìm ra các giải pháp có chi phí thiết kế mạng thấp hơn mà còn giảm đáng kể thời gian tính toán. Đồ thị so sánh chi phí xây dựng mạng cho thấy PGAMSOND luôn đạt được chi phí thấp hơn, đặc biệt là trên các bộ dữ liệu thực tế. Điều này chứng minh tính hiệu quả của việc song song hóa thuật toán trong việc giải quyết các bài toán tối ưu hóa phức tạp. Tuy nhiên, việc triển khai PGAMSOND đòi hỏi phải có kiến thức về lập trình song song và sử dụng các công cụ hỗ trợ song song hóa. Việc đánh giá hiệu quả của các giải thuật meta-heuristic khác như thuật toán ACO, thuật toán PSO cũng cần được thực hiện để so sánh và lựa chọn phương pháp phù hợp nhất cho từng loại mạng và yêu cầu cụ thể.

5.1. So sánh giải thuật di truyền và di truyền song song 56 ký tự

Giải thuật di truyền song song (PGAMSOND) thường vượt trội hơn so với giải thuật di truyền (GAMSOND) truyền thống, đặc biệt trong việc giải các bài toán tối ưu hóa mạng phức tạp. PGAMSOND tận dụng khả năng tính toán song song để khám phá không gian giải pháp rộng lớn hơn một cách nhanh chóng. Kết quả là, PGAMSOND thường tìm ra các giải pháp tốt hơn và giảm thời gian tính toán. Tuy nhiên, PGAMSOND đòi hỏi nhiều tài nguyên tính toán hơn và cần kiến thức về lập trình song song.

5.2. Ảnh hưởng của dữ liệu đầu vào đến hiệu quả thuật toán 58 ký tự

Dữ liệu đầu vào có ảnh hưởng đáng kể đến hiệu quả của các giải thuật meta-heuristic. Các bộ dữ liệu khác nhau có thể có các đặc tính khác nhau, chẳng hạn như kích thước mạng, mật độ kết nối, và các yêu cầu về độ tin cậy. Các giải thuật meta-heuristic có thể hoạt động tốt hơn trên một số loại bộ dữ liệu so với các loại khác. Do đó, cần phải thử nghiệm các thuật toán khác nhau trên nhiều bộ dữ liệu khác nhau để đánh giá hiệu quả của chúng một cách khách quan.

VI. Kết Luận và Hướng Phát Triển Trong Thiết Kế Mạng 55 ký tự

Luận văn đã trình bày việc ứng dụng giải thuật meta-heuristic để giải quyết bài toán thiết kế mạng chịu lỗi. Các kết quả nghiên cứu cho thấy giải thuật di truyền song song có tiềm năng lớn trong việc tìm kiếm các cấu hình mạng tối ưu về chi phí và độ tin cậy. Tuy nhiên, vẫn còn nhiều hướng nghiên cứu cần được khám phá. Việc kết hợp các giải thuật meta-heuristic khác nhau, hoặc kết hợp giải thuật meta-heuristic với các phương pháp tối ưu hóa truyền thống có thể mang lại kết quả tốt hơn. Việc phát triển các mô hình đánh giá độ tin cậy chính xác hơn cũng là một hướng đi quan trọng. Ngoài ra, cần nghiên cứu các phương pháp triển khai và quản lý mạng chịu lỗi một cách hiệu quả hơn. Hướng phát triển của đề tài là tập trung vào việc phát triển các thuật toán tối ưu hóa hiệu quả hơn, có khả năng thích ứng với các thay đổi trong mạng và đáp ứng các yêu cầu ngày càng cao về độ tin cậy mạng. Theo [Tài liệu gốc], cần xem xét các yếu tố như bảo mật mạng và khả năng mở rộng trong tương lai.

6.1. Các hướng nghiên cứu tiềm năng trong tương lai 48 ký tự

Có nhiều hướng nghiên cứu tiềm năng trong tương lai liên quan đến việc ứng dụng giải thuật meta-heuristic vào thiết kế mạng chịu lỗi. Các hướng nghiên cứu này bao gồm: phát triển các thuật toán tối ưu hóa hiệu quả hơn, kết hợp các giải thuật meta-heuristic khác nhau, tích hợp các yếu tố bảo mật mạng và khả năng mở rộng trong tương lai, và nghiên cứu các phương pháp triển khai và quản lý mạng chịu lỗi hiệu quả hơn.

6.2. Tầm quan trọng của bảo mật và khả năng mở rộng 51 ký tự

Bảo mật và khả năng mở rộng là hai yếu tố quan trọng cần được xem xét trong thiết kế mạng chịu lỗi. Mạng cần phải được bảo vệ khỏi các tấn công mạng, và cần có khả năng mở rộng để đáp ứng nhu cầu ngày càng tăng về băng thông và số lượng người dùng. Các giải thuật meta-heuristic có thể được sử dụng để tối ưu hóa các khía cạnh khác nhau của bảo mật và khả năng mở rộng, chẳng hạn như lựa chọn các giao thức bảo mật phù hợp và phân bổ tài nguyên mạng một cách hiệu quả.

Trích đoạn nội dung tài liệu

MỞ ĐẦU il CHUGNG 1: CO SOLY THUYET. Một số khải niệm cơ bản về MAAN eee ces ceeeeesse renee 14 1. Công nghệ ghép kênh theo bước sóng(WDIM) 14 1. Mô hình mạng |P-over-W1M 1.

Mạng chịu lỗi 1. Các khái niệm cơ bản về đồ thị. Dinh nghia dé thi 1. Dễ thị COD.

Đường đi rong đỗ thị. LÝ thuyết về độ phức tạp thuật toán. Mộtsố khái niệm 1. Các ký hiệu tiệm cận.

Dộ phức tạp tính toán của bài toán. Lớp bái tán NP-khó Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT tà Dé tai: Gidi thudt Meta-heuristic dé gid quyét bai todn thiél ké mang chiu 151 1. Mộtsố khái niệm cơ bản. 22 Lép bai toan P, NP, va co-NP.

Khái niêm quy dẫn - 24 1. Lớp bài toán đầy đủ và NP-khó.24 CHƯƠNG 2: BÀI TOÁN THIẾT KẾ MẠNG QUANG CHỊU LỖI ĐA TẢNG ,. Phát biểu bài toán 5 2. Các ứng dụng của bải toán.

Các nghiên cửu liên quan. 29 CIIUGNG 3: GIAI THUAT DI TRUYEN VA DI TRUYEN SONG SONG 31 3. Giới thiệu về giải thuật đi truyền 31 3. Các khải niệm cơ bản trong giải thuật di truyền.

Cá thể nhiễm sắc thể. Hàm mục tiêu - - 34 3. Đột biển và lai ghép. Chọn lọc tự nhiền - 34 3.

M6 hinh giải thuật di truyền - - 35 3. Các thành phan chính của giải thuật đitruyền Hư "¬— 3. Giải thuật di truyền song song. 37 CHƯƠNG 4: GIẢI THUẬT DI TRUYÊN SONG SÓNG GIẢI BÀI TOÁN THIẾT KẾ MẠNG QUANG CHỊU LỖI ĐA TẦNG .4Ó Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Dé tai: Gidi thudt Meta-heuristic dé gid quyét bai todn thiél ké mang chiu 151 41.

Hảm thích nghĩ. Khởi tạo nhiễm sắc thể. Khởi tạo quần thể ban đầu 46 44. Lựa chọn cá thể lai ghép.

Lai ghép trao dổi nhiễm sắc thể 46 4. Lai ghép trao đôi gen. Đột biến biến đổi gen. Đột biển thay thế một nhiễm sắc thể.

Đột biển tái tạo cá thể - loại ]. Dột biến tải tạo cá thể - loại 2. Đầu tranh sinh tên 4. Song song hóa thuật toán.

CHƯƠNG 5: KÉT QUÁ THỦ NGHIỆM VẢ ĐÁNH GIÁ. _ Dữ liệu thử nghiệm. Phương pháp xây dựng các bộ dữ liệu. Các bộ dữ liệu thử nghiệm.

Môi trường thứ nghiệm. Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Dé tai: Gidi thudt Meta-heuristic dé gid quyét bai todn thiél ké mang chiu 151 5. Tham số thực nghiệm 3. Kết quả thử nghiệm và so sánh.

Bảng thống kể kết quả CHƯƠNG 6: BẢN LUẬN 6. Các kết quả đạt dược 62. Hướng phát triển của để tài. DANH MỤC TÀI LIỆU THAM KHẢO PHI LỤC Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Pb tai: Cidi thud Meta-heuristic dé gidi quyét bai tadn thiél ké mang chin 151 Tĩnh 22: Dỗ thị so sánh chỉ phí xây dựng mạng trưng bình và tốt nhất của các giải thuật Hranch and Price [1], GAMSOND thường, GAMBOMND song song, qua 20 lần chạy trên các bộ dữ liệu thực tẾ.

Tuy we 67 Hình 23: Đồ thị so sánh thời gian của các giải thuật GAMSOND thường, GAMSONL song song chay trén 1 mAy va 2 may qua 20 lần chạy trên các bộ dữ liệu ngẫu nhiên 68 Tỉnh 24: Đồ thị so sảnh thời gian của các giải thuật GAMSOND thường, GAMSOND song song chạy trên Ì máy và 2 máy qua 20 lần chạy trên các bộ dữ liệu thực tế - - 69 Hình 25: Giao điện chương trình. 74 Tình 26: Cầu hình các thông số đi truyền. : 7§ Hinh 27: Thidt ké database Server. - - 76 Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Pb tai: Cidi thud Meta-heuristic dé gidi quyét bai tadn thiél ké mang chin 151 DANH MUC CAC KÝ ATEU, CAC CHT VIFT TAT Chữ viết tắt | Viết đầy đủ nghĩa NST Nhiém sắc thể hiểm sắc thể GA Genetic algorithms Giải thuật đi truyền OXC Optical cross connect Thist bi chuyén doi quang WDM Wavelength Division Ghép kênh theo bước sóng Multiplexing MSOND Multilayer survivable optical | Mang quang chịu lỗi đa tảng network GAMSOND | Genetic algorithms multilayer | Giai thuật di truyền giải bải toán survivable optical network thiết kế mạng quang chịu lỗi đa tang PGAMSOND | Parallel Genetic algorithms | Giai thuat di truyén song song multilayer survivable optical | giai bai toán thiết kế mạng quang network chiu 15: da Ling TSP Travel Sale man Problem Bai toán người du lịch TP Internet Protocol Giao thức liên mạng MPLS Multiprotocol Label Switching Học viền thực hiện: Tào Thanh Tùng— CB110260 - Láp: IIBCNTT.KT Pb tai: Cidi thud Meta-heuristic dé gidi quyét bai tadn thiél ké mang chin 151 DANH MUC CAC KÝ ATEU, CAC CHT VIFT TAT Chữ viết tắt | Viết đầy đủ nghĩa NST Nhiém sắc thể hiểm sắc thể GA Genetic algorithms Giải thuật đi truyền OXC Optical cross connect Thist bi chuyén doi quang WDM Wavelength Division Ghép kênh theo bước sóng Multiplexing MSOND Multilayer survivable optical | Mang quang chịu lỗi đa tảng network GAMSOND | Genetic algorithms multilayer | Giai thuật di truyền giải bải toán survivable optical network thiết kế mạng quang chịu lỗi đa tang PGAMSOND | Parallel Genetic algorithms | Giai thuat di truyén song song multilayer survivable optical | giai bai toán thiết kế mạng quang network chiu 15: da Ling TSP Travel Sale man Problem Bai toán người du lịch TP Internet Protocol Giao thức liên mạng MPLS Multiprotocol Label Switching Học viền thực hiện: Tào Thanh Tùng— CB110260 - Láp: IIBCNTT.KT Pb tai: Cidi thud Meta-heuristic dé gidi quyét bai tadn thiél ké mang chin 151 Tĩnh 22: Dỗ thị so sánh chỉ phí xây dựng mạng trưng bình và tốt nhất của các giải thuật Hranch and Price [1], GAMSOND thường, GAMBOMND song song, qua 20 lần chạy trên các bộ dữ liệu thực tẾ.

Tuy we 67 Hình 23: Đồ thị so sánh thời gian của các giải thuật GAMSOND thường, GAMSONL song song chay trén 1 mAy va 2 may qua 20 lần chạy trên các bộ dữ liệu ngẫu nhiên 68 Tỉnh 24: Đồ thị so sảnh thời gian của các giải thuật GAMSOND thường, GAMSOND song song chạy trên Ì máy và 2 máy qua 20 lần chạy trên các bộ dữ liệu thực tế - - 69 Hình 25: Giao điện chương trình. 74 Tình 26: Cầu hình các thông số đi truyền. : 7§ Hinh 27: Thidt ké database Server. - - 76 Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Pb tai: Cidi thud Meta-heuristic dé gidi quyét bai tadn thiél ké mang chin 151 DANH MỤC CÁC BẰNG Băng1: Bộ dữ liệu ngẫu nhiên - - 58 Bằng2: Bộ dữ liệu thực tê.

Hee, SỐ Bang 3 Câu hình hệ thống thử nghiệm.- Bang 4: Bộ tham số GAMISORTD thử nghiệm 60 Bang 5: Kết quả thực nghiệm của giải thuật Branch and Price [1] vá giải thuật GAMSOND qua 20 lần chạy trên các bộ dữ liệu ngẫu nhiên - 6 Bang 6: Kết quả thực nghiệm của giải thuật Hranch and Price [1] và giải thuật GAMSOND qua 20 lần chạy trên các bộ đữ liệu thực tế. 4E Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Pb tai: Cidi thud Meta-heuristic dé gidi quyét bai tadn thiél ké mang chin 151 DANH MỤC CÁC BẰNG Băng1: Bộ dữ liệu ngẫu nhiên - - 58 Bằng2: Bộ dữ liệu thực tê. Hee, SỐ Bang 3 Câu hình hệ thống thử nghiệm.- Bang 4: Bộ tham số GAMISORTD thử nghiệm 60 Bang 5: Kết quả thực nghiệm của giải thuật Branch and Price [1] vá giải thuật GAMSOND qua 20 lần chạy trên các bộ dữ liệu ngẫu nhiên - 6 Bang 6: Kết quả thực nghiệm của giải thuật Hranch and Price [1] và giải thuật GAMSOND qua 20 lần chạy trên các bộ đữ liệu thực tế. 4E Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Pb tai: Cidi thud Meta-heuristic dé gidi quyét bai tadn thiél ké mang chin 151 DANH MỤC CÁC BẰNG Băng1: Bộ dữ liệu ngẫu nhiên - - 58 Bằng2: Bộ dữ liệu thực tê.

Hee, SỐ Bang 3 Câu hình hệ thống thử nghiệm.- Bang 4: Bộ tham số GAMISORTD thử nghiệm 60 Bang 5: Kết quả thực nghiệm của giải thuật Branch and Price [1] vá giải thuật GAMSOND qua 20 lần chạy trên các bộ dữ liệu ngẫu nhiên - 6 Bang 6: Kết quả thực nghiệm của giải thuật Hranch and Price [1] và giải thuật GAMSOND qua 20 lần chạy trên các bộ đữ liệu thực tế. 4E Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Dé tai: Gidi thudt Meta-heuristic dé gid quyét bai todn thiél ké mang chiu 151 5. Tham số thực nghiệm 3. Kết quả thử nghiệm và so sánh.

Bảng thống kể kết quả CHƯƠNG 6: BẢN LUẬN 6. Các kết quả đạt dược 62. Hướng phát triển của để tài. DANH MỤC TÀI LIỆU THAM KHẢO PHI LỤC Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Dé tai: Gidi thudt Meta-heuristic dé gid quyét bai todn thiél ké mang chiu 151 5.

Tham số thực nghiệm 3. Kết quả thử nghiệm và so sánh. Bảng thống kể kết quả CHƯƠNG 6: BẢN LUẬN 6. Các kết quả đạt dược 62.

Hướng phát triển của để tài. DANH MỤC TÀI LIỆU THAM KHẢO PHI LỤC Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Pb tai: Cidi thud Meta-heuristic dé gidi quyét bai tadn thiél ké mang chin 151 DANH MỤC CÁC BẰNG Băng1: Bộ dữ liệu ngẫu nhiên - - 58 Bằng2: Bộ dữ liệu thực tê. Hee, SỐ Bang 3 Câu hình hệ thống thử nghiệm.- Bang 4: Bộ tham số GAMISORTD thử nghiệm 60 Bang 5: Kết quả thực nghiệm của giải thuật Branch and Price [1] vá giải thuật GAMSOND qua 20 lần chạy trên các bộ dữ liệu ngẫu nhiên - 6 Bang 6: Kết quả thực nghiệm của giải thuật Hranch and Price [1] và giải thuật GAMSOND qua 20 lần chạy trên các bộ đữ liệu thực tế. 4E Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Pb tai: Cidi thud Meta-heuristic dé gidi quyét bai tadn thiél ké mang chin 151 TOI CAM DOAN Tôi xin cam đoạn: 1.

Những nội dung trong luân văn nảy là công trình nghiên cứu của tôi đưới sự hướng dẫn trục tiếp của T8, Huỳnh Thị Thanh Bình. Mọi tham khâo đồng trong liên văn đều được trích dẫn rõ răng lên tác giã, lên công trình, thời gian, dịa diễm công bó. Các số liệu, kết quả nẻu trong lưận văn là trung thực và chưa từng được ai công bổ trong bất kỳ công trình nảo khác. Mọi sao chứp không hợp lê, vi pham quy chế đào tạo, hay gian trá, tôi xin chịu hoán toàn trách nhiệm.

Tác giả luận văn (Ký và ghủ rõ họ tên) Học viền thực hiện: Tào Thanh Tùng— CB110260- Láp: IIBCNTT.KT Pb tai: Cidi thud Meta-heuristic dé gidi quyét bai tadn thiél ké mang chin 151 DANH MUC CAC HINH VE, BO THT Hinh 1: M6 hinh mang IP/WDM. 16 Hình 2: Đơn dé thi G. 17 Hình 3: Dé thi day đủ Œ 18 Tình 4: Đồ thị con 11. 18 Hình 5: Các lớp bài toán P, MP vả co-NP 24 Ilinh 6: Bé thi G,, G2, lightpath L}, L?