Исследование случайных входных воздействий для стохастических имитационных моделей дискретных систем тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Шляева, Анна Викторовна

• Шляева, Анна Викторовна
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Шляева, Анна Викторовна

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ.

ВВЕДЕНИЕ.

1. АНАЛИЗ МЕТОДОВ МОДЕЛИРОВАНИЯ СЛУЧАЙНЫХ.

ВХОДНЫХ ВОЗДЕЙСТВИЙ.

1.1. Классификация методов моделирования входных воздействий

1.1.1. Классификация по наличию выборки.

1.1.2. Классификация по наличию зависимости между различными моделируемыми входными воздействиями.

1.1.3. Классификация по наличию зависимости внутри моделируемого воздействия.

1.2. Методы оценки внутренней зависимости ряда данных.

1.2.1. Графические методы оценки независимости выборки.

1.2.2. Аналитические методы оценки независимости выборки.

1.3. Методы моделирования случайной величины.

1.3.1. Использование эмпирического распределения вероятностей.

1.3.2. Выбор теоретического распределения вероятностей.

1.3.3. Обратное распределение с полиномиальным фильтром.

1.3.4. Выбор распределения из семейства распределений Джонсона.

1.3.5. Выбор распределения из семейства распределений Пирсона.

1.3.6. Использование распределений Безье.

1.4. Методы моделирования стационарного случайного процесса.

1.4.1. Авторегрессионные процессы и процессы скользящего среднего.

1.4.2. ТЕ8-процессы.

1.4.3. АЯТА-процессы.

1.5. Анализ существующих программных продуктов для моделирования входных данных.

1.5.1. Специализированное программное обеспечение.

1.5.2. Программное обеспечение для статистической обработки данных.

1.6. Выводы.

2. МЕТОД МОДЕЛИРОВАНИЯ СЛУЧАЙНОГО ВХОДНОГО ВОЗДЕЙСТВИЯ С АВТОКОРРЕЛЯЦИЕЙ НА ОСНОВЕ АЯТА-ПРОЦЕССОВ.

2.1. Оценка параметров АЯТА-процесса.

2.1.1. Определение типа распределения Джонсона.

2.1.2. Оценка порядка автокорреляции базового процесса.

2.1.3. Оценка начальных значений параметров распределения Джонсона.

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

2.1.5. Алгоритм минимизации.

2.1.6. Общий алгоритм оценки параметров АЯТА-процесса.

2.1.7. Модификация алгоритма оценки параметров.

2.1.8. Вычисление целевой функции.

2.2. Выбор параметров АЯТА-процесса в отсутствие ряда данных.

2.2.1. Определение параметров безусловного распределения.

2.2.2. Определение параметров базового авторегрессионного процесса

2.3. Генерация случайного входного воздействия.

2.3.1. Алгоритм генерации равномерно распределенных случайных величин.

2.3.2. Алгоритм генерации нормально распределенных случайных величин.

2.3.3. Генерация значений авторегрессионного процесса.

2.4. Выводы.

3. МЕТОДИКА ОЦЕНКИ СТАТИСТИЧЕСКОГО СОГЛАСИЯ МОДЕЛИ СЛУЧАЙНОГО ВХОДНОГО ВОЗДЕЙСТВИЯ И ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА МОДЕЛИРОВАНИЯ ВХОДНЫХ ВОЗДЕЙСТВИЙ.

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

3.1.1. График квантиль-квантиль.

3.1.2. Критерий Колмогорова-Смирнова.

3.1.3. Критерий Андерсона-Дарлинга.

3.2. Методы оценки статистического согласия структур автокорреляции.

3.2.1. Сравнение коэффициентов автокорреляции.

3.2.2. Сравнение диаграмм разброса наблюдений.

3.2.3. Критерий Колмогорова-Смирнова для спектральной функции распределения.

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

3.4. Программное обеспечение для моделирования случайных входных воздействий.

3.4.1. Язык программирования.

3.4.2. Используемые библиотеки.

3.4.3. Структура классов.

3.4.4. Интерфейс пользователя.

