Содержание к диссертации
Введение
Глава 1. Задача размещения измерительных средств: аналитический обзор 10
1.1. Задача размещения. Общие положения 10
1.2. Структурная оптимизация измерительных систем 12
1.2.1. Линейные динамические системы 12
1.2.2. Статические модели наблюдений 18
1.3. Планирование процесса наблюдения в динамических системах . 24
Выводы 31
Глава 2. Модели оптимизации размещения оптических измерителей . 33
2.1. Линейная динамическая модель оптических траекторных измерений 33
2.1.1. Элементы теории фильтрации Кал мана для оптических траекторных измерений 33
2.1.2. Оптимальное планирование измерений в динамической модели 43
2.2. Статическая модель оптических измерений 50
2.2.1. Ориентирование кадра 50
2.2.2. Оптимальное планирование оптических измерений в статической модели 52
Выводы 58
Глава 3. Алгоритмы оптимального размещения оптических измерителей 60
3.1. Алгоритмы оптимального размещения оптических измерителей в динамической модели наблюдени 60
3.1.1. Алгоритм ветвей и границ 60
3.1.2. Генетический алгоритм 62
3.1.3. Гибридный эволюционный алгоритм 74
3.2. Генетический алгоритм размещения измерителей в статической модели наблюдений 76
Выводы 78
Глава 4. Прикладные задачи оптимального размещения оптических измерительных средств 79
4.1. Планирование сеанса впешнетраекторных измерений 79
4.1.1. Постановка задачи 79
4.1.2. Размещение оптических измерительных средств следящего типа 83
4.1.3. Размещение оптических измерительных средств обзорного типа 87
4.1.4. Оптимальная доустановка измерительных средств 89
4.1.5. Оптимизация перекрытия интервалов видимости 91
4.2. Планирование оптических измерений на заключительных участках траекторий 95
4.2.1. Постановка задачи 96
4.2.2. Размещение измерительных средств без территориальных ограничений 99
4.2.3. Размещение измерительных средств с территориальными ограничениями 100
Выводы 101
Глава 5. Программная реализация алгоритмов планирования . 102
5.1. Общее описание программной реализации 102
5.2. Пользовательский интерфейс 103
5.2.1. Визуализация сеанса внешнетраекторных измерений 103
5.2.2. Размещение ОИС в динамической модели наблюдений . 104
5.2.3. Оптимизация расписания измерений ОИС 110
5.2.4. Расчет значений критериев точности для текущей модели сеанса измерений 112
5.2.5. Оптимальное планирование наблюдения объекта на заключительном участке траектории 113
5.3. Типовые сценарии планирования оптических траекторных измерений 115
Выводы 119
Заключение 120
Список литературы 122
- Планирование процесса наблюдения в динамических системах
- Генетический алгоритм размещения измерителей в статической модели наблюдений
- Размещение оптических измерительных средств обзорного типа
- Оптимальное планирование наблюдения объекта на заключительном участке траектории
Введение к работе
Актуальность. Подготовка и проведение траєкторних измерений является сложной и рес>рсоемкой задачей Это делает актуальной проблему планирования измерительного эксперимента, целями которого являются рационализация затрат па проведение измерений и повышение точности оценивания параметров объекта наблюдения В связи с этим существует потребность в разработке методов и алгоритмов планирования траєкторних измерений, которые бы упрощали этот процесс и придавали решению о выборе того или иного плана эксперимента большую достоверность
Широкий класс задач планирования траекторных измерений составляют задачи оптимального размещения измерительных средств или пространственной оптимизации измерительной системы Несмотря на большое количество исследований в этой области, многие специфические задачи размещения измерительных средств остаются неизученными Так, недостаточно исследованы задачи размещения оптических измерительных средств, которые обладают рядом затрудняющих их решение характеристик
Специфика задачи оптимизации размещения оптических измерительных средств в динамической модели заключается, в частности, в необходимости как выбора точек установки, так и наведения измерительных средств с целью наблюдения движущегося объекта на некотором временном интервале Таким образом, размещение оптических измерительных средств подразумевает также решение задачи, известной как планирование расписания измерений
Другой недостаточно исследованной, но имеющей важное практическое значение задачей является задача размещения неоткалиброванных оптических измерителей в статической модели наблюдений Особенностью этой задачи является применение опорных ориентиров, используемых при расчете пространственных координат объекта наблюдения Это приводит, помимо усложнения расчета точности оценивания параметров объекта, к проблеме размещения ориентиров в поле зрения измерительных средств
Представленные задачи характеризуются большой размерностью, многоэкстре-мальностыо, наличием плохо формализуемых ограничений, что препятствует применению аналитических и классических численных методов оптимизации Для решения подобных задач в областях, смежных с рассматриваемой, с успехом применяются точные и приближенные эвристические методы оптимизации различного рода Это позволяет сделать вывод о целесообразности применения таких методов к решению задач оптимального размещения оптических измерительных средств
Таким образом, актуальность исследования задач оптимизации размещения оптических измерительных средств для проведения траекторных измерений определяется, с одной стороны, необходимостью автоматизации этого процесса, а с другой - возможностью их эффективного решения с помощью эвристических методов
Цель работы и задачи исследования. Целью работы является разработка методов и алгоритмов оптимального размещения оптических измерительных средств в различных моделях траекторных измерений
Исследовательские задачи, решаемые в диссертационной работе для достижения поставленной цели
1 Разработка моделей оптимального размещения оптических измерительных средств
Разработка критериев оптимальности размещения оптических измерительных средств
Разработка алгоритмов планирования траєкторних измерений, исследование их эффективности
Реализация программных средств планирования траекторных измерений
Решение прикладных задач планирования оптических траекторных измерений
Предметом исследования являются динамические и статические модели оптических траекторных измерений
Методы исследований В работе использованы методы оптимизации, теории вероятностей, теории оптимального планирования эксперимента, теории стохастического управления и аналитической фотограмметрии
Научные положения, выносимые на защиту
Критерии оптимальности размещения измерительных средств
Алгоритмы оптимизации размещения оптических измерительных средств в линейной динамической модели наблюдения
Алгоритмы оптимального размещения оптических измерительных средств в статической модели наблюдения
Научную новизну составляют следующие результаты
Критерии оптимальности планирования измерений в линейной динамической модели, основанные на усеченном неравенстве Рао-Крамера и обобщенном обращении информационной матрицы Фишера
Подход к формированию критерия оптимальности размещения измерительных средств, учитывающий точность оценивания траекторных параметров и стоимость измерительного комплекса
D-оптимальные размещения оптических измерительных средств в симметричной модели наблюдений
Аналитические выражения для частных производных угловых координат по элементам ориентирования кадра
Алгоритмы оптимизации размещения измерительных средств в широком смысле, связанного с определением пространственной и временной структуры измерений
Метод адаптации параметров генетических алгоритмов, основанный на совместном учете меры разнообразия и значений целевой функции в популяции
Практическая значимость работы заключается в возможности применения предложенных критериев и алгоритмов при планировании реальных комплексов траекторных измерений
Достоверность результатов исследования подтверждается корректным использованием математического аппарата и результатами экспериментальных исследований на тестовых моделях
Внедрение результатов работы Результаты работы внедрены в ОАО "НИЦ СПбЭТУ" (Санкт-Петербург) при проведении НИР "Исследование топологии и номенклатуры средств обеспечения испытаний и их расположения на типовом полигоне МО РФ для верификации испытываемого перспективного вооружения и военной техники",
шифр "Шаутбенахт", а также в учебный процесс кафедры "Математическое обеспечение и применение ЭВМ" СПбГЭТУ "ЛЭТИ"
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях
XI Международная научно-техническая конференция студентов и аспирантов "Радиотехника, электротехника и энергетика"(Москва, МЭИ(ТУ), 2005),
XV Международная научно-техническая конференция "Математические методы и информационные технологии,в экономике, социологии и образовании"(Пенза, ПГТА, 2005),
VIII Международная конференция по мягким вычислениям и измерениям SCM '2005 (Санкт-Петербург, СПбГЭТУ "ЛЭТИ", 2005),
V Всероссийская конференция "Финансово-актуарная математика и смежные вопросы" ФАМ '2006 (Красноярск, 2006),
IX Международная конференция по мягким вычислениям и измерениям SCM '2006 (Санкт-Петербург, СПбГЭТУ "ЛЭТИ", 2006),
Межвузовский конкурс-конференция "Технологии Microsoft в теория и практике программирования "(Санкт - Петербург, СПбГПУ, 2007),
VI Всероссийская конференция "Финансово - актуарная математика и смежные вопросы" ФАМ '2007 (Красноярск, 2007),
X Международная конференция по мягким вычислениям и измерениям SCM '2007 (Санкт-Петербург, СПбГЭТУ "ЛЭТИ", 2007),
- VII Всероссийская конференция "Финансово-актуарная математика и смежные
вопросы" ФАМ '2008 (Красноярск, 2008)
Публикации. По теме диссертации опубликовано 11 научных работ, из них 6 статей (1 статья опубликована в научном издании, определенном ВАК), 5 докладов в трудах международных и всероссийских конференций
Структура и объём диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы, включающего 145 наименований, и шести приложений Основная часть работы изложена па 121 странице машинописного текста Работа содержит 41 рисунок и 16 таблиц
Планирование процесса наблюдения в динамических системах
Ковариационная матрица оценки координат наблюдаемых точек рассчитывается в соответствии с выражением где Ар - ковариационная матрица определения картинных координат изображений точек. В качестве критерия оптимальности используются следующие функционалы от Лр: 1) Е -критерий Лтах(Лр) — max; 2) А-критерий trAp — max; 3) максимальный диагональный элемент Лрй — тах і.з В работе [131] также реализован ге етический алгоритм оптимизации размещения камер, позволяющий эффективно решать нелинейные задачи комбинаторной оптимизации с большим пространством поиска.
Особый класс задач структурной оптимизации измерительной системы в статической модели наблюдения составляют задачи размещения датчиков обнаружения отказов. Здесь под оптимальным размещением понимается выбор такого минимального множества точек установки датчиков, чтобы собранные данные обеспечивали наилучшую возможность обнаружения сбоев. С точки зрения диссертационного исследования эта задача ценна тем, что хорошо изучена за последнее десятилетие; методы ее решения изложены во многих публикациях, в том числе в [94, 99, 110]. Рассмотрим эту задачу в такой постановке, как она рассмотрена в работе [99].
Пусть задана измерительная система, состоящая из N сенсоров, размещенных в заданных точках в пространстве R3 и связанных между собой каналами беспроводной связи. Входной сигнал каждого из N сенсоров задается вектором di = (d,u, d,2i,..., dpi). Вектор измерений у определяется данными, получаемыми от каждого сенсора, у = 2/./v)- Индивидуальный вклад каждого сенсора задается вектором q = (q\,q2, ...,g ). В этих обозначениях математическая модель вектора измерений у (при отсутствии шума предполагается, что у = (уі, ...,УР,0, ..., 0)) задается уравнением где D - матрица, столбцами которой являются векторы di, w N(0, a21) - шум измерений и других помех. Основная цель работы [99] - найти оптимальное размещение N сенсоров из максимального числа М при минимально возможной размерности Р вектора d.B качестве критерия оптимизации используется определитель матрицы Грама G = DTD, т. е. .D-критерий оптимальности.
Оптимальное размещение датчиков - это комбинаторная задача, в которой требуется установить N датчиков в М возможных точках. Проверка всех возможностей редко реализуема. Поэтому можно рассматривать множество N датчиков одновременно, применяя, например, метод имитации отжига, метод эволюционного моделирования (генетические алгоритмы)[ПО, 114] или использовать метод последовательных приближений, удаляя или добавляя по одному датчику на каждом шаге.
Таким образом, подход к структурной оптимизации измерительных систем в статической модели измерений может основываться на теории оптимального эксперимента. Для некоторых простых случаев найдены условия оптимальности: так, в работе [125] получены условия оптимальности размещения неподвижных дальномеров при статической модели наблюдения в двумерном и трехмерном случаях. Показано, что оптимальной является такая конфигурация дальномеров, при которой они равномерно распределены на окружности либо сфере вокруг центра области наблюдения, подтверждая тем самым естественное интуитивное решение проблемы. Однако, в более сложных случаях, как правило, применяются эвристические методы оптимизации различного рода.
Задача размещения оптических измерителей предполагает также выбор расписания измерений, т. е. интервалов видимости каждого прибора. В связи с этим рассмотрим задачи такого рода и методы их решения. 1. Задачи планирования процесса наблюдения связаны с совместной оптимизацией оптимизацией программы и состава измерений. Они могут интерпретироваться как задачи программного управления точностью калма-новской фильтрации, либо" как задачи планирования эксперимента. В первом случае они известны как задачи оптимального управления наблюдениями [19, 42, 88], во втором - как задачи расписания измерений [7, 127]. Рассмотрим задачи управления наблюдениями. Применительно к динамическим системам со случайными возмущениями они исследуются в работах Григорьева [19], Любимова и Постникова [41], Харисова [82], Хуторцева [83] - [86], Черноусько [88], Майера, Пешона и Дресслера [128] и др.; с возмущениями неопределенной природы - в работах Гусева [24], Куржанского [37], Малышева, Карлова и Красильщикова [42]. В дальнейшем ограничимся рассмотрением стохастических задач управления наблюдениями. Приведем некоторые из постановок задач управления наблюдениями. В работе [128] исследуется система следующего вида: где и и u f Є U - управление состоянием и наблюдениями соответственно. Авторы указывают на то, что оптимизация этих управлений может проводиться по-отдельности, причем критерием качества является следующий функционал.
Генетический алгоритм размещения измерителей в статической модели наблюдений
В разработанном алгоритме используются следующие правила [59, стр. 218-219]. 1. правило последовательного дробления элементов разбиения (правило построения дерева вариантов). Пусть D{ - множество возможных вариантов выставки измерителя, установленного в точке дг, г = 1,..., G, G - общее количество точек установки. Под вариантом выставки здесь будем понимать выбранные тем или иным способом углы выставки (азимут и угол места) визирной оси измерителя. Зафиксировав точку д і = G, G — 1,..., 1 с вариантом выставки j, j = 1,2,..., \Di\, относим к одному множеству все варианты, содержащие эту точку, а к другому - не содержащие ее. 2. Правила отнесения элементов разбиения к AQ: Элемент исключается из рассмотрения, если содержит количество точек gi больше первоначально заданной верхней границы М или зафиксированного рекорда (минимальное количество измерителей при полном соответствии ограничениям), либо вариант не удовлетворяет условию перекрытия интервалов видимости тп 2, п = 1,..., N, где тп - число измерителей, наблюдающих точку хп. 3. Правило выбора ветвей: односторонний обход дерева вариантов.
Достоинство метода ветвей и границ заключается в том, что он позволяет найти точное решение. Его основным недостатком является время поиска, которое приемлемо только для задач размещения малой размерности. При необходимости выбора расписания измерений, существенно увеличивающего размерность задачи размещения, метод ветвей и границ в большинстве случаев неприменим. Другим существенным недостатком метода ветвей и границ является невозможность получения решения при отсутствии отсутствии, полностью соответствующих заданным ограничениям.
Для преодоления недостатков, внутренне присущих методу ветвей и границ, в работе предложен и реализован принципиально иной алгоритм, базирующийся на методологии эволюционного моделирования. Данный метод с успехом применяется для решения различных задач, близких к исследуемым в настоящей работе, например [23], [110], [114], [131].
При решении оптимизационных задач с помощью генетических алгоритмов решение кодируется в виде вектора параметров (хромосомы), каждый параметр представлен одним геном. Популяция представляет собой множество решений, или особей, которые изменяются в процессе выполнения генетического алгоритма путем скрещивания (кроссовера) и мутации. Направление эволюции задается целевой функцией, или функцией приспособленности. Типовой генетический алгоритм включает следующие действия: 1) генерация начальной популяции; 2) отбор особей для скрещивания; 3) выполнение оператора кроссовера над парами отобранных родительских особей с генерацией особей-потомков; 4) выполнение оператора мутации над особями-потомками; 5) формирование новой популяции; 6) завершение при соответствии критерию останова; 7) переход к шагу 2. Кратко опишем особенности генетических алгоритмов по сравнению с другими методами оптимизации [27]: - генетические алгоритмы работают не напрямую с параметрами задачи, а с закодированным множеством ее параметров; - поиск осуществляется путем использования многих альтернатив на множестве решений, что позволяет анализировать различные области пространства решений одновременно; - для оценки качества решений используется значение целевой функции, а не ее приращений; - применяются вероятностные правила анализа оптимизационных задач. Перейдем теперь к рассмотрению особенностей генетического алгоритма оптимального размещения измерителей. 1. Представление решения. Варианты размещения кодируются следую щим образом. Хромосома (генотип особи), соответствующая варианту разме щения S, представляет собой целочисленный вектор [66]: Если в точке gi установлен измеритель, то 0 А D{, в противном случае полагаем А := 0. Каждый ген А представлен в двоичном коде, под него отводится 1{ разрядов, \Di\ Є [21і г,21і). Таким образом, общая длина хромосомы составляет / = Хл=і разрядов. 2. Формирование начальной популяции. В начальной популяции из Np особей Np — 1 особей формируются случайно. Одна из особей генерируется так, чтобы удовлетворять условию перекрытия интервалов видимости: в каждый момент времени tn количество тп измерителей, наблюдающих объект, должно быть не меньше двух, тп 2. Такая стратегия позволяет ускорить сходимость алгоритма на первых итерациях. 3. Целевая функция. Особенностью решаемой задачи являются ограничения различного типа, налагаемые на решение. Для учета ограничений в генетических алгоритмах, как правило, используются два подхода. Первый из них допускает существование в популяции только допустимых решений. При этом решения, не удовлетворяющие ограничениям, отбрасываются по мере их появления, либо приводятся к допустимому виду. Данный подход имеет тот недостаток, что в условиях частого появления недопустимых решений процедура отсева или исправления может быть чрезмерно ресурсоемкой.
Согласно второму подходу учет ограничений осуществляется с помощью штрафной функции p(S), которая мультипликативным образом вводится в целевую функцию ф{Б). Один из способов задания штрафной функции, учитывающей ограничения по точности, налагаемые на структуру измерительного комплекса, описан, например в работе [23].
Вид функции p(S) существенно зависит от специфики конкретной решаемой задачи. В случае слишком жестких штрафов в популяции доминируют одно или несколько допустимых решений, что приводит к преждевременной сходимости алгоритма к локальному экстремуму целевой функции. Напротив, при малых штрафах возрастает вероятность получения результата, не удовлетворяющего заданным ограничениям.
В данной работе предлагается метод, лишенный этих недостатков. Это достигается за счет задания такой внешней штрафной функции p(S), параметры которой изменяются в ходе выполнения алгоритма [22]. Аналогичный подход, описанный в работе [97], заимствует идею метода имитации отжига: штрафная функция определяется как р(М, Т) = e q/T: где параметр Т - температура, уменьшаемая в процессе выполнения алгоритма, ад- мера несоответствия ограничениям. Итоговая целевая функция особи (f)(S) имеет вид
Размещение оптических измерительных средств обзорного типа
Рассмотрим пример решения задачи размещения ОИС следящего типа. Она имеет меньшую относительно задачи размещения ОИС обзорного типа размерность, поскольку не требует оптимизации расписания измерений. Эта особенность позволяет во многих случаях эффективно применять метод ветвей и границ, получая точное решение за приемлемое время. Пользуясь этим, рассмотрим варианты размещения, полученные при различных критериях оптимальности (ірі-ірв, ФІ ФА)- Кроме того, исследуем применимость генетического алгоритма к оптимизации размещения ОИС, проведя его тестирование на задаче с известным точным решением.
Параметры задачи представлены в табл. 4.1, графики, координатных функций;гх, г у и rz расчетной: траектории, геодезические координаты территории размещения вынесены в Приложение 6.. В этом же приложении представлены схемы полученных вариантов размещения. Под опасной зоной; в табл. 4.1 понимается минимальное допустимое расстояние от точки установки измерительного средства до проекции траектории на-земную поверхность: Точки, попавшие приразбиении территории в опасную зону, исключаются из дальнейшего рассмотрения.
Рассмотрим оптимальные варианты размещения ОИС, полученные с использованием различных критериев оптимальности. Отметим, что даже в случае относительно небольшого пространства поиска (110 возможных точек установки, 106 вариантов) использование большинства критериев дает разные вариантььразмещения; При этом полученные оптимальные варианты можно разбить, на несколько групп близкой конфигурации; К первой из них принадлежат (pi- и щ- оптимальные варианты, которые полностью совпадают. К следующей группе относятся варианты, оптимальные в смысле 2, б, 0з и 04- Варианты, полученные при использовании критериев; 4 и 5 составляют третью группу. Здесь несколько выделяютсялр$- и -оптимальные варианты: так как эти критерии основаны на использовании Д-взвешенной матрицы наблюдаемости, которая не зависит от шума состояния, измерительные средства смещены ближе к началу траектории. Наконец, четвертую группу составляют ф\- и 02-оптимальные варианты, которые отличаются большим смещением измерительных средств к заключительному участку траектории вследствие большего влияния шума состояния.
Значения критериев оптимальности представлены в табл. 4.2. Полученные варианты дают в основном близкие значения критериев оптимальности; большинство из них могут быть использованы при проектировании измерительного комплекса. Исходя из совокупности критериев, наиболее обоснованным в данном случае представляется выбор вариантов из группы 3 (критерии 4 и ір). Явно нерациональным является выбор ф\- и -оптимальных вариантов, поскольку значения прочих критериев для этих вариантов наиболее велики.
Для ( -оптимального варианта приведем графики следа ковариационных матриц состояния tvPn и максимального среднеквадратичного отклонения оценки траекторных параметров при сглаживании max сгп (рис. 4.1). Эти графики позволяют сделать следующие выводы: 1) на всем интервале наблюдений среднеквадратичное отклонение при полученных вариантах размещения остается в заданных пределах; 2) значения функций увеличиваются при удалении объекта от ОИС, либо при уменьшении количества измерений в момент времени; 3) максимальное изменение значений функций на интервале наблюдениі соответствует моментам переключения ОИС. Последнее обстоятельство свидетельствует о том, что роль расписания измерений при формировании значения критерия оптимальности достаточно велика, что актуально для задачи размещения ОИС обзорного типа. Проведем сравнение результатов, полученных при помощи метода ветвей и границ и генетического алгоритма. Для -оптимального размещения ОИС получен следующий точный результат (см. табл. 4.2):
Оптимальное планирование наблюдения объекта на заключительном участке траектории
В этом разделе описывается решение задачи оптимизации перекрытия интервалов видимости ОИС обзорного типа. Задача заключается в поиске оптимального в смысле критерия (2.31) варианта выставки установленных га ОИС. Задачи такого типа известны как задачи расписания измерений или управления наблюдениями.
Пространство поиска при решении такой задачи, как правило, существенно меньше, чем для задачи размещения, что позволяет во многих случаях получить точное решение за приемлемое время. Для получения точного решения используется рассмотренный выше алгоритм ветвей и границ с некоторыми модификациями. Вариант размещения б1 из га ОИС задан вектором S = (dn, da,..., dim), dik Є А- Таким образом, количество точек установки постоянно и равно га, изменяется лишь вариант выставки.
Общим методом приближенного решения схожих задач является сведение к более простой эквивалентной задаче, которая затем решается алгоритмами, основанными на дискретном аналоге принципа максимума Понтряги-на. Исследование возможности разработки такого алгоритма для оптимизации управления оптическими наблюдениями привело к выводу о ее нецелесообразности. Применение метода Крылова-Черноусько для мультиканальных систем (см. главу 1) оправдано при наличии ограничений вида (1.23): в каждый момент времени измерения может производить только один канал. При отсутствии этого ограничения и задействовании т измерительных средств необходим расчет программных последовательностей для всех их возможных комбинаций, каждая из которых будет соответствовать некоторому фиктивному измерителю с собственной последовательностью матриц измерений {Cn}n=i- При ограничении тп 2 количество таких последовательностей составляет 2т — 3. Кроме того, плохо формализуемые ограничения, вызванные наличием фиксированных интервалов видимости и условием их перекрытия, приводят к необходимости полного перебора возможных вариантов решения с целью выбора наилучшего допустимого управления на каждой итерации алгоритма.
Если определить управление, как 0 ип 1 [82], то возможно формирование одной программной последовательности {Mn} L1; а новое управление будет рассчитываться, как ип = Мп/ Y n=i - т- е- будет представлять долю измерений в момент времени tn. Выбор матриц Сп при расчете программной последовательности определяется из условия Сп = arg max Мп, где множество Еп формируется с учетом матриц измерений, выбранных для предыдущих моментов времени ti, г = 1, ...,п — 1 и условия перекрытия интервалов видимости. Если Sn = 0, то необходим возврат к новому выбору матрицы Сп-ъ т- е- реализуется поиск с возвратами до получения допустимой последовательности {Сп} =1. Выбор новой последовательности матриц Сп, соответствующих управлениям ип, требует введения некоторой числовой характеристики точности измерений в этот момент времени. Пусть такая характеристика определена (например, некоторый функционал от информационной матрицы). Тогда можно найти допустимый план измерений {Сп}п=ъ наиболее близкий к плану, заданному управлением {ип} :=1. Однако такой подход, как и в предыдущем случае, требует полного перебора допустимых вариантов решения.
Экспоненциальная сложность описанных приближенных алгоритмов приводит к тому, что при малом числе измерительных средств т более оправдано применение алгоритма ветвей и границ, а при чрезмерной сложности точного решения - генетического алгоритма, описанного выше. При этом в алгоритм вносится изменение в кодировании: хромосома представлена вектором Л = (li, 12,..., lm), а г—й ген принимает значение в интервале [0, Д- — 1]; значению гена її соответствует вариант выставки с номером k + 1.
В качестве примера рассмотрим задачу оптимизации расписания измерений для размещения 7 ОИС (схема приведена в Приложении 6). Полученные оптимальные расписания измерений и значения критериев оптимальности представлены в табл. 4.6 и 4.7.
В силу относительно небольшого пространства поиска результаты применения различных критериев оптимизации дали только 5 различных вариантов расписания. При этом расписания, полученные при использовании критериев /?2, ірь, фь, Фіі Фі характеризуются большим количеством ОИС, наблюдающим начальный участок интервала наблюдений; фз- и 04-оптимальные расписания - большим числом ОИС, наблюдающим заключительный уча
Для исследования эффективности применения генетического алгоритма к задаче планирования расписания измерений рассмотрим решение двух задач с различным отношением количества допустимых вариантов расписания к размеру пространства поиска.
Первый вариант размещения ОИС обладает следующей особенностью: часть ОИС размещена так, что имеет малое количество вариантов выставки, причем некоторые (ОИС под номерами 2 и 7) - только 1 вариант. Это уменьшает размер пространства поиска ( 106 возможных расписаний), но увеличивает число допустимых вариантов ( 8 104). Напротив, для второго варианта (вариант Si из задачи размещения ОИС обзорного типа), при котором ОИС размещены равномерно вдоль наблюдаемого участка траектории, пространство поиска относительно велико, включая 7 107 вариантов расписания, но количество допустимых решений составляет только 397.
