Khóa luậ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
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Vũ Công Đức
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
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Vũ Công Đức
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
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: TS. Nguyễn Minh Hằng
HÀ NỘI - 2010
Lời cảm ơn!
Trước tiên tôi xin gửi lời cảm ơn sâu sắc nhất đến Tiến sĩ Nguyễn Minh Hằng,
người đã tận tình chỉ bảo hướng dẫn tôi trong suốt quá trình thực hiện khóa luận.
Tôi xin chân thành cảm ơn các thầy cô trong trường đại học Công Nghệ nói
chung và các thầy cô trong bộ môn mạng máy tính và truyền thông nói riêng đã tạo
điều kiện thuận lợi để tôi học tập, nghiên cứu, tích lũy kiến thức làm hành trang bước
vào cuộc sống.
Cuối cùng tôi muốn gửi lời cảm ơn đến gia đình, bạn bè, những người luôn ở bên
cạnh động viên tôi trong quá trình thực hiện khóa luận.
Vũ Công Đức
Tóm tắt
Trong thời đại công nghệ thông tin CNTT ngày nay sự b ng n c a các d ch v
thông tin đ c biệt là sự phát triển nhanh chóng c a Internet làm gia t ng không ng ng
nhu cầu về dung lượng mạng Trong t nh cảnh đó hệ thống mạng quang ra đời như một
giải pháp tối ưu để giải quyết vấn đề trên. N i bật là sự ra đời c a mạng gh p kênh phân
bước sóng DM Wavelength Division Multipexing).
Một trong những vấn đề quan trọng c a mạng quang WDM là vấn đề đ nh tuyến và
phân bước sóng RWA ( Routing and Wavelength Asignment ) tức là đ nh tuyến đường đi
cho một bộ các đường quang (lightpath) và phân một bước sóng cho mỗi đường quang
đó. Một trong những phương pháp đưa ra và sẽ được nghiên cứu ở trong khóa luận này là
sử d ng thuật toán gen (Genetic Algorithm) hay còn gọi là thuật toán di truyền để giải bài
toán RWA cho mạng WDM.
1
Mục lục
Tóm tắt............................................................................................................................................1
Lời mở đầu .....................................................................................................................................4
Bảng kí hiệu – chữ viết tắt............................................................................................................6
Chương 1: Hệ thống mạng quang ...........................................................................................7
1.1. Giới thiệu chung.............................................................................................................. 7
1.2. Lịch sử và sự phát triển.................................................................................................. 8
1.3. Đặc điể c hệ hống ạng quang ............................................................................. 8
1.3.1.
1.3.2.
Ưu điểm.......................................................................................................................9
Nhược điểm.................................................................................................................9
1.4. Sợi quang ....................................................................................................................... 10
Chương : ạng u ng D ..............................................................................................12
2.1. Giới thiệu chung............................................................................................................ 12
2.2. Nguyên lý hoạ động ..................................................................................................... 13
2.2.1.
2.2.2.
2.2.3.
Tổng quan .................................................................................................................13
Sơ đồ hoạ động.........................................................................................................14
Ưu điểm, vấn đề tồn tại và hướng giải quyế ương l i c a hệ thống WDM...............15
2.3. Định tuyến và gán bước sóng...................................................................................... 16
2.3.1.
2.3.2.
Giới thiệu chung........................................................................................................16
Tổng quan về định tuyến và gán bước sóng (RWA)...................................................16
Chương : Thuậ án g n ......................................................................................................19
3.1. Giới thiệu ....................................................................................................................... 19
3.2. Thuật toán gen trên máy tính ...................................................................................... 19
2
3.3. Các uá rình cơ bản c a thuật toán gen.................................................................... 22
3.3.1.
3.3.2.
3.3.3.
Quá trình lai ghép (phép lai)......................................................................................22
Quá rình đột biến (phép đột biến) ............................................................................24
Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn) .....................................24
quang............................................................................................................................................25
4.1. Giới thiệu chung............................................................................................................ 25
4.2.1.
4.2.2.
Lý thuyế đồ thị.........................................................................................................25
Thuật toán BFS.........................................................................................................26
4.4. Thuật toán BFD-RWA ................................................................................................. 30
4.4.1.
4.4.2.
Mô tả thuật toán........................................................................................................30
Chứng minh thuật toán .............................................................................................36
4.5.1.
4.5.2.
4.5.3.
Đặt vấn đề .................................................................................................................37
Thuật toán gen trong bài toán RWA..........................................................................38
Chứng minh thuật toán .............................................................................................41
Chương : Thực hiện ô ph ng ............................................................................................42
5.1. Công cụ thực hiện ......................................................................................................... 42
5.3. Kết quả........................................................................................................................... 45
Chương 6: Kết luận ..................................................................................................................54
Tài liệu tham khảo ....................................................................................................................55
3
Lời mở đầu
Ngày nay, nhu cầu b ng thông rộng ngày t ng đ c biệt là sự bùng n c a các loại
hình d ch v thông tin như Internet và orld ide eb Điều này đòi hỏi phải xây dựng
và phát triển các mô hình mạng quang với b ng thông cao. Công nghệ ghép kênh phân
bước sóng WDM ra đời như một giải pháp hoàn hảo, cho phép tận d ng tốt b ng thông
rộng lớn c a sợi quang. WDM cho phép sử d ng hiệu quả hơn công suất c a các sợi
quang, nó cho phép truyền đồng thời nhiều kênh khác nhau theo một sợi quang bằng cách
mỗi kênh đó sẽ sử d ng một bước sóng khác nhau.
Đ nh tuyến và phân bước sóng RWA ( Routing and Wavelength Asignment ) là một
trong những vấn đề quan trong nhất c a mạng WDM. Trong mạng quang một lightpath
được đ nh nghĩa là một kết nối giữa hai node trong mạng (có thể qua những node trung
gian). Trong mạng WDM hai lightpath có thể sử d ng chung một bước sóng miễn là
chúng không sử d ng cùng một sợi quang nào trên đường đi Số bước sóng khác nhau sử
d ng có liên quan rất lớn đến chi phí xây dựng cũng như quản lí mạng Do đó vấn đề đ t
ra là làm thế nào để giảm thiểu số bước sóng khác nhau được sử d ng Phương pháp được
đưa ra và nghiên cứu trong khóa luận này là sử d ng thuật toán gen (Genetic Algorithm)
để giảm thiểu số lượng bước sóng khác nhau được sử d ng.
Khóa luận gồm 6 chương với nội dung được mô tả sơ bộ dưới đây:
Chương 1: Hệ thống mạng quang. Chương này sẽ giới thiệu t ng quan về một hệ
thống mạng quang bao gồm l ch sử đ c điểm c a mạng quang và cấu trúc c a sợi quang.
Chương 2: Mạng quang WDM Chương này sẽ giới thiệu về mạng WDM về
nguyên lý hoạt động và các khái niệm chung về đ nh tuyến và gán bước sóng trong mạng
WDM
Chương : Thuật toán gen Chương này sẽ giới giới thiệu t ng quan về sử d ng
thuật toán di truyền trên máy tính và các phép toán trong thuật toán di truyền
Chương : Thuật toán gen trong bài toán định tuyến và phân bước sóng mạng
quang Chương này sẽ mô tả chi tiết việc áp d ng thuật toán gen trong bài toán đ nh tuyến
và phân bước sóng mạng WDM
4
Chương : Thực hiện mô phỏng. Mô phỏng lại thuật toán trong một số mô hình
mạng ví d .
Chương 6: Kết luận
5
Chương 1: Hệ thống mạng quang
1.1. Giới thiệu chung
Hệ thống mạng quang là hệ thống truyền thông tin qua sợi quang. Thông tin được
biến đ i thành ánh sáng và được truyền trong sợi quang. Tại thiết b nhận nó biến đ i
thành thông tin ban đầu.
Lượng thông tin trao đ i trên các hệ thống mạng ngày càng t ng lên rất nhanh. Số
lượng truy cập t ng cao mà Internet là một ví d điển hình: số lượng người sử d ng
Internet ngày càng t ng nhu cầu về b ng thông cũng ngày càng lớn. Chẳng hạn khi
download những dữ liệu hàng GB chúng ta phải chờ đợi hàng ngày mới có được dữ liệu
cần thiết ho c với nhu cầu giải tr cao như em video HD nghe nhạc lossless trực tuyến
khó có thể thực hiện được với mạng cáp đồng tr c hiện nay.
Hình 1.1 Hệ thống mạng sử d ng sóng điện t
Hình 1.2 Hệ thống mạng quang
Hệ thống mạng quang ra đời ch nh là để giải quyết vấn đề trên Với những ưu điểm
như b ng thông lớn có thể tới 5 Tbps độ suy giảm t n hiệu thấp n ng lượng đòi hỏi
thấp không b nhiễm sóng điện t khả n ng bảo mật cao V vậy mạng quang được coi
7
như kĩ thuật c a hệ thống mạng b ng thông rộng Do đó ây dựng và phát triển hệ thống
mạng quang rất cần thiết cho nhu cầu phát triển thông tin trong tương lai
1.2. Lịch sử và sự phát triển
Các phương tiện sơ khai c a thông tin quang là khả n ng nhận biết c a con người về
chuyển động, hình dáng và màu sắc c a sự vật thông qua đôi mắt. Tiếp đó một hệ thống
thông tin điều chế đơn giản xuất hiện là các ngọn đèn hải đ ng Sau đó n m 1791
VC Chape phát minh ra máy điện báo quang. Thiết b này sử d ng khí quyển làm môi
trường truyền dẫn, do đó ch u ảnh hưởng c a các điều kiện thời tiết Để giải quyết hạn chế
này Marconi đã sáng chế ra máy điện báo vô tuyến có khả n ng thực hiện trao đ i thông
tin giữa những người gửi và người nhận ở xa nhau.
Đầu n m 198 A G Bell – người phát minh ra hệ thống điện thoại – đã nghĩ ra một
thiết b quang thoại có khả n ng biến đ i dao động c a máy hát thành ánh sáng. Tuy
nhiên, sự phát triển tiếp theo c a hệ thống này đã b bỏ rơi do sự ra đời c a hệ thống vô
tuyến.
Những nghiên cứu hiện đại về thông tin quang được bắt đầu bằng sự phát minh
thành công c a Laser n m 196 và bằng khuyến ngh c a Kao và Hockham n m 1966 về
việc chế tạo sợi quang có độ t n thất thấp N m 197 Kapron đã chế tạo ra các sợi quang
trong suốt có độ suy hao truyền dẫn khoảng 2 dB/km Được c vũ bởi thành công này,
các nhà khoa học và kĩ sư trên toàn thế giới đã bắt đầu tiến hành các hoạt động nghiên
cứu, phát triển, và kết quả là các công nghệ mới về giảm suy hao truyền dẫn, t ng b ng
thông … đã được phát triển thành công trong những n m 7 Hơn nữa, trong những n m
70, Laser bán dẫn có khả n ng thực hiện dao động liên t c ở nhiệt độ cao đã được chế tạo.
Tu i thọ c a nó ước lượng hơn 1 n m
Dựa trên các công nghệ sợi quang và Laser bán dẫn giờ đây có thể gửi một khối
lượng lớn các tín hiệu âm thanh/dữ liệu đến các đ a điểm cách xa hàng 100 km bằng một
sợi quang có độ dày như một sợi tóc
1.3. Đặc điểm c hệ hống ạng quang
8
1.3.1. Ưu điểm
13
B ng thông lớn đầy tiềm n ng: tần số sóng mạng quang trong khoảng 1 đến
1016 H cung cấp b ng thông lớn hơn nhiều so với hệ thống cáp đồng tr c
khoảng 5 Mh Do đó dung lượng mạng c a hệ thống mạng quang lớn hơn
nhiều so với hệ thống mạng cáp đồng tr c
Sợi quang k ch thước nhỏ và nh : sợi quang có bán k nh rất nhỏ thường chỉ
bằng sợi tóc V thế cho d được ph thêm những lớp bảo vệ th vẫn nhỏ và nh
hơn nhiều so với cáp đồng Điều đó giúp sợi quang có khả n ng linh hoạt trong
việc lưu trữ lắp đ t, vận chuyển
Cách li điện, nhiễu: sợi quang được chế tạo t th y tinh ho c chất d o Đó là
những vật liệu cách điện, không b ảnh hưởng bới nhiễu điện t và các tần số
vô tuyến. Vì thế hệ thống mạng quang có thể truyền tốt dữ liệu qua những môi
trường nhiều sóng điện t
Nguyên liệu r : chất d o và th y tinh là những nguyên liệu rất r so với nguyên
liệu c a cáp đồng Do đó khi bài toán về công nghệ chế tạo được giải thì hệ
thống quang sẽ có tính kinh tế hơn hệ thống cáp đồng rất nhiều.
Tính bảo mật: một đ c điểm rất quan trọng c a sợi quang là có độ an toàn, bảo
mật cao, tu i thọ dài và có khả n ng đề kháng môi trường lớn, dễ bảo dưỡng.
Nhờ những ưu điểm này, sợi quang được sử d ng cho các mạng lưới điện thoại,
máy tính, phát thanh truyền h nh b ng thông rộng đ c biệt là những ứng d ng
cần tính bảo mật cao như trong quân đội, ngân hàng và các ứng d ng truyền dữ
liệu.
Suy hao thấp: đ c tính này giúp cho việc lắp đ t hệ thống quang dễ bớt phức
tạp hơn và chi ph t hơn cho các bộ khuyến đại đường truyền
1.3.2. Nhược điểm
Tuy có nhiều ưu điểm vượi trội nhưng hệ thống mạng quang cũng có một vài nhược
điểm:
9
Khó đấu nối
Giá thành cao: m c dù giá nguyên liệu r nhưng do công nghệ chế tạo vẫn còn
hạn chế.
1.4. Sợi quang
Sợi quang là những dây nhỏ và d o truyền các ánh sánh nhìn thấy được và các tia
hồng ngoại. Chúng có lõi (Core) ở giữa, phần bao bọc xung quanh lõi gọi là áo (Cladding)
và vỏ bọc ngoài cùng (Buffer Coating) Để ánh sáng có thể phản xạ một cách hoàn toàn
trong lõi thì chiết suất c a lõi phải lớn hơn chiết suất c a áo.
Hình 1.3 Sợi quang
Vỏ bọc ở phía ngoài bảo vệ sợi quang khỏi b ẩm và n mòn Lõi và áo được làm
bằng th y tinh hay chất d o (silicast, chất d o, sợi quang kết tinh) có chiết suất khác nhau.
Khi truyền trong sợi quang, sóng ánh sáng b chi phối bởi một số hiện tượng sau:
Suy giảm (Attenuation): suy giảm trong sợi quang do hai nguyên nhân chính là
sự hấp th c a vật liệu và tán xạ ReyLeng. Hấp th vật liệu khá nhỏ lên có thể
bỏ qua. Tán xạ ReyLeng là loại tán xạ làm lệch hướng mạnh các ánh sáng có
bước sóng ngắn Do đó có thể làm giảm tán xạ ReyLeng bằng cách t ng độ dài
bước sóng.
Tán sắc (Dispersion): là hiện tượng các thành phần khác nhau c a tín hiệu cần
truyền đi với tốc độ khác nhau trong sợi quang. Tán sắc gây ra hiện tượng giãn
10
xung ánh sáng ở đầu ra, gây nhiễu chồng ph và là nguyên nhân chính dẫn đến
hạn chế c a khoảng cách truyền trong sợi quang ngày nay.
Các hiệu ứng phi tuyến: Khi truyền nhiều mode trong sợi quang, hiện tượng phi
tuyến gây ra hiện tượng nhiễu tại đầu thu và giảm công suất tín hiệu truyền.
11
Chương : ạng u ng D
2.1. Giới thiệu chung
Sự phát triển nhanh chóng c a các mô hình truyền số liệu đ c biệt là Internet đã làm
bùng n nhu cầu t ng b ng thông Nhu cầu b ng thông t ng đột biến với nhiều ứng d ng
mới phong phú như thương mại điện tử, video yêu cầu, truyền hình qua Internet
(IPTV),...T đó cho thấy nhu cầu sử d ng b ng thông rộng đang rất bức thiết. Trong bối
cảnh Internet Protocol IP đang n i lên như là nền tảng chung c a mọi loại hình d ch v
trong tương lai các nhà cung cấp d ch v truyền dẫn bắt buộc phải xem xét lại phương
thức truyền dẫn nhằm tối ưu hơn cho việc tận d ng b ng thông
Để thích ứng với sự phát triển không ng ng đó và thỏa mãn yêu cầu tính linh hoạt
về thay đ i mạng, các công nghệ truyền dẫn khác nhau đã được nguyên cứu, triển khai và
thử nghiệm và đưa vào ứng d ng như:
Truyền dẫn ghép kênh phân không gian SDM (Space Devision Multiplexing):
đây là một phương pháp rất đơn giản, chỉ đơn thuần là t ng số lượng sợi quang,
tốc độ đường truyền vẫn giữ nguyên. Ta có thể chọn SDM nếu tuyến đường cần
t ng b ng thông đã có sẵn số lượng các sợi quang chưa d ng và khoảng cách
truyền đ ngắn để không cần dùng các bộ l p, bộ khuyếch đại.
Truyền dẫn ghép kênh phân thời gian TDM (Time Devision Multiplexing): ở
phương pháp này thời gian sử d ng, tức là thời gian sử d ng đường truyền được
chia thành nhiều khung. Mỗi khung được chia thành nhiều khe thời gian và mỗi
người sẽ sử d ng một khe thời gian dành riêng cho m nh để ph c v việc truyền
tin
Hình 2.1 Hệ thống TDM
12
Truyền dẫn gh p kênh phân bước sóng WDM (Wavelength Devision
Multiple ing : đây là phương pháp gh p nhiều bước sóng để có thể truyền trên
một sợi quang, không cần t ng tốc độ truyền dẫn trên một bước sóng.
Hình 2.2 Hệ thống WDM
Trong những phương pháp trên công nghệ gh p kênh phân bước sóng DM được
ưa chuộng hơn cả Điều này là 2 công nghệ SDM và TDM điều bộc lộ những khuyết điểm
đáng kể:
Với SDM khi khoảng cách truyền xa cần phải lắp thêm các bộ l p và bộ
khuyếch đại Điều này sẽ làm cho chi ph t ng lên rất lớn do mỗi sợi quang được
lắp thêm điều cần một số lượng bộ l p, bộ khuyếch đại như nhau
Với TDM cũng có chi ph nắp đ t hệ thống tương đối cao đ c biệt TDM gây
lãng phí một số kênh thông tin khi mỗi khe thời gian được dự trữ ngay cả khi
không có dữ liệu để gửi và ph a thi khó kh n khi phân biệt các khe thời gian
thuộc kênh nào để giải ghép kênh tín hiệu.
WDM chính là tiến bộ lớn nhất trong công nghệ truyền thông quang, nó cho phép
t ng dung lượng c a kênh mà không cần t ng tốc độ đường truyền hay dùng thêm các sợi
quang.
2.2. Nguyên lý hoạ động
2.2.1. Tổng quan
13
Nguyên lý cơ bản c a gh p kênh phân bước sóng là công nghệ truyền đồng thời
nhiều bước sóng tín hiệu quang trong một sợi quang. Ở đầu phát, nhiều tín hiệu quang có
bước sóng khác nhau được t hợp lại gh p kênh được truyền đi trên một sợi quang. Ở
đầu thu, tín hiệu t hợp đó được phân giản ra (tách kênh), khôi ph c lại các tín hiệu gốc
rồi chia vào các thiết b đầu cuối khác nhau.
2.2.2. Sơ đồ hoạ động
Như minh họa trên hình 2.3 để đảm bảo việc truyền nhận nhiều bước sóng trên một
sợi quang, hệ thống WDM phải hoạt động dựa các chức n ng sau:
Hình 2.3 Nguyên lý hoạt động c a hệ thống
Phát tín hiệu: trong hệ thống WDM, nguồn phát quang dùng là laser. Yêu cầu
đối với nguồn phát laser là phải có độ rộng ph h p bước sóng phát n đ nh,
mức công suất phát bước sóng trung tâm độ rộng ph phải nằm trong giới hạn
cho phép
Ghép/tá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
14
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
15
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)
16
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.
17
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.
18
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
19
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
20
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
21
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)
22
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:
23
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.
24
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 }
25
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.
26
Để 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)
4)
5)
6)
Create Queue Q = Φ;
Insert v into Q;
Mark v is explore;
while (!Q.empty() ) do
w is front Q;
7)
8)
9)
for ( u incident w) do
if (u is unexplored)
then do
10)
11)
12)
13)
14)
15)
Insert u into Q
Mark u is explore
end – if;
end – for;
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
27
Tải về để xem bản đầy đủ
58 trang
28/04/2025
150
Bạn đang xem 30 trang mẫu của tài liệu "Khóa luậ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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- khoa_luan_thuat_toan_gen_trong_bai_toan_dinh_tuyen_va_phan_b.pdf
