Tóm tắt Luận án Nghiên cứu thuật toán nâng cao độ chính xác định vị mục tiêu trong rađa thụ động sử dụng nguyên lý TDOA

huật toán di truyền. 
2.1 Thuật toán di truyền định vị mục tiêu trong hệ thống TDOA 
2.1.1 Tính ưu việt của thuật toán di truyền cải tiến đề xuất áp dụng 
trong các hệ thống ra đa thụ động theo nguyên lý TDOA 
GA là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp thích 
hợp cho các bài toán tối ưu tổ hợp, vận dụng các nguyên lý của tiến hóa như 
di truyền, đột biến, chọn lọc tự nhiên và lai ghép. GA được sử dụng rộng rãi 
trong việc xác định các lời giải tối ưu của các bài toán khác nhau. NCS đã kế 
thừa những ưu điểm của GA và các công trình đi trước [31], [50] để đề xuất 
giải hệ phương trình phi tuyến hyperbol cho bài toán định vị TDOA (thuật 
toán 2). 
2.1.2 Mô tả bài toán định vị TDOA cho thuật toán di truyền 
Tình huống được mô tả trong hình 1.1. Ký hiệu các giá trị khi không có 
nhiễu là mũ không, thì TDOA ri,0 khi có nhiễu sẽ là (i=0 là trạm tham chiếu): 
𝑟𝑖,0 = 𝑟𝑖,0
0 + 𝑐𝑛𝑖,0 = 𝑟𝑖
0 − 𝑟0
0 + 𝑐𝑛𝑖 − 𝑐𝑛0,
𝑣ớ𝑖 𝑖 = 1. . 𝑁 − 1 
(2.1) (2.2) 
với 𝑛𝑖,0 = 𝑛𝑖 − 𝑛0 là thành phần nhiễu (sai số ước lượng giữ chậm), c là 
vận tốc sóng điện từ, 𝑐𝑛𝑖 với 𝑖 = 0. . 𝑁 − 1 được xem là nhiễu Gauss trắng 
trung bình không, độc lập có phương sai là 𝜎2 thì ma trận hiệp phương sai 
của 𝑐𝑛 sẽ là [31], [49]. 
𝑅 = [
2𝜎2 𝜎2  𝜎2
𝜎2 2𝜎2  𝜎2
⋮ ⋮ ⋱ 𝜎2
𝜎2 𝜎2  2𝜎2
] = 𝜎2 [
2 1  1
1 2  1
⋮ ⋮ ⋱ 1
1 1  2
] ≜ 𝜎2Ω (2.3) 
Từ công thức (1.2) với 𝑟𝑖 là khoảng cách giữa mục tiêu và N trạm thu và 
từ (2.1) (2.2) , (𝑥𝑡 , 𝑦𝑡 , 𝑧𝑡) là tọa độ của mục tiêu, và (𝑥𝑖, 𝑦𝑖 , 𝑧𝑖) là tọa độ của 
các trạm thu ta có: 
𝑟𝑖,0 = 𝑟𝑖 − 𝑟0 = √(𝑥𝑡 − 𝑥𝑖)2 + (𝑦𝑡 − 𝑦𝑖)2 + (𝑧𝑡 − 𝑧𝑖)2
−√𝑥𝑡
2 + 𝑦𝑡
2 + 𝑧𝑡
2 + 𝑐𝑛𝑖,0, 𝑖 = 1. . 𝑁 − 1 
(2.4) 
Đặt 𝛥𝑟 là vec-tơ ước lượng TDOA, ta có: 
8 
𝛥𝑟 = [𝑟1,0, 𝑟2,0, . . , 𝑟𝑁−1,0](𝑁−1)𝑥1
𝑇
𝑟0 = [𝑟1
0, 𝑟2
0,  , 𝑟𝑁−1
0 ](𝑁−1)𝑥1
𝑇 
𝑟1
0 = [𝑟1
0, 𝑟1
0,  , 𝑟1
0](𝑁−1)𝑥1
𝑇 
Xác định vec-tơ nhiễu là 𝑛 = [𝑛1,0, 𝑛2,0, . . , 𝑛𝑁−1,0](𝑁−1)𝑥1
𝑇
vậy 𝛥𝑟 có thể viết lại: 
𝛥𝑟 = 𝑟0 − 𝑟1
0 + 𝑐𝑛
= [
√(𝑥1 − 𝑥𝑡)2 + (𝑦1 − 𝑦𝑡)2 + (𝑧1 − 𝑧𝑡)2
⋮
√(𝑥𝑁−1 − 𝑥𝑡)2 + (𝑦𝑁−1 − 𝑦𝑡)2 + (𝑧𝑁−1 − 𝑧𝑡)2
]
(𝑁−1)𝑥1
− [
√(𝑥0 − 𝑥𝑡)2 + (𝑦0 − 𝑦𝑡)2 + (𝑧0 − 𝑧𝑡)2
⋮
√(𝑥0 − 𝑥𝑡)2 + (𝑦0 − 𝑦𝑡)2 + (𝑧0 − 𝑧𝑡)2
]
(𝑁−1)𝑥1
+ 𝑐�⃗� 
(2.5) 
Xét trường hợp khi số trạm N≥3, theo xác suất thống kê, để có thông tin 
đầy đủ về mục tiêu ta xét ước lượng hợp lý tối đa của tọa độ mục tiêu 
(𝑥𝑡 , 𝑦𝑡 , 𝑧𝑡), vì các phép đo độc lập nhau nên hàm thích nghi 𝛥𝑟 phụ thuộc vào 
vec-tơ tham số 𝜃 = [𝑥𝑡 , 𝑦𝑡 , 𝑧𝑡]
𝑇là [29]: 
𝑝(𝑟1,0, 𝑟2,0, . . , 𝑟𝑁−1,0|𝜃) 
= {(2𝜋)
𝑁−1
2 |𝑅|
1
2}
−1
𝑒𝑥𝑝 {−
1
2
(𝛥𝑟 − 𝛥𝜇)𝑇𝑅−1(𝛥𝑟 − 𝛥𝜇)}, 
𝑣ớ𝑖 𝛥𝜇 ≜ [𝑟1,0
0 , 𝑟2,0
0 ,  , 𝑟𝑁−1,0
0 ]
𝑇
(2.6) 
2.1.3 Cải tiến thuật toán di truyền áp dụng cho thuật toán định vị 
hyperbol TDOA 
Theo (2.6) ước lượng hợp lý cực đại của tọa độ mục tiêu sẽ là: 
𝜃 = [𝑥𝑡, 𝑦𝑡 , 𝑧𝑡]
𝑇 
𝜃 = 𝑎𝑟𝑔 {𝑚𝑎𝑥 [𝑒𝑥𝑝 (−
1
2
(𝛥𝑟 − 𝛥𝜇)𝑇𝑅−1(𝛥𝑟 − 𝛥𝜇))]} 
(2.7) 
Từ (2.7) bỏ qua hệ số 𝜎2 trong 𝑅−1 ta nhận được tọa độ mục tiêu qua 
hàm ước lượng hợp lý cực tiểu [29]: 
[𝑥𝑡 , 𝑦𝑡 , 𝑧𝑡]
𝑇 = 𝑎𝑟𝑔 {𝑚𝑖𝑛 [−
1
2
(𝛥𝑟 − 𝛥𝜇)𝑇Ω−1(𝛥𝑟 − 𝛥𝜇)]} 
(2.8) 
Giải hệ phương trình phi tuyến (2.8) khó khả thi nên trong phần nghiên 
cứu này, NCS đề xuất cải tiến thuật toán di truyền để tìm tọa độ mục tiêu. 
Lưu đồ thuật toán như sau: 
9 
Tính độ thích nghi cho mỗi vec-tơ nhiễm sắc thể; 
Chọn số ngẫu nhiên xác định đột biến (Ran);
Lai ghép các nhiễm sắc thể cùng thế hệ theo xác suất pc
i = 0;
Khởi tạo bộ giá trị nhiễm sắc thể; 
flag = 0;
i < 0
Đúng
i < t0Ran < pm
Sai
Kết thúc
Đúng Sai
Tìm đột biến dựa 
trên kích thước ô tìm 
kiếm mới
Flag = 0
Đúng
Thiết lập phạm vi 
ô tìm kiếm mới;
Flag =1;
Đúng
Tìm đột biến dựa 
trên kích thước ô tìm 
kiếm hiện tại
Lưu lại vec-tơ nhiễm sắc thể phù hợp tốt 
nhất trong vòng lặp này；
i = i +1;
[xtt2, ytt2, ztt2]
T là vec-tơ nhiễm sắc 
thể kết quả cuối cùng;
Bắt đầu
Sai
Sai
Hình 2-3. Lưu đồ thuật toán di truyền cải tiến giải hệ phương trình phi 
tuyến hyperbol định vị cho hệ thống ra đa thụ động TDOA 
1. Tính toán độ thích nghi tương đối của các cá thể theo (2.12); 2. Lựa 
chọn thế hệ tiếp theo dựa trên xác suất thích nghi trên quần thể theo 
(2.13). 
Các bước lai ghép cá thể: Giả sử hai cá thể cha mẹ là 𝑔1
𝑗
 và 𝑔2
