автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы и алгоритмы оптимизации траектории наблюдателя в задаче определения координат и параметров движения цели

Іа правах рукої

СТЕПАНОВ Денис Вячеславович

МЕТОДЫ И АЛГОРИТМЫ ОПТИМИЗАЦИИ ТРАЕКТОРИИ НАБЛЮДАТЕЛЯ В ЗАДАЧЕ ОПРЕДЕЛЕНИЯ КООРДИНАТ И ПАРАМЕТРОВ ДВИЖЕНИЯ ЦЕЛИ

Специальность 05.13.01. Системный анализ, управление и обработка информации

(судостроение)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

26І2

Санкт Петербург - 2012

005020067

Работа выполнена в НИО-ЗО ОАО «Концерн «НПО «Аврора»

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор технических наук,

профессор ШАЛЫТО Анатолий Абрамович

ЧУДАКОВ Олег Евгеньевич доктор технических наук, профессор, Военный учебно-научный центр «Военно-морская академия» (филиал г. Петродворец), профессор кафедры информационных технологий

ТУЛУПЬЕВ Александр Львович доктор физико-математических наук, доцент, Санкт-Петербургский институт информатики и автоматизации РАН, заведующий лабораторией теоретических и междисциплинарных проблем информатики

ОАО «Концерн «Океанприбор», Санкт-Петербург

Защита диссертации состоится «

он

2012 г. в 14.00 на заседании

диссертационного совета Д 411.003.01 при ОАО «Концерн «НПО «Аврора» по адресу: 194 021, Санкт-Петербург, ул. Карбышева, 15. Ч/

С диссертацией можно ознакомиться в библиотеке ОАО «Концерн «НПО «Аврора» по адресу: 194021, Санкт-Петербург, ул. Карбышева, 15.

Автореферат разослан « и » О3 2012 г.

Ученый секретарь диссертационного совета, доктор технических наук, профессор

А.А. Шалыто

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность. В диссертации рассматривается задача совершенствования методов построения траектории наблюдателя, оптимизированной по точности статистических оценок координат и параметров движения цели (КПДЦ). Задача определения КПДЦ состоит в статистической оценке наблюдателем координат и параметров движения объекта наблюдения (цели). Задача построения оптимизированной траектории наблюдателя представляет собой оптимизационную задачу поиска параметров движения наблюдателя, обеспечивающих повышение точности оценок КПДЦ. В настоящей работе задача построения оптимальной траектории наблюдателя рассматривается применительно к оценке параметров движения морских целей только по измерениям пеленга.

Анализ существующих рекомендаций по маневрированию и методов построения траектории наблюдателя при определении КПДЦ показал, что они обладают следующими недостатками: не доставляют оценки КПДЦ приемлемой точности; делают ограничительные предположения относительно параметров движения цели; не позволяют получать решение в режиме реального времени; предполагают частое маневрирование; сложно масштабируются на случай нескольких целей.

Из изложенного следует, что существуют нерешенные вопросы в области повышения точности определения КПДЦ, которые могут быть устранены путем оптимизации траектории движения наблюдателя, что определяет актуальность проводимых исследований.

Цель диссертационной работы состоит в разработке методов и алгоритмов решения задач построения в режиме реального времени траектории наблюдателя, оптимизированной по точности статистических оценок координат и параметров движения одной или нескольких целей.

Основные задачи исследования. Достижение указанной цели диссертации осуществляется посредством решения следующих задач, решения которых выносятся на защиту:

1. Разработать метод построения траектории наблюдателя заданной длительности, оптимизированной по точности статистических оценок координат и параметров движения одной или нескольких целей (прямая задача).

2. Разработать метод оценки минимального времени, необходимого для получения статистических оценок координат и параметров движения одной или нескольких целей заданной точности (обратная задача).

3. Разработать алгоритмы оптимизации, предназначенные для решения в режиме реального времени прямой и обратной задач построения траектории наблюдателя, оптимизированной по точности статистических оценок координат и параметров движения цели.

Методы исследования. В диссертации применялись методы математической статистики, регрессионного анализа, планирования эксперимента, оптимального управления, генетические алгоритмы.

Достоверность и обоснованность полученных результатов обеспечивается использованием апробированных научных методов, применяемых при планировании регрессионных экспериментов, оптимизации сложных функций, робастной обработке сигналов; соблюдением в процессе моделирования необходимых и достаточных условий обеспечения адекватности разрабатываемых моделей и их отдельных фрагментов реальным процессам; непротиворечивостью результатов исследования результатам, опубликованным в рецензируемых научных периодических изданиях и полученным различными научно-исследовательскими учреждениями флота и промышленности при проведении натурных экспериментов и испытаний по точности определения КПДЦ.

Научная новизна полученных результатов.

Первый метод, в отличие от известных методов построения оптимизированной траектории наблюдателя, позволяет находить близкое к оптимальному решение по одной или нескольким целям в режиме реального времени и автоматически определяет необходимое число и длительность галсов траектории наблюдателя.

Второй метод, в отличие от известных методов оценки искомой величины, оперирует траекториями наблюдателя, близкими к оптимальным, что позволяет уточнить оценку минимального времени, необходимого для получения статистических оценок КПДЦ заданной точности. Предложенный метод является первым методом, который применим в режиме реального времени при определении КПДЦ по одной или нескольким целям.

Алгоритм оптимизации, реализующий первый метод, является генетическим алгоритмом с эмиссией интронов (Intron Emission Genetic Algorithm (IEGÁ)). Компьютерный эксперимент показал, что предложенный алгоритм позволяет сократить (по сравнению с классическим генетическим алгоритмом) число перебираемых вариантов при решении оптимизационной задачи в методе построения траектории наблюдателя заданной длительности, оптимизированной по точности статистических оценок КПДЦ. Данный алгоритм может быть использован в других задачах оптимизации дискретных по времени управляющих воздействий.

Алгоритм оптимизации, реализующий второй метод, является генетическим алгоритмом с распространением триплетов (Triplet Propagation Genetic Algorithm (TPGA)). Компьютерный эксперимент показал, что предложенный алгоритм позволяет сократить (по сравнению с классическим генетическим алгоритмом) число перебираемых вариантов при решении оптимизационной задачи в методе оценки минимального времени, необходимого для получения статистических оценок КПДЦ заданной точности. Предложенный алгоритм является первым алгоритмом, позволяющим одновременно находить траектории движения наблюдателя различной длительности, оптимизированные по точности статистических оценок КПДЦ.

Практическая полезность результатов диссертационной работы состоит в том, что они позволяют: принимать обоснованные решения и оценивать принятые решения по выбору параметров движения наблюдателя при определении координат и параметров движения одной или нескольких целей; строить в режиме реального времени оценку минимального времени, необходимого для получения оценок КПДЦ заданной точности.

Результаты работы использовались в ОАО «Концерн «НПО «Аврора» в НИР «Опти-мизация-2011» и «ИСБУ-НАШГ» (подтверждено двумя актами о реализации), а также в учебном процессе по курсу «Технологии программирования», читаемом на кафедре «Компьютерные технологии» Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики.

Апробация работы. Основные результаты диссертационной работы докладывались на научно-технических конференциях «Системный анализ при создании кораблей, вооружения и военной техники ВМФ» (СПб.: BMA им. Н.Г. Кузнецова, 2011) и «Интегрированные многофункциональные системы управления для ВМФ» (М.: ОАО Концерн «Моринформсистема-Агат», 2011), а также на конференциях молодых специалистов «Ш Всероссийский конкурс молодых ученых» (Миасс: «Межрегиональный совет по науке и технологиям», 2011) и «Корабельные системы управления и обработки информации» (СПб.: ОАО Концерн «НПО «Аврора», 2011, доклад был удостоен первого места в секции «Программное обеспечение»).

