Luận án Điều khiển tối ưu luồng video điểm - đa điểm trong mạng 5G siêu dày đặc

ownlink Resource Sharing and Caching 
Helper Selection). 
Theo cách tiếp cận chung, các tác giả trong [47] đã giới thiệu một mô hình phân 
tích và tối ưu cho D2DC điểm - đa điểm. Nghiên cứu này xem xét đánh giá các thông 
số hiệu suất quan trọng của D2DC như xác suất bao phủ, số lượng trung bình của đầu 
thu được bao phủ và thông lượng của chúng. Mô hình đề xuất cũng tối ưu hiệu suất 
truyền thông điểm - đa điểm bằng cách tìm tỷ lệ truyền thông điểm - đa điểm tối ưu và 
số lần truyền lại tối ưu. 
Trong [48] và [49], bằng cách khai thác cụm truyền thông điểm - đa điểm, các 
CH được chọn để truyền cho một số RU gần nhau. Kết quả cho thấy các cách thức lựa 
chọn CH được đề xuất làm giảm lưu lượng tại MBS, giảm chi phí truyền video và thời 
gian truyền lại trung bình. Để đạt được hiệu quả cao hơn, một phương thức kết hợp 
giữa truyền thông di động thông thường và D2DC được nghiên cứu cho các dịch vụ 
video truyền thông điểm - đa điểm [50]. Phương thức được đề xuất sử dụng D2DC dựa 
trên tần số đơn cho phép các CH được chọn truyền video điểm - đa điểm tới các RU. 
Mục tiêu là tối đa hóa tốc độ dữ liệu bằng cách phân bổ tài nguyên vô tuyến. 
Mối quan hệ xã hội giữa các MU cũng được xem xét trong D2DC để cải thiện 
hiệu suất truyền điểm - đa điểm [38], [67], [76]–[78]. Trong [38] và [76], CH và RU 
được nhóm thành cụm dựa trên các tính chất vật lý (ví dụ: khoảng cách và chất lượng 
kênh vô tuyến) và cả các mối quan hệ xã hội của chúng. Năng lượng và tài nguyên 
kênh truyền được mô hình toán và giải để cực đại thông lượng hệ thống đồng thời 
giảm thiểu khoảng cách kênh và số lượng kênh cần thiết trong các cụm truyền điểm - 
40 
đa điểm khác nhau. Theo cách tiếp cận tương tự nhằm khai thác các mối quan hệ xã 
hội, các tác giả trong [67], [77], [78] đã đề xuất một cơ chế phân cụm và lựa chọn CH 
để tăng cường hiệu suất năng lượng của mạng D2DC điểm - đa điểm và cải thiện tổng 
tỷ lệ các mối quan hệ xã hội của tất cả các RU. 
Các kỹ thuật D2DC điểm - đa điểm quan trọng khác được trình bày tại [51] và 
[79], trong đó, các tác giả xem xét đến vấn đề truyền đa chặng và phân cụm dựa trên 
chi phí. Trong [51], để tăng cường hiệu suất, nhiều cụm và các CH liên quan được 
thiết lập dưới dạng mạng đa chặng. Mỗi CH trung gian đóng vai trò là nút chuyển tiếp 
và là nút truyền điểm - đa điểm sao cho độ trễ giảm thiểu và hiệu suất năng lượng 
được đảm bảo đồng thời cực tiểu hóa số lần truyền dư thừa. Ngoài ra, làm thế nào 
khuyến khích MU trở thành CH và làm cách nào để cân bằng lợi ích và chi phí của 
CH, bài toán phân cụm dựa trên chi phí để chia sẻ nội dung qua D2DC điểm - đa điểm 
đã được nghiên cứu nhằm cải thiện lợi ích trung bình của RU [79]. 
Có thể nhận thấy rằng, các nghiên cứu đã nói ở trên không xem xét đến lợi ích 
của việc tận dụng các tài nguyên kênh truyền xuống có sẵn để chia sẻ với các CH 
trong truyền thông điểm - đa điểm. Một số nghiên cứu khác đã thực hiện D2DC điểm - 
đa điểm để cực đại hiệu quả năng lượng hệ thống [39] và thông lượng hệ thống [41]. 
Tuy nhiên, các tác giả trong [39] và [41] đã không sử dụng phương thức lựa chọn CH 
để cải thiện hơn nữa hiệu suất của D2DC điểm - đa điểm có phân cụm. 
3.1.3. Tính mới của cơ chế DRS-CHS 
Optimal
Controller
(MBS)
Actuator
(v*)
Control index
Plant
(SUs, CHs, IoT 
devices)
(C*)
Maximum video 
streaming capacity 
at MU and devices
Network
System parameters
SINR (0) 
Hình 3.1. Sơ đồ khối cơ chế DRS-CHS điều khiển luồng video điểm - đa điểm 
41 
Từ những phân tích về sự cần thiết của cơ chế DRS-CHS và hiện trạng các 
nghiên cứu liên quan, để khắc phục các vấn đề còn tồn đọng của D2DC điểm - đa điểm 
có phân cụm, trong Chương 3 này, tôi đề xuất sơ đồ khối cơ chế DRS-CHS điều khiển 
luồng video điểm - đa điểm như được mô tả trong Hình 3.1. Trong hệ thống này, giả 
sử rằng 5G UDN có: 1) một số người dùng chia sẻ (SU) sẵn sàng chia sẻ tài nguyên 
kênh truyền xuống với các người dùng khác; 2) một số người dùng trợ giúp lưu trữ 
(CH), tức là các MU đã lưu các video phổ biến; và 3) nhiều người dùng yêu cầu (RU) 
yêu cầu các video giống nhau. Sau đó, các kỹ thuật phân cụm và D2DC được áp dụng 
để điều khiển luồng video điểm - đa điểm từ CH đến các RU hoặc từ MBS đến RU 
theo cơ chế DRS-CHS. Để thực thi cơ chế DRS-CHS, bộ điều khiển tối ưu (MBS) sẽ 
thu thập các thông tin của hệ thống và thông tin QoS đặc trưng bởi tỷ số tín hiệu trên 
nhiễu trắng và can nhiễu 0 (SINR - Signal to Interference plus Noise Ratio) phản hồi 
từ các SU nhằm đảm bảo chất lượng cho các SU ở mức ngưỡng cho phép khi chúng 
chia sẻ tài nguyên kênh truyền xuống hỗ trợ D2DC. Các thông tin được thu thập này sẽ 
cho phép MBS xây dựng bài toán tối ưu DRS-CHS và giải nó để xác định chỉ số điều 
khiển v* để điều khiển quá trình 1) chọn lựa vị trí lưu trữ (tại chính MBS hoặc tại CH) 
và 2) chọn lựa SU nào để chia sẻ tài nguyên phổ tần cho CH nào trong cụm nào nhằm 
cung cấp cho RU dung lượng luồng video điểm - đa điểm cực đại C*. Những đóng góp 
và điểm mới của cơ chế DRS-CHS trong Chương 3 được tóm tắt ở Bảng 3-1, cụ thể 
như sau: 
• Đề xuất một mô hình điều khiển luồng video điểm - đa điểm trong 5G UDN. 
Mô hình này tận dụng 1) tài nguyên kênh truyền xuống của SU, 2) các video 
được lưu trong CH, và 3) đặc tính quảng bá tự nhiên của môi trường truyền 
vô tuyến, để truyền các video được lưu trữ trong các CH tới các RU qua 
D2DC điểm - đa điểm trong phạm vi gần. 
• Mô hình hệ thống được xây dựng dưới dạng bài toán điều khiển tối ưu DRS-
CHS thỏa mãn ràng buộc về tính công bằng QoS (SINR) tại các SU. Giải bài 
toán tối ưu để tìm ra cặp SU và CH tốt nhất, nghĩa là điều khiển quá trình 
chọn lựa SU nào sẽ chia sẻ tài nguyên kênh truyền xuống cho CH nào để 
phục vụ các RU trong các cụm khác nhau với dung lượng là lớn nhất qua 
D2DC điểm - đa điểm (tái sử dụng tài nguyên kênh truyền xuống được chia 
42 
sẻ bởi SU). Cơ chế DRS-CHS cũng cho phép điều khiển các RU hoặc là nhận 
video từ các CH thông qua D2DC điểm - đa điểm hoặc là từ MBS thông qua 
truyền thông điểm - đa điểm của mạng di động thông thường sao cho tổng 
dung lượng luồng video thu được là cực đại. 
• Vì kích thước của 5G UDN là rất lớn nên thuật toán tìm kiếm vét cạn khó 
thực thi. Do đó, tôi đề xuất thuật toán di truyền có chỉnh sửa (GA - Genetic 
Algorithms) khả thi hơn để giải bài toán điều khiển tối ưu được đề xuất trong 
5G UDN. Kết quả mô phỏng được trình bày và thảo luận để chứng minh lợi 
ích của giải pháp DRS-CHS được đề xuất so với các giải pháp thông thường 
khác. 
Bảng 3-1. Tóm tắt các điểm mới và đóng góp của cơ chế DRS-CHS 
Cơ chế 
(Chương) 
Tiêu chí 
Giải 
thuật 
Cơ chế chia sẻ 
tài nguyên 
kênh truyền 
xuống 
Công bố 
Vị 
trí 
lưu 
trữ 
Mối 
quan 
hệ xã 
hội 
Tính 
công 
bằng 
QoS 
Cực 
đại 
dung 
lượng 
DRS-CHS 
(Chương 3) 
MBS 
CH 
 SU(0) ✓ GA 