3.5. Выводы.

4. ИССЛЕДОВАНИЕ МЕТОДА МОДЕЛИРОВАНИЯ СЛУЧАЙНЫХ ВХОДНЫХ ВОЗДЕЙСТВИЙ.

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

4.1.1. Рассматриваемые модели случайного воздействия и их параметры.

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

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

4.2. Исследование зависимости результатов моделирования системы от задания входных воздействий.

4.2.1. Случайные входные воздействия и их модели.

4.2.2. Результаты прогонов имитационной модели.

4.3. Моделирование дорожных потоков.

4.3.1. Исследуемая система, модель системы.

4.3.2. Методы моделирования дорожных потоков.

4.3.3. Результаты моделирования случайных входных воздействий.

4.4. Выводы.

ВЫВОДЫ

Введение диссертации (часть автореферата) на тему «Исследование случайных входных воздействий для стохастических имитационных моделей дискретных систем»

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

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

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

При создании имитационной модели системы одной из важных задач является задача формализации случайных входных воздействий, поступающих в систему в дискретные моменты времени. Особый интерес представляют методы моделирования входных воздействий при наличии ряда данных, соответствующих искомому случайному воздействию, ; полученных в результате натурных экспериментов или наблюдений над исследуемой системой. Имеющиеся данные возможно проанализировать, выявив в них зависимости и закономерности, построить соответствующую им модель входного воздействия, а также оценить параметры этой модели по данным. В ходе моделирования поведения системы генерация требуемого случайного входного воздействия осуществляется в соответствии с выбранной моделью входного воздействия. Вопрос моделирования входных данных для имитационных моделей систем рассматривался в трудах Б. Биллер, М. Карио, Б. Нельсона, Дж. Вилсона, Б. Шнейдера, Р. Кашьяпа, С. Хендерсона, Л. Лимиса, Б. Меламеда.

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

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

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

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

1. Анализ методов формализации случайных входных воздействий, в том числе входных воздействий без внутренней зависимости и входных воздействий с автокорреляцией.

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

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

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

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

1 АшоК^геББ^е-То-АпуНш^, авторегрессионный процесс для моделирования любого распределения

Заключение диссертации по теме «Теоретические основы информатики», Шляева, Анна Викторовна

114 ВЫВОДЫ

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

1. Проведен анализ методов формализации входных данных для стохастических моделей систем, в частности, стационарных случайных процессов, в результате предложен метод моделирования случайных входных воздействий с автокорреляцией на основе модели стационарного случайного процесса — АЛТА-процесса.

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Шляева, Анна Викторовна, 2009 год

1. Андерсон Т. Статистический анализ временных рядов. М.: Мир, 1976.-755 с.

2. Аттетков A.B., Галкин C.B., Зарубин B.C. Методы оптимизации. М.: Издательство МГТУ им. Н.Э. Баумана, 2001. - 440 с.

3. Бокс Дж., Дженкинс Г. Анализ временных рядов. Прогноз и управление. М.: Мир, 1974. - 608 с.

4. Брайловский Н.О., Грановский Б.И. Моделирование транспортных систем. -М.: Транспорт, 1978. 125 с.

5. Брандт 3. Анализ данных. Статистические и вычислительные методы для научных работников и инженеров. М.: Мир, 2003. - 686 с.

6. Бусленко Н.П. Моделирование сложных систем. — М.: Наука, 1968.-355 с.

7. Вентцель Е.С., Овчаров JI.A. Теория случайных процессов и ее инженерные приложения. — М.: Издательский центр Академия, 2003. 432 с.

8. Волков И.К., Зуев С.М., Цветкова Г.М. Случайные процессы. -М.: Издательство МГТУ им. Н.Э. Баумана, 2001. 448 с.

9. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985.-509 с.

10. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Издательство ЛКИ, 2007. - 400 с.

11. Кельтон В., Лоу А. Имитационное моделирование. СПб.: Питер, 2004. - 847 с.

12. Кендалл М., Стьюарт А. Многомерный статистический анализ и временные ряды. М.: Наука, 1976. - 736 с.

