Ứng dụng giải thuật tiến hóa đa mục tiêu trong thiết kế tối ưu kiến trúc mạng viễn thông

Hoàng Ngọc Thanh

VNPT Bà Rịa - Vũng Tàu, Tp.Vũng Tàu thanhhn@vnpt-brvt.com.vn

Dương Tuấn Anh

Khoa Khoa Học và Kỹ Thuật Máy Tính

Đại Học Bách Khoa Tp. Hồ Chí Minh

dtanh@cse.hcmut.edu.vn

Tóm tắt - Bài viết này đề xuất cách tiếp cận sử dụng giải thuật tiến hóa đa mục tiêu (MOEA) để giải quyết bài toán thiết kế tối ưu kiến trúc mạng viễn thông với nhiều ràng buộc phức tạp và các mục tiêu của bài toán gồm yếu tố chi phí và độ tin cậy. Mỗi cá thể trong quần thể là biểu diễn của một mô hình mạng (topology) có yếu tố chi phí được xác định nhờ giải thuật đơn hình trong quy hoạch tuyến tính và độ tin cậy được xác định nhờ giải thuật Monte Carlo. Một số giải thuật tiến hóa đa mục tiêu khác nhau như NSGA, NSGAII, NSGAIIC và SPEA đã được hiện thực và thử nghiệm để so sánh và đánh giá hiệu quả.

Abstract - The paper proposes a new approach based on a multi-objective evolutionary algorithm (MOEA) to solve the optimal design of telecommunication network. This design involves many complex constraints and multiple optimization objectives including connection cost and network reliability. Each individual in the population is a representation of a network topology which connection cost is determined by Simplex method of linear programming and reliability is derived by Monte Carlo algorithm. A number of popular MOEA variants such as NSGA, NSGAII, NSGAIIC and SPEA have been implemented and experimented to compare their performances.

Từ khóa: tối ưu hóa đa mục tiêu, giải thuật tiến hóa đa mục tiêu, thiết kế mạng viễn thông

1. GIỚI THIỆU

Trong thiết kế mạng viễn thông, các nút tượng trưng cho các tổng đài hoặc các trung tâm chuyển mạch, cần được kết nối với nhau theo một cách tối ưu nhất (theo nghĩa chi phí truyền tải phải là tối thiểu, trong khi độ tin cậy phải là tối đa) nhằm điều khiển các lưu lượng điểm - điểm mong đợi. Các ràng buộc khác nhau trên mô hình mạng, dung lượng nút và liên kết phải được tôn trọng. Đây là dạng bài toán tối ưu đa mục tiêu có tính phi tuyến cao, mà cho đến nay, việc tìm kiếm một phương pháp chính xác để giải quyết vẫn còn để ngỏ.

Mấy năm gần đây, một số tác giả đã giải quyết bài toán nêu trên theo hướng dùng thuật giải di truyền (GA) để tối ưu một trong hai mục tiêu nêu trên hoặc bỏ qua một số các ràng buộc của bài toán; một số tác giả khác giải quyết hạn hẹp ở một vài cấu trúc mạng đặc thù. Chẳng hạn như trong [5] Berry và các cộng sự, 1995 báo cáo việc dùng giải thuật di truyền để thiết kế tối ưu mạng viễn thông có cấu trúc cây (Tree-structured Communications Network). Trong [4], Ko và các cộng sự, 1997, đề cập đến việc dùng giải thuật di truyền để thiết kế các mạng viễn thông dạng lưới (Mesh Network). Konak và Smith, năm 1999 ([8]) đã dùng giải thuật di truyền lai để thiết kế trục chính (backbone) của mạng viễn thông. Trong nước, năm 2002, tác giả Lương Hồng Khanh cũng có bài viết về việc ứng dụng giải thuật di truyền trong việc tối ưu hóa các tham số chất lượng mạng viễn thông [2]. Tuy nhiên, nhìn chung bên cạnh sự ra đời rất sôi động của nhiều dạng thức của giải thuật tiến hóa đa mục tiêu (multi-objective evolutionary algorithm - MOEA) kể từ giữa thập niên 80 đến nay trong cộng đồng nghiên cứu về tối ưu hóa đa mục tiêu trên thế giới ([23]), việc ứng dụng họ giải thuật MOEA này để giải quyết các bài toán thực tế, đặc biệt trong lĩnh vực viễn thông, thì hãy còn rất ít trên phạm vi thế giới cũng như trong nước. Ở đây, chúng tôi, lần đầu tiên, nghiên cứu tiếp cận bài toán thiết kế tối ưu kiến trúc mạng viễn thông theo hướng tối ưu đa mục tiêu sử dụng một số các giải thuật tiến hóa đa mục tiêu như NSGA, NSGAII, SPEA,… trên cơ sở tôn trọng các ràng buộc và các mục tiêu thực tế, không đơn giản hóa hoặc bỏ qua các ràng buộc và tối ưu đồng thời nhiều mục tiêu. Sau khi hiện thực và thực nghiệm, kết quả mà chúng tôi đạt được cho thấy có thể vận dụng họ giải thuật tiến hóa đa mục tiêu để thiết kế các mạng viễn thông có cấu trúc không đặc thù.

