автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Адаптивные алгоритмы сокращения трудоемкости статистического моделирования

На правах рукописи

Лихолет Николай Олегович

ги43

АДАПТИВНЫЕ АЛГОРИТМЫ СОКРАЩЕНИЯ ТРУДОЕМКОСТИ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ

Специальность 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

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

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

2 "! ?л-г)

003470431

Работа выполнена в Балтийском государственном техническом университете «ВОЕНМЕХ» им. Д.Ф. Устинова, г. Санкт-Петербург.

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

кандидат технических наук, доцент Емельянов Валентин Юрьевич Официальные оппоненты:

доктор технических наук, профессор Холоднов Владислав Алексеевич

доктор технических наук, профессор Толпегин Олег Александрович

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

ОАО «Концерн «Гранит-Электрон» (г. Санкт-Петербург)

Зашита диссертации состоится « 2. » ц^А 2009 г. в )Ь_часов на заседании

Совета по защите докторских и кандидатских диссертаций Д 212.230.03 при государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный технологический институт (технический университет)» по адресу; 190013, г. Санкт-Петербург, Московский пр., д. 26(ауд. 61).

С диссертацией можно ознакомиться в библиотеке института.

Отзывы на автореферат, заверенные печатью, просим направлять по адресу: 190013, г. Санкт-Петербург, Московский пр., д. 26, СПбГТЩТУ), Ученый Совет; тел +7 (812) 494-93-75, факс +7 (812) 712-77-91, e-mail: dissovet@lti-gti.ru

Автореферат разослан « го » 2009 г.

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

Халимон В.И.

Актуальность темы

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

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

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

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

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

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

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

Объектом исследования является совокупность методов сокращения трудоемкости статистического моделирования.

Предметом исследования является повышение их эффективности.

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

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

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

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

3. Программная реализация алгоритмов, решающих задачи оптимизации параметров.

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

5. Апробация разработанных метода, расчетных схем и программного комплекса при решении конкретных практических задач.

На защиту выносятся:

1. Принцип адаптации методов сокращения трудоемкости статистического моделирования в процессе проведения эксперимента.

2. Расчетные схемы и алгоритмы оптимизации методов сокращения трудоемкости.

3. Обобщенный адаптивный алгоритм статистического моделирования.

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

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

Научная новизна результатов диссертации состоит в следующем:

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

2. Впервые формализованы и решены задачи оптимизации параметров основных методов сокращения трудоемкости статистического моделирования.

3. Разработаны два мультиметода, предусматривающие одновременное применение двух совместимых стандартных методов, решены задачи их оптимизации.

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

Достоверность результатов, полученных в работе, определяется:

- корректным использованием математического аппарата математической статистики и методов численной оптимизации.

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

Практическая ценность результатов диссертации состоит в следующем:

Обобщенный адаптивный алгоритм статистического моделирования обеспечивает возможность сокращения времени разработки сложных стохастических систем в различных областях при оценке вариантов их построения методом статистического моделирования. Предлагаемые алгоритмы и их программная реализация позволяют достичь выигрыша в трудоемкости 20-30 раз и выше по сравнению со стандартной схемой и до 2-4 раза и выше по сравнению с достигнутыми ранее результатами для известных способов сокращения трудоемкости. Сформулированы практические рекомендации по применению методов сокращения трудоемкости статистического моделирования и по мерам обеспечения корректности получаемых результатов.

Внедрение результатов. Результаты диссертационного исследования внедрены в ОАО «Концерн «Гранит-Электрон» в рамках программы работ с целью совершенствования технических характеристик систем управления, а также в учебном процессе БГТУ «ВОЕНМЕХ» им. Д.Ф. Устинова, о чем имеются соответствующие акты.

Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на X международной конференции «Региональная информатика - 2006», IV конференции молодых ученых "Навигация и управление движением" (ЦНИИ "Электроприбор" СПб, 2002) и на семинарах кафедры «Систем обработки информации и управления» БГТУ «ВОЕНМЕХ» им. Д.Ф. Устинова и ОАО «Концерн «Гранит-Электрон».

Публикации. По теме диссертационной работы опубликовано 10 научных работ, из них - 4 статей (1 статья из перечня изданий, рекомендованных ВАК), 4 свидетельства об официальной регистрации программ.

Структура и объем диссертации

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

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

_ 2 л

арифметическое Х = —У\Х/1. Согласно центральной предельной теореме,

Пы

случайная величина X распределена асимптотически нормально с математическим - „

ожиданием /иЛ- и дисперсиеи О- = ——.

п

Как следствие, при достаточно большом объеме выборки (на практике и>50) погрешность оценки определяется как е = а^^Щ = ам а количество опытов,

необходимое для достижения заданной допустимой погрешности £доп с заданной доверительной вероятностью Рдое, как:

аг а1

дг - "а»"* /П

Здесь адое~се^ое(Раов) - коэффициент для доверительного интервала.

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

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

Модель динамической системы задается в виде системы уравнений

у (Л-„(\г(А,1Л ¡=11 „ (2)

Л, у,- ), I о-,*.,.V-/

где Х(()=(Х/(с)^^),... ,Х„({)) - вектор переменных состояния системы; У=(У1,У2,...,Ут) - вектор случайных параметров - коэффициентов правых частей уравнений или начальных условий. Качество системы характеризуется

мгновенным значением неременной состояния Х—Х, в момент времени /-1. Таким образом, задача сводится к оценке т* математического ожидания функции отклика Х1 на генерируемые в процессе статистического моделирования реализации вектора V: тх-М[Х(1], V)].

Метод выделения главной части. Решение системы (2) Х(1, V) заменяют приближенным выражением удобным для аналитических преобразований.

Например, квадратичной формой:

Вводится новая переменная состояния 2(/,У)=Х,(/,У)-У((,У) и выполняется замена переменной X на 1 путем подстановки:

у.1 V.! кА

Оценка искомого математического ожидания определяется как т'х = А/[у(71,К)]+Л/[2(/1,Р)] = ту + т., где первое слагаемое может быть найдено

а2 И

аналитически. Необходимое количество опытов в этом случае: = ■г .

При удачном выборе функции У(/,К) дисперсия случайной величины может оказаться существенно меньше, чем дисперсия Х^,, V).

Метод выборки по группам. В соответствии с данным методом область й возможных значений случайного вектора разбивается на К непересекающихся областей 6к: С=0]иС2и...и0Л-.

Если для области О^ выполним Л'* опытов, получим оценку математического

1

ожидания искомого показателя для данной области: т"^ = — ¿^Х^У^^). Тогда результирующая оценка определяется усреднением:

= (3)

*.1 4=1 IV ь 1.1

где рк = Р{у е ).

Введя в рассмотрение доли от общего количества опытов, соответствующие N /

областям Сь дк = у^, на основе (1) получим соотношение для определения количества опытов, необходимого для получения результата с погрешностью не вышее^,,:

8»„ *-1 Чк

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

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

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

Уточненная оценка математического ожидания Л0 находится как

. . , .

-Ц) ,

