Разработка теории и основных принципов принятия решений в САПР на основе методов, инспирированных природными системами
Характеристика специфических особенностей комбинаторного подхода к решению оптимизационных задач принятия решений на графовых моделях. Разработка архитектуры бионического и квантового поиска, которая ориентирована на решение задач проектирования.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | автореферат |
| Язык | русский |
| Дата добавления | 30.01.2018 |
| Размер файла | 430,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Размещено на http://www.allbest.ru
Введение
Актуальность работы. Одной из основных проблем в науке и технике 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 наименований и приложений. В приложение вынесены акты об использовании и внедрении результатов диссертационной работы.
1. Анализ процесса развития систем поддержки принятия решений в проектировании
Сформулирована постановка задачи и рассмотрены существующие основные модели принятия решений. Построена модифицированная классификация методов принятия решений. Рассмотрен информационный подход к разработке систем поддержки принятия решений. Приведены новые и модифицированные способы приобретения знаний при принятии решений. Проведен анализ новых и модифицированных моделей представления нечетких и неопределенных знаний. Сделаны выводы о необходимости построения комплексной методологии на основе методов, инспирированных природными системами, для эффективного принятия решений.
Принятием решений считают множество альтернатив в условиях определенности, позволяющих получать однозначные, непротиворечивые, корректные решения на основе формализованных моделей анализируемых объектов, моделей управления и моделей внешней среды. К задачам поддержки принятия решений в новых информационных технологиях относятся все задачи, включая класс задач в условиях нечеткости и неопределенности, окончательное решение которых осуществляется на основе анализа полученных альтернатив. В этих случаях информацию преобразуют к виду, упрощающему и облегчающему принятие решений. Поэтому при невозможности получения решения задачи при заданных условиях автор предлагает использовать следующие принципы, положения и методы: «Бритвы Оккама» - упрощение условий решения задачи и сведение ее к известной. «Разделяй и властвуй» - разбиение сложной задачи на отдельные подзадачи с возможностью последующей сборки. «Data mining» (DM) - использование интеллектуального анализа извлечения знаний. «Выживание сильнейших» - то есть выбор оптимальных решений в процессе моделирования эволюции.
Сформулируем постановку задачи исследований. Обозначим вектором = {1,…,r} множество неконтролируемых параметров системы проектирования, которые, являясь случайными величинами, влияют на значения выходных параметров. Обозначим другим вектором = (1, 2,…, к) совокупность неконтролируемых параметров, которые, являясь расплывчатыми величинами, влияют также на значения выходных параметров. При этом i = i, zi, где i - функция принадлежности элемента zi к множеству , i=[0,1]. Тогда математическое описание системы примет вид:
Y = F (X, Z, , ). (1)
Модель принятия решения включает шесть основных, циклических повторяющихся этапов: сбор всех видов информации, как четкой, так и нечеткой; анализ данных; преобразование данных; разработка критериев оценки решений; получение вариантов решений (альтернатив); исследование альтернатив и выбор помножества вариантов (или одного из них) на основе заданных критериев.
В работе описана модифицированная обобщенная схема поддержки принятия решений. Она имеет иерархический вид, состоящий из нескольких уровней. В методологическом плане, в зависимости от возможностей и полноты их количественного описания, задачи принятия решений можно распределить на такие группы:
· задачи с полным математическим описанием исходных данных,
условий, критериев и принципов оптимальности решений;
· задачи с неполным математическим описанием исходных данных,
условий и качественным описанием критериев и принципов оптимальности;
· задачи с математическим описанием основных ресурсных исходных данных и качественным описанием условий, критериев и принципов оптимальности решений.
Под задачей принятия решений в условиях неопределенности понимается тройка {A,X,S}. Взаимодействие рассматриваемых элементов можно представить общей схемой:,т.е. состояние в сочетании с выбранной альтернативой определяет исход решения. Многие задачи СППР являются NP-полными и не поддаются формализации ввиду неопределенности и нечеткости задач проектирования, исходных данных, критериев, ограничений и граничных условий. Задачи ПР в САПР будем рассматривать в контексте поиска в пространстве состояний. Формально задача ПР запишется:
ПР=<U, Sн, Sк, Sдоп., ЦФ, ОГР, ГУ, цпр>,
где: U - универсум (множество всех состояний), Sн(Sк) - подмножество начальных (конечных) состояний, Sдоп. - подмножество допустимых (U \Sдоп. - недопустимых) состояний, Sн, Sк, Sдоп.U, цпр: Sдоп.> Sдоп. - множество правил преобразования, ЦФ- множество целевых функций, критериев оценки найденных решений, ОГР - ограничения, ГУ - граничные условия.
Решением задачи ПР можно считать подмножество альтернативных проектно-конструкторских решений, полученных на основе алгоритмов (последовательности применения правил). При этом результаты композиции и суперпозиции остаются в подмножестве допустимых состояний.
ц1 ? ц2 ? … ?цn ю Sк
ц1 ? ц2 ? … ?цn ю Sк ,
где ? и ? знаки композиции и суперпозиции соответственно. На рис.1. приведена обобщенная схема процесса принятия решений при проектировании.
В последнее время появились новые технологии решения задач поддержки принятия решений. К ним относятся бионические и биоинспирированные методы и алгоритмы.
Рис. 1. Обобщенная схема процесса принятия решений при проектировании
В этих алгоритмах используется новая технология моделирования эволюции, а также методы естественного отбора среди живых организмов в природе для выбора сильнейших. Эти методы позволяют создавать предельно гибкие, быстрые и эффективные инструменты проектирования и анализа данных. В этой связи автор планирует разработку теории и принципов поддержки принятия решений выполнять на основе указанных технологий.
Приведем упрощенную схему взаимодействия САПР и СППР (рис.2). Она подробнее раскрывает блок проблемной области на рис.1. В хранилище данных находятся сведения о Гостах, стандартах, технологиях проектирования и ранее выполненных проектах, которые могут быть вызваны экспертной системой (ЭС) для принятия решений по реализации нового проекта. В базе данных (БД) основным является библиотека стандартных топологических решений. На вход препроцессора подаются все модели объекта проектирования и коммутационного рабочего поля. На вход СППР подаются все данные о ПР, приведенные выше. Постпроцессор анализирует полученные альтернативные решения. В блоке «?» определяется получение удовлетворительного решения. В случае его отсутствия происходит адаптация с внешней средой с учетом прогнозов и рисков проектирования. Далее процесс продолжается итерационно до получения оптимального решения.
Рис. 2. Упрощенная схема взаимодействия САПР и СППР
комбинаторный квантовый бионический
2. Интеллектуальная система поддержки принятия решений (ИСППР) в САПР
Под ИСППР понимают организационно-техническую систему, состоящую из интеллектуального комплекса средств поддержки принятия решений, взаимосвязанного и взаимодействующего с пользователями и сетями ЭВМ, и выполняющую решения задач проектирования и конструирования.
Укрупненная структура ИСППР в САПР по аналогии с другими интеллектуальными системами состоит из четырех подсистем: адаптивной; интерактивной; обрабатывающей; подсистемы управления и блока «внешняя среда» (рис.3.). Первая подсистема состоит из нескольких уровней: микро, макро и мета - уровней. Между данными уровнями организована связь на основе полных и неполных, четких (нечетких) графов и гиперграфов. На каждом уровне строится интегрированная целевая функция, определяются свои граничные условия и ограничения. Далее строится обобщенная целевая функция для всей ИСППР. Целевые функции на микро-, макро- и метауровне будут частными целевыми функциями. Здесь реализуется эффект «матрешки» (англ. - nesting). В этом случае:
ЦФ1= б1K1 + б2K2 + … бnKn , (б1 + б2 + … бn = 1), (2)
где ЦФ1 - целевая функция на микроуровне, K1, K2, …, Kn - частные целевые функции, б1, б2, …, бn - коэффициенты, определяющие степень принадлежности (важности) каждого критерия на этом уровне, n - число частных критериев. Соответственно, на макро- и метауровне запишем:
ЦФ2= в1М1 + в2М2 + … вnМn , (в1 + в2 + … вn = 1), (3)
ЦФ3= г1R1 + г2R2 + … гnRn , (г1 + г2 + … гn = 1), (4)
где ЦФ2 (ЦФ3) - целевая функция на макроуровне (метауровне), М1, М2, …, Мn (R1, R2, …, Rn) - частные целевые функции, в1, в2, …, вn (г1, г2, … гn) - коэффициенты, определяющие степень принадлежности (важности) каждого критерия на макро- (мета) уровне, n - число частных критериев. Отметим, что для простоты взято общее число частных критериев (n) на всех уровнях. Тогда обобщенная (интегрированная) целевая функция ИСППР запишется:
ЦФинт= 1ЦФ1 + 2ЦФ2 + 3ЦФ3 , (1+2+3 = 1), (5)
где 1, 2, 3 - коэффициенты, определяющие степень принадлежности (важности) каждого критерия микро-, макро- и метауровня в интегрированном критерии (ЦФинт) для всей СППР.
Вторая подсистема анализирует входные описания на языке пользователя на основе имеющихся знаний и формирует внутреннее неполное и расплывчатое представление задачи. Здесь важно задание четкого множества исходных данных X = {x1, x2, …, xl} и определение на нем нечеткого множества Г = {< µ1, x1>, < µ2, x2>, … < µl, xl>,}. При этом µi М(X) функция принадлежности элемента xi, а величина М(X) изменяется на интервале [0, 1].
Рис. 3.Трехуровневая адаптивная система
Третья подсистема превращает неполное и расплывчатое описание задачи в полное и четкое и снова передает его интерактивной подсистеме. Далее процесс происходит итерационно до получения удовлетворительного решения. Четвертая подсистема управляет процессом решения, взаимодействуя с 1, 2 и 3 подсистемами.
Задачу поиска решений в пространстве состояний формулируется следующим образом. Пусть исходная задача описывается тройкой (S, F, Т, М), где S - множество начальных состояний; F - нечеткое множество операторов, отображающих одни состояния в другие; Т - множество целевых состояний, М - функция принадлежности на множестве F. Решение задачи состоит в нахождении последовательности операторов fijz--ji (fi sF), которые преобразуют нечеткие начальные состояния в конечные.
Существует несколько путей передачи знаний в ЭС. Первый путь: знания могут быть получены от эксперта посредством инженера знаний или с помощью специального механизма извлечения знаний, который заменяет в данном случае инженера знаний. Путь второй: приобретение знаний из текстов и различных, уже каким-то образом обработанных данных с помощью механизмов извлечения знаний. Процесс принятия решений тесно связан с извлечением, добычей знаний. При этом важную роль играет интеграция полученных результатов. Особую роль играют методы распределения и построения иерархии.
Одна из основных проблем - это сложность анализируемых и определяемых шаблонов. Шаблоны должны содержать нечеткие, неопределенные и неожиданные кластеры и регулярные объекты в данных, составляющие так называемые скрытые данные. Новая технология DM включает следующие этапы в процессе анализа и обнаружения в неопределенных данных: нечетких; нетривиальных; полезных для данной практической деятельности; доступных интерпретаций знаний, необходимых для принятия решений в исследуемой области.
Типичную ЭС можно представить как систему, состоящую из следующих основных компонент: модуль DM; база данных; база знаний (БЗ); интерпретатор; компонент общения. Такие структуры принято называть динамическими ЭС, так как они изменяются в процессе принятия решения. ЭС такого типа используют в тех приложениях, где учитываются изменения, происходящие за время решения задачи.
Новая методология проектирования динамических ЭС (ДЭС) включает перспективные элементы адаптивной технологии, анализ риска, обучения и самоорганизации, достоинства эволюционных и бионических моделей. Таким образом, ДЭС как вычислительная среда имеет прямое применение для проектирования РЭА и ЭВА в качестве средства автоматизации принятия решений.
Стандартная система поддержки принятия решения состоит из следующих основных блоков:
генерация возможных альтернатив решений (сценариев);
оценки решений (построения ЦФ);
согласование решений, анализ динамики развития ситуации;
выбор решения (группы решений), сценария;
оценка соответствия принятых решений заданным целям.
Сравнивая эту систему со структурой генетических алгоритмов, можно заметить много общего. Генетические алгоритмыманипулируют популяцией хромосом на основе механизма натуральной эволюции. Приведем формальное определение ГА.
ГА= (6)
где Pio - исходная популяция хромосом (альтернативных решений), - хромосома (альтернативное решение), принадлежащее i-ой исходной популяции; N - мощность популяции, т.е. число входящих в нее хромосом, - k-я хромосома, принадлежащая i-ой популяции, находящейся в T поколении эволюции; T = 0,1,2,… - номер поколения, проходимого популяцией во время эволюции. Число поколений связывают с числом генераций генетического алгоритма, обозначаемых буквой - длина i-ой хромосомы (альтернативного решения). Число генов (элементов, входящих в закодированное решение, представленное в заданном алфавите), например, | - произвольный абстрактный алфавит, в котором, кодируются хромосомы, например, A1={0,1}, A2={0,1,2,…,10}, A3={0,1,2,*}, A4={A,B,C,D}, здесь * - метка, означающая любой символ в алфавите A2; (ЦФ,ОГР,ГУ) - целевая функция, ограничения и граничные условия, которые определяются на основе заданной модели исходной решаемой задачи; ГО - генетические операторы, t - критерий окончания работы ГА. Тогда обобщенная структура ГА при решении задач ПР будет состоять из четырех предварительных этапов: выбор представления решения; разработка операторов случайных изменений; определение законов выживания решения; создание начальной популяции альтернативных решений.
При решении задач ПР в САПР с некоторыми допущениями в качестве автономного агента рассмотрим генетический алгоритм. Приведем модифицированную архитектуру «Машина Тьюринга» для задачи ПР в САПР. Такая архитектура (рис. 4.) объединяет в себе механизмы рассуждений на основе знаний о задаче проектирования.
Рис. 4. Многоуровневая архитектура ГА «Машина Тьюринга»
Пусть задан «главный» генетический алгоритм, взаимодействующий с другими, соподчиненными ГА, анализирующий нечеткие события внешней среды, информация о которой носит фрагментарный характер. При этом «главный» алгоритм выступает в роли экспертной системы или лица, принимающего решения. Предлагается такая архитектура поиска, которая функционирует в условиях неопределенности, неполноты, неточности и реагирует на неожиданные (незакрепленные в жесткой структуре алгоритма) нечеткие высказывания о проектировании. Например, добавить микросхему согласования входа и выхода, провести дублирование основных библиотечных элементов проектируемой схемы, провести анализ всех соединений между элементами топологии, выполнить синхронизацию и передачу глобальных сигналов, разработать схему композиции системы из различных компонентов и провести статистический анализ временных задержек. Пример такой архитектуры приведен на рис.4. Каждый уровень напрямую связан с подсистемами действия и восприятия. Любой уровень независимо от других может реагировать на текущее состояние внешней среды. В рассматриваемой архитектуре включена подсистема управления на основе различного вида правил, активируемая внешней средой и подсистемой адаптации. Ее основная задача - получение локально-оптимальных результатов. Система играет роль «посредника» между входом и выходом, т.е. вероятностным или нечетким автоматом, который анализирует данные разных уровней, вводит на различные уровни новые и удаляет ненужные данные.
Предлагается подход динамического “отслеживания” оптимальных параметров и структур алгоритма с помощью методов параметрической и структурной адаптации. Схема процесса альтернативной адаптации при принятии решений показана на рис. 5.
Рис. 5. Схема процесса альтернативной адаптации
В схеме на рис.5. используются три популяции альтернативных решений (A1 - полученная случайным образом, A2 - направленным, А3 - комбинированным). Необходимо обеспечить минимизацию , где Fk - показатель качества решения, полученного для задачи ПР. Используем модифицированный автомат (МА), представляющий собой четверку: МA={S,A,B,F}, где множество внутренних состояний автомата, m - глубина памяти автомата, F=fij матрица переходов. А={a1,a2,...,an}-множество действий автомата; B={0,1} - множество входов автомата, причем “0” соответствует “выигрышу”, а “1” - проигрышу автомата. Считаем, что каждому из действий автомата соответствует та или иная методика ПР. Входы В определяются результатами применения какого-либо из действий: удачное применение -”1”, неудачное -”0”. В зависимости от входного сигнала автомат изменяет внутреннее состояние. Оно, в свою очередь, определяет действие, применяемое автоматом в следующий дискретный момент времени ti, t=1,2,…
Матрица переходов F=fij определяет зависимость между предыдущим состоянием автомата и последующим, при этомносит смысл вероятности перехода автомата из состояния в состояние . В детерминированном случае fij={0,1}. Таким образом, при наличии конечного числа структур является возможным адаптивный выбор одной из них с целью повышения среднего уровня качества решений на потоке задач.
В работе описаны и проанализированы модифицированные методы вывода и поиска решений в продукционных системах на фреймах и семантических сетях. Это позволяет построить иерархическую систему вывода, действующую по принципу «матрешки». Рассмотрены представления данных, знаний и метаданных в СППР. Это позволяет эффективно осуществлять поиск знаний, необходимых для функционирования системы. Предложено использование экспертных систем в СППР. Это сделано для введения ЛПР в систему обратной связи с внешней средой. Рассмотрено представление данных и знаний в системах поддержки принятия решений в реальном времени. Разработаны новые и модифицированные алгоритмы работы динамических экспертных систем при выборе конфигурации системы поддержки принятия решений в САПР.
Применение нестандартных архитектур генетического поиска позволяет эффективно решать задачи принятия решений при проектировании. Разработанные алгоритмы позволяют получать не одно, а набор оптимальных, или квазиоптимальных альтернативных решений. Время получения лучших результатов соответствует полиномиальному времени (O(nlogn)-О(n2), где n - число входных данных.
Фундаментальным методом повышения производительности при проектировании систем на кристалле (СнК) является повторное использование IP-блоков (начиная с маленьких и переходя к большим). Это соответствует созданию стандартных блоков в генетических алгоритмах. В этой связи необходимы разработка и построение новых и модернизация существующих моделей эволюции. В работе проведен анализ и обзор состояния основных моделей эволюции.
Модель эволюции Ч. Дарвина - это условная структура, реализующая процесс, посредством которого особи некоторой популяции, имеющие более высокое функциональное значение, получают большую возможность для воспроизведения потомков, чем «слабые» особи. Такой механизм часто называют методом «выживания сильнейших». Модель эволюции Ж. Ламарка основана на предположении, что характеристики, приобретенные особью (организмом) в течение жизни, наследуются его потомками. Эти изменения, как утверждал Ж. Ламарк, вызываются прямым влиянием внешней среды, упражнением органов и наследованием приобретенных при жизни признаков. В основе модели эволюции Г. де Фриза лежит моделирование социальных и географических катастроф, приводящих к резкому изменению видов и популяций.
Модель прерывистого равновесия Гулда-Элдриджа является развитием и модификацией модели Г. де Фриза. Метод прерывистого равновесия использует палеонтологическую теорию, которая строит модели эволюции на основе описаний вулканических и других изменений земной коры. Модель К. Поппера - это условная структура, реализующая иерархическую систему гибких механизмов управления, в которых мутация интерпретируется как метод случайных проб и ошибок, а отбор - как один из способов управления при взаимодействии с внешней средой. Отметим, что модель эволюции Поппера естественно вкладывается в человеко-машинную систему принятия решений. Человек-оператор практически всегда работает методом «проб и ошибок». М. Кимура предложил модель нейтральной эволюции с нейтральным отбором. Теория нейтральности предполагает, что большая часть молекулярных вариантов имеет равную приспособленность друг относительно друга. Изменчивость здесь поддерживается балансирующим отбором. Рассматриваемый процесс всегда сходится к одному из поглощающих состояний.
Основная задача синтетической теории эволюции - определение природы противоречий или постепенной эволюции, то есть разных форм противоречий между наследственностью и постоянно меняющимися потребностями в приспособлениях, а также взаимодействие между микро-, макро- и метаэволюцией на разных иерархических уровнях.
Автор считает важным объединение всех видов и моделей эволюций в интегрированную многоуровневую модель. На рис.6 приведена условная интегрированная схема эволюции. Отметим, что блоки 1-n соответствуют рассмотренным схемам моделей эволюции. Основным этапом в каждой модели эволюции является анализ популяции, ее преобразование тем или иным способом и эволюционная смена форм.
Рис. 6. Условная интегрированная схема эволюции
Приведем условную архитектуру поиска для принятия решений в САПР (рис. 7). Она состоит из четырех основных блоков. В блоке инициализации производится выбор и построение моделей эволюции. В блоке обработки на основе выбранных моделей строится алгоритм поиска решений. Далее в блоке вычислений производится генерация альтернативных решений, построение целевой функции и выбор квазиоптимальных решений при проектировании. В случае получения неудовлетворительных решений, в блоке распределения, производится распараллеливание процесса решения и реализация алгоритмов с помощью многопроцессорных систем.
В работе описана модифицированная модель эволюции Шмальгаузена, основанная на преобразовании специальных кубов. Автор использовал четыре типа скрещиваний и четыре основные формы отбора в СППР при принятии решений по выбору эффективных алгоритмов проектирования. Эксперименты показали, что при компоновке целесообразным является инбридинг, а для остальных задач проектирования ассортативное и селективное скрещивание. Эволюция здесь - это авторегулируемый процесс, основанный на обратной связи. На ее основе происходит анализ микроэволюции. Она рассматривает процессы, протекающие на уровне популяций, начиная с механизмов изменчивости.
Рис. 7. Условная архитектура поиска
На рис. 8 приведена схема алгоритма на основе модифицированной модели ЭШ. Эволюционирующую популяцию и внутривидовую дифференциацию популяций представим как трехмерную решетку. В ней каждая плоскость - это эволюция особи, прошедшей естественный отбор, а вершины (узлы) ячейки - результат их скрещивания. Модель демонстрирует процесс перехода от микроэволюции популяций к макроэволюции (эволюции надвидов). Будем считать, что узлы решетки это особи (хромосомы), т.е. альтернативные сценарии анализируемой задачи принятия решений. Они образуют начальную популяцию альтернативных решений P = {X1, X2,…, X8}, |P| = 8. Согласно произвольному генетическому алгоритму для каждого элемента XjP определяется целевая функция (функция приспособленности). Далее согласно целевой функции (ЦФ) производится отбор элементов для реализации генетического поиска.
Рис. 8. Схема алгоритма на основе модифицированной модели ЭШ
Он состоит из последовательной, параллельной или комбинированной реализации генетических операторов (ГО). На основе решетки Шмальгаузена построен новый оператор кроссинговера (ОК).
Начальную популяцию особей (хромосом, альтернативных решений), предлагается создавать таким образом, чтобы ее размер был кратным 8. Далее исходная популяция разбивается на ряд подпопуляций P = {P1, P2,…, Pn}, при этом строится две решетки (рис. 9).
Рис. 9. Пример работы ЭШ на двух решетках
Причем |Pi|=8, i 1,2,…,n. n (mod 2) т.е. четное и обязательно делится на 8. Это сделано для того, чтобы каждый раз иметь возможность строить трехмерные решетки Шмальгаузена.
Произведем ранжирование исходной популяции по значению целевой функции. Далее начинаем реализовать параллельную микроэволюцию внутри каждого куба. Процесс реализации ОК продолжается, пока не будет достигнут критерий остановки. Основными критериями останова алгоритма являются следующие: время (ЦФ1), выполнение всех итераций ГА (ЦФ2), попадание в локальный оптимум (ЦФ3), получение заданного результата, если он известен (ЦФ4). Построим аддитивный обобщенный критерий:
K = ЦФ11+ ЦФ22+ ЦФ33+ ЦФ44, причем 1+2+3+4=1.
Отметим, что обычно один критерий задается как основной, а остальные учитываются как ограничения. Приведем описание генетического алгоритма на основе модифицированной ЭШ.
1. Во взаимодействии с внешней средой строится одна из возможных популяций P1, P2 и P3 или P4 на основе прямого, случайного, направленного или комбинированного взаимодействий.
2. Производится построение целевой функции для определения степени приспособленности каждой хромосомы. Производится ранжирование каждой хромосомы (альтернативного решения) по максимальному значению ЦФ.
3. Выполняется удаление “плохих” хромосом таким образом, чтобы мощность популяции была кратной восьми.
4. Популяция разбивается на подпопуляции P1, P2,…Pn, P1 U P2 U… U Pn = P, P1 ? P2 ? … ? Pn ? , где n- кратно восьми.
5. Для каждой подпопуляции строится решетка (куб) Шмальгаузена.
6. В каждом кубе, используя механизмы “дробовика”, “одеяла”, ”фокусировки”, “колеса рулетки” и др., выбираются вершины кубов. Они определяют, какие хромосомы будут в дальнейшем скрещиваться, мутировать и т.п., т.е. каким образом будут реализовываться генетические операторы.
7. На основе ЭШ производится реализация ГО. Если критерии останова достигнуты, то переход к 8, если нет, то t=t+1 и переход к 4 с разбитием популяции на другие подпопуляции.
8. Выполнение операции объединения кубов и повторения операций 1-7.
9. Построение подмножества оптимальных или квазиоптимальных альтернативных решений.
10. Конец работы алгоритма.
В процессе макроэволюции преобразование будет происходить на уровне популяции и ее подпопуляций. На этапе метаэволюции процесс преобразования происходит между большим числом частей популяций и даже целых популяций. Понятие надуровень предполагает взаимодействие целых популяций, видов и частей видов, согласно идеям, предположенным Вернадским. В работе отмечено, что все преобразования выполняются под управлением внешней среды (стандарты, ГОСТы, технологии, опыт конструктора и технолога), внутри которой происходят эти преобразования.
В работе приведены основные элементы теории биоинспирированных алгоритмов (БА). Она основана на основных положениях теории множеств, теории алгоритмов, теории графов, алгебры логики, оптимизации и др. На ее основе построены модифицированные схемы научных теорий индуктивного метода и К. Поппера (рис. 10).
Рис. 10. Модифицированная структура построения теории К. Поппера
В рассматриваемой теории объектами являются хромосомы (альтернативные решения задач проектирования и конструирования), а универсумом - вся их совокупность. Введем следующие понятия: Объекты - хромосомы. Универсум - популяция хромосом. Константы - простейшие из выражений, обозначающих предметы, т.е. их имена.
Приведем основные аксиомы этой теории:
1. Высказывания принимают логические значения.
2. Единственными общепринятыми логическими значениями являются истина и ложь.
3. Каждая теория имеет свой универсум, т.е. множество рассматриваемых предметов. Если универсумов несколько, они называются сортами или типами.
4. Высказывания о предметах образуются при помощи отношений или предикатов.
5. Выражения, обозначающие предметы, называются термами.
6. Термы строятся из переменных и констант при помощи операций или функциональных символов, которые применяются к предметам и в результате дают предмет.
7. Отношения (предикаты) применяются к термам и в результате дают высказывания (элементарную формулу).
Пусть каждому исходному понятию и отношению аксиоматической теории БА поставлен в соответствие некоторый конкретный математический объект. Совокупность таких объектов называется полем интерпретации. Всякому утверждению U теории БА ставится в соответствие некоторое высказывание U* об элементах поля интерпретации, которое может быть истинным или ложным. Тогда можно сказать, что утверждение U теории БА соответственно истинно или ложно в данной интерпретации. Поле интерпретации и его свойства сами обычно являются объектом рассмотрения другой теории простых генетических алгоритмов (ПГА), которая, в частности, может быть аксиоматической. Этот метод позволяет доказывать суждения типа: если теория БА непротиворечива, то непротиворечива и теория ПГА. Пусть теория БА проинтерпретирована в теории ПГА таким образом, что все аксиомы Ai теории БА интерпретируются истинными суждениями Ai* теории ПГА. Тогда всякая теорема теории БА, то есть всякое утверждение А, логически выведенное из аксиом Ai в БА, интерпретируется в ПГА некоторым утверждением A*, выводимым в ПГА из интерпретаций Ai* аксиом Ai и, следовательно, истинным. Уточнением понятия аксиоматической теории является понятие формальной системы. Это позволяет представлять математические теории как точные математические объекты и строить общую теорию или метатеорию таких теорий. Общая схема построения произвольной формальной системы БА такова:
1. Язык системы БА: аппарат алгебры логики; теория четких и нечетких множеств; теория графов и гиперграфов, теория четких и нечетких алгоритмов, основные положения биоинформатики, теории систем, синергетики и теория принятия решений.
1.1. Алфавит - перечень элементарных символов системы: двоичный, десятичный, буквенный, Фибоначчи и др.
1.2. Правила образования (синтаксис), по которым из элементарных символов строятся формулы теории БА: построение моделей эволюций; конструирования популяций; построения ЦФ; разработки новых и модифицированных генетических операторов; репродукции популяций; рекомбинации популяций; редукции; адаптации; выбор структуры генетических алгоритмов; построение комбинированных генетических, биоинспированных и квантовых алгоритмов проектирования.
Последовательность элементарных символов считается формулой тогда и только тогда, когда она может быть построена с помощью правил образования.
2. Аксиомы системы БА. Выделяется некоторое множество конечных формул, которые называются аксиомами системы. В БА существует большое число наборов аксиом. Например, следующий базовый набор аксиом:
· Выбор модифицированной модели эволюции Дарвина.
· Популяция конструкторских и технологических решений строится случайным образом.
· Размер хромосомы (альтернативных решений) остается постоянным.
· Выполнение оператора репродукции производится на основе «колеса рулетки».
· Обязательное использование операторов кроссинговера, мутации и инверсии.
· Размер популяции после каждой генерации остается постоянным.
· Редукция выполняется на основе элитной схемы.
· Размер популяции задается экспертной системой, внешней средой или лицом, принимающим решения.
· Число копий (решений), переходящих в следующую генерацию, определяется согласно теореме генетических алгоритмов.
· Целевая функция определяется на основе принципа «Выживание сильнейших».
3. Правила вывода БА. Фиксируется конечная совокупность предикатов П1, П2,…, Пk на множестве всех формул системы.
Заданием 1,2,3 исчерпывается задание формальной системы БА как математического объекта.
Итак, можно выстроить следующую цепочку построения и реализации теории генетических алгоритмов. Стратегия - теория - концепция - принципы - аксиомы - гипотезы - практическая реализация.
Предлагается ряд основных стратегий взаимодействия методов эволюционного и локального поиска в задачах САПР: «поиск - эволюция»; «эволюция - поиск »; «поиск - эволюция - поиск»; «эволюция - поиск - эволюция»; «эволюция - поиск - эволюция - поиск - эволюция - поиск»; «поиск - эволюция - адаптация»; «эволюция - поиск - адаптация»; «поиск - эволюция - поиск - миграция - адаптация»; «эволюция - поиск - эволюция - миграция - адаптация». Заметим, что иерархически можно строить стратегии такого типа любого уровня сложности. Например, «эволюция - поиск - эволюция - поиск - эволюция - поиск», используя последовательную, параллельную или любые другие стратегии поиска. Отметим, что такое построение зависит от наличия вычислительных ресурсов и времени, заданного на получение окончательного решения.
В последнее время появились новые подходы решения NP-полных проблем и неструктурированных проблем поиска. При поиске и обнаружении данных предлагается новая технология на основе квантового поиска. Для реализации поиска квантовое пространство преобразуется в общую суперпозицию, которая концентрируется в векторе, определяющем путь до цели поиска. Для решения NP-полных проблем принятия решений при поиске неструктурированных знаний предлагается анализировать базу знаний (БЗ), чтобы «выращивать» полные решения, рекурсивно расширяя последовательные частичные решения. Приведем модифицированный алгоритм квантового поиска.
1. Начало.
2. Ввод исходных данных.
3. Проверка условий существования инвариантных частей в БЗ.
4. Анализ математической модели БЗ, и на ее основе построение подмножества деревьев частичных решений.
5. Суперпозиция частичных решений на основе «жадной» стратегии, квантового, генетического или бионического поиска.
6. В случае наличия тупиковых решений возврат к шагу 4 и проведение параллельного поиска.
7. Последовательный поиск в ветвях дерева решений с пошаговым возвращением.
8. Если набор полных решений построен, то переход к 9, если нет, то к 4.
9. Лексикографический перебор полных решений и выбор из него оптимального или квазиоптимального решения.
10. Конец работы алгоритма.
Следует отметить, что, изменяя параметры, алгоритмы и схему квантового поиска, в некоторых случаях можно выходить из локальных оптимумов. На рис. 11 приведена схема распараллеливания квантового поиска на основе октаэдра. Введение экспертной подсистемы позволит определить назначение каждого блока квантового алгоритма. Например, КА1 - определяет целевую функцию, КА2 - операцию суперпозиции и т.п.
Рис. 11. Схема распараллеливания квантового поиска на основе октаэдра
Для повышения скорости нахождения оптимальных решений предлагаются комплексные алгоритмы, основанные на взаимодействии жадных, генетических, квантовых и бионических алгоритмов (рис.12). Очевидно, что данные схемы можно взять как строительные блоки (IP-блоки при проектировании систем на кристалле) и наращивать иерархически. При этом возможно построить схему последовательного или параллельного совместного поиска любой сложности.
Рис. 12. Схемы взаимодействия алгоритмов
На рис. 13 приведена схема каскадной реализации бионического поиска. Идея подхода заключается в каскадном построении схемы бионического поиска. Здесь ГА - генетический, МА - муравьиный, КА - квантовый, ЭА - эволюционный, МО - моделирования отжига алгоритмы. Они реализуются каждый на своем процессоре. Коммутаторы Ki (i I = 1,2,…,n) обеспечивают полнодоступную коммутацию между процессорами i-го и (i +1) - го каскадов. Имеется также возможность прямой передачи результатов поиска с коммутатора Ki на входы коммутатора Ki + 1 следующего каскада. Отметим, что такой поиск обеспечивает более гибкую коммутацию между процессорными элементами. В этой связи затраты на реализацию поиска будут уменьшаться. Заметим, что такой макроконвейер можно строить не только на уровне алгоритмов, но и на уровне крупных операций, использую принцип «матрешки».
Рис. 13. Схема каскадной реализации бионического поиска
Для управления и реализации процессом совместного поиска автор предлагает ввести следующие модифицированные принципы:
· Принцип целостности. В квантовых, жадных, генетических и бионических алгоритмах значение целевой функции альтернативного решения не сводится к сумме целевых функций частичных решений. Такие алгоритмы будем называть инспирированными природными системами (ИПА).
· Принцип чувствительности к начальным условиям. Результат работы ИПА существенно зависит от представления входных данных исследуемой модели.
· Принцип дополнительности. При принятии решений в неопределенных и нечетких условиях возникает необходимость использования различных несовместимых и взаимодополняющих моделей эволюций и операторов, инспирированных природными системами.
· Принцип неточности. При росте сложности анализируемой задачи уменьшается возможность построения точной модели.
· Принцип управления неопределенностью. При принятии решений в неопределенных и нечетких условиях необходимо вводить различные виды неопределенности в ИПА.
· Принцип соответствия. Язык описания исходной задачи должен соответствовать наличию имеющейся о ней информации.
· Принцип «007». Используй только те входные данные, которые необходимы для решения задачи принятия решений.
· Принцип спонтанного возникновения Пригожина. Инспирированные природными системами алгоритмы позволяют спонтанно генерировать наборы альтернативных решений, среди которых с большой вероятностью может возникнуть оптимальное.
· Принцип разнообразия путей развития. Реализация ИПА многовариантна и альтернативна. Основная задача выбрать путь, приводящий к получению оптимального или квазиоптимального решения.
· Принцип единства и противоположности порядка и хаоса. «Хаос не только разрушителен, но и конструктивен», т.е. в хаосе области допустимых решений обязательно содержится порядок, определяющий искомое решение.
· Принцип совместимости и разделительности. Процессы поиска решений носят поступательный, пульсирующий или комбинированный характер.
· Принцип иерархичности. Инспирированные природными системами алгоритмы могут надстраиваться по горизонтали и вертикали (например, сверху вниз и снизу вверх).
· Принцип «Бритвы Оккама». Нежелательно увеличивать сложность архитектуры поиска и ИПА без необходимости.
· Принцип гомеостаза. Инспирированные природными системами алгоритмы конструируются таким образом, чтобы любое полученное альтернативное решение не выходило из области допустимых решений.
Использование данных принципов позволяет строить алгоритмы принятия решений в САПР с локальными оптимумами за полиномиальное время. Сложность алгоритмов имеет в среднем квадратичный порядок.
В четвертом разделе. Проведен синтез алгоритмов принятия решений при разбиении графовых моделей в САПР. При проектировании систем на кристалле важным является дублирование и троирование графовых моделей для учета современных критериев энергосбережения и задержек сигналов при проектировании объектов в наносекундном диапазоне. Основой алгоритмов дублирования и троирования является метод определения точек сочленения в графовых моделях. Приведем алгоритм определения точек сочленения и блоков.
Подобные документы
Человеко-машинные комплексы, специально предназначенные для принятия решений. Процесс принятия решений и его этапы. Методы поиска новых вариантов решений: дерево решений, морфологические таблицы, конференции идей. Принцип математической оценки тенденций.
курсовая работа [272,1 K], добавлен 30.07.2009Классификация задач системы поддержки принятия решений, их типы и принципы реализации при помощи программы "Выбор". Обзор современных систем автоматизированного проектирования "Компас", "AutoCad", "SolidWorks", оценка преимуществ и недостатков программ.
курсовая работа [1,4 M], добавлен 22.07.2014Реализация интерфейса пользователя для инструментального средства, обеспечивающего работу с таблицами принятия решений, встроенными в систему управления базами данных Oracle. Составление таблиц принятия решений и архитектуры инструментального средства.
курсовая работа [1,8 M], добавлен 18.07.2014Классификация методов анализа по группам. Сбор и хранение необходимой для принятия решений информации. Подготовка результатов оперативного и интеллектуального анализа для эффективного их восприятия потребителями и принятия на её основе адекватных решений.
контрольная работа [93,2 K], добавлен 15.02.2010Классификация систем поддержки принятия решений. Сравнительный анализ методик для оценки рисков розничного кредитования. Структура системы поддержки принятия решений, формирование начальной базы знаний. Проектирование базы данных информационной системы.
дипломная работа [1,9 M], добавлен 10.07.2017Обслуживание двух встречных потоков информации. Структура информационных систем. Разработка структуры базы данных. Режимы работы с базами данных. Четыре основных компонента системы поддержки принятия решений. Выбор системы управления баз данных.
курсовая работа [772,0 K], добавлен 21.04.2016Выбор и анализ языка программирования для проектирования системы автоматизированного поиска по таблицам. Ввод в теории поиска и принятия решений. Роль формальных методов при решении практических проблем выбора. Средства ввода и корректировки таблиц.
отчет по практике [53,0 K], добавлен 12.05.2015Разработка алгоритмического и программного обеспечения для решения задачи поддержки принятия решений о выпуске новой продукции. Математическое обеспечение задачи поддержки принятия решений о выпуске новой продукции, основные входные и выходные данные.
дипломная работа [943,0 K], добавлен 08.03.2011Методы решения проблем, возникающих на стадиях и этапах процесса принятия решений, их реализация в информационных системах поддержки принятия решений (СППР). Назначение СППР, история их эволюции и характеристика. Основные типы СППР, области их применения.
реферат [389,3 K], добавлен 22.11.2016Разработка программного средства для поиска альтернативных решений многокритериальных задач. Проектирование программного средства с помощью объектно-ориентированного подхода. Пример листинга программного кода. Особенности работы программы на примере.
контрольная работа [346,5 K], добавлен 11.06.2011
