Поиск минимума функции методами исключения интервалов.

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

(13)

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

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

При практической реализации методов поиска экстремума функции выделяют два этапа:

- этап установления границ интервала, на котором реализуется процедура поиска границ достаточно широкого интервала, содержащего экстремум функции;

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

На первом этапе обычно используют эвристические методы поиска. В качестве примера приведем здесь эвристический метод, предложенный Свенном. Согласно этому методу (k+1)-ая пробная точка определяется по рекуррентной формуле :

(14)

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

Знак D определяется путем сравнения значений функции , и . Если

, (15)

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

, (16)

то точка минимума х* расположена между и и поиск граничных точек закончен.

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

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

Определение требуемого размера выборки.

К наиболее важным задачам при проведение имитационного эксперимента относится задача определения требуемого объема выборки. Следует заметить, что поскольку имитационная модель носит стохастический характер, то точность полученных результатов существенно зависит от объема выборки. Известно также, что многие методы анализа стохастических систем базируются на предположении о том, что распределение случайных величин в таких системах подчиняется нормальному закону, т.к. на основании применения центральной предельной теоремы теории вероятности, отклики в таких системах представляют собой некоторую совокупность “больших” чисел на отклик сложной системы. Это приводит к тому, что отклик носит нормальное распределение. На основании этого эффекта и производится выбор требуемого объема выборки. Оцениваемым параметром, в этом случае, является среднее значение и среднеквадратическое отклонение. При этом используют правило метода доверительных интервалов, в котором предполагается задание точности по двум параметрам:

{d_n - m_n} и {b_n - s_n (D =s_n² )}.

Для некоторого отклика модели для определения объема выборки необходимо задавать d_n, b_n и a (a - 1), где a - уровень значимости.

Требуемый объем выборки должен удовлетворять условиям:

Y_n,k - d_n £ M_n £Y_n,k + d_n,

D_n,k - b_n £ D £ D_n,k + b_n.

Исследователь обычно задает число опытов слишком большое, однако, на практике рекомендуется следующий алгоритм выбора объема выборки: задают N₁ = 5, где N₁ - объем выборки и первая итерация заключается в подсчете

Вторая итерация: для очередного номера N выходных сигналов определяют точность b_n1, d_n1 (d_n1 £ d_n, b_n1 £ b_n при уровне значимости a) и проводят эксперимент. Эта оценка может быть оценена тремя способами:

1 способ.

Если объем выборки N₁ < 30, то для вычисления доверительного интервала можно воспользоваться Т - статистикой, из которой d_n1 определяется следующим образом:

В этой формуле t_кр - значение, определяемое из таблицы распределения Стъюдента или Т-статистики аналогично вопросам адекватности по уровню значимости a (1 - a) и по числу степеней свободы g = N₁ -1.

2 способ.

Если объем выборки N₁> 30, то для вычисления доверительного интервала используют двухстороннюю статистику нормированного нормального распределения.

(4)

Z _a/2 = t, Z _a/2 - определяют также из таблиц по заданному уровню значимости.

3 способ.

Если нормальность отклика Y_n,k заранее установить нельзя, то применяется неравенство Чебышева, в котором предполагается, что N₁ > 30.

где

Y_n - среднее значение выборки N1,

m_n - математическое ожидание,

h - константа, определяющая среднеквадратическое отклонение, которое удовлетворяет исследованию, как правило, n > 1 , тогда доверительный интервал:

или при оценке дисперсии:

Р{(1 - b_n) s_n² £ D_n £ (1+b_n) s_n²} = 1 - a,

Третья итерация связана с оценкой полученных значений b_n1, d_1n с заданными: d_n1 £ d_n, b_n1 £ b_n.

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

Четвертый шаг итерации связан с увеличением начальной выборки N₁ = N₁ +1. Затем осуществляется переход к первому шагу.

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

Пример1.

Рассчитать необходимый объем выборки N₁ для достижения оценки математического ожидания с заданной точностью d_n = 3.5 и доверительной вероятностью р = 0.95. Известны оценки двух дисперсий: D₁ = s₁² = 295, D₂ = s₂² = 547 вычислены по двум выборкам малого объема из одной генеральной совокупности.

Процедура нахождения объема выборки может быть следующей:

1.Вычисляется среднее значение дисперсии:

s₀² = (295 + 547)/2 = 421.

