Навчально-науковий комплекс «Інститут прикладного системного аналізу» Національний технічний університет України «Київський політехнічний інститут», Україна
| Вид материала | Документы |
- Навчально-науковий комплекс «Інститут прикладного системного аналізу» Національний, 47.34kb.
- Інститут економіки та промисловості нан, 3422kb.
- Інститут економіки та промисловості нан, 9040.04kb.
- Національний технічний університет україни "київський політехнічний інститут" фізико, 288.71kb.
- Національний технічний університет «Харківський політехнічний інститут»,, 70.45kb.
- Роль малих та середніх підприємств в економічному розвитку держави ( порівняльний аналіз), 314.38kb.
- Національний технічний університет україни “київський політехнічний інститут” Факультет, 11.38kb.
- Cx-x особливості низькотемпературної теплоємності наноалмазу детонаційного синтезу, 45.64kb.
- Задача автоматизованого аналізу ефективності використання будівель та приміщень університету, 95.58kb.
- В. Я. Круглицька, В. М. Пахомова, О. Г. Осьмаков,, 195.49kb.
УДК 004.94
ПОРІВНЯННЯ ГЕНЕРАТОРІВ ПСЕВДОВИПАДКОВИХ ЧИСЕЛ В СИСТЕМАХ
ІМІТАЦІЙНОГО МОДЕЛЮВАННЯ OPENGPSS, GPSS WORLD ТА ANYLOGIC
Д.Г. Діденко
Навчально-науковий комплекс «Інститут прикладного системного аналізу»
Національний технічний університет України «Київський політехнічний інститут», Україна
Вступ
Одним з сучасних методів аналізу роботи складних систем є використання імітаційного моделювання. Для проведення повторюваних комп’ютерних прогонів стохастичних моделей використовуються події, які отримані від датчиків псевдовипадкових чисел (ДПЧ). Тому якість псевдовипадкових послідовностей має велике значення при отриманні достовірних результатів. В докладі розглядаються сучасні системи імітаційного моделювання OpenGPSS (ссылка скрыта) [1, 2], GPSS World [3] та AnyLogic [4], які працюють з дискретними моделями. Системи моделювання підтримують роботу з великою кількістю імовірнісних розподілів – від Бернуллі до Вейбула: 29-ть розподілів в OpenGPSS, в допомозі AnyLogic описано 29-ть розподілів (хоча в [4] йдеться мова про 37-ім), 24-ри розподіли у GPSS World [5 - 7]. Всі види розподілів будуються на рівномірному розподілі, якість якого й оцінюється далі.
Тести псевдовипадкових послідовностей
На сьогодні існує багато графічних і статистичних тестів для перевірки псевдовипадкових послідовностей. Серед статистичних тестів широко використовуються наступні: NIST, TEST-U01, CRYPT-X, The pLab Project, DIEHARD, ENT тощо. В цьому докладі розглядається застосування набору тестів Diehard (автор George Marsaglia) для трьох систем імітаційного моделювання.
Для кожного середовища моделювання була написана власна невелика програма на відповідній мові (GPSS та Java), яка дозволяє отримати велику вибірку псевдовипадкових чисел з рівномірним розподілом. Далі, за допомогою пакету програм Diehard, бінарні файли якого взяті з сайту ссылка скрыта, виконаний аналіз послідовностей чисел для кожної системи моделювання окремо.
Опис лабораторного устаткування
Для всіх практичних експериментів використовувався один комп’ютер класу Intel Core Duo з процесором 2,1 Ггц та оперативною пам’яттю 2 ГБ, операційна система Windows XP SP3. Експерименти ставилися на системах моделювання наступних версій: OpenGPSS 1.2.1.0, GPSS World 5.2.2. та AnyLogic 6.4.1. Всі експерименти проводилися над генератором псевдовипадкових чисел №1, з наступними початковими зміщеннями: 300 (OpenGPSS), 200 (GPSS World) та 100 (AnyLogic).
Особливості проведення обчислювального експерименту в системах моделювання
Для системи моделювання GPSS World при малій кількості чисел (до 4 млн. чисел) програма Diehard видає помилку: “run-time error F6501: Read(назва файлу) - end of file encountered”. Це відбувається на тесті №2 «Перестановки, що перетинаються», хоча в тексті самого тесту написано, що він обробляє послідовність з одного млн. 32-бітних чисел двічі.
Нажаль відразу згенерувати дані у бінарний файл не дозволяють середовища моделювання, тому що підтримується читання та запис лише текстового файлу. Отримати кінцевий файл можемо лише за два кроки: перший – створення текстового файлу з 4 млн. рядків, в кожному рядку одне число, яке записано текстом, і другий – переведення текстового файлу в бінарний.
Звичайна програма генерування послідовності у GPSS World в текстовий файл спочатку навіть для 40 тис. чисел триває 2 години. І лише після модифікації програми на GPSS генерування такого файлу відбувається за 2 хвилини. Справа в тому, що блок відкриття файлу OPEN довго працює. Тому його не потрібно кожний раз викликати для кожного транзакту, а необхідно перенести в окремий часовий сегмент GENERATE, OPEN, ADVANCE, CLOSE та TERMINATE і викликати один раз для всієї програми.
Для системи моделювання OpenGPSS текстовий файл отримано за 30 хвилин.
Проміжний текстовий файл займає 46 Мбайт. Потім на конвертацію в потрібний бінарний файл розміром 15 Мбайт за допомогою VisualBasic-сценарію витрачається 3 хвилини.
Кожний тест на виході формує спеціальне число p-value є [0;1). Результати проведених експериментів наведені в таблиці 1. Кількість згенерованих чисел для кожної системи моделювання – 4 млн. В таблиці «+» означає, що тест пройдено (якщо p-value є [0,025;0,975]), а «-» - тест не пройдено.
Таблиця 1. Значення p-value тестів DIEHARD
| № | Тест | OpenGPSS | GPSS World | AnyLogic | |||
| 1 | Дні народження (Birthday Spacings) | 0,359018 | + | 1,000000 | - | 0,431397 | + |
| 2 | Перестановки, що перетинаються (Overlapping Permutations) | 1,000000 | - | 0,060425 | + | 0,008494 | - |
| 3 | Ранги матриць (Ranks of matrices) | 0,950574/ 0,991835/ 0,999961 | +/-/- | 0,413445/ 0,536567/ 0,097624 | +/+/+ | 0,382749/ 0,342521/ 0,249165 | +/+/+ |
| 4 | Потік бітів (The bitstream test) | 0,805974* | + | 1,000000 | - | 0,482539* | + |
| 5 | Мавпячі тести (Monkey Tests) | 1,000000 | - | 0,585412* | + | 0,494274* | + |
| 6 | Підрахунок одиничок (Count the 1’s) | 1,000000 | - | 1,000000/ 0,495902* | -/+ | 0,558042*/ 0,587793 | +/+ |
| 7 | Тест на парковку (Parking Lot Test) | 0,979816 | - | 0,751581 | + | 0,221977 | + |
| 8 | Тест на мінімальну відстань (Minimum Distance Test) | 0,992231 | - | 0,545258 | + | 0,506258 | + |
| 9 | Тест випадкових сфер (Random Spheres Test) | 0,173505 | + | 0,162508 | + | 0,278340 | + |
| 10 | Тест стискання (The Squeeze Test) | 1,000000 | - | 0,475504 | + | 0,985307 | - |
| 11 | Тест сум, що перетинаються (Overlapping Sums Test) | 0,919356 | + | 0,681207 | + | 0,899422 | + |
| 12 | Тест послідовностей (Runs Test) | 0,312858 | + | 0,458301* | + | 0,549636* | + |
| 13 | Тест гри в кості (The Craps Test) (for no. of wins/ for throws/game) | 0,406554/ 1,000000 | +/- | 0,214467/ 0,807587 | +/+ | 0,343878/ 0,396355 | +/+ |
Примітка: * - означає, що рахувалося середнє арифметичне для цього тесту, тому що виводилось багато значень p-value у результуючому файлі.
Були повністю використані усі тринадцять тестів цього пакету. Але звичайно проходження (або не проходження) тестів недостатньо, щоб прийняти або відхилити гіпотезу про випадковість потоку даних. Тести Diehard формують на виході числа p-value, які рівномірно розподілені в інтервалі [0;1], якщо вхідний потік чисел дійсно випадковий. Перевіряємо нашу «нульову» гіпотезу про вхідний потік через статистичну значимість по критерію Пірсона (критерій «Хі-квадрат»). Для критерію Пірсона потрібно багато реалізацій, а тестів всього 13, тому використовуємо всі значення p-value з результуючого файлу, там їх приблизно 240 (!). Результати розрахунків по критерію показано в таблиці 2.
Таблиця 2. Перевірка статистичної гіпотези о випадковості потоку даних
| Генератор псевдовипадкових чисел | Кількість пройдених тестів з набору Diehard | Критерій Пірсона («Хі-квадрат») | Аналіз результату | |
| отримане | табличне | |||
| OpenGPSS | 5 | 90,00 | 36,2 | Потік не можна вважати випадковим |
| GPSS World | 10 | 29,45 | 36,2 | Потік можна вважати випадковим |
| AnyLogic | 11 | 28,17 | 36,2 | Потік можна вважати випадковим |
Висновки
1. Системи моделювання GPSS World и AnyLogic можна використовувати для побудови стохастичних моделей досліджуваних систем. В системі OpenGPSS необхідно покращити роботу ДПЧ.
2. Одним з варіантів покращення рівномірності згенерованих псевдовипадкових чисел є використання не одного алгоритму отримання рівномірного розподілу, а декількох, що відрізняються по відношенню якість/швидкість. Перед комп’ютерним прогоном експериментатор має можливість вибирати режим генерування рівномірного розподілу в залежності від своїх потреб та апаратних можливостей. Але поки таке у системах, що розглядаються, не реалізовано.
3. Для покращення поведінки стохастичних моделей слід використовувати декілька ДПЧ. Наприклад, кількість ДПЧ в GPSS World – 103, в OpenGPSS - 1038, а в AnyLogic (з урахуванням датчиків користувача) – не обмежено.
Література
1. Дiденко Д.Г. Особливості роботи СМО з абсолютними пріоритетом обслуговування у системі моделювання OpenGPSS. // V науково-практична конференція з міжнародною участю «Математичне та імітаційне моделювання систем. МОДС'2010». - Київ. - 2010. - С.196-197.
2. Томашевский В.Н., Диденко Д.Г. Агентная архитектура распределенной дискретно-событийной системы имитационного моделирования OpenGPSS. Системні дослідження та інформаційні технології. № 4, 2006. – К.: ВПК «Політехніка», 2006. С.123–133.
3. Бражник А.Н. Имитационное моделирование: возможности GPSS WORLD. - СПб.: Реноме, 2006. - 439 с.
4. Карпов Ю. Имитационное моделирование систем. Введение в моделирование с AnyLogic 5. - СПб.: БХВ-Петербург, 2005. - 400 с.: ил.
5. Рыжиков Ю. И. Имитационное моделирование. Теория и технологии. СПб.: КОРОНА принт; М.: Альтекс-А, 2004. 384 с.
6. Боев В.Д. Моделирование систем. Инструментальные средства GPSS World: учеб. пособие / В. Боев. – СПб.: БХВ-Петербург, 2004. – 368 с.
7. Алиев Т.И. Основы моделирования дискретных систем. – СПб: СПбГУ ИТМО, 2009. – 363 с.