Содержание к диссертации
Введение
1. Анализ систем поддержки принятия решений и средств автоматизации их разработки, направления по совершенствованию технологии автоматизированного проектирования СППР 16
1.1. Анализ методов и инструментальных сред, используемых в системах поддержки принятия решений 16
1.2. Технология проектирования и разработки промышленных экспертных систем 27
1.3. Методы решения задач и их повторное использование в системах поддержки принятия решений 38
1.4. Цель и задачи исследования 42
2. Методика автоматизации проектирования прикладных систем поддержки принятия решений и формирование базы знаний методов принятия решений 45
2.1. Разработка методики автоматизированного проектирования систем поддержки принятия решений 45
2.2. Формирование базы знаний методов принятия решений на основе их классификации 54
2.3. Разработка базы знаний методов принятия решений и формальной спецификации задачи 68
2.4. Основные выводы главы 76
3. Математическое моделирование задач оптимального синтеза структуры программного обеспечения СППР на основе градиентных методов оптимизации 77
3.1. Построение комбинаторной модели рационального выбора СППР, проектируемой на основе набора компонентов 77
3.2. Разработка оптимальной компонентной структуры прикладной СППР в подсистеме автоматизированного проектирования 88
3.3. Разработка вероятностного алгоритма оптимального выбора вариантов СППР, создаваемых на основе набора программных компонентов 94
3.4. Основные выводы главы 104
4. Реализация и применение подсистемы автоматизированного проектирования прикладных СППР 106
4.1. Разработка структуры подсистемы автоматизированного проектирования прикладных СППР 106
4.2. Реализация повторного использования методов поддержки принятия решений в подсистеме автоматизированного проектирования СППР 115
4.3. Характеристики прикладных СППР "Альтернатива" и "Конкурс", созданных с применением подсистемы автоматизированного проектирования прикладных СППР 122
4.4. Основные выводы главы 129
Заключение 130
Литература 132
Приложения
- Технология проектирования и разработки промышленных экспертных систем
- Формирование базы знаний методов принятия решений на основе их классификации
- Разработка оптимальной компонентной структуры прикладной СППР в подсистеме автоматизированного проектирования
- Реализация повторного использования методов поддержки принятия решений в подсистеме автоматизированного проектирования СППР
Введение к работе
Актуальность темы. Современный этап развития общества характеризуется его глубокой и всесторонней информатизацией. Направления развития информатики увязываются с возможными решениями главных проблем развития человечества. Одна из них состоит в создании инструмента, способного помочь человеку в принятии решений любой сложности, любого уровня, в любой сфере деятельности, локального и глобального масштабов. Основой такого инструмента служит «коллективный разум», или коллективные знания, хранящиеся в компьютерных системах. Однако анализ состояния разработок в области поддержки принятия решений показывает крайнюю ограниченность методов и средств, используемых для решения подобного класса задач. В связи с этим актуальность темы исследования определяется необходимостью развития методологии создания систем поддержки решений.
Обостряется проблема несоответствия теоретической базы поддержки принятия решений изменившимся требованиям к качеству управления предприятиями. В рамках направления искусственного интеллекта существует множество информационных технологий и систем, призванных помочь в деле управления обществом, производством, торговлей, кредитной и финансовой сферами и т.д. Наиболее известными являются: экспертные системы, советующие системы, системы поддержки принятия решений, системы исполнения решений, интеллектуальные системы. Общей чертой перечисленных систем и технологий является использование в них знаний человека-эксперта. Применение таких систем дает наибольший эффект при решении задач, которые характеризуются слабой формализацией и большую, а иногда решающую роль играют знания и опыт высококвалифицированных специалистов (экспертов). Известные сегодня теоретические положения создания систем поддержки решений не позволяют разрабатывать инструментальные средства, которые могли бы комплексно поддерживать все этапы принятия решений и синтезировать формальные методы формирования решений со знаниями и интуицией менеджера.
Специфика задач в области принятия решения состоит в том, что не существует универсальных средств решения, и поэтому для каждой задачи фактически приходится создавать свою систему поддержки принятия решений, являющуюся реализацией конкретного метода или группы методов. Как результат, в большинстве случаев системы поддержки принятия решений создаются как системы "под ключ", исключая их дальнейшее развитие без участия разработчиков.
Исходя из сказанного, актуальной является проблема разработки аппарата и технологии, которые позволили бы автоматизировать процесс создания систем поддержки принятия решений и моделей принятия решений. Этот аппарат помимо функций создания должен также обеспечивать и решение задачи, возможность его исследования, то есть являться технологией создания и использования методов принятия решений, систем поддержки принятия решений настраиваемых на задачу.
В связи с этим возникает необходимость разработки инструментальных средств создания прикладных систем поддержки принятия решений, формализованного аппарата синтеза программного обеспечения систем поддержки принятия решений, ориентированных на решение того или иного класса задач и оптимальных в смысле заданных технико-экономических требований.
В настоящее время в области инженерии знаний, целью которой является исследование и разработка прикладных программных систем, основанных на знаниях и моделирующих работу экспертов в трудно формализуемых предметных областях, существует множество методологий и инструментальных средств, ориентированных, в первую очередь, на повторное использование методов решения задач, где под повторным использованием методов по нимается использование ранее разработанных методов при создании новых систем, основанных на знаниях.
Известными примерами таких методологий являются Task Structures, Role-Limiting Methods, Methodoask и Components of Expertise. Ma основе этих методологий разработаны такие инструментальные средства, как CommonKADS, PROTEGE-II, Spark/Burn/Firefighter, MIKE и другие. Характерной особенностью этих инструментальных средств является наличие библиотеки различных методов решения задач. Практика разработки таких библиотек основана на повторном использовании так называемых "парадигм" решения задач, например, таких, как Heuristic Classification и Propose-and-Revise. Эти методы представляют собой описание общей схемы решения задачи на некотором неформальном языке с использованием предметно независимой терминологии.
В процессе разработки системы, основанной на знаниях, эксперту предметной области на основе общей методологии предстоит определить соответствие между терминами, в которых описан метод, и терминами предметной области, для которой создается система. Использование библиотек методов позволяет сделать из инженерии знаний обычную инженерную дисциплину.
Таким образом, актуальность темы заключается в необходимости разработки научно-обоснованных и практически значимых методов синтеза программных средств автоматизированных систем (систем поддержки принятия решений), позволяющих повысить эффективность процесса автоматизированного проектирования.
Работа выполнена в соответствии с межвузовской комплексной научно-технической программой 12.Ї1 «Перспективные информационные технологии в высшей школе» в рамках одного из основных направлений Воронеж ского государственного технического университета "Проблемно - ориентированные системы управления". Цель работы и задачи исследования. Разработка методики, моделей и алгоритмов синтеза программного обеспечения систем поддержки принятия решений, реализующих принцип повторного использования методов и многокритериального выбора сгенерированных вариантов систем поддержки принятия решений.
Для достижения указанной цели в работе решались следующие основные задачи: произвести анализ прикладной области с целью формирования набора типовых методов принятия решений, пригодных для формирования базы знаний методов;
сформировать описание способа решения задачи автоматизированного проектирования систем поддержки принятия решений в виде формальной спецификации задачи;
разработать технологию формирования программной системы систем поддержки принятия решений из типовых, повторно используемых компо- 4 нентов (методов принятия решений);
сформировать многокритериальную оптимизационную модель разрабатываемых систем поддержки принятия решений на основе типового набора методов принятия решений в соответствии с исходной постановкой задачи;
разработать вероятностно - детерминированный алгоритм поиска оптимального варианта систем поддержки принятия решений на базе метода многоальтернативной оптимизации;
разработать программные средства базы знаний методов решения задач принятия решений, многоальтернативной оптимизации для использования в задачах автоматизированного синтеза программных средств систем под держки принятия решений, рационального выбора вариантов реализаций систем поддержки принятия решений.
Методы исследования основываются на теории сложных систем,, теории множеств, теории принятия решений, теории вероятностей, теории исследования операций, в частности, аппарате дискретной стохастической и многоальтернативной оптимизации. При разработке программных средств применялись методы объектно-ориентированного программирования и разработки интеллектуальных систем.
Научная новизна. В работе получены следующие результаты, характеризующиеся научной новизной:
методика автоматизированного проектирования систем поддержки принятия решений, отличающаяся выделением ряда типовых задач и определения механизма решения задачи путем формального разбиения ее на подзадачи и покрытия ее типовыми методами принятия решений;
база знаний методов принятия решений, предназначенная для хранения этих методов в форме, удобной для автоматизированной разработки прикладных систем поддержки принятия решений, отличающаяся возможностью повторного использования методов решения задач;
комбинаторная модель рационального выбора проектируемой на основе набора компонентов прикладной системы поддержки принятия решений с учетом характеристик компонентов и ограничений, накладываемых на «совместимость» компонентов, отличающаяся использованием метрик программного обеспечения в качестве критериев оптимизации;
модели задач многокритериальной оптимизации, ориентированная на поиск оптимальных алгоритмов с учетом их модульной структуры, а также механизмов ведения памяти и режимов работы системы, отличающиеся воз можностью использования вероятностного алгоритма псевдобулевой оптимизации;
метод и процедуры многоальтернативной оптимизации, предусматривающие в качестве инвариантной части вероятностный алгоритм дискретной оптимизации псевдобулевой функции векторного аргумента, к которому предъявляется требования булевости, отличающийся возможностью выполнения условий локального улучшения с учетом эквивалентного преобразования ее из матричной формы в векторную.
Практическая ценность и реализация результатов работы. В результате проведенного исследования разработаны структура, математическое, информационное и программное обеспечение подсистемы автоматизированного проектирования прикладных систем поддержки принятия решений, обеспечивающие создание и быстрое прототипирование экспертных систем поддержки принятия решений в различных предметных областях. Применение предложенных методов и процедур позволяет сократить сроки на проведение разработки, оценку и внедрение таких систем как в виде самостоятельных программных средств, так и в виде модулей сложных информационно-управляющих систем.
Использованный в процессе разработки программного продукта принцип повторного использования методов позволил создать универсальные инвариантные программные системы поддержки принятия решений с возможностью их разнообразной конфигурации и широким спектром приложения в различных предметных областях.
В рамках предложенной методики автоматизированного проектирования программного обеспечения систем поддержки принятия решений, разработана эффективная подсистема повторного использования методов решения задач принятия решений, применение которой позволило повысить произво дительность труда проектировщиков, обеспечить приемлемый уровень использования экономических ресурсов, получить программное обеспечение % высокого качества.
Реализация и внедрение результатов работы. Результаты работы внедрены и используются в ОАО "Видеофон" (г. Воронеж). Научные результаты используются в учебном процессе Воронежского государственного технического университета по специальности: 200800- «Проектирование и технология радиоэлектронных средств». Получен годовой экономический эффект в сумме более 134 тыс. руб.
Апробация работы. Научные результаты и положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Научно-технических конференциях " Проблемы обеспечения надежности и качества приборов, устройств и систем" (Воронеж 2000-2001 гг.); Трудах всероссийской конференции "Интеллектуализация управления в социальных и экономических системах" (Воронеж, 2001-2003 гг.); Международной научно-технической конференции "Системные проблемы качества, й математического моделирования и информационных технологий" (Москва Воронеж-Сочи 2001 г.); ежегодных научных конференциях профессорско-преподавательского состава Воронежского государственного технического университета.
Публикации. По теме диссертационной работы опубликовано 9 печатных работ.
В работах, опубликованных в соавторстве и приведенных в конце авто- % реферата, лично соискателю принадлежит: в [2] постановка задачи, в [3] ком бинаторная модель проектирования систем поддержки принятия решений на основе набора компонентов, в [8] процедуры многоцелевой оптимизации, ориентированные на интеллектуальную поддержку процессов принятия ре- # шений и эффективное сочетание априорной и текущей информации об объ ектах проектирования.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 112 наименований и приложения. Основной объем работы составляют 142 страниц текста, 17 рисунков и 6 таблиц.
Во введении обоснована актуальность работы, дана ее краткая харак теристика, показаны основные пути решения сформулированных задач.
В первой главе диссертации проводится обзор и анализ методов и инструментальных сред, используемых в системах поддержки принятия решений, рассматривается технология проектирования и разработки промышленных экспертных систем, изучаются методы решения задач и их повторное использование в системах поддержки принятия решений, ставится цель и за- . дачи исследования.
Показано, что в области инженерии знаний, целью которой является исследование и разработка прикладных программных систем, основанных на знаниях и моделирующих работу экспертов в трудно формализуемых предметных областях, все еще остаются актуальными проблемы повторного использования существующих методов решения задач. Основная причина этого заключена в трудности формального описания задач, решаемых в инженерии знаний, что, несомненно, является следствием сложности рассматриваемых предметных областей. Отмечается, что создание технологии, поддерживаю щей процесс разработки прикладных систем поддержки принятия решений с использованием библиотеки формальных методов решения задач, пригодных для повторного использования в различных предметных областях, позволило бы из области инженерии знаний (которая своими методами сегодня напоминает скорее область искусства) сделать обычную инженерную дисциплину.
Вторая глава посвящена разработке методики автоматизированного проектирования прикладных систем поддержки принятия решений, в которой выделяется ряд типовых задач и определяется механизм решения задачи путем формального разбиения ее на подзадачи и покрытия ее типовыми методами принятия решений.
В основу предлагаемой технологии положен тот факт, что в принятии решений, как и в любой другой области, можно выделить ряд действий, которые семантически и с формальной точки зрения совпадают. Соответственно, для реализации такого рода действий могут быть использованы типовые элементы как некоторые структуры, формируемые специальным образом.
Вводится определение типового элемента "ЗАДАЧА" , использование которого в построении отношения ЗАДАЧА-МОДЕЛЬ-МЕТОД позволяет получить гибкий аппарат решения задачи принятия решения:
При изменении модели на верхнем уровне (для исходной задачи) она автоматически меняется и для подзадач;
При решении каждой из подзадач возможно варьировать методами в пределах отношений ЗАДАЧА-МЕТОД, ЗАДАЧА-МОДЕЛЬ, МЕТОД-МОДЕЛЬ;
Для подзадач метод может также строится на основе типового элемента «ЗАДАЧА». Следовательно, можно строить иерархические методы-модели принятия решений.
На основе проведенной классификации методов принятия решений формируется набор типовых задач многокритериальной оптимизации. Ука занный набор типовых задач в формате «Дано, Требуется определить» ориентирован на представление в базе знаний методов решения задач.
Формируется база знаний методов принятия решений, предназначенная для хранения этих методов в форме, удобной для автоматизированной разработки прикладных систем поддержки принятия решений и допускающая возможность повторного использования методов решения задач.
База знаний методов решения задач составляет ядро системы автоматизированного проектирования прикладных систем поддержки принятия решений.
Особенность предложенной методики автоматизированного проектирования прикладных систем поддержки принятия решений заключается в том, что она предназначена для класса задач, в которых основой для принятия решения является информация числового характера, так как эти задачи наиболее распространены в инженерной практике и во многих случаях нечисловую задачу можно свести к числовой.
В третьей главе диссертационной работы рассматриваются вопросы формализации принципов модульного программирования в виде программного комплекса многоальтернативной оптимизации и практической реализации его на примере проектирования прикладных систем поддержки принятия решений.
С целью формирования оптимизационной модели выявляется взаимно однозначное соответствие между методами принятия решений прикладной системы поддержки принятия решений и функциональными проектирующими элементами. Обобщенную математическую формулировку рассматриваемой задачи предлагается записывать в виде многокритериальной задачи дискретного программирования с ограничениями.
Решение задачи предлагается осуществить, используя вероятностно -детерминированные алгоритмы, что позволяет работать с задачами высокой размерности в ситуациях минимальной априорной информированности схемы и алгоритмические процедуры.
В четвертой главе описывается реализация и применение подсистемы автоматизированного проектирования прикладных систем поддержки принятия решений, приводится структура и функциональное описание подсистемы автоматизированного проектирования прикладных систем поддержки принятия решений, описываются инструментальные средства, поддерживающие процесс создания программных средств систем поддержки принятия решений.
Рассматривается реализация повторного использования методов поддержки принятия решений в подсистеме автоматизированного проектирования систем поддержки принятия решений. В качестве библиотеки методов решения задач используется стандартный репозиторий объектов универсальной среде разработки Borland C++ Builder. Репозиторий объектов предназначен для хранения программного кода, который может быть использован повторно в различных проектах, разрабатываемых в указанной среде.
Созданный технологический комплекс, ориентированный на генерацию эффективных прикладных систем поддержки принятия решений, позволил разработать на его основе с максимальным использованием уже разработанных компонентов специализированные системы поддержки принятия решений "Альтернатива" и "Конкурс", учитывающие специфику постановки, получения и использования результатов решения конкретных задач выбора.
В заключении приведены основные результаты диссертационной работы.
В приложениях приведены модели и метрики оценки качества программного обеспечения, перечень компонентов для создания прикладных систем поддержки принятия решений и акты внедрения подсистемы автоматизированного проектирования прикладных систем поддержки принятия решений.
Технология проектирования и разработки промышленных экспертных систем
Разработка программных комплексов ЭС и СППР как за рубежом, так и в нашей стране находится на уровне скорее искусства, чем науки. Это связано с тем, что долгое время системы искусственного интеллекта внедрялись в основном во время фазы проектирования, а чаще всего разрабатывалось несколько прототипных версий программ, и на их основе уже создавался конечный продукт. Такой подход действует хорошо в исследовательских условиях, однако в коммерческих условиях он является слишком дорогим» чтобы оправдать затраты на разработку-Процесс разработки промышленной экспертной системы, опираясь на традиционные технологии [5, 60, 66], практически для любой предметной области можно разделить на шесть более или менее независимых этапов (рис. 1-2),
Последовательность этапов дана только с целью получения общего представления о процессе создания идеального проекта. Конечно, последовательность эта не вполне фиксированная. В действительности каждый последующий этап разработки может принести новые идеи, которые могут повлиять на предыдущие решения и даже привести к их переработке. Именно поэтому многие специалисты по информатике весьма критично относятся к методологии экспертных систем. Они считают, что расходы на разработку таких систем очень большие, время разработки слишком велико, а полученные в результате программы накладывают тяжелое бремя на вычислительные ресурсы, В целом за разработку экспертных систем целесообразно браться организации, где накоплен опыт по автоматизации рутинных процедур обработки информации, таких как: формирование корпоративных информационных систем; организация сложных расчетов; работа с компьютерной графикой; обработка текстов и автоматизированный документооборот. Решение таких задач, во-первых, подготавливает высококвалифицированных специалистов по информатике, необходимых для создания интеллектуальных систем, во-вторых, позволяет отделить от экспертных систем неэкспертные задачи. Выбор подходящей проблемы. Этот этап определяет деятельность, предшествующую решению начать разрабатывать конкретную ЭС, Он включает [60]: определение проблемной области и задачи; нахождение эксперта, желающего сотрудничать при решении про блемы, и назначение коллектива разработчиков; определение предварительного подхода к решению проблемы; анализ расходов и прибылей от разработки; подготовку подробного плана разработки. Правильный выбор проблемы представляет самую критическую часть разработки в целом. Если выбрать неподходящую проблему, можно очень быстро увязнуть в «болоте» проектирования задач, которые никто не знает, как решать. Неподходящая проблема может также привести к созданию экспертной системы, которая стоит намного больше, чем экономит. Дело будет обстоять еще хуже, если разработать систему, которая работает, но неприемлема для пользователей. Даже если разработка выполняется самой организацией для собственных целей, эта фаза является подходящим моментом для получения рекомендаций извне, чтобы гарантировать удачно выбранный и осуществимый с технической точки зрения первоначальный проект При выборе области применения следует учитывать, что если знание, необходимое для решения задач, постоянное, четко формулируемое и связано с вычислительной обработкой, то обычные алгоритмические программы, по всей вероятности, будут самым целесообразным способом решения проблем в этой области.
Экспертная система ни в коем случае не устранит потребность в реляционных базах данных, статистическом программном обеспечении, электронных таблицах и системах текстовой обработки. Но если результативность задачи зависит от знания, которое является субъективным, изменяющимся, символьным или вытекающим частично из соображений здравого смысла, тогда область может обоснованно выступать претендентом на экспертную систему. Обычно экспертные системы разрабатываются путем получения специфических знаний от эксперта и ввода их в систему. Некоторые системы могут содержать стратегии одного индивида. Следовательно, найти подходящего эксперта - это ключевой шаг в создании экспертных систем, В процессе разработки и последующего расширения системы инженер по знаниям и эксперт обычно работают вместе- Инженер по знаниям помогает эксперту структурировать знания, определять и формализовать понятия и правила, необходимые для решения проблемы.
Во время первоначальных бесед они должны решить, будет ли их сотрудничество успешным. Это немаловажно, поскольку обе стороны будут работать совместно, по меньшей мере в течение одного года- Кроме них в коллектив разработчиков целесообразно включить потенциальных пользователей и профессиональных программистов. Подробно функции каждого члена коллектива описаны в следующем параграфе Предварительный подход к программной реализации задачи определяется, исходя из характеристик задачи и ресурсов, выделенных на ее решение. Инженер по знаниям выдвигает обычно несколько вариантов, связанных с использованием имеющихся на рынке программных средств. Окончательный выбор возможен лишь на этапе разработки прототипа.
После того как задача определена, необходимо подсчитать расходы и прибыль от разработки экспертной системы, В расходы включаются затраты на оплату труда коллектива разработчиков, В дополнительные расходы будет включена стоимость приобретаемого программного инструментария, с помощью которого будет разработана экспертная система.
Прибыль может быть получена за счет снижения цены продукции, повышения производительности труда, расширения номенклатуры продукции или услуг или даже разработки новых видов продукции или услуг в области, в которой будет использоваться ЭС. Соответствующие расходы и прибыль от системы определяются относительно времени, в течение которого возвращаются средства, вложенные в разработку. На современном этапе большая часть фирм, развивающих крупные экспертные системы, предпочли разрабатывать дорогостоящие проекты, приносящие значительную прибыль.
Формирование базы знаний методов принятия решений на основе их классификации
При принятии управленческих решений лицо, принимающее решение должно не только полагаться на свой опыт и интуицию, но и обращаться к хорошо разработанным в настоящее время математическим моделям поддержки принятия решений, позволяющих корректно выбирать наиболее лучшие альтернативы из имеющихся. От того, насколько трамотно, квалифицированно осуществляется поддержка принятия управленческих решений, зависит успешность функционирования системы в целом [1, 33, 34, 54, 55, 84].
Исследования показывают, что лица, принимающие решения без дополнительной аналитической поддержки, используют упрощенные, а иногда и противоречивые решающие правила [18, 52]. Поддержка принятия решения требуется во всех без исключения областях прикладной деятельности человека, что связано с увеличивающимся объемом информации, необходимостью учитывать большое количество противоречивых факторов, объективных и субъективных составляющих при принятии решений.
Приведем классификацию моделей и методов принятия решений. Модель задачи принятия решений в [19] представляется в виде:
M= t,XR,A,F,G,D , где t - постановка задачи (например, выбрать одну наилучшую в некотором смысле альтернативу или упорядочить все множество альтернатив); X - множество допустимых альтернатив; R - множество критериев оценки степени достижения поставленных целей; А - множество шкал измерения по критериям (шкалы наименований, порядковые, интервальные, отношений); F - отображение множества допустимых альтернатив в множество критериальных оценок; G - система предпочтений решающего элемента; D - решающее правило, отражающее систему предпочтений. Классификация моделей задач принятия решений в [19] проводится в соответствии со следующими признаками: 1) по виду отображения F - детерминированное, вероятностное или неопределенное, можно выделить соответственно: задачи принятия решений в условиях определенности, задачи принятия решений в условиях риска, задачи принятия решений в условиях неопределенности; 2) по мощности множества R - одноэлементное множество или состоящее из нескольких критериев, выделяются соответственно: задачи принятия решений со скалярным критерием, задачи принятия решений с векторным критерием (многокритериальные задачи); 3) по типу системы G - отражает предпочтения одного лица или коллектива в целом, выделяются задачи индивидуального принятия решений, задачи группового принятия решений. В [29] под моделью выбора понимается пара (X, R)r состоящая из множества альтернативХи бинарного отношения R на нем, В [17] при определении модели принятия решений предполагается, что рассматривается некоторое множество исходных структур предпочтений и исследуется определенная задачи принятия решений, процесс решения которой понимается как оптимальный выбор метода обработки исходной структуры из некоторого базового класса методов. При этом можно считать, что на множестве исходных структур задана модель решения поставленной задачи принятия решений, если указан некий принцип или правило, согласно которому произвольному отношению ставится в соответствие некоторый набор методов. Конкретные модели ориентированы на соответствие тех или иных методов принятия решений определенным базовым структурам.
В [16, 19] приведена классификация методов принятия решений по таким признакам, как содержание экспертной информации, тип получаемой информации, на основе которой можно определить группу методов принятия решений в условиях неопределенности (рис. 2.3),
В диссертационной работе рассматривается возможность анализа различных вопросов управления методами принятия решений в условиях неопределенности. Это связано с тем, что информация, описывающая деятельность крупного производственного предприятия, является заведомо неполной и неточной, что ставит под сомнение целесообразность использования для оптимального выбора точных методов. Очень часто, и особенно при исследовании экономических, социальных и других систем, в функционировании которых участвует человек, значительное количество информации может быть получено от людей, имеющих опыт работы с данной системой и знающих ее особенности, от людей, имеющих представление о целях функционирования системы. Эта информация носит субъективный характер, и ее представление в естественном языке содержит неопределенности, которые не имеют аналогов в языке традиционной математики- В этом случае лучше рассматривать задачи оптимального управления с позиций методов, учитывающих неопределенность описания модели исследуемого объекта.
При этом под неопределенностью будем понимать явления, не поддающиеся анализу и измерению со сколь угодно большой точностью [53, 59].
Рассмотрим модели и алгоритмы некоторых методов принятия решений, основанные на парном сравнении альтернатив и предоставляющие ЛПР их линейное упорядочивание [17, 58]. Используемые в практике модели линейного упорядочивания традиционно разделяются на две большие группы, различающиеся своим подходом к решению задачи упорядочивания объектов.
Разработка оптимальной компонентной структуры прикладной СППР в подсистеме автоматизированного проектирования
К мерам сложности, учитывающим вложенность управляющих конструкций, относят тестирующую меру М и меру Харрисона-Мейджела, учитывающих уровень вложенности и протяженности программного обеспечения, меру Пивоварского - цикломатическую сложность и глубину вложенности, и меру Мак-Клура - сложность схемы разбиения программного обеспечения на модули с учетом вложенности модулей и их внутренней сложности.
Функциональная мера сложности Харрисона-Мейджела предусматривает приписывание каждой вершине графа своей собственной сложности (первичной) и разбиение графа на сферы влияния предикатных вершин. Сложность сферы называют приведенной и слагают ее из первичных сложностей вершин, входящих в сферу ее влияния, плюс первичную сложность самой предикатной вершины. Первичные сложности вычисляются всеми возможными способами- Отсюда функциональная мера сложности программного обеспечения есть сумма приведенных сложностей всех вершин управляющего графа-Мера Пивоварского ставит целью учесть в оценке сложности программного обеспечения различия не только между последовательными и вложенными управляющими конструкциями, но и между структурированными и неструктурированными программами. Она выражается отношением N(G) = n (G)+S Р,, где n (G) - модифицированная цикломатическая сложность, вычисленная так же, как и V(G)S но с одним отличием: оператор CASE с п- выходами рассматривается как один логический оператор, а не как п-1 операторов. Pj - глубина вложенности і-ой предикатной вершины.
Для подсчета глубины вложенности предикатных вершин используется число сфер влияния. Под глубиной вложенности понимается число всех сфер влияния предикатов, которые либо полностью содержаться в сфере рассматриваемой вершины, либо пересекаются с ней- Глубина вложенности увеличивается за счет вложенности не самих предикатов, а сфер влияния. Сравнительный анализ цикломатических и функциональных мер с обсуждаемой для десятка различных управляющих графов программы показывает что при нечувствительности прочих мер этого класса, мера Пивоварского возрастает при переходе от последовательных программ к вложенным и далее к неструктурированным.
Мера Мак-Юіура предназначена для управления сложностью структурированных программ в процессе проектирования. Она применяется к иерархическим схемам разбиения программ на модули, что позволяет выбрать схему разбиения с меньшей сложностью задолго до написания программы. Метрикой выступает зависимость сложности программы от числа возможных путей исполнения, числа управляющих конструкций и числа переменных (от которых зависит выбор пути). Методика расчета сложности по Мак-Клуру четко ориентирована на хорошо структурированные программы. Тестирующей мерой М называется мера сложности, удовлетворяющая следующим условиям:
Мера возрастает с глубиной вложенности и учитывает протяженность программы, 1С тестирующей мере близко примыкает мера на основе регулярных вложений. Идея этой меры сложности программ состоит в подсчете суммарного числа символов (операндов, операторов, скобок) в регулярном выражении с минимально необходимым числом скобок, описывающим управляющий граф программы. Все меры этой группы чувствительны к вложенности управляющих конструкций и к протяженности программы. Однако возрастает уровень трудоемкости вычислений.
Рассмотрим меры сложности, учитывающие характер разветвлений. В основе узловой меры Вудворда, Хедли лежит идея подсчета топологических характеристик потока управления. При этом под узловой сложностью понимается число узлов передач управления- Данная мера отслеживает сложность линеаризации программы и чувствительна к структуризации (сложность уменьшается). Она применима для сравнения эквивалентных программ, предпочтительнее меры Холстеда, но по общности уступает мере Мак-Кейба,
Топологическая мера Чепа выражает сложность программы числа пересечений границ между областями, образуемыми блок - схемой программы. Этот подход применим только к структурированным программам, допускающим лишь последовательное соединение управляющих конструкций. Для неструктурированных программ мера Чена существенно зависит от условных и безусловных переходов- В этом случае можно указать верхнюю и нижнюю границы меры. Верхняя - есть m-И, где т - число логических операторов при их гнездовой вложенности- Нижняя - равна 2, Когда управляющий граф программы имеет только одну компоненту связности, мера Чена совпадает с цикломатической мерой Мак-Кейба.
Метрики Джилба оценивают сложность графоориентированных модулей программ отношением числа переходов по условию к общему числу исполняемых операторов. Хорошо зарекомендовала себя метрика, относящаяся число межмодульных связей к общему числу модулей. Названные метрики использовались для оценки сложности эквивалентных схем программ, в особенности схем Янова. Используются также меры сложности, учитывающие историю вычислений, характер взаимодействия модулей и комплексные меры. Совокупность цикломатических мер пригодна для оценивания сложности первичных формализованных спецификаций, задающих в совокупности исходные данные, цели и условия построения искомого программного обеспечения.
Таким образом, оценка первичной программы или сравнение нескольких альтернативных ее вариантов позволит изначально гармонизировать процесс разработки программного обеспечения и от стартовой точки контролировать и управлять его текущей результирующей сложностью.
Реализация повторного использования методов поддержки принятия решений в подсистеме автоматизированного проектирования СППР
Сборка прикладной Сі 11 IP, Инструментальная подсистема должна включать в себя средства, позволяющие автоматизировать процесс подключения новых функциональных модулей (ФМ), генерировать варианты для решения отдельных классов задач, собирать статистическую информацию о решенных задачах.
Вызов всех подпрограмм как системных, так и функциональных осуществляется по единому алгоритму. Описание модуля позволяет автоматически сгенерировать список параметров модуля, после чего ему передается управление- Необходимые для модуля параметры выбираются из вектора параметров по их именам, поэтому подключение нового ФМ происходит путем добавления нового описания задачи во множество описаний задач, описания новых методов в архив пакета и самого модуля в библиотеку функциональных модулей. Как правило, это не влечет расширения библиотеки системных модулей, поскольку используются универсальные механизмы управления параллельными процессами и манипулирования данными, а транслятор может настраиваться на входной язык. Кроме того, диалоговая подсистема поддерживает команды, позволяющие автоматизировать этот процесс.
Генерация вариантов решения задач происходит следующим образом. На множестве системных и функциональных модулей задается отношение предшествования, которое описывается ориентированным графом межмодульных связей- Модуль aj находится в отношении предшествования с модулем bJ9 если перед вызовом модуля bj должен быть вызван модуль аг По списку имен описаний задач из множества описаний задач и множества описаний методов осуществляется выборка нужных элементов. Из компонент программной оболочки выбираются необходимые подмножества системных и функциональных модулей и строится подграф межмодульных связей. Проблема передачи параметров между системными модулями решается за счет общего вектора параметров. Следует отметить, что системная и функциональная части пакета являются открытыми для расширения. Структура сгенерированной прикладной СППР приведена на рис, 4.2.
Создание новых методов может достигаться путем задания последовательности выполнения функциональных модулей вместе с временными или оценочными критериями завершения работы. Последовательность функциональных модулей удобно задавать с помощью ориентированного взвешенного графа, где в качестве узлов выступают методы решения задачи, а в качестве весов - условия их применимости. Связь по данным реализуется за счет использования общей базы данных.
Сбор статистической информации о решенных задачах позволит разработчикам анализировать эффективность используемых методов, частоту их применения, а при необходимости формулировать задание на разработку новых алгоритмов.
Каждая из описанных частей инструментальной подсистемы должна иметь свои инструментальные средства, которые бы позволяли ускорять разработку СППР. Поскольку вышеупомянутые компоненты программной оболочки носят универсальный характер (вне зависимости от решаемой задачи), то они образуют технологическую среду, в которой можно создавать новые прикладные СППР для указанного класса задач.
Разработка прикладной СППР проводится в соответствии с методикой, изложенной в разделе 2, и состоящей из четырех этапов (см. рис. 2,5): построения модели предметной области, постановки задачи на модели, разработки метода решения и генерации программы СППР.
На первом этапе при помощи соответствующего редактора строится модель предметной области; определяются имена и свойства шкал, сортов, неизвестных и параметров, множество логических соотношений, определяющих свойства неизвестных и параметров, и значение параметров модели.
Модель предметной области, возможно, уже была разработана для решения других задач и хранится в архиве проектов, поэтому на данном этапе возможно повторное использование моделей предметных областей.
На втором этапе формально в терминах модели предметной области описывается задача: указываются имена неизвестных, значения которых является исходными данными задачи, и имена неизвестных, значения которых являются результатом задачи. Постановка задачи выполняется при помощи соответствующего редактора и хранится в архиве проектов. На этапе разработки метода решения, если это необходимо, происходит разбиение задачи на подзадачи и определяется порядок их выполнения (управление). Например, в тех случаях, когда в постановке задачи указаны в качестве результата значения нескольких неизвестных, то задача может быть разбита на подзадачи, каждая из которой находит значение только одной неизвестной. Процесс выделения подзадач в общем случае не может быть автоматизирован и полностью зависит от умения разработчика выделять подзадачи и определять эффективное управление над ними. Так в предыдущем примере можно принять произвольную последовательность решения подзадач, но при этом не исключена ситуация, что при решении разных подзадач будут выполняться одни и те же действия. После выделения подзадач осуществляется поиск методов решения каждой из них.
