Разработка теории и основных принципов принятия решений в сапр на основе методов, инспирированных природными системами

Вид материала

Автореферат диссертации

Содержание Общая характеристика работы Цель диссертационной работы. Методы исследования Научная новизна работы Практическая ценность результатов Реализация результатов работы. Апробация работы. Структура и объем диссертационной работы. Краткое содержание работы В первом разделе Во втором разделе В четвертом разделе. Основные результаты диссертации опубликованы в следующих работах

Подобный материал:

• Программа профилирующей дисциплины "теория игр и исследование операций" Содержание, 69.55kb.
• 05. 13. 12 Системы автоматизации проектирования (машиностроение), 22.99kb.
• Технологический Институт Южного Федерального Университета e-mail: lbk@tsure ru Введение, 145.03kb.
• Рейтинг-план освоения дисциплины «Теория принятия решений» Недели, 83.54kb.
• Разработка математических моделей и алгоритмов принятия решений по кредитованию предприятий, 286.47kb.
• Рабочая программа по курсу «теория принятия решения», 87.49kb.
• Методы обучения систем поддержки принятия решений, 64.31kb.
• Анализ принятия управленческих решений, 54.28kb.
• Вдокладе рассматриваются проблемы и перспективы многокритериальных методов принятия, 12.62kb.
• Направление 080100 экономика профили : «Экономика предприятий и организаций», "Бухгалтерский, 35.44kb.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ


ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ


«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»


На правах рукописи




СОРОКОЛЕТОВ ПАВЕЛ ВАЛЕРЬЕВИЧ


РАЗРАБОТКА ТЕОРИИ И ОСНОВНЫХ ПРИНЦИПОВ ПРИНЯТИЯ РЕШЕНИЙ В САПР НА ОСНОВЕ МЕТОДОВ, ИНСПИРИРОВАННЫХ ПРИРОДНЫМИ СИСТЕМАМИ


Специальность: 05.13.12 – Cистемы автоматизации проектирования (вычислительная техника и информатика);

Специальность: 05.13.17 – Теоретические основы информатики


Автореферат

диссертации на соискание ученой степени доктора технических наук


Научный консультант:

д-р. техн. наук, профессор Курейчик В.В.


Работа выполнена в Технологическом институте Южного федерального университета в г. Таганроге


Научный консультант: доктор технических наук,

профессор Курейчик В.В.


Официальные оппоненты: доктор технических наук, профессор

Васильев В. И. (МГУП, г.Москва)

доктор технических наук, доцент

Рыжов А. П. (МГУ, г.Москва)

доктор технических наук, профессор

Ковалев С. М. (РГУПС, г. Ростов-на-Дону)


Ведущая организация: ГУ РосНИИ информационных технологий и автоматизации проектирования г. Москва


Защита диссертации состоится «_25_» ноября 2010г. в 14²⁰ на заседании диссертационного совета Д 212.208.22 при Южном федеральном университете по адресу: 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406.


С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.


Автореферат разослан «14» октября 2010г.


Ученый секретарь

диссертационного совета Д 212.208.22,

доктор технических наук, профессор Целых А.Н.

Общая характеристика работы

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

Основополагающими работами, оказавшими влияние на исследования автора, являются труды О.И.Ларичева, Г.С.Поспелова, Д.А.Поспелова, А.Л.Стемпковского, В.Н. Вагина, И.П. Норенкова, А.А. Колесников, Д.И.Батищева, Г.Г.Казенова, В.Н.Гридина, В.П.Корячко, А.И. Петренко, Б.В. Баталова, Ю.Х. Вермишева, Л.С.Берштейна, С.В.Емельянова, А.П.Еремеева, Н.Н.Моисеева, Г.С.Осипова, Э.В.Попова, Л.А.Растригина, Э.А.Трахтенгерца, Л.Заде, М.Месаровича, Д.Фогеля, А.Н. Тихонова, Р.Л. Кини, Х. Райфа, О. Уотермена., Б. Приса, Н.Шервани, Д.Гольдберга, Д.Холланда, Л.Девиса и многих других.