13. Кендалл М., Стьюарт А. Статистические выводы и связи. — М.: Наука, 1973.-899 с.

14. Кендалл М., Стьюарт А. Теория распределений. — М.: Наука, 1966.-587 с.

15. Кнут Д.Э. Искусство программирования: В 3 т. — М.: Издательский дом Вильяме, 2000. Т. 2: Получисленные алгоритмы. - 832 с.

16. Кобзарь А.И. Прикладная математическая статистика. Для инженеров и научных работников. М.: ФИЗМАТЛИТ, 2006. - 816 с.

17. Математическая статистика: Учеб. для вузов / В.Б. Горяинов, И.В. Павлов, Г.М. Цветкова и др. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - 424 с.

18. Норенков И.П. Основы автоматизированного проектирования. — М.: Изд-во МГТУ им. Баумана, 2006. 448 с.

19. Носко В.П. Эконометрика: Введение в регрессионный анализ временных рядов. М.: МФТИ, 2002. - 273 с.

20. Прохоров С.А. Математическое описание и моделирование случайных процессов. Самара: Самар. гос. аэрокосм, ун-т, 2001. — 209 с.

21. Рудаков И.В., Шляева A.B. Моделирование входных данных для стохастических имитационных моделей систем // Информационные технологии. 2006. - №11. - С. 8-12.

22. Рудаков И.В. Компьютерное моделирование системы безопасности путепровода тоннельного типа в составе транспортной развязки в районе пересечения Кутузовского проспекта Электронный ресурс. — Москва, 2006. 11 с.

23. Рудаков И.В., Шляева A.B. Моделирование входных потоков данных для стохастических моделей сложных систем // Вестник МГТУ им. Н.Э. Баумана. Приборостроение. 2008. - №2. - С. 65-72.

24. Семенов В.В. Математическое моделирование динамики транспортных потоков мегаполиса. Москва, 2004. - 44 с. (Препринт ИПМ; № 34).

25. Советов Б.Я., Яковлев С.А. Моделирование систем: Учебник для вузов по спец. Автоматизированные системы управления. М.: Высшая школа, 1985. —271 с.

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

27. Шляева А.В. Использование ART А- и TES-процессов для моделирования входных данных стохастических имитационных моделей

28. Новые информационные технологии в автоматизированных системах-9.: Сборник трудов научно-практического семинара. Москва, 2006. - С. 178180.

29. Шляева А.В. Анализ методов моделирования стационарных входных потоков заявок для вычислительной системы, формализованной при помощи СМО // Online Educa Moscow 2007.: Тезисы докладов международной конференции. Москва, 2007. - С. 27-32.

30. Шляева А.В. Моделирование стационарных входных потоков данных для стохастических моделей дискретных систем // Информационные технологии и системы (ИТиС'08).: Сборник трудов конференции молодых ученых. М.: ИППИ РАН, 2008. - С. 376-381.

31. Anderson T.W. On the Distribution of the Two-Sample Cramer-von Mises Criterion // The Annals of Mathematical Statistics. 1962. - Vol. 33. - P. 1148-1159.

32. Anderson T.W. Goodness of Fit Tests for Spectral Distributions // Annals of Statistics. 1993. - Vol. 21. - P. 830-847.

33. Andradyttir S. Analysis methodology: are we done? // 2005 Winter Simulation Conference: Proceedings. Orlando, 2005. - P. 790-796.

34. Barton R.R., Schruben L.W. Resampling Methods for Input Modeling // 2001 Winter Simulation Conference: Proceedings. Arlington, 2001. - P. 372378.

35. Bazaraa M.S., Sherali M.S., Shetty C.M. Nonlinear Programming: Theory and Algorithms. New York: John Wiley and Sons, 1993. - 853 p.

36. Biller В., Nelson B.L. Answers to the top ten input modeling questions // 2002 Winter Simulation Conference: Proceedings. San Diego, 2002. -P. 35-40.

37. Biller В., Nelson B.L. Fitting time-series input processes for simulation: Technical report. Evanston, 2005. — 44 p.

