Содержание к диссертации
Введение
РАЗДЕЛ I. Принципы исследования диалоговых систем телеобработки информации 9
1.1. Существующие методы исследования диалоговых систем 10
1.2. Особенности ДСТИ в ГА на примере узла телеобработки информации
1.3. Анализ метода многокритериальной оптимизации
1.4. Постановка задачи исследования
Выводы по разделу 37
РАЗДЕЛ II. Математическая модель
2.1. Модель подсистемы
2.2. Модель подсистемы
2.3. Характеристики
Выводы по разделу
РАЗДЕЛ III. Методика прогнозирования характеристик 58
3.1. Алгоритм вычисления значений прогнозируемых характеристик 59
3.2. Зондирование пространства параметров . 66
3.3. Верхние границы времени обработки для системы
3.4. Методика прогнозирования характеристик при системном подходе к моделированию. 83
Выводы по разделу 89
РАЗДЕЛ ІV. Оптимизация 90
4.1. Алгоритм выбора оптимального варианта 91
4.2. Функциональные ограничения 93
4.3. Сравнитальный анализ двух методик прогнозирования 106
Выводы по разделу 110
Основные результаты
Литература
- Существующие методы исследования диалоговых систем
- Анализ метода многокритериальной оптимизации
- Алгоритм вычисления значений прогнозируемых характеристик
- Функциональные ограничения
Существующие методы исследования диалоговых систем
В настоящее время наиболее широко используются два подхода к доследованию диалоговых систем. Первый подход основан на математическом моделировании ІЇ$+%&,Щ; второй - на имитационном [4%&].
Ключевым вопросом при построении модели сложного объекта является вопрос адекватности, которую следует понимать в относительном змысле. В общем случае доказательство адекватности модели и объекта может быть проведено по следующей схеме. Постулируется вид функционала качества, значение которого может быть вычислено по заданным значениям параметров модели. На объекте ставится эксперимент, целью которого является определение параметров режима функционирования эбъекта и определение экспериментального значения функционала качества. Если при подстановке значений параметров вычисленное значение рункционала качества близко к полученному экспериментальному, то принято модель считать адекватной объекту относительно данного критерия качества. Следует заметить, что натурные эксперименты часто оказываются дорогостоящими ; кроме того, модель признанная адекватной объекту по одному критерию может оказаться не адекватной при выборе другого критерия.
В тех случаях, когда принципиально нельзя провести серию экспериментов, например, невозможно измерить время срабатывания программного модуля до тех пор, пока он не отлажен, качество моделей приходится оценивать косвенным образом. Под косвенными оценками имеются в виду оценки на допустимые границы изменения параметров и значений функционала качества, которые не должны противоречить здравому смыслу.
Математическим аппаратом, который используется при построении моделей диалоговых систем является аппарат теории массового обслуживания [НЧ +4 8].
В заключение следует заметить, что подход к построению математических моделей ДСТЙ на основе чисто аналитических методов ТМО имеет дно принципиальное ограничение, которое является следствием одной нерешенной проблемы теории СИО. Эта проблема построения теории сис-гемы G1QI1 , которая была сформулирована А.Я.Хинчиным в 30-е годы. В последующее время была построена теория систем МКМ4 и решения проблемы системы GUQll не известно. Более того, для этой системы нет даже аналогов формул Поллячека - Хинчина, позволяющие находить средние значения характеристик системы по известным первым моментам распределений интервалов потока запросов и времени обслуживания. Следствием этого является ограниченность возможностей использования аналитической теории СМО для построения математических моделей диалоговых систем телеобработки информации.
Имитационное моделирование сложной системы, в том числе диалоговой системы, есть метод проведения на цифровых вычислительных малинах экспериментов с математическими моделями, которые описывают поведение сложных систем в течение продолжительных периодов времени /2, 3] При таком подходе диалоговая система рассматривается как система массового обслуживания, которая характеризуется? I/ потоком заявок, который задается функцией распределения интервалов времени между поступлением двух соседних заявок ; 2/ совокупностью обслуживающих приборов, для каждого из которых известна функция распределения времени обслуживания заявок ; 3/ дисциплиной обслуживания заявок, находящихся в очереди. Состояния системы характеризуются вероятностями ph() / в момент времени -Ь в системе и в очереди находится и заявок/. Моделирование процесса обслуживания сводится к получению реализации случайных величин и к подсчету числа требований в системе в момент t0 . Проводя моделирование N раз по независимым последовательностям случайных чисел, можно оценить вероятность Р„ ), построив гистограмму распределения числа требований в системе в «омент 1Ь . Б случае, когда требуется определить среднее время ожидания в очереди на отрезке времени С,ТД приходится просматривать независимых реализаций поведения системы от момента времени і-о цо момента времени.
Анализ метода многокритериальной оптимизации
Настоящий раздел содержит анализ последовательности этапов, характерных для системного подхода при моделировании ДСТИ и определение места методики прогнозирования характеристик в этой последовательности. Задачи разработки и проектирования сложных систем и моделирования последних на этапе проектирования тесно связаны. ДСТИ представляет сложный аппаратурно-программный комплекс, проектирование которого невозможно без всестороннего анализа, который возможен на основе чисто аналитических моделей, вычислительных экспериментов, имитационного моделирования.
Математические модели обычно предназначаются для решения таких задач как: - качественное изучение режимов функционирования системы ; - определение количественных показателей эффективности ; - определение /отбор/ оптимальных вариантов из множества альтернативных. Математическое моделирование в рамках системного подхода к изучению сложных систем может стать не только методом исследования, но и инструментом проектирования. Преимущества математического моделирования сводятся к следующим факторам: - анализ и синтез структур ДСТИ возможен только с использова нием математических моделей, имеющих программную реализацию, которая позволяет получать численные результаты в случае большой размернос ти пространства параметров ; - процессы обработки запросов ДСТИ настолько сложны, что тре-Зуют моделирования на ЭВМ ; - решение сложных многокритериальных задач, к которым относится задача проектирования ЗХСТИ, с необходимостью приводит к процедурам принятия решения, которые невозможны без интерактивного режима работы с ЭВМ. Эти аргументы позволяют рассматривать математическое моделирование на ЭВМ в качестве основного аппарата исследования и проектирования ЭСТИ. В [63 дается следующая последовательность задач по математическому моделированию, которая возникает при системном подходе к проектированию сетей связи ; 1. выбор варианта построения системы и принципов ее функционирования на этапе эскизного проектирования /задача синтеза и ориентировочных оценок/ ; 2. сравнение конкурентоспособных вариантов системы и выбор предпочтительного варианта для дальнейшей проработки на стадии технического проектирования /точные оценки, многокритериальный синтез и принятие решений на множествах вариантов/ ; 3. моделирование работы программного обеспечения /моделирование управляющих алгоритмов и проверка правильности заложенных в них принципов, создание макетов программ, которые предполагается разрабатывать для реальной системы/У 4. оценка характеристик проектируемой системы на имитационной модели и исследование качества функционирования системы ; 5. проведение полунатурных испытаний системы с использованием частично штатного расписания оборудования и модельного блока ; 6. получение экспериментально-аналитических оценок реальных показателей качества функционирования системы, в первую очередь вероятностно-временных показателей ; 7. моделирование типовых процессов функционирования системы в реальных условиях с учетом данных по результатам опытной эксплуатации. Математическое моделирование при системном родходе понимается достаточно широко. На первых этапах рассматриваются как аналитические модели, целью которых в основном является общее формальное представление проектируемой системы. Эти модели позволяют произвести лишь качественные и груоые количественные оценки рассматриваемых вариантов систем. Детальные исследования проводят на специальной программной модели, построение которой возможно, например, с помощью систем автоматизированного проектирования /САПР/ см. [2,3,4/121,15 16] Существенная особенность системного подхода к моделированию ДСТИ состоит в том, что разработка различных математических моделей представляет собой взаимосвязанный процесс. Взаимосвязь эта проявляется в том, что модели создаваемые на разных этапах должны согласовываться друг с другом. Согласованность моделей следует понимать в том смысле, что результаты, полученные на одной модели, должны являться входными данными для следующей. С позиций современных концепций системного анализа, вышесказанное приводит к необходимости построения комплексной модели проектируемой системы, т.е. такой модели, которая бы объединяла в себе все разрозненные математические модели, каждая из которых ориентирована на решение задачи определенного этапа. Б работе 16] исходя из методологии системного подхода сформулированы следующие условия, необходимые для построения комплексной модели. 1. На каждом этапе создания комплексной модели ее текущее состояние должно позволять решать определенный круг взаимосвязанных задач. 2. Комплексная модель представляет собой математическое формализованное представление реального процесса проектирования системы. Характер взаимосвязи различных подсистем в системе должен предопределять характер взаимосвязи соответствующих частных моделей и программных блоков в комплексной моделе.
Алгоритм вычисления значений прогнозируемых характеристик
Выражение /42 / имеет следующий смысл для каждого фп задается некоторый максимальный уровень о( h , после чего пытаются как можно больше уменьшить этот максимальный уровень по самому худшему показателю. В работах [6 62,6]рассмотрено много таких обобщенных критериев ; их разнообразие является следствием того, что эти критерии трудно сопоставимы.
Попытки искать решение многокритериальной оптимизационной задачи на пути сведения ее к однокритериальной оптимизационной задачи следует рассматривать как отказ от задачи наховдения единственной оптимальной точки во множестве Парето и замена этой задачи следующей: среди возможных вариантов построения обобщенного критерия найти единственный, оптимальный. Другими словами: задача нахождения оптимальной точки заменяется на задачу нахождения оптимального обобщенного критерия, которая не проще.
Другим возможным подходом к проблеме выбора единственной точки среди точек, оптимальных по Парето, является метод экспертных оценок [ 65/. Сущность этого метода состоит в формировании кол лектива специалистов /совета экспертов/, который в отсу "сзвии объективного критерия сравнения осуществляет коллективный выбор одного варианта из множества альтернативных. Назовем совокупность исходных данных, на косновании которых совет экспертов принимает решение репрезентативным выборочным пространством. Качество последнего сильно влияет на успех экспертной оценки, так как вряд ли можно ожидать успешной оценки, которая основана на "плохом" репрезентативном выборочном пространстве.
При использовании метода экспертных оценок возникает проблема, аналогичная проблеме переформулировки оптимизационной задачи в случае замены многих критериев - одним.
В рассматриваемом случае задача выбора оптимальной точки среди множества Парето, заменяется задачей построения оптимального репрезентативного выборочного пространства среди множества альтернативных вариантов. Метод зондирования пространства параметров на основе ЛГЦ. последовательностей гарантирует оптимальность репрезентативной выборки в силу аргументов, приведенных в разделе 3.2L.
Конкурирующим методом зондирования пространства параметров является метод Монте-Карло. Последний уступает методу зондирования пространства параметров на основе ЛГЦ последовательностей по быстродействию и, следовательно, по эффективности /за одинаковое время методом АП-с последовательностей можно вычислить больше точек, чем методом Монте-Карло/.
Блок-схема алгоритма выбора оптимального варианта ДСТИ представлена на рис. 2.0. Этот алгоритм включает в себя алгоритм прогнозирования характеристик ДСТИ /см. раздел В А /. Ниже содержится описание блоков, отсутствующих в блок-схеме алгоритма прогнозирования. Блок ввода критериальных ограничений. Осуществляет ввод зна чении которые определяются советом экспертов по таблицам испытаний и являются верхними гра ницами для значений критериев оптимизации ДСТК. Едок проверки на пустоту множества Парето. Проверка состоит в просмотре таблицы испытаний с целью выявления всех номеров точек, посредством которых было проведено зондирование пространства допустимых решений, для которых значения всех 2f)QC\ критериев оптимизации не превосходят соответствующих критериальных ограничений. Если множество Парето не пусто, то происходит формирование массива точек, образующих оптимальную репрезентативную выборку. Выбор единственного элемента этого массива /оптимального варианта ДСТИ/ осуществляется методом совета экспертов. Процесс принятия решения описан в разделе Блок совет экспертов П. Вход в этот блок происходит в случае, когда множество Парето пусто. В этой ситуации совет экспертов должен ответить на единственный вопрос: возможно ли изменение /в сторону увеличения/ по крайней мере одного из критериальных ограничений. Если ответ положительный, то есть существует хотя бы одно критериальное ограничение, увеличение значения которого возможно.
Функциональные ограничения
Синтезирован алгоритм многокритериальной оптимизации ДСТИ, основе зондирования пространства параметров точками, образую-ли ЛП- последовательность.
Получены стохастические функциональные ограничения, позволя-ш оценивать вероятность неравенств, выражающих условие того, ) время /стоимость/ обмена информацией между терминалом и цент-л обработки не превосходит среднего времени / стоимости/ соб-зенной обработки запроса.
Сравнительный анализ методики прогнозирования характеристик М, основанной на имитационном моделировании и методики, осно-іной на методе зондирования пространства параметров точками ;ледовательностей показал преимущество последней. Выигрыш при юльзовании второй методики получается за счет того, что порядок [бки во втором случае (І/N) , в то время как порядок [бки при использовании метода Монте-Карл. 1. На основе теоретико-вероятностного подхода построена модель процесса передачи информации между терминалом и центром обработки запросов, территориально-разнесенной ДСТИ. Модель учитывает особенности протокола передачи информации, принятого ИВС ГА. 2. Разработана модель собственной обработки запроса ДСТИ. Эта модель построена на основе алгоритмического подхода теории графов и сетевой модели Джексона. Предложенная модель позволяет находить вектор интенсивностей потоков входных запросов без имитационного моделирования. 3. Построена модель полной обработки запроса территориально-разнесенной ДСТИ, учитывающая особенности ИВС ГА. 4. Для разработанных моделей получены соотношения, позволяющие проводить сравнительный анализ времени /стоимости/ собственной обработки запроса с сопутствующим временем /стоимостью/ обмена информацией между терминалом и центром. Учет этих соотношений особенно важен при проектировании территориально-разнесенных ДСТИ. 5. Разработана модификация метода зондирования пространства параметров ЛПХ " последовательностями для прогнозирования характеристик ДСТИ. 6. Построены алгоритмы вычисления прогнозируемых характеристик. Эти алгоритмы обеспечивают возможность интерактивного режима проектирования ДСТИ. 7. Поставлена задача многокритериальной оптимизации для проектирования территориально-разнесенной ДСТИ ИВС ГА со стохастическими ограничениями ; разработан алгоритм решения поставленной задачи. 8. Проведен сравнительный анализ предложенной методики прогнозирования и методики имитационного моделирования. Обоснована эффективность предложенной методики. Результаты настоящей диссертационной работы: - доложены и обсуждены на научно-технических семинарах кафедры "Автоматизированные системы управления" Московского института инженеров гражданской авиации ; - на ІУ Всесоюзной научно-технической конференции "Эффективность и оптимизация систем и процессов гражданской авиации" /март 1979, МИИ ГА г. Москва/ ; - на Всесоюзной научно-технической конференции, посвященной 10-летию Московского института инженеров гражданской авиации "Совершенствование системы управления эффективностью производства в гражданской авиации с применением АСУ и вычислительной техники" /март 1931 г./ - отражены в отчетах по научно-исследовательской работе, проводимой кафедрой АСУ Московского института инженеров гражданской авиации в рамках хоздоговора с ЦНИИ АСУ ГА /г.Рига/ и Казахским филиалом ВГІІТИ ЦСУ СССР /г. Алма-Ата/. - внедрены в НИР "Разработать научные основы создания и развития центров обработки данных и сети передачи данных" /шифр S.0I.29/, выполняемой в соответствии с планом НИР МГА по решению научно-технической проблемы 0.80.09 ГКНТ СМ СССР, проводимой ЦНИИ АСУ ГА /г.Рига/.