Разработка гибридных человеко-машинных систем поддержки принятия решений (СППР) позволит проводить этапы анализа, синтеза и моделирования альтернативных решений с учетом опыта, знаний и предпочтений разработчиков, конструкторов и технологов. Тогда для эффективного принятия решений в САПР необходимо каждый раз определять сходимость процесса к искомому множеству решений. При этом производится перебор по всему множеству решений (родители), в результате чего возникают новые альтернативные решения - потомки. При этом технология моделирования эволюции преобразуется в комплекс алгоритмов смены поколений. В этой связи становится необходимой интеграция природно-инспирированных и поисковых методов с целью модернизации СППР. Одним из таких подходов является использование методов моделирования эволюции, применение биоинспирированных, бионических, квантовых и генетических алгоритмов, эволюционных стратегий, адаптации и взаимодействия с внешней средой.

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

В этой связи разработка фундаментальной научной теории и принципов принятия эффективных решений в САПР имеет важное экономико-социальное значение и является в настоящее время актуальной и важной.

Цель диссертационной работы. Разработка фундаментальной теории и принципов принятия решений в САПР на основе методoв, инспирированных природными системами.

Указанная цель достигается решением следующих задач.

1. Построение новых и модифицированных математических моделей эволюционных и поисковых методов принятия решений.
   
2. Разработка новых технологий принятия решений на основе методoв, инспирированных природными системами.
   
3. Разработка динамических экспертных систем при принятии решений.
   
4. Исследование и разработка графовых и гиперграфовых моделей как стандартных блоков в САПР.
   
5. Разработка новой инструментальной среды системы поддержки принятия решений при проектировании.
   

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

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

1. Разработаны основные элементы фундаментальной теории поддержки принятия решений в САПР. Она порождает новую технологию ПР, эффективно сочетающую методы бионики и информатики.
   
2. Построена модифицированная интеллектуальная система поддержки принятия решений в САПР. Основное преимущество заключается в использовании интегрированной целевой функции, трехуровнего моделирования и взаимодействия с внешней средой. Это позволяет построить иерархическую систему вывода, действующую по принципу «матрешки».
   
3. Предложен единый комбинаторный подход к решению оптимизационных задач принятия решений на графовых моделях. Исследованы и обобщены методы принятия решений в задачах проектирования.
   
4. Построены новые архитектуры бионического и квантового поиска, ориентированные на решение задач проектирования.
   
5. Разработана методика бионического поиска в СППР на основе методов, инспирированных природными системами, позволяющая получать наборы квазиоптимальных решений.
   
6. Исследованы и обоснованы модели принятия решений на основе эволюционных теорий Дарвина, Ламарка, Фризе, Киммуры, Поппера, Дубинина, Шмальгаузена, Эйгена-Фишера и др.
   
7. Показана связь между механизмами принятия решений и генетическими алгоритмами. Это позволяет применить теорию эволюционного моделирования и генетических алгоритмов для построения эффективных систем поддержки принятия решений.
   
8. Разработаны новые алгоритмы принятия решений при проектировании на основе построенных эволюционных моделей. Это позволяет повысить скорость проектирования за счет распараллеливания процесса решения.
   

Практическая ценность результатов диссертационной работы определяется созданием программной среды и комплекса программных средств принятия решений, позволяющих использовать разработанные математические модели, стратегии, методы, принципы и алгоритмы, отвечающие стандартам проектирования. Разработана специальная программная среда для моделирования задач принятия решений. Комплексы программ реализованы на языке C++ под WINDOWS. Предлагаемые в диссертации программные средства поддержки принятия решений на основе методов, инспирированных природными системами, дают возможность представления задач реального пользователя и ЛПР в виде стандартных блоков и кластеров, что позволяет распараллеливать процесс решения. Широкий спектр экспериментальных исследований, проведенных автором, показал преимущество разработанной фундаментальной теории и принципов принятия решений в САПР на основе методов, инспирированных природными системами, по сравнению с классическими методами. Сравнение проводилось на стандартных тестовых задачах (бенчмарках), известных из литературы. Оно показало, что время решения разработанных алгоритмов позволяет получать наборы оптимальных или квазиоптимальных результатов. Улучшение работы предложенных архитектур генетического поиска по сравнению с известными методами составило по качеству от 15% до 40%, а по времени - от 10% до 25% в зависимости от вида оптимизационных задач проектирования. Время получения лучших результатов соответствует времени, которое требуют итерационные алгоритмы.