38. Biller В., Nelson B.L. Fitting time series input processes for simulation // Operations Research. 2005. - Vol. 53. -P. 549-559.

39. Biller В., Nelson B.L. Parameter estimation for ARTA processes2002 Winter Simulation Conference: Proceedings. San Diego, 2002. - P. 255262.

40. Cario M.C., Nelson B.L. Autoregressive to anything: Time-series input processes for simulation // Operations Research Letters. 1996. — Vol. 19. — P. 51-58.

41. Cario M.C., Nelson B.L. Numerical methods for fitting and simulating autoregressive-to-anything processes // INFORMS Journal on Computing. 1998. -Vol. 10.-P. 72-81.

42. Chatfield C. The Analysis of Time Series: An Introduction. — New York: Chapman and Hall, 1996. 293 p.

43. Chen H. Initialization for NORTA: Generation of random vectors with specified marginals and correlations // INFORMS Journal on Computing. 2001. -Vol. 13.-P. 312-331.

44. Devroye L. Non-Uniform Random Variate Generation. — New York: Springer-Verlag, 1986. 843 p.

45. Eshel G. The Yule Walker Equations for the AR Coefficients: Lecture notes Электронный ресурс. Philadelphia, 2003. - 7 p. http://www-stat.wharton.upenn.edu/~steele/Courses/956/ResourceDetails/YWSourceFiles/YW -Eshel.pdf

46. Evans G.W., Stockman В., Mollaghasemi M. Multicriteria Optimization of Simulation Models // 1991 Winter Simulation Conference: Proceedings. Phoenix, 1991. - P. 894-900.

47. Gaver D.P., Lewis P.A.W. First-order autoregressive gamma sequences and point processes // Advances in Applied Probability. 1980. - Vol. 12.-P. 727-745.

48. Gibbons J.D., Chakraborti S. Nonparametric Statistical Inference. -New York: CRC Press, 2003. 645 p.

49. Hahn G.J., Shapiro S.S., Hahn G.H. Statistical Models in Engineering. New York: John Wiley, 1994. - 355 p.

50. Handbook of Semidefínite Programming. Theory, Algorithms and Applications / Ed. H. Wolkowicz, R. Saigal, L. Vandenberghe. Boston: Kluwer, 2000. - 599 p.

51. Henderson S.G. Should we model dependence and nonstationarity, and if so how? // 2005 Winter Simulation Conference: Proceedings. Orlando, 2005.-P. 41-55.

52. Hill I.D., Hill R., Holder R.L. Fitting Johnson curves by moments // Applied Statistics. 1976. - Vol. 25. - P. 180-189.

53. Introduction to modeling and generating probabilistic input processes for simulation / E.K. Lada, N.M. Steiger, M.A. Wagner, J.R. Wilson // 2005 Winter Simulation Conference: Proceedings. — Orlando, 2005. P. 41-55.

54. Jacobs P.A., Lewis P.A.W. A mixed autoregressive-moving average exponential sequence and point process (EARMA(1,1)) // Advances in Applied Probability. 1977. - Vol. 9. - P. 87-104.

55. Johnson N.L. Systems of frequency curves generated by methods of translation // Biometrika. 1949. - Vol. 36. - P. 149-176.

56. Keefer D.L., Bodily S.E. Three-Point Approximations for Continuous Random Variables // Management Science. 1983. - Vol. 29. - P. 595-609.

57. Kühl M.E., Wilson J.R. Least-squares estimation of non-homogeneous Poisson processes // Journal of Statistical Computation and Simulation. — 1999. -Vol. 67.-P. 75-108.

58. Law A.M., McComas M.G. How the Expertfit distribution-fitting software can make your simulation models more valid // 2003 Winter Simulation Conference: Proceedings. — New Orleans, 2003. — P. 169-174.

59. Law A.M., McComas M.G. ExpertFit: Total Support for Simulation Input Modeling // 1998 Winter Simulation Conference: Proceedings. -Washington, 1998.-P. 303-308.

60. Lawless J.F. Statistical Models for Lifetime Data. New York: John Wiley, 2002. - 664 p.