Cấu trúc các phần còn lại trong bài báo này như sau. Mục 2 sẽ mô tả định nghĩa của bài toán thiết kế tối ưu mạng viễn thông. Mục 3 trình bày sơ lược về tối ưu hóa đa mục tiên và các giải thuật tiến hóa đa mục tiêu. Mục 4 mô tả chi tiết về phương pháp ứng dụng giải thuật tiến hóa đa mục tiêu để giải bài toán thiết kế tối ưu mạng viễn thông. Mục 5 báo cáo kết quả hiện thực và thực nghiệm. Mục 6 nêu một số kết luận và hướng phát triển trong tương lai.

2. ĐỊNH NGHĨA BÀI TOÁN

Mạng được mô hình hóa dưới dạng một đồ thị với các nút mạng được thể hiện là các đỉnh và các liên kết là các cạnh trong đồ thị. Cạnh của đồ thị có các trọng số tương ứng với loại của liên kết. Các liên kết cho phép dòng thông tin đi theo hai chiều. Vì vậy đồ thị ở đây là đồ thị vô hướng và có trọng số. Xét đồ thị G(V,E) với tập nút V và tập cung E thuộc tập đồ thị vô hướng S. Ta biểu diễn G bằng nửa trên của một ma trận kề nút - nút B với các phần tử b_ij (b_ij biểu diễn loại của liên kết (i, j) có giá trị trong khoảng [0, t]; 0 tương ứng với không có liên kết). Bài toán của chúng ta là tìm một đồ thị G* có chi phí truyền tải lưu lượng tối thiểu, độ tin cậy tối đa; đồng thời đảm bảo các ràng buộc về độ trễ, dung lượng nút mạng, dung lượng liên kết, bậc của nút và giới hạn số nút trung gian.
Định nghĩa:

F_pq là tổng băng thông yêu cầu trên các kết nối giữa các cặp nút nguồn - đích (p, q), F_pq có thể được biểu diễn bằng một phần tử trong ma trận lưu lượng. Băng thông này có thể được xem là tương đương với dung lượng. Và F_avg,pq là lưu lượng trung bình dự báo.

Với mỗi liên kết (i, j), có t loại liên kết, tương ứng với độ tin cậy là r_t,ij và chi phí cho từng đơn vị băng thông là c_t,ij.

Băng thông riêng phần của một đường thứ r từ nút p đến nút q được biểu thị là . Chi phí cho từng đơn vị băng thông trên đường này là . Rõ ràng ta có:.

Khi đó tổng băng thông của kết nối (p, q) là:

Каталог: download -> version
version -> Nhật Bản Đất nước mặt trời mọc (Phần 1) Lịch sử Nhật Bản
version -> CÁc hàm thông dụng các hàm tóan học (math & trig)
version -> ĐỀ CƯƠng kt hoc ky 1 khốI 10 2013-2014
version -> CHƯƠng II: TỔng quan về ĐẦu tư quốc tế Khái niệm và đặc điểm của đầu tư quốc tế
version -> BÊn thắng cuộC – chưƠng III: ĐÁnh tư SẢN
version -> Nhà Tây Sơn
version -> United States of America Hợp chúng quốc Hoa Kỳ
version -> Hiệp hội các Quốc gia Đông Nam Á tiếng Anh: Association of Southeast Asia Nations, viết tắt là asean
version -> BÊn thắng cuộC – chưƠng IX: XÉ RÀO