Реализация результатов работы. Теоретические и практические результаты, полученные в диссертационной работе, использовались в 7 научно исследовательских работах, выполненных в рамках грантов РФФИ, программ Минобразования, госбюджетной и хоздоговорной тематики. Материалы диссертации использованы в госбюджетных работах: «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска». В программе развития потенциала научной школы «Разработка бионических методов и принципов поиска оптимальных решений при проектировании». При выполнении грантов РФФИ «Разработка теории и принципов принятия решений при разбиении сложных математических объектов на части на основе моделирования эволюций и фрактальных множеств». «Разработка теории и принципов построения систем автоматизированного проектирования на основе эволюционной адаптации». «Разработка теории и принципов построения систем поддержки принятия решений на основе эволюционной адаптации, самообучения и самоорганизации». «Разработка теории и исследование эволюционных, синергетических и гомеостатических методов принятия решений».

Результаты работы используются в Институте проблем естественных монополий (г.Москва), ОАО «Российские космические системы» (г.Москва), ОАО «РусГидро» (г.Москва), ФГУП «ЦНИИМАШ» (г.Москва), в научных исследованиях Южного федерального университета (г. Ростов-на-Дону), Технологического института Южного федерального университета в г. Таганроге, что подтверждается соответствующими актами.

Результаты научных исследований внедрены в учебный процесс Южного федерального университета (г. Ростов-на-Дону), Технологического института Южного федерального университета в г. Таганроге, что подтверждено актами использования.

Результаты диссертационной работы обобщены в 12 изданных монографиях и 19 работах, опубликованных в изданиях, рекомендованных ВАК для диссертаций на соискание ученой степени доктора наук.

Апробация работы. Основные научные и практические результаты диссертационной работы докладывались, обсуждались и были одобрены на всероссийских научно-технических конференциях с участием зарубежных представителей и международных научно-технических конференциях "Новая информационная технология и проблемы управления" (г. Москва, 1990г.), «Интеллектуальные СППР» (г. Дивноморск 2002-2009гг.), «Интеллектуальные системы» (г. Дивноморск, 2003-2009гг.), III и IV «Интегрированные модели и мягкие вычисления в искусственном интеллекте (г.Коломна, 2005,2007,2009 г.г.) по информационным технологиям, проводимых на международных выставках (г. Шеньян 2006г., г. Харбин 2007г., КНР), и выставке СEBIT (г. Ганновер 2007г., Германия); на научных семинарах Артуа университета (г.Бетюн, Франция, 2006-2010г.г.) и Северо-Кавказкого Научного Центра Высшей Школы (г. Ростов-на-Дону, Таганрог, 2003- 2007г.г.).

Публикации. Основные результаты диссертационной работы отражены в 56 печатных работах, в том числе: 12 монографиях и учебных пособиях. Список основных работ по теме диссертации приведен по мере цитирования в списке использованной литературы в конце диссертации.

Структура и объем диссертационной работы. Диссертация состоит из введения, пяти разделов, заключения, изложенных на 349 страницах, 97 рисунков, расположенных на 49 страницах, 10 таблиц, списка литературы из 288 наименований и приложений. В приложение вынесены акты об использовании и внедрении результатов диссертационной работы.

Краткое содержание работы

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

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

Принятием решений считают множество альтернатив в условиях определенности, позволяющих получать однозначные, непротиворечивые, корректные решения на основе формализованных моделей анализируемых объектов, моделей управления и моделей внешней среды. К задачам поддержки принятия решений в новых информационных технологиях относятся все задачи, включая класс задач в условиях нечеткости и неопределенности, окончательное решение которых осуществляется на основе анализа полученных альтернатив. В этих случаях информацию преобразуют к виду, упрощающему и облегчающему принятие решений. Поэтому при невозможности получения решения задачи при заданных условиях автор предлагает использовать следующие принципы, положения и методы: «Бритвы Оккама» - упрощение условий решения задачи и сведение ее к извест­ной. «Разделяй и властвуй» - разбиение сложной задачи на отдельные подзадачи с возможностью последующей сборки. «Data mining» (DM) - использование интеллектуального анализа извлечения знаний. «Выживание сильнейших» - то есть выбор оптимальных решений в процессе моделирования эволюции.

Сформулируем постановку задачи исследований. Обозначим вектором  = {₁,…,_r} множество неконтролируемых параметров системы проектирования, которые, являясь случайными величинами, влияют на значения выходных параметров. Обозначим другим вектором  = (₁, ₂,…, _к) совокупность неконтролируемых параметров, которые, являясь расплывчатыми величинами, влияют также на значения выходных параметров. При этом _i = _i, z_i, где _i – функция принадлежности элемента z_i к множеству , _i=[0,1]. Тогда математическое описание системы примет вид:

