Nghiên cứu sử dụng thuật toán tiến hóa vi phân để tăng tốc độ hội tụ và nâng cao độ chính xác định vị mục tiêu trong hệ thống ra đa thụ động TDOA

Nghiên cứu khoa học công nghệ<br /> <br /> NGHIÊN CỨU SỬ DỤNG THUẬT TOÁN TIẾN HÓA VI PHÂN<br /> ĐỂ TĂNG TỐC ĐỘ HỘI TỤ VÀ NÂNG CAO ĐỘ CHÍNH XÁC ĐỊNH<br /> VỊ MỤC TIÊU TRONG HỆ THỐNG RA ĐA THỤ ĐỘNG TDOA<br /> Phạm Quyết Thắng1*, Trần Văn Hùng2<br /> Tóm tắt: Bài báo đề xuất phương án giải bài toán định vị mục tiêu trong hệ<br /> thống ra đa thụ động TDOA bằng thuật toán tiến hóa vi phân và kết hợp với một<br /> thuật toán định vị trực tiếp. Việc kết hợp bằng cách sử dụng ước lượng vị trí của<br /> một thuật toán định vị trực tiếp làm giá trị khởi tạo cho thuật toán tiến hóa vi phân<br /> đã làm giảm không gian tìm kiếm cũng như tăng tốc độ hội tụ của thuật toán. Đây<br /> là phương pháp giải bài toán cho tốc độ hội tụ nhanh, độ chính xác định vị cao, đặc<br /> biệt khi cường độ nhiễu lớn.<br /> Từ khóa: Rađa thụ động, Sai số định vị, Thuật toán di truyền, Thuật toán tiến hóa vi phân, TDOA.<br /> <br /> I. ĐẶT VẤN ĐỀ<br /> Theo lý thuyết cơ bản của thuật toán tiến hóa vi phân (Differential Evolution<br /> Algorithm, DE hoặc DEA) có thể thích hợp để áp dụng vào định vị mục tiêu trong hệ<br /> thống TDOA cũng như mô phỏng trên máy tính. Qua kết quả mô phỏng và so sánh với các<br /> thuật toán định vị trực tiếp (khảo sát sử dụng thuật toán bình phương tối thiểu LS [3] ,<br /> Least Square) và thuật toán di truyền cải tiến [2] , [10] , [11] (Genetic Algorithm, GA)<br /> cho thấy thuật toán tiến hóa vi phân có thể áp dụng vào hệ thống ra đa thụ động TDOA<br /> thực có hiệu quả.<br /> Thuật toán tiến hóa vi phân và các thuật toán tiến hóa thông thường có những điểm<br /> khác nhau sau [12] , [13] , [15] , [16] :<br /> - Thuật toán tiến hóa vi phân được mã hóa bằng số thực, trong khi thuật toán tiến hóa<br /> thông thường mã hóa bằng chuỗi nhị phân.<br /> - Trong thuật toán tiến hóa thông thường, thường chọn hai cá thể để sản sinh con mới<br /> qua lai ghép, trong khi thuật toán tiến hóa vi phân sản sinh thế hệ con cháu được kết hợp<br /> bởi ba cá thể cha mẹ. Sau đó mới lựa chọn để có được một thế hệ dân số mới.<br /> - 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<br /> 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<br /> giá trị ngưỡng để ra quyết định.<br /> Tính ưu việt của thuật toán tiến hóa vi phân:<br /> So với các thuật toán tiến hóa khác, thuật toán tiến hóa vi phân có chiến lược tìm kiếm<br /> dựa vào cực trị toàn cục, chiến lược tồn tại dựa trên tác vụ biến thể đơn giản và một đối<br /> thủ cạnh tranh để giảm bớt sự phức tạp của các thao tác tái tạo gen. Hơn nữa, thuật toán<br /> tiến hóa vi phân có khả năng nhớ độc đáo để nó có thể tự động theo dõi các điều kiện tìm<br /> kiếm hiện tại, do đó điều chỉnh chiến lược tìm kiếm hợp lý. Các đặc tính ưu việt như sau:<br /> - Thuật toán tổng quát không phụ thuộc vào loại thông tin;<br /> - Phương pháp này dễ thực hiện và cài đặt mô phỏng;<br /> - Các nhóm tìm kiếm, các cá thể có khả năng ghi nhớ các lời giải tối ưu;<br /> - Tìm kiếm hỗ trợ, các cá thể có khả năng sử dụng thông tin cục bộ và các nhóm toàn<br /> cục để định hướng thuật toán tìm kiếm tốt hơn trên phạm vi rộng;<br /> - Dễ dàng để kết hợp với các thuật toán khác để tạo thành thuật toán kết hợp có hiệu<br /> quả tốt hơn.<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 51<br />  Ra đa<br /> <br /> Trong thực tế các bài toán định vị thường được sử dụng là các bài toán định vị trực tiếp<br /> (ĐVTT) [1] , [3] , [6] , [7] bằng cách tính toán dựa trên phương pháp hình học bố trí trạm<br /> thu và thời gian trễ của tín hiệu từ một trạm tham chiếu đến các trạm còn lại trong hệ<br /> thống tạo thành một hệ phương trình phi tuyến hyperbol. Việc giải hệ phương trình này có<br /> nhiều phương pháp khác nhau, các phương pháp số học như biến đổi chuỗi Taylor [5] ,<br /> phương pháp giải tích biến đổi hệ phương trình phi tuyến về một hệ tuyến tính trung gian<br /> như phương pháp Chan/Ho [6] , Fang [7] . Đa số các bài toán này thuộc loại tuyến tính<br /> bình phương nhỏ nhất (LLSA). Nhìn chung các bài toán định vị TDOA là phải tuyến tính<br /> hóa hệ phương trình qua những bước trung gian và quy về một hệ phương trình bậc hai,<br /> việc giải và biện luận các trường hợp phương trình bậc 2 có nghiệm đơn, nghiệm kép, vô<br /> nghiệm, hay 2 nghiệm phân biệt sẽ cho ta hình dung được sự phụ thuộc của bố trí hình học<br /> trạm thu đến việc giải được hệ phương trình phi tuyến và tính khả nghiệm của nó. Trong<br /> những trường hợp đặc biệt, nếu hệ có 2 nghiệm ta có thể sử dụng một số cách để chọn<br /> nghiệm đúng, khi hệ vô nghiệm thì hệ thống không hoàn thành nhiệm vụ, tức không xác<br /> định được vị trí mục tiêu. Để hỗ trợ những trường hợp như thế này, đến nay người ta vẫn<br /> dùng các cách tiếp cận sau:<br /> 1) Tìm kiếm nghiệm tối ưu, trong đó dựa trên phân tích toán học, người ta đưa ra các<br /> quy tắc định hướng tìm kiếm một lời giải đủ tốt [4] [6] .<br /> 2) Sử dụng các kỹ thuật tìm kiếm cục bộ để tìm lời giải tối ưu địa phương [5] .<br /> 3) Tìm lời giải gần đúng nhờ các thuật toán mô phỏng tự nhiên [10] như giải thuật di<br /> truyền (GA) [8] , [9] , tiến hóa (EA) [13] .<br /> Hai cách tiếp cận đầu thường cho lời giải nhanh nhưng không thể cải thiện thêm lời giải<br /> tìm được, nên cách tiếp cận thứ ba đang được sử dụng cho các bài toán có không gian tìm<br /> kiếm lớn. Trong các phương pháp mô phỏng tự nhiên, thuật toán di truyền và tiến hóa là<br /> cách tiếp cận tương đối mới đang được nghiên cứu và ứng dụng cho các bài toán định vị<br /> thiết bị di động [8] , [9] . Thuật toán vi tiến hóa là một bước cải tiến tiếp theo của thuật toán<br /> di truyền nhằm tăng tốc độ hội tụ và cải thiện độ chính xác của lời giải tối ưu toàn cục.<br /> DEA là một thuật toán dựa trên dân số tiến hóa với bộ nhớ các cá thể trong quần thể và khả<br /> năng giải được của đặc tính chia sẻ thông tin, thông qua sự hợp tác và cạnh tranh giữa các cá<br /> thể trong quần thể để đạt được lời giải tối ưu của bài toán. Bản chất của nó được tác giả Paul<br /> đưa ra dựa trên mã hóa một số thực để cải tiến thuật toán di truyền vét cạn rất tốt. Thuật toán di<br /> truyền chuẩn đều có ba tác vụ: lựa chọn, lai ghép và đột biến, thuật toán tiến hóa vi phân khác<br /> hơn một bước là sử dụng tuần tự các biến thể, lai ghép và lựa chọn [12] [13] .<br /> <br /> II. GIẢI BÀI TOÁN ĐỊNH VỊ BẰNG THUẬT TOÁN TIẾN HÓA VI PHÂN CHO<br /> HỆ THỐNG RA ĐA THỤ ĐỘNG TDOA 4 TRẠM THU<br /> A. Mô hình bài toán<br /> 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ũ<br /> không, thì TDOA ri,0 khi có nhiễu sẽ là (i = 0 là trạm tham chiếu):<br /> , = , + , = − + − , ớ = 1. . −1 (1)<br /> với, , = − là thành phần nhiễu (sai số ước lượng giữ chậm), c là vận tốc sóng<br /> điện từ, với = 0. . − 1 là nhiễu Gauss trắng trung bình không, độc lập có phương<br /> sai là thì ma trận hiệp phương sai của sẽ là.<br /> <br /> <br /> 52 P.Q. Thắng, Tr.V. Hùng, “Nghiên cứu sử dụng thuật toán… ra đa thụ động TDOA.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> 2 … 2 1 … 1<br /> 2 … 1 2 … 1<br /> = = ≜ Ω (2)<br /> ⋮ ⋮ ⋱ ⋮ ⋮ ⋱ 1<br /> … 2 1 1 … 2<br /> là khoảng cách giữa mục tiêu và N trạm thu và từ , ( , , ) là tọa độ của mục tiêu, và<br /> ( , , ) là tọa độ của các trạm thu ta có:<br /> <br /> , = − = ( − ) +( − ) +( − ) − + + + , ,<br /> (3)<br /> = 1. . −1<br /> Đặt là vec-tơ ước lượng TDOA, ta có:<br /> = , , , ,..., , ( )<br /> <br /> = [ , ,…, ]( )<br /> <br /> = [ , ,…, ]( )<br /> <br /> Xác định vec-tơ nhiễu là = , , , ,.., , ( )<br /> <br /> Vậy có thể viết lại:<br /> = − +<br /> ( − ) +( − ) + ( − )2<br /> = ⋮<br /> ( − ) +( − ) +( − )2 ( )<br /> (4)<br /> ( − ) +( − ) +( − )2<br /> − ⋮<br /> ( − ) +( − ) +( − )2 ( )<br /> +<br /> 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<br /> 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<br /> nhau nên hàm thích nghi phụ thuộc vào vec-tơ tham số = [ , , ] là:<br /> 1<br /> , , , ,.., , = (2 ) | | − ( − ) ( − ),<br /> 2 (5)<br /> ớ ≜ , , , ,…, ,<br /> <br /> <br /> <br /> Ta xét trường hợp khi N≥3 sử dụng đầy đủ thông tin thống kê ước lượng hợp lý cực đại<br /> của tọa độ mục tiêu ( , , ). Theo (5) ước lượng hợp lý cực đại của tọa độ mục tiêu sẽ là:<br /> 1 (6)<br /> =[ , , ] = − ( − ) ( − )<br /> 2<br /> Từ (6) bỏ qua hệ số ta nhận được tọa độ mục tiêu qua hàm ước lượng hợp lý cực tiểu:<br /> 1 (7)<br /> [ , , ] = − ( − ) Ω ( − )<br /> 2<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 53<br />  Ra đa<br /> <br /> Giải hệ phương trình phi tuyến (7) khó khả thi nên trong phần nghiên cứu này, chúng<br /> tôi đề xuất cải tiến thuật toán di truyền đã nêu [2] để tìm tọa độ mục tiêu. Quá trình tìm<br /> kiếm các lời giải sẽ sinh ra các điểm khác nhau như quá trình tiến hóa để phục vụ việc tìm<br /> kiếm các giải pháp tối ưu trên toàn cục.<br /> B. Thuật toán tiến hóa vi phân giải bài toán định vị TDOA<br /> Trong phần này sẽ trình bày việc áp dụng thuật thuật toán tiến hóa vi phân để giải bài<br /> toán định vị hyperbol cho hệ thống TDOA. Thuật toán dựa trên mô hình đã thiết lập trong<br /> phần thuật toán di truyền [2] . Các bước cài đặt thuật toán tiến hóa vi phân như sau:<br /> Bước 1: Mã hóa nhiễm sắc thể<br /> Mã hóa các nhiễm sắc thể bằng số thực. Trong không gian 2 chiều biểu diễn mỗi cá thể<br /> bằng 2 gen, trong không gian 3 chiều biểu diễn bằng 3 gen. Trước hết, xác định tọa độ của<br /> mục tiêu chuyển động trong bán kính phát hiện của trạm thu đầu tiên nhận được tín hiệu<br /> theo công thức :<br /> x ≤x≤x<br /> y ≤y≤y (8)<br /> z ≤z≤z<br /> Trong đó x , x , y ,y , z ,z là giới hạn tọa độ của một trạm có thể<br /> quan sát được mục tiêu. Sau đó ước lượng hiệu chỉnh theo công thức sau tối ưu tọa độ (x,<br /> y, z) theo (9):<br /> x=x + v(1)[x −x ]<br /> y=y + v(2)[y −y ] (9)<br /> z=z + v(3)[z −z ]<br /> Tọa độ mục tiêu khởi tạo được mã hóa bằng cách ánh xạ vào khoảng số thực [0,1] với<br /> các gen v(i), i=1, 2, 3 tương ứng với các biến x, y, z tạo thành bộ mã nhiễm sắc thể<br /> v = [v(1), v(2), v(3)] .<br /> Bước 2: Thiết lập số lượng dân số ban đầu của quần thể<br /> Theo công thức (8) xác định số chiều tọa độ sẽ sinh ra ma trận 3xΣ chiều số ngẫu nhiên<br /> độc lập , = { , , . . , } sẽ là số lượng cá thể bậc cha mẹ, Σ là tổng cá thể trong quần<br /> thể. Mỗi cá thể = , , , , . . , , là lời giải cần ước lượng, D là số chiều tọa độ,<br /> không gian 2 chiều D=2, không gian 3 chiều D=3. Trong đó , , , , . . , , các thành<br /> phần biểu diễn cho véc-tơ nhiễm sắc thể tương ứng với các chiều tọa độ của mục tiêu<br /> , , .<br /> Bước 3: Tính toán hàm mục tiêu<br /> Hàm mục tiêu được áp dụng theo công thức<br /> 1<br /> f( ) = (10)<br /> ( − ) Ω ( − )|<br /> <br /> Trong đó =[ , , ] trong đó , , là tọa độ mục tiêu tương ứng với nhiễm sắc<br /> thể v khi thay vào công thức (10). Trong đó = = , , , , , .<br /> Bước 4: Biến thể<br /> <br /> <br /> 54 P.Q. Thắng, Tr.V. Hùng, “Nghiên cứu sử dụng thuật toán… ra đa thụ động TDOA.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Đối với mỗi cá thể (ước lượng kết quả tọa độ mục tiêu) chuyển động luôn tồn tại<br /> một biến thể theo (11):<br /> = + . − (11)<br /> <br /> F ∈ [0, 1] là hệ số tỉ lệ độ khác biệt giữa gen bố mẹ và gen khác bố mẹ được chọn theo<br /> [14] .<br /> Bước 5: Lai ghép<br /> Sử dụng công thức (12), để sinh ra cá thể lai ghép và (11) để sinh ra biến thể<br /> từ cá thể<br /> , ế ()≤ ℎ ặ = () (12)<br /> =<br /> , ế ℎá đ ề ệ ê<br /> Bước 6: Lựa chọn<br /> Tính toán lựa chọn giữa các thể và cá thể lai ghép thông qua so sánh hàm mục<br /> tiêu của hai cá thể này. Nếu cá thể nào có chất lượng tốt sẽ được chọn làm các thể<br /> trong tập dân số mới.<br /> <br /> , ế < ( ) (13)<br /> =<br /> , ế ℎá đ ề ệ ê<br /> Bước 7: Sinh thế hệ dân số mới<br /> Sau các quá trình biến thể, lai ghép và lựa chọn từ các các thể thế hệ cha mẹ sẽ tạo ra<br /> thế hệ tiếp theo.<br /> Bước 8: Đánh giá chất lượng dân số mới<br /> Trong Bước 3, tính toán các giá trị hàm thích nghi của mỗi nhiễm sắc thể trong quần thể<br /> mới, nếu các giá trị hàm thích nghi của các cá thể trong tập dân số mới cao hơn thì được<br /> chọn, nếu không thì chọn cá thể trong tập dân số thế hệ trước. Kiểm tra điều kiện kết thúc,<br /> 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<br /> kiện chấm dứt được đáp ứng, ở dây sử dụng số lần lặp tối đa làm điều kiện kết thúc.<br /> C. Kết hợp thuật toán định vị trực tiếp với thuật toán tiến hóa vi phân<br /> Đối với thuật toán tiến hóa vi phân, giá trị khởi tạo ngẫu nhiên theo (8) sẽ tạo ra không<br /> gian tìm kiếm rất lớn, dẫn đến kéo dài thời gian hội tụ và có thể có nghiệm cục bộ và làm<br /> giảm độ chính xác, do đó phải tìm cách thu hẹp không gian tìm kiếm.<br /> Giả sử ta sử dụng một thuật toán định vị trực tiếp như [1] , [3] , [6] [7] (trong thử<br /> nghệm sử dụng thuật toán LS [3] ) để xác định được ước lượng tọa độ mục tiêu là<br /> ( , , )và sai số cự ly là E, thì tọa độ chính xác của mục tiêu sẽ nằm trong khoảng<br /> không gian [ − , + ], [ − , + ], [ − , + ], tức là:<br /> − ≤ ≤ +<br /> − ≤ ≤ + (14)<br /> − ≤ ≤ +<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 55<br />  Ra đa<br /> <br /> Ta đã thu hẹp được không gian tìm kiếm và các tác giả đề xuất kết hợp một thuật toán<br /> định vị trực tiếp (thuật toán LS) với thuật toán tiến hóa vi phân. Giả sử kết quả của thuật<br /> toán LS thỏa mãn theo công thức (14), ta sử dụng kết quả này để thu hẹp không gian tìm<br /> kiếm ban đầu nhằm làm tăng tốc độ hội tụ của thuật toán tiến hóa vi phân và đạt được độ<br /> chính xác định vị cao hơn.<br /> D. Lựa chọn tham số cho thuật toán tiến hóa vi phân<br /> Ba tham số chính ảnh hưởng trực tiếp đến hiệu quả của thuật toán tiến hóa vi phân [13] :<br /> Số lượng cá thể trong quần thể ∑, hệ số tỷ lệ F, xác suất lai ghép pc. Quá trình thử nghiệm<br /> cho thấy, khi tiến hóa đến thế hệ tối đa nhất định, quy mô dân số nên vừa phải, để duy trì<br /> tỷ lệ đa dạng ở một mức cân bằng và tốc độ hội tụ nhanh, nếu quy mô dân số lớn, sẽ phải<br /> trả các chi phí cho các thế hệ tiến hóa lớn. Hệ số tỉ lệ F đóng vai trò điều tiết thuật toán<br /> trong quá trình tìm kiếm tối ưu cục bộ và toàn cục. Hệ số tỉ lệ lớn sẽ có lợi cho việc duy trì<br /> sự đa dạng về dân số và khả năng tìm kiếm toàn cục, ngược lại sẽ có lợi trong lợi trong tìm<br /> tìm kiếm cục bộ và tăng tốc độ hội tụ. Do đó, các giá trị của hệ số tỉ lệ phải không quá lớn<br /> và không được nhỏ hơn một giá trị nhất định, giá trị tỉ lệ trong khoảng [0.5, 1] thì thuật<br /> toán đạt được kết quả tốt hơn. Khi xác suất lai ghép pc nhỏ, dẫn đến tốc độ hội tụ chậm,<br /> nhưng tỷ lệ thành công cao, thuật toán ổn định hơn, ngược lại pc lớn thì đẩy nhanh tốc độ<br /> hội tụ, nhưng dễ dàng rơi vào tối ưu cục bộ, như hiện tượng của trẻ sinh sinh non tháng, tỷ<br /> lệ thành công thấp, tính ổn định của thuật toán thấp. Có thể thấy tỷ lệ thành công và tốc độ<br /> hội tụ luôn trái ngược nhau.<br /> <br /> III. KẾT QUẢ MÔ PHỎNG<br /> Quá trình mô phỏng, so sánh thuật toán DE với các thuật toán khác dưới tác động của<br /> nhiễu Gauss.<br /> Để so sánh, thiết lập các thông số như sau: Số lượng cá thể trong quần thể ∑ = 30, số<br /> lần lặp là ∑ = 45, hệ số tỉ lệ, xác suất lai ghép pc=0.15, xác suất biến thể pm=0.25, ước<br /> lượng kết quả trung bình tọa độ mục tiêu mô phỏng với dữ liệu thực của hệ thống thử<br /> nghiệm RTh được trình bày trong Bảng 1.<br /> Bảng 1. Bảng thống kê dữ liệu kết quả kiểm thử các thuật toán<br /> bằng dữ liệu thực của hệ thống ra đa thử nghiệm RTh.<br /> Tọa độ đo được theo thuật toán và sai số định vị<br /> S<br /> Tọa độ đặt Thuật toán Sai Thuật toán Sai Thuật toán tiến Sai<br /> T<br /> nguồn phát định vị trực số di truyền số hóa vi phân số<br /> T<br /> tiếp LS (m) (GA) (m) (DEA) (m)<br /> 1 21.10347oN, 21.103250oN, 300 21.103250oN, 271 21.103250oN, 242<br /> 105.78685oE 105.789807oE 105.789807oE 105.789807oE<br /> 2 21.10347oN, 21.100648oN, 360 21.100648oN, 320 21.100648oN, 290<br /> 105.78685oE 105.790260 Eo o<br /> 105.790260 E 105.790260oE<br /> 3 21.09834oN, 21.096864oN, 410 21.096864oN, 370 21.096864oN, 322<br /> 105.78646oE 105.790067 Eo o<br /> 105.790067 E 105.790067oE<br /> 4 21.06908oN, 21.059807oN, 119 21.059807oN, 970 21.059807oN, 900<br /> 105.78622oE 105.793485oE 0 105.793485oE 105.793485oE<br /> <br /> <br /> <br /> <br /> 56 P.Q. Thắng, Tr.V. Hùng, “Nghiên cứu sử dụng thuật toán… ra đa thụ động TDOA.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Bảng 1 cho thấy kết quả sai số định vị của các thuật toán khác nhau có nghĩa là sai số<br /> trung bình bình phương dưới tác động nhiễu Gauss. Sai số đo thuật toán DE nhỏ hơn sai số<br /> đo của thuật toán GA và nhỏ hơn sai số đo của thuật toán LS.<br /> <br /> <br /> <br /> <br /> Hình 1. So sánh các thuật toán với các mức nhiễu khác nhau.<br /> <br /> <br /> <br /> <br /> Hình 2. So sánh tốc độ hội tụ của các thuật toán với các mức nhiễu nhỏ 10ns.<br /> Hình 1 cho thấy thuật toán GA có khả năng rơi vào hội tụ cục bộ, khi sai số đo tăng lên,<br /> trong khi đó thuật toán DE và DE-LS cho kết quả tốt hơn. Vì thuật toán kết hợp DE-LS<br /> khởi tạo bằng ước lượng kết quả của thuật toán LS và có không gian tìm kiếm nhỏ trong<br /> phạm vi ước lượng kết quả của thuật toán LS và sai số của nó (14), giúp thuật toán DE-LS<br /> hội tụ nhanh, thời gian tính toán ít hơn và có độ chính xác cao hơn so với thuật toán DE<br /> khi chưa kết hợp.<br /> Để so sánh tốc độ hội tụ của các thuật toán, số vòng lặp kết thúc thuật toán GA và DEA<br /> được thiết lập là 45 thế hệ. Hình 2, 3, 4 cho thấy ba đường cong hội tụ giá trị sai số trung<br /> bình MSE của các thuật toán dưới tác động ở các mức nhiễu khác nhau.<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 57<br />  Ra đa<br /> <br /> Khi sai số phép đo nhỏ (Hình 2), thuật toán DE-LS và LS có sai số gần giống nhau<br /> nhưng tốt hơn so với thuật toán GA và DE. Khi nhiễu tăng lên mức trung bình (Hình 3),<br /> thuật toán DE-LS, GA, DE chính xác hơn so với thuật toán LS nhưng không đáng kể. Khi<br /> nhiễu tăng lên mức cao (Hình 4), thuật toán DE-LS và cả GA, DE đều có độ chính xác cao<br /> hơn so với thuật toán LS. Hình 2-4 cho thấy thuật toán DE-LS hội tụ nhanh hơn GA và<br /> DE, trong khoảng năm thế hệ có thể đạt được sự hội tụ gần đúng với cực tiểu toàn cục,<br /> trong khi thuật toán GA, DE phải đến khoảng thế hệ 20 mới hội tụ. Để khắc phục khả năng<br /> hội tụ cục bộ của thuật toán GA, thuật toán DE-LS đã sử dụng một không gian tìm kiếm<br /> thu hẹp nhỏ hơn.<br /> <br /> <br /> <br /> <br /> Hình 3. So sánh tốc độ hội tụ của các thuật toán với các mức nhiễu vừa 25ns.<br /> <br /> <br /> <br /> <br /> Hình 4. So sánh tốc độ hội tụ của các thuật toán với các mức nhiễu lớn 50ns.<br /> <br /> Trong thực tế để hỗ trợ thuật toán định vị trực tiếp LS trong trường hợp không có<br /> nghiệm hoặc không phân biệt chính xác nghiệm thực, nghiệm giả nhằm tăng tính ổn định<br /> của hệ thống, tức là tăng khả năng phát hiện mục tiêu thì phải dung hòa với thời gian tính<br /> <br /> <br /> 58 P.Q. Thắng, Tr.V. Hùng, “Nghiên cứu sử dụng thuật toán… ra đa thụ động TDOA.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> vì phải giải hai thuật toán khác nhau. Tuy nhiên thời gian giải một thuật toán rất nhỏ cỡ<br /> khoảng 0,01ms đối với thuật toán LS và 0,1ms đối với thuật toán GA, DE trên máy tính<br /> 2GHz nên hoàn toàn chấp nhận được.<br /> <br /> IV. KẾT LUẬN<br /> Qua phân tích thuật toán và mô phỏng kết quả cho thấy thuật toán kết hợp DE-LS đề<br /> xuất có tính ổn định hơn, đồng thời có tốc độ hội tụ nhanh hơn và sai số định vị trung bình<br /> nhỏ hơn so với các thuật toán DE, GA và LS độc lập. Tuy mức độ cải thiện về tốc độ hội<br /> tụ và độ chính xác chưa cao nhưng có thể áp dụng cài đặt song song vào hệ thống TDOA<br /> thực tế nhằm cải thiện độ chính xác định vị và hỗ trợ trong những trường hợp thuật toán<br /> định vị trực tiếp không xác định được nghiệm.<br /> TÀI LIỆU THAM KHẢO<br /> [1] . Phạm Quyết Thắng, Nguyễn Mạnh Cường, “Thuật toán nâng cao độ chính xác định<br /> vị mục tiêu trong rađa thụ động TDOA”, Tạp chí Nghiên cứu Khoa học và Công<br /> nghệ Quân sự, Số 33, 10/2014, tr. 28-35.<br /> [2] . Phạm Quyết Thắng, Trần Văn Hùng, Phạm Văn Hùng, Vũ Văn Đáng, Phạm Văn<br /> Toàn, (12/2015) “Nâng cao độ chính xác định vị mục tiêu trong hệ thống ra đa thụ<br /> động TDOA bằng thuật toán di truyền”, Tạp chí Nghiên cứu khoa học và công nghệ<br /> quân sự, số 40, tr. 63-69.<br /> [3] . Yan-Ping Lei，Feng-Xun Gong and Yan-Qiu Ma, “Optimal Distribution for Four-<br /> Station TDOA Location System”, 978-1-4244-6498-2/10 IEEE, 3rd International<br /> Conference on Biomedical Engineering and Informatics (BMEI 2010), PP. 2858-2862.<br /> [4] . J.S. Abel, “A divide and conquer approach to least-squares estimation,” IEEE<br /> Trans. Aerosp. Electron. Syst., vol. 26, pp. 423-427, Mar. 1990.<br /> [5] . Foy, H, Wade. “Position-location solutions by Taylor-series estimation”. 1976.<br /> IEEE Transaction on Aerospace and Electronic Systems. vol. AES-12, No. 2, pages<br /> 187-194. ISSN: 0018-9251.<br /> [6] . Chan, Y.T.; Ho, K.C. “A simple and efficient estimator for hyperbolic location”.<br /> IEEE Trans. Signal Proc. 1994, 42, 1905–1915.<br /> [7] . Fang, B.T. “Simple solutions for hyperbolic and related position fixes”. IEEE<br /> Trans. Aerosp. Electr. Syst. 1990, 26, 748–753.<br /> [8] . Lili Chun, Ranchong Sen, Wei Feng, “Enhanced Genetic Algorithm for TDOA<br /> location estimation in nonlinear optimization problem”. Systems Engineering and<br /> Electronics, 2003, pp. 971-973.<br /> [9] . Yao-Tang Chang, Chi-Lin Wu and Hsu-Chih Cheng, “The Enhanced Locating<br /> Performance of an Integrated Cross-Correlation and Genetic Algorithm for Radio<br /> Monitoring Systems”. SSN 1424-8220, Sensors 2014, p.7541-7562;<br /> [10] . Z. Michalewicz, “Genetic Algorithms + Data Structure = Evolution Programs”.<br /> NewYork, Springer Press, 1996, ch. 5.<br /> [11] . David A.Coley, “An instroduction to Genetic Algorithm”, 2006.<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 59<br />  Ra đa<br /> <br /> [12] . Musrrat Ali1, Millie Pant1 and Ajith Abraham, “Simplex Differential Evolution”,<br /> Acta Polytechnica Hungarica, Vol. 6, No. 5, 2009.<br /> [13] . Liu Bo, Wang Ling, Jin Yihui, “Differential evolutionary algorithm research<br /> progress”, Vol. 22, No. 7, July 2007.<br /> [14] . R. Storn, K. Price, “DE-a Simple and Efficient Adaptive Scheme for Global<br /> Optimization over Continuous Space”, Technical Report TR-95-012, ICSI, March 1995.<br /> [15] . Li Ke, Zheng Jinhua Ling, “An improved multi-objective evolutionary algorithm<br /> based on differential evolution”. Computer Engineering and Applications, 2008, p.<br /> 51-56.<br /> [16] . Ashish Ghosh, “Evolutionary Algorithms for Muti-Criterion Optimization: A<br /> Survey”, International Journal of Computing & Information Sciences, Vol 2, No.1,<br /> April 2004.<br /> ABSTRACT<br /> ENHANCED POSITION ESTIMATION PRECISION BY IMPROVING THE<br /> DIFFERENTIAL EVOLUTION ALGORITHM FOR SOLVING THE HYPERBOLIC<br /> LOCATION IN TDOA PASSIVE RADAR SYSTEM<br /> This paper proposes solutions to solve the problems of locating the target in<br /> passive radar systems TDOA by using differential evolution algorithm and<br /> combined with a directly positioning algorithm. The combination of using the<br /> estimated location of a directly positioning algorithm to initializes the differential<br /> evolution algorithm to reduce the search space as well as speed up the convergence<br /> of differential evolution algorithm . This method of solving the optimization problem<br /> for fast convergence speed, high positioning accuracy, especially when large noise<br /> intensity.<br /> Keywords: Passive radar, Location errors, Genetic algorithms, Differential evolution algorithms, TDOA<br /> <br /> <br /> Nhận bài ngày 09 tháng 3 năm 2016<br /> Hoàn thiện ngày 14 tháng 4 năm 2016<br /> Chấp nhận đăng ngày 20 tháng 4 năm 2016<br /> <br /> 1<br /> Địa chỉ: Cục Khoa học quân sự/BQP,<br /> 2<br /> Viện Ra đa, Viện Khoa học, Công nghệ quân sự/BQP;<br /> *<br /> Email: phamquyetthang@outlook.com<br /> <br /> <br /> <br /> <br /> 60 P.Q. Thắng, Tr.V. Hùng, “Nghiên cứu sử dụng thuật toán… ra đa thụ động TDOA.”<br />