𝑗 thì lai 
ghép giữa hai các thể tạo ra các cá thể mới lần lượt là 𝑔1
𝑗′
và 𝑔2
𝑗′
 theo (2.13): 
𝑔1
𝑗′ = 𝜆𝑔1
𝑗 + (1 − 𝜆)𝑔2
𝑗
; 𝑔2
𝑗′ = 𝜆𝑔2
𝑗 + (1 − 𝜆)𝑔1
𝑗
 (2.13) 
với λ là một số ngẫu nhiên trong khoảng [0, 1]. 
10 
Đột biến cá thể: Sử dụng toán tử đột biến không đồng nhất, giả sử 𝑔𝑗+1 
là cá thể đột biến từ cá thể 𝑔𝑗, theo [42], [51] để cải thiện độ chính xác, bộ 
kiểm soát đột biến được xác định theo (2.14): 
𝑔𝑗+1 =
{
 𝑔𝑗 +𝑀𝐾𝑥𝐾(𝑈𝐵 − g
𝑗) (1 −
𝑗
Σ0
)
𝑏
, 𝑠ố 𝑛𝑔ẫ𝑢 𝑛ℎ𝑖ê𝑛 0
𝑔𝑗 −𝑀𝐾𝑥𝐾(g
𝑗 − 𝐿𝐵) (1 −
𝑗
0
)
𝑏
, 𝑠ố 𝑛𝑔ẫ𝑢 𝑛ℎ𝑖ê𝑛 1
 (2.14) 
Ban đầu, thuật toán di truyền sẽ tìm trong toàn bộ không gian tìm kiếm, 
khi số vòng lặp tăng lên, xác suất của các con được sinh mới xung quanh cha 
mẹ chúng sẽ tăng lên. Bằng cách này, việc tìm kiếm trong không gian cục bộ 
được tăng cường sẽ giúp tăng độ chính xác. 
Trong bài toán định vị hyperbol cho hệ thống TDOA có N trạm, giả sử 
tổng số cá thể là  , bộ giá trị nhiễm sắc thể tại vòng lặp thứ j là 
[𝑔1
𝑗, 𝑔2
𝑗,  , 𝑔
𝑗
], khi 𝑗 > 𝑗0 xác định ô tìm kiếm theo (2.15): 
𝑥𝑈𝐵′ = max[𝑔𝑖
𝑗(1,1)] + 𝛼;𝑦𝑈𝐵′ = max[𝑔𝑖
𝑗(2,1)] + 𝛼 
𝑧𝑈𝐵′ = max[𝑔𝑖
𝑗(3,1)] + 𝛼;𝑥𝐿𝐵′ = min[𝑔𝑖
𝑗(1,1)] − 𝛼 
𝑦𝐿𝐵′ = min[𝑔𝑖
𝑗(2,1)] − 𝛼;𝑧𝐿𝐵′ = min[𝑔𝑖
𝑗(3,1)] − 𝛼 
, 𝑣ớ𝑖 𝑖 = 1,2, . . . , 
(2.15) 
Với tham số 𝛼 > 0 được quyết định bởi bán kính vùng phát hiện của 
trạm thu. Với cận trên [𝑥𝑈𝐵′, 𝑦𝑈𝐵′, 𝑧𝑈𝐵′] và [𝑥𝐿𝐵′, 𝑦𝐿𝐵′, 𝑧𝐿𝐵′] hình thành một 
khối hình hộp chữ nhật mà mục tiêu sẽ nằm trong đó. Hình 2.2 mô tả quá 
trình thu hẹp khu vực tìm kiếm. 
Sản sinh thế hệ mới: Sau các quá trình lựa chọn, lai ghép và đột biến các 
cá thể thế hệ cha mẹ sẽ sinh ra thế hệ mới. Đánh giá thế hệ mới: Quay lại 
bước 3 để đánh giá thế hệ mới qua hàm thích nghi cho từng cá thể. Kiểm tra 
điều kiện kết thúc, thuật toán sẽ lặp lại bước 4 đến bước 8 cho đến khi điều 
kiện dừng thỏa mãn. Ngoài điều kiện tối ưu thì số vòng lặp tối đa cũng là điều 
kiện để kết thúc. 
11 
2.1.4 So sánh thuật toán 2 với các thuật toán 1, LS [28], SI [25] 
Hình 2-4: So sánh kết quả trung 
bình bình phương sai số của thuật 
toán 2 với các thuật toán 1, LS, SI 
Hình 2-7: So sánh tốc độ thực hiện 
của các thuật toán với mức sai số 
thời gian giữ chậm lớn 50ns 
Kết quả trên Hình 2-4 cho thấy sai số của thuật toán LS, SI lớn hơn so 
với thuật toán 1 và 2 khi nhiễu tăng lên. 
Hình 2-5, 2-6, 2-7 cho thấy tốc độ thực hiện của thuật toán 2 khi chưa cải 
tiến có tốc độ thực hiện chậm hơn khi đã cải tiến và chậm hơn nhiều so với 
thuật toán kết hợp dưới tác động của các mức sai số khác nhau. 
2.2 Kết hợp thuật toán định vị trực tiếp (thuật toán 1) với thuật 
toán di truyền cải tiến TDOA (thuật toán 2) 
2.2.1 Đặt vấn đề 
Khi áp dụng GA cho thuật toán định vị TDOA sẽ hội tụ và cho nghiệm 
tối ưu, mặc dù hiệu suất tìm kiếm tốt, cải thiện độ chính xác định vị, nhưng 
quá trình tìm kiếm và thời gian tính toán khá dài nên có thể sử dụng các thuật 
toán tính toán trực tiếp cho nghiệm nhanh, như thuật toán định vị trực tiếp 
(thuật toán 1) để tăng hiệu quả thu hẹp ô tìm kiếm lời giải tối ưu, đẩy nhanh 
tốc độ thực hiện của thuật toán di truyền và cho kết quả ước lượng cuối cùng 
chính xác hơn. 
2.2.2 Cơ sở kết hợp hai thuật toán 
Giả sử thuật toán 1 xác định được ước lượng tọa độ mục tiêu là 
(𝑥𝑏 , 𝑦𝑏 , 𝑧𝑏)và sai số cự ly là E, thì khoảng tìm kiếm sẽ là [𝑥𝑏 − 𝐸, 𝑥𝑏 + 𝐸], 
[𝑦𝑏 − 𝐸, 𝑦𝑏 + 𝐸], [𝑧𝑏 − 𝐸, 𝑧𝑏 + 𝐸]. Do đó tọa độ mục tiêu sẽ nằm trong 
khoảng (2.17): 
12 
𝑥𝑏 − 𝐸 ≤ 𝑥 ≤ 𝑥𝑏 + 𝐸;𝑦𝑏 − 𝐸 ≤ 𝑦 ≤ 𝑦𝑏 + 𝐸; 
2.9) 𝑧𝑏 − 𝐸 ≤ 𝑧 ≤ 𝑧𝑏 + 𝐸(2.10) 
(2.17) 
Dựa trên nhiễm sắc thể này mã hóa các lựa chọn còn lại, lai ghép và quá 
trình đột biến để cải tiến thuật toán di truyền nhằm đạt được hiệu quả tốt hơn. 
2.2.3 Ước lượng kết hợp tuyến tính của thuật toán 1 và thuật toán 2 
Gọi 𝑅1 = [
𝑥𝑡𝑡1
𝑦𝑡𝑡1
] và 𝑅2 = [
𝑥𝑡𝑡2
𝑦𝑡𝑡2
] là hai ước lượng kết quả của thuật toán 
1 và thuật toán 2 tương ứng trong không gian hai chiều. Ước lượng mới 𝑅𝑡 =
[
𝑥𝑡
𝑦𝑡
] nhận được là một ước lượng kết hợp tuyến tính của hai ước lượng trên 
với một độ bù sai lệch 𝛿𝑖 , 𝑖 = 1,2 như sau [20]: 
𝑅𝑡 = 𝛿1𝑅1 + 𝛿2𝑅2 (2.18) 
Theo thực tế nếu hai giá trị ước lượng là không sai lệch và có tính chất 
tuyến tính mong muốn, ta có: 
𝐸[𝑅𝑡] = 𝛿1𝐸[𝑅1] + 𝛿2𝐸[𝑅2] (2.19) 
Do đó 1 = 𝛿1 + 𝛿2 hay 𝛿1 = 1 − 𝛿2. 
Xác định phương sai ma trận hiệp biến từ phương trình (2.19), ta có: 
𝑣𝑎𝑟[𝑅𝑡] = 𝐸[(𝑅𝑡 − 𝐸[𝑅𝑡])
2]
= 𝐸[(𝛿1𝑅1 + 𝛿2𝑅2 − 𝐸[𝛿1𝑅1 + 𝛿2𝑅2])
2] 
= 𝐸 [((𝛿1𝑅1 − 𝛿1𝐸[𝑅1]) + (𝛿2𝑅2 − 𝛿2𝐸[𝑅2]))
2
] 
= 𝛿1
2𝐸[(𝑅1 − 𝐸[𝑅1])
2] + 𝛿2
2𝐸[(𝑅2 − 𝐸[𝑅2])
2] 
(2.20) 
Phương trình (2.20) có thể viết lại như sau: 
𝑣𝑎𝑟[𝑅𝑡] = 𝛿1
2|𝑣𝑎𝑟[𝑅1]| + (1 − 𝛿1)
2|𝑣𝑎𝑟[𝑅2]| (2.21) 
Để tối thiểu phương sai ma trận hiệp biến 𝑣𝑎𝑟[𝑅𝑡] thì cần thiết lập biểu 
thức dẫn xuất |𝑣𝑎𝑟[𝑅𝑡]| với mong muốn 𝛿1 → 0, lúc này ta có: 
𝛿1 = 
𝜎𝑡𝑡2𝑥
2 + 𝜎𝑡𝑡2𝑦
2
𝜎𝑡𝑡2𝑥
2 + 𝜎𝑡𝑡2𝑦
2 + 𝜎𝑡𝑡1𝑥
2 + 𝜎𝑡𝑡1𝑦
2 (2.22) 
Đối với không gian 3 chiều: 
𝛿1 = 
𝜎𝑡𝑡2𝑥
2 + 𝜎𝑡𝑡2𝑦
2 + 𝜎𝑡𝑡2𝑧
2
𝜎𝑡𝑡2𝑥
2 + 𝜎𝑡𝑡2𝑦
2 + 𝜎𝑡𝑡2𝑧
2 + 𝜎𝑡𝑡1𝑥
2 + 𝜎𝑡𝑡1𝑦
2 + 𝜎𝑡𝑡1𝑧
2 (2.23) 
Do đó, ước lượng kết hợp cuối cùng ta sẽ có: 
𝑅𝑡 = 𝛿1 [
𝑥𝑡𝑡1
𝑦𝑡𝑡1
] + (1 − 𝛿1) [
𝑥𝑡𝑡2
𝑦𝑡𝑡2
], hay 
𝑅𝑡 = 𝛿1[𝑥𝑡𝑡1, 𝑦𝑡𝑡1,]
𝑇 + (1 − 𝛿1)[𝑥𝑡𝑡2, 𝑦𝑡𝑡2]
𝑇 
(2.24) 
13 
Biến đổi tương tự như trên để xác định ước lượng kết hợp cho hệ thống 
TDOA trong không gian 3 chiều: 
𝑅𝑡 = 𝛿1 [
𝑥𝑡𝑡1
𝑦𝑡𝑡1
𝑧𝑡𝑡1
] + (1 − 𝛿1) [
𝑥𝑡𝑡2
𝑦𝑡𝑡2
𝑧𝑡𝑡2
], hay 
𝑅𝑡 = 𝛿1[𝑥𝑡𝑡1, 𝑦𝑡𝑡1, 𝑧𝑡𝑡1]
𝑇
+ (1 − 𝛿1)[𝑥𝑡𝑡2, 𝑦𝑡𝑡2, 𝑧𝑡𝑡2]
𝑇 
(2.25) 
Với [
𝑥𝑡𝑡1
𝑦𝑡𝑡1
𝑧𝑡𝑡3
] , [
𝑥𝑡𝑡2
𝑦𝑡𝑡2
𝑧𝑡𝑡2
] là nghiệm của thuật toán 1 và thuật toán 2 tương ứng. 
2.2.4 Kết hợp ước lượng nghiệm hệ phương trình phi tuyến hyperbol 
của thuật toán 1 và thuật toán 2 
Thuật toán 2 cần một giá trị khởi tạo gần đúng với vị trí thực của mục 
tiêu để đảm bảo thuật toán hội tụ nhanh, luận án đã đề xuất sử dụng ước lượng 
kết quả của thuật toán 1 để tính toán giá trị vị trí khởi tạo cho thuật toán 2 
thay cho giá trị khởi tạo ngẫu nhiên. Phương pháp kết hợp hai thuật toán chi 
tiết như sau: 
- Khởi tạo thuật toán 2 bằng giá trị tọa độ mục tiêu (x, y, z) bằng nghiệm 
của thuật toán 1 là (xtt1, ytt1, ztt1). 
- Sử dụng bộ kiểm soát đột biến (2.14) và với bộ giá trị nhiễm sắc thể tại 
vòng lặp thứ i [𝑔1
𝑖 , 𝑔2
𝑖 ,  , 𝑔Σ
𝑖 ] để tính toán thiết lập giới hạn ô tìm kiếm mới 
theo (2.15) và tìm nghiệm là vị trí mục tiêu cho thuật toán 2. 
- Sau đó ta có nghiệm của 
thuật toán 2 là [xtt2, ytt2, ztt2]T. 
- Xác định ước lượng 𝑅𝑡 kết 
hợp cuối cùng theo (2.25). 
2.2.5 So sánh thuật toán 
kết hợp 1-2 với thuật toán 1, thuật 
toán 2 
Kết quả trên Hình 2-10 cho thấy 
ước lượng của thuật toán kết hợp 
luôn có độ chính xác vị trí RMSE 
tốt hơn ước lượng của từng thuật 
toán và tăng tỉ lệ thuận với số trạm 
thu. 
Hình 2-10: Kết quả trung bình bình 
phương sai số của thuật toán 1-2 
14 
Trên đồ thị cũng thấy rằng tỷ lệ giữa RMSE với độ lệch chuẩn nhiễu Gauss 
(σ) cũng cho thấy khả năng chịu tác động của nhiễu tốt hay không của từng 
thuật toán. Hình 2-9 trình bày lưu đồ thuật toán kết hợp: 
Tính độ thích nghi cho mỗi vec-tơ nhiễm sắc thể; 
Chọn số ngẫu nhiên xác định đột biến (Ran);
Lai ghép các nhiễm sắc thể cùng thế hệ theo xác suất pc
i = 0
Khởi tạo bộ giá trị nhiễm sắc thể bằng nghiệm của thuật toán 1: 
[x, y, z]T = [xtt1, ytt1, ztt1]
T; flag = 0;
i < 0
Đúng
i < t0Ran < pm
Sai
Kết thúc
Đúng
Sai
Tìm đột biến dựa 
trên kích thước ô 
tìm kiếm mới
Flag = 0
Đúng
Thiết lập phạm vi 
tìm kiếm mới;
Flag =1;
Đúng
Tìm đột biến dựa 
trên kích thước ô tìm 
kiếm hiện tại
Lưu lại vec-tơ nhiễm sắc thể phù 
hợp tốt nhất trong vòng lặp này；
i = i +1;
[xtt2, ytt2, ztt2]
T là vec-tơ nhiễm sắc thể kết quả cuối cùng;
Tính toán ước lượng kết hợp
Rt = δ1 [xtt1, ytt1, ztt1]
T + (1-δ1)[xtt2, ytt2, ztt2]
T 
Bắt đầu
Sai
Sai
Hình 2-9. Lưu đồ thuật toán kết hợp thuật toán 1 và thuật toán 2 
15 
2.3 Thuật toán tiến hóa vi phân định vị mục tiêu trong hệ thống ra 
đa thụ động TDOA (thuật toán 3) 
Kế thừa những ưu điểm của thuật toán 2, phần này NCS đề xuất áp dụng 
thuật toán tiến hóa vi phân (DEA, thuật toán 3) để nâng cao khả năng tìm 
kiếm tối ưu và cũng tăng độ chính xác nghiệm, khả năng kết hợp với thuật 
toán 1 cũng sẽ làm tăng tốc độ thực hiện của thuật toán. 
2.3.1 Nguyên lý cơ bản thuật toán tiến hóa vi phân 
2.3.2 Tính ưu việt và sự khác nhau giữa thuật toán tiến hóa vi phân 
với thuật toán tiến hóa thông thường 
2.3.3 Các bước thực hiện của thuật toán tiến hóa vi phân 
Trình tự thuật toán tiến hóa vi phân được thực hiện qua bước [32], [35]. 
2.3.4 Lựa chọn tham số cho thuật toán tiến hóa vi phân 
2.3.5 Thuật toán tiến hóa vi phân định vị trong hệ thống TDOA 
Thuật toán dựa trên mô hình đã thiết lập trong phần thuật toán di truyền. 
Các bước cài đặt thuật toán tiến hóa vi phân như sau trải qua các bước tương 
tự như thuật toán di truyền, tuy nhiên thuật toán tiến hóa vi phân sản sinh thế 
hệ con cháu được kết hợp bởi ba cá thể cha mẹ sau đó mới chọn các tác vụ để 
có được một thế hệ cá thể mới. Các cá thể trong thuật toán tiến hóa vi phân 
được sử dụng để tạo ra một cá thể mới hay không bằng cách so sánh với giá 
trị hàm thích nghi được lựa chọn và đối chiếu với các giá trị ngưỡng để ra 
quyết định. Cuối cùng kiểm tra điều kiện kết thúc, nếu thỏa mãn thì kết thúc 
thuật toán, nếu không thì lặp lại các bước 4-8 cho đến khi một điều kiện chấm 
dứt được đáp ứng. Số lần lặp tối đa là điều kiện kết thúc. 
2.3.6 Kết hợp thuật toán 1 với thuật toán 3 
Tương tự kết hợp thuật toán định vị trực tiếp thuật toán 1 với thuật toán 
di truyền trong không gian 2 chiều và 3 chiều, NCS cũng đề xuất kết hợp thuật 
toán 1 với thuật toán tiến hóa vi phân (thuật toán 3). Giả sử kết quả của thuật 
toán 1 thỏa mãn theo công thức (2.17), sử dụng kết quả này để thu hẹp không 
gian tìm kiếm nhằm làm tăng tốc độ thực hiện của thuật toán tiến hóa vi phân 
và đạt được độ chính xác định vị cao hơn. Phần tính toán ước lượng kết hợp 
hoàn toàn như thuật toán kết hợp với thuật toán di truyền đã mô tả trong mục 
2.2 và hình 2-9. 
2.4 So sánh tốc độ thực hiện của thuật toán 2, thuật toán 3 kết hợp 
với thuật toán 1 định vị trực tiếp trong ra đa thử nghiệm RTh 
Hình 2-11, 2-12, 2-13 cho thấy tốc độ thực hiện nhanh hơn và giá trị sai 
số trung bình MSE nhỏ hơn tương ứng với các của thuật toán kết hợp 1-2, 
thuật toán 3, thuật toán 2 dưới tác động ở các mức nhiễu khác nhau. 
16 
2.5 Thời gian hội tụ của thuật toán GA/DEA 
Thuật toán GA/DEA là thuật toán biến đổi ngẫu nhiên, do vậy để tìm 
được một giải pháp tối ưu sau một số lượng hữu hạn lần lặp luận án cũng đã 
phân tích để xác định khoảng thời gian mà thuật toán GA/DEA hội tụ theo 
xác suất để tìm thấy lời giải tối ưu. 
2.6 Thuật toán bố trí trạm thu tối ưu theo sai số định vị nhỏ nhất 
2.6.1 Đặt vấn đề 
Phân tích các trường hợp có nghiệm và khảo sát sai số định vị cho thấy 
bố trí trạm thu ảnh hưởng đến độ chính xác định vị. Trong triển khai chiến 
đấu và nghiên cứu thiết kế thử nghiệm hệ thống ra đa thụ động TDOA, bố trí 
trạm thu tối ưu luôn là một nhiệm vụ quan trọng. Có một số công trình công 
bố về sự ảnh hưởng của của bố trí hình học trạm thu lên độ chính xác định vị 
trong ra đa thụ động [1], [5], [17], trong [54] đã trình bày thuật toán đưa ra bố 
trí trạm thu tối ưu dựa trên xác suất sai số hình tròn nhỏ nhất. Thuật toán này 
có hiệu suất không cao do đặc điểm vét cạn của nó đồng thời chỉ đưa ra cấu 
hình chung chung không dựa trên các điều kiện cụ thể như cự ly giới hạn giữa 
các trạm, góc hình thành giữa các trạm. Trong phần này NCS sẽ đề xuất giải 
bài toán tối ưu này bằng thuật toán di truyền để áp dụng những ưu điểm và 
thích hợp cho những bài toán tìm nghiệm tối ưu. 
2.6.2 Giải bài toán tối ưu bố trí trạm thu bằng thuật toán di truyền 
Các điều kiện của bài toán: Cho  là một tập hợp các vùng tạo nên bởi 
bố trí N trạm thu {S1, S2, , SN} của hệ thống Ra đa thụ động TDOA và  là 
vùng phân bố mục tiêu trong cùng một hệ tọa độ đề-các. Cả hai vùng có thể 
chồng lên nhau hoặc không giao nhau, hoặc vùng này là tập con của vùng kia. 
Kết quả của thuật toán tối ưu hóa là tìm tọa độ của các trạm Si sao cho sai số 
định vị mục tiêu CEP được phát hiện nằm trong vùng  ở mức nhỏ nhất. 
2.6.3 Hàm mục tiêu và thích nghi 
Một số giả thiết trước khi xây dựng mô hình: 
1. Trạm thu vô hướng trong môi trương đồng nhất và suy hao đường truyền 
tính theo công thức suy hao trong không gian tự do; 2. Các trạm thu có độ 
tăng ích anten như nhau; 3. Phân bố mục tiêu đồng đều trên toàn khu vực. 
Với ba giả thiết ở trên, vùng phát hiện của các trạm sẽ có kích thước 
giống nhau, dạng hình tròn với bán kính r được tính sao cho công suất tín hiệu 
thu ở bước sóng λ tại bất kỳ một điểm nào nằm trong bán kính r cũng lớn hơn 
một ngưỡng 𝜃𝑟 cần thiết, cụ thể theo công thức (2.34). 
Giả sử mục tiêu có thể xuất hiện và được phát hiện bởi hệ thống N trạm 
thu có xác suất sai số vòng tròn CEPi. Thì sai số trung bình cho một bố trí 
17 
trạm thu (2.37) sẽ được sử dụng làm hàm mục tiêu và hàm thích nghi của thuật 
toán (2.38). 
Thuật toán di truyền tối ưu trạm thu: Với hàm mục tiêu (2.37) và thích 
nghi (2.38) tiến hành cài đặt thuật toán 2 áp dụng cho bài toán tối ưu trạm thu 
với các tham số sau: pr, pm: xác suất giao hoán, xác suất đột biến; f1 = f(CEP): 
hàm mục tiêu về sai số; f2(f1): Hàm đánh giá mức độ phù hợp của tổ hợp ai đối 
với hàm mục tiêu f1; Σ: Số lượng tổ hợp vị trí ban đầu; max: Số lần lặp cho trước 
của thật toán ; Φ0, Φc, Φr, Φm: tập hợp dân cư ban đầu, các tập hợp dân cư 
trung gian qua bước lựa chọn, lai ghép, đột biến. Kết quả thuật toán zj là bộ 
cấu hình bố trí N trạm thu có sai số CEPj nhỏ nhất. 
2.7 Điều kiện dừng 
Thuật toán di truyền, thuật toán tiến hóa vi phân là một quá trình ngẫu 
nhiên, nên chúng ta không thể đảm báo chắc chắn thuật toán di truyền sẽ dừng 
sau hữu hạn bước. Vì vậy, để đảm bảo thuật toán di truyền sẽ kết thúc, khi cài 
đặt thuật toán phải định nghĩa điều kiện dừng cho thuật toán. Ví dụ, nó sẽ 
dừng sau một số hữu hạn các thế hệ hoặc tối ưu toàn cục đã đạt được, hoặc 
giá trị trung bình của độ thích nghi trên tất cả các cá thể của quần thể không 
thay đổi. 
2.8 Kết luận chương 
- Thuật toán 2: Thuật toán di truyền cải tiến để giải bài toán định vị mục 
tiêu trong hệ thống ra đa thụ động TDOA đã được cải tiến với phương pháp 
lai ghép mới: Sử dụng kỹ thuật mã hóa số thực các biến liên tục để giải bài 
toán tối ưu; Tác vụ lai ghép sử dụng một toán tử số học từ lý thuyết tập hợp 
để hợp nhất một điểm lai ghép; Các ma trận hai chiều trực giao sử dụng trong 
tác vụ lựa chọn cá thể chọn lai ghép theo hàm mục tiêu. 
- Thuật toán 3: Thuật toán tiến hóa vi phân giải bài toán định vị hyperbol. 
Độ chính xác định vị của thuật toán tiến hóa vi phân cũng được cải thiện hơn 
so với thuật toán di truyền. 
- Kết hợp thuật toán 1 với thuật toán 2 (hoặc thuật toán 1 với thuật toán 3) 
cho thấy tính hiệu quả và khả thi, đó là: 1. Nâng cao độ chính xác: Theo 
nguyên tắc thống kê, càng nhiều lần đo thì kết quả trung bình càng chính xác. 
2. Tăng tốc độ tính toán cho hệ thống: Thuậ