2.По заданной доверительной вероятности р = 0.95 определяют из специальных таблиц для нормального распределения значение интеграла: 1/(2p) ò⁰_{ti e}-Z²/2 dz, ti - квантин нормального распределения, t = 1.96 (при =0.95), р/2 = 0.475.

3. t = Z_a/2, j₀(t) = p/2.

4. Необходимый объем выборки в этом случае берется по четвертой формуле:

N₁ = (t²D_n)/d².

Сведем полученные результаты в таблицу:

Dn=D0	d	p	Ф0 (t)	t	N1
421	3.5	0.95	0.475	1.96	132

Пример2.

Предположим, что надо оценить среднесуточный выход продукции с вероятностью р = 0.95 так, чтобы ошибка точности представления была ± 4 тонны. Пусть известен допустим, размер колебаний выхода продукции s_n =80т. Требуется определить N₁.

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

m_x = (x_max + x_min) /2,

s_x = (x_max + x_min)/2Ö3, т.к. x _min = 0, то m_x = 40 тонн, s_x = 80/2Ö3.

2Ö3 = 4, s_x = 20.

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

m_x - d_n £ Y_n £ m_x + d_n.

Если известен допустимый размах выходной составляющей, то дисперсия D = s² = 400, т.к. s = 20.

Из формулы (4) N₁ = (s´t²)/d², где t = 1.96, т.к. р = 0.95 (a=0.95).

Пример 3.

Допустим, мы не знаем максимального размаха выходной переменной, а значит не знаем среднеквадратического отклонения. Тогда задача формулируется следующим образом: какая выборка обеспечит оценку с вероятностью 0.95 в пределах m_n ± s/4? В этом случае выбирают d_n = s /4 при t = Za/2 = 1.96 и

N₁ = (1.96 s²)/ (s/4)² = 61.

Вывод: размер выборки N₁ можно определить и не зная s, но задавшись оценкой d_n = s/4 (при равномерном распределении!).

Пример 4.

Рассчитать количество реализаций N₁ при моделировании системы, если в качестве показателя эффективности используется вероятность р при достоверности q = 0.95. В этом случае уровнем значимости a = 1 - q = 0.05. t = 1.96, d_n = 0.01, 0.02, 0.05.

Рассмотрим N₁ = (s´t²)/d².

Для доказательства используют следующие выражения:

М | x | = x₁p + x₂(1-p),

D | x | = (x₁- М | x |)² p + (x₂ - М | x |)²(1-p), где

х1 - может принимать значения 1 с вероятностью р, а

х2 - принимает значение 0 с вероятностью (1- р), т.е. с помощью х1 и х2 оценивается выполнение некоторых событий.

М | x | = 1p + 0(1-p),

D | x | = (1 - р)² p + (0 - р)²(1-p),

D = p(1-p),

N₁ = [t² ´ p (1-p)]/d².

Проведем два вычисления:

р = 0.1 и d = 0.01, d = 0.05.

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

Задачи имитационных экспериментов.

Условно задачи имитационного моделирования можно разделить на три типа:

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

- Второй тип задач основан на базе дисперсионного и регрессионного анализа (определение влияния параметров на выходные переменные).

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

Определение длительности переходного процесса.

Статистическая информация, собираемая в модели, имеет смысл в том случае, если процесс носит стационарный характер. Стационарность процесса определяет сам исследователь. Можно также воспользоваться критерием Вилксона: с интервалом времени Dt проводятся сравнение средних длин очереди l _k и l _k’ (для одной компоненты, а лучше для всех компонент). Проверяется гипотеза однородности выборок: {l _k}, {l _k’}.

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

1 способ: использование длинных прогонов, увеличивающих модельное время t₀.

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

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

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

Чувствительность имитационной модели устанавливается в результате оценки DY / DX. Если при незначительном изменении DX DY изменяется существенно, то данный параметр определяет чувствительность модели. Модель считается чувствительной по отношению к этому параметру. Чувствительность проверяется по DY / DG. Анализ поведения системы при колебаниях X и G позволяет выявить основные чувствительные параметры на модель и, как правило, вопросы чувствительности модели решаются путем корректировки алгоритмов имитационного моделирования в сторону упрощения.

Основные стандартные процедуры выполняются в этом случае следующим образом:

Чувствительность модели определяется по паре {d_Xq , d_Yq }, которая показывает на сколько процентов может изменяться отклик модели при увеличении q - й компоненты на d_Xq ^%. Эти исследования выполняются для каждой компоненты входного вектора X или G.

