Xem mẫu
- Tên lửa & Thiết bị bay
PHƯƠNG THỨC TỰ TỔ CHỨC VÀ ỨNG DỤNG NHẬN DẠNG
MỤC TIÊU TRÊN BIỂN
Nguyễn Công Thức1*, Đàm Hữu Nghị2, Nguyễn Xuân Hùng1, Phạm Tuấn Hùng3
Tóm tắt: Phỏng theo sự tiến hóa của tự nhiên là phương pháp đang được áp
dụng rộng rãi trong nhiều lĩnh vực đặc biệt là trong điều khiển học kỹ thuật để xây
dựng thuật toán giải các bài toán nhận dạng, điều khiển và dự báo. Trong bài báo
này, nhóm tác giả trình bày một sự bắt chước như thế đó là phương thức tự tổ chức
với thuật toán tổng quát МГУА. Ứng dụng thuật toán để giải quyết bài toán phân
lớp và nhận dạng các mục tiêu trên biển. Kiểm tra trên tập dữ liệu thực cho thấy
xác suất phân lớp và nhận dạng đúng đặt trên 98,4%.
Từ khóa: Hải quân; Tàu tên lửa; Tự tổ chức; Tối ưu hóa; Nhận dạng.
1. ĐẶT VẤN ĐỀ
Một trong những vấn đề của điều khiển học kỹ thuật là xây dựng các thuật toán tối ưu
để nhận dạng, dự báo và điều khiển tự động các đối tượng phức tạp. Trong điều kiện
không có đầy đủ thông tin, bằng phương pháp giải tích,đưa ra các thuật toán này là hết sức
khó khăn [4, 5]. Bởi vậy, mô phỏng hoạt động của tự nhiên là một phương pháp có triển
vọng mang lại kết quả tích cực - phương thức tự tổ chức với thuật toán tổng quát МГУА.
Có thể nói, МГУА đã bước đầu được áp dụng thành công trong các trường hợp, mà
việc mô tả toán học cho bài toán gặp rất nhiều khó khăn. Ví dụ: các hệ thống phức hợp
(complex systems) với các hàm mục tiêu ẩn và các mối ràng buộc phức tạp, các bài toán
thiết kế với các hàm mục tiêu quá phức tạp không tuyến tính, hay là bài toán vận tải.
Trong lĩnh vực quân sự, nhìn chung thuật toán МГУА chưa thu hút được các nghiên cứu
và đề xuất. Lí do cho nhận định này có thể thấy là bài toán tự động hóa chỉ huy trong quân
sự thuộc lớp bài toán rộng rất nhiều lĩnh vực có thể nhìn thấy như bài toán nhận dạng mục
tiêu lập kế hoạch tác chiến, bài toán chuẩn bị vật chất kỹ thuật phục vụ chiến đấu, bài toán
phân chưa tên lửa vào mục tiêu và đánh giá tình hình diễn biến trên khu vực tác chiến.
Trong khuôn khổ bài báo này, các tác giả đã tìm hiểu xây dựng bài toán nhận dạng mục
tiêu trên biển ngay cả khi thông tin về mục tiêu không đầy đủ.
Bài báo tập trung khai thác xây dựng thuật toán tự động hóa quá trình ra quyết định
trong tác chiến với biên đội tàu tên lửa.
Đóng góp chính của bài báo này bao gồm: Phân tích và xây dựng mô hình bài toán
nhận dạng và phân loại mục tiêu trên biển ứng dụng thuật toán МГУА. Các tác giả đã sử
dụng biểu diễn số nguyên sau khi đã lượng tử hóa, các toán tử lai ghép và lựa chọn. Thực
hiện phép tiến hóa qua nhiều thế hệ để chọn ra phương án phù hợp nhất. Kết quả thử được
trên bộ dữ liệu thử nghiệm cho thấy việc nhận dạng và phân nhóm đạt kết quả tốt. Kết quả
này cũng được kiểm chứng thông qua so sánh với thuật toán cây quyến định, mạng nơ ron
nhân tạo. Bài báo gồm các nội dung chính sau: Tổng quan về phương thức tự tổ chức và
thuật toán МГУА; ứng dụng giải bài toán nhận dang mục tiêu trên biển và phần kết luận
đánh giá.
2. NỘI DUNG BÀI BÁO
2.1. Tổng quan về phương thức tự tổ chức
Trong tự nhiên, những quy luật qua trọng nhất liên quan tới quá trình chọn lọc tự nhiên,
tiến hóa và thích nghi. Chính những quy luật của các quá trình này tạo nên nền tảng của
một phương thức tiếp cận mới đối với bài toán tối ưu hóa mô hình toán học các đối tượng
nhận dạng, điều khiển và dự báo - phương thức tự tổ chức [4, 5, 10].
14 N. C. Thức, …, P. T. Hùng, “Phương thức tự tổ chức … nhận dạng mục tiêu trên biển.”
- Nghiên cứu khoa học công nghệ
Bản chất của phương thức tự tổ chức là quá trình chọn lọc nhiều tầng [9]. Sau mỗi tầng
lựa chọn, mô hình sẽ được phức tạp hóa dần.
Thuật toán chọn N cặp dấu hiệu tốt nhất
Thuật toán chọn N cặp dấu hiệu tốt nhất
Thuật toán chọn N cặp dấu hiệu tốt nhất
Bảng dữ liệu đầu vào
gồm N dấu hiệu đã
Thuật toán dừng
lượng tử hóa
Thuật toán dừng
Thuật toán dừng
Hình 1. Mô hình hoạt động của phương thức tự tổ chức (Thuật toán МГУА).
Cũng như tiến hóa dựa trên khái niệm cho rằng quá trình tiến hóa tự nhiên là hoàn hảo
nhất, hợp lý nhất và tự nó đã mang tính tối ưu. Sự tối ưu đó được thể hiện ở chỗ thế hệ sau
bao giờ cũng phát triển tốt 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ổ sung thay thế thế hệ cũ, cá thể nào thích ứng với môi
trường sẽ tồn tại, ngược lại sẽ bị đào thải.
Phương thức tự tổ chức cung cấp một phương pháp học được thúc đẩy bởi sự tương tự
với sự tiến hóa sinh học. Thay vì tìm kiếm các giả thuyết từ tổng quát đến cụ thể hoặc từ
đơn giản đến phức tạp, phương thức tự tổ chức tạo ra các giả thuyết kế tiếp bằng phương
pháp lặp lại việc tái hợp các cặp dấu hiệu của bộ dấu hiệu nhận dạng ban đầu.
Phương thức tự tổ chức hoạt động bằng cách cập nhật liên tục tập giả thuyết - được gọi
là bộ dấu hiệu khởi tạo. Ở mỗi tầng chọn lọc, tất cả dấu hiệu nhận dạng trong quần thể
được ước lượng tương ứng với hàm thích nghi. Các cặp biến mới được tạo thành bằng
cách lựa chọn theo thứ tự các bộ dấu hiệu tốt nhất được ra từ lần tiến hóa hiện tại.
2.2. Thuật toán МГУА
2.2.1. Cơ sở khoa học
Phương pháp Bayes có thể phân loại cho hai hay nhiều tổng thể và có thể dựa ra cảnh
báo bằng xác suất nhận dạng sai [2, 6, 7, 8].
Cho biến cố A và {H1,H2..Hk} là nhóm biến cố đầy đủ của một phép thử, khi đó, ta có
công thức:
k
P(A)= P(H i )P( A ) (1)
i=1
Hi
P(H j )P( A )
Hj
P(H j /A)= k
; j = 1,2..k (2)
P(Hi )P( A
i=1
Hi
)
Trong bài toán phân loại, A liên quan tới biến quan sát, Hi là tổng thể thứ i; P(Hi) là xác
suất tiên nghiệm cho tổng thể thứ i. Mục tiêu là tìm xác suất hậu nghiệm P(Hi/A). Việc
phân loại hay nhận dạng một mẫu nào đó vào lớp này hay lớp kia đều chữa đựng một độ
mạo hiểm nhất định [5].
Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 15
- Tên lửa & Thiết bị bay
k
ρ(d i )= P(H i ).L[H i ,d j (A)].P( A ) (3)
i=1
Hi
Trong đó:
ρ(di ) : Độ mạo hiểm gặp phải khi có sự lựa chọn dj mà kết quả của sự lựa chọn
này lại là chọn giải pháp Hi;
L[H i ,d j (A)] : Ma trận thiệt hại, thể hiện mức độ thiệt hại phải gánh chịu khi giải
pháp đúng là Hi nhưng lại lựa chon dj có lợi cho giải pháp Hj.
d11 d12 d13 ... d1n
d d 22 d 23 ... d 2n
L[H i ,d j (A)]=
21
(4)
... ... ... ...
d n1 d n2 d n,n-1 ... d nn
d j (A) : Lựa chọn dj khi biến cố A xẩy ra.
P(Hi): xác suất tiên nghiệm.
Nếu biến cố A được lượng tử hóa bằng bộ tham số rời rạc x1, x2…xn với xi nhận giá trị
0,1,2…q thì (3) được viết lại như sau:
k
x1 ,x 2 ,...,x n
ρ(d i )= P(H i ).L[H i ,d j (x1 ,x 2 ,...,x n )].P( ) (5)
i1
Hi
Quyết định được lựa chọn nhận dạng thỏa mãn:
d*j =arg dmin
j
ρ(d j ) (6)
Ta thấy rằng thuyết giải pháp thông kê dựa trên biểu thức (5) rất khó áp dụng vào các
bài toán thực tiến vì các lý do sau:
Các ma trận d j (x1 ,x 2 ,...,x n ) và P(x1 ,x 2 ,...,x n /Hi là m trân đầy đủ vì có tính tới tất cả
các biến cũng như biến liên hiệp khi các biến này phụ thuộc lẫn nhau.
Để xác định được đầy đủ các ma trận này đòi hỏi phải có lượng thông tin ban đầu đủ
lớn và phải đảm bảo nghiêm tính dừng trong quá trình lựa chọn.
Trong thực tế, dù lượng thông tin không đầy đủ cũng phải giải quyết bài toán để đưa ra
được quyết định cuối cùng.
Ngoài ra, bài toán lựa chọn giải pháp còn phụ thuộc độ chính xác của thông tin tiên
nghiệm P(Hi) và thông tin về mức độ thiệt hại liên quan tới việc lựa chọn giải pháp.
Phương pháp giải pháp thống kê nhiều tầng được xây dựng trên cơ sở biến đổi công
thức (5) thành dạng nhiều tầng.
Khả năng biến đổi thuật toán (5) thành thuật toán nhiều tầng là ở chỗ, trong (5) có phần
tử p(x1,x2…xn).
x1 ,x 2 ,...,x n
Coi mô tả P( ) f(x1 ,x 2 ,...,x n ) , thay mô tả đầy đủ
Hi như mô tả đầy đủ
x ,x ,...,x n x ,x
P( 1 2 ) bằng các mô tả thành phần P( i j ) . Những mô tả thành phần
Hi Hi
x ,x
P( i j ) tương ứng mô tả thành phần f(x i ,x j ) của , (5) được biến đổi thành:
Hi
16 N. C. Thức, …, P. T. Hùng, “Phương thức tự tổ chức … nhận dạng mục tiêu trên biển.”
- Nghiên ccứu
ứu khoa học công nghệ
k
x ,x
ρ (d j )=P(Hi ).L[Hi ,d j (x ,x )].P( ) (7)
i1
Hi
Trong mmỗi
ỗi tầng chọn lọc sử dụng độ mạo hiểm tối thiểu (6) để lựa chọn các mô hhình
ình
phần tử tốt nhất. Độ mạo hiểm ρ được
phần được xác định theo các điểm kiểm tra.
Các mô hình phphần
ần tử tốt nhất ở tầng chọn lọc tr
trưước
ớc sẽ đđư
ược
ợc sử dụng nh
nhưư các bi
biến
ến ở
tầng
ầng chọn lọc sau.
Sửử dụng các giá trị lựa chọn dj ở tầng chọn lọc tr
trước
ớc llàm
àm bi
biến
ến cho các mô tả th
thành
ành ph
phần
ần
của
ủa tầng chọn lọc sau.
αk-1 k-1
r ,αs
αk =argmin
= argmin ρkr,s (d j )=argmin{
)= argmin{ P(Hi )L[Hi ,d j (αrk-1,αsk-1 )].P( )} (8)
dj dj i
Hi
Trong đó:
k là ký hiệu
hiệu tổng quát của biến trong mô tả th
thành
ành phần
phần của tầng chọn lọc thứ k.
r,s là chỉ
chỉ số các biến trong mô tả th
thành
ành ph
phần
ần của tầng chọn lọc tr
trước.
ớc.
Thuật
Thu ật toán sẽ dừng tại tầng chọn lọc có số
ố lần ra quyết định dj đúng nhiều
nhiều nhất tr
trên
ên ttập
ập
kiểm
ểm tra.
k
Như vậy
vậy, tại
ại mỗi tầng chọn lọc, ngo
ngoài
ài việc tạo các mô tả phần tử để
việc để thực hiện xây
dựng
ựng mô hhình
ình còn ph
phải (α rk-1 ,αsk-1 )] và tính toán llại
ải chính xác hóa ma trận phạt L[Hi ,d j (α ại ma
α k-1 k-1
r ,α s
ận xác suất hậu nghiệm P(
trận ) . Chính quá trình thích nghi các ma tr ận này
trận này làm
Hi
tăng tính hhội
ội tụ của quá tr
trình
ình chọn
chọn lọc.
2.2.2. Xây dựng
2.2.2. dựng thuật toán
Dữ
ữ liệu ban đầu của bbài
ài toán nh
nhận
ận dạng llàà giá trị
trị của các dấu hiệu và quy ết định để
quyết
phân lo
loại
ại mẫu vào
vào lớp
lớp nnày
ày hay llớp
ớp khác. Tập dữ liệu đđược
ợc biểu diễn ở dạng bảng 1.
Bảng 1. Biểu
ảng 1. ểu diễn tập dữ liệu ban đầu
đầu..
l i, j Mẫu
Mẫu thử j đặc tr
trưng bởi giá trị của các dấu hiệu i trong llớp
ưng bởi ớp l. Các giá trị i , j
trong các llớp
ớp có thể llàà giá tr
trịị tuyệt đối hoặc giá trị llượng
ợng tử hóa.
Ri Lớp
ớp thứ i. Giá trị của các Ri là biết
biết tr
trước.
ớc. Mỗi lớp Ri đđặc
ặc tr
trưng
ưng bởi
bởi một nguy
nguyên
ên m
mẫu.
ẫu.
Tạp
ạp chí Nghi
Nghiên
ên cứu
cứu KH&CN quân
uân sự,
sự, Số 566, 088 - 2018
20 8 17
- Tên lửa & Thiết bị bay
αk+1 k+1
r ,αs αkr ,αsk
P( ) P( )
Hi Hi
Hình 2. Lưu đồ thuật toán phương thức tự tổ chức sử dụng
mô hình giải pháp thống kê nhiền tầng.
3. MÔ PHỎNG, TÍNH TOÁN VÀ THẢO LUẬN
3.1 Xây dựng bảng số liệu đầu vào
Từ [1] cho ta bảng thông số kỹ thuật chung của một số lớp tàu là đối tượng tác chiến
của Hải quân nhân dân Việt Nam.
Bảng 2. Thông số kỹ thuật của một số tàu Hải quân nước ngoài.
Áp dụng thuật toán phân cụm dữ liêu, các tác giả đã xây dựng 657 mẫu cho 7 lớp tàu
trên như phụ lục và bảng 2.
18 N. C. Thức, …, P. T. Hùng, “Phương thức tự tổ chức … nhận dạng mục tiêu trên biển.”
- Nghiên ccứu
ứu khoa học công nghệ
Bảng 3. Dấu
ảng 3. ấu hiệu nhận dạng mẫu sau llượng
ợng tử
tử..
Bảng 4 Quy ước
ảng 4. ước biến sơ cấp
cấp cho bài
bài toán
toán..
3.2. Phương pháp, công ccụ ụ mô phỏng
Trong bài báo này
này, nhóm tác gi
giảả sử dụng phần mềm Matlab để tính toán, mô phỏng vvàà
kiểm
ểm chứng khả năng nhận dạng đúng của thuật toán. Đồng thời thời, so sánh m ức độ tối ưu
mức
của
ủa ph
phương
ương thức
thức tự tổ chức với mộtột số thuật toán nh
nhưư mạng
mạng nnơ
ơ ron nhân ttạo,
ạo, thuật toán
cây quy
quyết
ết định.
3.3 K
3.3. Kết
ết quả mô phỏng
3.3.1. Nhận
3.3.1. Nhận dạng bằng mạng N Nơơ ron
Hình 3. Kết quả phân nhóm mục ti
Kết tiêu
êu bằng
bằng mạng N
Nơ
ơ ron
ron.
Tạp
ạp chí Nghi
Nghiên
ên cứu
cứu KH&CN quân
uân sự,
sự, Số 566, 088 - 2018
20 8 19
- Tên lửa & Thiết bị bay
Kết quả trên cho ta thấy, khả năng phân lớp đúng của mạng Nơ ron đạt từ 80% trở lên.
Trung bình nhận dạng đúng đạt 90%.
3.3.2. Nhận dạng bằng cây quyết định
Tổng số node 28.
Xác suất nhận dạng đúng 91.85%.
3.3.3. Nhận dạng bằng phương thức tự tổ chức sử dụng mô hình giải pháp thống kê nhiều
tầng
Bảng 5. Hệ số nhận dạng đúng của các lớp sau từng tầng chọn lọc.
Bằng phương pháp truy xuất biến, thuật toán cho ta thấy những dấu hiệu nào là ảnh
hưởng lớn nhất, những dấu hiệu nào không ảnh hưởng đến kết quả nhận dạng.
x2x6.x1x3.x2x6.x1x5.x2x6.x1x3.x2x3.x1x5.x2x6.x1x3.x2x6.x1x5.x2x3.x1x5.x2x5.x2x6.
s
x (9)
ρ(d j )= P(R i )L[R i ,d j (x)]Pa ( )
i=1 R i
x xx xx xx xx xx
Trong đó: Pa ( )= P 6 ( 2 6 ).P 4 ( 1 5 ).P 3 ( 1 3 ).P 2 ( 2 3 ).P( 2 5 ) (10)
Ri Ri Ri Ri Ri Ri
P(Ri): Xác xuất tiên nghiệm ban đầu.
L[R i ,d j (x)] : Ma trận phạt sau khi đã thích nghi.
Vậy ta có thuật toán nhận dạng
s
6 x2 x6 4 x1 x5 3 x1 x3 2 x2 x3 x2 x5
j P(R i )L[R i ,d j (x)]P ( R ).P ( R ).P ( R ).P ( R ).P( R )
ρ(d )=
i=1 i i i i i
(11)
*
d j = argmin ρ(d j )
dj
Bảng 6. Độ phức tạp của mô hình qua từng tầng chọn lọc.
Từ bảng 5, bảng 6 có thể thấy, khả năng phân nhóm đúng của thuật toán tăng dần theo
mỗi tầng chọn lọc. Mô hình nhận dạng của bài toán theo đó cũng được phức tạp hóa dần
làm tăng độ chính xác.
Ma trận thiệt hại
20 N. C. Thức, …, P. T. Hùng, “Phương thức tự tổ chức … nhận dạng mục tiêu trên biển.”
- Nghiên cứu khoa học công nghệ
0 0.1285 0.1457 0.1003 0.0997 0.1372 0.1526
0.1084 0 0.1457 0.1003 0.0997 0.1372 0.1526
0.1084 0.1285 0 0.1003 0.0997 0.1372 0.1526
L 0.1084 0.1285 0.1457 0 0.0997 0.1372 0.1526
0.1084 0.1285 0.1457 0.1003 0 0.1372 0.1526
0.1084 0.1285 0.1457 0.1003 0.0997 0 0.1526
0.1084 0.1285 0.1457 0.1003 0.0997 0.1372 0
Hình 4. Xác suất phân loại đúng sau mỗi tầng chọn lọc.
Hình 5. Xác suất nhận dạng đúng sau các lần chạy kiểm tra thuật toán.
Với kết quả thực nghiệm mô phỏng có thể thấy phương thức tự tổ chức cho ta kết quả
nhận dạng khá tốt ngay cả khi thông tin về đối tượng không đầy đủ. Điều này rất cần thiết
và phù hợp để ứng dụng thuật toán trong lĩnh vực quân sự.
4. KẾT LUẬN
Dựa trên phương thức tiến hóa và chọn lọc trong tự nhiên phương thức tự tổ chức với
thuật toán tổng quát МГУА đã hình thành và phát triển mang lại triển vọng lớn để giải
quyết bài toán nhận dạng điều khiển và dự báo ngay cả khi thông tin về đối tượng nhận
dạng là không đầy đủ. Có thể thấy với bài toán nhận dạng mục tiêu trên biển ứng dụng
trong lĩnh vực quân sự, thuật toán đã mang lại kết quả tốt hơn so với một số thuật toán đã
sử dụng trước đây. Ngoài ra, thuật toán có thể được xem xét cải tiến theo hướng kết hợp
với giải thuật di truyền gây “đột biến” ở một số cặp dấu hiệu ở các vòng lặp.
TÀI LIỆU THAM KHẢO
[1]. Quân chủng Hải quân (2000) “Nhận dạng mục tiêu trên biển” NXB Quân đội Nhân
dân (2000).
[2]. Võ Văn Tài, Phạm Gia Thụ, Tô Anh Dũng, “Sai số Bayes và khoảng cách giữa hai
hàm mật độ xác suất trong phân loại hai tổng thể”, Tạp chí phát triển khoa học và
công nghệ, Đại học Quốc gia TPHCM (2008), 11(1) tr 21 - 30.
Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 21
- Tên lửa & Thiết bị bay
[3]. Hoàng Kiểm (1981), “Một số mô hình và thuật toán chẩn đoán, ứng dụng trong
điều tra cơ bản”.
[4]. Ивахненко. Аг. “Самообучающеся системы распознавания
автоматического управления” , Изд. Теника 1974.
[5]. Ивахненко Аг., Зайченко Ю.П, “Принятие решений на основе
cамоорганизаций”, Советское радио (1976).
[6]. Richard O. Duda, Peter E. Hart, David G. Stork (2001) Pattern classification (2nd
edition), Wiley, New York, ISBN 0-471-05669-3.
[7]. Fukunaga, K. “Introduction to statistical pattern recognition”, 2nd Ed., Academic
Press, New York(1990).
[8]. Matinez, W.L. and Matinez, A.R “Computational statistics handbook whit
Matlab”, Chapman&Hall/CRC, Boca Raton.,(2008).
[9]. A.G. Ivakhnenko, “Heuristic Self-Organization in Problems of Engineering
Cybernetics”, vol.6 (1970), pp. 207-219.
[10]. Roman Sushkov “ Self-Organizing Structures for the Travelling Salesman
Problems in a Plygonal Domain”, Czech Technical University in Prague (2015).
ABSTRACT
SELF-ORGANIZATION AND APPLICATIONS
FOR IDENTIFYING TARGETS AT THE SEA
Emulating the evolution of the nature is a method that is widely applied in
numerous fields, especially in cybernetics for building algorithms related to
recognition, cybernetics and prediction. In this paper, the emulation for generated
algorithm MIYA is applied. The MTYA likely included of different variations. In the
paper, one application of a statistical solution to resolve the layered and
recognition problems. The verification on the real data shows that accurate layered
statistic and recognition is over 98.4%.
Keywords: Navy; Missile corvettes; Self-organization; Optimization; Recognition.
Nhận bài ngày 19 tháng 01 năm 2018
Hoàn thiện ngày 03 tháng 4 năm 2018
Chấp nhận đăng ngày 10 tháng 8 năm 2018
1
Địa chỉ: Học viện Hải quân;
2
Học viện Kỹ thuật quân sự;
3
Viện Kỹ thuật Phòng không - Không quân.
*
Email: congthucauto@gmail.com.
22 N. C. Thức, …, P. T. Hùng, “Phương thức tự tổ chức … nhận dạng mục tiêu trên biển.”
nguon tai.lieu . vn