Y = F (X, Z, , ). (1)

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

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

• задачи с полным математическим описанием исходных данных,
  условий, критериев и принципов оптимальности решений;
  
• задачи с неполным математическим описанием исходных данных,
  условий и качественным описанием критериев и принципов оптималь­ности;
  
• задачи с математическим описанием основных ресурсных исход­ных данных и качественным описанием условий, критериев и принци­пов оптимальности решений.
  

Под задачей принятия решений в условиях неопределенности понимается тройка {A,X,S}. Взаимодействие рассматриваемых элементов можно представить общей схемой:,т.е. состояние в сочетании с выбранной альтернативой определяет исход решения. Многие задачи СППР являются NP-полными и не поддаются формализации ввиду неопределенности и нечеткости задач проектирования, исходных данных, критериев, ограничений и граничных условий. Задачи ПР в САПР будем рассматривать в контексте поиска в пространстве состояний. Формально задача ПР запишется:

ПР=н, S_к, S_доп., ЦФ, ОГР, ГУ, φ_пр>,

где: U – универсум (множество всех состояний), S_н(S_к) – подмножество начальных (конечных) состояний, S_доп. – подмножество допустимых (U \S_доп. - недопустимых) состояний, S_н, S_к, S_доп.U, φ_пр: S_доп.→ S_доп. - множество правил преобразования, ЦФ- множество целевых функций, критериев оценки найденных решений, ОГР – ограничения, ГУ - граничные условия.

Решением задачи ПР можно считать подмножество альтернативных проектно-конструкторских решений, полученных на основе алгоритмов (последовательности применения правил). При этом результаты композиции и суперпозиции остаются в подмножестве допустимых состояний.

φ₁ ◦ φ₂ ◦ _… ◦φ_n ‏ S_к

φ₁ ▫ φ₂ ▫ _… ▫φ_n ‏ S_к ,

где ▫ и ◦ знаки композиции и суперпозиции соответственно. На рис.1. приведена обобщенная схема процесса принятия решений при проектировании.

В последнее время появились новые технологии решения задач поддержки принятия решений. К ним относятся бионические и биоинспирированные методы и алгоритмы.



Рис. 1. Обобщенная схема процесса принятия решений при проектировании

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

Приведем упрощенную схему взаимодействия САПР и СППР (рис.2). Она подробнее раскрывает блок проблемной области на рис.1. В хранилище данных находятся сведения о Гостах, стандартах, технологиях проектирования и ранее выполненных проектах, которые могут быть вызваны экспертной системой (ЭС) для принятия решений по реализации нового проекта. В базе данных (БД) основным является библиотека стандартных топологических решений. На вход препроцессора подаются все модели объекта проектирования и коммутационного рабочего поля. На вход СППР подаются все данные о ПР, приведенные выше. Постпроцессор анализирует полученные альтернативные решения. В блоке «?» определяется получение удовлетворительного решения. В случае его отсутствия происходит адаптация с внешней средой с учетом прогнозов и рисков проектирования. Далее процесс продолжается итерационно до получения оптимального решения.



Рис.2. Упрощенная схема взаимодействия САПР и СППР

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

Укрупненная структура ИСППР в САПР по аналогии с другими интеллектуальными системами состоит из четырех подсистем: адаптивной; интерактивной; обрабатывающей; подсистемы управления и блока «внешняя среда» (рис.3.). Первая подсистема состоит из нескольких уровней: микро, макро и мета - уровней. Между данными уровнями организована связь на основе полных и неполных, четких (нечетких) графов и гиперграфов. На каждом уровне строится интегрированная целевая функция, определяются свои граничные условия и ограничения. Далее строится обобщенная целевая функция для всей ИСППР. Целевые функции на микро-, макро- и метауровне будут частными целевыми функциями. Здесь реализуется эффект «матрешки» (англ. – nesting). В этом случае

ЦФ₁= α₁K₁ + α₂K₂ + … α_nK_n , (α₁ + α₂ + … α_n = 1), (2)

где ЦФ₁ – целевая функция на микроуровне, K₁, K₂, …, K_n – частные целевые функции, α₁, α₂, …, α_n – коэффициенты, определяющие степень принадлежности (важности) каждого критерия на этом уровне, n – число частных критериев. Соответственно, на макро- и метауровне запишем