Публикации. Основные результаты работы опубликованы в семи научных трудах, в числе которых одна статья опубликована в журнале из списка ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Общий объем диссертации 132 страницы, включающих 114 страниц текста, 26 рисунков и восемь страниц приложения. Список литературы содержит 108 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертационной работы, поставлены цель и задачи исследования, решения которых выносятся на защиту.

Первая глава содержит анализ опубликованных результатов по исследуемому вопросу. Со второй половины 70-х годов прошлого века началось исследование вопроса построения оптимизированной по точности статистических оценок КПДЦ траектории наблюдателя для различных моделей совместного движения системы «наблюдатель - цель». Вопросы оптимизации

траектории наблюдателя в режиме реального времени стали рассматриваться в мире с начала 21-го века. В задачах, рассматриваемых в диссертационной работе, можно смягчить требования к скорости работы оптимизационной процедуры в предположении о том, что под работой в реальном времени будет пониматься время работы, не превышающее период обновления входной информации. Однако даже в такой постановке задача поиска оптимума, близкого к глобальному, при построении траектории наблюдателя не была решена до настоящего времени.

Алгоритмы поиска оптимизированной по точности оценок КПДЦ траектории наблюдателя сводятся к решению оптимизационных задач. Основная сложность модели, рассматриваемой в диссертационной работе, состоит в том, что оптимизационные задачи, в ней возникающие, не позволяют ее решать методами динамического программирования: оптимальная траектория наблюдателя не разбивается на последовательность оптимальных траекторий меньшей длительности. Поэтому оказываются непригодными методы пошаговой оптимизации, примененные другими исследователями. Задачи состоят в поиске глобального оптимума или близкого к глобальному оптимуму решения. Локально оптимальные решения не позволяют получить оценки КПДЦ высокого качества и дают различные результаты при одинаковых начальных данных.

Среди всех алгоритмов глобальной оптимизации наиболее подходящими оказываются так называемые популяционные алгоритмы, рассматривающие вместо одного решения целый набор (популяцию) решений, над которым определены операции отбора и изменения, формирующие следующие поколения решений, характеризуемых более высоким (при максимизации) значением оптимизируемой функции. Популяционные алгоритмы осуществляют направленный перебор решений-кандидатов, стараясь сократить число перебираемых вариантов.

Существующие методы оптимизации траектории наблюдателя разбиваются на три группы: «экспертные» (полученные экспериментально и пригодные не во всех тактических ситуациях), «аналитические» (состоящие в строгом решении оптимизационной задачи или задачи оптимального управления при определенных ограничениях) и «численные» (использующие эвристические методы оптимизации). Предлагаемые методы построения оптимальной траектории наблюдателя относится к численным методам. Основным отличием является то, что в предлагаемых методах решаются задачи глобальной оптимизации.

В первой главе показано место, которое занимают рассматриваемые задачи и предложенное автором решение в контексте современных исследований по данной теме. Ни одно из известных решений не позволяет на текущий момент сказать, что поставленная проблема уже имеет удовлетворительное решение, и поэтому выполненное исследование является актуальным.

Вторая глава описывает подход к задаче построения траектории наблюдателя, оптимизированной по точности оценок КПДЦ, как к задаче планирования регрессионного эксперимента. В диссертационной работе рассматривается задача определения КПДЦ только по затушенным измерениям пеленга.

Под точностью статистических оценок в настоящей работе понимается величина обобщенной дисперсии оценок. Качество оценок будем определять вероятностью их попадания в заранее заданную окрестность истинных значений параметров.

Оценивание КПДЦ производится одним из методов статистической обработки измерений, предоставляющих оценки коэффициентов регрессионных моделей, описывающих взаимное движение наблюдателя и цели. К основным методам построения оценок в задаче определения КПДЦ относятся метод наименьших квадратов (МНК) и обобщенный фильтр Калмана, а также их модификации. В настоящем исследовании в качестве основного метода оценивания КПДЦ был выбран метод «М-пеленгов», основанный на МЖ-оценивании параметров линейной регрессионной модели, который не требует задания априорных данных.

В классической постановке задачи определения КПДЦ предполагается, что на всем временном промежутке решения задачи (с момента 10) цель движется равномерно и прямолинейно по плоскости из начальной точки с координатами ('"л® ('о )> ('о)) со скоростью

= (у® , V® ) . Цели в каждый момент времени I сопоставляется четырехкомпонентный век--{^ШНФТ^ГГ, а наблюдателю сопоставляется вектор

тор состояния Xf,

У Ahí

По

зашумленным измерениям пеленга

П,= П( +Е, , где nt =n(/t) = arctan

y(h)j

требуется оценить компоненты вектора 0 неиз-

является иллюстрациеи к

Рис. 1. Схема совместного движения наблюдателя и цели в задаче определения КПДЦ

вестных параметров движения цели. Схема, приведенная на рис. описанию задачи определения КПДЦ но измерениям пеленга.

Оценивание вектора 0 методом «N-пеленгов» сводится к решению избыточной системы уравнений вида H9 = D, в которой элементы матрицы регрессионных коэффициентов Н зависят от измерений пеленга и тем самым, от параметров движения наблюдателя и неизвестных параметров движения цели. Таким образом, модель задачи «N-пеленгов» является моделью конфлю-энтного регрессионного анализа (учитывающего ошибки в регрессионных коэффициентах).

Использование МНК в модели конфлюэнт-ного регрессионного анализа приводит к получению смещенных оценок. Получить асимптотически несмещенные оценки можно с помощью метода ортогональных проекций, известного в англоязычной литературе как Total Least Squares, TLS. Предложенные методы оптимизации траектории наблюдателя не зависят от способа построения оценок в задаче «N-пеленгов».

Основное условие применимости методов статистической оценки КПДЦ по измерениям пеленга состоит в обеспечении наблюдаемости системы «наблюдатель - цель». Под наблюдаемостью понимается возможность однозначного восстановления параметров системы по производимым измерениям. Необходимое условие наблюдаемости в задаче определения КПДЦ состоит в выполнении наблюдателем маневра, состоящего в изменении курса и/или скорости.

Понятие наблюдаемости имеет смысл расширить, включив помимо граничных значений (система наблюдаема/не наблюдаема) также и промежуточные, описывающие различные градации «наблюдаемости». Расширенное понятие наблюдаемости напрямую связано с точностью оценок КПДЦ.

Теоретически достижимая точность несмещенных оценок определяется нижней границей неравенства Pao - Крамера cov(0)> Л/~'(0), где cov(0) - ковариационная матрица, а информационная матрица Фишера вектора оцениваемых параметров 0. Исходя из этого, информационная матрица часто выбирается как характеристика точности статистических оценок.

Информационная матрица в задаче определения КПДЦ зависит от параметров траектории движения наблюдателя. Данная зависимость может быть рассмотрена в терминах задачи планирования эксперимента, состоящей в оптимизации траектории наблюдателя с целью получения оценок КПДЦ как можно более высокой точности. Задача оптимизации траектории наблюдателя представляет собой поиск параметров движения наблюдателя, «увеличивающих» информационную матрицу (рис. 2).

Параметры движения цели

Априорное распределение

Ковариационная матрица оценок

Наблюдаемость? I

Г Г

Информационная матрица

К

Неравенство Рао-Крамера

Параметры движен наблюдателя

НС

1анирования гпвриманта

Качество оценок

Рис. 2. Планирование эксперимента в задаче определения КПДЦ

В качестве плана эксперимента предлагается рассматривать последовательность углов поворота при переходе наблюдателя с галса на галс ^(Со.-.Сд,^.,), где ЛГцл - число галсов. Возможностью маневрирования скоростью предлагается пренебречь для упрощения анализа получаемых результатов. К числу упрощений модели следует также отнести и отсутствие циркуляции при смене галса. Предлагаемые методы оптимизации траектории на-

блюдателя позволяет избавиться от данных допущений при минимальном числе игменений.

Углы поворота наблюдателя выбираются дискретно с шагом Д из интервалов С} еПс =[амш,аМАХ) * где 0<ашк <0,^ <360.

Определяется

различных углов поворота наблюдателя. Выбор

шага дискретизации А выполняется из соображений статистической различимости траекторий

Выбранные параметры движения наблюдателя !; должны, прежде всего, обеспечить строгую наблюдаемость системы. Далее, множество всех траекторий, обеспечивающих наблюдаемость, упорядочивается по точности доставляемых ими оценок, характеризуемой информационной матрицей Л/(0, ¡;).

Если бы на множестве информационных матриц можно было бы ввести отношение полного порядка, то планы эксперимента § можно было бы упорядочить, сравнивая их информационные матрицы. Однако, поскольку множество матриц является лишь частично упорядоченным, то для сравнения оценок обычно используют одномерную характеристику матрицы, например, определитель, след или минимальное собственное число. Связанные с данными характеристиками критерии оптимальности: 1. И-оптимальность - поиск экстремума функции от определителя матрицы. 2. А-оптимальность - поиск экстремума функции от следа матрицы. 3. Е-оптимальность - поиск экстремума функции от минимального собственного числа матрицы.

Оптимальность по одному из критериев не влечет оптимальности по другому критерию. В рассматриваемой задаче наиболее предпочтительным является критерий Б-

оптимальности, поскольку функция в нем автоматически обнуляется при отсутствии наблюдаемости и известны результаты, показывающие, что оптимизация траектории по другим критериям приводит к оценкам КПДЦ меньшей точности. Статистическая интерпретация критерия И-оптимальности состоит в том, что данный критерий минимизирует обобщенную дисперсию параметров 8.

Обозначим через ^(71^(9,^)) функцию выбранного критерия оптимальности. Задача планирования эксперимента состоит в поиске таких параметров движения наблюдателя с,", при которых достигается максимум функции Ф:

^ = а^тахЧ^Лф,!;)).

