Software generators in the GPSS WORLD environment for distributions-probability mixtures with qualityassessment results

Full Text

Введение

Имитационному моделированию и, в частности, универсальной системе дискретно-событийного моделирования GPSS WORLD, которая широко используется при моделировании систем массового обслуживания и производственных систем, посвящено много работ [3–9]. Система GPSS WORLD включает множество библиотечных программ, в том числе генераторы псевдослучайных последовательностей для различных законов распределений.

В теории массового обслуживания востребованы законы распределений с широким диапазоном коэффициента вариации случайной величины, такие как гиперэрланговский или гиперэкспоненциальный. Как было отмечено в [1; 2], таких генераторов в системе моделирования GPSS WORLD нет, как их нет и в других системах имитационного моделирования. В [1; 2] представлены эти генераторы в качестве имитационных моделей систем массового обслуживания (СМО) HE₂/M/1 и H₂/M/1 соответственно на основе имеющихся в библиотеке GPSS WORLD генераторов.

Постановка задачи

В статье приводятся результаты применения статистических тестов к функционированию имитационных моделей систем HE₂/M/1 и H₂/M/1 в GPSS WORLD для оценки качества программных генераторов гиперэрланговского и гиперэкспоненциального распределений. Выводы об адекватности имитационных моделей систем HE₂/M/1 и H₂/M/1 делаются на основе статистического теста Пирсона, сопоставления теоретических и статистических моментов указанных распределений, а также сопоставления результатов имитации с известными результатами численно-аналитических моделей указанных систем в Mathcad.

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

Проверка гипотезы о гиперэрланговском распределении псевдослучайных последовательностей (ПСП) на примере СМО HE₂/M/1

Приведенную в [1] имитационную модель для СМО HE₂/M/1 дополним блоками GPSS WORLD с приведенными ниже комментариями для фиксации длин интервалов между соседними требованиями во входящем потоке для последующего построения по ним статистического ряда и гистограммы распределения интервалов поступлений. После этого представим полную имитационную модель уже без комментариев.

Для прогона имитационной модели установим следующие исходные данные: возьмем коэффициент загрузки $\rho ={\overline{\tau }}_{\mu }/{\overline{\tau }}_{\lambda }=\mathrm{0,9}$, коэффициент вариации интервалов поступлений $c_{\lambda }=2$ и единичное время обслуживания ${\overline{\tau }}_{\mu }=1$. Отсюда параметры гиперэрланговского распределения $p=\frac{1}{2}+\sqrt{\frac{2(1+c_{\lambda }^2)-3}{8(1+c_{\lambda }^2)}}=\mathrm{0,918}$, $1-p=\mathrm{0,082}$, ${\lambda }_1=\mathrm{3,306}$, ${\lambda }_2=\mathrm{0,294}$.

Тогда средние значения для формирования первой и второй фаз гиперэрланговского распределения будут равны ,  единиц времени. Ширину разряда для статистического ряда установим равной единице, число испытаний в прогоне возьмем N=500. Таким образом, не проводя многочисленных экспериментов мы выбрали небольшой объем выборки, равный 500, с тем, что статистический критерий Пирсона придется считать вручную. Это связано с тем фактом, что в автоматизированных программных продуктах нет рассматриваемых законов распределений. Фактически это означает, что мы берем данные для переходного режима функционирования СМО. Для установившегося режима необходимо провести несколько сотен тысяч испытаний в одном прогоне. Результаты прогона с выходными данными для статистического ряда и гистограммы представлены на рисунках 1 и 2.

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

Рисунок 2. Полученная гистограмма распределения HE₂

Окончательная имитационная модель тогда будет иметь вид:

10 InterArr TABLE X$Arr,1,1,16

20 INITIAL X$Time,0

30 P_1 EQU 0.082

40 P_2 EQU (1-P_1)

50 T_1 EQU 3.401

60 T_2 EQU 0.303

70 Fun VARIABLE (AC1-X$Time)

80 GENERATE ,,,1

90 Switch TRANSFER P_1,Met_2,Met_1

100 Met_1 TRANSFER ,Kl_1

110 Met_2 TRANSFER ,Kl_2

120 Kl_1 LOGIC S Kluch1