где т\ - оценка математического ожидания функции отклика для основной модели, ц* - оценка математического ожидания функции отклика для упрощенной модели, ц - истинное значение математического ожидания для упрощенной модели, Эщ -корреляционный момент связи результатов параллельных опытов с основной и упрощенной моделями, 0$ -дисперсия функции отклика для упрощенной модели.

Требуемое для получения результата с заданной точностью ейо„ количество опытов:

£<пп

0

где = а\ - дисперсия функции отклика для основной модели, рт = -, ® - -

V АА'

коэффициент корреляции функций отклика.

Теоретически данный метод обеспечивает сокращение трудоемкости статистического эксперимента по сравнению со стандартной схемой в 1/(1 - р2^) раз.

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

Метод выборки по группам является наиболее устойчивым в смысле сокращения трудоемкости - при условии наличия в каждом слое достаточного числа опытов, некоторый выигрыш практически гарантирован.

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

ЦЯнКлтчтРГП чЖДкчлм оттвтиАШт тп,;т1Лв»гтт/>м1

------_ V ^ - '- ' л**'~ * '"■

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

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

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

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

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

Мультиметодом в работе названо одновременное применение двух совместимых стандартных методов. В рамках выбранных методов сокращения трудоемкости возможно построение двух мультиметодов - совмещение метода выборки по группам с методом выделения главной части (мультиметод 1) и совмещение метода выборки по группам с комбинированным методом (мультиметод 2).

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

сокращения трудоемкости iV^.j-1,2,...,5.

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

N0 . /

максимизации выигрыша в трудоемкости тр"'/>л> тах или> ПРИ

/ ^треб.

фиксированном для конкретной модели Nlm6, по критерию N'mK6 -> min. Затем сравниваются предполагаемые результаты применения этих методов и определяется тот метод, для которого оценка выигрыша в трудоемкости является наибольшей.

После определения наиболее эффективного для рассматриваемой модели метода сокращения трудоемкости моделирование продолжается на его основе.

Для метода выборки по группам предметом оптимизации является количество и границы групп (слоев) Gt: G=GilXj?u... U3k. Трудоемкость эксперимента оптимизируется как функция от этой совокупности аргументов: ^„Ж & ]-•••)-> где {¿f}-соответственно количество

и совокупность границ слоев для j-го случайного параметра модели.

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

/! /1 /

1 1 1 ( 1 1.....

/

1 I 1

✓ г *

ХоУоЯо X1 X;

Рисунок 1.

На рисунке показан пример разбиения области определения случайного трехмерного вектора. Область определения случайного параметрах делится двумя границами на три части, область определения случайного параметра Y не делится, область определения случайного параметра Z делится одной границей на две части. В результате получается разбиение всей области определения случайного вектора -аргумента функции отклика - на шесть слоев.

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

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

В настоящей работе главная часть строилась в виде полиномов второго порядка следующего вида: Одномерный случай: Y(V) = C0Vj2 + С,К,'. Двумерный случай: Г(к) = С/,'2 + С/2'г + С./Х + С/; + СгУг. Трехмерный случай: ^

у(и)=С/;2+сУг + су;г+c/;v;+с/2>;+c5v;v; +су;+c7v;+cHv;

и так далее, где величины V*t являются нормированными значениями компонент случайного BcKiOpa " в сишнешшии с формулами:

(5)

где '^¿тах соответственно, максимальнее я минимальное значения *-ок

компоненты случайного вектора Fno начальной выборке.

Трудоемкость эксперимента для данного метода оптимизируется как функция от вектора коэффициентов: Nmpc6 (с) -> min.

Для комбинированного метода упрощенная модель также строится в виде полинома (4), величины F*; нормируются аналогичным с (5) образом. Алгоритм оптимизации комбинированного метода аналогичен алгоритму оптимизации метода выделения главной части.

1 i ГП ГУМ) г11 П II; Г ( ы {• UVUtTIJUPTrtïïf\U 1 nrт ТЧ1WIi'JТ 1>Л1 'I(ЛТ^гт глпимолтпл п тлитпи

" V Ulj.iu.iuuviu^viii i Ullllll'liiJIlJlJ IMi V/l UW.ltl^lVWlUW 11 1 ^иИНДЦ!

слоев и для каждого слоя находится соответствующая ему оптимальная главная часть в виде полинома второй степени Yk{V), где к - номер слоя. В этом случае

где Zt( V) =Х( V)-Yk(V). Требуемое количество опытов:

Ci)m '-1 Чк

В рамках мультиметода 2 оптимизируются количество и границы слоев, а также коэффициенты упрощенной модели \ik=Yk(V) для каждого слоя. При обработке результатов моделирования для каждого слоя, помимо т'}^, находятся оценки корреляционных моментов 6даь дисперсий Dsk и DKk, коэффициентов корреляции рsskв каждом слое. Тогда математическое ожидание функции отклика находится как

m, = ZMо. W Ло = тТ]

а требуемое количество опытов равно:

ебш Чк

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

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

Программный комплекс был написан на языке С++ в среде Microsoft Visual Studio версии 6.0 с использованием библиотеки MFC. Он представляет собой компилируемое приложение с некоторыми пустыми функциями, которые пользователь должен определить в соответствии со своими задачами. Пользователь должен описать исследуемую модель, задать количество случайных параметров в ней и законы их распределения, а также доверительную вероятность и доверительный интервал. Можно выбрать один из часто встречающихся законов распределения и указать его параметры. Например, равномерный закон и его границы, нормальный закон и его математическое ожидание и дисперсию. Также

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

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

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

- рщдщ-------------------

1

Ш ш

\ дал ■ . ' iv.4jr.T~ )

г •■ ии^^нц]-; | м

. Г.: ЦцпцууддУ ] Ц

....

-г,

тт.