1 SU chia sẻ 
cho 1 CH 
trong 1 cụm 
Bài báo tạp chí trong nước: 
Journal of Science and 
Technology: Issue on Information 
and Communications Technology 
SSC 
(Chương 4) 
MBS 
CH 
✓ 
SU(0) 
RU(C) 
✓ GA 
1 SU chia sẻ 
cho nhiều CH 
trong nhiều 
cụm 
Bài báo tạp chí quốc tế: IEEE 
Systems Journal (IF=4.5) 
DRS-MCS 
(Chương 5) 
MBS 
SBS 
CH 
 SU(0) ✓ 
Vét cạn, 
phân tán 
1 SU chia sẻ 
cho 1 CH trong 
1 cụm 
Bài báo tại Hội nghị quốc tế 
INISCOM’20 (International 
Conference on Industrial Networks 
and Intelligent Systems) 
Bố cục của Chương 3 được tổ chức như sau. Phần 3.2 đề xuất mô hình truyền 
video điểm - đa điểm trong 5G UDN và tính toán các thông số của hệ thống. Phần 3.3. 
xây dựng và giải bài toán tối ưu cho mô hình DRS-CHS được đề xuất bằng thuật toán 
GA. Kết quả mô phỏng, đánh giá và thảo luận được trình bày trong Phần 3.4. Cuối 
cùng là kết luận chương trong Phần 3.5. 
43 
3.2. Mô hình và tính toán các thông số hệ thống DRS-CHS 
3.2.1. Mô hình hệ thống DRS-CHS 
Từ các phân tích ở Chương 1 và các thảo luận ở phần 3.1, tôi đề xuất mô hình hệ 
thống DRS-CHS điều khiển luồng video điểm - đa điểm trong 5G UDN nhằm cực đại 
dung lượng người dùng được thể hiện trong Hình 3.2. 
1CH 
2CH 
1
CHM 
1RU 
2RU 
1
RUN 
CH
JM
1RU 
2RU 
RU
JN
Cellular links
D2D cluster 1
D2D cluster 2
D2D cluster J
Inteference links
Multicast links Cached videos
1SU 
SU3 
SUK 
1CH 
2CH 
2
CHM 1RU 
2RU 
2
RUN 
1CH 
2CH 
MBS 
Control signals
Feedback signals
Network
2SU 
Hình 3.2. Mô hình hệ thống DRS-CHS điều khiển luồng video điểm - đa điểm trong 5G UDN 
Mô hình này bao gồm một MBS và K SU chia sẻ tài nguyên kênh truyền xuống 
cho J cụm để thiết lập D2DC điểm - đa điểm. Cụm thứ j (j=1, 2, , J) có Mj CH (CH1, 
CH2, , CHMj) đã lưu video yêu cầu và Nj RU (RU1, RU2, , RUNj) yêu cầu video. 
Trong cụm thứ j, CH thứ m được chọn tối ưu từ Mj CH để cung cấp cho Nj RUs dung 
lượng luồng video cực đại. Khi MBS nhận được yêu cầu video, cơ chế DRS-CHS bắt 
đầu hoạt động theo 3 bước như sau: 
• Bước 1 – Phân cụm người dùng D2D: Trong bước này, MBS thiết lập người 
dùng D2D thành J cụm bằng cách sử dụng kỹ thuật phân cụm dựa trên D2D 
[14] để mở rộng vùng phủ sóng. Trong mỗi cụm, MBS biết được MU nào có 
lưu trữ video được yêu cầu hay không. Kết quả là, cụm thứ j có Mj CH và Nj 
RU có khả năng D2DC trực tiếp với nhau. 
44 
• Bước 2 – Xây dựng và giải bài toán tối ưu DRS-CHS: MBS tiếp tục thu thập 
các thông số của các kênh truyền vô tuyến từ nó đến các SU và các RU cũng 
như từ các CH đến các SU và các RU. Dựa trên những thông số này, MBS 
xây dựng bài toán tối ưu DRS-CHS, giải bài toán này sẽ cho ta chỉ số nhị 
phân điều khiển tối ưu quá trình chọn lựa SU và CH 𝑣𝑗
𝑘,𝑚
. Ở đây, 𝑣𝑗
𝑘,𝑚 = 1 
có nghĩa là SU thứ k được chọn để chia sẻ tài nguyên kênh truyền xuống của 
nó với CH thứ m nhằm thiết lập D2DC truyền video điểm - đa điểm từ CH 
thứ m đến Nj RU trong cụm thứ j, ngược lại 𝑣𝑗
𝑘,𝑚 = 0. Các giá trị tối ưu 𝑣𝑗
𝑘,𝑚
tìm được để cực đại dung lượng luồng video điểm - đa điểm của hệ thống. 
Trong quá trình tìm kiếm kết quả tối ưu 𝑣𝑗
𝑘,𝑚
, có 3 ràng buộc được xem xét 
bao gồm: 
i) ∑ ∑ 𝑣𝑗
𝑘,𝑚𝑀𝑗
𝑚=1
𝐾
𝑘=1 ≤ 1, j = 1, 2, , J để đảm bảo rằng một SU chỉ có thể 
chia sẻ tài nguyên kênh truyền xuống của nó cho tối đa một CH trong 
mỗi cụm; 
ii) ∑ ∑ 𝑣𝑗
𝑘,𝑚𝑀𝑗
𝑚=1
𝐽
𝑗=1 ≤ 1, k = 1, 2, , K đảm bảo một SU không thể chia sẻ 
tài nguyên kênh truyền xuống của nó với nhiều hơn một CH trong J cụm; 
iii) QoS (đặc trưng bởi SINR) tại SU được đảm bảo lớn hơn hoặc bằng mức 
ngưỡng 0, để hạn chế tác động nhiễu gây ra bởi D2DC điểm - đa điểm 
đến hiệu suất dung lượng của các SU, nghĩa là phải đảm bảo tính công 
bằng về QoS cho SU khi nó chia sẻ tài nguyên kênh truyền xuống. 
• Bước 3 – Truyền video điểm - đa điểm: Sau khi tìm được 𝑣𝑗
𝑘,𝑚
, các SU và CH 
tương ứng được chỉ định để chia sẻ tài nguyên đường xuống với CH nhằm 
thiết lập D2DC điểm - đa điểm truyền video đến các RU với dung lượng lớn 
nhất. Cần lưu ý rằng, nếu video được yêu cầu không nằm trong bất kỳ cụm 
nào hoặc chất lượng kênh truyền từ CH đến các RU kém hơn từ MBS đến các 
RU, thì video này được phân phối bởi MBS. 
45 
3.2.2. Tính toán các thông số của hệ thống DRS-CHS 
3.2.2.1. Dung lượng tại các RU 
Để tính được dung lượng phân phối video đến các RU, ta phải tính toán tỷ số tín 
hiệu trên nhiễu (SNR – Signal to Noise Ratio) của kênh truyền giữa CH thứ m và RU 
thứ n trong cụm thứ j như sau: 
𝛾𝑗
𝑚,𝑛 =
𝑃𝑗
𝑚𝐺𝑗
𝑚,𝑛
𝑁0
 (3.1) 
