Tóm tắt luận văn Thạc sĩ: Nghiên cứu định tuyến và gán bước sóng trong mạng WDM sử dụng phương pháp tính toán tiến hóa lai

Chia sẻ: Nguyễn Thị Thu Trang | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

118
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt luận văn thạc sĩ đề tài nghiên cứu định tuyến và gán bước sóng trong mạng wdm sử dụng phương pháp tính toán tiến hóa lai. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt luận văn Thạc sĩ: Nghiên cứu định tuyến và gán bước sóng trong mạng WDM sử dụng phương pháp tính toán tiến hóa lai

1 LỜI NÓI ĐẦU Sự bùng nổ của mạng Internet, sự phát triển số lượng người HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG sử dùng, sự phát triển của các ứng dụng và dịch vụ mới trên nền IP, --------------------------------------- đó là những gì mà chúng ta đã chứng kiến trong vòng gần một thập kỉ qua [7]. Mạng truyền dẫn quang đã đáp ứng được rất nhiều yêu cầu về dung lượng, chi phí xây dựng và tính bảo mật thông tin. Hai công nghệ quan trọng gần đây giúp tăng dung lượng mạng quang đó là ghép kênh theo bước sóng WDM và khuếch đại sợi quang EDFA [25]. Định tuyến và gán bước sóng (RWA) có thể được coi là một bài toán cổ điển trong mạng quang WDM [17]. Trong đó nó có thể được phân thành hai bài toán con: (i) định tuyến và (ii) gán bước TIÊU VĂN GIANG sóng. Bài toán con định tuyến là tìm đường từ nguồn tới đích, còn bài toán con gán bước sóng thực hiện gán một bước sóng cho tuyến được thiết lập bởi bài toán con định tuyến. Bài toán RWA có tính NGHIÊN CỨU ĐỊNH TUYẾN VÀ GÁN BƯỚC SÓNG kết hợp bởi bản chất của nó và thuộc lớp bài toán tối ưu hóa, do TRONG MẠNG WDM SỬ DỤNG PHƯƠNG PHÁP vậy phù hợp với cách tiếp cận heuristic [13]. TÍNH TOÁN TIẾN HÓA LAI Đối với vấn đề RWA ta có thể xem xét nhiều mục tiêu thiết kế mạng đồng thời như tối đa hóa số lượng yêu cầu liên lạc để được phục vụ và giảm thiểu số lượng kênh bước sóng được chỉ NGÀNH : KHOA HỌC MÁY TÍNH định[3][6]. MÃ SỐ : 60.48.01 Để giải bài toán thiết kế đa mục tiêu, các kỹ thuật tối ưu hóa đa mục tiêu thường được sử dụng. Một số phương pháp sử dụng TÓM TẮT LUẬN VĂN THẠC SĨ các gần đúng đơn mục tiêu để giải các bài toán đa mục tiêu như ràng buộc  và tổng trọng số [1]. Tuy nhiên các gần đúng đơn mục tiêu có một nhược điểm là rất khó tìm được các nghiệm tối ưu[16]. Do vậy mà các thuật toán tiến hóa đa mục tiêu được áp dụng để HÀ NỘI - 2012 giải các bài toán thiết kế đa mục tiêu này [18] sẽ thu được những kết quả quan trọng cho việc thiết kế mạng toàn quang trên cơ sở công nghệ WDM.
2 Qua đây tôi xin trân trọng cảm ơn TS.Nguyễn Đức Nhân và 1.1. Mạng WDM. các thầy cô trong hội đồng khoa học nhà trường, Khoa Quốc tế và sau đại học đã giúp đỡ rất nhiều cho tôi để hoàn thiện luận văn này. 1.1.1. Định nghĩa: Tuy nhiên, do thời gian và trình độ còn giới hạn, tôi kính mong WDM (Wavelength Division Multiplexing – Ghép kênh theo được các thầy cô tiếp tục đóng góp, giúp đỡ để luận văn được hoàn bước sóng) là công nghệ “trong một sợi quang truyền dẫn đồng thiện tốt hơn và được ứng dụng vào thực tế. thời nhiều tín hiệu quang với nhiều bước sóng khác nhau”. ở đầu Tôi xin trân trọng cảm ơn! phát, nhiều tín hiệu quang có bước sóng khác nhau được tổ hợp lại TÁC GIẢ (ghép kênh) để truyền đi trên một sợi quang. ở đầu thu, tín hiệu tổ TIÊU VĂN GIANG hợp đó được phân giải ra (tách kênh), khôi phục lại tín hiệu gốc rồi đưa vào các đầu cuối khác nhau. 1.1.2. Các công nghệ dùng trong mạng thông tin quang. Phần này sẽ trình bày về các công nghệ đã, đang và sẽ được CHƯƠNG 1: TỔNG QUAN dùng trong hệ thống thông tin quang. Hệ thống thông tin của con người có lịch sử phát triển từ rất lâu. Cho tới nay, đã có rất nhiều các hệ thống thông tin dưới các 1.1.2.1. TDM (Time Division Multiplexing): hình thức đa dạng. Các hệt hống thông tin này được gán cho các TDM là phương pháp ghép kênh phân chia theo thời gian. tên gọi nhất định theo môi trường truyền dẫn và đôi khi theo cả tính Đây là phương pháp giúp tăng số lượng tín hiệu được gửi trên chất dịch vụ của hệ thống. So với hệ thống thông tin hiện đại đầu đường truyền vật lý. tiên là thông tin điện báo (đưa vào khai thác năm 1844) thì hệ thống thông tin quang (mới được khai thác từ những năm 1980) là hệ thống có tuổi đời còn khá trẻ. Tuy vậy cùng với sự phát triển của các dịch vụ mạng và đòi hỏi ngày càng cao về dung lượng và băng thông, hệ thống thông tin quang cũng đã phát triển rất mạnh mẽ về công nghệ trong gần 3 thập niên qua. Do có ưu điểm như vậy nên các hệ thống thông tin quang nhanh chóng được áp dụng rộng rãi trên mạng lưới. Chúng còn tiềm tàng những khả năng rất lớn trong việc hiện đại hoá các mạng lưới viễn thông trên thế giới. Hình 1.1 : Ghép kênh theo thời gian
3 1.1.2.2. SONET/SDH: vi công ty cho đến thiết bị quang gán trực tiếp vào SONET/SDH. SONET (Sychronous Optical Network : Mạng quang đồng Công nghệ Ethernet Gigabit hỗ trợ cả cáp sợi quang đơn mode và bộ) là một chuẩn của American National Standards Institute để đa mode. Tuy vậy, các khoảng cách được hỗ trợ tùy vào các kiểu truyền dữ liệu đồng bộ trên môi trường truyền là cáp sợi quang. cáp sợi quang và bước sóng được thực thi trong ứng dụng. Tương đương với SONET về mặt quốc tế là SDH. 1.1.3. Hệ thống thông tin quang nhiều kênh SONET/SDH lấy các luồng n bit, ghép chúng lại, điều chế quang Trên thực tế, sự ra đời của các hệ thống quang đa kênh đã giải tín hiệu và sử dụng thiết bị phát quang để gửi nó ra ngoài với một quyết được những hạn chế của hệ thống đơn kênh, đồng thời cũng tốc độ bit tương đương với : (tốc độ bit đi vào)  n . Vì vậy lưu tận dụng được những công nghệ hiện có để phát triển mạnh mẽ. Cụ lượng đi đến bộ ghép kênh SONET tù bốn đầu vào với tốc độ 2,5 thể là : Gbps sẽ đi ra như một luồng đơn ở tốc độ 4  2,5 Gbps = 10 Gbps. Nguyên tắc này được minh họa trong hình 1.2. Thứ nhất, đối với hệ thống đơn kênh, khi tốc độ đạt tới mức khoảng vài chục Gbit/s thì khoảng cách tuyến truyền dẫn sẽ bị rút ngắn lại, các thiết bị điện tử sẽ đạt đến giới hạn của nó và không đáp ứng được các xung tín hiệu cực kì hẹp; thêm vào đó chi phí dành cho các giải pháp trên tuyến truyền dẫn trở nên tốn kém vì cấu trúc, thuật toán phức tạp và đòi hỏi các thiết bị có công nghệ cao. Thứ hai, kỹ thuật ghép kênh quang được sử dụng sẽ tận Hình 1.2 : Nguyên tắc ghép kênh trong mạng SONET dụng được phổ hẹp của Laser, tận dụng được băng tần rất lớn của sợi quang. SONET cung cấp các chuẩn cho một số lượng lớn các tốc độ 1.1.4. Nguyên lý cơ bản của ghép kênh theo bước sóng quang. truyền (tốc độ truyền thực tế vào khoảng 20 Gbps). Nguyên lý cơ bản của ghép kênh theo bước sóng mang có 1.1.2.3. Gigabit Ethernet: thể minh họa như hình 1.3. Công nghệ Ethernet 10 Gigabit được xây dựng trên nghi thức Ethernet, nhưng có tốc độ nhanh gấp 10 lần Ethernet (1000 Mbps). Ethernet Gigabit được triển khai như một công nghệ xương sống cho các mạng đô thị. Đối với mạng diện rộng WAN, Ethernet 10 Gigabit cho phép các ISP (Internet Service Provider) và NSP (Network Service Provider) tạo ra các liên kết tốc độ rất cao với giá Hình 1.3 : Quá trình ghép và giải ghép WDM thành thấp từ các bộ chuyển mạch và các bộ định tuyến trong phạm
4 1.1.5. Mục đích công nghệ WDM. 1.2. Định tuyến và gán bước sóng trong mạng WDM. Do băng thông quang rất lớn nên nếu chỉ sử dụng cho mục đích đơn lẻ sẽ rất hao phí. Vì vậy sử dụng công nghệ WDM nhằm 1.2.1. Định tuyến (Routing) mục đích tận dụng băng tần truyền dẫn của sợi quang bằng cách 1.2.1.1. Giới thiệu truyền đồng thời nhiều kênh bước sóng trên cùng một sợi quang. Định tuyến được coi là thành phần cốt yếu của kiến trúc 1.1.6. Phân loại hệ thống truyền dẫn WDM. mạng, thiết kế mạng và điều hành mạng của mọi mạng thông tin, là thành phần không thể thiếu trong mạng viễn thông. 1.1.6.1. Hệ thống ghép bước sóng đơn hướng: Chỉ thực hiện truyền theo một chiều trên sợi quang. Do vậy 1.2.1.2. Phân loại định tuyến để truyền thông tin giữa hai điểm cần hai sợi quang. Có nhiều cách phân loại định tuyến, có thể đưa ra một số loại định tuyến như sau:  Dựa vào chức năng thích nghi với trạng thái hiện thời của mạng để phân loại thành: định tuyến tĩnh và định tuyến động + Định tuyến tĩnh: với định tuyến tĩnh, đường dẫn được chọn trước cho mỗi cặp nguồn – đích của các node trong mạng. + Định tuyến động: định tuyến động lựa chọn tuyến dựa trên thông tin trạng thái hiện thời của mạng. Hình 1.4: Hệ thống WDM đơn hướng  Dựa vào phạm vi định tuyến, ta phân loại thành: định tuyến trong và định tuyến ngoài. 1.1.6.2. Hệ thống ghép bước sóng song hướng: Định tuyến trong: định tuyến xảy ra bên trong một hệ thống Có thể truyền theo hai chiều trên một sợi quang nên chỉ cần độc lập (AS – Autonomous System), các giao thức thường dùng là một sợi quang để có thể trao đổi thông tin giữa hai điểm. RIP (Router Information Protocol), IGRP (Interior Gateway Routing Protocol), OSPF (Open Shortest Path First), EIGRP (Enhanced IGRP),… Định tuyến ngoài: định tuyến xảy ra giữa các hệ thống độc lập (AS), liên quan tới dịch vụ của nhà cung cấp mạng sử dụng giao thức định tuyến ngoài rộng và phức tạp. Giao thức thường Hình 1.5: Hệ thống WDM song hướng dùng là BGP (Border Gateway Protocol).
5 Điều kiện tính riêng biệt về bước sóng: tất cả các lightpath sử dụng cùng một link (fiber) phải được gán các bước sóng riêng biệt. Hình 1.6: Định tuyến trong và định tuyến ngoài 1.2.2. Định tuyến và gán bước sóng (Routing and Wavelength Assignment - RWA). Tìm đường được hiểu theo hai khía cạnh, đó là tìm đường vật lí mang được mẫu lưu lượng yêu cầu (Routing) và đưa ra bước Hình 1.8: Mạng WDM định tuyến bước sóng sóng phù hợp để mang lưu lượng trên mỗi link dọc path (Wavelength Assignment) trong số các bước sóng cho phép (bởi 1.3. Động cơ và mục tiêu nghiên cứu. mỗi path gồm một số fiber, mà trên mỗi fiber này, bạn có thể có W 1.3.1. Động Cơ sub-chanels, cũng là W bưóc sóng và W lựa chọn cho yêu cầu kết nối hiện tại). Vấn đề này được viết tắt là RWA. Rắc rối đặt ra đối Để giải bài toán thiết kế đa mục tiêu, các kỹ thuật tối ưu hóa với bài toán RWA là nó đưa ra hai điều kiện sau: đa mục tiêu thường được sử dụng. Một số phương pháp sử dụng Điều kiện tính liên tục bước sóng: một lightpath phải sử các gần đúng đơn mục tiêu để giải các bài toán đa mục tiêu như dụng chung một bước sóng trên tất cả các link dọc theo đường đi ràng buộc  và tổng trọng số. Tuy nhiên các gần đúng đơn mục tiêu của nó từ nguồn đến đích. có một nhược điểm là rất khó tìm được các nghiệm tối ưu. Do vậy mà các thuật toán tiến hóa đa mục tiêu được áp dụng để giải các bài toán thiết kế đa mục tiêu này. 1.3.2. Mục tiêu nghiên cứu Nghiên cứu giải quyết bài toán định tuyến và gán bước sóng đa mục tiêu trong mạng WDM bao gồm: + Xây dựng bài toán RWA như là một bài toán tối ưu đa mục tiêu. Hình 1.7: Điều kiện tính liên tục bước sóng
6 + Giải bài toán RWA được xây dựng ở trên bằng thuật toán Đề tài cũng làm cơ sở định hướng nghiên cứu cho các đề tài di truyền để tối ưu hóa các tham số mạng khác nhau. tốt nghiệp của sinh viên đại học và cho các nghiên cứu chuyên sâu tiếp theo đối với sinh viên cao học. 1.4. Nội dung và đóng góp của luận văn. CHƯƠNG 2:ĐỊNH TUYẾN VÀ GÁN BƯỚC 1.4.1. Nội dung của luận văn SÓNG TRONG MẠNG WDM Nội dung của luận văn dự kiến sẽ được chia thành 4 chương với những nội dung cụ thể như sau: Chương 1: Trình bày tổng quan về mạng WDM, các vấn đề 2.1. Giới thiệu bài toán RWA. cơ bản về định tuyến và gán bước sóng trong mạng WDM, nhiệm vụ, hướng nghiên cứu và những đóng góp của luận văn. Phân loại bài toán RWA được thể hiện trong Bảng 2.1. Chương 2: Giới thiệu bài toán RWA, các mục tiêu thiết kế, Bảng 2.1: Phân loại RWA các phương pháp tiếp cận bài toán RWA: heuristic và meta- Phân loại RWA heuristic. Kiểu lưu lượng Static,Dynamic Chương 3: Trình bày bài toán tối ưu hóa đa mục tiêu, các giải thuật tiến hóa trong tối ưu hóa đa mục tiêu, các giải thuật di Hàm mục tiêu Max-RWA,Min-RWA truyền trong RWA đa mục tiêu. Công thức ILP Link-based, Path-based Chương 4: Trình bày mô hình mô phỏng RWA đa mục tiêu, cách thức giải bài toán RWA đa mục tiêu bằng phương pháp tính Chuyển đổi bước sóng Full,Sparse,None toán tiến hóa lai và kết quả mô phỏng bài toán RWA. Cáp quang Single,Multiple 1.4.2. Những đóng góp của luận văn. Yêu cầu Request multiplicity Kết quả của đề tài có thể ứng dụng cho thiết kế mạng quang RWA bài toán được coi là một bài toán NP-đầy đủ. Phức tạp định tuyến bước sóng WDM hiệu quả hơn. Bằng việc sử dụng tiếp của bài toán RWA phát sinh từ hai sự kiện sau đây: cận đa mục tiêu thay cho chỉ xem xét từng mục tiêu một cách độc (i) Ràng buộc bước sóng liên tục : Một lightpath phải chiếm lập, nghiệm thu được trong việc giải bài toán RWA bằng phương cùng bước sóng trên tất cả các sợi liên kết mà qua đó nó đi qua. pháp tiến hóa lai cho kết quả khả thi tốt hơn, hay nói cách khác nó (ii) Ràng buộc bước sóng riêng biệt: Hai lightpaths phải cung cấp cho nhà thiết kế mạng những thông tin bù trừ bổ ích giữa không được chỉ định cùng một bước sóng trên một liên kết nào. nhiều mục tiêu khác nhau. Hơn nữa các thuật toán tiến hóa được nghiên cứu có thể áp dụng cho việc điều khiển mạng quang định tuyến bước sóng động một cách hiệu quả hơn.
7 2.2. Cách tiếp cận heuristic đối với bài toán RWA. Zhong Pan [21] phát triển một chức năng phù hợp mới để Chlamtac[8] đề xuất khái niệm về Lightnet kiến trúc để đối giải quyết các bài toán con của của bài toán RWA bằng cách sử phó với các vấn đề không phù hợp giữa tốc độ xử lý điện tử và dụng thuật toán di truyền. Mục tiêu là để định tuyến mỗi lightpath truyền dẫn quang băng thông trong WDM dựa trên các mạng diện theo cách để giảm thiểu số lượng bước sóng cần thiết để nhường rộng. quyền tất cả các lightpaths tĩnh. Các mục tiêu thứ yếu là giảm thiểu Zhang và Acampora[26] đã đề xuất một thuật toán hiệu quả chi phí trong việc thiết lập các lightpaths. để gán một số giới hạn các bước sóng giữa các trạm truy cập của D. Bisbal[5] đề xuất một thuật toán di truyền để thực hiện mạng trong đó các phương tiện vật lý bao gồm các phân đoạn sợi định tuyến động và gán bước sóng trong định tuyến bước sóng quang được kết nối qua các thiết bị chuyển mạch bước sóng quang mạng quang không có bước sóng chuyển đổi. chọn lọc. Le[15] đã đề xuất một thuật toán di truyền cải tiến để giải Banerjee [4] đã xem xét các vấn đề thiết kế một cấu trúc liên quyết bài toán RWA động. Để đạt được cân bằng tải tốt hơn giữa kết mạng quang học hợp lý cho một mô hình vật lý và một ma trận các cá thể, họ đã xây dựng một hàm thích hợp mới, đồng thời liên nhu cầu giao thông giữa những người sử dụng cuối cùng. quan đến chiều dài đường đi, số bước sóng tự do và khả năng Banerjee và Mukherjee[2] đã trình bày một công thức lập chuyển đổi bước sóng trong tuyến đường đánh giá. trình tuyến tính số nguyên để đưa ra một giải pháp tối thiểu khoảng cách bước nhảy đến các vấn đề thiết kế cấu trúc liên kết ảo trong 2.4. Các mục tiêu thiết kế trong bài toán RWA. một mạng bước sóng định tuyến quang học, trong trường hợp Bài toán thiết kế đa mục tiêu được thể hiện với các hàm đa không có ràng buộc bước sóng liên tục. mục tiêu thường được giải quyết với "kỹ thuật tối ưu hóa đa mục tiêu". Tối ưu hóa đa mục tiêu là một kỹ thuật để tìm ra giải pháp tốt 2.3. Cách tiếp cận meta-heuristic đối với bài toán RWA. nhất từ các giải pháp lớn có thể xem xét tất cả các mục tiêu cùng Các giải pháp meta Heuristic thiết kế các cấu trúc liên kết một lúc. trong khu vực mạng mesh diện rộng để giảm thiểu chi phí mạng. Có một số nghiên cứu[20] được lồng ghép trong các tài liệu Các thuật toán di truyền đã được sử dụng để giải quyết bài toán mà hình thành heuristics và meta-heuristics cho việc thiết kế hiệu RWA theo giả định khác nhau. Các tác giả đã xây dựng các vấn đề quả của biểu đồ tổng quát dựa trên các cấu trúc liên kết mạng. RWA tĩnh trong các mạng quang học là một vấn đề tối ưu hóa mục tiêu duy nhất và giải quyết nó bằng cách sử dụng một thuật toán CHƯƠNG 3: tiến hóa. MC Sinclair[23] đã đề xuất một chi phí tối thiểu định tuyến MÔ HÌNH ĐA MỤC TIÊU CHO BÀI TOÁN RWA đường đi bước sóng và phương án phân bổ bước sóng bằng cách sử dụng một thuật toán di truyền / Heuristic dựa trên thuật toán lai ghép.
8 3.1. Xây dựng bài toán đa mục tiêu. 1 nếu lightpath k giữa cặp nút (i, j) được thiết  Bài toán RWA là một bài toán tối ưu hóa tổ hợp và một loạt Bk ,e (i, j )  (i,j) = lập bước sóng w với liên kết e các phương pháp tối ưu đã được sử dụng để giải quyết bài toán này. 0 nếu không Các bài toán RWA có thể được mô hình hóa như một bài toán lập trình số nguyên tuyến tính (ILP) và giải quyết ILP được đảm bảo để cung cấp cho các tối ưu toàn phần 3.1.3. Xây dựng ILP đa mục tiêu. 3.1.1. ký hiệu sử dụng. Trong phần này, xây dựng các bài toán RWA như là một bài Ký hiệu được sử dụng trong việc xây dựng ILP được quy toán đa mục tiêu ILP. Lightpaths được nhóm lại theo cặp nút định như sau: + V = Thiết lập các nút trong mạng. nguồn-đích của nó. K là tập hợp các yêu cầu lightpath. Thì K được + E = Thiết lập các liên kết sợi hai chiều trong mạng. tính theo công thức: + W = Thiết lập các kênh bước sóng không nhiễu hỗ trợ bởi tất cả các liên kết sợi trong mạng. K  K (i, j ); K (i, j)  K ( j, i) | andi  j ( i , j )V V + (i,j) Là cặp nút nguồn-đich; {i,j}  V. + D = Ma trận nhu cầu của các yêu cầu kết nối, nơi Dij dùng  D iV jV ij để chỉ một giá trị đầy đủ ghi rõ nhu cầu tối đa giữa các cặp nút (i, j) K  2 và Dij = Dji. +  -(v) = Thiết lập các liên kết sợi được sử dụng bởi K (i, j )  K ( j , i)  Dij  D ji 3.1 lightpath vào nút v. Các hàm mục tiêu mà chúng ta muốn tối ưu hóa được quy định như + +(v) = Thiết lập các liên kết sợi được sử dụng bởi lightpath rời khởi nút v. sau: 3.1.2. Các biến sử dụng + Giảm thiểu ách tắc của nhiều nhất liên kết tắc nghẽn trong Các biến được sử dụng trong việc xây dựng ILP được quy mạng: định như sau: w, e 1 nếu lightpath k giữa cặp nút (i, j) được thiết lập Minimize max   b k ( i, j ) (3.4) Bk(i,j) = eE ( i , j )V V : Dij 0 kK ( i , j ) wW 0 nếu không  1 nếu lightpath k giữa cặp nút (i, j) được thiết lập bước Bk (i, j )  sóng w 0 nếu không
9 + Giảm thiểu sự khác biệt giữa tắc nghẽn nhiều nhất và tắc Minimize max  (d e |  bkw, e (i, j )  0 (3.9) k  K ( i , j ) eE wW nghẽn ít nhất liên kết trong mạng: ( i , j ):Dij 0 Trong đó de = Trễ liên quan đến liên kết e. w,e w,e Min max { eE   b (i, j ) V:Dij 0 kK (i, j ) w V W k (i, j)  min eE   b (i, j ) V :Dij 0 kK (i, j ) w V W k (i, j) } (3.5) + Hạn chế tối đa tổng chiều dài tuyến đường: w,e + Giảm thiểu sự khác biệt giữa các liên kết tắc nghẽn nhiều Minimize    (d |  b ( i , j ): Dij  0 k K ( i , j ) e E e wW k (i, j )  0) (3.10) nhất và ùn tắc trung bình của tất cả các liên kết trong mạng: 3.2. Các giải thuật tiến hóa trong tối ưu hóa đa mục tiêu. w,e   b k (i, j) w,e (i, j ) V:Dij 0 kK (i, j ) w V W 3.2.1. Thuật toán đáp ứng tiến hóa. Min { max eE   b k (i, j)  E } (3.6) (i, j ) V:Dij 0 kK (i, j ) w V W EA là một thủ tục lặp ngẫu nhiên để tạo ra các nghiệm thăm dò cho một bài toán P nào đó. Thuật toán điều khiển một bộ sưu tập P + Hạn chế số lượng tối đa của bước nhảy đi qua trung gian: của các cá nhân (quần thể), một trong số đó bao gồm một hoặc nhiều nhiễm sắc thể. Các nhiễm sắc thể này cho phép mỗi cá nhân Minimize max   bkw, e (i, j ) (3.7) đại diện cho một nghiệm tiềm năng cho các bài toán đang được k  K (i , j ) eE wW xem xét. ( i , j ):Dij 0 Toàn bộ quá trình được phác thảo trong hình 3.1. + Giảm thiểu số lượng các liên kết sợi được sử dụng để cho tất cả các lightpaths: w, e Minimize {e  E |   b ( i , j ): Dij  0 k K ( i , j ) wW k (i, j )  0} (3.8) Hình 3.1: Tác giả của phương pháp tiến hóa để tối ưu hóa. + Hạn chế chiều dài tuyến đường tối đa: Thuật toán tiến hóa như sau: 1. P ← áp dụng ι trên G để có được các cá nhân μ (quản thể ban đầu);
10 2. while Tiêu chuẩn kết cuối không được đáp ứng do a.Nếu kích thước của Pt 1 vượt quá thì loại bỏ các (a) P0 ← áp dụng σ trên P; / * lựa chọn * / cá nhân có tối thiểu k- khoảng cách hàng xóm gần nhất trong Pt 1 (b) P00 ← áp dụng ω1, · · ·, ωk P0; / * sinh sản * / cho đến khi Pt 1 = N (c) P ← áp dụng ψ trên P và P00; thay thế / * / Endwhile. b.Nếu kích thước của Pt 1 là ít hơn so với N thì Điền Quá trình này được lặp đi lặp lại cho đến khi một tiêu chí Pt 1 với các cá nhân chiếm ưu thế trong Pt và Pt . chấm dứt nhất định (thường là đạt được một số lượng tối đa lần lặp 6. Biến đổi và đảo chéo các cá nhân trong Pt. lại) được thỏa mãn. Mỗi lần lặp của quá trình này thường được gọi 7. Lặp lại các bước 2-6, cho đến khi thỏa mãn với số lượng là một thế hệ. tối đa của lặp. 3.2.2. Giải thuật SPEA2 3.3. Các giải thuật di truyền trong RWA đa mục tiêu. Thuật toán tiến hóa cải tiến đầy đủ Pareto (SPEA2) ) là nổi Thuật toán di truyền (GA) đã được sử dụng để giải quyết bài toán tiếng như là một kỹ thuật hiệu quả để tìm kiếm tập hợp Pareto tối tối ưu hóa đa mục tiêu ở một số lĩnh vực. Khả năng GA đa mục ưu trong bài toán tối ưu hóa đa mục tiêu chung. SPEA2 đã được đề tiêu được khuyến khích để tìm kiếm theo hướng đúng Pareto trước xuất bởi Zitzler[29]. SPEA2 là một thuật tiến hóa đa mục tiêu toán trong khi vẫn duy trì sự đa dạng trong quần thể. Đầu tiên, thế hệ thứ hai (MOEA), thành công của thuật toán được sử dụng để Schaffer[24] đề xuất đánh giá thuật toán di truyền vector tiến giải quyết một số vấn đề kỹ thuật. hóa(VEGA) để giải quyết tối ưu hóa đa mục tiêu trong từng mục N đại diện cho kích thước quần thể, N là kích thước lưu trữ. tiêu riêng biệt và kết hợp các con hoặc các quần thể của từng mục 1. Tạo một cá thể ban đầu P0 và tạo khoảng trống lưu trữ P0 . tiêu lại với nhau. Các nghiệm thu được từ VEGA vô cùng nhiều cho từng mục tiêu. Fonseca và Fleming[11] đề xuất một thuật toán 2. Tính toán số lượng yêu cầu kết nối được chấp nhận và các tiêu di truyền đa mục (MOGA) để tìm kiếm các nghiệm trong tất cả kênh bước sóng yêu cầu, bằng cách sử dụng GA-MDF. các hướng có thể không gian mục tiêu. 3. Tính toán giá trị sức mạnh của các cá nhân trong Pt và Pt . Ví dụ về GA thảo luận bởi Konak trong[13] bao gồm các 4. Xếp hạng cá nhân theo giá trị sức mạnh của họ và k- thuật toán di truyền đa mục tiêu khác nhau. Thảo luận này phân khoảng cách hàng xóm gần nhất nơi loại các thuật toán di truyền đa mục tiêu dựa trên các tính năng của gán độ hợp lý và xếp hạng nghiệm thành bốn nhóm: k NN (3.26) 5. Môi trường lựa chọn 1. Hàm tổng hợp các mục tiêu chuẩn hóa. a. GA dựa trên trọng số (WBGA).
11 b. GA trọng số ngẫu nhiên (RWGA). giảm thiểu số lượng bước sóng yêu cầu. Điều này cho phép một số 2. So sánh trực tiếp của độ chi phối Pareto. yêu cầu liên lạc nhất định bị chặn để tiết kiệm một số kênh bước a. GA đánh giá vector (VEGA). sóng. Yêu cầu liên lạc đã được gán thành công với một bước sóng b. Niched Pareto GA (NPGA). được gọi là "yêu cầu được chấp nhận". Hàm mục tiêu của bài toán 3. Tiếp cận xếp hạng cụ thể. bao gồm: a. GA Đa mục tiêu (MOGA). 1. Mục tiêu thiết kế đầu tiên là để tối đa hóa số lượng yêu b. GA xếp loại không bị chi phối (NSGA) và GA xếp loại nhanh không bị chi phối (NSGA-II). cầu kết nối được chấp nhận. Một số lượng lớn các yêu cầu chắc c. Thuật toán tiến hóa đầy đủ Pareto (SPEA) và bản chắn đòi hỏi một số lượng lớn các kênh truyền dẫn (hay được gọi là cải thiện SPEA là (SPEA2). các kênh bước sóng). Mục tiêu thiết kế này là tùy vào số lượng giới 4. Phương pháp tiếp cận dựa trên không dân cư. hạn kênh bước sóng trên mỗi cạnh mạng. a. Chiến lược tiến hóa Pareto lưu trữ (PAES). 2. Mục tiêu thiết kế thứ hai là để giảm thiểu số lượng bước CHƯƠNG 4: MÔ PHỎNG VÀ ĐÁNH GIÁ KẾT sóng yêu cầu trên mỗi cạnh trong khi thỏa mãn một giá trị mục tiêu QUẢ về yêu cầu kết nối được chấp nhận. Ta giả định rằng mỗi cạnh 4.1. Mô hình mô phỏng. mạng có cùng số lượng bước sóng. Mục tiêu thiết kế này là để Trong phần này, bài toán thiết kế RWA đa mục tiêu và mô giảm thiểu số lượng các bước sóng trong khi đáp ứng được lượng hình thiết kế sẽ được trình bày. Bài toán RWA trong thiết kế mạng yêu cầu được chấp nhận. quang WDM được xem xét để hỗ trợ nhiều yêu cầu liên lạc đồng Thông tin đã cho: thời (bài toán luồng đa yêu cầu kết nối).. Mỗi yêu cầu kết nối có rất - Cấu hình mạng nhiều tuyến có thể và mỗi tuyến có một số lựa chọn gán kênh bước sóng. Bài toán thiết kế mạng trong chương này là để tối đa hóa số - Tập các yêu cầu (tức là, các cặp nút nguồn đích với yêu yêu cầu được chấp nhận từ một tập các yêu cầu đã định sẵn và để cầu băng thông).
12 Tối thiểu hóa: KA   k (4.10) k K - f obi  min{ f c  f w } (4.1) QA T (4.11) Q  QA Q - fc  (4.2) Q e,k  eE q  H ; q  Q, k  K (4.12) KA - fw  (4.3) K max e,k  ( D . eE e q )  L; q  Q, k  K (4.13) Tùy theo:  q  {0,1}; q  Q (4.14)   q , i  sourceq e, k e, k  k  {0,1}; k  K (4.15)   q    q   q , i  Destq q  Q, i  N (4.4) eE (*,i ) k  K eE ( i ,*) k  K  0, otherwise k  q  {0,1}; q  Q, k  K (4.16)  qe , k   qk ; q  Q, e  E, k  K (4.5)  qe , k  {0,1}; q  Q, k  K , e  E (4.17) k  q  1; q  Q (4.6) k K 4.2. Định tuyến và gán bước sóng sử dụng phương pháp tiến hóa lai. e, k  k K q   q ; q  Q, e  E (4.7) Phần này sẽ trình bày các thuật toán được sử dụng để giải quyết bài toán định tuyến gán bước sóng đa mục tiêu. Ta xem xét QA    q (4.8) bài toán RWA tối đa hóa số lượng yêu cầu được chấp nhận và giảm qQ thiểu số lượng các kênh bước sóng yêu cầu cùng một lúc. Bài toán RWA có thể được phân loại vào hai vấn đề, định tuyến và gán e, k  qQ q  k ; e  E , k  K (4.9) bước sóng. Cả hai đều cùng phụ thuộc vào nhau. 4.2.1. Thuật toán NSGA-II
13 Thuật toán di truyền phân loại nhanh không bị chi phối bao gồm nhiều cá thể. Mỗi cá thể trong quần thể sẽ luôn được gán (NSGA-II) được biết như là một kỹ thuật hiệu quả để tìm kiếm tập một thứ hạng hoặc bậc vì lý do đó mà các cá thể ưu tú được duy trì hợp tối ưu Pareto trong bài toán tối ưu hóa đa mục tiêu chung. cho thế hệ sau. Các cá thể ưu tú sẽ có một thứ hạng thấp hơn hoặc NSGA-II là một thuật toán rất nhanh để có thể hội tụ nhanh chóng tốt hơn so với những cá thể khác. Thứ hạng của các nghiệm được về mặt trước Pareto. NSGA-II đã được đề xuất bởi Deb[11] và tính toán từ sắp xếp không bị chi phối nhanh trước. Sau đó, các được mô tả như sau. nghiệm trong cùng một mặt trước được sắp xếp bằng việc sử dụng Gọi Rt là đại diện cho tổng số quần thể, Pt là quần thể được thuật tóan gán khoảng cách tạo đám.. Việc phân hạng được thể hiện bảo tồn, Qt là quần thể được tái tổ hợp của thế hệ t. Fi là mặt trước trong thủ tục 1 và 2 trong hình 4.2. i, trong đó i là một số nguyên dương. Lưu ý rằng các nghiệm trong mặt trước F1 là tốt hơn so với những nghiệm trong mặt trước của F2, và cứ như vậy tiếp tục. 1. Kết hợp Pt và Qt để Rt. 2. Tính toán số lượng yêu cầu kết nối được chấp nhận và các kênh bước sóng yêu cầu, bằng cách sử dụng GA-MDF (được mô tả trong Phần 4.2.2) 3. Gán mỗi quần thể trong Rt cho mặt trước (F1, F2, F3, ... ) bằng cách sử dụng thuật toán sắp xếp nhanh không bị chi phối (Rt). 4. Tính khoảng cách tạo đám trong mỗi Fi bằng cách sử dụng thuật toán gán khoảng cách tạo đám (Fi). 5. Xếp loại quần thể Rt (sắp xếp theo bậc mặt trước (Fi) theo thứ tự tăng dần và khoảng cách tạo đám theo thứ tự giảm dần. 6. Chọn lựa chỉ có một nửa đầu tiên của quần thể Rt và gán cho Pt+1. 7. Tái kết hợp (qua lai tạo và đột biến) quần thể Pt +1 và gán Hình 4.2: Thủ tục NSGA-II cho Qt+1. 8. Tăng vòng lặp (t = t + 1). 9. Lặp lại bước 1-8, cho đến quá trình lặp được thỏa mãn 4.2.1.1. Gán độ hợp (Fitness assignment) bởi số lần lặp tối đa. NSGA-II xếp thứ hạng cho cá thể i trong quần thể sử dụng Từ thuật toán NSGA-II, hai thủ tục quan trọng của NSGA-II bậc mặt trước (Fi) và khoảng cách tạo đám (Di). Các bậc mặt trước bao gồm thủ tục gán độ hợp (xếp loại không bị chi phối nhanh và (Fi) được gán bằng cách sử dụng thuật toán sắp xếp không bị chi gán khoảng cách tạo đám) và thủ tục lựa chọn. Quần thể xem xét
14 phối nhanh [11] và khoảng cách tạo đám được tính bằng thuật toán gán khoảng cách tạo đám [11]. Phương pháp sắp xếp nhanh không bị chi phối 4.2.1.2. Thủ tục lựa chọn Gọi Fi là mặt trước i trong đó i là số nguyên dương. Ban đầu, cá thể có một bậc mặt trước thấp hơn sẽ được 1. Đối với mỗi cá thể p trong quần thể chọn. Nếu không gian có sẵn của quần thể trong thế hệ tiếp theo a. Tìm tập các cá thể bị chi phối bởi p. không thể hỗ trợ toàn bộ các cá thể trong mặt trước Fi, cá thể trong b. Tìm các thể không bị chiếm ưu thế và gán cho mặt cùng một mặt trước có khoảng cách tạo đám lớn hơn sẽ được lựa trước F1 trước tiên. chọn trước tiên như thể hiện trong thủ tục 3 hình. 4.2. 2. Gán các cá thể khác cho mặt trước thứ hai, thứ ba, và tiếp Thủ tục lựa chọn đó, cho đến khi tất cả các cá thể đều có mặt trước của chúng. 1.Đối với mỗi cá thể i Gán khoảng cách tạo đám (Crowding-distance- a. Chọn toàn bộ các cá thể có bậc mặt trước thấp hơn assignment) trước tiên. Gọi Fi là mặt trước i trong đó i là số nguyên dương, Di là b. Nếu toàn bộ các cá thể trong mặt trước Fi không khoảng cách tạo đám của nghiệm i trong mặt trước Fi, N là số thể được lấp đầy trong không gian có sẵn trong các thế hệ tiếp theo, lượng nghiệm trong mặt trước Fi, f mmax và f mmin là các giá trị cực đại thì chọn các cá thể có số khoảng cách tạo đám lớn hơn trước tiên. và cực tiểu của mục tiêu m. 1. Thiết lập khoảng cách tạo đám của cá thể i (Di) = 0, cho 4.2.2.Thuật toán di truyền cho việc định tuyến và gán bước sóng tất cả các cá thể trong Fi. theo bậc tối thiểu trước tiên (GA-MDF) 2. Đối với mỗi mục tiêu m Thuật toán này là một thuật toán heuristic gọi là thuật toán a. Sắp xếp theo thứ tự tăng dần các cá thể i theo giá di truyền cho việc định tuyến với việc gán bước sóng bậc tối thiểu trị mục tiêu fm. trước tiên (GA-MDF). GA-MDF có hai phần là định tuyến bằng b. Đặt khoảng cách tạo đám (Di) của các cá thể trong thuật toán di truyền và gán bước sóng theo bậc tối thiểu trước tiên. bậc đầu tiên và bậc cuối cùng =  (tức là, D1 =  và DN = ) c. Đối với tất cả các cá thể khác (i = 2 tới N-1). Tính 4.2.2.1. Thuật toán di truyền cho định tuyến khoảng cách tạo đám của cá thể i sử dụng Trước đây, thuật toán di truyền được sử dụng để giải quyết ( f (i  1)  f (i  1)) bài toán định tuyến trong mạng quang WDM [3]. Banerjee và Di  Di  m max mmin ( f m  fm Sharan đã đề xuất một thuật toán di truyền dựa trên tiếp cận định tuyến luân phiên cố định. Cá thể có giá trị khoảng cách nhỏ có nghĩa là nó được tạo đám nhiều hơn so với những cá thể khác. Cá thể mà cách xa khỏi Mã hóa chuỗi: Mã hóa chuỗi là một quá trình mã hóa bài những cá thể khác sẽ được lựa chọn trước tiên. Thủ tục lựa chọn toán tổ hợp thành một tập hợp các gen hoặc nhiễm sắc thể. Mã hóa này được trình bày như sau. chuỗi ở đây, là một tập hợp các số nguyên cái chỉ ra tuyến đường
15 của mỗi yêu cầu kết nối. Giả sử rằng trong bài toán thiết kế mạng có 5 nút mạng như hình 4.4.. Hình 4.6: Một ví dụ của quá lai tạo. Đột biến: Đột biến là quá trình khai thác các nghiệm mới từ các nghiệm hiện có. Một ví dụ của quá trình đột biến được thể hiện trong hình 4.7 Hình 4.4: Một mẫu 5-node mạng Hình 4.7: Một ví dụ của quá trình đột biến Hình 4.5: Một ví dụ về mã hóa chuỗi 4.2.2.2. Gán bước sóng mức độ tối thiểu trước tiên Lai tạo: Lai tạo là quá trình khám phá các nghiệm mới từ (MDF). các nghiệm hiện có. Một ví dụ về quá trình lai tạo được cho thấy Trong gán bước sóng, thuật toán độ tối thiểu trước tiên trong hình 4.6. (MDF) được đề xuất để gán một kênh bước sóng giới hạn cho một tập các yêu cầu. Thuật toán gán độ hợp trước tiên thực hiện gán bước sóng từ chỉ số kênh nhỏ nhất đển chỉ số kênh cao nhất [11]. Còn trong thuật toán này, mức độ tối thiểu ít nhất được gán trước
16 tiên. Giả định rằng mức độ tối thiểu của một đồ thị phụ trợ thể hiện MDF có thể được kiểm tra bởi một mạng nhỏ có quan hệ kiểu sao cho số lượng ít nhất các yêu cầu bị chồng lấn nhau. chồng lấn như hình 4.9. Mối quan hệ chồng lấn thu được từ tập sáu Thuật toán MDF có thể được trình bày như sau: yêu cầu trong NFSNET như thể hiện trong hình 4. 10. Sáu yêu cầu đó là: 1.Sắp xếp tất cả các yêu cầu theo số lượng các mức độ từ Yêu cầu 0: có tuyến đường từ nút 1 đến 12: 1 3 4 mức độ nhỏ nhất đến mức độ lớn nhất. 2. Tại hạng đầu tiên (số lượng mức độ ít nhất, hoặc bị chồng 67 8 12 lấn ít nhất bởi yêu cầu khác), gán bước sóng đầu tiên. Yêu cầu 1: từ nút 0 đến 3: 0  1  3 3. Tại yêu cầu tiếp theo, nếu yêu cầu không bị chồng lấn với Yêu cầu 2: từ nút 3 đến 5: 3 4 5 các yêu cầu trước đó, gán cùng kênh bước sóng tương tự như yêu Yêu cầu 3: từ nút 6 0: 6 7 0 cầu trước đó, nếu không thì gán bước sóng tiếp theo. Yêu cầu 4: từ nút 7 9: 7 8 9 4. Lặp lại bước 3, cho đến khi tất cả các yêu cầu được xem Yêu cầu 5: từ nút 11 đến 12: 11 8 12 xét. Ví dụ MDF Yêu cầu 2 (2): từ nút 2 đến nút 4  kênh bước sóng 1. Yêu cầu 3 (3): từ nút 3 nút 4  kênh bước sóng 1. Bởi vì nó không chồng chéo với yêu cầu kết nối trước đó. Yêu cầu 1 (1): từ nút 1 đến nút 3  kênh bước sóng2. Hình 4.9: Một biểu đồ phụ trợ cho các thuật toán gán bước sóng. Bởi vì nó bị chồng chéo với 2 và 3 Hình 4.8: Một đồ thị phụ trợ cho thuật toán mức độ tối thiểu trước tiên (MDF) Hình 4.10: NFSNET với 14 nút và 42 cạnh.
17 4.2.2.3. Cơ chế xén tỉa trong các thí nghiệm như cho thấy trong các hình 4.10, 4.11 và 4.12 Trước đây, Konak[14], Taboada và Coit[26] đã đề xuất cơ chế để bao gồm mạng NFSNET với 14 nút và 42 cạnh định hướng, mạng cắt giảm nhiều nghiệm không bị chiếm ưu thế trong hai phương CHNNET với 15 nút và 54 cạnh định hướng và mạng ARPANET pháp tiếp cận, đó là thuật toán mức độ ưu tiên xếp hạng và tạo đám với 20 nút và 64 cạnh hướng [30]. Đối với mỗi kích thước bài toán, dữ liệu. Trong phương pháp đầu tiên, người ra quyết định có biết một tập hợp các nhu cầu thông tin liên lạc được khảo sát bằng một mức ưu tiên của từng mục tiêu, xem xét nó theo trật tự để tìm ra tập hợp các kênh bước sóng. Ở đây giả định rằng tất cả các cạnh có nghiệm ưu tiên. Trong phương pháp thứ hai, cắt tỉa bằng cách sử cùng một số khả năng bước sóng. dụng phân nhóm dữ liệu được coi là phù hợp hơn bởi vì người ra quyết định không cần phải biết mức ưu tiên của từng mục tiêu. Trong phần này, nhiều nghiệm (các nghiệm không bị chi phối) thu được từ NSGA-II được cắt bỏ bớt bằng cách sử dụng một thuật toán nổi tiếng phân nhóm dữ liệu (tức thuật toán K-means). Thuật toán K-means cơ bản được thể hiện như sau: 1. Chọn K điểm như là trọng tâm ban đầu. 2. Repeat (Lặp lại) a. Hình thành K cụm bằng cách gán mỗi điểm cho trọng tâm gần nhất với nó. b. Tính toán lại trọng tâm của mỗi cụm Hình 4.11: Mạng lưới Quốc gia Trung Quốc (CHNNET) với 15 nút 3. Until (Cho đến khi) các trọng tâm không thay đổi. và 54 cạnh hướng Độ gần của các nghiệm so với trọng tâm của nó chính là khoảng cách Euclide. Vấn đề chính trong thuật toán K-means là để tìm giá trị thích hợp của K. 4.3 Kết quả mô phỏng. Thiết kế mạng RWA đa mục tiêu với một cấu hình mạng và một tập các yêu cầu đã cho sẽ được xem xét trong một số thí nghiệm. Một số lượng giới hạn các kênh bước sóng trong mỗi cạnh hoặc liên kết của mạng sẽ được áp đặt và ít nhất 80% các yêu cầu phải được chấp nhận. Một tập hợp các bài toán kiểm tra với số Hình 4.12: ARPANET với 20 nút và 64 cạnh hướng. lượng các yêu cầu khác nhau sẽ được tạo ngẫu nhiên theo phân bố đều trong mỗi bài kiểm tra. Các mạng ví dụ khác nhau được chọn
18 Thuật toán GA-MDF được chuẩn hóa với các thuật toán Số yêu cầu được chấp nhận FAR-FF để so sánh. Các kết quả mô phỏng được cho thấy trong các hình 4.13, 4.14, 4.15 và bảng 4.1 chi ra GA-MDF thực hiện tốt hơn so với FAR-FF với 5 tuyến ngắn nhất tiềm năng trong tất cả ba cấu trúc mạng. Số yêu cầu được chấp nhận Số kênh bước sóng Hình 4.15: Các nghiệm không bị chi phối của GA-MDF và FAR-FF thu được từ ARPANET. Số kênh bước sóng Hình 4.13: Các nghiệm không bị chi phối của GA-MDF và FAR-FF thu được từ NFSNET. Số yêu cầu được chấp nhận Số kênh bước sóng Hình 4.14: Các nghiệm không bị chi phối của GA-MDF và FAR-FF thu được từ CHNNET.
19 Bảng 4.1:Thời gian tính toán của GA-MDF và FAR-FF trong mạng khác nhau cấu trúc liên kết với 150 mặt hàng. Network No.of (non- No.of Noof edges Degree CPU times RWA topologies driection) Nodes no.of nodes Total Averge Max Min techniques Average cpu Total cpu edge deg deg deg deg time(s) time (s) NPSNET 21 14 15 42 4 3 2 GA-MDF 14,806.3 44,419.0 FAR-FF 11,986.7 35,960.0 CHN 27 15 18 54 3.6 3 5 GA-MDF 16,512.7 49,538.0 FAR-FF 12,344.7 37,034.0 ARPANET 32 20 1.6 64 3.2 3 4 GA-MDF 29,435.0 88,305.0 FAR-FF 21,540.3 64,621.0 Bảng 4.2 cho thấy các kết quả thu được với tổng số 150 yêu cầu sử dụng tiếp cận Weighted-Sum, trong đó 11 trường hợp giá trị trọng số được xem xét. Những kết quả này (được hiển thị là "○" ) được so sánh với kết quả thu được từ NSGA-II (hiển thị là "×") trong hình 4.16. Số yêu cầu được chấp nhận Số kênh bước sóng 150 yêu cầu Hình 4.16: Kết quả từ phương pháp tiếp cận Weighted-Sum trong các trường hợp khác nhau của trọng số và NSGA-II. Bảng 4.2: Kết quả từ cách tiếp Weighted-Sum với các trường hợp khác nhau của các thông số trọng số (150 mặt hàng). No.of accepted No.of wavelengths No.of accepted {W0,Ww} {W0,Ww} No.of wavelengths used comodities used comodities {1.0,0.0} 123.0 9.0 {0.4,0.6} 127.0 10.0
20 {0.9,0.1} 123.0 9.0 {0.3,0.7} 127.0 10.0 {0.8,0.2} 121.0 9.0 {0.2,0.8} 127.0 11.0 {0.7,0.3} 122.0 9.0 {0.1,0.9} 140.0 13.0 {0.6,0.4} 122.0 9.0 {0.0,1.0} 150.0 17.0 {0.5,0.5} 123.0 9.0 Như được thấy trong Bảng 4.3, thuật toán NSGA-II đòi hỏi nhiều tính toán, với thời gian CPU tính toán trung bình là 14806,3 s đối với trường hợp của 150 yêu cầu thu được từ thuật toán NSGA-II, trong khi thời gian tính toán thu được từ cách tiếp cận Weighted-Sum (với 11 trường hợp trọng số) chỉ là 349,0 x 11 = 3839 s. Bảng 4.3: Số lần lặp lại và thời gian tính toán của tổng trọng (nhiều trọng số) và phương pháp tiếp cận NSGA-II. Weighted-Sum (multiple weights) NSGA-II No.of total comodity Iteration CPU time(s) Iteration CPU time(s) Average (per 1 replication run) 10 33.0 1.0 2400.0 85.0 30 39.2 9.1 2400.0 6.503 50 50.2 32.6 2400.0 1617.7 100 51.0 132.2 2400.0 6403.3 150 58.2 349.0 2400.0 14806.3 Total 10 1090.0 33.0 7200.0 255.0 30 1293.0 300.0 7200.0 1816.0 50 1656.0 1077.0 7200.0 4853.0 100 1684.0 4363.0 7200.0 19210.0 150 1921.0 11518.0 7200.0 44419.0 Đối với các cơ chế xén tỉa, phân nhóm dữ liệu bằng K-means được ở giữa của mặt trước như hình.4.17 (a). Đối với các trường hợp K chọn bởi vì các mục tiêu không được ưu tiên hóa trong phương = 3 và K = 5, các trọng tâm hoặc các đại diện của tất cả các cụm pháp này. Số lượng các nghiệm thu được từ NSGA-II trong cách được thể hiện bằng ký hiệu . tiếp cận này là 31 nghiệm như hình 4.16. Tất cả trong số đó có thể được phân cụm lại bằng cách sử dụng thuật toán K-means. Nghiệm với K = 1 là dễ dàng để đưa ra quyết định và nó được đặt