- 3-

Ш'

428 2 ПО Ж)6?Ш М5СИМ П0 11 сйо«и по/ц)иенисл«дующир реэулимм ть

^ЭМотожмпш.*«: 13.591 Л

Рисунок 2.

1 - окно законов распределения входных случайных величин;

2 - кнопка генерации начальной выборки;

3 - кнопка запуска моделирования в соответствии с оптимальным методом сокращения трудоемкости (этот оптимальный метод будет определен программным комплексом);

4 - кнопка запуска полного моделирования (в соответствии со всеми методами сокращения трудоемкости (для сравнительного анализа результатов);

5 - поле счетчика выполненных и оставшихся шагов на текущем этапе моделирования;

6 - ряд кнопок оценки эффективности отдельных методов сокращения трудоемкости;

7 - ряд кнопок запуска отдельных методов сокращения трудоемкости;

8 - ряд «чекбоксов», задающих методы сокращения трудоемкости, которые будут рассматриваться при оптимизации (кнопка 3). Неотмеченные методы (на рисунке это два последних) не будут анализироваться;

9 - кнопка запуска прямого моделирования;

10 - кнопки окончания работы приложения - с сохранением результатов и без;

11

. ПО ТТР РТ.ТИГЧЛ

резу.

Л01Снио

рабоТЫ аДаПТйеКО! и ЭЛ1 ОрйТМа.

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

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

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

Для оценки £>* = (сг")' известно, что она распределена по нормальному закону

с математическим ожиданием а и среднеквадратическим отклонением

V п

(6)

где /¿4 - центральный момент четвертого порядка. Предлагается в процессе накопления результатов эксперимента дополнительно оценивать и находить избыточную оценку дисперсии, соответствующую верхней границе доверительного интервала: £>* = £>* +апап, где а0 - коэффициент, соответствующий достаточно близкой к единице доверительной вероятности ро- Представленные ниже результаты вычислительного эксперимента получены с учетом предложенной корректировки оценки дисперсии при рд=0,997.

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

В частности, рассматривались модели со следующими функциями отклика:

5х уг 4 у Зх (7)

- + 50 ,

1 + (*-2 У 1 + СУ-4)1 1 + 0>-8)4 1 + (х - 9)4 где х распределено равномерно в диапазоне [1;10], у - равномерно в диапазоне [1;5]; доверительный интервал был взят равным ±0.05, доверительная вероятность - 0.9973 («три сигмы»);

Р(х,= [(, - 2)2 (у - ЗУ (, - 3)4* -1)2 + + 20зш(^М) ,

где х распределено равномерно в диапазоне [0;4],_у - равномерно в диапазоне [0;6]; доверительный интервал ±0.2, доверительная вероятность - 0.9973.

Вид функций отклика для рассмотренных моделей показан на рисунке 3:

Рисунок 3. а) - модель (7), б) - модель (8).

Для таких моделей проводилось 104 полных циклов моделирования и по прямому методу и в соответствии с каждым методом сокращения трудоемкости.

Таблица 1 - Модель (7).

Метод Nтп гп. пт

Стандартная схема 694306 1.00

Выборка по группам 55282 12.56

Выделение главной части 85416 8.13

Комбинированный 84029 8.26

Мультиметод 1 3050 222.64

Мультиметод 2 2984 232.68

Таблица 2 - Модель (8).

Метод N____ - •чу. Г)

Стандартная схема 331897 1.00

Выборка по группам 175852 1.89

Выделение главной 187942 1.77

части

Комбинированный 182535 1.82

Мультиметод 1 62689 5.29

Мультиметод 2 60717 5.47

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

Для восстановленных законов расчетное значение X варьировалось от 0.439 до 1.066, что соответствует уровню значимости 0.25 в худшем случае.

Кроме того, с использованием соответствующего параметрического критерия проверялась гипотеза о величине вероятности попадания оценки в рассматриваемый до верительный интервал относительно «истинного» (полученного по 107 опытам) значения не менее Рфов=0.9973. Количество выходов оценки за пределы доверительного интервала («трех сигм») составило 26, 26, 28, 23, 8, 20 для модели (7) и 28, 27, 25, 28, 20, 22 для модели (8). Положив уровень значимости при проверке статистической гипотезы о значении доверительной вероятности не меньшей, чем 0.9973 5=0.1, для 10000 опытов получаем нижнюю границу критической области равной 0.9966, что соответствует 34 допустимым выходам за пределы доверительного интервала.

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

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

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

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

начальные значения лилейных и угловых координат. По результатам моделирования оценивалось математическое ожидание конечной ошибки управления (промаха). При различных вариантах выигрыш составил 6-14 раз для метода выборки по группам, 2-13 раз для метода выделения главной части, 2-15 раз для комбинированного метода и 8-30 раз для мультиметодов.

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

Рисунок 4.

Эталонное изображение определяется заранее во время подготовки полётного задания и представляет двухмерный массив Аэ (размерности МхЫ) нормированных значений признака А отражённого сигнала (интенсивности, поляризации и др.), распределённых по координатам Хп 2.

Задача определения местоположения сводится к нахождению значений х0 и г0, при которых измеренный массив Ац размерности тхп и подмножество эталонного массива той же размерности (аГу = А1+х ) максимально идентичны

(рисунок 4). Степень идентичности массивов оценивается по величине нормированного коэффициента корреляции

п т

, Е1<Л/

О _ 1 м М_

пт

или невязки

V м

где М(х) = —-¿¡2х// " математическое ожидание измеренной величины;

пт „1 м

1 " т [ ■ \2

х'. = х, 1 - М(х) - центрированный массив измерений; П(х) = — ХХгС) "

пт »

дисперсия массива измерений; = — " дисперсия

эталонного массива.

По максимальному значению или по минимальному значению N.,

найдем пару (хоДо), которая максимально соответствует измеренному по одному из указанных признаков. Эта пара определяет оценку искомых координат БПЛА, то есть его места на карте.

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

Моделирование проводилось для карты, показанной на рисунке 4.

Параметры карты: размеры - 4000x3000 м.; элемент разрешения - 10x10 м.; зона поиска (красный квадрат на рисунке 5) - 1500x1500 м.; шаг контраста - 5 децибел; размеры осматриваемой локатором зоны - 500x500 м.