5

Вводится обозначение 8Га (Е,б) для функции логарифма от определителя информационной матрицы, соответствующей вектору 6, времени Т, выделенному на определение КПДЦ, средне-квадратичное отклонение (СКО) пеленга а и траектории наблюдателя \. Для 5Г 0(^,б) будем использовать обозначение 8г(с,б). Выбирая критерий О-оптимальности, определяем

Вводится обозначение (¡у для функции качества оценок, сопоставляющей времени

Г, выделенному на определение КПДЦ, СКО пеленга <т и траектории \ вероятность получения «хороших» оценок. Под «хорошими» понимаются оценки, попадающие в некоторую заранее заданную окрестность истинных значений параметров.

Прямая и обратная задачи поиска оптимальной траектории наблюдателя схематично представлены на рис. 3.

Прямая задача состоит в поиске оптимальной траектории, доставляющей (для фиксированных времени решения Т и СКО пеленга о) оценки наибольшей точности, и записывается в

виде =а^тах(й7-(^,О)). ?

Обратная задача состоит в поиске минимального времени решения Г, доставляющего (для фиксированного СКО пеленга ст) оценки заданного качества ?, и записывается в виде т т(г):?г>а(^)>9.

В диссертации прямую задачу предложено решать как задачу глобальной оптимизации. Основным недостатком выбрашюго критерия Б-оптимальности является отсутствие свойства монотонной аддитивности, что не позволяет пользоваться методами динамического программирования при поиске глобального максимума. В рассматриваемой ситуации оптимальная траектория наблюдателя не состоит из оптимальных траекторий меньшей длительности, и методы динамического программирования позволяют получить только локально оптимальные траектории.

Указанное обстоятельство очень важно для правильного понимания того, в каком смысле оптимизируются траектории наблюдателя, получаемые при решении прямой задачи: они максимизируют точность оценок на заданный конечный момент времени Ти не гарантируют максимизацию точности оценок на предшествующие моменты времени.

Выполнено сравнение глобального и локальных оптимумов с точки зрения пригодности доставляемых ими оценок КПДЦ. Делается вывод о необходимости поиска оптимума, близкого к глобальному, из-за более низкого качества оценок, доставляемых локально оптимальными траекториями.

В этой главе также выполнено обсуждение статического (использующего только априорную информацию) и последовательного (использующего динамически поступающую информацию) вариантов планирования эксперимента применительно к задаче оптимизации траектории наблюдателя. Делается замечание о возникающем в данном контексте свойстве наблюдаемости: локально оптимальные траектории часто оказываются плохо наблюдаемыми. Сделан вывод о целесообразности проведения предварительного статического планирования эксперимента, при котором оптимизация траектории наблюдателя производится по минимальному доступному набору априорных данных.

Далее приводится графическое представление функции ЬТ{Ь) выбранного критерия, иллюстрирующее сложность возникающей задачи оптимизации. Для этого траектории наблюдателя \ сопоставляется угол ф, рассчитываемый по формуле:

/ \ ^ро д

<р(с0,-,с„шН)=с0+ X

¡=1 1

Интерпретируя 8 как функцию от <р, представим график функции 8 так, как это сделано на рис. 4. Оптимальной траектории наблюдателя соответствует угол (р, в направлении которого приведенный график более всего удаляется от нуля. По мере увеличения числа рассматриваемых галсов, число локальных экстремумов будет быстро расти. Подводя итог, отметим, что оп-

оптимальной траектории наблюдателя

тимизируемая (целевая) функция многомерна, нелинейна и имеет множество локальных экс-

Решение обратной задачи в диссертации предлагается производить в два этапа. Первый из них состоит в параллельной оптимизации траекторий наблюдателя различной длительности. Второй - в расчете функции качества, отвечающей найденным оптимизированным траекториям.

Было предложено ограничиться рассмотрением трехгалсовых траекторий !;, = (с,', С^, С]) наблюдателя, поскольку функция качества не убывает при увеличении числа галсов. Рассматриваются траектории, длительности которых попадают во временной интервал [Гт;„,7'111И]. Число траекторий ЛГ51ЛСЕ определяется требованиями по точности оценок минимального времени решения.

Первый этап решения обратной задачи формулируется в виде задачи оптимизации = а^тах(бГт41 (С,б)), где векторный аргумент С, = (Е,,..., £Л,м[ ) состоит из трехгалсовых

траекторий с длительностями 7] из вышеопределенного интервала [Гтт, 7'тах ]. Целевая функция определяется следующим образом:

ММ5^ (5г, .е)-.8г_ .в))-

Результатом первого этапа является нахождение набора оптимизированных траекторий = ) различной длительности. Параллельная оптимизация траекторий позволяет

сократить время работы алгоритма, что является необходимым условием его использования в режиме реального времени.

Второй этап решения обратной задачи состоит в расчете функции качества <7у, методом Монте-Карло при пе-

реборе Г, от ТтЬ к Гти до первого превышения функционалом качества заданного уровня q (рис. 5). гя1я1 время Т- Тт т На рис. 6 приведена схема алгоритма ре-

шения задачи оптимизации траектории Рис. 5. Поиск оценки минимального времени решения наблюдателЯ; описывающая взаимосвязь

прямой и обратной задач. Прерывистыми линиями на этом рисунке отмечены переходы, устанавливающие связи между задачами.