ЦФ₂= β₁М₁ + β₂М₂ + … β_nМ_n , (β₁ + β₂ + … β_n = 1), (3)

ЦФ₃= γ₁R₁ + γ₂R₂ + … γ_nR_n , (γ₁ + γ₂ + … γ_n = 1), (4)

где ЦФ₂ (ЦФ₃) – целевая функция на макроуровне (метауровне), М₁, М₂, …, М_n (R₁, R₂, …, R_n) – частные целевые функции, β₁, β₂, …, β_n (γ_1, γ₂, … γ_n) – коэффициенты, определяющие степень принадлежности (важности) каждого критерия на макро- (мета) уровне, n – число частных критериев. Отметим, что для простоты взято общее число частных критериев (n) на всех уровнях. Тогда обобщенная (интегрированная) целевая функция ИСППР запишется:

ЦФ_инт= ₁ЦФ₁ + ₂ЦФ₂ + ₃ЦФ₃ , (₁+₂+₃ = 1), (5)

где ₁, ₂, ₃ – коэффициенты, определяющие степень принадлежности (важности) каждого критерия микро-, макро- и метауровня в интегрированном критерии (ЦФ_инт) для всей СППР.

Вторая подсистема анализирует входные описания на языке пользователя на основе имеющихся знаний и формирует внутреннее неполное и расплывчатое представление задачи. Здесь важно задание четкого множества исходных данных X = {x_1, x₂, …, x_l} и определение на нем нечеткого множества Ã = {< µ_1, x₁>, < µ_2, x₂>, … < µ_l, x_l>,}. При этом µ_i  Μ(X) функция принадлежности элемента x_i, а величина Μ(X) изменяется на интервале [0, 1].



Рис.3.Трехуровневая адаптивная система

Третья подсистема превращает неполное и расплывчатое описание задачи в полное и четкое и снова передает его интерактивной подсистеме. Далее процесс происходит итерационно до получения удовлетворительного решения. Четвертая подсистема управляет процессом решения, взаимодействуя с 1, 2 и 3 подсистемами.

Задачу поиска решений в пространстве состояний формулируется следующим образом. Пусть исходная задача описывается тройкой (S, F, Т, Μ), где S - множество начальных состояний; F – нечеткое множество операторов, отображающих одни состояния в другие; Т - множество целевых состояний, М – функция принадлежности на множестве F. Решение задачи состоит в нахождении последовательности операторов fijz—ji (fi sF), которые преобразуют нечеткие начальные состояния в конечные.

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

Одна из основных проблем – это сложность анализируемых и определяемых шаблонов. Шаблоны должны содержать нечеткие, неопределенные и неожиданные кластеры и регулярные объекты в данных, составляющие так называемые скрытые данные. Новая технология DM включает следующие этапы в процессе анализа и обнаружения в неопределенных данных: нечетких; нетривиальных; полезных для данной практической деятельности; доступных интерпретаций знаний, необходимых для принятия решений в исследуемой области.

Типичную ЭС можно представить как систему, состоящую из следующих основных компонент: модуль DM; база данных; база знаний (БЗ); интерпретатор; компонент общения. Такие структуры принято называть динамическими ЭС, так как они изменяются в процессе принятия решения. ЭС такого типа используют в тех приложениях, где учитываются изменения, происходящие за время решения задачи.

Новая методология проектирования динамических ЭС (ДЭС) включает перспективные элементы адаптивной технологии, анализ риска, обучения и самоорганизации, достоинства эволюционных и бионических моделей. Таким образом, ДЭС как вычислительная среда имеет прямое применение для проектирования РЭА и ЭВА в качестве средства автоматизации принятия решений.

Стандартная система поддержки принятия решения состоит из следующих основных блоков:

• генерация возможных альтернатив решений (сценариев);
  
• оценки решений (построения ЦФ);
  
• согласование решений, анализ динамики развития ситуации;
  
• выбор решения (группы решений), сценария;
  
• оценка соответствия принятых решений заданным целям.
  

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

ГА= (6)