Trong đó 𝑃𝑗
𝑚 là công suất truyền của CH thứ m trong cụm thứ j, 𝐺𝑗
𝑚,𝑛
 là độ lợi 
kênh truyền giữa CH thứ m và RU thứ n trong cụm thứ j và N0 là công suất của nhiễu 
trắng Gaussian. Trong chương này, độ lợi kênh truyền được mô hình theo tài liệu [66], 
xác định bằng tích của hệ số fading phân phối mũ có trị trung bình là 1 ( exp(1)) và 
hàm suy hao đường truyền theo lũy thừa chuẩn có hệ số suy hao lũy thừa là . 
Tuy nhiên, bởi vì kênh truyền giữa CH thứ m và RU thứ n trong cụm thứ j sử 
dụng lại tài nguyên kênh truyền xuống của SU thứ k để thiết lập D2DC điểm - đa 
điểm, nên nó bị ảnh hưởng bởi can nhiễu do công suất truyền từ MBS (𝑃0,𝑘) đến SU 
thứ k. Bằng cách thêm vào chỉ số điều khiển 𝑣𝑗
𝑘,𝑚
 trong DRS-CHS. Công thức (3.1) 
được viết lại thành 
𝛾𝑗
𝑘,𝑚,𝑛 =
𝑣𝑗
𝑘,𝑚𝑃𝑗
𝑚𝐺𝑗
𝑚,𝑛
𝑁0 + 𝑃0,𝑘𝐺𝑗
0,𝑛 (3.2) 
Trong đó, 𝐺𝑗
0,𝑛
 là độ lợi kênh giữa MBS và RU thứ n trong cụm thứ j. 