Исследование свойств имитационной модели.

Наиболее важными процедурами этого блока исследования модели являются:

* оценка погрешности имитации,

* определение длительности переходного процесса в имитационной модели,

* оценка чувствительности выходных откликов от рабочей нагрузки.

Рассмотрим некоторые из вышеназванных оценок, в частности, оценку погрешности. Она существенно зависит от применения генераторов случайных чисел. Известно, что каждый из них использует определенный базовый генератор, числа с выхода которого потом преобразуются для создания псевдопоследовательности величин с заданным законом распределения. Установлено, что для различных прогонов имитационной модели при одних и тех же значениях Q и F результаты Y будут отличаться, если в модели используется разные генераторы случайных чисел (RN$1 ¸ RN$8 - генераторы случайных чисел в GPSS).

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

Калибровка имитационной модели.

За калибровку имитационной модели отвечает блок 20 технологической структуры этапов моделирование. Обращение к этому блоку возникает в том случае, если модель неадекватна объекту. В этом случае производят калибровку модели, для чего корректируют алгоритм модели : j (Х, G), Q Î X. Калибровку модели осуществляют по трем направлениям:

1. Глобальные структурные изменения (добавляют программы процессов, изменяют события в процессах).

2. Локальные изменения в модели. В этом случае производят замену компонент модели более точными, т.е. изменяют параметры компонентов модели.

3. Изменение калибровочных параметров. Те параметры, которые наиболее существенно влияют на изменение выходных характеристик модели.

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

1. Сравнение распределений функций на объекте и модели.

E_1n = Y* - Y - min.

E_1n = {E_1n}

Более эффективно осуществляется первый этап по функциональному распределению вероятностных значений: F(Y_Qn*) и F(Y_Q).

| F(Y_Qn*) - F(Y_Q) | = E_2n ,

E_2n определяется по критерию Колмогорова (Д - статистика) при использовании критерия Пирсона. Аналогичным образом, обращаются к соответствующей таблице по коэффициентам значимости и числу степеней свободы:^a_L-1, где L - число интервалов функции распределения. Находят критическое значение c и сравнивают с E_2n. Если E_2n £ c² , то различие между функциями распределения незначительно. Проверяя различие между функциями распределения по всем компонентам, исследователь определяет степень улучшения модификации компонентов модели, при этом предполагается, что модификация выполняется относительно структуры или замены главных составляющих модели.

2. Связан с балансировкой модели. Допустим, было зафиксировано некоторое среднее значение на объекте, был сделан некоторый натурный эксперимент на объекте. Y * = {y _Qnk*} на каждой итерации будет меняться значение параметров Q модели аналогично эксперименту на объекте. Q = {yQnk} - фиксированная выборка на модели. Определяется среднее значение квадрата разности компонент отклика:

Для нахождения минимума составляют регрессионные уравнения относительно E_3n:

E_3n = b₀ + b₁Q₁ + b₂Q₂ + …+ b_q Q_q .

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

3.Оптимизация модели.

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

Общая структура калибровки.

Адекватность имитационного моделирования.

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

Y* = F*(X*, G*) (1).

Пусть известен отклик реальной системы Y* при нагрузке G* и управляющих изменяющихся параметров Q, а функция (1) пока еще плохо изучена из-за сложности объекта. Модель представляет собой:

Yk = F (Qk, Gk), k=1,…, N, где

k - номер, N - число опытов. Проверку на адекватность выполняют, в основном, тремя способами:

n по средним значениям откликов модели и системы,

n по дисперсиям откликов моделей от среднего значения откликов системы,

n по максимальному значению абсолютных отклонений откликов модели от откликов системы.

В первом способе адекватность оценивается по близости средних значений каждой N- й компоненты откликов модели. Y = Y₁, Y₂,…, Y_N. Проводят N₁ опытов на реальном объекте и N₂ опытов на модели. Обычно N₁ = N₂. Часто N₁ << N₂.

Основной проверкой в этом случае является разность:

g = N₁ + N₂ - 2 - число степеней свободы.

В этом способе используется таблицы t статистики, в которых по двум параметрам определяют оценку t_кр. В качестве параметров используют {g,a}, a - уровень значимости. Уровень значимости лежит в пределах от 0 до 1 и определяется как 1 - р. Если р = 0.95, то a = 0.05 (5). Значение D₀ в выражении (4) считается статистически независимым, поэтому можно записать их в виде:

