Содержание к диссертации
Введение
Глава 1. Методы и алгоритмы имитационного моделирования поисковых систем.
1.1. Сложные системы 8
1.2. Проектирование систем 10
1.3. Поисковые системы 16
1.3.1. Вероятностные характеристики поисковой системы 27
1.4. Имитационное моделирование сложных систем 29
1.4.1. Методы и алгоритмы имитационного моделирования. 30
1.4.2. Имитация способом составления расписаний событий. 35
1.4.3. Имитация транзактным способом. 37 1.4.4 Имитация агрегатным способом. 40
1.4.5. Имитация процессным способом. 44
1.4.6. Имитация непосредственно алгоритмами 46 функционирования блоков или просмотра активностей
Выводы по 1-ой главе. 50
Глава 2. Построение имитационной модели поисковой системы 51
2.1.1. Формулировка проблемы и определение цели построения модели 52
2.1.2. Анализ априорной информации о моделируемой системе 52
2.1.3. Содержательное описание поисковой системы 52
2.1.4. Концептуальная модель поисковой системы. 56
2.1.5. Выбор универсального либо специального языка моделирования. 58
2.1.6. Формальное описание имитационной модели и программирование ее на ЭВМ. 60
2.1.7. Алгоритм моделирования поисковой системы в виде чисел 65
2.1.8. Числовая модель поисковой системы 73
2.1.9. Этап проверки адекватности модели 85
2.1.10. Планирование имитационных экспериментов с моделью 86
2.1.11. Реализация имитационных экспериментов с моделью в соответствии с разработанным планом эксперимента 86
2.1.12. Анализ статистических данных о поведении модели по результатам различных имитационных экспериментов 86
2.1.13. Анализ статистических данных о поведении модели по различным имитационным экспериментам 87
2.2. Модель режима захвата 87
2.3. Модель режима сопровождения поисковой системы 89
Выводы по 2-ой главе. 90
Глава 3. Имитация поисковой ситуации в числовой модели 91
3.1. Исходные параметры системы оптического поиска 91
3.2. Процедура вбрасывания объекта поиска с использованием генераторов случайных чисел различных законов распределения 92
3.3. Подпрограмма ввода помех 97
Выводы по 3-й главе. 99
Глава 4. Проверка адекватности числовой модели 100
4.1. Программный комплекс моделирования поисковой системы 100
4.2. Моделирование реальных оптических систем поиска. 101
Выводы по 4-й главе. 115 Заключение. 116
Список литературы. 118
Приложения. 125
- Сложные системы
- Вероятностные характеристики поисковой системы
- Формулировка проблемы и определение цели построения модели
- Исходные параметры системы оптического поиска
Введение к работе
С быстрым развитием информационных технологий изменяется и технология проектируемых технических систем. Наиболее широкое применение технических систем находят информационные системы, сложность которых возрастает. Одно из направлений применения информационной технологий - это решение задач получения, обработки, анализа и распознавания информации, а также для управления другими сложными системами и объектами. Большая группа таких задач характеризуется тем, что источник информации представляет собой распределенное в пространстве информационное поле. Таким образом, процесс получения информации и ее переработки сводится к поиску необходимой информации в информационном пространстве, в котором помимо полезного сигнала могут присутствовать различного рода помехи.
Для отыскания нужной информации в области поиска используются поисковые процедуры. В настоящее время существуют множество систем поиска, работающих в различных диапазонах. Это могут быть как системы, работающие в оптическом диапазоне, радиолокационные системы поиска, так и поисковые системы информационного поиска в базе данных.
В процессе проектирования к сложной системе выдвигают требования по характеристикам решению ей поставленной задачи, т.е. система должна решать возложенные на нее задачи в соответствии с заданными количественными или качественными показателями. При проектировании сложной системы используется набор как существующих, так и возможно совершенно новых конструкторских решений, что может привести к неоднозначности выбора правильного проектного решения. Таким образом, встает проблема выбора проектного решения, соответствующего заданным характеристикам функционирования. Для поисковой системы такими характеристиками являются вероятностные и временные характеристики.
При выборе проектного решения или модернизации существующей поисковой системы возникают значительные трудности из-за невозможности оптимизации вероятностно-временных характеристик проектируемой (модернизируемой) системы поиска с помощью натурных экспериментов. Кроме того, не всегда удается создать все необходимые условия натурного эксперимента, а проведение их требует больших временных затрат и средств. Другим фактором сложности проведения натурных экспериментов является стохастический характер процессов, протекающих в системе поиска (шумы, помехи, сбои аппаратуры, изменения параметров во времени и тд.). Это означает, что поисковую систему в общем случае можно изучить лишь посредством многократно повторяемых испытаний, позволяющие получить оценки вероятностно-временных характеристик и качество функционирования системы. Поэтому для снижения временных затрат и ресурсов на проведение натурного эксперимента используется математическое моделирование.
Любую систему, в том числе и поисковую систему, можно представить в виде подсистем. Методология имитационного моделирования позволяет произвести анализ всей системы на основе квазипараллельного моделирования ее подсистем.
Процесс моделирования предполагает разработку алгоритма, позволяющий автоматизировать получения вероятностно-временных характеристик системы без проведения натурных экспериментов. Решение подобной многоальтернативной задачи является актуальной проблемой.
Целью работы является разработка алгоритма и аппаратная реализация имитационного моделирования проектных решений поисковой системы на этапе проектирования и испытаний.
Методы исследования, используемые в работе: теория вероятности и методы имитационного моделирования.
Научная новизна работы определяется тем, что в ней впервые:
Разработан алгоритм поисковой системы, ориентированный на автоматизированное проектирование.
Представлена числовая модель поисковой системы для имитационного моделирования в системе автоматизированного проектирования.
Сформулирован критерий принятия решения для числовой модели о наличии - отсутствии объекта поиска.
Разработан алгоритм анализа области поиска на основе критерия принятия решения для числовой модели.
Представлена схема формирования входных воздействий для числовой модели поисковой системы, позволяющая учитывать в процессе моделирования поисковые ситуации на заданном множестве в интерактивном режиме.
Разработана числовая модель движущегося объекта с изменяемыми параметрами движения.
Разработана числовая модель захвата и сопровождения объекта поиска.
Разработано программное обеспечение САПР поисковых систем на основе числовой модели.
Основные результаты, выносимые на защиту:
Алгоритм поисковой системы, ориентированный на автоматизированное проектирование.
Числовая модель поисковой системы для имитационного моделирования в системе автоматизированного проектирования.
Алгоритм анализа области поиска на основе критерия принятия решения для числовой модели.
Схема формирования входных воздействий для числовой модели поисковой системы, позволяющая учитывать в процессе
7 моделирования поисковые ситуации на заданном множестве в интерактивном режиме.
Числовая модель движущегося объекта с изменяемыми параметрами движения.
Числовая модель захвата и сопровождения объекта поиска.
Результаты экспериментальных исследований. Практическая ценность работы.
Предложен алгоритм поисковой системы, ориентированный на автоматизированное проектирование.
Предложена числовая модель, позволяющая осуществить выбор проектного решения поисковой системы методами математического имитационного моделирования.
Разработана методика расчета параметров системы по заданным вероятностно-временным характеристикам функционирования систем поиска.
Разработана числовая модель генерации исходной ситуации, представления области и объектов поиска.
Апробация работы. Результаты работы докладывались и обсуждались на XXXII (февраль 2003 г) и XXXIV (февраль 2005 г.) конференциях профессорско-преподавательского состава СПб ГУИТМО, II - ой конференции молодых ученых (март 2005 г.) СПб ГУИТМО с двумя докладами, Международная конференция по системам искусственного интеллекта при поддержке IEEE AIS'05/CAD-2005, Политехнический симпозиум (декабрь 2005 г.) и III - ой конференции молодых ученых (апрель 2006 г.) СПб ГУИТМО. Публикации. По материалам диссертации опубликовано 5 работ.
Структура и объем работы. Работа состоит из введения, 4-х глав, заключения, библиографического списка из 82 наименований, содержит 124 страницы основного текста, 33 рисунка и 9 таблиц.
Сложные системы
Под системой будем понимать объект любой природы. Если система может быть представлена в виде подсистем, но в целом все они работают по разным физическим законам, то такую систему будем называть сложной системой.
Любая система характеризуется[59,75]: 1). Параметрами системы - это характеристики системы, от которых зависит процесс выполнения системой поставленной перед ней задачи.
Все параметры можно разделить на контролируемые, которые выбирает сам разработчик, и неконтролируемые. Все неконтролируемые по признаку информированности о них разработчика системы могут быть разбиты на три класса: 1.1. детерминированные параметры, значения которых известны разработчику; 1.2. случайные параметры с известными законами распределения; 1.3. неопределенные случайные параметры, для которых известно только возможное множество законов распределения. Этот класс может быть разделен на подклассы:
а) неопределенные факторы, связанные с воздействием активных систем, цели которых не всегда совпадают с целями проектируемой системы;
б) неопределенные факторы, связанные с недостаточной изученностью каких-либо явлений или величин;
в) неопределенные факторы, связанные с неточностью знания цели системы или критерия эффективности.
2). Вектором входного воздействия на систему w(t) є W - множество информационных сигналов, поступающих на вход системы. Причем вектор w(t) включает в себя и управляющие сигналы, которые позволяют управлять поведением сложной системы. 3). Вектором возмущений внешней среды на систему %(t) є Е- сигналы помех, создающие внешней средой, в которой функционирует система. 4). Вектором состояний системы x(t) є X - множество всевозможных состояний системы. Переменные хьх2,.. .,хк вектора x(t) - это переменные, характеризующие состояние системы. 5). Вектором выхода системы у(0 є Y. 6). Вектором измерений z(t) є Z.
Таким образом, процесе функционирования системы можно описать векторно-матричными дифференциальными уравнениями вида [5]:
Проектирование системы - это создание, преобразование и представление в принятой форме образа этого ещё не существующего объекта. Проектирование включает в себя разработку технического задания, отражение потребности в техническом объекте, и реализацию технического задания в виде проектной документации [55].
Техническое задание - это первичное описание объекта. Результатом проектирования является получение полного комплекта документации, т.е проектирование - это процесс получения и преобразования исходного описания объекта в окончательное описание на основе выполнения комплекта работ исследовательского, расчетного и конструкторского характера.
Выделим шесть основных процедур системного анализа, используемым при проектировании систем, основные характеристики которых представлены в таблице 1.1 [70]:
Система в процессе проектирования представляет собой информационную модель будущей реальной системы. Информационная модель системы может быть представлена как алгебраическая система, образующая четверкой множеств, т.е процесс проектирования формально можно определить следующим образом [14,64]: A=A(W,M,R,P) (1.2) где W - множество типовых проектных описаний; М - множество типовых проектных процедур; R - множество межуровневых информационных связей; Р - множество правил логического вывода для построения из элементов W, М и R оптимальных маршрутов проектирования.
Состояние системы при проектировании в каждый момент проектирования характеризуется значениями элементов множеств W, М, R и Р.
Вероятностные характеристики поисковой системы
При обнаружении информационного сигнала выдвигаются две гипотезы о его обнаружении[52, 79, 81]: Ао - объект нет. Ai — объект есть. В результате возможны два решения: Ао - объекта нет. Ai — объект есть.
Очевидно возможны четыре ситуации совместных случайных событий «гипотезы» и «решения»: 1. Ai Aj - правильное обнаружение. 2. Ао Ао - правильное необнаружение. 3. A0 Ai - пропуск цели - проходит информация о необнаружении объекта к заданному сроку при наличии объекта в информационном пространстве. 4. Ai Ао - ложное срабатывание - проходит информация о обнаружении объекта при его отсутствии в пространстве.
Эти события образуют полную группу событий, т.е. Р(А/А, )+Р(Ао А1)+Р(А1 Ао)+Р(Ао Ао) = 1 (1.15)
Таким образом, для поисковой системы характерны следующие вероятностные характеристики, описывающие функционирование системы: вероятность правильного обнаружения объекта - Р0; вероятность ложного обнаружения - Рлт; вероятность пропуска объекта - Рпц . Задача поиска в этом случае может быть сформулирована в следующем виде: за время tj наблюдатель должен с наибольшей вероятностью обнаружить цель, т.е. наблюдатель должен выбрать некоторую траекторию перебора области поиска на интервале t є (0,t,], при движении по которой вероятность обнаружения максимальна; вероятности пропуска цели и ложного обнаружения должны быть минимальны.
Вероятность обнаружения «складывается» из вероятности попадания цели вО,и вероятности обнаружения ее в Q [71], т.е Роб = РкРф (1.16) где Рк - вероятность попадания объекта BQ- вероятность кинематического обнаружения, Рф- вероятность обнаружения объекта в D. - вероятность физического обнаружения. Вероятность Рф, причем правильного обнаружения, может быть представлена в виде[16]: Рф=1-Рдг-Рпц (1.17)
Для получения вероятностно-временных характеристик поисковой системы будем использовать математическое моделирование, для чего необходимо составить модель, описывающую функционирование системы и воздействие внешних факторов аналитическими зависимостями. Учитывая их сложность, а также многофакторность процесса и невозможность учета всех возможных факторов, аналитические зависимости практически непригодны для моделирования на ЭВМ. В этой связи целесообразно применять имитационное моделирование, которое позволяет описывать поведение поисковой системы набором алгоритмов, отображающих по исходным данным реальные явления в системе[21]. Рассмотрим более подробно этап моделирования.
Имитационное моделирование натурное или математическое - это вид моделирования, для которого характерно имитирование некоторых возможных условий функционирования подсистем моделируемой системы. Совокупность результатов имитации подсистем позволяет с той или иной степенью достоверности представить поведение системы в целом.
Имитационная модель образуется взаимодействием следующих элементов[65,82]: Состояний системы - упорядоченная совокупность значений внутренних и внешних параметров, определяющих ход процессов в системе. Множество состояний системы, как правило, конечное или счетное множество. События - скачкообразное изменение состояния системы. Генераторы случайных чисел - позволяет формировать очередное состояние. Таймер - счетчик развития процесса во времени. Цепи событий - реализация логики модели. Цели моделирования - определения показателей качества функционирования системы. Счетчики - накопление результатов моделирования. Блок инициализации - блок приведения модели до начала проведения эксперимента в исходное состояние. Критерий остановки - определяет момент прекращения прогона модели. Метод обработки результатов - метод сжатия получаемой информации, вычисление статистических оценок, построение гистограмм и статистических функций распределения.
Основными этапами разработки имитационной модели является Формулировка проблемы и определение цели построения модели. Анализ априорной информации о моделируемой системе. Составление содержательного описания объекта моделирования. Построение концептуальной модели. Выбор универсального либо специального языка моделирования. Формальное описание имитационной модели и программирование ее на ЭВМ. Проверка адекватности модели. Планирование имитационных экспериментов с моделью. Реализация имитационных экспериментов с моделью в соответствии с различным планом эксперимента. На основе анализа данных по результатам текущей реализации принимается решение о продолжении моделирования. Анализ статистических данных о поведении модели по результатам различных имитационных экспериментов.
Формулировка проблемы и определение цели построения модели
Выбор показателей качества определяется функциональной задачей проектируемой системы, для которой строится модель [61, 78, 51].
Показатели качества работы поисковой системы могут быть и не числовыми характеристиками, но главное, чтобы их число не было бы меньше количества выходных параметров. При выборе показателей качества для поисковой системы будем исходить из следующих требований к показателю: реализуемость; регистрируемость; полнота; обоснованность и соответствие выходным параметрам системы; согласованность с нормативно-техническими документами. Тогда показателями качества поисковой системы выбираем: вероятностные параметры обнаружения цели (вероятность обнаружения объекта поиска к заданному сроку, вероятность правильного обнаружения, вероятность ложной тревоги и вероятность пропуска цели, математическое ожидание числа объектов, обнаруженных к заданному сроку), вероятность появления объекта поиска в пределах дальности действия поисковой системы, математическое ожидание времени обнаружения объекта поиска (среднеожидаемое));
кинематические параметры обнаружения цели(стратегия поиска, скорость объекта поиска, разность курсовых углов движения наблюдателя и объекта поиска, расстояние от наблюдателя до объекта поиска, курсовой угол наблюдателя на объект поиска; точностные показатели системы (точность определение координат местоположения объекта поиска, его скорость и курсовой угол); временные показатели системы (время просмотра поля анализа, период просмотра); внешние ограничения (область поиска; поле анализа; объект поиска); внутренние ограничения (параметры входного устройства (энергетическая, спектральная и интегральная чувствительности); параметры функциональной электроники; параметры электромеханической части; параметры БЦВМ; спектральный диапазон работы; разрешающая способность);
На данном этапе в соответствии с описанием компонент реальной поисковой системы или согласно техническому заданию на проектируемую систему устанавливается состав управляемых и контролируемых характеристик объекта моделирования. Прежде всего, выделяются те характеристики управления поисковой системы и контроля ее работой, которые имеют отношение к цели моделирования. Все составляющие функциональные зависимости, определяющие значение показателя качества системы включаются в состав управляющих переменных и контролируемых характеристик моделирования. Управляющими параметрами поисковой системы являются: сигнал, определяющий поле анализа, в котором необходимо произвести анализ. Управление осуществляется в соответствии со стратегией поиска; сигнал, отвечающий за «переключение» системы из режима в режим; Контролируемыми параметрами поисковой системы являются: уровень информационного сигнала в поле анализа; время анализа в поле анализа; общее время просмотра области поиска; параметры движения объекта поиска.
Данный этап заключается в переработке и дополнении имеющейся информации для необходимого выделения алгоритмов функционирования в каждом из режимов работы поисковой системы. На этом этапе устраняются возникающие неопределённости и составляются временные диаграммы функционирования. Определяются наиболее узкие места процесса функционирования компонент поисковой системы, устанавливается необходимая последовательность действий компонент, выделяются вероятные места возникновения конфликтных ситуаций и описывается принятый порядок их разрешения в системе [78].
Узкими местами поисковой системы являются: пропускная способность входного устройства; производительность ЭВМ, обрабатывающая информацию с целью обнаружения объекта поиска;
Местами, в которых возможно возникновение конфликтных ситуаций в поисковой системе, являются: алгоритм выделения информационного сигнала из сообщения; пространство решений, где решается задача принятия решения о наличии - отсутствии объекта поиска.
Исходные параметры системы оптического поиска
В соответствии с предложенным алгоритмом необходимо задать следующие исходные параметры: 1) Область поиска - область, в которой производится поиск. Область характеризуется двумя координатами X и Y - это соответственно высота и ширина области поиска. Координаты X и Y задаются в градусах. 2) Поле анализа Q„ - для системы оптического поиска это поле зрения 2со, задаваемое в градусах. 3) Разрешающая способность а - задается в градусах. 4) Задаются размеры искомого объекта поиска. Размеры задаются в градусах. 5) Вероятность нахождения объекта поиска в заданной области поиска - Рн. 6) Стратегия поиска - определяется количество элементов разбиения для каждой ячейки. 7) Параметры внешней среды - задается уровень помех в области поиска. Параметры внешней среды более подробно будут рассмотрены далее. На основе вышеперечисленных исходных параметров вычисляется по формулам 2.20 и 2.22 размеры массива, инициализируется рабочий массив необходимыми значениями, задается количество элементов разбиения для каждой ячейки области поиска в соответствии с заданной стратегией поиска в эксперименте и осуществляется процедура вбрасывания объекта поиска. Местоположение объекта поиска в области поиска и в поле зрения определяется с помощью генератора случайных чисел с учетом вероятности нахождения объекта в области поиска Рн. Рассмотрим процедуру вбрасывание объекта, используя генераторы случайных чисел с различными законами распределение.
Получить последовательность случайных величин с произвольным законом распределения можно из последовательности равномерно распределенных в интервале (0;1) случайных чисел, применив метод обратных функций и метод моделирования 7, 65].
В соответствии с методом обратных функций генерация случайной величины с заданным законом распределения производится следующим образом. Если имеется случайная величина , равномерно распределенная на (0;1), и непрерывная случайная величина г с функцией распределения F(t) и плотностью распределения f(t), то связь между этими величинами устанавливается соотношением = jf(t)dt = F(r1) (3.1) —СО Для получения величины г при известной Ъ, необходимо взять F" (4).
Для некоторых распределений, например нормальное, определение обратной функции F_1( ) требует очень большой вычислительной работы. Поэтому в этих случаях удобно использовать вероятностные схемы, позволяющие точно или приближенно получить требуемый закон распределения.
В работе исследовались генераторы случайных чисел со следующими законами распределения: Нормальное распределение. Равномерное распределение на отрезке (а,Ь). Показательное распределение. Распределение Пуассона. Результаты вбрасывания объекта поиска в область поиска проводились с учетом следующих условий: Количество испытаний равно 1000. Поле анализа с объектом поиска определялось путем генерации двух индексов случайным образом, используя выбранный закон распределения. Область поиска представляет собой размер 6 6 полей анализа. Для всех экспериментов задавалось одинаковое начальное значение для генератора равномерно распределенных случайных чисел.
