Phương thức tự tổ chức và ứng dụng nhận dạng mục tiêu trên biển

Tên lửa & Thiết bị bay 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.” 14 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]. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 15 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. B ảng dữ liệu đ ầu vào g ồm N dấu hiệu đ ã lư ợ ng tử hóa T huật toán chọ n N cặp dấu hiệu tốt nh ất T hu ật toán dừ n g T huật toán ch ọn N cặp dấu hiệu tố t nh ất T huật toán dừ ng T huật toán chọ n N cặp dấu hiệu tốt nh ất T hu ật toán dừ n g 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 i i i=1 AP(A)= P(H )P( ) H (1) j j j k i i i=1 AP(H )P( ) H P(H /A)= ; j = 1,2..k AP(H )P( ) H (2) 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ên lửa & Thiết bị bay 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.” 16 k i i j i i=1 Aρ(d )= P(H ).L[H ,d (A)].P( ) Hi (3) Trong đó: iρ(d ) : Độ 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; i jL[H ,d (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. 11 12 13 1n 21 22 23 2n i j n1 n2 n,n-1 nn d d d ... d d d d ... d L[H ,d (A)]= ... ... ... ... d d d ... d             (4) jd (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, x2xn với xi nhận giá trị 0,1,2q thì (3) được viết lại như sau: 1 2 i i j 1 2 i1 x ,x ,...,x ρ(d )= P(H ).L[H ,d (x ,x ,...,x )].P( ) H k n i n i  (5) Quyết định được lựa chọn nhận dạng thỏa mãn: j * min j d jd =arg ρ(d ) (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 j 1 2d (x ,x ,...,x )n và 1 2 iP(x ,x ,...,x /Hn 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,x2xn). Coi mô tả 1 2 i x ,x ,...,x P( ) H n như mô tả đầy đủ 1 2f(x ,x ,...,x )n , thay mô tả đầy đủ 1 2 i x ,x ,...,x P( ) H n bằng các mô tả thành phần i x ,x P( ) H i j . Những mô tả thành phần i x ,x P( ) H i j tương ứng mô tả thành phần f(x ,x )i j của , (5) được biến đổi thành: Nghiên c Tạp chí Nghi ph tầng chọn lọc sau. của tầng chọn lọc sau. kiểm tra. dựng mô h trận xác suất hậu nghiệm tăng tính h 2.2.2 phân lo trong các l Trong m ần tử tốt nhất. Độ mạo hiểm Các mô hình ph Sử dụng các giá trị lựa chọn d Trong đó: k r,s là ch Thu Như v . Dữ liệu ban đầu của b  Ri α =argminρ (d )=argmin{ P(H )L[H ,d (α ,α )].P( )} là ký hi ật toán sẽ dừng tại tầng chọn lọc có Xây d ại mẫu v i, j l M Lớp thứ i. Giá trị của các R ứu khoa học công nghệ k k k-1 k-1 ỉ số các biến trong mô tả th ậy ình còn ph ội tụ của quá tr ẫu thử j đặc tr ớp có thể l ên c ỗ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ô h ệu tổng quát của biến trong mô tả th , tại mỗi tầng chọn lọc, ngo ựng thuật toán ứu KH&CN j jd d ào l ần tử tốt nhất ở tầng chọn lọc tr ớp n r,s j i i j r s ải chính xác hóa ma trận phạt à giá tr ρ (d )= P(H ).L[H ,d (x ,x )].P( )  P( ) ình ch ài toán nh ày hay l ưng b quân s α ,α ị tuyệt đối hoặc giá trị l j i ρ k-1 k-1 r s ọn lọc. ớp khác. Tập dữ liệu đ ởi giá trị của các dấu hiệu ự, Số k i  đư j ở tầng chọn lọc tr i là bi 1 ợc xác định theo các điểm kiểm tra. ành ph H ận dạng l ết tr 56 i  ài vi i , 08 số lần ra quyết định d ệc tạo các mô tả phần tử . Chính quá trình thích nghi các ma tr ước. Mỗi lớp R - 20 i j ần của tầng chọn lọc tr à giá tr 18 ành ph   ư ước l L[H ,d ( ị của các dấu hiệu Bảng 1 ượng tử hóa. ớc sẽ đ àm bi ần của tầng chọn lọc thứ k. i j r s ược biểu diễn ở dạng bảng 1. .  i đ x ,x ư ến cho các mô tả th k-1 k-1α ,α )] Biểu diễn tập dữ liệu ban đầu i trong l ặc tr   ợc sử dụng nh j ưng b ước. đúng nhi iH  ớp l. Các giá trị ởi một nguy k-1 k-1 r sα ,α k đ và tính toán l và quy ư các bi ều nhất tr ể thực hiện xây ận n ết định để ành ph iH ày làm ên m ến ở ên t ại ma  ẫu. 17 (7) ình ần (8) ập . ,i j Tên lửa & Thiết bị bay 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.” 18 k+1 k+1 k k r s r s i i α ,α α ,α P( ) P( ) H H  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. Nghiên c Tạp chí Nghi 3.2. Phương pháp, công c kiểm chứng khả năng nhận dạng đúng của thuật toán. Đồng thời của ph cây quy 3.3 3.3.1 Trong bài báo này . K . ương th ết định. ết quả mô phỏng Nh ứu khoa học công nghệ ận dạng bằng mạng N ên cứu KH&CN ức tự tổ chức với Hình 3. , nhóm tác gi K quân s ụ mô phỏng ết quả phân nhóm mục ti ơ ron ự, Số ả sử dụng phần mềm Matlab để tính toán, mô phỏng v một số thuật toán nh 56 , 08 Bảng 3 - 2018 . Bảng 4 Dấu hiệu nhận dạng mẫu sau l êu b . Quy ư ư m ằng mạng N ạng n ớc biến ơ ron nhân t , so sánh m ơ ron sơ c ấp cho b . ạo, thuật toán ức độ tối ượng tử ài toán 19 . . à ưu Tên lửa & Thiết bị bay 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.” 20 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 j i i j a i=1 i x ρ(d )= P(R )L[R ,d (x)]P ( ) R  (9) Trong đó: 6 4 3 22 6 1 5 1 3 2 3 2 5 i P ( )= P ( ).P ( ).P ( ).P ( ).P( ) R a i i i i i x x x x x x x x x xx R R R R R (10) P(Ri): Xác xuất tiên nghiệm ban đầu. i jL[R ,d (x)] : Ma trận phạt sau khi đã thích nghi. Vậy ta có thuật toán nhận dạng j s 6 4 3 22 6 1 5 1 3 2 3 2 5 j i i j i=1 * j j d ρ(d )= P(R )L[R ,d (x)]P ( ).P ( ).P ( ).P ( ).P( ) d =argmin ρ(d ) i i i i i x x x x x x x x x x R R R R R       (11) 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 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 21 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ên lửa & Thiết bị bay 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.” 22 [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 Địa chỉ: 1 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.