если tn £ t_крит, найденного из таблицы по a и g, то гипотеза о близости средних значений n-x компонент для откликов модели и системы принимается, т.е. модель считается адекватной объекту. При этом следует иметь в виду, что близость откликов должна соблюдаться по всем выходным параметрам, если хотя бы одна из переменных не удовлетворяет заданному неравенству - модель считается неадекватной.

Во второй способе для каждой n - й компоненты откликов проверяется гипотеза о значимости оценок дисперсий, которые можно определить из уравнений (4), (5) для модели и объекта. Оценку дисперсии отклонения откликов модели от среднего значения можно получить при проведении натурных экспериментов в соответствии со следующим выражением:

Для сравнения дисперсий составляют F - cтатистику:

F = D_0N /D_N* (9).

По a и g находят F_крит. Если F<F_крит, то модель адекватна. Если F>F_крит хотя бы по одному параметру - модель неадекватна.

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

{y_nk} - из модели,

{y_nk*} - из объекта, к - номер эксперимента.

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

Пример. Рассмотрим первый и второй способы проверки адекватности.

Первый способ:

	1	2	3	4	5	Ср.зн.	Диспер	D0	t a g
y1/y1*	18/19	15/20	18/17	17/16	17/18	17/18	1,5/2.5	2	1.12
y2/y2*	19/20	23/24	19/23	22/22	22/21	21/22	3.5/2.5	3	0.91

g = 5 + 5 - 2 = 8,

N₁ = N₂ = 5, a = 0.05, t_крит. = 2.31, t < t _крит., следовательно, модель адекватна.

Второй способ:

	1	2	3	4	5	Ср.зн.	D0n/Dn*	F
y1/y1*	18/19	15/20	18/17	17/16	17/18	17/18	2,75/2.5	1.1
y2/y2*	19/20	23/24	19/23	22/22	22/21	21/22	4.75/2.5	1.9

Находим Fкрит. для второго способа.

F = D_0n/D_n* = 2.75/2.5 =1.1;

F = D_0n/D_n* = 4.75/2.5 =1.9;

g₁ = g₂ = N₁ = N₂ = g = 5 , a = 0.05.

Используя таблицу Фишера, определяем F_крит. = 5.1, F < F _крит. - модель будет адекватна.

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

Вопросы испытания и эксплуатации имитационных моделей.

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

- исследование,

- составление планов,

- эксплуатация.

Любой объект исследования можно представить как:

На реальную систему воздействуют переменные G*, которые можно изменять, но нельзя ими управлять. Параметр Х* можно менять в ходе натурных экспериментов. Выходные параметры Y* можно измерять:

Y* = F*(X*, G*) (1).

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

Y = F( X, G) (2).

Параметры Х в модели могут выбираться произвольно исследователем, а параметры G могут принимать только те значения, которые характерны для данного объекта и соответствующих задач моделирования. (Позиция G - концептуальное описание) G Î G* - принадлежит в ограниченном пространстве. Для выбора G, как правило, измеряют фактические G*, которые называют еще внешней нагрузкой. Результаты поведения системы Y_Q при заданных значениях определенной выборки из Х:

Q Î X, J_Q = F (Q, G), Q ® min.

Испытания имитационной модели (блок 17) начинается с задания исходной информации и тогда, перед исследователем встает вопрос, где взять эту информацию. Как правило, информацию о G* берут или из прототипа, или из натурных экспериментов на объекте, или благодаря аппроксимации полученных результатов при натурных экспериментах. Затем, в блоке 16 выполняют верификацию, которая происходит в соответствии с комплексной отладкой при заданных значениях G*, Q. Следует при этом обратить внимание на то, что модели могут создаваться для существующих и проектирующихся систем. В первом случае модель реализовать значительно проще, а поэтому эти модели создаются более точными, чем во втором случае. Точность этих моделей осуществляется в результате проверки адекватности модели (блок 19). При построении моделей проектируемых систем можно рекомендовать упрощение проекта. Адекватность модели в этом случае выполнить практически нельзя. Адекватность осуществляется благодаря калибровке самой модели (блок 20). Блок 21 связан с исследованием свойств имитационной модели, которое осуществляется следующим образом:

Ôоценивается погрешность моделей,

Ôопределяется минимальное модельное время при заданной точности,

Ôоценивается устойчивость выходных результатов Y при различных X и G модели,

Ôоценивается чувствительность выходных параметров к изменениям Y.

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