130 ADVANCE (T_1#7.03)

140 LOGIC R Kluch1

150 TRANSFER ,Switch

160 Kl_2 LOGIC S Kluch2

170 ADVANCE (T_2#7.03)

180 LOGIC R Kluch2

190 TRANSFER ,Switch

200 GENERATE (GAMMA(11,0,T_1,2))

210 GATE LS Kluch1,Met_10

220 TRANSFER ,Met_20

230 GENERATE (GAMMA(21,0,T_2,2))

240 GATE LS Kluch2,Met_10

250 Met_20 SAVEVALUE Arr,V$Fun

260 SAVEVALUE Time,AC1

270 TABULATE InterArr

280 MARK 2

290 QUEUE QCHAN

300 SEIZE CHAN

310 DEPART QCHAN

320 ADVANCE (Exponential(31,0,1.0))

330 RELEASE CHAN

340 TERMINATE 1

350 Met_10 TERMINATE

360 START 500

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

${\text{χ}}^2=\sum _{i=1}^K\frac{{(m_i-p_i\cdot N)}^2}{p_i\cdot N}$. (1)

Здесь m_i – число попаданий исследуемой случайной величины в i – й разряд статистического ряда I, p_i – теоретические вероятности попаданий в данный разряд

$p_i=\underset{t_{i-1}}{\overset{t_i}{\int }}[p{\text{λ}}_1^{2}t{\text{e}}^{-{\text{λ}}_{1}t}+(1-p\left){\text{λ}}_2^{2}t{\text{e}}^{-{\text{λ}}_{2}t}\right]dt$, (2)

K – число разрядов, N – общее число испытаний. Если в некоторых разрядах число попаданий m_i мало, то эти разряды следует объединять с соседними, чтобы тем самым исключить случайные факторы. Для данных на рис. 1 объединим разряды с малыми значениями m_i=1 с соседними, как это показано в таблице 1.

Как известно, например из [10], статистический тест Пирсона определяет меру расхождения статистического распределения от теоретического закона распределения, в качестве которого нами выбрано гиперэрланговское распределение. Критерий (1) представляет собой случайную величину, зависящую от выбранного закона распределения, числа степеней свободы, количества разрядов статистического ряда и числа испытаний.

Для данных, представленных на рис.1, запишем нужные нам параметры K=9 – число разрядов статистического ряда, N=523 – число испытаний, определенное как число входов транзактов в модель (ENTRY). Все промежуточные вычисления статистики Пирсона для статистического ряда, представленного на рисунке 1, поместим в табл. 1. Результаты вычисления статистики Пирсона приведены в таблице 1.

Таблица 1. Вычисления критерия Пирсона

По таблице критических значений критерия  для числа степеней свободы r=9-4=5 найдем близкие значения этого критерия: 4,35 с вероятностью 0,5 и 6,06 с вероятностью 0,3. Тогда линейная интерполяция нам дает вероятность P=0,43 для значения =4,99. Эта вероятность в статистике не маленькая, поэтому полученный в ходе прогона статистический ряд не противоречит гипотезе о том, что данные значения интервалов поступлений требований в систему HE₂/M/1 распределены по гиперэрланговскому закону.

Сравнение моментов закона распределения HE₂ показывает некоторые расхождения, что можно объяснить в данном случае с небольшим числом испытаний N=523. По исходным данным, среднее значение для интервалов поступлений 10/9=1,111, а коэффициент вариации равен двум. Статистические моменты равны: среднее значение 0,944 (Mean), а стандартное отклонение 1,759 (Std.Dev.), что дает коэффициент вариации 1,86. С увеличением числа испытаний, такое расхождение должно будет уменьшаться.

Проверка гипотезы о гиперэкспоненциальном распределении ПСП на примере СМО H₂/M/1

Имитационную модель СМО H₂/M/1 на GPSS WORLD, представленную в [2] для построения статистического ряда и построения гистограммы распределения дополним теми же блоками, что и для системы HE₂/M/1. Ниже представлена полная имитационная модель с учетом дополнительных блоков. Для этого случая ширину разряда статистического ряда положим равной двум, а число испытаний в прогоне – 1000. Установим для прогона исходные данные: возьмем коэффициент загрузки , коэффициент вариации интервалов поступлений  и единичное время обслуживания . Тогда параметры гиперэкспоненциального распределения , , , . Отсюда средние значения для формирования первой и второй фаз гиперэкспоненциального распределения составляют ,  единиц времени.

10 InterArr TABLE X$Arr,2,2,14

20 INITIAL X$Time,0

30 P_1 EQU 0.113

40 P_2 EQU (1-P_1)

50 T_1 EQU 4.929

60 T_2 EQU 0.626

70 Fun VARIABLE (AC1-X$Time)

80 GENERATE ,,,1

90 Switch TRANSFER P_1,Met_2,Met_1

100 Met_1 TRANSFER ,Kl_1

110 Met_2 TRANSFER ,Kl_2

120 Kl_1 LOGIC S Kluch1

130 ADVANCE (T_1#6.22)

140 LOGIC R Kluch1

150 TRANSFER ,Switch

160 Kl_2 LOGIC S Kluch2

170 ADVANCE (T_2#6.22)

180 LOGIC R Kluch2

190 TRANSFER ,Switch

200 GENERATE (Exponential(11,0,T_1))

210 GATE LS Kluch1,Met_10

220 TRANSFER ,Met_20

230 GENERATE (Exponential(21,0,T_2))

240 GATE LS Kluch2,Met_10

250 Met_20 SAVEVALUE Arr,V$Fun

260 SAVEVALUE Time,AC1

270 TABULATE InterArr

280 MARK 2

290 QUEUE QCHAN

300 SEIZE CHAN

310 DEPART QCHAN

320 ADVANCE (Exponential(31,0,1.0))

330 RELEASE CHAN

340 TERMINATE 1

350 Met_10 TERMINATE

360 START 1000

Результаты прогона с выходными данными для статистического ряда и гистограммы представлены на рисунках 3 и 4.

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

Рисунок 4. Полученная гистограмма распределения H₂

Для данных, представленных на рис.3, запишем нужные нам параметры K=10 – число разрядов статистического ряда, N=1054 – число испытаний, определенное как число входов транзактов в модель (ENTRY). Все промежуточные вычисления статистики Пирсона для статистического ряда, представленного на рисунке 3 поместим в таблицу 2.

Таблица 2. Вычисления критерия Пирсона

По таблице критических значений критерия  для числа степеней свободы r=K-4=6 найдем близкие значения этого критерия: 7,23 с вероятностью 0,3 и 8,56 с вероятностью 0,2. Степень свободы r определяется числом наложенных связей для закона распределения. К примеру, для показательного закона с одним параметром распределения r=K-2, для нормального закона с двумя параметрами r=K-3. Закон распределения H₂ включает три параметра, поэтому r=K-4. Линейная интерполяция значений критерия Пирсона нам дает для значения =7,36 вероятность P=0,29. Эта вероятность при проверке гипотез в статистике не маленькая, поэтому полученный в ходе прогона статистический ряд не противоречит гипотезе о том, что данные значения интервалов распределены по гиперэкспоненциальному закону.

Сравнение теоретических моментов распределения H₂ с статистическими моментами показывает также некоторые расхождения, что можно объяснить в данном случае тоже с относительно небольшим числом испытаний N=1054. По исходным данным, среднее значение интервалов поступлений 10/9=1,111, а коэффициент вариации равен двум. Статистические моменты равны: среднее значение 1,183 (Mean), а стандартное отклонение 2,126 (Std.Dev.), что дает коэффициент вариации 1,8. С увеличением числа испытаний можно ожидать, что такое расхождение будет уменьшаться.

В статье использованы приемы аппроксимации законов распределений с использованием моментных характеристик. Эти методы более подробно описаны в [11–16].

Заключение

В работе представлены разработанные в GPSS World имитационные модели функционирования СМО HE₂/M/1 и H₂/M/1 с гиперэрланговским и гиперэкспоненциальным входным распределениями второго порядка. Представлены также результаты статистических тестов для оценки качества генерирования псевдослучайных чисел по законам HE₂ и H₂ в случае переходного режима функционирования СМО. Результаты показывают удовлетворительное качество работы соответствующих представленных генераторов ПСП.

Полученные результаты публикуются впервые.

About the authors

Veniamin N. Tarasov

Author for correspondence.
Email: tarasov-vn@psuti.ru

Head of Software and Management in Technical Systems Department, Professor

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

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

Download (227KB)

Indexing metadata

3. Рисунок 2. Полученная гистограмма распределения HE2

Download (52KB)

Indexing metadata

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

Download (157KB)

Indexing metadata

5. Рисунок 4. Полученная гистограмма распределения H2

Download (51KB)

Indexing metadata