При решении прямой задачи полученную оценку достижимого качества можно задать в качестве входного значения обратной задачи для уточнения оценки минимального времени решения. Минимальное время решения, отвечающее оцененному уровню качества, может оказаться меньше заданного в прямой задаче, поскольку качество оценок является ступенчатой функцией от времени из-за дискретизации пространства траекторий наблюдателя.

При решении обратной задачи полученную оценку времени решения можно задать в качестве входного значения прямой задачи для построения оптимизированной траектории с галсами различной длительности.

тремумов (невыпуклая).

Рис. 4. Графическое представление функции 87.(9) для трехгалсовых траекторий при шаге дискретизации угла поворота 30°

ПРЯМАЯ ЗАДАЧА

Задано арамя раш*м*я Т

Нахахд*нм« оптимальной трхчтори» 1

Оц* на* достижимого

ОБРАТНАЯ ЗАДАЧА

Задан уровень

качастаая

X

Нахожданиа набора-

тртегктин с

Оценка минимального ■романи рошония Т

Рис. 6. Схема алгоритма построения оптимальной траектории наблюдателя

Решение прямой и обратной оптимизационных задач выполняется по принципу «черного ящика» - методами, не требующими знания точного аналитического выражения целевой функции. Эта функция может быть вычислена для любого значения аргумента, но ее аналитическое выражение слишком сложно для вывода и анализа. Алгоритмы, реализующие метод «черного ящика» - вероятностные алгоритмы оптимизации. В отличие от детерминированных алгоритмов, последовательность их приближенных решений недетерминирована (изменяется от реализации к реализации, носит вероятностный характер). Инициализация таких алгоритмов обычно также осуществляется случайным образом.

Нахождение глобального экстремума невыпуклой функции сопряжено с опасностью попадания в локальные экстремумы. Предлагаемый оптимизационный алгоритм должен перебирать точки из различных областей пространства для того чтобы увеличить шансы нахождения глобального экстремума. Алгоритмы, рассматривающие только одно приближенное решение на каждом шаге, не обеспечивают должное исследование всего пространства. Для указанной цели подходят популяционные алгоритмы, рассматривающие на каждой итерации множество решений (популяцию особей), обеспечивающих представительство различных областей пространства аргументов, которое называется разнообразием. Одно из основных отличий популяционных алгоритмов от непопуляционных состоит в том, что первые используют правила построения новых приближенных решений на основе существующих, используя информацию, накопленную всей популяцией. Иными словами, в популяционных алгоритмах особи обмениваются полученной информацией, увеличивая общую эффективность работы алгоритма. Популяционные алгоритмы обычно используют идеи и терминологию, заимствованные из генетики и биологии.

Генетические алгоритмы (ГА) относятся к классу вероятностных популяционных оптимизационных алгоритмов. Векторный аргумент £, называется хромосомой, а элементы вектора \ - генами. Вектор % теперь имеет дуальную интерпретацию: с точки зрения генетического алгоритма, он является носителем генотипических свойств, важных для функционирования алгоритма, а с точки зрения решаемой задачи - носителем фенотипических свойств, характеризующих его как решение-кандидат для оптимизационной задачи. Вектор % как носитель фенотипических свойств называется особью.

Целевая функция в теории Г4 называется функцией приспособленности. Основные преимущества ГА состоят в том, что они: 1. Делают минимальное число предположений относительно пространства поиска. 2. Легко модифицируются под решение конкретных задач. 3. Пригодны для поиска глобального экстремума мультимодальной функции.

Основные этапы работы ГА включают: 1. Создание начального поколения решений-кандидатов (начальная популяция особей) - обычно задается случайным образом. 2. Сопоставление каждой особи значения, определяющего ее «приспособленность» - в случае поиска экстремума функции это значение целевой функции для данного аргумента. 3. Отбор (оператор отбора) - реализует аналог биологического естественного отбора путем отбрасывания наименее приспособленных особей по некоторому правилу. 4. Скрещивание (оператор кроссовера) -реализует аналог биологического скрещивания путем выбора родительских особей и задания правила получения потомков. 5. Мутация (оператор мутации) - реализует аналог биологиче-

ской мутации путем внесения «ошибок» в векторное представление особей по заранее определенному правилу с некоторой частотой (обычно очень небольшой).

Алгоритм продолжает работу до выполнения условий выхода, которые могут быть определены различным образом. Обычно эти условия определяются через значение функции приспособленности. Под сходимостью алгоритма можно понимать достижимость условий выхода.

Одним из условий эффективной работы ГА является обеспечение достаточного разнообразия популяции в течение всего времени работы алгоритма. Генетические операторы кроссовера и мутации играют противоположную роль по отношению к разнообразию популяции. Кроссовер сокращает разнообразие, концентрируясь на разработке какой-то области пространства аргументов. Мутация увеличивает разнообразие, добавляя в популяцию точки из других областей пространства. Таким образом, кроссовер способствует сходимости алгоритма, но может привести к локальному экстремуму. В свою очередь, мутация препятствует сходимости, но увеличивает вероятность нахождения глобального экстремума за счет исследования других областей пространства аргументов.

Глава продолжается описанием байесовского подхода к планированию эксперимента, применительно к задаче определения КПДЦ. В рассматриваемой задаче оптимальная траектория наблюдателя зависит от неизвестных параметров движения источника. Обычный способ решения данной проблемы состоит в задании априорного распределения тг(о) неизвестных параметров, которое определяется как равномерное на отрезках значений дистанции (DMm,DMAX), курса