При моделировании рассматривалась задача оценки вероятности правильного определения координат отдельно по коэффициенту корреляции и по невязке. Разброс между действительными и измеренными значениями по амплитуде и по обеим координатам приводит к искажению радиолокационной «картинки» и является предпосылкой для неправильного определения координат БПЛА.

Правильным определением координат считалась ошибка не более 50 м. в первом варианте и 15 м. во втором.

Реализация одного опыта может выглядеть, например, как показано на рисунке 5.

В

с

Рисунок 5.

Здесь: 1 центр сканируемой зоны (истинное местоположение БПЛА);

2 - участок, соответствующий максимуму коэффициента корреляции;

3 - участок, соответствующий минимуму невязки;

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

С - массив значений невязки для всего участка, максимум интенсивности соответствует минимуму невязки.

Доверительный интервал для вероятности был принят равным 2%, Доверительная вероятность - 0.95 («две сигмы»).

Результаты моделирования представлены в таблице 3. Здесь: АХ, разброс определения координаты X и 2 отдельных участков; <уА ~ среднеквадратичное отклонение амплитуды; стц - среднеквадратичное отклонение угла ориентации.

Таблица 3.

Параметры опыта Мот л т. »"■> ад Всромшосгь правильного определения координат (±2%)

АХ - ± 20 метров - ± 20 метров ад - 10 децибел По коэффициенту корреляции 59 % (35 %)

По невязке 93 % (54 %)

ДХ - ± 30 метров Дг-±30 метров стА- 10 децибел По коэффициенту корреляции 47% (20%)

По невязке 82 % (36 %)

ДХ - ± 20 метров &2-±20 метров Стд -15 децибел По коэффициенту корреляции 57 % (31 %)

По невязке 90 % (51 %)

ДХ - ± 20 метров Дг - ± 20 метров Стд - 20 децибел По коэффициенту корреляции 55 % (30 %)

По невязке 90 % (49 %)

ДХ - ± 20 метров дг-±20 метров стА- 10 децибел ста-0.1 градуса По коэффициенту корреляции 42% (18%)

По невязке 74 % (31 %)

(в скобках - значения вероятности для допустимой ошибки в 15 метров).

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

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

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

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

1. Реализация всех рассмотренных методов на основе предложенного адаптивного подхода обеспечивает существенное повышение точности или снижение трудоемкости статистического эксперимента.

2. В общем случае не представляется возможным (целесообразным) отдать предпочтение какому-либо одному из рассмотренных методов, в силу существенной зависимости их эффективности от исходной трудоемкости задачи, вида функции отклика, количества случайных факторов и законов их распределения. Так при сокращении исходной трудоемкости задачи до тысяч или сотен опытов преимущества метода выборки по группам или мультиметодов нивелируются в силу нецелесообразности использования исходной выборки объемом более 100-200 опытов.

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

- варьирование начальной выборки (от 100 до 1000 опытов) в зависимости от прогнозируемой трудоемкости задачи;

- варьирование минимально допустимого количества опытов в слое (от 30 до 50) с обязательной корректировкой оценки дисперсии в соответствии с (6);

- окончательный выбор метода решения задачи после получения по начальной выборке оценок требуемого объема для всех рекомендуемых методов;

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

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

Выводы по диссертационной работе:

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

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

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

4 С. нгптк"!пплпигпплшяимнпт комплекса пешены практические задачи — задача оценки конечной ошибки управления БПЛА и задача определения влияния различных условий на вероятность правильного определения координат БПЛА, о чем имеется акт внедрения. Получен большой объем экспериментальных результатов, подтверждающих корректность предложенных расчетных схем и эффективность предложенных методов.

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

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

В приложениях ппивслсны исхотше тексты пгнпвчых чпт/чр»

программного комплекса, функций, реализующих рассмотренные в диссертации

модели, пример файла с описанием пользовательского закона распределения.

ОПУБЛИКОВАННЫЕ ПО ТЕМЕ ДИССЕРТАЦИИ РАБОТЫ

1 Лихолет Н.О. Особенности оптимизации многотактных непрерывно-дискретных систем наведения. // Техническая кибернетика, радиоэлектроника и системы управления. Тез. Докл. V Всеросс. науч. конф. студентов и аспирантов 12-13 октября 2000 г. - Таганрог. 2000. - с. 109.

2 Лихолет Н.О. Адаптивный алгоритм многомерного статистического моделирования. // Вопросы новых информационных технологий в технических системах: Сборник статей. - СПб: БГТУ 2001. - с. 56-60.

3 В.Ю. Емельянов, А.Б. Каледин, Н.О. Лихолет Реализация адаптивного принципа при построении алгоритмов ускоренного статистического моделирования. // Матер. IV всероссийской конф. Молодых ученых «Навигация и управление движением» - Гироскопия и навигация № 3(38), 2002. -с. 127.

4 В. Ю. Емельянов, Н. О. Лихолет. Повышение эффективности методов сокращения трудоемкости статистического моделирования на основе адаптивного подхода. // Мехатроника, автоматизация, управление, №5, 2007. -с. 25-27.

5 Свидетельство об официальной регистрации программ для ЭВМ № 2008613002. Адаптивные алгоритмы сокращения трудоемкости статистического моделирования / В.Ю. Емельянов, Н.О. Лихолет. - 2008.

6 Свидетельство об официальной регистрации программ для ЭВМ №2008613003. Адаптивный алгоритм оптимизации комбинированного метода при статистическом моделировании / В.Ю. Емельянов, Н.О. Лихолет. - 2008.

7 Свидетельство об официальной регистрации программ для ЭВМ №2008613004. Адаптивный алгоритм оптимизации метода выборки по группам при статистическом моделировании / В.Ю. Емельянов, Н.О. Лихолет. - 2008.

8 Свидетельство об официальной регистрации программ для ЭВМ № 2008613005. Адаптивный алгоритм оптимизации метода выделения главной части при статистическом моделировании / В.Ю. Емельянов, Н.О. Лихолет. - 2008.

9 В. 10. Емельянов, Н. О. Лихолет. Возможности сокращения трудоемкости метода статистического моделирования корреляционно-экстремальных систем беспилотных летательных аппаратов. // Известия Российской академии ракетных и артиллерийских наук, № 4(58), 2008. - с. 46-53.

10 В. Ю. Емельянов, Н. О. Лихолет. Адагпивный алгоритм статистического моделирования. // Известия Российской академии ракетных и артиллерийских наук, №4(58),2008.-с. 54-57.

27.04.09 г. Зак. 113-80 РТП ИК «Синтез» Московский пр., 26

