ВВЕДЕНИЕ
В настоящее время в современном обществе изменился круг задач, решаемых человеком в различных сферах своей деятельности. Возникли новые сложные проблемы, для которых характерна ситуация, когда новые явления возникают сразу параллельно, а не «по очереди», и относятся к различным предметным областям. Л это потребовало организации совместной работы специалистов в разных областях экспертизы над решением единой задачи или проблемы. В связи с этим появился новый класс вычислительных систем -распределенные системы поддержки принятия решений /РСППР/, которые объединяют локальные специализированные системы принятия решений /СПР/, обладающие элементами искусственного интеллекта и решающих задачи в составной области экспертизы через обмен взаимными консультациями (сообщениями).
Действительно, увеличение объема информации, поступающей непосредственно к лицам, принимающим решения /ЛПР/, усложнение решаемых задач, необходимость учета большого числа взаимосвязанных факторов и быстро меняющейся обстановки требует шире использовать многопроцессорные вычислительные комплексы разной архитектуры и сети ЭВМ, ресурсы которых распределены в пространстве.
Слишком велика цена потерь, которые несут коммерческие фирмы и некоммерческие организации за счет недооценки важности комплексного подхода к созданию РСППР па основе распараллеливания вычислительных процессов РСППР должны не только быть информационными системами, т.е. выполнять функции сбора, обработки, хранения, передачи и представления информации, но и выполнять многовариантные расчеты, необходимые для принятия наиболее обоснованных управленческих решений.
В настоящее время в качестве распределенных вычислительных систем, как правило, используются распределенные экспертные системы, имеющие следующие особенности:
• физическая или логическая распределсиность в зависимости от того, располагаются они на разных узлах вычислительной сети или на одном узле; степень и характер распределенности зависит от характера вычислительных средств, реализующих экспертную систему; характера обрабатываемой информации;
• распределенность баз данных и знаний;
• распределенность задач; каждая экспертная система при рассмотрении ее как операционного узла способна выполнить одну или несколько задач, которые она может решить в зависимости от поступающей информации; выбор задач, которые способна решить система, зависит от доступных ей базы знаний, базы данных, входной информации;
• стратегия информационного обмена, которая определяет, когда узел должен передавать информацию другим узлам, какого типа информация должна передаваться и кто является адресатом информации.
Однако использование таких распределенных систем все еще наталкивается на определенные методологические трудности, связанные с объединением фрагментарно или полностью различных областей экспертизы (проблема представления знаний при наличии больших баз знаний), организацией распределенного принятия решений (логического вывода) при обходе нескольких областей экспертизы (одновременно в нескольких локальных СПР) для решения задач, требующих привлечения знаний многих экспертов и, с организацией параллельных вычислений, т.е. параллельного выполнения нескольких взаимодействующих процессов на разных процессорах, когда процессы обмениваются информацией и синхронизируют свои действия, ожидая, при необходимости, готовности друг друга к выполнению совместных вычислений.
Сама реализация параллельных вычислений в РСППР дала иное понимание самого вычислительного процесса, который трактуется как совокупность асинхронно выполняемых параллельных вычислительных процессов или параллельно реализуемых действий агентов. Развитие региональных и глобальных вычислительных сетей, к которым могут быть подключены локальные сети специалистов, обеспечивает получение всей необходимой
информации в реальном времени. А это налагает ограничения на скорость передачи информации из одной точки сети в другую б условиях наложения помех, искажения сообщений. Резкое увеличение объемов информации, перерабатываемых такой системой в единицу времени, влияет на ужесточение временных характеристик работы системы.
Дополнительным системным осложнением реализации распределенного подхода поддержки принятия решений является необходимость организации распределенного, а не централизованного управления вычислительным процессом, которое должно включать дисциплину планирования решения задач, поступающих в непредсказуемые моменты времени, в каждом узле сети; определение приоритетов задач, которыми запущен узел и которые стоят в очереди; определение механизма управления вычислительным процессом при изменении загрузки сети; приоритетное упорядочивание передачи сообщений; организацию выполнения параллельного шага распределенного принятия решений (РПР); выбор необходимого числа пакетов в шаге РПР; аналитическое и имитационное моделирование, как узла, так и всей распределенной вычислительной сети и т. д.
Единой методологической концепции решения указанных вопросов для выдачи рекомендаций по построению РСППР, когда в ее узлах расположены модули баз знаний (источники знаний) из разных, пусть и смешенных предметных областей, в настоящее время, по сути, нет. Не отражены в отечественной и зарубежной литературе экспериментальные исследования количественно-качественных показателей функционирования рассматриваемых распределенных СППР.
Перечисленные выше вопросы, требующие определения необходимых вычислительных ресурсов узлов сети, а так же существующие проблемы неопределенности, противоречивости, свойственные процессам принятия решений, являют собой краткий перечень типов трудностей, возникающих при практической реализации распределенного подхода поддержки принятия решений, которые вместе со сложностями подбора и реализации необходимого математического обеспечения, определяют актуальность создания методологии
б
построения РСППР.
Цель исследования
заключается в разработке алгоритмов и средств построения РСППР с использованием локальных систем принятия решений с элементами искусственного интеллекта и аналитических моделей.
Задачи исследования:
• обоснование необходимости разработки моделей и алгоритмов создания РСППР для различных прикладных областей;
• анализ существующих средств представления знаний и стратегий выполнения распределенного принятия решений с целью использования в РСППР и выбора компонентов ее архитектуры;
• исследование специфики, условий и принципов организации взаимодействия локальных СПР в сети на основе консультаций и особенностей многопользовательской работы РСППР;
• выбор и обоснование модели обмена сообщениями в составной предметной области и разработка логической структуры узла РСППР, механизмов РПР и управления потоками заданий на основе системно-сетевой организации взаимодействия прикладных процессов;
• разработка моделей и алгоритмов формализованного планирования решений задач, поступающих в непредсказуемые моменты времени, в узлах сети, оценки приоритетов стоящих в очереди задач, управления процессом обработки информации при изменении загрузки сети и одновременного выбора характеристик нескольких узлов сети в условиях шумов;
• исследование основных количественных и качественных параметров функционирования РСППР на основе имитационного моделирования распределенной вычислительной сети.
Идея работы
заключается в выявлении взаимосвязей между выполняемым параллельным шагом распределенного принятия решений и формируемой дисциплиной обмена знаниями для локальных систем принятия решений.
Основные научные положения, разработанные соискателем, и их новизна:
- механизмы распределенного принятия решений с отложенным выполнением и управления потоками заданий при совместном решении сложной проблемы несколькими ЛПР позволяют, в отличие от существующих, найти оптимальные отношения между основными программными и информационными элементами вычислительной сети ЭВМ;
- модели и алгоритмы распределенного управления ходом процесса в сети на основе теорий отсекающих плоскостей Гомори, принципов Парето и равномерной загрузки узлов отличаются возможностью находить не полностью загруженные процессоры, перераспределять задачи между узлами сети при их решении и загружать РСППР в режиме, близком к оптимальному, при изменении загрузки процессоров сети с учетом возможных изменений приоритетов стоящих в очереди задач, поступающих в непредсказуемые моменты времени;
- модель информационной цепочки из нескольких промежуточных узлов при обработке и передаче сообщений от узла - источника до узла - адресата в условиях шумов на основе положений теории информации, позволяет, в отличие от известных, определить условия повышения достоверности передачи сообщений, не снижая величины пропускной способности;
- имитационная модель позволяет, в отличие от существующих, найти зависимость производительности РСППР от производительности сетевой операционной системы и определить область изменения характеристик сетевой операционной системы (время обслуживания для распределенного принятия решений, объем концентратора и т.д.), в которой ее применение для организации многопользовательского режима работы оправдано.
Достоверность научных положений, выводов и рекомендаций, сформулированных в диссертации, подтверждается:
- корректным использованием в проведенных исследованиях методов теории исследования операций, принятия решений, многокритериальной оптимизации, массового обслуживания, параллельных процессов обработки информации, систем искусственного интеллекта, статистического анализа;
- положительными результатами имитационного и экспериментального моделирования режимов последовательного выполнения заданий и параллельного выполнения шага распределенного поиска решений при совместной работе РСППР и специализированной сетевой операционной
8
системы (СОВПП) в локальной сети ЭВМ с помощью разработанных инструментальных средств, показавшими достаточную для практики точность полученных оценок временных показателей (время обслуживания заявки, время параллельного выполнения шага РПР, время обработки модуля базы знаний, время управления СОВПП и т.д.) и производительности РСППР (максимальные отклонения в пределах 6% от реальных значений).
Научная значимость работы
состоит в разработке комплексного подхода к распределенному управлению процессами обработки информации и механизма формализованного описания взаимодействия нескольких локальных СПР при параллельной обработке информации в узлах вычислительной сети ЭВМ, который включает модели и алгоритмы обмена сообщениями и распределенного решения задач, поступающих в непредсказуемые моменты времени из нескольких предметных областей, что позволяет построить алгоритмы и модели создания распределенных систем поддержки принятия решений для различных приложений.
Практическая значимость работы состоит :
• в формировании алгоритмов выполнения параллельного шага распределенного принятия решений, позволяющих определять оптимальное число свободных процессоров для управления параллельным РПР;
• выборе рациональной частоты обращений к блоку управления разделяемой памятью, при которой не будет перегрузки сетевых средств непроизводительной работой и сокращается время выполнения РПР;
• проведении имитационного моделирования как отдельного узла, так и всей распределенной вычислительной сети;
• создании инструментальных средств для реализации предложенных алгоритмов распределенной обработки данных в локальной сети ЭВМ;
• внедрении основных результатов диссертационной работы в разработки ЗАО «НПО ГидроМаш» (г.Москва), а также в учебный процесс для подготовки бакалавров, специалистов и магистров по направлению 550800 «Информатика и вычислительная техника» на кафедре «Автоматизированные системы управления» МГТУ.
Апробация работы.
Основные результаты диссертации и ее отдельные положения докладывались на семинарах кафедры АСУ и следующих конференциях: Product Development in Engineering Education (Лохмар, Германия, 1998г.), «Неделя горняка» (г. Москва, 2001-2003 гг.), Advanced Engineering Design (Прага, Чехия, 2003г.).
Публикации.
По теме диссертации опубликовано 6 научных работ.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 132 наименований, содержит 23 рисунка, 8 таблиц.
10
1. ОБЗОР ТЕОРЕТИЧЕСКИХ ИССЛЕДОВАНИЙ В ОБЛАСТИ
ПОСТРОЕНИЯ СИСТЕМ ПРИНЯТИЯ РЕШЕНИЙ НА ОСНОВЕ
РАСПРЕДЕЛЕННОЙ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ИНФОРМАЦИИ.
1.1 Особенности компьютерной поддержки принятия согласованных групповых решений
Компьютерная система поддержки групповых решений предназначена для оказания помощи участникам переговоров в их проведении и выработке согласованного решения. Помощь СППР заключается в [ 12 ]:
• сборе данных и компьютерной поддержке анализа обстановки, сложившейся перед обсуждением проблемы;
• организации связи всех участников переговоров вычисли тельной сетью независимо от того, где они находятся, и предоставления им возможности легкого обмена предложениями и контрпредложениями;
• помощи в оценке приоритетов отдельных составляющих обсуждаемой проблемы;
• предоставлении средств формализации предложений, делаемых каждым участником переговоров, включающих алгоритмы их оценки, ранжирования и моделирования последствий;
Такие системы имеют место при принятии стандартных решений в процессе купли продажи, предоставлении кредита и т.д. Наиболее интересный для нас класс переговоров: переговоры между экспертами и/или руководителями с помощью систем поддержки переговоров.
Рассмотрим общие задачи компьютерных систем поддержки принятия решений, поскольку одной из основных задач СПП является согласование решений.
Принятие решений - каждодневная деятельность человека, часть его повседневной жизни. Простые, привычные решения человек принимает легко,
часто автоматически, не очень задумываясь. В сложных и ответственных случаях
11
он обращается к друзьям, родственникам, опытным и знающим людям за подтверждением споего решения, несогласием с ним или за советом: каким могло бы быть другое решение. Часто обращаются к книгам, в том числе и религиозным, даже астрологии и гаданиям. Такие обращения - это процесс поддержки принятия решения.
Принятие решения в большинстве случаев заключается в генерации возможных альтернатив решений, их оценке и выборе лучшей альтернативы.
При выборе альтернатив приходится учитывать большое число противоречивых требований и, следовательно, оценивать варианты решений по многим критериям. Противоречивость требований, неоднозначность оценки ситуаций, ошибки в выборе приоритетов сильно осложняют принятие решений.
Сейчас положение изменилось. Большое количество задач, если не большинство, являются многокритериальными задачами, в которых приходится учитывать большое число факторов. В этих задачах человеку приходится оценивать множество сил, влияний, интересов и последствий, характеризующих варианты решений. Например, при принятии решения в строительстве завода приходится учитывать не только ожидаемую прибыль и необходимые для строительства капиталовложения, но и динамику рынка, действия конкурентов, экологические, политические, социальные факторы и т.п.
Системы поддержки принятия решений существуют очень давно: это военные советы, коллегии министерств, всевозможные совещания, аналитические центры и т.д. Хотя они никогда не назывались системами поддержки принятия решения, но выполняли именно их задачи (в некоторых случаях частично). До последнего времени они, естественно, не использовали вычислительные машины и правила их функционирования, хотя регламентировались, но были формализованы далеко не так, как это требуется в человеко-машинных процедурах.
Термин "система поддержки принятия решений" (СППР) появился в начале семидесятых годов [5]. За это время дано много определений СППР [28,29,119], характеризующие функции СППР по аналогии с процессом принятия решения
человеком. Если исходить из необходимости осуществления компьютерной
12
поддержки на всех этапах принятия решения человеком, то СППР можно определить как человеко-машинную систему, позволяющую руководителем использовать свои знания, опыт и интересы, объективные и субъективные модели, оценки и данные для реализации компьютерных методов выработки решений и выполняющую следующие функции:
1. Производит анализ обстановки (ситуаций).
2. Генерирует возможные управленческие решения (сценарии действий).
3. Осуществляет оценку сгенерированных сценариев (действий, решений) и выбирает лучший.
4. Обеспечивает постоянный обмен информацией принимаемых решений и помогает согласовать групповые решения.
5. Моделирует принимаемые решения (в тех случаях, когда это возможно).
6. Осуществляет компьютерный анализ возможных последствий принимаемых решений.
7. Производит сбор данных о результатах реализации принятых решений и осуществляют оценку результатов.
1.2. Особенности целесообразности построения РСМПР и схема ее
функционирования
1. Характер распределенное! и. СППР могут быть сосредоточенные и распределенные [27].
1.1. Сосредоточенные СППР реализуются на одной вычислительной машине. Они выполняют функции 1-3, 5-7 перечисленные выше (или часть их), помогая небольшой группе специалистов оценивать обстановку и согласовывать принимаемые решения.
1.2. Распределенные вычислительные системы могут быть распределены пространственно и/или функционально. Пространственно распределенные СППР состоят из локальных СППР, расположенных в связанных между собой узлах вычислительной сети. Каждая из них может независимо решать свои частные задачи, обслуживая своего менеджера или специалиста. Но для решения общей проблемы ни одна из них не обладает достаточными знаниями, информацией и
13
ресурсами (или некоторыми из этих составляющих). Общую проблему они могут решать только сообща, объединяя свои локальные возможности, согласовывая принятые частные и вырабатывая общие решения. Функционально распределенные системы состоят из нескольких экспертных систем (или СППР), связанных между собой информационно и установленных на одной вычислительной машине (пространственно они сосредоточены). Распределенные системы выполняют функции 1 -7, перечисленные в разд. J. 1 (или часть их).
Необходимо особо отметить очень распространенный класс систем -иерархические системы поддержки принятия решений.
Иерархические вычислительные подсистемы поддержки переговоров располагаются в узлах, связанных между собой вычислительной сетью. По значимости вырабатываемых рекомендаций узлы не равноправны. Самый простой пример такой системы - это система, состоящая из подсистем W\, W^..., W'n первого уровня и одной подсистемы W2i второго (более высокого) уровня. Цель подсистемы W2i - влиять на низшие подсистемы таким образом, чтобы достигалась общая цель, заданной для всей системы. Такая двухуровневая система может служить в качестве элементарного блока при построении более сложных систем.
Распределенные СППР могут иметь следующие модификации:
1.2.1. Рекомендации предлагают несколько локальных СППР, находящихся в одном или различных узлах. Они могут подходить к ним с разных точек зрения, могут быть предложены различные рекомендации, которые теперь уже должны будут выбирать и согласовывать специалисты, находящиеся, возможно, в различных - узлах сети. Если один из узлов передал не одно, а несколько решений, то ситуация принципиально не меняется.
1.2.2. Локальные СППР, находящиеся в разных узлах, выдают между собой варианты (или один вариант) решения. Руководитель выбирает один из вариантов предложенных решений с возможной его коррекцией, если это необходимо.
Эта модификация СППР аналогична модификации 1.1.2 стой разницей, что решение вырабатывает не одна, а несколько локальных систем поддержки
переговоров.
14
2. Типы структурированности проблем.
Опыт решения различного класса задач выявили большие различия в природе изучаемых систем. В связи с этим была предложена следующая классификация проблем [28].
2.1. Хорошо структурированные или количественно сформулированные проблемы, в которых существенные зависимости выяснены настолько хорошо, что они могут быть выражены в числах или символах, получающих, в конце концов, численные оценки. Этот класс задач широко применяется при оценке и выборе элементов технических устройств, то есть в тех случаях, когда существуют адекватные математические модели устройств или процессов и есть опытные данные, позволяющие априорно определить параметры этих моделей.
2.2. Неструктурированные или качественно выраженные проблемы, содержащие лишь описание важнейших ресурсов, признаков и характеристик, количественные зависимости между которыми совершенно не известны.
2.3. Слабо структурированные или смешанные проблемы, которые содержат как качественные, так и количественные элементы, причем качественные, малоизвестные и неопределенные стороны проблем имеют тенденцию доминировать.
3. Характер оценки результата ситуации и согласованного решения. В
соответствии с [28] проблемы, решаемые с помощью СППР, могут быть с объективно и субъективно оцениваемыми результатами.
3.1. Задачи с объективно оцениваемыми результатами - это задачи, для которых может быть объективно определен факт их окончательного решения. В этих задачах в явном виде задан критерий, позволяющий определить успешность достижения цели. Сюда относятся сложные комбинаторные задачи, различные игры с четкими правилами (шахматы, шашки), задачи проектирования и т.д. Для этих задач, как правило, имеются хорошие аналитические или алгоритмические модели. Для них имеется возможность объективной оценки результата решения или хотя бы сравнительной оценки нескольких вариантов решений.
15
3.1.1. Существует класс задач, в которых анализ сложившейся обстановки, принятие по ней решения является достаточным и не требует дальнейшего анализа (во всяком случае, но данной конкретной ситуации). Такой компьютерный анализ назовем статистическим. Примером такого анализа является решение по ликвидации аварийного разлива нефти. Принимается решение обеспечивающее, исходя из имеющихся возможностей, наиболее безопасный, быстрый и дешевый способ ликвидации аварии. Вопрос о ее дальнейших последствиях и необходимых мерах (экологических, финансовых и др.) не является, как правило, предметом обсуждения при выборе средств и методов ликвидации аварии. Это другая проблема. Для многих задач такой подход дает очень хорошие результаты.
3.1.2. Однако, во многих случаях ситуация оказывается более сложной. Существует очень большой класс проблем, в которых нельзя оценить эффективность решения без анализа возможных последствий; таковы, например, подавляющее большинство политических и экономических решений, выбор хода в шахматах и т.д.
3.2. К задачам с субъективно оцениваемыми решениями отнесем задачи, для которых объективная оценка результата решения отсутствует, и ее заменяют экспертные оценки, основанные на эвристических предпочтениях. То есть качество решения основывается на субъективных оценках человека. К таким задачам относятся принятие экономических и политических решении, задачи, медицинской диагностики и т.д.
4. Характер ситуации, в которой принимается согласованное решение.
4.1. Принятие решений в экстремальной ситуации характеризуется острым дефицитом времени и, в большинстве случаев, быстро меняющейся обстановкой. Эти два фактора сильно усложняют процесс принятия согласованных решений для руководителей или специалистов, участвующих в переговорах. Задачи, решаемые в экстремальных ситуациях, можно подразделить на ранее решавшиеся и уникальные. Однако даже при решении аналогичных задач практически не бывает двух чрезвычайных одинаковых ситуаций, поэтому наряду с
16
использованием информации, хранящейся в базе данных, специалисты должны вводить новую информацию, отображающую данную чрезвычайную ситуацию, корректировать "веса" (значимость) критериев, модифицировать метод ликвидации чрезвычайной ситуации и т.д.
Пропускная способность - один из важнейших сточки зрения пользователей факторов. Она оценивается количеством данных, которые сеть может передавать в единицу времени от одного подсоединенного к ней устройства к другому [25].
Идеальная характеристика. К подобному виду характеристики стремится каждый разработчик. Пропускная способность монотонно растет по мере роста нагрузки до тех пор, пока нагрузка на сеть не достигает некоторого критического значения. После этого пропускная способность остается на постоянном максимальном уровне и не зависит от дальнейшего увеличения нагрузки.
Хорошая характеристика. Это практическая альтернатива идеальной ситуации. Пропускная способность сети плавно возрастает по мере увеличения нагрузки на сеть, постепенно приближаясь к максимальному значению. Плохая характеристика встречается на практике, но не может удовлетворить пользователя. Пропускная способность сети растет с увеличением нагрузки на нее до некоторого пикового значения, не достигая теоретического максимума. Затем она падает, хотя нагрузка на сеть продолжает увеличиваться.
Недопустимая характеристика. Практических реализаций сети с подобными характеристиками не должно быть. Пропускная способность сети растет до пикового значения, которое ниже теоретического максимума, а затем падает до нуля, когда на сеть достигает некоторой критической точки. В этой точке сеть блокируется, и дальнейшим увеличением нагрузки на сеть уже нельзя добиться передачи данных через нее.
Основные факторы, влияющие на пропускную способность сети. Предполагается, что подключенные к сети устройства уже подготовили информацию к передачи, поместив ее в соответствующие пакеты.
Задержка в очереди. Когда пакет готов к передаче, его необходимо поместить в очередь в интерфейсном устройстве сети вслед за другими пакетами,
ожидающими передачу.
17

Получить работу