Trong trường hợp không có SU chia sẻ tài nguyên kênh truyền xuống với bất kỳ 
CH nào trong cụm thứ j, video được phân phối bởi MBS. Ta có SNR của kênh truyền 
từ MBS đến RU thứ n được tính bởi 
𝛾𝑗
0,𝑛 =
(1 − ∑ ∑ 𝑣𝑗
𝑘,𝑚𝑀𝑗
𝑚=1
𝐾
𝑘=1 )𝑃𝑗
0,𝑛𝐺𝑗
0,𝑛
𝑁0
 (3.3) 
Trong đó, 𝑃𝑗
0,𝑛
 là công suất truyền từ MBS đến RU thứ n trong cụm thứ j. 
46 
Cuối cùng, tổng dung lượng luồng video tại RU thông qua D2DC điểm - đa điểm 
từ CH và thông qua truyền thông điểm - đa điểm từ MBS được xác định bởi 
𝐶𝑅𝑈 = 𝑊∑[∑∑∑log2(1 +
𝑁𝑗
𝑛=1
𝑀𝑗
𝑚=1
𝐾
𝑘=1
𝛾𝑗
𝑘,𝑚,𝑛) +∑ log2(1 + 𝛾𝑗
0,𝑛)
𝑁𝑗
𝑛=1
]
𝐽
𝑗=1
 (3.4) 