ВВЕДЕНИЕ.

1. АНАЛИЗ ПРОБЛЕМЫ СОКРАЩЕНИЯ ТРУДОЕМКОСТИ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ И ОБЗОР МЕТОДОВ ЕЕ РЕШЕНИЯ.

1.1. Теоретические основы.метода статистического моделирования.

1.1.1. Оценки вероятностных характеристик выборки, их вычисление, точность и трудоемкость эксперимента.

1.1.2. Итерационный подход.

1.2. Обзор методов снижения трудоемкости.

1.2.1. Метод выделения главной части.

1.2.2. Метод существенной выборки.

1.2.3. Метод выборки по группам.

1.2.4. Комбинированный метод Пугачева.

1.2.5. Метод критических реализаций.

1.2.6. Метод нестохастического имитационного моделирования.

1.2.7. Сравнительный анализ методов сокращения трудоемкости .34 Выводы по главе 1.и постановка задачи.

2. РАЗРАБОТКА ПРИНЦИПА АДАПТАЦИИ И АЛГОРИТМОВ ОПТИМИЗАЦИИ МЕТОДОВ СОКРАЩЕНИЯ ТРУДОЕМКОСТИ.

2.1. Принцип адаптации методов сокращения трудоемкости статистического моделирования в процессе проведения эксперимента.

2.2. Оптимизация решения в рамках метода выборки по группам

2.3. Оптимизация решения в рамках метода выделения главной части.

2.4. Оптимизация решения в рамках комбинированного метода

2.5. Мулыпметоды.

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

2.7. Оптимизация решения в рамках мультиметода - выборка по группам и комбинированный метод внутри каждой группы. выводы по главе 2.

3. ОБОБЩЕННЫЙ АДАПТИВНЫЙ АЛГОРИТМ И ПРОГРАММНЫЙ КОМПЛЕКС.

3.1. Обобщенный адаптивный алгоритм.

3.2. Программный комплекс, реализующий адаптивные алгоритмы.

3.2.1. Пользовательские функции и программирование конкретной модели.

3.2.2. Интерфейс и получение результатов.

3.2.3. Структура программного комплекса.

3.3. Проверка корректности работы программного комплекса.82 Выводы по главе 3.

4. РЕШЕНИЕ ПРАКТИЧЕСКИХ ЗАДАЧ И РЕКОМЕНДАЦИИ ПО ПРИМЕНЕНИЮ РАЗЛИЧНЫХ МЕТОДОВ.

4.1. Модель динамики движения управляемого летательного аппарата.

4.2. Моделирование определения местоположения БПЛА.

4.2.1. Статистическое моделирование как инструмент подготовки полётного задания для корреляционно-экстремальной навигационной системы.

4.2.2. Признаки сравнения результатов измерения дистанции для определения местоположения БПЛА.

4.2.3. Моделирование определения местоположения БПЛА.¡

4.3. Сравнительный анализ эффективности и применения различных методов сокращения трудоемкости.

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

ВЫВОДЫ.

Одной из наиболее важных задач анализа и синтеза сложных систем является оценка их качества и эффективности с учетом реальных условий функционирования. Никакую реальную систему нельзя считать изолированной, не подверженной влиянию внешней среды. Взаимодействие с внешней средой влияет на поведение и характеристики системы. Существенной особенностью реальных условий является их случайность, или стохастичность. Стохастический подход приходится использовать практически во всех моделях систем, учитывающих реальные условия применения [27,37,69].

Свойство случайности состоит в том, что значения некоторых параметров самой системы или внешней среды или характер их изменения для конкретного опыта или конкретного момента времени непредсказуемы. Однако в условиях многократного повторения таких опытов или на продолжительном интервале времени проявляется некоторая закономерность. Эта закономерность может быть определена (аналитическими преобразованиями, обработкой статистических данных или на основе экспертных оценок) и формализована в виде закона распределения или набора средних статистических характеристик [21,27,43,72,79].

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

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

Аналитические методы восходят к тому времени, когда вычислительные мощности ЭВМ были недоступны и нахождение вероятностных характеристик требовало строгого или приближенного, но аналитического решения. Основные результаты теории аналитических методов исследования стохастических систем содержатся в трудах Б.Г. Доступова, Л.Г. Евланова, И.Е. Казакова, B.C. Пугачева и других видных ученых.

К числу наиболее известных аналитических методов определения статистических характеристик динамических систем относятся спектральный метод [3,6,19,73,71], метод статистической линеаризации [3,6,66], метод динамики средних [40,65], интерполяционный метод [26,65,82], метод сопряженных систем [39,62], методы статистической динамики, опирающиеся на уравнение Фоккера-Планка-Колмогорова [38,39,65] и другие.

К числу существенных особенностей всех аналитических методов о i носятся неизбежность применения приемов построения приближенных моделей: линеаризация, гауссова или функциональная аппроксимация, ортогональное разложении [65,71], или использование в качестве основы достаточно жестких допущений, например о марковском характере случайных процессов в системе [38,75]. Усложнение же моделей по мере развития исследуемых систем и необходимость отказа от упомянутых допущения обусловили построение специальных аналитических методов [ 13,22,39,41], которые также не свободны от приближенности.

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

Универсальным методом исследования стохастических систем является статистическое моделирование. Статистическое моделирование и возникло тогда, когда появились вычислительные ресурсы, позволившие заменить кропотливые вычисления — моделированием задачи на ЭВМ [88]: Таким образом, именно сложность аналитических методов явилась тем, что породило такую широкую область математической статистики, как статистическое моделирование.

Задачей статистического моделирования является получение значений определенных величин с некоторой точностью при помощи проведения .значительного количества экспериментов. Статистическое моделирование используется при разработке сложных систем [10,11,12,15,27,32,37,69,74,85] (в первую очередь - стохастических), при исследовании естественных систем (макро- и микромира), при предсказании их поведения [26,68,74,76]. Во всех таких случаях статистическое моделирование является наилучшим, а зачастую и единственным способом достижения поставленных целей. — создания адекватной структуры и конструкции или же выяснения некоторых неизвестных ранее свойств и деталей поведения систем. Развитию идей и методов статистического моделирования как неотъемлемой части технической кибернетики посвятили свои труды многие отечественные и зарубежные ученые, начиная с А.Н. Колмогорова, Т. Неймана, Р. Шеннона, и в последующие годы Н.П. Бусленко, В.В. Быков, С.М. Ермаков, Дж. Клейнен, В.Н. Пугачев, О.Ю. Сабинин, В.И. Тихонов, A.C. Шалыгин и другие.