(CmIN'^max) и скорости (^MIN'^MAxJ- При предположении о том, что скорость наблюдателя значительно меньше скорости цели и наличии оценки знака величины изменения пеленга, априорный диапазон курсов можно свести до соответствующего квадранта. Определим апостериорное среднее 5r(§)= JSr(§, б)л(0)Л. Тогда байесовский оптимальный

в

план является решением задачи Ь,' = arg max5r (Д).

Процедура построения оптимального байесовского плана может быть реализована с помощью задания конкретных точек из пространства параметров. Множество из N^i выбранных точек параметрического пространства (представляющих параметры движения «целей») было названо облаком целей. Для каждой цели / б {l,..., NCL \ записывается своя система уравнений наблюдений типа D, = //,9,. Системы уравнений наблюдений облака объединяются в общую систему наблюдений с блочно-диагональной матрицей регрессионных коэффициентов, и апостериорное среднее облака принимает вид:

5 = —ln(det(//T//))= ^5ln(det(tf f Я,)). "CL ncl M

Аналогичным образом автор предлагает включать в систему данные по нескольким целям, переходя, таким образом, к построению оптимальной траектории наблюдателя, определяющего КПДЦ по нескольким целям.

Системы реального времени требуют минимизации времени работы алгоритмов, поэтому предпочтительно заменить распределение параметров одной точкой 8 параметрического пространства - «центром масс» распределения:

9'' : I }5 r fo вЦе>Ю - 5 т fe, 9') || min.

В диссертации предложен способ нахождения «центра масс» с помощью ГА. Для этого параметрическому вектору 9 = (ДС, V) сопоставляется вектор ß, компоненты которого ß, e[0,l] определяются по формулам: ß, : D() = £>MIN + ß, • (Dmax - £>min) - Для дистанции, ß2: Cp = CMIN + ß2 • (CMAX - CMIN) - для курса и ß3 : Vp = VMm + ß-, • (KMAX - KMIN) - для скоро-

сти. Обозначим параметрический вектор 6, представленный с помощью ß через 0р, а координаты цели с параметрами 0 в момент времени t через r/I£1'(0).

Определяется функционал QT(ß)= гДе d(x,y) - расстояние

м ат

между точками х и у. Ставится оптимизационная задача ß* : QT (ß) —> min, которая решается в диссертации с помощью ГА. В качестве хромосомы используется весовой вектор ß.

Таким образом, во второй главе диссертации предложена организация планирования эксперимента в задаче построения оптимальной траектории наблюдателя, пригодная к использованию в ситуации неопределенности в режиме реального времени.

Третья глава диссертации описывает предложенные автором оптимизационные алгоритмы, предназначенные для решения прямой и обратной задач построения оптимальной по точности оценок КПДЦ траектории движения наблюдателя.

Глава начинается описанием генетического алгоритма с эмиссией нитронов, предназначенного для решения прямой задачи оптимизации.

Выбранные для целей оптимизации ГА не могут быть использованы в своей «классической» форме, описанной в работах Дж. Холланда. Это утверждение проиллюстрировано результатами имитационного моделирования оптимизации траектории наблюдателя, показывающего, что при отсутствии мутации классический алгоритм быстро сходится к локальному максимуму, характеризуемому низким значением функции приспособленности, а при наличии мутации алгоритм не сходится, продолжая переход от одного локального максимума к другому.

ГА являются алгоритмами направленного перебора. Эффективность их работы определяется тем, насколько сильно удастся сократить число перебираемых вариантов. Дж. Холлан-дом было введено понятие схемы для обозначения комбинаций генов. Функция приспособленности схемы определяется как среднее значение приспособленности всех хромосом, содержащих данную схему. Схемы, которые характеризуются малой длиной и высокой приспособленностью, называются строительными блоками. Из теоремы схем Дж. Холланда, определяющей одношаговую вероятность сохранения схемы при смене поколения, следует, что больше шансов увеличить свое представительство в следующем поколении будет у строительных блоков. На основании этого, Д. Гольдберг высказал так называемую гипотезу строительных блоков, состоящую в том, что генетические алгоритмы эффективно работают в тех задачах, в которых отбор производится не на уровне генов, а на уровне строительных блоков.

Хромосома рассматриваемой задачи - траектория наблюдателя, представленная в виде вектора 4 углов поворота. Каждый угол поворота - ген хромосомы. В случае отсутствия поворота ген принимается равным нулю. Автор назвал «нулевые гены» интронами по аналогии с биологическим термином, обозначающим некодирующий участок хромосомы. Все прочие гены, согласно той же аналогии, названы экзонами.

Траектория с галсами различной длительности может быть получена как решение задачи построения траектории, состоящей из большого числа избыточно заданных галсов, названных «элементарными». Действительно, известно, что оптимальное управление в задаче оптимизации траектории наблюдателя является двухпозиционным с чередованием углов поворота, доставляющих максимум производной пеленга. Для получения более точных оценок следует производить измерения пеленга из точек, разнесенных как можно дальше друг от друга. Таким образом, оптимальные траектории не могут быть сильно изломанными, и часть избыточно заданных галсов будет сливаться в галсы различной длительности. Отсюда следует, что высоко приспособленные хромосомы будут содержать большое число интронов. Блоки, состоящие из интронов, в диссертации было предложено рассматривать как строительные блоки алгоритма.

Поскольку одним из условий эффективной работы ГА является поддержание достаточного разнообразия в течение всего периода работы алгоритма, существенным является вопрос о выборе подходящей меры разнообразия. В диссертации была предложена мера (среднее рас-

стояние Хэмминга по популяции), построенная на базе расстояния Хэмминга, равного числу отличающихся элементов двух строк одинаковой длины. По аналогии с методом имитации отжига, интенсивность работы операторов модифицированного алгоритма была поставлена в зависимость от меры разнообразия популяции для сокращения числа выполняемых операций.

ГА был дополнен несколькими параллельно выполняемыми операциями: 1. Эмиссией интронов - искусственным добавлением интронов в хромосомы на разных этапах работы алгоритма (включая этап получения начального поколения) с интенсивностью, зависящей от меры разнообразия. 2. Выделением интронных островов (участков хромосомы, состоящих только из интронов) с помощью моделей статистической физики, интерпретирующих вероятность расположения интронов и экзонов в терминах энергетического состояния системы, описываемого распределением Максвелла - Больцмана. 3. Применением операторов локального перебора, работающих только на экзонных островах (участках хромосомы, состоящих из экзонов).

Для увеличения скорости сходимости алгоритма были изменены основные генетические операторы скрещивания и мутации. Модифицированный оператор скрещивания с частотой, зависящей от меры разнообразия популяции, заменяется оператором эмиссии интронов. Частота модифицированного оператора мутации зависит от меры разнообразия популяции и определяет новое значение мутантного гена согласно эмпирическому распределению частот генов по популяции. Результаты работы модифицированных генетических операторов принимаются только в случае увеличения приспособленности хромосомы после внесенных изменений (по аналогии с методом случайного восхождения).

С целью сохранения полученных строительных блоков в модифицированном алгоритме использовался одноточечный вариант кроссовера, при котором родительские хромосомы «рвутся» в одной случайно выбранной точке. Пары родителей для скрещивания выбирались по правилу вожака стада (heard leader breeding), согласно которому наилучшая особь составляет пары со всеми остальными. Для обеспечения высокого разнообразия алгоритм был реализован как островной: задавалось некоторое число параллельно развивающихся популяций. В случае вырождения популяции (обращения в ноль меры разнообразия популяции) на острове с не самой высокой приспособленностью остров очищался, на него переносились строительные блоки с острова с наилучшей популяцией и процесс поиска решения на острове перезапускался. Условие выхода модифицированного алгоритма было определено как вырождение популяции на острове с наилучшей функцией приспособленности.

Предложенный модифицированный генетический алгоритм был назван автором генетическим алгоритмом с эмиссией интронов (IEGA).

Сравнение работы классического ГА (без мутации и с частотой мутации 0,05) для случая построения оптимизированной траектории на множестве траекторий, состоящих из 20 «элементарных» галсов, приведено в таблице.

Таблица. Сравнение результатов работы ГА и IEGA

Алгоритм Среднее число галсов Среднее расстояние Хэмминга Среднее число поколений Среднее время выполнения, с 6 СКО(6)

ГА (без мутации) 18 18,02 10 0,80 19,92 0,24

ГА (частота мутации 0.05) 17 16,84 100 11,00 20,71 0,10

IEGA 4 2,62 21 26,00 21,08 0,03

По результатам сравнения алгоритмов можно сделать следующие выводы: 1. ІЕСА находит оптимизированные траектории со значительно меньшим числом галсов, чем классический ГА. 2. Разброс числа различных решений ¡ЕвА ниже, чем у классического варианта ГА. 3. ¡ЕйА требуется для сходимости в среднем больше поколений, чем ГА без мутации (ГА с мутацией не сходится за обозримое число поколений). А. Среднее время выполнения ]ЕСА выше,

21,50 X 21,00

5і С 19,50

її С 19,00

САбеі мутации .б.А.МутдаИЯ.0,0.5. - IEGA

1 3 5 7 9 11 13 15 17 19 21 23 25 27 НОМЕР ПОКОЛЕНИЯ

чем у ГА. 5. Значение функции приспособленности особей 1EGA выше, чем у ГА. 6. Разброс значений функции приспособленности особей 1EGA ниже, чем у ГА.

Как видно из графиков на рис. 7, функция приспособленности IEGA выше, чем у классического алгоритма уже в начальном поколении. Это происходит за счет искусственного добавления интронов в хромосомы модифицированного алгоритма.

Как показало компьютерное моделирование, предложенный алгоритм IEGA существенным образом сокращает число Рис. 7. Графики функций приспособленности класси- перебираемых вариантов решения и, соот-ческого и модифицированного ГА ветственно, время работы алгоритма. Это

позволяет использовать данный алгоритм в системах реального времени.

Глава продолжается описанием предложенного автором генетического алгоритма с распространением триплетов, предназначенного для решения обратной задачи. В диссертации было предложено использовать ГА для решения поставленной оптимизационной задачи.

В диссертации высказана гипотеза, состоящая в том, что близкие по длительности решения задачи определения КПДЦ траектории будут либо совпадать, либо будут близки.

Данная идея схематично изображена на рис. 8. Высказанная гипотеза наводит на мысль о том, как могут быть устроены строительные блоки генетического алгоритма рассматриваемой задачи. Под строительными блоками хромосомы С, будем понимать триплеты !;,- = {с1,С2,С^).

Вторая идея предлагаемого алгоритма состоит в том, чтобы заменить многомерную функцию приспособленности на одномерную. Идея базируется на том, что большему времени решения задачи определения КПДЦ соответствует большее значение логарифма от определителя информационной матрицы: 8Г. 6Г (jjj.) при Tt>Tj. Определим число инверсий

Inv(i^) как число пар триплетов с Т: >Tj и 8Т, (¡^ )< ). Максимальное значение числа

инверсий InvMAX(i^) равно Nslice (A'slice —1)/2. Заменим многомерную функцию приспособленности 5Г . у fe,0) функцией

Л

Рис. 8. Иллюстрация идеи решения обратной задачи

"SLICE /

Зг-л.(С.е) = 5А fe;)I Aw '(1 -InvfeVlnvMAxfe)).

Для осуществления отбора на уровне строительных блоков был введен оператор распространения триплетов, который копирует триплет в соседнее место, в случае увеличения

ii н» / + 1, [5Т. fe)>57 fo+1)) функции приспособленности триплета: ТР(/, i + 1)=- "