61. Leemis L. Simulation Input Modeling // 1999 Winter Simulation Conference: Proceedings. Phoenix, 1999. - P. 14-23.

62. Leemis L. Input modeling techniques for discrete-event simulations2001 Winter Simulation Conference: Proceedings. Arlington, 2001. — P. 62-73.

63. Lewis P.A.W., McKenzie E., Hugus D.K. Gamma processes

64. Communications in Statistics-Stochastic Models. 1989. - Vol. 5. - P. 1-30.

65. Livny M., Melamed B., Tsiolis A.K. The impact of autocorrelation on queueing systems // Management Science. 1993. - Vol. 39. - P. 322-339.

66. Mallows C.L. Linear processes are nearly Gaussian // Journal of Applied Probability. 1967. - Vol. 4. - P. 313-329.

67. Marsaglia G. Random number generators // Journal of Modern Applied Statistical Methods. 2003. - Vol. 2. - P. 2-13.

68. Matsumoto M., Nishimura T. Mersenne twister: A 623-dimensionally equidistributed uniform" pseudorandom number generator // ACM Trans. On Modeling and Computer Simulations. 1998. - Vol. 8. - P. 3-30.

69. Mehrotra S. On the implementation of a primal-dual interior point method // SIAM Journal on Optimization. 1992. - Vol. 2. - P. 575-601.

70. Melamed B., Hill J.R., Goldsman D. The TES methodology: Modeling empirical stationary time series // 1992 Winter Simulation Conference: Proceedings. Arlington, 1992.-P. 135-144.

71. Mignolet M.P. ARMA simulation of multivariate and multidimensional random processes: PhD thesis. — Houston, 1987. — 307 p.

72. Model order selection criteria: comparative study and applications / Z. Leonowicz, J. Karvanen, T. Tanaka, J.1 Rezmer // Computational Problems of

73. Electrical Engineering: proceedings of the international workshop. Zagreb, 2004. -P. 193-196.

74. Najim K., Ikonen E., Daoud Ait-Kadi. Stochastic processes. Estimation, Optimization & Analysis. London: Kogan Page Science, 2004. - 332 P

75. Nelson B.L., Yamnitsky M. Input modeling tools for complex problems // 1998 Winter Simulation Conference: Proceedings. Washington,1998.-P. 105-112.

76. Schmeiser B. Advanced input modeling for simulation experimentation // 1999 Winter Simulation Conference: Proceedings. Phoenix,1999.-P. 110-115.

77. Seber G.A.F. Linear Regression Analysis. New York: John Wiley, 1977.-432p.

78. Song W.T., Hsiao L., Chen Y. Generating pseudorandom time series with specified marginal distributions // European Journal of Operational Research. 1996.-Vol. 93.-P. 1-22.

79. Swain J.J., Venkatraman S., Wilson J.R. Least-squares estimation of distribution functions in Johnson's translation system // Journal of Statistical Computation and Simulation. 1988. - Vol. 29. - P. 271-297.

80. Takus D.A., Profozich D.M. Arena Software Tutorial // 1997 Winter Simulation Conference: Proceedings. — Atlanta, 1997. P. 541-544.

81. Vandenberghe L., Boyd S. Semidefinite Programming // SIAM Review. 1996. - Vol. 38. - P. 49-95.

82. Wagner M.A.F., Wilson J.R. Recent Developments in Input Modeling with Bezier Distributions // 1996 Winter Simulation Conference: Proceedings. -Coronado, 1996. P. 1448-1456.

83. Ware P.P., Page T.W., Nelson B.L. Automatic modeling of file system workloads using two-level arrival processes // ACM TOMACS. 1998. - Vol. 8. -P. 305-330.

84. Wei W.W.S. Time Series Analysis: Univariate and Multivariate Methods. New York: Addison Wesley, 1990. - 614 p.

85. Wilson J.R. Modeling dependencies in stochastic simulation inputs // 1997 Winter Simulation Conference: Proceedings. Atlanta, 1997. - P. 47-52.