автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему: Задачи стохастической оптимизации параметров эксперимента на примере информационных систем
Автореферат диссертации по теме "Задачи стохастической оптимизации параметров эксперимента на примере информационных систем"
РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ГЕОФИЗИКИ
ЗАДАЧИ СТОХАСТИЧЕСКОЙ ОПТИМИЗАЦИИ ПАРАМЕТРОВ ЭКСПЕРИМЕНТА НА ПРИМЕРЕ ИНФОРМАЦИОННЫХ СИСТЕМ
05.13.16 - применение вычислительной техники, математического моделирования, математических методов в научных исследованиях
диссертации на соискание ученой степени кандидата физико-математических наук
На правах рукописи
ШАХОВ Владимир Владимирович
Работа выполнена на кафедре вычислительных систем механико-математического факультета Новосибирского государственного университета.
Научный руководитель: к.т.н., доцент А.С.Родионов.
Официальные оппоненты: д. ф.-м. н., профессор Г.С. Лбов,
к. ф.-м. н., доцент C.B. Рогазинский.
Ведущая организация: Новосибирский государственный
Защита состоится 11 апреля 2000 г. в 15 часов на заседании Специализированного совета Д.002.10.02 в Институте вычислительной математики и математической геофизики СО РАН (630090, Новосибирск, пр-т Акад. Лаврентьева, б).
С диссертацией можно ознакомиться в читальном зале библиотеки ИВМиМГ СО РАН.
Ж.-. сМ&Ц? Гй 2000 года.
Ученый секретарь диссертационного совета к. ф.-м. н., доцент С.Б.Сорокин
Общая характеристика работы
Актуальность темы. С развитием научно-технического прогресса информационные технологии стали важнейшим элементом современного общества, что обуславливает необходимость развития и улучшения информационных систем (ИС). Первостепенное значение принимают методологии, позволяющие исследовать ИС, строить модели ИС и оптимизировать их исследования с точки зрения различных критериев.
В данной диссертации рассматриваются задачи, возникающие при оптимизации натурных и имитационных экспериментов над ИС и их моделями (МИС), а также при мониторинге цифровых информационных сетей (ЦИС).
Одной из таких задач является проблема оптимального планирования регрессионного эксперимента, где необходимо учитывать специфику моделей ИС, а именно дискретность и ограниченность факторного пространства и возможность управления дисперсией.
При всем многообразии алгоритмов для решения задач планирования задаче построения дискретных оптимальных планов не уделялось должного внимания. В литературе излагаются приближенные методы построение дискретных планов, которые основаны на замело дискретной задачи непрерывной с последующим округлением полученного решения до какого-либо ближайшего дискретного, или используют идею последовательного улучшения начального плана переносом измерения из одной точки в другую, доставляющую наибольшее увеличение максимизируемого функционала. Указанные подходы не всегда дают приемлемый результат.
Вторая проблема, исследованная в данной работе - обнаружение разладки по наблюдению характеристик ИС в режиме ее экстремальной работы, где4йод экстремальностью подразумевается скачкообразное изменение параметров ИС. Здесь, по сути, речь идет о правиле выбора параметров управления экспе-
риментом, в ходе которого принимается обоснованное решение завершить эксперимент. Задача возникает в связи с потребностями исследования поведения системы, некоторые элементы которой вышли из строя, что повлекло частичную потерю работоспособности системы, т.е. с математической точки зрения произошло изменение параметров, описывающих функционирование системы.
Цель работы. Целью диссертации является разработка методов, позволяющих получить решение задачи оптимального планирования дискретного регрессионного эксперимента (рассмотрен критерий D-оптимальности), а также исследование и модификация методов обнаружения разладки для задач, возникающих при изучении ИС.
Методика исследования. Методы данного исследования базируются на известных подходах к формализации ЙС и их имитационном моделировании, методах теории вероятности и математической статистики, планировании эксперимента, регрессионного и математического анализа, исследовании операций. При создании программных средств, для апробации полученных теоретических результатов, использовались языки программирования Simula-67, Modula-2 (Top Speed) и система моделирования СИДМ-2.
Научная новизна и практическая значимость. Все результаты являются новыми и находят применение при решении задач стохастической оптимизации исследований информационных систем, в задачах планирования дискретного регрессионного эксперимента, в исследованиях моделей ИС и аналогичных моделей в различных отраслях знаний, задачах обеспечения контроля качества.
Апробация работы. Основные положения диссертационной работы докладывались, обсуждались и получили положительную оценку на Третьем Сибирском Конгрессе по Прикладной и Индустриальной Математике (ИНПРИМ-98) посвященном памяти С.Л.Соболева (Новосибирск, 1998 г.), 11-й
Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, 1998 г.), Международной конференции "Математическое моделирование и информационные технологии в образовании и науке" (Алматы, Казахстан, 1998 г.), Конференции молодых ученых ИВМ и МГ (Новосибирск, 1999 г.), Международной конференции "Distributed Computer Communication Networks" (Тель-Авив, Израиль, 1999 г.), конференциях молодых ученых ИВМ и МГ (ВЦ) СО РАН (Новосибирск, 1995, 1997, 1999), а также на семинарах под руководством члена-корреспондента РАН Г.А.Михайлова (ИВМ и МГ СО РАН), профессора М.И.Нечепуренко (ИВМ и МГ СО РАН), профессора В.К.Попкова (ИВМ и МГ СО РАН), профессора Б.Ю. Лемешко (НГТУ), семинарах кафедры Теоретической кибернетики НГУ под руководством профессора В.Т.Дементьева (ИМ СО РАН).
Публикации. По материалам диссертации опубликовано 9 печатных работ.
Объем и структура работы. Диссертаций состоит из введения, четырех, глав, списка литературы, включающего 84 наименования, приложения, и изложена на 120 страницах.
Во введении приведена краткая аннотация данной диссертации, изложены актуальные проблемы, которые подлежат исследованию, и то новое, что предложено лично автором для их решения. Сформулированы основные положения, выносимые на защиту.
Первая глава содержит обзор литературы по исследованию ИС. Рассмотрены причины, согласно которым возникает необходимость подобного рода исследований. При детальном анализе математического аппарата, позволяющего изучать ИС, выявлены вопросы, которым не уделялось достаточного внимания в работах предшественников - оптималь-
ное планирование дискретного регрессионного эксперимента (ОПДЭ), рассмотрен критерий Б-оптимальности, и задача обнаружения разладки в дисциплине обслуживания устройства.
В главе подробно рассмотрены существующие подходы к решению задачи ОПДЭ, обоснована ограниченность их применения. Построен пример с уравнением регрессии т>(к,р)) цифрой 2 - г](к,р), цифрой 3 - и цифрой 4 чМ п(М '
Оптимальный план, в данном случае, содержится в точке, соответствующем минимально возможному значению буфера к = 1 (см. табл. 1 в приложении А.
Рис. 4. Отношение функций регрессии с р* и р = 0.1
Рис. 6. Функция регрессии, вычисленная для параметра д = 0.5 и его оценок
Рис. 8. Отношение функций регрессии с р и р = 0.5
Как было прошпострированно, картина принципиально не изменилась при среднем значении коэффициента использования. Оптимальный план будет тот же, что и в предыдущем случае. Однако с ростом р оптимальный план будет смещаться в сторону увеличения буфера. При р = 0.9 он соответствует значению буфера, равного 3, а при избыточных нагруках, равен максимально возможному значению. Заметим, что в ситуациях с большими нагрузками оценки параметра превосходят истинное значение, в то время как при низких, наоборот.
Рис. 9. Функция регрессии, вычисленная для параметра i? = 0.9 и его оценок
Рис. 11. Отношение функций регрессии с р и р = 0.9
Рис. 13. Отношение функций регрессии с р* и р = 1.1
Таким образом показано существенное преимущество оптимальных оценок над равномерными. Заметим, что при значениях параметра 0.9 и 1.1 качество равномерных оценок может считаться приемлемым (до 20 % при нелинейной функции регрессии), но в данном случае, оценки, полученные по равномерному плану, дают неправильное представление о сути процесса - получается, что система не справляется с потоком заявок в первом случае, и справляется во втором, хотя в реальности все наоборот.
Наблюдая значения точек оптимальных планов, видно, что при низких нагрузках проводить измерения надо с минимальным объемом буфера, который растет с увеличением нагрузки на систему. Получается, что при низкой нагрузке (р < 0.6) и, даже, небольшом объеме буфера заявки, практически, не получают отказов на обслуживание, хотя значения коэффициента использования могут значительно отличаться друг от друга в процентном соотношении. Чем меньше объем буфера,.тем больше отказов и, соответственно, информации.
Картина принципиально меняется при высокой нагрузке на систему. Становится невыгодным проводить измерения при небольшом объеме буфера, т.к. доля отказов будет одинаково высокой для существенно различных значений коэффициента использования. Чтобы снизить влияние переполняющего потока, имеет смысл увеличение объема буфера, что и подтверждается экспериментальными расчетами (см. таблицы в приложении А).
4.3. Модель системы с запросами на установление виртуальных цепей.
Для исследования сети передачи данных, в которой моменты поступления соответствуют запросам на установление виртуальных цепей между двумя узлами, а максимально возможное число виртуальных цепей равно га, используется модель М/М/т/т. Эта система массового обслуживания подобна системе М/М/т за исключением того, что если требование при поступлении в систему обнаружит, что все m обслуживающих приборов заняты, оно не поступит в систему, а потеряется (эта модель, также, широко используется в телефонии). Средняя длительность обслуживания прибором заявки в этом случае равна среднему времени использования виртуальной цепи.
Рассмотрим задачу оценки параметров, аналогичную предыдущей, т.е. по наблюдению доли отказов в общем количестве заявок получим оценку коэффициента использования и покажем преимущество оптимального плана над равномерным.
Для уравнения регрессии, соответствующего средней доли потерянных требований, согласно В-формуле Эрланга имеем :
Рт — vm ' п=0 п! где коэффициент р имеет тот же смысл, что и в предыдущем разделе.
Будем полагать, что максимально возможное количество соединений не превосходит 12, р принимает значения 0.1, 1, 2, 3, 4, 5. Техника вычислений плана и оценок такая же как в п.4.2. Для данной модели оптимальный план также дает существенный выйгрыш перед равномерным, что отражено в таблице 9,
По результатам работы можно сделать следующие выводы.
Актуальность решения проблем, возникающих при исследовании информационных сетей представляется очевидной. В этом ряду особое место здесь занимает задача стохастической оптимизации экспериментов с информационными сиистемами и их моделями. В рамках данной проблемы можно выделить две важные подзадачи.
Первая — задача планирования регрессионного эксперимента над моделями информационных сетей, которая решается для улучшения оценок параметров, входящих в модель, с точки зрения некоторого критерия оптимальности (в работе рассмотрен критерий D-оптимальности). Указанная задача впервые сведена к целочисленной задаче оптимизации с нелинейной (в общем случае) целевой функцией. Результаты, полученные во второй главе, позволяют использовать для оптимального плана задачи ОПДЭ методологию динамического программирования, а в некоторых случаях получить оптимальный план в явном виде.
Вторая задача — обнаружение возникновения изменений в режиме функционирования системы. Подобные изменеия могут быть связаны как с изменениями параметров обслуживающих устройств (например, в случае частичного отказа оборудования), так и с изменением характера запросов на обслуживание. В диссертации рассмотрен случай обнаружения разладки в системах, моделируемых СМО с одним прибором. В рамках данной проблемы впервые поставлена и изучена задача о разладке с фиксированной длиной зоны обнаружения, для которой получено аналитическое решение для оптимального порогового значения в алгоритме кумулятивных сумм, сделаны рекомендации по использованию АКС. Предложен также собственный метод обнаружения разладки, основанный на рассмотрении медианы распределения и о случайной величины после возникновения разладки.
Результаты данной диссертации могут использоваться как при исследовании и мониторинге реальных сетей, так и при построении и оптимизации моделей информационных сетей. Кроме того, результаты диссертации могут использоваться и при исследовании других дискретных стохастических систем.
Библиография Шахов, Владимир Владимирович, диссертация по теме Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)
1. Ashish. Sen, Muni S. Srivastava. On multivariate tests for detecting change in median. - Sankhya, 1973, ser. A, v. 35, №2, p. 173-186.
2. Ashish Sen, Muni S. Srivastava. Some one-sided test for change in level. Technometrics, 1975, v. 17, №1, p. 173-186.
3. Ashish Sen, Muni S. Srivastava. On test for detecting change in mean. Ann. of Stat., 1975, v.3, №1, p. 98 - 108.
4. D.S. van Dobben de Bruyn. Cumulative sum tests: theory and practice. London: Griffin, 1968.
5. Hinkley D. V. Inference about the change-point from cumulative sum tests. Biometrika, 1971, v. 58, № 3, p. 509 - 523.
6. Hinkley D. V. Time-ordered classification. Biometrika, 1972, v. 59, № 3, p. 509 - 523.
7. Johnson R. A., Bagshaw M. L. The effect of serial correlation on the performance of CUSUM tests. I, II. Technometrics, 1974, v. 16, №1, p. 73-80, 1975, v. 17, №1, p. 103-112.
8. Johnson R. A., Bagshaw M. L. Sequential procedures for detecting parameter changes in a time-series model. JASA, 1977, v. 72, №359, p. 593-597.
9. Itai A., Perl Y., Shiloach Y. The complexity of finding maximum disjoint paths with length constraints. Networks, 1982, V.12, N3, p. 277-286.
10. Kajitani Y., Ueno S. The minimum augmentation of a directed tree to a K-edge connected directed graph. Networks, 1986, V.16, N2.
11. Lee G.B. Science information Service directions Changing Patterns in Information Retrieval Philadelphia: ASIS,1974,p. 130136.
12. Page E.S. Continuous inspection schemes. Biometrika, 1954, v.41, N2, p.100-114.
13. Page E.S. A test for a change in parameter occuring at an unknown point. Biometrika, 1955,v.42, N4, p.523-527.
14. Page E.S. On problems in which a change in parameter occurs at an unknownpoint. Biometrika, 1957,v.44, N2, p.248-252.
15. Pettit A.N. A simple cumulative sum type statistic for the change point with zero-one observations. Biometrika, 1980, v. 67, № i, p. 79 . 84.
16. Reynolds A. Approximations to the overage run length in cumulative sum control charts. Technometrics, 1975, v. 17, № 1, p. 65 - 71.
17. Rodionov A.S., Shakhov V.V. About point-of-change problem in the information systems with exponetial distribution. Proceeding of Digital Computer Comminication Network Conference, Tel-Aviv (Israel), 1999, p.141 145 .
18. Ronen D., Perl Y. Heuristics for finding a maximum number of disjoint bounded path. Networks, 1984, V.14, N4.
19. Royston J. P., Abrams R. M. An objeective method for detecting the shift in basal body temperature in women. Biometrics, 1980, v. 36, p. 217 - 224.
20. Shalchov V.V. The problems of similation optimization. Bulletin of the Novosibirsk Computing Center, Special Issue, 1999.
21. Takacs L. Introduction to the Theory of Queues. London and New York: Oxford Univ. Press, 1962.
22. Watanable Т., Nakamura A. Edge-connectivity augmentation problems. J. of Computer and System Sciences, 1987, V.35.
23. Авен О.И., Турин Н.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982.
24. Адлер Ю.П., Маркова Е.В., Грановский Ю.В. Планирование эксперимента при поиске оптимальных условий. 2-е изд., перераб. и дополн. - М.: Наука, 1976. - 184 с.
25. Айламазян А.Н. Информация и информационные системы. -М.: Радио и Связь, 1982.
26. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987.
27. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. М.: Наука, 1989.
28. Башарин Г.П., Куренков Б.Е. О дискретной модели узла одной сети передачи данных. В кн.: Системы управления информационных сетей. М.: Наука, 1983. 82 с.
29. Беляков В.Г. и др. Об исследовании систем и сетей с бимодальной плотностью длительности обслуживания./ Труды ИВМ и МГ, серия: информатика, вып.З, 1998.
30. Берестнев B.JL, Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1976.
31. Бертсекас Д., Галагер Р. Сети передачи данных. М.: Мир, 1989.
32. Бродкин Л.И., Моттль В.В. Алгоритм обнаружения моментов изменения параметров уравнения случайного процесса. -Автоматика и телемеханика, 1976, №6, с. 23 -32.
33. Бусленко Н.П. Моделирование сложных систем. -М.: Наука, 1968.
34. Вальд А. Последовательный анализ.- М.: Физматгиз.1960, с. 328.
35. Гэри М., Джонсон Д. Вычислительные машины и трудноре-шаемые задачи. М.: Мир, 1982.
36. Дарховский Б.С., Бродский Б.Е. Непараметрический метод скорейшего обнаружения изменения свойств случайной последовательности. Теория вероятности и ее применение, 1987, т. 32, вып. 4.
37. Денисов В.И. Математическое обеспечение системы ЭВМ-экспериментатор. М.: Наука, 1977.
38. Денисов В.И., Попов А.А. Пакет программ оптимального планирования эксперимента. М.: Финансы и статистика, 1986.
39. Дрейпер Н., Смит Т. / Прикладной регрессионный анализ./М:" Статистика", 1973.
40. Зайченко Ю.П. Исследование операций Киев: В ища школа, 1975.
41. Клеинрок. Вычислительные системы с очередями. М.: Наука, 1982.
42. Клеинрок. Теория массового обслуживаниям. М.: Наука, 1982.
43. Клейнен Дж. Статистические методы в имитационном моделировании. Пер. с англ./Под ред. Адлера Ю.П.и Варыгина В.Н. М,-.Статистика,1978.
44. Клигене Н., Телькснис JI. Методы обнаружения моментов изменения свойств случайных процессов./ АиТ, 1983, н.10, с.5-56.
45. Кокс Д.Р., Смит B.JI. Теория очередей. М.: Мир, 1966.
46. Куликовский Л.Ф., Морозов В.К. Основы информационной техники.- М.:Наука, 1977.
47. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов. М.: Радио и связь, 1986.
48. Мизин И.А., Уринсон JI.C., Храмешин Г.К. Передача информации в сетях с коммутацией сообщений. М.: Связь, 1972.
49. Мину М. Математическое программирование. М.: Наука, 1990.
50. Морозов В.К., Долганов А.В. Основы теории информационных сетей.- М. .'Высшая школа. 1987.
51. Налимов В.В., Чернова Н.А. Статистические методы планирования экспериментов. М.: Наука, 1965.
52. Нейлор Т. Машинные имитационные эксперименты с моделями экономических систем. М.: Мир, 1975.
53. Никифоров И. В. Модификация и исследование процедуры кумулятивных сумм. Автоматика и телемеханика, 1980, № 9, с. 74 - 80.
54. Никифоров И.В. Применение кумулятивных сумм для обнаружения изменения характеристик случайного процесса./ АиТ, 1979, № 2, с.48-58.
55. Никифоров И. В. Применение последовательного анализа к процессам авторегрессии. Автоматика и телемеханика, 1975, №8, с. 174 -177.
56. Никифоров И.В. Последовательное обнаружение изменения свойств временных рядов. М.: Наука,1983.
57. Новые идеи в планировании эксперимента: Сб.статей. М.: Наука, 1969.
58. Попов О.В., Жигулин Л.Ф., Петровский И.Б. Об оценке вероятностных характеристик системы передачи данных впроцессе ее работы. Вопросы кибернетики, 1978, вып. 42, с. 57-63.
59. Риордан Дж., Вероятностные системы обслуживания. М.: Сов. радио, 1966.
60. Рогинский В.Н. Теория сетей связи. М.: Радио и связь, 1981, 192 с.
61. Родионов А.С. К вопросу автоматизации имитации сетей интегрального обслуживания. Труды ВЦ СО РАН. сер. Моделирование информационных сетей. Новосибирск, 1995.
62. Родионов А.С. Объектная ориентация в интеллектуальных системах моделирования. Труды ВЦ СО РАН. сер. Системное моделирование, вып.2, Новосибирск, 1994.
63. Саати T.JL, Элементы теории массового обслуживания с применениями. М.: Сов. радио, 1965.
64. Саати Т, Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. М.: Мир, 1973.
65. Системы управления информационных сетей: Сб.статей. -М.: Наука, 1983.
66. Солтон Дж. Динамические библиотечно-информационные системы: Пер. с англ./Под ред. Петрова.-М,:Мир,1979.
67. Труды международной научно-технической конференции "Проблемы функционирования информационных сетей". Новосибирск: 1991.
68. Федоров В.В. Теория оптимального эксперимента. М.: Наука, 1971.
69. Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966.
70. Фрэнк Г., Фриш И. Сети, связи и потоки. М.: Связь, 1978. 192 с.
71. Хикс Ч. Основные принципы планирования эксперимента. -М.: Мир, 1967.
72. Шахов В.В. Анализ системы сбыта в условиях нестабильного спроса. Труды конференции молодых ученых ИВМ и МГ СО РАН. Новосибирск, 1997.
73. Шахов В.В. "Вопросы имитационного моделирования". Труды 11-й Байкальской международной школы-семинара Методы оптимизации и их приложения, 1998, том 3, с. 191-195.
74. Шахов В.В. Задачи оптимизации имитационного эксперимента. Материалы международной конференции "Математическое моделирование и информационные технологии в образовании и науке". Алматы, Казахстан, 1998, с. 113.
75. Шахов В.В. Некоторые задачи оптимизации имитационного эксперимента. Третий Сибирский конгресс по прикладной и индустриальной математике, тезисы докладов, часть 3, Новосибирск, 1998.
76. Шахов В.В. "Некоторые задачи планирования имитационного эксперимента". Труды ИВМ и МГ, Серия: Системное моделирование, вып.4(22), 1997.
77. Шахов В.В. Некоторые задачи планирования имитационного эксперимента// Труды конференции молодых ученых ВЦ СО РАН. Новосибирск, 1995. - С. 200-212.
78. Шахов В.В., Родионов А.С. "О разладке в системах с экспоненциальным распределением". Труды ИВМ и МГ, Серия: Системное моделирование, 1998.
79. Шенннон Р. Имитационное моделирование систем искусство и наука. Пер. с англ./Под ред. Масловского Б.К. -М,:Мир,1978.
80. Ширяев А.Н.Вероятность. М.: "Наука", 1989, с.258.
81. Ширяев А. Н. Статистический последовательный анализ. -М.: "Наука", 1976.
82. Шметтеррер JL Введение в математическую статистику. -М.: "Наука", 1976, с.104.
83. Якубайтис Э.А. Информационно-вычислительные сети.-М: Высшая школа,1987.