г + Ь

(8г, few )>8Г( fe,))

, где j і—^ к

- операция копирования триплета из временного среза _/ во временной срез к .

Мера разнообразия популяции и оператор мутации в данном алгоритме были устроены как в генетическом алгоритме с эмиссией интронов. Был выбран одноточечный оператор крос-

совера. Вероятность выбора в качестве точки кроссовера границы триплетов увеличивалась по мере снижения меры разнообразия, во избежание разрушения строительных блоков.

Предложенная модификация генетического алгоритма была названа в диссертации генетическим алгоритмом с распространением триплетов (ТРвЛ). С помощью ТРСА предлагается производить параллельную оптимизацию траекторий различной длительности.

Четвертая глава диссертационной работы содержит результаты имитационного моделирования, иллюстрирующие работу предложенных алгоритмов.

Было экспериментально показано, что двугалсовые траектории доставляют оценки значительно худшего качества, а переход к числу галсов большему трех не приводит к существенному улучшению оценок КПДЦ.

Получающиеся в результате использования метода решения прямой задачи траектории наблюдателя представляют собой (при больших начальных дистанциях до цели) последовательность галсов, почти перпендикулярных начальному пеленгу. Данный результат согласуется с результатами аналитических методов построения траекторий.

Имитационное моделирование показало, что при достаточно широких диапазонах априорных данных байесовский подход позволяет построить траекторию наблюдателя, не сильно проигрывающую по точности оценок КПДЦ траектории, оптимизированной для точно заданных параметров движения цели, взятых из облака целей.

Приведены результаты расчета КПДЦ по двум целям одновременно, показывающие, что траектория наблюдателя, оптимизированная для оценки параметров двух целей, предпочтительнее траектории, оптимизированной для оценки параметров одной из целей, по критерию усредненной точности оценок параметров обеих целей.

В ходе имитационного моделирования методом решения обратной задачи были получены оценки времени, необходимого для получения КПДЦ заданного качества, согласующиеся с экспертными оценками специалистов, участвовавших в ходовых испытаниях.

Среднее время работы алгоритмов, реализующих методы решения прямой и обратной задач, не превысило длительность временного интервала между получением входящих измерений пеленга в широком диапазоне практически интересных значений параметров.

Проведенное моделирование иллюстрирует повышение точности определения КПДЦ при переходе к оптимизированному движению наблюдателя и возможность применения предложенных алгоритмов в системах реального времени.

ЗАКЛЮЧЕНИЕ

Основные результаты диссертационного исследования состоят в следующем.

1. Разработан метод построения траектории наблюдателя заданной длительности, оптимизированной по точности статистических оценок координат и параметров движения одной или нескольких целей (прямая задача).

2. Разработан метод оценки минимального времени, необходимого для получения статистических оценок координат и параметров движения одной или нескольких целей заданной точности (обратная задача).

3. Разработаны алгоритмы решения (в режиме реального времени) прямой и обратной задач построения оптимизированной траектории наблюдателя: генетический алгоритм с эмиссией интронов и генетический алгоритм с распространением триплетов.

Предложенные алгоритмы оптимизации могут быть использованы также в задачах оптимального управления с дискретным по времени управляющим воздействием.

На основании полученных результатов можно утверждать, что в диссертации решена научная задача - разработаны новые методы и алгоритмы решения задач построения в режиме реального времени оптимизированной траектории наблюдателя, обеспечивающей повышение точности определения КПДЦ по одной или нескольким целям.

Содержание работы отражено в следующих публикациях

1. Беляев Б. Л., Панкратьев В. В., Степанов Д. В. Использование метода ортогональных проекций в задаче «N-пеленгов» // Системы управления и обработки информации. 2011. Вып. 22, с. 56-64.

2. Степанов Д. В. Построение несмещенных оценок координат и параметров движения цели в задаче «N-пеленгов» методом ортогональных проекций ^Системный анализ при создании кораблей, вооружения и военной техники: тематический сборник. 2011. Вып. 22, с. 72 - 77.

3. Беляев Б. Л., Кузьменко Ю. А., Панкратьев В. В., Степанов Д. В. Об ожидаемом качестве оценок определения координат и параметров движения цели методом «N-пеленгов» при выбранном варианте собственного маневрирования / Сборник докладов научно-технической конференции «Состояние, проблемы и перспективы создания корабельных информационно-управляющих комплексов» М.: 2011, с. 97-101.

4. Степанов Д. В. Использование генетического алгоритма для нахождения оптимального маневра в задаче «N-пеленгов» / Итоги диссертационных исследований. Том I. Материалы 111 Всероссийского конкурса молодых ученых. М.: РАН, 2011, с. 214 -224. Входил в перечень ВАК.

5. Степанов Д. В. Использование генетического алгоритма для построения оптимальной траектории наблюдателя в задаче «N-пеленгов» / Сборник тезисов докладов научно-технической конференции молодых специалистов «Корабельные системы управления и обработки информации». СПб.: 2011, с. 62, 63.

6. Беляев Б. Л., Гаврилов А. Ф., Кузьменко Ю. А., Панкратьев В. В., Степанов Д. В. О связи между собственным маневрированием и качеством оценок координат и параметров движения цели // Морская радиоэлектроника. 2011. № 4, с. 32-35. Входил в перечень ВАК.

7. Степанов Д. В., Шалыто А. А. Использование генетического алгоритма для нахождения оптимальной траектории наблюдателя // Научно-технический вестник информационных технологий, механики и оптики. 2012, № 1, с. 90 - 95. Входит в перечень ВАК.

Личный вклад автора. В работах, опубликованных в соавторстве, личный вклад соискателя кратко характеризуется следующим образом. В работе [1] Д. В. Степанову принадлежит представление модели метода «N-пеленгов» как модели «ошибок в переменных» и обоснование применимости метода Total Least Squares для оценки параметров модели. В [2, 6] Д. В. Степановым для ранжирования траекторий наблюдателя по критерию качества была предложена функция сравнения и получены оценки параметров линейной модели, аппроксимирующей предложенную функцию. В [7] для оптимизации траектории движения наблюдателя Д. В. Степановым была предложена модификация генетических алгоритмов (IEGA).