Величины и данные, определенные методом статистического моделирования всегда имеют некоторую погрешность, которая тем меньше, чем больше объем выборки — количество проведенных опытов (при прочих равных). Вместе с тем, каждый проведенныйопыт есть затраты - временные, а в случае натурного и полунатурного моделирования еще и значительные материальные [27,37,57]. Таким образом, в области статистического моделирования существует проблема сокращения трудоемкости — то есть уменьшения количества требуемых опытов. Появление современных компьютеров и использование их вычислительных мощностей при статистическом моделировании сильно облегчило решение данной проблемы, но вопрос сокращения трудоемкости по-прежнему остается актуальным. Такие задачи, как моделирование эволюции галактик [91], процесса распада звездных кластеров [90], формирования белков при фотосинтезе [92] требуют существенного времени (до нескольких недель) даже при использовании мощностей суперкомпьютеров. Кроме того, при исследовании и проектировании сложных технических систем важное место занимают полунатурные и физические модели. В силу характерного для них требования - проведения эксперимента в реальном масштабе времени [27,57] - задача сокращения его трудоемкости может решаться только за счет сокращения количества опытов.

Существуют различные способы сокращения трудоемкости при статистическом моделировании. Среди них следует упомянуть метод выделения главной части [16,24,27,35], метод выборки по группам [16,27,35,44], комбинированный метод [10,27,63,64], метод критических реализаций [7,59,89] и т. д. При помощи различных манипуляций с планированием эксперимента данные способы позволяют заметно сократить трудоемкость или достичь меньшей погрешности при сохранении трудоемкости.

Недостаток применения всех этих методов состоит в том, что они требуют экспертного подхода к каждой отдельно взятой задаче [17,34,42,52,63,87]. Таким образом, сохраняется проблема выбора наиболее подходящего метода сокращения трудоемкости и подбор наилучших параметров в рамках данного метода. От правильного и наименее затратного решения этой проблемы зависит в итоге и успешность решения задачи сокращения трудоемкости, то есть эффективность применения метода

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

В связи с этим перспективным путем решения рассматриваемой проблемы представляется организация статистического эксперимента на основе принципа адаптации, развитого в теории систем автоматического управления [1,2,3,46,81].

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

Разработке такого подхода и реализации его в виде семейства алгоритмов и программного комплекса и посвящена настоящая диссертационная работа.

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

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

Основные задачи исследования:

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

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

3. Программная реализация алгоритмов, решающих задачи оптимизации параметров.

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

5. Апробация разработанных метода, расчетных схем и программного комплекса при решении конкретных практических задач.

Объект исследования: . совокупность методов сокращения трудоемкости статистического моделирования.

Предмет исследования: повышение их эффективности.

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

На защиту выносятся следующие основные положения:

1. Принцип адаптации методов сокращения трудоемкости статистического моделирования в процессе проведения эксперимента.

2. Расчетные схемы и алгоритмы оптимизации методов сокращения трудоемкости.

3. Обобщенный адаптивный алгоритм статистического моделирования.

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

5. Рекомендации по применению различных методов сокращения трудоемкости в конкретных условиях.

Научная новизна результатов диссертации состоит в следующем:

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

2. Впервые формализованы и решены задачи оптимизации параметров основных методов сокращения трудоемкости статистического моделирования.

3. Разработаны два мультиметода, предусматривающие одновременное применение двух совместимых стандартных методов, решены задачи их оптимизации.

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

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

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

Практическая ценность результатов диссертации состоит в' следующем:

Обобщенный адаптивный алгоритм статистического моделирования обеспечивает возможность сокращения времени разработки сложных стохастических систем в различных областях при оценке вариантов их построения методом статистического моделирования. Предлагаемые алгоритмы и их программная реализация позволяют достичь выигрыша в трудоемкости 20-30 раз и выше по сравнению со стандартной схемой и до 2-4 раза и выше по сравнению с достигнутыми ранее результатами для известных способов сокращения трудоемкости. Сформулированы практические рекомендации по применению методов сокращения трудоемкости статистического моделирования и по мерам обеспечения корректности получаемых результатов.

Апробация работы:

Основные результаты диссертационного исследования докладывались и обсуждались на X международной конференции «Региональная информатика — 2006», IV конференции молодых ученых "Навигация и управление движением" (ЦНИИ "Электроприбор" СПб, 2002) и на семинарах кафедры «Систем обработки информации и управления» БГТУ «ВОЕНМЕХ» им. Д.Ф. Устинова и ОАО «Концерн «Гранит-Электрон».

Внедрение результатов:

Результаты диссертационного исследования внедрены в ОАО «Концерн «Гранит-Электрон» в рамках программы работ с целью совершенствования технических характеристик систем управления, а также в учебном процессе БГТУ «ВОЕНМЕХ» им. Д.Ф. Устинова, о чем имеются соответствующие акты.

Публикации. По теме диссертационной работы опубликовано 10 научных работ, из них — 4 статьи (1 статья в издании из перечня, рекомендованного ВАК), 4 свидетельства об официальной регистрации программ.

Структура и объем работы:

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

выводы

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

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

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

4. С использованием программного комплекса решены практические задачи - задача оценки конечной ошибки управления БПЛА и задача определения влияния различных условий на вероятность правильного определения координат БПЛА, о чем имеется акт внедрения. Получен большой объем экспериментальных результатов, подтверждающих корректность предложенных расчетных схем и эффективность предложенных методов.

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

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

1. Александров А.Г. Оптимальные и адаптивные системы. — М.:. Высшая школа, L989.-263 с.

2. Андриевский Б.Р., Фрадкое A.JI. Избранные главы теории автоматического управления. — СПб: Наука, 1999. 467 с.

3. Астапов Ю.М., Медведев B.C. Статистическая теория систем автоматического регулирования и управления. — М.: Наука, 1982. 304 с.

4. Белецкий В.К., Юрьев А.Н. Корреляционно-экстремальные методы навигации. М: Радио и связь, 1982. - 256 с.

5. Белоглазое И.Н., Тарасенко В.П. Корреляционно-экстремальные системы. М: Сов. радио, 1974. 392 с.

6. Бесекерский В.А., Попов Е.П. Теория систем автоматического управления. -М.: Наука, 1975.-768 с.