Với W là băng thông của hệ thống. 
Có thể thấy trong công thức (3.4) rằng, việc xác định giá trị của chỉ số điều khiển 
𝑣𝑗
𝑘,𝑚
 sẽ cho phép hoặc là thành phần tổng thứ nhất được chọn (D2DC điểm - đa điểm 
từ CH) hoặc thành phẩn tổng thứ hai được chọn (truyền thông điểm - đa điểm từ MBS) 
cho từng cụm thứ j, nhằm cực đại CRU. 
3.2.2.2. Tỷ số tín hiệu trên nhiễu trắng và can nhiễu (SINR) tại các SU 
Trong bài toán tối ưu DRS-CHS, khi SU thứ k chia sẻ tài nguyên kênh truyền 
xuống, SINR tại SU thứ k phải được đảm bảo để cho QoS cao. Do vậy, ta cần tính toán 
SINR tại SU thứ k dưới ảnh hưởng của nhiễu gây ra bởi D2DC điểm - đa điểm như 
sau: 
𝛾𝑘 =
𝑃0,𝑘𝐺0,𝑘
𝑁0 + 𝑣𝑗
𝑘,𝑚𝑃𝑗
𝑚𝐺𝑗
𝑚,𝑘 (3.5) 
Trong đó, 𝐺0,𝑘 là độ lợi kênh truyền từ MBS đến SU thứ k và 𝐺𝑗
𝑚,𝑘
 là độ lợi kênh 