Подписано в печать 21.03.2012. Формат 60 X 84/16. Бумага офсетная. Печать цифровая. Объем 1,0 печ. л. Тираж 100 экз. Заказ № 13/03

Отпечатано в типографии «Фалкон Принт» (197101, г. Санкт-Петербург, ул. Большая Пушкарская, д. 54, офис 2)

61 12-5/2647

ОАО «Концерн «НПО «Аврора»

Степанов Денис Вячеславович

МЕТОДЫ И АЛГОРИТМЫ ОПТИМИЗАЦИИ ТРАЕКТОРИИ НАБЛЮДАТЕЛЯ В ЗАДАЧЕ ОПРЕДЕЛЕНИЯ КООРДИНАТ И ПАРАМЕТРОВ ДВИЖЕНИЯ ЦЕЛИ

Специальность 05.13.01. «Системный анализ, управление и обработка

информации» (судостроение)

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель -доктор технических наук, профессор А. А. Шалыто

Санкт Петербург 2012

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ....................................................................................................................................4

ГЛАВА 1. ОПТИМИЗАЦИЯ ТРАЕКТОРИИ НАБЛЮДАТЕЛЯ В ЗАДАЧЕ ОПРЕДЕЛЕНИЯ КООРДИНАТ И ПАРАМЕТРОВ ДВИЖЕНИЯ ЦЕЛИ. ИСТОРИЯ ВОПРОСА И ЦЕЛЬ ИССЛЕДОВАНИЯ......................................................................................................................Ю

1.1. Общее описание задачи определения КПДЦ...............................................................10

1.2. Методы построения оценок в задаче определения КПДЦ..........................................11

1.3. Наблюдаемость в задаче определения КПДЦ..............................................................13

1.4. Планирование эксперимента в задаче определения КПДЦ.........................................15

1.5. Целевая функция и функция качества..........................................................................17

1.6. Критерии оптимальности, связанные с характеристиками информационной матрицы Фишера.................................................................................................................................18

1.7. Методы оптимизации в задаче определения КПДЦ....................................................20

1.8. Генетические алгоритмы..............................................................................................22

1.9. Цель исследования........................................................................................................24

Выводы по главе 1...............................................................................................................24

ГЛАВА 2. ОПТИМИЗАЦИЯ ТРАЕКТОРИИ НАБЛЮДАТЕЛЯ КАК ЗАДАЧА ПЛАНИРОВАНИЯ ЭКСПЕРИМЕНТА.....................................................................................25

2.1. Задача определения КПДЦ по измерениям пеленга............................................................25

2.1.1. Постановка задачи определения КПДЦ по измерениям пеленга.............................26

2.1.2. Информационная матрица Фишера в задаче определения КПДЦ...........................29

2.1.3. Наблюдаемость в задаче определения КПДЦ...........................................................31

2.1.4. Метод определения КПДЦ «N-пеленгов».................................................................33

2.2. Оптимизация траектории наблюдателя в задаче определения КПДЦ................................36

2.2.1. Критерии оптимальности, связанные с информационной матрицей Фишера.........37

2.2.2. Методы оптимизации траектории наблюдателя в задаче определения КПДЦ........39

2.2.3. Требования, предъявляемые к методам оптимизации траектории наблюдателя в задаче определения КПДЦ..................................................................................................43

2.3. Планирование эксперимента в задаче определения КПДЦ................................................44

2.3.1. Последовательное и статическое планирование эксперимента...............................44

2.3.2. Задачи планирования эксперимента..........................................................................45

2.3.3. Параметризация траектории наблюдателя................................................................47

2.3.4. Целевая функция........................................................................................................50

2.3.5. Функция качества.......................................................................................................54

2.3.6. Прямая и обратная задачи оптимизации траектории наблюдателя.........................57

2.3.7. Применение генетических алгоритмов в задаче оптимизации траектории наблюдателя.........................................................................................................................60

2.3.8. Байесовский подход к задаче оптимизации траектории наблюдателя....................63

2.3.9. Метод решения прямой задачи..................................................................................66

2.3.10. Метод решения обратной задачи.............................................................................67

Выводы по главе 2...............................................................................................................70

ГЛАВА 3. ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В ЗАДАЧЕ ОПТИМИЗАЦИИ

ТРАЕКТОРИИ НАБЛЮДАТЕЛЯ..............................................................................................71

3.1. Решение прямой задачи с помощью генетического алгоритма с эмиссией интронов (IEGA)...........................................................................................................................................71

3.1.1. Классический ГА и гипотеза строительных блоков..................................................72

3.1.2. Применение классического ГА в прямой задаче.......................................................75

3.1.3. Мера разнообразия популяции..................................................................................79

3.1.4. Интроны и экзоны......................................................................................................80

3.1.5. Выделение интронных островов...............................................................................82

3.1.6. Операторы локального перебора на экзонных островах..........................................86

3.1.7. Модифицированный оператор мутации....................................................................86

3.1.8. Модифицированный оператор рекомбинации..........................................................87

3.1.9. Генетический алгоритм с эмиссией интронов (.ШСА)..............................................90

3.1.10. Результаты моделирования: сравнение СЛ и ДХМ................................................91

3.2. Решение обратной задачи с помощью генетического алгоритма с распространением триплетов (ТРОА)........................................................................................................................95

3.2.1. Задание хромосомы алгоритма..................................................................................96

3.2.2. Функция приспособленности алгоритма............................ .......................................97

3.2.3. Оператор распространения триплетов......................................................................98

3.2.4. Операторы мутации и скрещивания..........................................................................98

3.2.5. Генетический алгоритм с распространением триплетов (ТРОА).............................98

3.2.6. Пример использования ТРОА при решении обратной задачи..................................99

3.3. Варианты обобщения и замечания относительно предложенных алгоритмов................100

Выводы по главе 3.............................................................................................................102

ГЛАВА 4. РЕЗУЛЬТАТЫ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ.................................103

4.1. Сравнение двух- и трехгалсовых траекторий по критерию точности оценок КПДЦ......103

4.2. Определение КПДЦ с помощью оптимизированной траектории наблюдателя (одна цель) ....................................................................................................................................................106

4.3. Определение КПДЦ с помощью оптимизированной траектории наблюдателя (две цели)

.......................................................................................109

4.4. Построение зависимости времени решения задачи определения КПДЦ от СКО

пеленгования..............................................................................................................................Ш

Выводы по главе 4.............................................................................................................ИЗ

ЗАКЛЮЧЕНИЕ.........................................................................................................................114

ПРИЛОЖЕНИЕ. Применение метода ортогональных проекций (МОП) для оценки КПДЦ