7. Богданов B.C., Яковлев Н.П. Об одном приближенном методе вычисления вероятностей при исследовании нелинейных систем. Изв. АН СССР, Техническая кибернетика, №5, 1975. с. 97-101.

8. Боднер В.А. Системы управления летательными аппаратами. — М.: Машиностроение, 1973. 506 с.

9. Большее Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 1983.-416 с.

10. Борисов Ю.П., Цветное В.В. Математическое моделирование радиотехнических систем и устройств. М.: Радио и связь, 1985. - 177 с.

11. Бусленко В.И. Автоматизация имитационного моделирования. М.: Наука, 1976.-296 с.

12. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1978. 400 с.

13. Бухалев В.А. Анализ точности динамических систем со случайной структурой, описываемой условной марковской цепью. Изв. АН СССР, Техническая кибернетика, № 2, 1976, стр. 179-187.

14. Буч Г., Рамбо Д., Джекобсон А. Язык иМЬ. Руководство пользователя. М.: ДМК пресс; СПб.: Питер, 2004. 432 с.

15. Быков В.В. Цифровое моделирование в статистической радиотехнике. М.: Сов. радио, 1971. 328 с.

16. Васильев Д.В., Сабинин О.Ю. Ускоренное статистическое моделирование систем управления. Л.: Энергоатомиздат 1987. — 136 с.

17. Васильев Д.В., Сабинин О.Ю. Сабинина Н.В. Метод организации статистического моделирования сложных систем автоматического управления. Электричество 1977 №1. с. 9 12.

18. Вентцелъ Е.С. Теория вероятностей. М.: Наука, 1964. 564 с.

19. Виленкин С.Я. Статистические методы исследования стационарных процессов и систем автоматического регулирования. — М.: Советское радио, 1967.-200 с.

20. Войхонский В.Л., Сабинин О.Ю. Алгоритм экономичной организации статистического моделирования сложных систем обработки информации и управления.//Известия высших учебных заведений. Приборостроение. 1973. Т. 16. №9. с. 32-36.

21. Ганин М.П. Решение прикладных задач теории вероятностей: математическая статистика. Л.: ВМОЛУА, 1977. 602 с.

22. Ганэ В.А., Куклев Е.А., Степанов В.Л. Системы управления при скачкообразных воздействиях. Минск: Наук и техника, 1985. — 216 с.

23. Гнеденко Б. В., Хинчин А.Я. Элементарное введение в теорию вероятностей. М.: Наука, 1970. 168 с.

24. Григорьева О.В. Прием понижения дисперсии в методе Монте-Карло. Ученые записки Казанского университета. 1966. Т. 125 №6. с. 79 — 81.

25. Джонсон Н., Лион Ф. Статистика и планирование эксперимента в технике и науке: Методы планирования эксперимента: Пер. с англ. М.: Мир, 1981. — 516 с.

26. Евланов Л.Г., Константинов В.М. Системы со случайными параметрами. М.: Наука, 1976.-576 с.

27. Емельянов В.Ю. Методы моделирования стохастических систем управления. С.-Пб.: БГТУ, 2004. 134 с.

28. В. Ю. Емельянов, Н. О. Лихолет. Повышение эффективности методов сокращения трудоемкости статистического моделирования на основе адаптивного подхода. // Мехатроника, автоматизация, управление, №5, 2007.- с. 25-27.

29. Ермаков С.М. Математическая теория планирования эксперимента. М.: Наука, 1983.-392 с.

30. Ермаков С.М. Метод Монте-Карло и смежные вопросы. М., Наука, 1975.- 472 с.

31. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. М.: Наука, 1982.-296 с.

32. Жкглявский A.A., Жилипскас А.Г. Методы поиска глобального экстремума. М.: Наука, 1991. — 248 с.

33. Зарубгш B.C. Математическое моделирование в технике: учебник для ВУЗов. М.: Изд-во МГТУ им. Н. Э. Баумана, 2003. - 496 с.

34. Казаков И.Е. Вероятностный анализ смены режима работы автоматической системы. Автоматика и телемеханика, №1-, 1977, с. 23-29.

35. Казаков И.Е. Статистическая динамика систем с переменной структурой. -М.: Наука, 1977.-416 с.

36. Казаков И.Е. Статистическая теория систем управления в пространстве состояний. М.: - Наука, 1975. - 432 с.

37. Казаков И.Е., Доступов Б.Г. Статистическая динамика нелинейных автоматических систем. М.: Физматгиз, 1962. - 332 с.

38. Клейнен Дж. Статистические методы в имитационном моделировании. Вып.1, 2.- М.: Статистика, 1978.-221 с, 335 с.

39. Коваленко H.H., Филлипова A.A. Теория вероятностей и математическая статистика. М.: Высшая школа, 1973. 368 с.

40. Кокрен У. Методы выборочного исследования. — М.: Статистика, 1976. — 440 с.

41. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров: Пер. с англ. М.: Наука, 1977. 832 с.

42. Справочник по теории автоматического управления / Под. ред. A.A. Красовского. — М.: Физматлит, 1987. — 712 с.

43. Красовский A.A., Белоглазое И.Н., Чигин Г.П. Теория корреляционно-экстремальных навигационных систем. — М.: Радио и связь, 1979. 448 с.

44. Латышева Т.В., Сабинин О.Ю. Алгоритм ускоренного статистического моделирования для оценки нескольких вероятностных характеристик сложных систем. М.: Изд-во АН СССР, 1977. с. 44 47.

45. Лебедев A.A., Карабанов В.А. Динамика систем управления беспилотными летательными аппаратами. М.: Машиностроение, 1965. 528 с.

46. Лебедев A.A., Черноброекин JJ.С. Динамика полета: М.: Оборонгиз, 1962.- 549 с.

47. Лецкий Э.К. Планирование эксперимента в исследовании технологических процессов. М.: Мир, 1977. — 552 с.

48. Лихолет И.О. Адаптивный алгоритм многомерного статистического моделирования. // Вопросы новых информационных технологий в технических системах: Сборник статей. — СПб: БГТУ 2001. — с. 56-60.

49. Налимов В. В. Теория эксперимента. — М.: Наука, 1971. - 208 с.

50. Пантелеев A.B., Летова Т.А. Методы оптимизации в примерах и задачах.- М.: Высшая школа, 2002. 544 с.