giữa CH thứ m trong cụm thứ j và SU thứ k. 
3.3. Bài toán và giải pháp tối ưu DRS-CHS 
3.3.1. Bài toán tối ưu DRS-CHS 
Trong bài toán tối ưu DRS-CHS, (3.4) là hàm mục tiêu được cực đại bằng cách 
tìm giá trị tối ưu của chỉ số 𝑣𝑗
𝑘,𝑚
 để điều khiển quá trình chọn lựa SU và CH cũng như 
chọn lựa vị trí lưu trữ là MBS hoặc CH cho truyền thông điểm - đa điểm. Bằng cách 
xem xét thêm 3 ràng buộc đã đề cập trong phần 3.2.1 của chương này, bài toán tối ưu 
DRS-CHS được trình bày như sau: 
47 
max
𝑣𝑗
𝑘,𝑚
𝐶RU (3.6) 
𝑠. 𝑡.
{
 ∑ ∑ 𝑣𝑗
𝑘,𝑚
𝑀𝑗
𝑚=1
𝐾
𝑘=1
≤ 1, 𝑗 = 1, 2,  , 𝐽
∑ ∑ 𝑣𝑗
𝑘,𝑚
𝑀𝑗
𝑚=1
𝐽
𝑗=1
≤ 1, 𝑘 = 1, 2,  , 𝐾 
𝑣𝑗
𝑘,𝑚𝑃𝑗
𝑚𝐺𝑗
𝑚,𝑘 ≤
𝑃0,𝑘𝐺0,𝑘
𝛾0
− 𝑁0, 𝑘 = 1, 2,  , 𝐾,
𝑗 = 1, 2,  , 𝐽,𝑚 = 1, 2,  ,𝑀𝑗 
 (3.7) 
Trong đó, ràng buộc thứ 3 để đảm bảo QoS cho SU thứ k được tính từ (3.5) bằng 
cách đặt 𝛾𝑘 ≥ 𝛾0. 
Bài toán tối ưu DRS-CHS được giải đơn giản và cho kết quả chính xác bằng 
thuật toán tìm kiếm vét cạn [86], [87]. Không gian ma trận để tìm ra 𝑣𝑗
𝑘,𝑚
 tối ưu trong 
(3.6) và (3.7) là 
 𝑉 = {𝑉𝐾×𝑀1
1 , 𝑉𝐾×𝑀1
2 ,  , 𝑉𝐾×𝑀1
2𝐾×𝑀1 ; 𝑉𝐾×𝑀2
1 , 𝑉𝐾×𝑀2
2 ,  , 𝑉𝐾×𝑀2
2𝐾×𝑀2 ;  ; 𝑉𝐾×𝑀𝑗
1 , 𝑉𝐾×𝑀𝑗
2 ,  , 𝑉𝐾×𝑀𝑗
2
𝐾×𝑀𝑗
} 
Trong đó, 𝑉𝐾×𝑀𝑗
𝑣 , 𝑣 = 1, 2,  , 2𝐾×𝑀𝑗 là ma trận nhị phân K hàng Mj cột. Phần tử ở 
hàng thứ k và cột thứ m bằng 1 (hoặc 0) nghĩa là SU thứ k chia sẻ (hoặc không chia sẻ) 
tài nguyên kênh truyền xuống của nó cho CH thứ m trong cụm thứ j. Tuy nhiên, vấn đề 
của thuật toán tìm kiếm vét cạn trong không gian ma trận này là khó khả thi khi J, K 
và Mj lớn trong các 5G UDN, tức là, độ phức tạp của bộ nhớ và thời gian tính toán lên 
đến 𝑂(2𝐾×
∑ 𝑀𝑗
𝐽
𝑗=1 ). Trong thực tế, một kết quả tối ưu chính xác hoặc gần đúng với độ 
phức tạp thấp hơn sẽ khả thi hơn so với kết quả chính xác được thực hiện ở độ phức 
tạp cao. Do đó, tôi áp dụng thuật toán di truyền (GA – Genetic Algorithms) để giải bài 
toán tối ưu DRS-CHS cho các giá trị tối ưu chính xác hoặc gần đúng của chỉ số điều 
khiển 𝑣𝑗
𝑘,𝑚
 với tài nguyên bộ nhớ và thời gian xử lý hợp lý. 
So sánh về độ phức tạp bộ nhớ và thời gian, thuật toán tìm kiếm vét cạn tăng theo 
cấp lũy thừa đối với J, K và Mj, thì GA luôn duy trì độ phức tạp bộ nhớ là 𝑂(𝑁𝑃 ×
𝑁𝐵), ở đây NP là kích thước quần thể ban đầu, tức là số lượng cá thể (hoặc các giải 
pháp tiềm năng) và 𝑁𝐵 = 𝐾 × ∑ 𝑀𝑗
𝐽
𝑗=1 là số bit được sử dụng để đại diện cho một cá 
thể. Độ phức tạp về thời gian của GA phụ thuộc cơ bản vào các giá trị của NP và NB, 
48 
các toán tử của GA (chọn lọc, lai tạo và đột biến), và phụ thuộc vào quá trình đánh giá 
hàm mục tiêu chủ yếu dựa trên các tiêu chí hội tụ được đưa ra bởi người dùng [66], 
[80]. Giải pháp GA, dựa trên các nguyên tắc tiến hóa của chọn lọc tự nhiên và biến đổi 
di truyền, được trình bày cụ thể trong phần tiếp theo. 
3.3.2. Giải pháp tối ưu DRS-CHS dùng GA 
Trong phần này, tôi sử dụng công cụ GA được đưa ra trong [80]. Công cụ GA 
này được triển khai để giải bài toán cho các giá trị tối ưu trong miền số thực dưới các 
ràng buộc đơn giản ở dạng giới hạn cận dưới và giới hạn cận trên. Do đó, nó không thể 
giải bài toán tìm ma trận nhị phân tối ưu trong không gian tìm kiếm V và thỏa mãn tập 
các ràng buộc phức tạp như trong (3.7). Vì vậy, tôi áp dụng phương pháp phạt (penalty 
method) [42] và thay đổi tìm kiếm trong miền số thực thành tìm kiếm ở dạng nhị phân, 
được trình bày như sau. 
Khi xem xét các ràng buộc phức tạp, phương pháp phạt được sử dụng để chuyển 
đổi bài toán tối ưu DRS-CHS có ràng buộc thành bài toán tối ưu không ràng buộc. Để 
làm như vậy, các ràng buộc của (3.7) được viết lại như sau 
{
 ∆𝑉𝑗 = 1 −∑ ∑ 𝑣𝑗
𝑘,𝑚
𝑀𝑗
𝑚=1
𝐾
𝑘=1
≥ 0, 𝑗 = 1, 2,  , 𝐽
 ∆𝑉𝑘 = 1 −∑ ∑ 𝑣𝑗
𝑘,𝑚
𝑀𝑗
𝑚=1
𝐽
𝑗=1
≥ 0, 𝑘 = 1, 2,  , 𝐾 
 ∆𝛾𝑘 =
𝑃0,𝑘𝐺0,𝑘
𝛾0
− 𝑁0 − 𝑣𝑗
𝑘,𝑚𝑃𝑗
𝑚𝐺𝑗
𝑚,𝑘 ≥ 0, 𝑘 = 1, 2,  , 𝐾,
𝑗 = 1, 2,  , 𝐽,𝑚 = 1, 2,  ,𝑀𝑗 
 (3.8) 
Ta có hàm phạt được thể hiện là 
𝑃 = 𝜆1∑(min{0, Δ𝑉𝑗})
2
+
𝐽
𝑗=1
𝜆2∑(min{0, Δ𝑉𝑘})
2 +
𝐾
𝑘=1
𝜆3∑∑∑(min{0, ∆𝛾
𝑘})2
𝑀𝑗
𝑚=1
𝐾
𝑘=1
𝐽
𝑗=1
 (3.9) 
Trong đó 1, 2, 3, là các tham số phản ánh mức độ vi phạm của các ràng buộc 
Vì vậy, thay vì giải (3.6) và (3.7), GA có thể được áp dụng để giải bài toán tối ưu 
DRS-CHS không ràng buộc bằng phương pháp phạt như sau 
max
𝑣𝑗
𝑘,𝑚
𝐶 = 𝐶RU − 𝑃 (3.10) 
49 
Lưu đồ của giải thuật GA gồm 5 bước được đưa ra như trong Hình 2.1 [80], [88]. 
Cụ thể, trong bước 1, NP cá thể ban đầu được tạo ngẫu nhiên. Một cá thể, đại diện là 
biến chỉ số điều khiển 𝑣𝑗
𝑘,𝑚
, được đặc trưng bởi nhiễm sắc thể gồm một chuỗi bit. Bởi 
vì hệ thống có J cụm và trong mỗi cụm có ma trận 𝑉𝐾×𝑀𝑗
𝑣 , 𝑣 = 1, 2,  . , 2𝐾×𝑀𝑗, mỗi cá 
thể đại diện cho các biến J được đặc trưng bởi một chuỗi có độ dài 𝑁𝐵 = 𝐾 × ∑ 𝑀𝑗
𝐽
𝑗=1 
bit. Điều đó có nghĩa là chúng ta hợp nhất J biến thành một biến có độ dài bit NB, khi 
đó, số lượng biến của GA là NV = 1. Để thuận tiện cho việc tìm kiếm nhị phân, chúng 
ta không cần phải chuyển đổi chuỗi bit thành giá trị thực trong các toán tử của GA và 
số của bit NB ở đây cũng là độ chính xác của biến. Trong bước này, các tham số ban 
đầu khác được kích khởi bao gồm: khoảng cách các thế hệ (PG), xác suất lai tạo (PC) 
và xác suất đột biến (PM). Sau thế hệ ban đầu, các giá trị mục tiêu C (3.10) được tính 
tương ứng với NP chuỗi được chọn ngẫu nhiên từ 2𝑁𝐵 cá thể. 
Trong bước 2, tất cả các chuỗi nhị phân và giá trị mục tiêu tương ứng được đưa 
vào nhóm giao phối để xếp hạng theo toán tử lấy mẫu toàn thể ngẫu nhiên (stochastic 
universal sampling operator) [89], gọi là tái tạo. Sau đó, với mỗi biến, NPPG chuỗi nào 
có giá trị hàm mục tiêu cao được chọn từ NP chuỗi sẽ được đưa vào nhóm giao phối 
được xếp hạng để nhân giống. 
Tiếp theo, trong bước 3, hai chuỗi bố mẹ trong nhóm giao phối xếp hạng được 
chọn ngẫu nhiên để tạo ra hai con thừa hưởng các đặc điểm di truyền của bố mẹ. Một 
toán tử lai đơn điểm (singl