методом «]Ч[-пеленгов»..............................................................................................................115

СПИСОК ЛИТЕРАТУРЫ.........................................................................................................123

ВВЕДЕНИЕ

Актуальность. В диссертации рассматривается задача совершенствования методов построения траектории наблюдателя, оптимизированной по точности статистических оценок координат и параметров движения цели (КПДЦ). Задача определения КПДЦ возникает в различных областях техники, связанных с вопросами акустической и оптической навигации, позиционирования и оценки параметров движущихся объектов. Задача состоит в построении наблюдателем статистических оценок координат и параметров движения объекта наблюдения («цели»). Объем накопленной информации об оцениваемых параметрах характеризуется информационной матрицей Фишера, которая в задаче определения КПДЦ зависит от траектории движения наблюдателя. Данная зависимость может быть рассмотрена в терминах задачи планирования эксперимента, состоящей в оптимизации траектории движения наблюдателя по критерию точности статистических оценок КПДЦ. Задача оптимизации траектории наблюдателя представляет собой поиск параметров движения наблюдателя, доставляющих экстремум функции от информационной матрицы.

Диссертационная работа посвящена рассмотрению задачи оптимизации траектории наблюдателя применительно к оценке параметров движения морских целей только по измерениям пеленга (в пассивном режиме).

Анализ существующих рекомендаций по маневрированию и методов построения траектории наблюдателя при определении КПДЦ показал, что они обладают следующими недостатками: не доставляют оценки КПДЦ приемлемой точности; делают ограничительные предположения относительно параметров движения цели; не позволяют получать решение в режиме реального времени; предполагают частое маневрирование; сложно масштабируются на случай нескольких целей.

Из изложенного следует, что существуют нерешенные вопросы в области повышения точности определения КПДЦ, которые могут быть устранены путем

оптимизации траектории движения наблюдателя, что определяет актуальность проводимых исследований.

Цель диссертационной работы состоит в разработке методов и алгоритмов решения задач построения в режиме реального времени траектории наблюдателя, оптимизированной по точности статистических оценок координат и параметров движения одной или нескольких целей.

Основные задачи исследования. Достижение указанной цели диссертации осуществляется посредством решения следующих задач, решения которых выносятся на защиту:

1. Разработать метод построения траектории наблюдателя заданной длительности, оптимизированной по точности статистических оценок координат и параметров движения одной или нескольких целей {прямая задача).

2. Разработать метод оценки минимального времени, необходимого для получения статистических оценок координат и параметров движения одной или нескольких целей заданной точности {обратная задача).

3. Разработать алгоритмы оптимизации, предназначенные для решения в режиме реального времени прямой и обратной задач построения траектории наблюдателя, оптимизированной по точности статистических оценок координат и параметров движения цели.

Методы исследования. В диссертации применялись методы математической статистики, регрессионного анализа, планирования эксперимента, оптимального управления, генетические алгоритмы.

Достоверность и обоснованность полученных результатов обеспечивается использованием апробированных научных методов, применяемых при планировании регрессионных экспериментов, оптимизации сложных функций, робастной обработке сигналов; соблюдением в процессе моделирования необходимых и достаточных условий обеспечения адекватности разрабатываемых моделей и их отдельных фрагментов реальным процессам; непротиворечивостью результатов исследования результатам, опубликованным в рецензируе-

мых научных периодических изданиях и полученным различными научно-исследовательскими учреждениями флота и промышленности при проведении натурных экспериментов и испытаний по точности определения КПДЦ.

Научная новизна полученных результатов.

Первый метод, в отличие от известных методов построения оптимизированной траектории наблюдателя, позволяет находить близкое к оптимальному решение по одной или нескольким целям в режиме реального времени и автоматически определяет необходимое число и длительность галсов траектории наблюдателя.

Второй метод, в отличие от известных методов оценки искомой величины, оперирует траекториями наблюдателя, близкими к оптимальным, что позволяет уточнить оценку минимального времени, необходимого для получения статистических оценок КПДЦ заданной точности. Предложенный метод является первым методом, применимым в режиме реального времени при определении КПДЦ по одной или нескольким целям.

Алгоритм оптимизации, реализующий первый метод, является генетическим алгоритмом с эмиссией интронов (Intron Emission Genetic Algorithm, IEGA). Компьютерный эксперимент показал, что предложенный алгоритм позволяет сократить (по сравнению с классическим генетическим алгоритмом) число перебираемых вариантов при решении оптимизационной задачи в методе построения траектории наблюдателя заданной длительности, оптимизированной по точности статистических оценок КПДЦ. Данный алгоритм может быть использован в других задачах оптимизации дискретных по времени управляющих воздействий.

Алгоритм оптимизации, реализующий второй метод, является генетическим алгоритмом с распространением триплетов {Triplet Propagation Genetic Algorithm, TPGA). Компьютерный эксперимент показал, что предложенный алгоритм позволяет сократить (по сравнению с классическим генетическим алгоритмом) число перебираемых вариантов при решении оп-

тимизационной задачи в методе оценки минимального времени, необходимого для получения статистических оценок КПДЦ заданной точности. Предложенный алгоритм является первым алгоритмом, позволяющим одновременно находить оптимальные по точности статистических оценок КПДЦ траектории движения наблюдателя различной длительности.

Практическая полезность результатов диссертационной работы состоит в том, что они позволяют: принимать обоснованные решения и оценивать принятые решения по выбору параметров движения наблюдателя при определении координат и параметров движения одной или нескольких целей; строить в режиме реального времени оценку минимального времени, необходимого для получения оценок КПДЦ заданной точности.

Результаты работы использовались в ОАО «Концерн «НПО «Аврора» в НИР «0птимизация-2011» и «ИСБУ-НАПЛ» (подтверждено двумя актами о реализации), а также в учебном процессе по курсу «Технологии программирования», читаемом на кафедре «Компьютерные технологии» Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики.

Апробация работы. Основные результаты диссертационной работы докладывались на научно-технических конференциях «Системный анализ при создании кораблей, вооружения и военной техники ВМФ» (СПб.: BMA им. Н.Г. Кузнецова, 2011) и «Интегрированные многофункциональные системы управления для ВМФ» (М.: Концерн «Моринформсистема-Агат», 2011), а также на конференциях молодых специалистов «III Всероссийский конкурс молодых ученых» (Миасс: «Межрегиональный совет по науке и технологиям», 2011) и «Корабельные системы управления и обработки информации» (СПб.: ОАО Концерн «НПО «Аврора», 2011, доклад был удостоен первого места в секции «Программное обеспечение»).

Публикации. Основные результаты работы опубликованы в семи научных трудах, в числе которых одна статья опубликована в журнале из списка ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и одного приложения. Общий объем диссертации 132 страницы, включающих 114 страниц текста, 26 рисунков и восемь страниц приложения. Список литературы содержит 108 наименований.

Первая глава настоящей работы посвящена обзору и анализу существующих результатов по исследуемому вопросу. В первой главе показано место, которые занимают рассматриваемые задачи и предложенное в диссертации их решение в контексте современных исследований по данной теме.

Во второй главе диссертационной работы оптимизация траектории наблюдателя рассматривается как задача планирования эксперимента. Предлагается разбить траекторию наблюдателя на большое число равных по длительности интервалов. В качестве плана эксперимента предлагается рассматривать вектор углов поворота траектории наблюдателя в начальных точках определенных выше временных интервалов. Дается постановка прямой и обратной задач оптимизации траектории наблюдателя и описание методов их решения, как задач глобальной оптимизации в режиме реального времени.

В третьей главе диссертации приводится описание алгоритмов оптимизации, предложенных для решения прямой и обратной задач в режиме реального времени. Предложенные алгоритмы представляют собой модификации генетических алгоритмов, сокращающие (по сравнению с классическим генетическим алгоритмом) перебор вариантов решений за счет реализации идеи гипотезы строительных блоков применительно к решаемым задачам оптимизации. Делается вывод о применимости данных алгоритмов для решения задач оптимального управления с дискретным по времени управляющим воздействием.

Четвертая глава посвящена описанию и анализу результатов имитационного моделирования, иллюстрирующих работу предложенных методов и алгоритмов решения прямой и обратной задач оптимизации траектории наблюдателя в задаче определения КПДЦ.

Благодарности. Автор хотел бы отметить, что без всесторонней и многообразной помощи многих людей данная работа не смогла бы состояться.

Автор благодарен научному руководителю докт. техн. наук, проф.

A. А. Шалыто - за указание направления поиска решения задачи; коллегам по работе в ОАО «Концерн «НПО «Аврора»: непосредственным руководителям, канд. техн. наук Н. М. Киваеву, канд. техн. наук А. Ф. Гаврилову и канд. техн. наук В. О. Михайлову - за создание условий, способствовавших проведению работы, Б. Л. Бел