51. Петров Г.М., Лакунин Н.Б., Бартолъд Э.Е. Методы моделирования систем управления на аналоговых и аналого-цифровых вычислительных машинах. М.: Машиностроение, 1975. -255 с.

52. Подоплёкии Ю.Ф. Андриевский В.Р., Выбор критических реализаций и его сочетание с другими методами ускорения статистического эксперимента. Информационно-управляющие системы. С.-Пб., 2005. Вып. 2 (15).— С. 13-15.

53. Подоплёкин Ю.Ф. Зимин С.Н., Выбор критических реализаций как метода ускорения статистического моделирования. Известия Российской академии ракетных и артиллерийских наук. М., 2007. Вып. 3 (53). —С. 3-5.

54. Подоплёкин Ю.Ф., Шаров С.Н. Некоторые особенности использования бортового радиолокатора для увеличения точности определенияместоположения беспилотного летательного аппарата. Известия PAP АН, выпуск 2, 2004. С. 66-73.

55. Полляк Ю.Г. Вероятностное моделирование на электронных вычислительных машинах. — М.: Советское радио. 1971. — 400 с.

56. Статистические методы в проектировании нелинейных систем автоматического управления / Под ред. Попова Е.П. и Доступова Б.Г. — М.: Машиностроение, 1970. — 386 с.

57. Пугачев В.Н. Комбинированные методы определения вероятностных характеристик. М.: Советское радио. 1973. — 256 с.

58. Пугачев В.Н. Определение характеристик сложных систем методом статистического моделирования с использованием результатов аналитического исследования.// Известия АН СССР. Техническая кибернетика. №6. 1970. с. 41 -47.

59. Пугачев B.C., Казаков И.Е., Евланов Л.Г. Основы статистической теории автоматических систем. — М.: Машиностроение, 1974. -400 с.

60. Пупков К.А. Статистический расчет нелинейных систем автоматического управления. — М.: Машиностроение, 1965. — 404 с.

61. Розенвассер E.H., Юсупов P.M. Чувствительность систем управления. М.: Наука. 1981.-440 с.

62. Рыжиков Ю.И. Имитационное моделирование: теория и технологии. -СПб: КОРОНА принт, 2004. 384 с.

63. Сабинин О.Ю. Статистическое моделирование технических систем. СПб.: СПбГЭТУ, 1994. 64 с.

64. Сабинина Н.В. О двух методах повышения точности результатов статистического моделирования систем управления. Морское приборостроение, серия VI, вып. 3, 1973. с. 117 122.

65. Свешников A.A. Прикладные методы теории случайных функций. М.: Наука, 1968.-464 с.

66. Смирнов Н.В., Дунин-Барковский И.В. Курс теории вероятностей и математической статистики для технических приложений. М.: Наука, 1965. — 510 с.

67. Солодовников В. В. Статистическая динамика линейных систем автоматического управления. М.: Физматгиз, 1960. — 655 с.

68. Советов Б.Я., Яковлев С.А. Моделирование систем. М.: Высшая школа, 1985.-271 с.

69. Тараканов К.Е., Овчаров Л.А., Тырышкин А.Н. Аналитические методы исследования систем. — М.: Советское радио, 1974. 240 с.

70. Тихонов В.И. Статистический анализ и синтез радиотехнических устройств и систем. — М.: Радио и связь, 2004. — 608 с.

71. М.А. Тынкевич. Численные методы анализа. Кемерово: КузГТУ, 1997. -122 с.

72. Уайльд Д.Дж. Методы поиска экстремума. М.: Наука, 1967. 268 с.

73. Уилкс С. Математическая статистика: Пер с англ. М.: Наука, 1967. — 632 с.

74. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. М.: Физматгиз, 1962. 607 с.

75. Фрадков А.Л. Адаптивное управление в сложных системах. — М.: Наука, 1990.-296 с.

76. Чернецкий В.И. Анализ точности нелинейных систем управления. — М.: -Машиностроение, 1968. —246 с.

77. Шалыгин A.C., Палагин Ю.И. Прикладные' методы статистического моделирования. JL: Машиностроение, 1986. — 320 с.

78. Шапорев С.Д. Прикладная статистика. СПб: БГТУ, 2003. - 256 с.

79. Шаракшаиэ, A.C., Железное И.Г., Ивницкий В.А. Сложные системы. — М.: Высшая школа, 1977. — 248 с.

80. Шаров СЛ. Информационные управляющие системы беспилотных летательных аппаратов СПб: БГТУ, 2007. - 256 с.

81. Шеннон Р. Имитационное моделирование систем искусство и наука. -М.: Мир, 1978.-418 с.

82. Метод статистических испытаний (метод Монте-Карло)/ Под ред. Ю.А. Щрейдера. М.: Физматгиз, 1962. — 332 с.

83. Яковлев Н.П., Богданов B.C., Куликов Ю.П. Способ уменьшения трудоемкости метода статистических испытаний при исследовании нелинейных систем автоматического управления. Морское приборостроения, сер VI, вып. I. 1973. с. 126 132.

84. Н. Baumgardt, P. Kroupa. A comprehensive set of simulations studying the influence of gas expulsion on star cluster evolution. Monthly Notices of the Royal Astronomical Society 380 (4) (2007) 1589-1598, D01:10.1111/j.l365-2966.2007.12209.xj

85. Sergey Mashchenko, James Wadsley, and H. M. P. Couchman. Stellar Feedback in Dwarf Galaxy Formation. Science 11 January 2008 319: 174-177; DOI: 10.1126/science.l 148666.

86. Свидетельство об официальной регистрации программ для ЭВМ №2008613002. Адаптивные алгоритмы сокращения трудоемкости статистического моделирования / В.Ю. Емельянов, Н.О. Лихолет. —2008.

87. Свидетельство об официальной регистрации программ для ЭВМ №2008613003. Адаптивный алгоритм оптимизации комбинированного метода при статистическом моделировании / В.Ю. Емельянов, Н.О. Лихолет. — 2008.

88. Свидетельство об официальной регистрации программ для ЭВМ № 2008613004. Адаптивный алгоритм оптимизации метода выборки по группам при статистическом моделировании / В.Ю. Емельянов, Н.О. Лихолет 2008.

89. Свидетельство об официальной регистрации программ для ЭВМ № 2008613005. Адаптивный алгоритм оптимизации метода выделения главной части при статистическом моделировании / В.Ю. Емельянов, Н.О. Лихолет. 2008.