Luận văn Thuật toán gen trong bài toán định tuyến và phân bước sóng mạng cáp quang

ách tín hiệu: ghép tín hiệu WDM là sự kết hợp một số nguồn sáng khác nhau thành một luồng tín hiệu ánh sáng t ng hợp để truyền dẫn qua sợi quang bằng bộ ghép tín hiệu có tên MUX. Tách tín hiệu WDM là sự phân chia luồng 15 sáng t ng hợp đó thành các t n hiệu ánh sáng riêng rẽ tại mỗi c ng đầu ra bộ tách tín hiệu có tên DE MUX.  Truyền dẫn tín hiệu: quá trình truyền dẫn tín hiệu trong sợi quang ch u sự ảnh hưởng c a nhiều yếu tố như: suy hao sợi quang, tán sắc, các hiệu ứng phi tuyến, vấn đề liên quan đến khuyếch đại tín hiệu,.. Mỗi vấn đề trên đều ph thuộc rất nhiều vào các yếu tố c a sợi quang như: loại sợi quang, chất lượng sợi …  Độ khuyếch đại: hệ thống WDM hiện tại ch yếu sử d ng bộ khuyếch đại sợi quang EDFA (Erbium-Doped Fiber Amplifier ). Khi dùng bộ khuyếch đại EDFA cho hệ thống mạng WDM cần đảm báo các yêu cầu sau • Độ khuyếch đại đồng đều đối với tất cả các kênh bước sóng (mức chiênh lệch không quá 1dB) • Sự thay đ i số lượng kênh bước sóng làm việc không được gây ảnh hưởng đến các mức công suất dầu ra c a các kênh • Có khả n ng phát hiện sự chênh lệch mức công suất đầu vào để điều chỉnh lại vác hệ số khuyếch đại nhằm đảm bảo khuyếch đại đồng đều đối với tất cả các kênh  Thu tín hiệu: là quá trình sử d ng bộ tách sóng quang để lấy ra tín hiệu 2.2.3. Ưu điểm, vấn đề tồn tại và hướng giải quyế ương l i c a hệ thống WDM Thực tế nghiên cứu và triển trai DM đã rút ra được những ưu nhược điểm c a công nghệ DM như sau:  Ưu điểm: • T ng b ng thông truyền trên sợi quang số lần tương ứng với số bước sóng gh p vào để truyền trên mội sợi quang • Có thể hỗ trợ các đ nh dạng số liệu và thoại như: ATM Gigabit Enthernet ESCON, chuyển mạch kênh IP … • Thuận lợi khi cho phép truyền dẫn đồng thời tín hiệu không đồng nhất 16  Vấn đề tồn tại và hướng giải quyết: Với hệ thống WDM, sợi quang cung cấp cho chúng ta tốc độ truyền mong muốn nhưng b ng thông lại b giới hạn bởi tốc độ xử lý ở mỗi node, do tốc độ xử lý ở mỗi node được thực hiện bằng điện tử, mà tốc độ điện tử lại thấp hơn rất nhiền so với tốc độ thông tin truyền trong sợi quang. Như vậy tín hiệu quang trên sợi khi truyền đến node sẽ được chuyển thành các tín hiệu điện để xử lý điện tử(sự chuyển đ i quang – điện O/E sau đó được chuyển lại thành tín hiệu quang để truyền đi Điều này đã làm giảm tốc độ mạng, giải pháp đ t ra là xậy d ng mạng mà trong đó các t n hiệu được xử lý hoàn toàn trong miền quang, gọi là mạng toàn quang (All-Optical Network). Trong mạng toàn quang, dữ liệu đi t nguồn đến đ ch mà không cần bất cứ sự chuyển đ i quang – điện nào trên đường đi việc điều khiển, xử lý chuyển mạch cũng được thực hiện dưới dạng quang. Tuy nhiên mạng toàn quang hiện tại vẫn chưa được tiến hành thành công bởi vì những tồn tại c a nó. Các thiết b logic hoàn toàn trong miền quang khó thực hiện hơn nhiều so với các thiết b logic. Bên cạnh đó các trạm l p bằng quang cũng rất khó thực hiện so với các trạm l p điện tử. 2.3. Định tuyến và gán bước sóng 2.3.1. Giới thiệu chung Trong mạng quang, một kết nối điểm – điểm (point – to – point) giữa hai node được gọi là một lightpath. Lightpath là một đường đi c a tín hiệu ánh sáng t nguồn đến đ ch dưới dạng quang thông qua các kết nối trung gian. Khi các lightpath thực hiên việc mang thông tin t một node nguồn đến một node đ ch nào đó th nó cần được đ nh tuyến và gán bước sóng Đ nh tuyến và gán bước sóng cho lightpath là vấn đ hết sức quan trong và xảy ra thường xuyên trong mạng. Phần này sẽ nói rõ về việc đ nh tuyến và gán bước sóng trong mạng WDM. 2.3.2. Tổng quan về định tuyến và gán bước sóng (RWA) 17 Khi một lightpath được chọn và ác đ nh, mỗi lightpath cần được đ nh tuyến và gán bước sóng cho nó. T đó đ t ra bài toán đ nh tuyến và gán bước sóng. Đ nh tuyến là vấn đề t m đường giữa hai node bất kì trong mạng để thỏa mãn một m c đ ch nào đó gọi là hàm m c tiêu (cost function). Vấn đề này rất quan trọng trong mạng. Bài toán RWA cần thỏa mãn hai điều kiện sau:  Điều kiện về tính liên t c c a bước sóng: mỗi lightpath phải sử d ng chung một bước sóng trên tất cả các link dọc theo đường đi c a nó t nguồn tới đ ch  Điều kiện về tính riêng biệt về bước sóng: nghĩa là tất cả các lightpath sử d ng một sợi quang trên đường đi phải được gán những bước sóng riêng biệt. Bài toán RWA có thể đưa ra như sau: cho một số hữu hạn các lightpath được thiết lập trên mạng và một số hữu hạn các các bước sóng. Ta phải ác đ nh đường đi cho mỗi lightpath và sác đ nh bước sóng gán cho các lighpath sao cho số bước sóng sử d ng là nhỏ nhất. M c dù những đường đi ngắn hơn có v tối ưu hơn nhưng đôi khi ta đành phải loại bỏ lựa chọn này để số bước sóng cần sử d ng là t hơn Các đường đi ánh sáng không thể thiết lập vì những rằng buộc về đường đi hay bước sóng gọi là nghẽn, do vậy vấn đề tối ưu mạng tương ứng với việc hạn chế thấp nhất mức xác suất tắc nghẽn này. Khi hai lightpath mà có tuyến truyền dẫn tr ng nhau th chúng không được gán cùng một bước sóng Thông thường một lightpath hoạt động với cùng một bước sóng trên những sợi quang mà nó đi qua Khi đó ta nói rằng lightpath thỏa mãn rằng buộc về tính liên t c c a bước sóng. Tuy nhiên nếu mạng được trang b các bộ chuyển bước sóng thì điều kiện rằng buộc về tính liên t c c a bước sóng không còn nữa, lighpath này có thể chuyển sang sử d ng nhiều bước sóng trên đường đi t nguồn đến đ ch c a nó. M c dù vậy chi phí cho mỗi bộ chuyển bước sóng là rất cao, cho nên các nghiên cứu hiện nay tập chung giải quyết bài toán với số bộ chuyển bước sóng ít nhất có thể ho c không sử d ng. Và trong khuôn kh khóa luận này bài toán giải quyết là không sử d ng bộ chuyển bước sóng. 18 Trong một mạng không có bộ chuyển bước sóng, các lightpath phải sử d ng cùng một bước sóng t nguồn tới đ ch Khi có nhu cầu cho việc chuyển dữ liệu, bộ đ nh tuyến phải sử d ng giải thuật được thiết lập t trước để chọn một đường đi và bước sóng tương ứng. Sự lựa chọn bước sóng đóng vai trò quan trọng đối với toàn bộ xác suất tắc nghẽn. Vì vậy một bộ đ nh tuyến cần phải t m đường đi cho yêu cầu thiết lập lightpath và thực hiện gán bước sóng sao cho tối thiểu hóa xác xuất tắc nghẽn. Chức n ng này có tầm quan trọng trong việc thiết kế mạng toàn quang. Bài toán R A được chia làm hai loại như sau:  R A dành cho lưu lượng mạng cố đ nh static trafic : đối với loại mạng này thì các yêu cầu về lightpath được biết trước, tất cả mọi đường đi và bước sóng gán cho các lighpath đã được thiết lập cố đ nh t trước(ví d như yêu cầu truyền t Router này đến Router khác là không đ i). Khi đó khi yêu cầu đến, một đường đi và một bước sóng đã được chỉ đ nh t trước đó được gán cho yêu cầu tương ứng đó V vậy quy tr nh đ nh tuyến và gán bước sóng là cố đ nh, không thay đ i theo thời gian. M c đ ch c a phương pháp này là t ng cực đại toàn bộ dung lượng c a mạng, tức là có thể thiết lập số lightpath nhỏ nhất. Mô hình mạng này cũng ch nh là mô h nh mạng được d ng để nghiên cứu thuật toán trong khóa luận này.  R A dành cho lưu lượng mạng thay đ i (dynamic traffic): trong mạng quang đ nh tuyến bước sóng, các yêu cầu về lightpath thay đ i theo thời gian Do đó cần có một giải thuật động để đ nh tuyến các lightpath qua những đường đi khác nhau dựa vào sự tắc nghẽn trên các tuyến truyền dẫn. T đó giải thuật cho bài toán RWA cho mạng lưu lượng động được đưa ra nó dựa vào trạng thái hiện tại c a mạng để ác đ nh đường đi cho mỗi lightpath yêu cầu. 19 Chương : Thuậ án gen 3.1. Giới thiệu Thuật toán gen (GA - Genetic Algorithm) hay thuật toán di truyền là thuật toán tìm kiếm dựa trên chọn lọc tự nhiên và quá trình thích nghi. Thuật toán này được áp d ng cho một loạt các vấn đề phức tạp để tìm ra một lời giải chính xác ho c gần đúng Thuật toán di truyền là một lớp đ c biệt c a thuật toán tiến hóa được lấy cảm hứng t tiến hóa sinh học di truyền, đột biến, lựa chọn và tái kết hợp. Thuật toán gen cũng như các thuật toán tiến hóa nói chung, hình thành dựa trên quang niệm cho rằng: quá trình tiến hóa tự nhiên là quá trình hoàn hảo nhất, hợp lí nhất, và tự nó đã mang t nh tối ưu Quan niệm này có thể được em như một tiên đề luôn luôn đúng không chứng minh được nhưng ph hợp với thực tế khách quan. Quá trình tiến hóa thể hiện tính tối ưu ở chỗ thế hệ sau bao giờ cũng tốt hơn phát triển hơn hoàn thiện hơn thế hệ trước. Tiến hóa tự nhiên được duy trì nhờ hai quá tr nh cơ bản: sinh sản và chọn lọc tự nhiên. Xuyên suốt quá trình tiến hóa tự nhiên, các thế hệ mới luôn được sinh ra, b xung thay thế thế hệ cũ Cá thể nào phát triển hơn th ch ứng hơn với môi trường sẽ tồn tại. Cá thể nào không thích ứng được với môi trường sẽ b đào thải. Sự thay đ i c a môi trường là động lực thúc đẩy quá trình tiến hóa Ngược lại, tiến hóa cũng tác động trở lại góp phần làm thay đ i môi trường Các các thể mới sinh ra trong quá trình tiến hóa nhờ sự lai ghép ở thế hệ cha m . Một cá thể mới sẽ mang những thể trạng c a cha – m (di truyền cũng có thể mang những trạng thái hoàn toàn mới đột biến). Di truyền và đột biến là hai cơ chế có vai trò như nhau trong quá tr nh tiến hóa, dù rằng đột biến xảy ra với xác xuất nhỏ hơn so với hiện tượng di truyền. Các thuật giải tiến hóa tuy có những điểm khác biệt nhưng điều mô phỏng 4 quá tr nh cơ bản: lai gh p đột biến, sinh sản và chọn lọc tự nhiên. 3.2. Thuật toán gen trên máy tính Với khả n ng hiện nay máy t nh đã giúp giải được rất nhiều bài toán khó mà trước kia không thể giải được. M c dù vậy, vẫn còn một số lớn các bài toán chưa có giải thuật 20 hợp lý để giải chúng. Trong số đó bài toán tối ưu là bài toán thường xuyên g p phải trong các ứng d ng thực tế. Bài toán tối ưu có thể được xem như bài toán t m kiếm lời giải pháp (tốt nhất) trong không gian (vô cùng lớn) các giải pháp. Khi không gian tìm kiếm lớn cần phải dùng những kĩ thuật trí tuệ nhân tạo đ c biệt. Thuật toán gen (GA) là một trong những kĩ thuật đó GA là một thuật toán mô tả các hiện tượng tự nhiên: kế th a đấu tranh sinh tồn để cải tiến lời giải và khảo sát không gian lời giải. Khái niệm kế th a và đấu tranh sinh tồn được giải thích qua ví d về sự tiến hóa c a quần thể thỏ như sau: Có một quần thể thỏ, trong số đó có một số con nhanh nh n và thông minh hơn những con khác. Những chú thỏ nhanh nh n và thông minh có xác suất b chồn cáo n th t nhỏ hơn do đó chúng tồn tại để làm những gì tốt nhất có thể: tạo thêm nhiều thỏ tốt Dĩ nhiên một số thỏ chậm chạp, kém thông minh cũng vẫn sống sót bởi may mắn. Quần thể những chú thỏ sống sót sẽ bắt đầu sinh sản. Việc sinh sản này sẽ tạo ra một hỗn hợp tốt về “nguyên liệu di truyền thỏ” Một số thỏ chậm chạp có con với những con thỏ nhanh, một số thỏ nhanh với thỏ nhanh, một số thỏ thông minh với thỏ k m thông minh … M t khác, thiên nhiên thỉnh thoảng đưa vào một vào con thỏ “hoang dã” bằng cách làm đột biến nguyên liệu di truyền thỏ. Những chú thỏ con, sẽ nhanh hơn và thông minh hơn những con trong quần thể gốc vì có nhiều bố m nhanh nh n và thông minh hơn những con trong quần thể gốc (ở bên kia thái cực những con chồn cáo cũng trải qua quá trình tiến hóa tương tự). Khi tìm kiếm lời giải tối ưu thuật toán gen cũng thực hiện các bước tương ứng với câu chuyện đấu tranh sinh tồn c a loài thỏ. Thuật toán gen sử d ng các thuật ngữ vay mượn c a di truyền học. Ta có thể nói các cá thể (hay kiểu gen, cấu trúc), trong một quần thể; những cá thể này cũng được gọi là chuỗi hay các nhiễm sắc thể. Điều này hơi khác so với sinh học: mỗi tế bào c a một ch ng loại sinh học mang một số nhiễm sắc thể nào đó v d ở người là 46 nhiễm sắc thể, ruồi là 8 nhiễm sắc thể nhưng trong thuật toán gen trên máy tính, ta chỉ nói về những cá thể có một nhiễm sắc thể. Các nhiễm sắc thể được tạo thành t các đơn v là các gen biểu diễn trong một chuỗi tuyến tính; mỗi gen kiểm soát một đ c trưng 21 Mỗi nhiễm sắc thể (gồm một nhóm gen) sẽ biểu diễn một lời giải c a bài toán đang giải ý nghĩa c a một nhiễm sắc thể c thể được người sử d ng ác đ nh trước); một tiến trình tiến hóa được thực hiện trên một quần thể các nhiễm sắc thể tương ứng với một quá trình tìm kiếm lời giải trong không gian lời giải. Tìm kiếm đó cần cân đối hai m c tiêu: khai thác những lời giải tốt nhất và khảo sát không gian tìm kiếm. Giải thuật leo đồi (hill- climbing) là một ví d về chiến lược cho phép khai thác và cải thiện lời giải tốt nhất hiện hành nhưng lại bỏ qua việc khảo sát không gian tìm kiếm Ngược lại, tìm kiếm ngẫu nhiên là một ví d điển hình c a chiến lược khảo sát không gian tím kiếm mà không chú ý việc khai thác những vùng hứa h n c a không gian. Thuật toán gen GA là phương pháp tìm kiếm tạo được sự cân đối đáng kể giữa việc khai thác và khảo sát không gian tìm kiếm. Thực ra, GA thuộc lớp các thuật toán xác suất nhưng lại rất khác những thuật toán ngẫu nhiên. Khác biệt quan trọng giữa tìm kiếm c a GA và các phương pháp t m kiếm khác là GA duy trì và xử lý một tập các lời giải (mà ta gọi là một quần thể). Tất cả các phương pháp khác chỉ xử lý một điểm trong không gian tìm kiếm. Chính vì thế, GA mạnh hơn các phương pháp t m kiếm hiện có rất nhiều. Ta so sánh GA với một phương pháp t m kiếm hiện đang được sử d ng rộng rãi là leo đồi: Phương pháp leo đồi d ng kĩ thuật l p và áp d ng cho một điểm duy nhất điểm hiện hành trong không gian tìm kiếm). Trong mỗi bước l p, một điểm mới được chọn t lân cận c a điểm hiện hành (vì thế leo đồi còn được gọi là phương pháp t m kiếm lân cận hay tìm kiếm c c bộ). Nếu điểm mới cho giá tr (c a hàm m c tiêu) tốt hơn điểm mới sẽ trở thành điểm hiện hành. Nếu không một lân cận điểm khác sẽ được chọn và thử. Quá trình sẽ dùng nếu khong cải thiện thêm được cho lời giải hiện hành. Rõ ràng phương pháp leo đồi chỉ cung cấp các giá tr tối ưu c c bộ và những giá tr này ph thuộc rất nhiều vào điểm khởi đầu Hơn nữa, không có thông tin sẵn có về sai số tương đối c a lời giải t m được. Để t ng cơ hội t m được giá tr tối ưu nhất có thể phương pháp leo đồi thường được thực hiện nhiều lần, mỗi lần với một tập hợp điểm khởi đầu khác nhau (những điểm này 22 không cần chọn ngẫu nhiên – một tập hợp các điểm khởi đầu c a một lần thực thi ph thuộc nhiều vào kết quả c a những lời giải trước đó Như đã đề cập, GA thực hiện tiến trình tìm kiếm lời giải tối ưu theo nhiều hướng, bằng cách duy trì một quần thể các lời giải, và thúc đẩy sự h nh thành và trao đ i thông tin giữa các hướng này. Quần thể trải qua quá trình tiến hóa: ở mỗi thế hệ lại tái sinh các lời giải tốt, còn các lời giải xấu thì b loại bỏ Để phân biệt các lời giải khác nhau, hàm m c tiêu đóng vai trò môi trường. Cấu trúc c a một giải thuật di truyền tương tự với cấu trúc c a bất kì một chương tr nh tiến hóa nào. Ở bước l p giả sử t, thuật toán gen duy trì một quần thể các lời giải (các nhiễm sắc thể) P(t) = {x1, x2 … n}. Mỗi lời giải xi được t nh để biết độ thích nghi c a nó. Rồi một quần thể mới (lần l p thứ t+1 được hình thành bằng cách chọn giữ lại những cá thể thích nghi nhất. Một số các thể c a quần thể này trải qua những biến đ i nhờ lai tạo ph p lai và đột biến ph p đột biến), hình thành lời giải mới. Phép lai kết hợp những tính chất c a hai nhiễm sắc thể cha – m để tạo thành nhiễm sắc thể con. Khác với ph p lai ph p đột biến tạo ra những cá thể mới với có nhiễm sắc thể không liên quan đến những cá thể còn lại c a quẩn thể Ph p đột biến cho ph p đưa thêm các thông tin mới vào quần thể làm cho nguyên liệu di truyền phong phú thêm.  Mội bài toán dựa vào thuật toán gen để giải cần phải có n m thành phần sau:  Một cấu trúc dữ liệu biểu diễn không gian lời giải c a bài toán  Phương pháp khởi tạo quần thể ban đầu  Hàm ác đ nh độ thích nghi  Các phép toán di miêu tả các quá trình di truyền  Các tham số thuật toán gen sử d ng k ch thước quần thể k ch thước các thể tốt, cá thể đột biến … 3.3. Các uá rình cơ bản c a thuật toán gen 3.3.1. Quá trình lai ghép (phép lai) 23 Phép lai là quá trình hình thành nhiễm sắc thể mới trên cơ sở các nhiểm sắc thể cha – m , bằng cách ghép một hay nhiều đoạn di truyền c a hai nhiễm sắc thể cha – m với nhau. Phép lai có thể được mô phỏng như sau:  Chọn ngẫu nhiên hai (hay nhiều) cá thể bất kì trong quần thể. Giải sử các nhiễm sắc thể đều có m gen.  Tạo một số ngẫu nhiên trong khoảng t 1 đến m – 1 (ta gọi là điểm lai Điểm lai chia các chuỗi cha – m có độ dài m thành hai nhóm chuỗi con có độ dài m1 và m2. Hai chuỗi nhiễm sắc thể con mới sẽ là m11 + m22 và m21 + m12.  Đưa hai cá thể mới này vào quần thể để tham gia các quá trình tiên hóa tiếp theo. Minh họa cho ph p lai như sau: Giả sử hai nhiễm sắc thể bố - m có dạng: Bố: 0 0 0 0 0 0 0 0 M : 1 1 1 1 1 1 1 1 Khi đó giả sử điểm cắt tại điểm giữa ta sẽ thu được 2 cá thể con có nhiễm sắc thể như sau: Con lai 1: 0 0 0 0 1 1 1 1 Con lai 2: ↓ 24 1 1 1 1 0 0 0 0 3.3.2. Quá rình đột biến (phép đột biến) Đột biến là hiện tượng các cá thể con mang một số trạng thái không có trong mã di truyền c a cha m Có thể sử d ng những phương pháp sau để tạo các cá thể đột biến  Phương pháp 1: tạo cá thể đột biến bằng cách thay đ i gen c a các cá thể hiện có trong quần thể: • Chọn ngẫu nhiên một cá thể bất kì trong quần thể • Chọn một số ngẫu nhiên k trong khoảng t 1 đến m – 1 Trong đó m là số gen c a nhiễm sắc thể. • Thay đ i gen thứ k c a nhiễm sắc thể được chọn. • Có thể l p lại các bước chọn số k và thay đ i nhiễm sắc thể thứ k nhiều lần. • Đưa cá thể đã được đột biến vào quẩn thể để tham gia các quá trình tiến hóa tiếp theo.  Phương pháp 2: tạo ra những nhiễm sắc thể mới gọi là đột biến giống với cách tạo ra những nhiễm sắc thể trong quần thể ban đầu. 3.3.3. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn) Ph p tái sinh là quá tr nh trong đó các cá thể được sao ch p trên cơ sở độ thích nghi c a nó Độ thích nghi là một hàm gián một giá tr thực cho mỗi cá thể trong quần thể. Phép chọn là quá trình loại bỏ các cá thể xấu trong quần thể, chỉ giữ lại các cá thể tốt. Phép chọn được mô tả như sau:  Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần.  Loại bỏ những cá thể ở cuối dãy chỉ giữ lại những cá thể tốt nhất. 25 Chương : Thuậ án gen trong bài toán định tu ến và ph n bước ng ạng u ng 4.1. Giới thiệu chung Qua những phần trên chúng ta có thể thấy rằng hệ thống mạng WDM và thuật toán gen đều có những ưu điểm rất vượt trội. Một bên là một công nghệ mạng được coi là cuộc cách mạng trong công nghệ truyền thông, một bên là một thuật toán tìm kiếm đang tỏ ra là thuật toán tối ưu nhất, hoàn thiện nhất so với các thuật toán tìm kiếm thường hay sử d ng. Vậy nếu có thể kết hợp chúng được vào cho nhau tức là sử d ng thuật toán gen cho bài toán đ nh tuyến và phân bước sóng thì rất có thể sẽ thu được những kết quả rất đáng mong đợi Và đây ch nh là vấn đề sẽ được nghiên cứu trong khóa luận này. Tuy nhiên trước đó chúng ta sẽ tìm hiểu qua về đồ th - một phương pháp d ng để biểu diễn một topology mạng và thuật toán duyệt đồ th theo chiều rộng BFS (Breadth- First Search) - thuật toán được sử d ng nhiều trong vấn đề t m đường đi đ nh tuyến c a các lightpath. 4.2. Sơ lược lý thuyế đồ thị và thuật toán BFS cho bài toán ì đường đi ngắn nhất. 4.2.1. Lý thuyế đồ thị Trong toán học và tin học đồ th là đối tượng nghiên cứu cơ bản c a lý thuyết đồ th Đồ th là một tập các đối tượng gọi là đỉnh được nối với nhau bởi các cạnh. Thông thường đồ th thường được vẽ dưới dạng tập các điểm đỉnh, node) nối với nhau bởi các đoạn thẳng (cạnh). Tùy theo ứng d ng mà các cạnh có thể có hướng ho c vô hướng. Có thể biểu diễn đồ th như sau: G = V A trong đó gồm: • V : Tập các đỉnh • A = { (u, v) | u, v  G } 26 H nh 4 1 Đồ th 6 đỉnh Đồ th thường được sử d ng để mô hình hóa một tập các đối tượng có quan hệ với nhau theo một cách nào đó Chẳng hạn trong lĩnh vực máy t nh đồ th được sử d ng để mô hình hóa một mạng truyền thông, kiến trúc c a máy t nh song song …Và rất nhiều vấn đề trong các lĩnh vực khác như công nghệ điện, hóa học, chính tr , kinh tế … cũng có thể biểu diễn bởi đồ th . Khi một vấn đề được mô hình hóa bởi đồ th thì vấn đề sẽ được giải quyết bằng cách sử d ng các thuật toán trên đồ th . Vì vậy các thuật toán đồ th có phạm v áp d ng rộng lớn và có tầm quan trọng đ c biệt 4.2.2. Thuật toán BFS Việc duyệt đồ th theo chiều rộng được thực hiện bằng cách sử d ng kĩ thuật tìm kiếm theo chiều rộng BFS (Breadth-First Search Ý tưởng c a tìm kiếm theo bề rộng xuất phát t đỉnh v như sau T đỉnh v ta lần lượt đi th m tất cả các đỉnh u kề đỉnh v mà u chưa được th m Sau đó đỉnh nào th m trước th các đỉnh kề c a nó cũng sẽ được th m trước. Quá trình trên sẽ được tiếp t c cho đến khi không thể th m đỉnh nào nữa. Ta cần quan tâm đến các đ c điểm sau trong kĩ thuật này: • Tại mỗi bước, t một đỉnh đã được th m ta đi th m tất cả các đỉnh kề đỉnh đó (tức là th m theo chiều rộng). • Trật tự các đỉnh được th m là: đỉnh nào được th m trước th các đỉnh kề c a nó cũng phải được th m trước. 27 Để lưu lại các đỉnh được th m chúng ta sử d ng một hàng đợi Q. Mỗi khi đến th m một đỉnh th đỉnh đó được xen vào đuôi hàng đợi Q. Thuật toán tìm kiếm theo chiều rộng xuất phát t đỉnh v được biểu diễn bởi hàm BFS(v). Ta có thể viết mã c a thuật toán như sau: 1) Procedure BFS(v) 2) begin 3) Create Queue Q = Φ; 4) Insert v into Q; 5) Mark v is explore; 6) while (!Q.empty() ) do 7) w is front Q; 8) for ( u incident w) do 9) if (u is unexplored) 10) then do 11) Insert u into Q 12) Mark u is explore 13) end – if; 14) end – for; 15) Remove w from Q; 16) end - while ; 17) end; Đoạn mã trên được diễn giải như sau:  Khởi tạo một hàng đợi rỗng Q (dòng 3)  Xen v vào hàng đợi Q đánh dấu v đã được th m dòng 4 5  Tạo một vòng l p với điều kiện Q không rỗng dòng 6 trong đó thực hiện: • Lấy phần tử w ở đầu hàng đợi (dòng 6) • T m các điểm u liền kề với w, nếu u chưa được đánh dấu thì xen u vào hàng đợi đồng thời đánh dấu u đã được th m dòng 8 - 14)  Loại w ra khỏi hàng đợi (dòng 15) T thuật toán duyệt đồ th theo chiều rộng BFS ta có thể t m được đường đi ngắn nhất c a đồ th . Giả sử ta cần t m đường đi ngắn nhất t điểm a đến điểm b Trước hết ta sử d ng thuật toán BFS duyệt qua đồ th với điểm bắt đầu là a. Sau khi duyệt qua đồ th 28 nếu trong tập được đánh dấu đã th m không có b th ta có thể kết luận giữa a và b không tồn tại đường đi ngược lại ta có đường đi ngắn nhất giữa 2 điểm này Để lấy đường đi này ta cần tạo một mảng list với thành phần list [u] sẽ ghi lại đỉnh trước đỉnh u trên đương duyệt t a đến u. Tạo một vòng l p như sau như sau ta thu được đường đi ngắn nhất t a đến b trong mảng _list: while (b != a) { _list.insert (b); //Đưa b vào trong _list; b = list[b]; } Thuật toán BFS có thể được minh họa như sau: Giả sử ta cần t m đường đi ngắn nhât giữa 2 điểm 0 – 5 trong đồ th sau: Ta tạo một hàng đợi rỗng và đưa điểm vào hàng đợi. Tạo một mảng d và đánh dấu d[0] = 1; mảng list lưu các giá tr c a đường đi 0 Lấy đỉnh hàng đợi (0) ra khỏi hàng đợi và đưa các đỉnh kề 1 2 vào hàng đợi đánh dấu d[1] = 1; d[2] = 1; list[1] = 0; list[2] = 0; 2 3 1 0 4 5 29 1 2 Lấy 1 ra khỏi hàng đợi và đưa đỉnh 3 kề với 1 vào hàng đợi; d[3] = 1; list[3] = 1; 2 3 Do đỉnh 3 kề với 2 đã được đánh dấu lên bước tiếp theo ta đưa 2 ra khỏi hàng đợi 3 Lấy 3 ra khỏi hàng đợi đưa đỉnh kề 4 vào hàng đợi đánh dấu d[4] = 1; list[4] = 3; 4 Lấy 4 ra khỏi hàng đợi đưa đỉnh kề 5 vào hàng đợi đánh dấu d[5] = 1; list[5] = 4; Đỉnh 5 không còn cạnh kề chưa đánh dấu lên kêt thúc T các giá tr c a mảng list ta thu được đường đi ngắn nhất t điểm 0 – 5 là: 0 – 1 – 3 – 4 – 5 4.3. Các nghiên cứu cho bài toán đ nh tuyến và phân bước sóng mạng WDM Bài toán đ nh tuyến và phân bước sóng RWA (Routing and Wavelength Assignment) c a chúng ta được mô tả như sau: Với một mạng quang WDM và một bộ lightpath có sẵn, cần tìm một tuyến đường cho mỗi sợi quang và gán cho mỗi sợi quang đó một bước sóng sao cho số lượng bước sóng sử d ng nhỏ nhất. 30 Có nhiều phương pháp khác nhau đề xuất để giải quyết bài toán RWA. Một số phương pháp th chia bài toán thành hai bài toán con: bài toán đ nh tuyến và bài toán phân bước sóng. Một số phương pháp khác th giải quyết đồng thời cả hai vấn đề. Bannerjee và Mukherjee [5] giải quyết bài toán trong 2 giai đoạn Đầu tiên một trong những tuyến đường cho mỗi lightpath được chọn bởi thuật toán làm t m đường ngẫu nhiên Sau đó một bước sóng sẽ được chọn cho để gán mỗi lightpath. Hyytia và Virtamo [6] cũng đi theo chiến thuật phân chia nhưng sử d ng thuật toán khác nhau cho t ng giai đoạn. Các tuyến đường được tính bằng cách sử d ng thuật toán đường đi ngắn nhất. Sau đó một bước sóng được chọn để gán cho mỗi lightpath. Manohar, Manjunath và Shegaonkar [7] sử d ng thuật toán tham lam để giải quyết bài toán R A đây là phương pháp đầu tiên giải quyết đồng thời cả hai bài toán con. Tại mỗi bước l p, một tập con các lightpath được chọn và đ nh tuyến sao cho những lightpath được chọn sử d ng những đường tách rời nhau khi đ nh tuyến Sau đó tất cả những lightpath này sẽ được gán cùng một bước sóng. Th t c được l p lại với các lightpath. Thuật toán tốt nhất cho bài toán R A được đưa ra gần đây do Skorin-Kapov [8] nghiên cứu mang tên BFD. Thuật toán này sẽ được giới thiệu kĩ trong phần tiếp theo Đây cũng ch nh là thuật toán làm tiền đề để áp d ng thuật toán gen vào bài toán RWA. 4.4. Thuật toán BFD-RWA 4.4.1. Mô tả thuật toán Thuật toán BFD (Best Fit Decreasing) là thuật toán được Skorin-Kapov nghiên cứu cho bài toán đ nh tuyến và phân bước sóng (RWA) trong mạng quang WDM. Một topology vật lý c a mạng quang được biểu diễn bằng đồ th G = (V, A) với V là số đỉnh c a đồ th tương ứng với số node trong mạng và A là số cạnh nối 2 đỉnh c a đồ th tương ứng với số sợi quang kết nối 2 node trong mạng. Thuật toán được mô tả như sau: các bản sao c a đồ th được tạo ra đồng thời có một bước sóng được gán cho bản sao. Các lighpath sẽ được đ nh tuyến trên các bản sao c a G, những lightpath được đ nh tuyến trên cùng một bản sao sẽ được gán cùng một bước sóng 31 tương ứng với bản sao đó M c tiêu số bước sóng sử d ng nhỏ nhất tương ứng với số bản sao được tạo ra ít nhất. Với một tập T biểu th số lightpath yêu cầu gồm các lightpath 1 2 …T một giá tr min-length được tính cho mỗi lightpath để biểu th đường đi ngắn nhất c a lightpath trong đồ thi G. Giá tr này được t nh để đánh giái độ ưu tiên xem lighpath nào được đ nh tuyến trước. Khi một lightpah được đ nh tuyến trên một bản sao c a G, tất cả các cạnh nối 2 node trên đường đi c a lightpath sẽ được xóa nhằm tránh các lightpath khác sử d ng đoạn đường đó Các lightpath có thể không được đ nh tuyến trên đường đi ngắn nhất ban đầu do có thể cạnh trên đường đi ngắn nhất c a lightpath đó đã được xóa trong quá trình đ nh tuyến lightpath trước đó Mà lúc này lightpath sẽ được đ nh tuyến trên đường đi ngắn nhất c a thực trạng bản sao khi đó Mã c a thuật toán BFD được viết như sau: 1) Procedure BFD-R A G T d π 2) Set S = Φ C = Φ 3) for i = 1 2 …|T| do 4) If (there is no (arc-disjoint) path available for routing π(i) with less than d arcs in any of the copies of G in C) 5) then do 6) Create a new copy of G and assign a wavelength; 7) Add to C the new copy of G; 8) end-if 9) Find the copy of G in C where lightpath π i can be routed with the smallest number of arcs; 10) Let pπ i be the shortest path between the endnodes of lightpath Wπ i be its corresponding wavelength; 11) Add (Pπ i , Wπ i ) into S: S = S (Pπ i , Wπ i ) 12) Delete all arcs in path Pπ i from this copy of G; 13) end-for; 14) return S; 15) end BFD-RWA Đoạn mã trên được diễn giải như sau: 32  Dòng 1: khởi tạo hàm và biểu diễn đầu vào: gồm một đồ th G biểu diễn một topology mạng, một tập các lightpath yêu cầu T, một vector π biểu thứ tự các lighpath được sắp xếp theo thứ tự giảm dần c a giá tr min-length, một giá tr d biểu diễn là giá tr lớn nhất c a một tuyến đường; giá tr này nhằm tránh cho lighpath có đ nh tuyến bằng đường đi quá lớn. Giá tr d được tính bằng c n bậc 2 c a tích số liên kết trong đồ th G nhân với đường kính c a đồ th ; đường kính c a đồ th được tính bằng giá tr lớn nhất trong số đường đi giữa 2 c p đỉnh bất kì tính bằng đường đi ngắn nhất Nghĩa là t nh đường đi ngắn nhất giữa 2 c p đỉnh bất k và đường k nh đồ th chính là giá tr lớn nhất trong số đó  Dòng 2: khởi tạo một tập S và một tập C ban đầu rỗng. Tập S biểu diễn đầu ra bao gồm đường đi c a lightpath và bước sóng tương ứng với nó; tập C lưu các bản sao c a đồ th G.  Các dòng t 3 – 13 thực hiện một vòng l p duyệt qua các lightpath theo thứ tự sắp xếp trong π tức là giá tr giảm dần theo giá tr min-length c a lightpath. Tại mỗi vòng l p thực hiện: • Nếu không tồn tại đường đi nào cho lighpath có độ dài nhỏ hơn d trong tập các bản sao C thì thêm vào C một bản sao mới c a G và gán 1 bước sóng tương ứng với bản sao đó dòng 4 5 6, 7, 8). • T m đường đi nhỏ nhất c a giữa 2 điểm đầu cuối c a lighpath đang được duyệt trong tất cả các bản sao c a G. Lấy ra giá tr nhỏ nhất trong số trên và bước sóng tương ứng với bản sao cho giá tr nhỏ nhát đó Gọi pπ i và Wπ i là đường đi và bước sóng thu được (dòng 9, 10). • Thêm Pπ i , Wπ i vào tập đầu ra S.  Dòng 14: trả về tập S.  Dòng 15: kết thúc. Thuật toán được minh họa như sau:  Giả sử dưới đây là một topology mạng với tập các lightpath yêu cầu là: 0 – 1, 1 – 3, 2 – 4, 0 – 4, 0 – 5 => Thứ tự lightght sắp xếp theo thứ tự giảm dần min- length là 0 – 5 , 0 – 4, 2 – 4, 0 – 1. 33  Đầu tiên do chưa có bản sao nào lên một bản sao c a G(0) được tạo ra và được thêm vào C và bước sóng được gán giả sử là w0  Lightpath 0 – 5 có độ dài min length lớn nhất sẽ được đ nh tuyến trước Đường đi ngắn nhất t m được là 0 – 1 – 3 – 4 – 5 Đây ch nh là đường đi c a lightpath c a lightpath 0 – 5 và bước sóng cho lightpath này là w0 Đường đi trên được xóa khỏi G(0) Khi đó tập C sẽ chứa đồ th G(0) dạng:  Lightpath 0 – 4 được đ nh tuyến tiếp theo. Do trong bản sao G(0) không có đường đi nên một bản sao mới G(1) bước sóng tương ứng được gán là w1) được tạo ra thêm vào tập C đường đi ngắn nhất thu được trên bản sao mới là 0 – 1 – 3 – 4 Đây ch nh là đường đi cho lightpath – 4 và bước sóng được gán là w1. Xóa các cạnh trên đường đi c a lightpath này trong bản sao G(1). Lúc này trong tập C gồm 2 bản sao c a G: 2 3 1 0 4 5 G(0) 2 3 1 0 4 5 34  Lightpath tiếp theo được đ nh tuyến là 2 – 4. Do tìm trong 2 bản sao G(0) và G(1) không có đường đi nên một bản sao G(2) được tạo ra và thêm vào tập C đồng thời cũng gán một bước sóng w2 tương ứng Đường đi ngắn nhất t m được là 2 – 3 – 4 Đây cũng ch nh là đường đi c a lightpath 2 – 4 được đ nh tuyến và bước sóng sử d ng là w2. Xóa các cạnh trên trên đường đi tại bản sao G(2) ta thu được tập C lúc này gồm 3 bản sao: 2 3 1 0 4 5 G(1) 2 3 1 0 4 5 G(0) 35  Lightpath cuối c ng được đ nh tuyến 0 – 1. Duyệt qua tập các bản sao c a G, thu được kết quả là đường 0 – 1 thuộc bản sao G(2) Khi đó lightpath – 1 được đ nh tuyến sẽ là 0 – 1 và được gán bước sóng tương đương với G(2) tức là w2. Xóa cạnh 0 – 1 tại bản sao G(2) ta thu được tập C như sau: 2 3 1 0 4 5 G(2) 2 3 1 0 4 5 G(1) 2 3 1 0 4 5 G(0) 36 Như vậy tất cả các bước sóng yêu cầu đã được đ nh tuyến. 4.4.2. Chứng minh thuật toán Chứng minh thuật toán đồng nghĩa với việc ta chứng minh thuật toán thỏa mãn hai điều kiện c a bài toán đ nh tuyến và phân bước sóng R A Đồng thời thuật toán cũng cho kết quả số bước sóng sử d ng nhỏ nhất có thể: 2 3 1 0 4 5 G(2) 2 3 1 0 4 5 G(1) 2 3 1 0 4 5 G(0) 37  Thứ nhất: ta thấy rằng mỗi lightpath được đ nh tuyến trên một bản sao c a đồ th và sử d ng bước sóng tương ứng với bản sao do đó điều kiện về tính liên t c c a bước sóng được thỏa mãn.  Thứ hai: sau khi một lightpath được đ nh tuyến trên một bản sao tất cả các cạnh trên đường đi c a lightpath được xóa bỏ do đó nếu các lighpath khác sử d ng những cạnh đó trên đường đi th cần phải đ nh tuyến trên bản sao khác. Mà các bản sao tương ứng với các bước sóng khác nhau Do đó t nh riêng biệt c a bước sóng được thỏa mãn.  Thứ 3: trước khi tạo một bản sao mới ứng với t ng thêm một bước sóng sử d ng. Mỗi lighpath đều được t m đường đi trong các bản sao trước đó nếu không tồn tại đường đi trong tất cả các bản sao thì mới tạo bản sao mới Điều này đã giảm thiểu tối đa việc t ng số bước sóng sử d ng Do đó số bước sóng sử d ng ở đây là nhỏ nhất. 4.5. Thuật toán gen r ng bài án định tuyến và ph n bước sóng (GA – RWA) 4.5.1. Đặt vấn đề Qua phần bên trên chúng ta có thể thấy thuật toán BFD thỏa mãn đầy đ hai đ c tính liên t c và riêng biệt về bước sóng. Thuật toán cũng sẽ tối ưu về số bước sóng nhỏ nhất sử d ng nếu như tất cả các lightpath có độ dài min-length khác nhau. Tuy nhiên vấn đề sẽ xảy ra nếu như có nhiều lightpath có cùng một độ dài min-length Khi đó việc xắp xếp thứ tự đ nh tuyến c a các lightpath có c ng độ dài min-length theo những thứ tự khác nhau sẽ cho ra những kết quả khác nhau Do đó nếu chỉ chạy thuật toán BFD một lần sẽ cho ra kết quả chưa chắc tốt nhất Để giải quyết vấn đề trên có thể chạy thuật toán BFD nhiều lần đến khi thu được một kết quả mong muốn. Tuy nhiên ở giải pháp này mỗi một lần chạy BFD các lightpath cùng min-length sẽ được sắp xếp theo một thứ tự ngẫu nhiên và kết quả thu được cũng sẽ là ngẫu nhiên, tức là kết quả thu được ở lần chạy sau có thể tốt hơn ho c có thể xấu hơn kết quả c a lần chạy trước đó Do đó phần này sẽ giới thiệu phương pháp sử d ng thuật toán gen trong bài toán RWA (GA- RWA) để sắp xếp thứ tự được đ nh tuyến c a các lightpath có cùng min-length qua mỗi vòng l p tương đương với các 38 thế hệ c a thuật toán gen. Và điều quan trọng nhất là kết quả c a lần chạy sau luôn tốt hơn ho c bằng với kết quả c a lần chạy trước. 4.5.2. Thuật toán gen trong bài toán RWA Qua phần giới thiệu về thuật toán gen bên trên chúng ta có thể h nh dung được các quy tr nh để giải bài toán bằng cách sử d ng thuật toán gen. Ở bài toán RWA này,một quần thể ban đầu được xây dựng với một tập các cá thể. Mỗi cá thể được biểu diễn bằng một nhiễm sắc thể (chromosome). Mỗi nhiễm sắc thể sẽ được đ nh nghĩa là một vector các số thực trong khoảng (0, 1) được tạo ra ngẫu nhiên, các số thực này chính là các gen. Một nhiễm sắc thể có dạng như sau: 0.15 0.245 0.762 0.425 0.828 0.171 0.065 0.963 Tại mỗi thế hệ quần thể được sắp xếp theo thứ tự giảm dần c a độ thích nghi (fitness) và được phân chia thành hai nhóm: TOP và REST Do đó k ch thước c a quần thể là |TOP| + |REST|. TOP là tập hợp các nhiễm sắc thể được đánh giá tốt, tức là có độ thích nghi tốt, REST là phần còn lại. Các phép toán gen được thực hiện qua mỗi thế hệ như sau:  Phép lai: một cá thể con được tạo ra t ph p lai như sau: chọn ngẫu nhiên một các thể trong TOP và ngẫu nhiên một cá thể trong REST làm bố - m . Một số ngẫu nhiên k được sinh ra trong khoảng 1 đến m-1 để làm điểm lai. Điểm lai sẽ chia nhiễm sắc thể bố - m thành 2 nhóm gen con Hai con lai được tạo ra bằng cách lấy nửa nhóm gen đầu c a bố ghép với nửa nhóm gen sau c a m và nửa nhóm gen đầu c a m sẽ được ghép với nửa nhóm gen sau c a bố. Ph p lai được minh họa như sau: Giả sử ta có hai nhiễm sắc thể bố - m : Bố: 39 0.15 0.24 0.76 0.42 0.82 0.17 0.77 0.96 M : 0.48 0.74 0.36 0.56 0.92 0.72 0.05 0.11 Giả sử điểm cắt ở giữa ta sẽ được hai nhiễm sắc thể con như sau: Con lai 1: 0.15 0.24 0.76 0.42 0.92 0.72 0.05 0.11 Con lai 2: 0.48 0.74 0.36 0.56 0.82 0.17 0.77 0.96 Nếu điểm cắt trong ví d này là tại điểm thứ 3 ta cũng có 2 nhiễm sắc thể con lai như sau: Con lai 1: 0.15 0.24 0.76 0.56 0.92 0.72 0.05 0.11 Con lai 2: 0.48 0.74 0.36 0.42 0.82 0.17 0.77 0.96 Tương tự với các trường hợp điểm cắt khác.  Ph p đột biến: có nhiều phương pháp để tạo ra nhiễm sắc thể đột biến trong thuật toán gen trên máy tính, có thể là thay đ i giá tr c a một ho c nhiều gen 40 c a một nhiễm sắc thể, ho c thay đ i thứ tự sắp xếp gen c a nhiễm nhiễm sắc thể ban đầu, ho c tạo ra các nhiễm sắc thể mới giống với cách tạo ra các nhiễm sắc thể c a quần thể ban đầu Phương pháp được sử d ng ở đây là phương pháp thứ 3 tức là tạo ra các nhiễm sắc thể đột biến giống với cách tạo ra các nhiễm sắc thể c a quần thể ban đầu. Tập các nhiễm sắc thể đột bến gọi là BOT.  Phép tái sinh và chọn lọc: sau khi ph p lai được thực hiện các nhiễm sắc thể thuộc TOP sẽ được sao chép sang thế hệ sau, các nhiễm sắc thể còn lại trong trong quần thể sẽ b loại bỏ để nhường chỗ cho những cá thể con lai và những cá thể đột biến. Số cá thể trong quần thể ở đây được quy đ nh không thay đ i qua các thế hệ, do đó khi một thế hệ mới được hình thành sẽ bao bồm các cá thể TOP c a thế hệ trước, các cá thể đột biến BOT, số còn lại được tạo ra t phép lai giữa các cá thể c a thế hệ trước đó Các quá trình c a thuật toán gen trong mỗi thế hệ sẽ được mô tả như h nh sau: Hình 4.2 Sơ đồ các phép toán di truyền. Thuật toán gen sẽ được áp d ng cho bài toán R A như sau:số gen trong một nhiễm sắc thể sẽ bằng với số lightpath yêu cầu. T quần thể ban đầu, sẽ có một vòng l p duyệt 41 qua t ng nhiễm sắc thể. Tại mỗi vòng l p, mỗi gen sẽ được cộng với giá tr min-length c a mỗi lightpath Sau đó các lightpath sẽ được sắp xếp theo giá tr giảm dần c a giá tr sau khi được cộng trên. Thứ tự sắp xếp này sẽ được đưa vào thuật toán BFD. Kết quả thu được sẽ là một tập các lightpath được đ nh tuyến và bước sóng sử d ng tương ứng. Do m c tiêu c a bài toán R A là đ nh tuyến cho các lightpath được yêu cầu sao cho số bước sóng sử d ng là thấp nhất nên số bước sóng sử d ng ở đầu ra c a thuật toán RWA sẽ được gán cho giá tri độ thích nghi c a nhiễm sắc thể. Sau khi duyệt qua quần thể ban đầu, mỗi nhiễm sắc thể sẽ có một giá tr độ th ch nghi tương ứng với số bước sóng sử d ng. Khi đó các nhiễm sắc thể sẽ được xắp xếp giảm dần c a độ thích nghi, tức là xắp xếp theo thứ tự t ng dần c a số bước sóng sử d ng tương đương do m c tiêu c a chúng ta là số bước sóng càng ít càng tốt). T đó quần thể sẽ được phân chia thành 2 phần TOP và REST Sau đó các phép toán di truyền: lai đột biến, tái sinh và chọn lọc được thực hiện tạo ra thế hệ mới. Thế hệ này sẽ lại được đưa vào để t m độ thích nghi và sinh ra các thế hệ tiếp theo. Thuật toán sẽ d ng lại khi một thời gian cho phép trôi qua hay một giải pháp tốt như m c tiêu được tìm thấy. 4.5.3. Chứng minh thuật toán Như đã giới thiệu, thuật toán gen được xem là một tiên đề đúng không chứng minh được như ph hợp với thực tế khách quan. Tính tối ưu c a thuật toán được thể hiện ở chỗ, thế hệ sau bao giờ cũng tốt hơn hoàn thiện hơn thế hệ trước. Trong thuật toán GA cho bài toán RWA, những cá thể có độ thích nghi tốt trong TOP được sao chép sang thế hệ sau. Do đó khi nếu những nhiễm sắc thể lai ghép và những nhiễm sắc thể đột biết được tạo ra ở thế hệ sau có độ thích nghi không tốt hơn những nhiễm sắc thể trong TOP thì sẽ b loại bỏ Ngược lại nếu trong các nhiễm sắc thể lai ghép và những nhiễm s c thể đột bến này có những nhiễm sắc thể tốt hơn một hay nhiều nhiễm sắc thể trong TOP thì nó sẽ được thay thế những nhiễm sắc thể trong TOP đó để sao chép và lai ghép ra thế hệ sau. Và nếu có nhiễm sắc thể tốt hơn nhiễm sắc thể đang có độ thích nghi tốt nhất trong TOP thì ta sẽ được một lời giải tối ưu hơn tức là số bước sóng sử d ng t hơn. 42 Chương : Thực hiện ô ph ng 5.1. Công cụ thực hiện Chương tr nh mô phỏng lại thuật toán được em sử d ng ngôn ngữ C++, lập trình trên nền windows, với IDE là Code::blocks. Ngôn ngữ được sử d ng để viết chương tr nh là C++ một ngôn ngữ thuần hướng đối tượng được sử d ng nhiều trong việc lập trình các thuật toán. Phần mềm được chọn để sử d ng viết chương tr nh là Code:blocks Đây là một IDE C/C++ miễn phí tính hợp sẵn trình biên d ch minGW, hỗ trợ biên d ch và debug trực tiếp chương tr nh ngoài ra Code::blocks còn được tích hợp nhiều t nh n ng như auto complete hightlight code … giao diện thân thiện, dễ sử d ng. 5.2. Bố cục chương rình Lưu đồ thuật toán: 43 Bắt đầu Nạp đồ th và tập lightpath yêu cầu Khởi tạo quần thể ban đầu Sắp xếp lightpath Đ nh tuyến và phân bước sóng bằng thuật toán BFD Sắp xếp quần thể theo độ thích nghi giảm dần Lai ghép – Đột biến – Tái sinh - Chọn lọc Đường đi đ nh tuyến và bước sóng sử d ng Kết thúc Số bước sóng sử dụng nhỏ nhất Tìm min-length c a mỗi lightpath BFS d 44 Chương tr nh được thiết kế giống như lưu đồ trên:  Ban đầu một đồ th biểu diễn một topology và một tập các lightpath yêu cầu được nhập vào làm tham số đầu vào.  Sau đó hàm BFS được sử d ng để t m đường đi ngắn nhất c a các lightpath qua đó t nh được giá tr min-length m t khác t BFS ta t nh được giá tr d tức là giá tr lớn nhất c a độ dài mà đường đi lightpath cho ph p nhằm tránh cho các lightpath có đường đi quá dài khi đ nh tuyến.  M t khác ta tạo được quần thể ban đầu thông qua số đỉnh c a đồ th lightpath yêu cầu. Ở đây số cá thể trong quần thể được tạo bằng với số đỉnh c a đồ th và số gen trong một nhiễm sắc thể bằng với số lightpath yêu cầu. Mỗi gen là một số thực được sinh ra ngẫu nhiên trong khoảng (0, 1). Giá tr TOP và BOT được gán bằng 0.2 số các thể trong quần thể. Các tham số này có thể thay đ i tùy ý.  Sau đó một vòng l p sẽ tạo ra để duyệt qua t ng nhiễm sắc thể. Với mỗi nhiễm sắc thể, mỗi gen trong đó sẽ được công với giá tr min-length c a mỗi lightpath. Sau đó lightpath được sắp xếp theo thứ tự giảm dần c a giá tr sau khi được cộng trên và đưa vào thuật tóan BFD.  Các lightpath sẽ được đ nh tuyến và gán bước sóng theo thuật toán BFS Đầu ra sẽ là các đường đi cho các lightpath và các bước sóng sử d ng tương đương T ng số bước sóng sử d ng sẽ được gán cho độ thích nghi c a nhiễm sắc thể d ng đ ghép với các giá tr min-length bên trên.  Sau đó các nhiễm sắc thể này được sắp xếp theo thứ tự giảm dần c a độ thích nghi tức là t ng dần c a số bước sóng sử d ng.  Tiếp đó các quá tr nh di truyền diễn ra qua các phép toán di truyền như: ph p lai ph p đột biến, phép tái sinh và chọn lọc. T đó h nh thành lên một thế hệ mới  Tại thế hệ mới này các nhiễm sắc thể lại được sử d ng kết hợp với các giá tr min-length để tạo thứ tự sắp xếp đầu vào cho các lightpath để bắt đầu một vòng l p t m đường đi và bước sóng cho các lightpath mới.  Quá trình d ng lại khi chạy đ số thế hệ trong tham số đầu vào.  Kết quả đầu ra sẽ là đường đi c a các lightpath và bước sóng tương ứng với số bước sóng sử d ng là nhỏ nhất trong tất cả các vòng l p trên. 45 Đầu vào c a chương tr nh là 2 file te t lưu trong thư m c input gồm một file lưu đồ th (graph.txt) và một file lưu tập các lightpath yêu cầu (lightpath.txt) có đ nh dạng như sau: graph.txt: nV nA a1 b1 a2 b2 …… an bn Trong đó: • nV là số cạnh c a đồ th (topology mạng) • nA là số đỉnh c a đồ th ((topology mạng) • a1,2,..n b1 2 … n biểu diễn các cạnh trên đồ th t các điểm a1, a2…, an đến các điểm b1, b2,…, bn. lightpath.txt: x1 y1 x2 y2 …… xn yn Trong đó: • x1,2,..,n y1 2 … n biểu diễn các lightpath yêu cầu t x1, x2 … n đến y1, y2 … yn. Đầu ra c a chương tr nh là một file t t lưu đường đi c a các lighpath được đ nh tuyến và bước sóng sử d ng tương ứng. 5.3. Kết quả thực nghiệ và đánh giá  Trước tiên chương tr nh được thử nghiệm với bài toán t m đường đi các lightpath: – 1, 1 – 3, 2 – 4, 0 – 4, 0 – 5 trong đồ th 6 đinh tương ứng với mô hình mạng 6 node: 46 Hinh 5.1 Mô hình mạng 6 node Như trong phần tính lý thuyết chúng ta t nh được kết quả các lightpath sẽ được đ nh tuyến theo các tuyến đường và bước sóng như sau:  Lightpath 0 – 5: 0 – 1 – 3 – 4 – 5 bước sóng sử d ng w0  Lightpath 0 – 4: 0 – 1 – 3 – 4 bước sóng sử d ng w1  Lightpath 2 – 4: 2 – 3 – 4 bước sóng sử d ng w2  Lightpath 0 – 1: 0 – 1 bước sóng sử d ng w2 Trong chương tr nh đầu vào là 2 file graph t t và lighpath t t như sau: graph.txt: lightpath.txt: 2 3 1 0 4 5 47 Chạy chương tr nh ta thu được đầu ra là file GA_RWA t t như sau: GA_RWA.txt Kết quả thu được: số bước sóng sử d ng 3 cùng đường đi và bước sóng sử d ng tương ứng. Kết quả này tối ưu hơn so với các thuật toán do Bannerjee và Mukherjee [5] và Hyytia và Virtamo [6] nghiên cứu khi sử d ng một bước sóng cho một lightpath (ở đây có 4 lightpath tương đương 4 bước sóng)  Mô hình mạng được thử nghiệm tiếp theo là một đồ th gồm 14 node và 21 cạnh như sau: 48 Hình 5.2 Mô hình mạng 14 node Với tập lightpath yêu cầu là các lightpath: 0 – 5, 5 – 10, 0 – 3, 2 – 4, 0 – 2, 8 - 6 ta được file kết quả: 13 7 1 3 9 8 11 2 0 12 10 0 5 6 4 49 Kiểm tra trên đồ th ta thấy tất cả các lightpath đều được đ nh tuyến đúng. Số bước sóng sử d ng ở đây chỉ là 2 cho 6 lightpath phương pháp do Bannerjee và Mukherjee [5] và Hyytia và Virtamo [6] đưa ra sẽ cần 6 bước sóng) Chạy lại thuật toán ta được kết quả: 50 Ta thấy ba bước sóng có giá tr min-length bằng 2 là: 0 – 5 , 5 – 10, 2 – 4; ba bước sóng 0 – 2, 0 – 3, 6 – 8 có giá tr min-length bằng 1. Theo hai kết quả ta thấy ba bước sóng có giá tr min-length dài hơn được đ nh tuyến trước, tuy nhiên thứ tự các bước sóng được đ nh tuyến khác nhau Điều này chính là do các ở mỗi lần chạy các gen khác nhau được cộng vào giá tr min-length làm cho thứ tự các lightpath được đ nh tuyến cũng thay đ i.  Thí nghiệm tiếp theo sẽ minh họa tính tối ưu khi áp d ng thuật toán gen (GA- RWA) so với thuật toán BFD ban đầu. Mô hình mạng được sử d ng được sử d ng là một cấu trúc dạng grid – topology được sinh tự động bằng mã C++ như sau: một node sẽ liên kết với bốn node gần nhất, xác xuất có lightpath yêu cầu giữa 2 node là p 51  Trong thí nghiệm này số node c a mạng là 50, xác xuất có lighpath yêu cầu giữa 2 node là p bằng 0.2 Hai file graph t t và lighpath t t sinh ra như sau graph t t: 5 đỉnh 99 cạnh. lightpath.txt: 486 lightpath Khi đó với thuật toán BFD cho ra kết quả: Số bước sóng sử d ng là 54 bước sóng. Thời gian thực hiện 1.554s 52 Chạy với thuật toán GA-RWA với số vòng l p thế hệ bằng 5 ta được kết quả: Số bước sóng sử d ng 53 bước sóng. Thời gian thực hiện 608.713s  Thí nghiệm tiếp theo được thực hiên với 70 node, xác xuất có lightpath giữa 2 node bất kì là 2 Hai file graph t t và lightpath được tạo ra như sau: graph t t: 7 đỉnh 139 cạnh lightpath.txt: 662 lightpath Với thuật toán BFD thu được kết quả: 53 Số bước sóng sử d ng là 75 bước sóng. Thời gian thực hiện 4.175s Chạy thuật toán GA_RWA với 5 vòng thế hệ ta thu được: Số bước sóng sử d ng là 72 bước sóng. Thời gian thực hiện 2123.575s  Những kết quả thực nghiệm trên đã minh chứng rõ hơn thuật toán gen rất thích hợp trong việc áp d ng cho bài toán đ nh tuyến và phân bước sóng mạng cáp quang để tìm ra lời giải tối ưu về số bước sóng sử d ng. Với topology mạng và số lightpath yêu cầu càng lớn, kết quả tối ưu hơn được thể hiện rõ hơn Tuy nhiên cũng có thể thấy nhược điểm c a thuật toán là thời gian thực hiện tương đối lâu. 54 Chương 6: Kết luận Nhu cầu xây dựng hệ thống mạng quang WDM nhằm giải quyết nhu cầu b ng thông đang trở lên rất bức thiết. Trong đó bài toán đ nh tuyến và gán bước sóng (RWA) có vai trò quyết đ nh đến chi ph cũng như ác uất tắc nghẽn c a hệ thống mạng. Khóa luận đã tiếp cận vấn đề trên, nghiên cứu và áp dụng thuật toán gen vào giải bài toán RWA. Từ đó thu được những kết quả:  Phân tích các vấn đề c a bài toán đ nh tuyến và gán bước sóng trong mạng WDM  Tìm hiểu cách thức sử d ng thuật toán gen trong bài toán tìm kiếm lời giải tối ưu  Sử d ng thuật thuật toán gen vào trong bài toán đ nh tuyến và gán bước sóng trong mạng quang WDM Các phương thức t m đường đi và gán bước sóng cho các lightpath yêu cầu. Áp d ng thuật toán gen để tìm lời giải tối ưu. Hướng nghiên cứu tiếp theo: sử d ng các phương pháp khác cho các ph p toán trong thuật toán gen nhằm t m ra phương pháp ph hợp nhất cho bài toán. Do giới hạn về thời gian cũng như kến thức lên chưa thể tìm hiểu thực hiện được những phương pháp đ nh tuyến và gán bước sóng khác để đánh giá trực quan hơn tính hiệu quả c a phương pháp đưa ra. 55 Tài liệu tham khảo Tài liệu tiếng việt [1] Tạ Đ nh Thúc Tr tuệ nhân tạo – Lập trình tiến hóa, NXB Giáo D c [2] Lê Sỹ Vinh. Cấu trúc dữ liệu và giải thuật, Đại học Công Nghệ - ĐHQGHN [3] Đỗ V n Việt Em Kĩ thuật thông tin quang, Học viện công nghệ bưu ch nh viễn thông Tài liệu tiếng anh [4] Thiago F. Noronha, Mauricio G.C. Resende, Celso C. Ribeiro. A genetic algorithm with random keys for routing and wavelength assignment. [5] D. Bannerjee and B. Mukherjee. Practical approach for routing and wavelength assignment in large wavelength routed optical networks. IEEE Journal on Selected Areas in Communications, 1995. [6] E. Hyytia and J. Virtamo. Wavelength assignment and routing in WDM networks. In Fourteenth Nordic Teletraffic Seminar, pages 31–40, Copenhagen, 1998. [7] P. Manohar, D. Manjunath, and R.K. Shevgaonkar. Routing and wavelength assignment in optical networks from edge disjoint path algorithms. IEEE Communications Letters, 2002. [8] N. Skorin-Kapov. Routing and wavelength assignment in optical networks using bin packing based algorithms. European Journal of Operational Research, 2007.