где P_i^o- исходная популяция хромосом (альтернативных решений), – хромосома (альтернативное решение), принадлежащее i-ой исходной популяции; N – мощность популяции, т.е. число входящих в нее хромосом, – k-я хромосома, принадлежащая i-ой популяции, находящейся в T поколении эволюции; T = 0,1,2,… – номер поколения, проходимого популяцией во время эволюции. Число поколений связывают с числом генераций генетического алгоритма, обозначаемых буквой – длина i-ой хромосомы (альтернативного решения). Число генов (элементов, входящих в закодированное решение, представленное в заданном алфавите), например, | – произвольный абстрактный алфавит, в котором, кодируются хромосомы, например, A₁={0,1}, A₂={0,1,2,…,10}, A₃={0,1,2,*}, A₄={A,B,C,D}, здесь * – метка, означающая любой символ в алфавите A₂; (ЦФ,ОГР,ГУ) – целевая функция, ограничения и граничные условия, которые определяются на основе заданной модели исходной решаемой задачи; ГО – генетические операторы, t – критерий окончания работы ГА. Тогда обобщенная структура ГА при решении задач ПР будет состоять из четырех предварительных этапов: выбор представления решения; разработка операторов случайных изменений; определение законов выживания решения; создание начальной популяции альтернативных решений.

При решении задач ПР в САПР с некоторыми допущениями в качестве автономного агента рассмотрим генетический алгоритм. Приведем модифицированную архитектуру «Машина Тьюринга» для задачи ПР в САПР. Такая архитектура (рис.4.) объединяет в себе механизмы рассуждений на основе знаний о задаче проектирования.



Рис.4. Многоуровневая архитектура ГА «Машина Тьюринга»

Пусть задан «главный» генетический алгоритм, взаимодействующий с другими, соподчиненными ГА, анализирующий нечеткие события внешней среды, информация о которой носит фрагментарный характер. При этом «главный» алгоритм выступает в роли экспертной системы или лица, принимающего решения. Предлагается такая архитектура поиска, которая функционирует в условиях неопределенности, неполноты, неточности и реагирует на неожиданные (незакрепленные в жесткой структуре алгоритма) нечеткие высказывания о проектировании. Например, добавить микросхему согласования входа и выхода, провести дублирование основных библиотечных элементов проектируемой схемы, провести анализ всех соединений между элементами топологии, выполнить синхронизацию и передачу глобальных сигналов, разработать схему композиции системы из различных компонентов и провести статистический анализ временных задержек. Пример такой архитектуры приведен на рис.4. Каждый уровень напрямую связан с подсистемами действия и восприятия. Любой уровень независимо от других может реагировать на текущее состояние внешней среды. В рассматриваемой архитектуре включена подсистема управления на основе различного вида правил, активируемая внешней средой и подсистемой адаптации. Ее основная задача - получение локально-оптимальных результатов. Система играет роль «посредника» между входом и выходом, т.е. вероятностным или нечетким автоматом, который анализирует данные разных уровней, вводит на различные уровни новые и удаляет ненужные данные.

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



Рис.5. Схема процесса альтернативной адаптации

В схеме на рис.5. используются три популяции альтернативных решений (A1 – полученная случайным образом, A2 – направленным, А3 – комбинированным). Необходимо обеспечить минимизацию , где F_k – показатель качества решения, полученного для задачи ПР. Используем модифицированный автомат (МА), представляющий собой четверку: МA={S,A,B,F}, где  множество внутренних состояний автомата, m – глубина памяти автомата, F=f_ij матрица переходов. А={a₁,a₂,...,a_n}-множество действий автомата; B={0,1} – множество входов автомата, причем “0” соответствует “выигрышу”, а “1” – проигрышу автомата. Считаем, что каждому из действий автомата соответствует та или иная методика ПР. Входы В определяются результатами применения какого-либо из действий: удачное применение -”1”, неудачное -”0”. В зависимости от входного сигнала автомат изменяет внутреннее состояние. Оно, в свою очередь, определяет действие, применяемое автоматом в следующий дискретный момент времени t_i, t=1,2,…

Матрица переходов F=f_ij определяет зависимость между предыдущим состоянием автомата и последующим, при этомносит смысл вероятности перехода автомата из состояния в состояние . В детерминированном случае f_ij={0,1}. Таким образом, при наличии конечного числа структур является возможным адаптивный выбор одной из них с целью повышения среднего уровня качества решений на потоке задач.

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

Применение нестандартных архитектур генетического поиска позволяет эффективно решать задачи принятия решений при проектировании. Разработанные алгоритмы позволяют получать не одно, а набор оптимальных, или квазиоптимальных альтернативных решений. Время получения лучших результатов соответствует полиномиальному времени (O(nlogn)-О(n²), где n - число входных данных.