LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "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": http://123doc.vn/document/1039358-nghien-cuu-dinh-tuyen-va-gan-buoc-song-trong-mang-wdm-su-dung-phuong-phap-tinh-toan-tien-hoa-lai.htm
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
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
mỗi path gồm một số fiber, mà trên mỗi fiber này, bạn có thể có W
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
với bài toán RWA là nó đưa ra hai điều kiện sau:
Điều kiện tính liên tục bước sóng: một 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 đến đích.
Hình 1.7: Điều kiện tính liên tục bước sóng
Đ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.8: Mạng WDM định tuyến bước sóng
1.3. Động cơ và mục tiêu nghiên cứu.
1.3.1. Động Cơ
Để 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
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ố. 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. 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.
6
+ Giải bài toán RWA được xây dựng ở trên bằng thuật toán
di truyền để tối ưu hóa các tham số mạng khác nhau.
1.4. Nội dung và đóng góp của luận văn.
1.4.1. Nội dung của luận văn
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 đề
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.
Chương 2: Giới thiệu bài toán RWA, các mục tiêu thiết kế,
các phương pháp tiếp cận bài toán RWA: heuristic và meta-
heuristic.
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
truyền trong RWA đa mục tiêu.
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
toán tiến hóa lai và kết quả mô phỏng bài toán RWA.
1.4.2. Những đóng góp của luận văn.
Kết quả của đề tài có thể ứng dụng cho thiết kế mạng quang
định tuyến bước sóng WDM hiệu quả hơn. Bằng việc sử dụng tiếp
cận đa mục tiêu thay cho chỉ xem xét từng mục tiêu một cách độc
lập, nghiệm thu được trong việc giải bài toán RWA bằng phương
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ó
cung cấp cho nhà thiết kế mạng những thông tin bù trừ bổ ích giữa
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.
Đề tài cũng làm cơ sở định hướng nghiên cứu cho các đề tài
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.
CHƯƠNG 2:ĐỊNH TUYẾN VÀ GÁN BƯỚC
SÓNG TRONG MẠNG WDM
2.1. Giới thiệu bài toán RWA.
Phân loại bài toán RWA được thể hiện trong Bảng 2.1.
Bảng 2.1: Phân loại RWA
Phân loại RWA
Kiểu lưu lượng Static,Dynamic
Hàm mục tiêu Max-RWA,Min-RWA
Công thức ILP Link-based, Path-based
Chuyển đổi bước sóng Full,Sparse,None
Cáp quang Single,Multiple
Yêu cầu Request multiplicity
RWA bài toán được coi là một bài toán NP-đầy đủ. Phức tạp
của bài toán RWA phát sinh từ hai sự kiện sau đây:
(i) Ràng buộc bước sóng liên tục : Một lightpath phải chiếm
cùng bước sóng trên tất cả các sợi liên kết mà qua đó nó đi qua.
(ii) Ràng buộc bước sóng riêng biệt: Hai lightpaths phải
không được chỉ định cùng một bước sóng trên một liên kết nào.
7
2.2. Cách tiếp cận heuristic đối với bài toán RWA.
Chlamtac[8] đề xuất khái niệm về Lightnet kiến trúc để đối
phó với các vấn đề không phù hợp giữa tốc độ xử lý điện tử và
truyền dẫn quang băng thông trong WDM dựa trên các mạng diện
rộng.
Zhang và Acampora[26] đã đề xuất một thuật toán hiệu quả
để 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
mạng trong đó các phương tiện vật lý bao gồm các phân đoạn sợi
quang được kết nối qua các thiết bị chuyển mạch bước sóng quang
chọn lọc.
Banerjee [4] đã xem xét các vấn đề thiết kế một cấu trúc liên
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
nhu cầu giao thông giữa những người sử dụng cuối cùng.
Banerjee và Mukherjee[2] đã trình bày một công thức lập
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
một mạng bước sóng định tuyến quang học, trong trường hợp
không có ràng buộc bước sóng liên tục.
2.3. Cách tiếp cận meta-heuristic đối với bài toán RWA.
Các giải pháp meta Heuristic thiết kế các cấu trúc liên kết
trong khu vực mạng mesh diện rộng để giảm thiểu chi phí mạng.
Các thuật toán di truyền đã được sử dụng để giải quyết bài toán
RWA theo giả định khác nhau. Các tác giả đã xây dựng các vấn đề
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
tiến hóa.
MC Sinclair[23] đã đề xuất một chi phí tối thiểu định tuyến
đườ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.
Zhong Pan [21] phát triển một chức năng phù hợp mớ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ử
dụng thuật toán di truyền. Mục tiêu là để định tuyến mỗi lightpath
theo cách để giảm thiểu số lượng bước sóng cần thiết để nhườ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
chi phí trong việc thiết lập các lightpaths.
D. Bisbal[5] đề xuất một thuật toán di truyền để thực hiện
định tuyến động và gán bước sóng trong định tuyến bước sóng
mạng quang không có bước sóng chuyển đổi.
Le[15] đã đề xuất một thuật toán di truyền cải tiến để giải
quyết bài toán RWA động. Để đạt được cân bằng tải tốt hơn giữa
các cá thể, họ đã xây dựng một hàm thích hợp mới, đồng thời liên
quan đến chiều dài đường đi, số bước sóng tự do và khả năng
chuyển đổi bước sóng trong tuyến đường đánh giá.
2.4. Các mục tiêu thiết kế trong bài toán RWA.
Bài toán thiết kế đa mục tiêu được thể hiện với các hàm đa
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
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
một lúc.
Có một số nghiên cứu[20] được lồng ghép trong các tài liệu
mà hình thành heuristics và meta-heuristics cho việc thiết kế hiệu
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.
CHƯƠNG 3:
MÔ HÌNH ĐA MỤC TIÊU CHO BÀI TOÁN RWA
8
3.1. Xây dựng bài toán đa mục tiêu.
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
các phương pháp tối ưu đã được sử dụng để giải quyết bài toán này.
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.1.
ký hiệu sử dụng.
Ký hiệu được sử dụng trong việc xây dựng ILP được quy
định như sau:
+ V = Thiết lập các nút trong mạng.
+ E = Thiết lập các liên kết sợi hai chiều trong mạng.
+ 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.
+ (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 D
ij
dùng
để chỉ một giá trị đầy đủ ghi rõ nhu cầu tối đa giữa các cặp nút (i, j)
và D
ij
= D
ji
.
+
-
(v) = Thiết lập các liên kết sợi được sử dụng bởi
lightpath vào nút v.
+ +(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.
3.1.2. Các biến sử dụng
Các biến được sử dụng trong việc xây dựng ILP được quy
định như sau:
3.1.3. Xây dựng ILP đa mục tiêu.
Trong phần này, xây dựng các bài toán RWA như là một bài
toán đa mục tiêu ILP. Lightpaths được nhóm lại theo cặp nút
nguồn-đích của nó. K là tập hợp các yêu cầu lightpath. Thì K được
tính theo công thức:
jiandijKjiKjiKK
VVji
),(
|),(),();,(
2
Vi Vj
ij
D
K
jiij
DDijKjiK ),(),(
3.1
Các hàm mục tiêu mà chúng ta muốn tối ưu hóa được quy định như
sau:
+ Giảm thiểu ách tắc của nhiều nhất liên kết tắc nghẽn trong
mạng:
0:),( ),(
,
),(max
ij
DVVji jiKk Ww
ew
k
Ee
jibMinimize
(3.4)
B
k
(i,j) =
1 nếu lightpath k giữa cặp nút (i, j) được thiết lập
0 nếu không
),( jiB
k
1 nếu lightpath k giữa cặp nút (i, j) được thiết lập bước
sóng w
0 nếu không
),(
,
jiB
e
k
(i,j) =
1 nếu lightpath k giữa cặp nút (i, j) được thiết
l
ập
bư
ớc sóng w với liên kết e
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
nghẽn ít nhất liên kết trong mạng:
0:),( ),( 0:),( ),(
,,
}),(min),(max{
ij ij
DVVji jiKk DVVji jiKk Ww
ew
k
Ee
Ww
ew
k
Ee
jibjibMin
(3.5)
+ Giảm thiểu sự khác biệt giữa các liên kết tắc nghẽn nhiều
nhất và ùn tắc trung bình của tất cả các liên kết trong mạng:
Min {
E
jib
jib
ij
ij
DVVji jiKk Ww
ew
k
DVVji jiKk Ww
ew
k
Ee
0:),( ),(
,
0:),( ),(
,
),(
),(max
} (3.6)
+ Hạn chế số lượng tối đa của bước nhảy đi qua trung gian:
Ee Ww
ew
k
jiKk
jibMinimize
ij
Dji
),(max
,
),(
0:),(
(3.7)
+ 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:
0:),( ),(
,
}0),(|{
ij
Dji jiKk Ww
ew
k
jibEeMinimize
(3.8)
+ Hạn chế chiều dài tuyến đường tối đa:
Ee Ww
ew
ke
jiKk
jibdMinimize
ij
Dji
0),(|(max
,
),(
0:),(
(3.9)
Trong đó d
e
= Trễ liên quan đến liên kết e.
+ Hạn chế tối đa tổng chiều dài tuyến đường:
0:),( ),(
,
)0),(|(
ij
Dji jiKk Ee Ww
ew
ke
jibdMinimize
(3.10)
3.2. Các giải thuật tiến hóa trong tối ưu hóa đa mục tiêu.
3.2.1. Thuật toán đáp ứng tiến hóa.
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
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
đại diện cho một nghiệm tiềm năng cho các bài toán đang được
xem xét.
Toàn bộ quá trình được phác thảo trong hình 3.1.
Hình 3.1: Tác giả của phương pháp tiến hóa để tối ưu hó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) P0 ← áp dụng σ trên P; / * lựa chọn * /
(b) P00 ← áp dụng ω1, · · ·, ωk P0; / * sinh sản * /
(c) P ← áp dụng ψ trên P và P00; thay thế / * /
Endwhile.
Quá trình này được lặp đi lặp lại cho đến khi một tiêu chí
chấm dứt nhất định (thường là đạt được một số lượng tối đa lần lặp
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
là một thế hệ.
3.2.2. Giải thuật SPEA2
Thuật toán tiến hóa cải tiến đầy đủ Pareto (SPEA2) ) là nổi
tiếng như là một kỹ thuật hiệu quả để tìm kiếm tập hợp Pareto tối
ưu trong bài toán tối ưu hóa đa mục tiêu chung. SPEA2 đã được đề
xuất bởi Zitzler[29]. SPEA2 là một thuật tiến hóa đa mục tiêu toán
thế hệ thứ hai (MOEA), thành công của thuật toán được sử dụng để
giải quyết một số vấn đề kỹ thuật.
N đại diện cho kích thước quần thể,
N
là kích thước lưu trữ.
1. Tạo một cá thể ban đầu P
0
và tạo khoảng trống lưu trữ
0
P
.
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.
3. Tính toán giá trị sức mạnh của các cá nhân trong P
t
và
t
P
.
4. Xếp hạng cá nhân theo giá trị sức mạnh của họ và k-
khoảng cách hàng xóm gần nhất nơi
NNk
(3.26)
5. Môi trường lựa chọn
a.Nếu kích thước của
1t
P
vượt quá thì loại bỏ các
cá nhân có tối thiểu k- khoảng cách hàng xóm gần nhất trong
1t
P
cho đến khi
1t
P
=
N
b.Nếu kích thước của
1t
P
là ít hơn so với
N
thì Điền
1t
P
với các cá nhân chiếm ưu thế trong P
t
và
t
P
.
6. Biến đổi và đảo chéo các cá nhân trong P
t
.
7. Lặp lại các bước 2-6, cho đến khi thỏa mãn với số lượng
tối đa của lặp.
3.3. Các giải thuật di truyền trong RWA đa mục tiêu.
Thuật toán di truyền (GA) đã được sử dụng để giải quyết bài toán
tối ưu hóa đa mục tiêu ở một số lĩnh vực. Khả năng GA đa mục
tiêu được khuyến khích để tìm kiếm theo hướng đúng Pareto trước
trong khi vẫn duy trì sự đa dạng trong quần thể. Đầu tiên,
Schaffer[24] đề xuất đánh giá thuật toán di truyền vector tiến
hóa(VEGA) để giải quyết tối ưu hóa đa mục tiêu trong từng mục
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
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
tiêu di truyền đa mục (MOGA) để tìm kiếm các nghiệm trong tất cả
các hướng có thể không gian mục tiêu.
Ví dụ về GA thảo luận bởi Konak trong[13] bao gồm các
thuật toán di truyền đa mục tiêu khác nhau. Thảo luận này phân
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:
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).
2. So sánh trực tiếp của độ chi phối Pareto.
a. GA đánh giá vector (VEGA).
b. Niched Pareto GA (NPGA).
3. Tiếp cận xếp hạng cụ thể.
a. GA Đa mục tiêu (MOGA).
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. Thuật toán tiến hóa đầy đủ Pareto (SPEA) và bản
cải thiện SPEA là (SPEA2).
4. Phương pháp tiếp cận dựa trên không dân cư.
a. Chiến lược tiến hóa Pareto lưu trữ (PAES).
CHƯƠNG 4: MÔ PHỎNG VÀ ĐÁNH GIÁ KẾT
QUẢ
4.1. Mô hình mô phỏng.
Trong phần này, bài toán thiết kế RWA đa mục tiêu và mô
hình thiết kế sẽ được trình bày. Bài toán RWA trong thiết kế mạng
quang WDM được xem xét để hỗ trợ nhiều yêu cầu liên lạc đồng
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
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ố
yêu cầu được chấp nhận từ một tập các yêu cầu đã định sẵn và để
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ố
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
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
đượ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
bao gồm:
1. Mục tiêu thiết kế đầu tiên là để tối đa hóa số lượng yêu
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
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á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
hạn kênh bước sóng trên mỗi cạnh mạng.
2. Mục tiêu thiết kế thứ hai là để giảm thiểu số lượng bước
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
về yêu cầu kết nối được chấp nhận. Ta giả định rằng mỗi cạnh
mạng có cùng số lượng bước sóng. Mục tiêu thiết kế này là để
giảm thiểu số lượng các bước sóng trong khi đáp ứng được lượng
yêu cầu được chấp nhận.
Thông tin đã cho:
- Cấu hình mạng
- Tập các yêu cầu (tức là, các cặp nút nguồn đích với yêu
cầu băng thông).
12
Tối thiểu hóa:
-
}min{
wcobi
fff
(4.1)
-
Q
f
A
c
(4.2)
-
max
K
K
f
A
w
(4.3)
Tùy theo:
NiQq
otherwise
Desti
sourcei
iEe Kk
ke
q
iEe Kk
ke
q
,
,0
,
,
,*)(
,
)(*,
,
(4.4)
KkEeQq
k
q
ke
q
,,;
,
(4.5)
Kk
k
q
Qq;1
(4.6)
EeQq
Kk
q
ke
q
,;
,
(4.7)
qA
Q
(4.8)
k
ke
q
KkEe ,;
,
(4.9)
Kk
kA
K
(4.10)
T
Q
Q
A
(4.11)
Ee
ke
q
KkQqH ,;
,
(4.12)
KkQqLD
Ee
ke
qe
,;).(
,
(4.13)
q
};1,0{
(4.14)
Kk
k
};1,0{
(4.15)
KkQq
k
q
,};1,0{
(4.16)
EeKkQq
ke
q
,,};1,0{
,
(4.17)
4.2. Định tuyến và gán bước sóng sử dụng phương pháp
tiến hóa lai.
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
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
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
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
(NSGA-II) được biết như là một kỹ thuật hiệu quả để tìm kiếm tập
hợp tối ưu Pareto trong bài toán tối ưu hóa đa mục tiêu chung.
NSGA-II là một thuật toán rất nhanh để có thể hội tụ nhanh chóng
về mặt trước Pareto. NSGA-II đã được đề xuất bởi Deb[11] và
được mô tả như sau.
Gọi R
t
là đại diện cho tổng số quần thể, P
t
là quần thể được
bảo tồn, Q
t
là quần thể được tái tổ hợp của thế hệ t. F
i
là mặt trước
i, trong đó i là một số nguyên dương. Lưu ý rằng các nghiệm trong
mặt trước F
1
là tốt hơn so với những nghiệm trong mặt trước của
F
2
, và cứ như vậy tiếp tục.
1. Kết hợp P
t
và Q
t
để R
t
.
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 R
t
cho mặt trước (F
1
, F
2
, F
3
, )
bằng cách sử dụng thuật toán sắp xếp nhanh không bị chi phối
(R
t
).
4.
Tính khoảng cách tạo đám trong mỗi F
i
bằng cách sử dụng
thuật toán gán khoảng cách tạo đám (F
i
).
5.
Xếp loại quần thể R
t
(sắp xếp theo bậc mặt trước (F
i
) 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ể R
t
và gán
cho P
t+1
.
7. Tái kết hợp (qua lai tạo và đột biến) quần thể P
t +1
và gán
cho Q
t+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
bởi số lần lặp tối đa.
Từ thuật toán NSGA-II, hai thủ tục quan trọng của NSGA-II
bao gồm thủ tục gán độ hợp (xếp loại không bị chi phối nhanh và
gán khoảng cách tạo đám) và thủ tục lựa chọn. Quần thể xem xét
bao gồm nhiều cá thể. Mỗi cá thể trong quần thể sẽ luôn được gán
một thứ hạng hoặc bậc vì lý do đó mà các cá thể ưu tú được duy trì
cho thế hệ sau. Các cá thể ưu tú sẽ có một thứ hạng thấp hơn hoặc
tốt hơn so với những cá thể khác. Thứ hạng của các nghiệm được
tính toán từ sắp xếp không bị chi phối nhanh trước. Sau đó, các
nghiệm trong cùng một mặt trước được sắp xếp bằng việc sử dụng
thuật tóan gán khoảng cách tạo đám Việc phân hạng được thể hiện
trong thủ tục 1 và 2 trong hình 4.2.
Hình 4.2: Thủ tục NSGA-II
4.2.1.1. Gán độ hợp (Fitness assignment)
NSGA-II xếp thứ hạng cho cá thể i trong quần thể sử dụng
bậc mặt trước (F
i
) và khoảng cách tạo đám (D
i
). Các bậc mặt trước
(F
i
) được gán bằng cách sử dụng thuật toán sắp xếp không bị chi
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
Gọi F
i
là mặt trước i trong đó i là số nguyên dương.
1. Đối với mỗi cá thể p trong quần thể
a. Tìm tập các cá thể bị chi phối bởi p.
b. Tìm các thể không bị chiếm ưu thế và gán cho mặt
trước F
1
trước tiên.
2. Gán các cá thể khác cho mặt trước thứ hai, thứ ba, và tiếp
đó, cho đến khi tất cả các cá thể đều có mặt trước của chúng.
Gán khoảng cách tạo đám (Crowding-distance-
assignment
)
Gọi F
i
là mặt trước i trong đó i là số nguyên dương, D
i
là
khoảng cách tạo đám của nghiệm i trong mặt trước F
i
, N là số
lượng nghiệm trong mặt trước F
i
,
max
m
f
và
min
m
f
là các giá trị cực đại
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 (D
i
) = 0, cho
tất cả các cá thể trong F
i
.
2. Đối với mỗi mục tiêu m
a. Sắp xếp theo thứ tự tăng dần các cá thể i theo giá
trị mục tiêu f
m
.
b. Đặt khoảng cách tạo đám (D
i
) của các cá thể trong
bậc đầu tiên và bậc cuối cùng = (tức là, D
1
= và D
N
= )
c. Đối với tất cả các cá thể khác (i = 2 tới N-1). Tính
khoảng cách tạo đám của cá thể i sử dụng
minmax
(
))1()1((
mm
mm
ii
ff
ifif
DD
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
những cá thể khác sẽ được lựa chọn trước tiên. Thủ tục lựa chọn
này được trình bày như sau.
4.2.1.2. Thủ tục lựa chọn
Ban đầu, cá thể có một bậc mặt trước thấp hơn sẽ được
chọn. Nếu không gian có sẵn của quần thể trong thế hệ tiếp theo
không thể hỗ trợ toàn bộ các cá thể trong mặt trước F
i
, cá thể trong
cùng một mặt trước có khoảng cách tạo đám lớn hơn sẽ được lựa
chọn trước tiên như thể hiện trong thủ tục 3 hình. 4.2.
Thủ tục lựa chọn
1.Đối với mỗi cá thể i
a. Chọn toàn bộ các cá thể có bậc mặt trước thấp hơn
trước tiên.
b. Nếu toàn bộ các cá thể trong mặt trước F
i
không
thể được lấp đầy trong không gian có sẵn trong các thế hệ tiếp theo,
thì chọn các cá thể có số khoảng cách tạo đám lớn hơn trước tiên.
4.2.2.Thuật toán di truyền cho việc định tuyến và gán bước sóng
theo bậc tối thiểu trước tiên (GA-MDF)
Thuật toán này là một thuật toán heuristic gọi là thuật toán
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ước tiên (GA-MDF). GA-MDF có hai phần là định tuyến bằng
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.
4.2.2.1. Thuật toán di truyền cho định tuyến
Trước đây, thuật toán di truyền được sử dụng để giải quyết
bài toán định tuyến trong mạng quang WDM [3]. Banerjee và
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.
Mã hóa chuỗi: Mã hóa chuỗi là một quá trình mã hóa bài
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
chuỗi ở đây, là một tập hợp các số nguyên cái chỉ ra tuyến đường
Không có nhận xét nào:
Đăng nhận xét