WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

 

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

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

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

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

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

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

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

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

Автореферат

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

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

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

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

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

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

       

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

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

               

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

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

               

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

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

               

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

Защита диссертации состоится «_25_» ноября 2010г. в 1420 на заседании диссертационного совета Д 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) - использование интеллектуального анализа извлечения знаний. «Выживание сильнейших» - то есть выбор оптимальных решений в процессе моделирования эволюции.

Сформулируем постановку задачи исследований. Обозначим вектором φ = {φ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. Упрощенная схема взаимодействия САПР и СППР

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

Укрупненная структура ИСППР в САПР по аналогии с другими интеллектуальными системами состоит из четырех подсистем: адаптивной; интерактивной; обрабатывающей; подсистемы управления и блока «внешняя среда» (рис.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. Согласно произвольному генетическому алгоритму для каждого элемента Xj∈P определяется целевая функция (функция приспособленности). Далее согласно целевой функции (ЦФ) производится отбор элементов для реализации генетического поиска.

Рис.8. Схема алгоритма на основе модифицированной  модели ЭШ.

Он состоит из последовательной, параллельной или комбинированной реализации генетических операторов (ГО). На основе решетки Шмальгаузена построен новый оператор кроссинговера (ОК).

Начальную популяцию особей (хромосом, альтернативных решений), предлагается создавать таким образом, чтобы ее размер был кратным 8. Далее исходная популяция разбивается на ряд подпопуляций        P = {P1, P2,…, Pn}, при этом строится две решетки (рис.9).

Рис.9. Пример работы ЭШ на двух решетках

Причем |Pi|=8, i ∈ 1,2,…,n. n ≡(mod 2) т.е. четное и обязательно делится на 8. Это сделано для того, чтобы каждый раз иметь возможность строить трехмерные решетки Шмальгаузена.

Произведем ранжирование исходной популяции по значению целевой функции. Далее начинаем реализовать параллельную микроэволюцию внутри каждого куба. Процесс реализации ОК продолжается, пока не будет достигнут критерий остановки. Основными критериями останова алгоритма являются следующие: время (ЦФ1), выполнение всех итераций ГА (ЦФ2), попадание в локальный оптимум (ЦФ3), получение заданного результата, если он известен (ЦФ4). Построим аддитивный обобщенный критерий:

K = ЦФ1λ1+ ЦФ2λ2+ ЦФ3λ3+ ЦФ4λ4, причем λ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. Алфавит – перечень элементарных символов системы: двоичный, десятичный, буквенный, Фибоначчи и др.
    2. Правила образования (синтаксис), по которым из элементарных символов строятся формулы теории БА: построение моделей эволюций; конструирования популяций; построения ЦФ; разработки новых и модифицированных генетических операторов; репродукции популяций; рекомбинации популяций; редукции; адаптации; выбор структуры генетических алгоритмов; построение комбинированных генетических, биоинспированных и квантовых алгоритмов проектирования.

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

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

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». Используй только те входные данные, которые необходимы для решения задачи принятия решений.
  • Принцип спонтанного возникновения Пригожина. Инспирированные природными системами алгоритмы позволяют спонтанно генерировать наборы альтернативных решений, среди которых  с большой вероятностью может возникнуть оптимальное.
  • Принцип разнообразия путей развития. Реализация ИПА многовариантна и альтернативна. Основная задача выбрать путь, приводящий к получению оптимального или квазиоптимального решения.
  • Принцип единства и противоположности порядка и хаоса. «Хаос не только разрушителен, но и конструктивен», т.е. в хаосе области допустимых решений обязательно содержится порядок, определяющий искомое решение.
  • Принцип совместимости и разделительности. Процессы поиска решений носят поступательный, пульсирующий или комбинированный характер.
  • Принцип иерархичности. Инспирированные природными системами алгоритмы могут надстраиваться по горизонтали и вертикали (например, сверху вниз и снизу вверх).
  • Принцип «Бритвы Оккама». Нежелательно увеличивать сложность архитектуры поиска  и  ИПА без необходимости.
  • Принцип гомеостаза. Инспирированные природными системами алгоритмы конструируются таким образом, чтобы любое полученное альтернативное решение не выходило из области допустимых решений.

Использование данных принципов позволяет строить алгоритмы принятия решений в САПР с локальными оптимумами за полиномиальное время. Сложность алгоритмов имеет в среднем квадратичный порядок.

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

  1. Анализируем поочередно все вершины графа xi∈X, i=1,2,…,n,  удаляя одну за другой вершины с инцидентными ребрами.
  2. Просматриваем поочередно полученные подграфы и проверяем получение компонент связности. В результате получаем все точки сочленения G.
  3. Образуем систему строк. Каждая строка соответствует точке сочленения. Причем в эти строки добавлены индексы соответствующих точек сочленения.
  4. Выполняем операцию пересечения строк первой со второй, третьей с  суммарным результатом пересечения первой и второй строк и т. д. В результате получим все блоки графа и точки сочленения.
  5. Конец работы алгоритма.

В работе рассмотрены новые комбинированные подходы для размещения вершин графовых моделей систем на кристалле. Задача размещения сводится к отображению заданного графа-модели схемы в решетку таким образом, чтобы множество вершин , , графа размещалось в узлах решетки, число которых конечно, а также соблюдался интегрированный критерий, представляющий собой интегрированную целевую функцию (ЦФ). Требование оптимизации: весовая функция должна быть наименьшей для всевозможных способов отождествления вершин графа и узлов решетки. Здесь предлагается каждое альтернативное решение (хромосому) представлять в виде строки переменной длины. Вместо того, чтобы определять хромосому как последовательность битов, ее, подобно естественной копии, будем определять как последовательность генов.

На рис.14 приведена упрощенная схема комбинированного поиска при решении задачи размещения. Здесь ИПА – алгоритмы, инспирированные природными системами, AC – модифицированный алгоритм Ant Colony, БА, ГА, ЖА, КА и МО – бионический, генетический, жадный, квантовый и моделирования отжига алгоритмы размещения, оператор редукции корректирует размер популяции альтернативных решений, ЭС – экспертная система, определяющая дальнейший ход поиска. ИПА представляет собой кортеж: ИПА = <AC, БА,ГА, ЖА,КА,МО,ОР, критерии останова>.

Рис.14. Архитектура комбинированного поиска

Для «борьбы с проклятием размерности» при переходе на проектирование изделий на кристалле в нанометровом диапазоне необходимо использовать технологию распараллеливания алгоритмов. Предлагается модифицированная стратегия распараллеливания на основе ИПА. Используется понятие «грубого» и «точного» параллелизма. В первом случае на основе клиент–серверной модели происходят соединения с серверами (в частном случае персональными компьютерами), где последовательно выполняются блоки алгоритма размещения. Во втором случае точными методами реализуется отдельные блоки алгоритма. Процесс размещения фрагментов БИС графовой модели коммутационной схемы при параллельном размещении будет осуществлен в 7 этапов: анализ, препроцессинг (построение начальной популяции), генетическое, бионическое, жадное и квантовое размещение, постпроцессинг.

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

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

Основными инвариантами графовой модели в САПР являются числа: цикломатическое, хроматическое, внешней и внутренней устойчивости, клик, полноты, ядер, планарности и т.д. Графовые деревья описывают модель неструктурированных знаний. В таких моделях важным является нахождение инвариантов. Инвариант графа G=(X,U), где |X|=n, а |U|=m, это число, связанное с G, которое принимает одно и то же значение на любом графе, изоморфном G. При определении клик графа найдем частичные решения, для каждой вершины графа рекурсивно расширяя “хорошие” решения и устраняя тупиковые решения.

       Приведем описание алгоритма стандартной операции суперпозиции для определения клик графа и построения независимых подмножеств:

1. Выбирается первое частичное решение.

2. Данное решение последовательно или параллельно склеивается со всеми остальными решениями.

3. В «склеенных» решениях устраняются повторяющиеся вершины.

4. Аналогичные операции проводятся со всеми остальными вершинами, кроме повторяющихся вершин, пока не будет найдено полное решение, в противном случае выбор следующего частичного решения и переход на шаг 2.

5. Конец работы алгоритма.

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

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

  1. Начало.
  2. Ввод исходных данных.
  3. Проверка необходимых условий существования ГЦ в графе.
  4. Анализ математической модели и на его основе построение дерева частичных решений.
  5. Суперпозиция частичных решений на основе жадной стратегии и квантового поиска.
  6. В случае наличия тупиковых решений – последовательный поиск с пошаговым возвращением.
  7. Если набор полных решений построен, то переход к 7, если нет, то к 5.
  8. Лексикографический перебор полных решений и выбор из него оптимального или квазиоптимального решения.
  9. Конец работы алгоритма.

В работе предложены новые идеи определения максимальных паросочетаний в  графовой модели на основе биоинспирированных алгоритмов, позволяющие находить наборы максимальных паросочетаний. Опишем модифицированную эвристику построения максимального паросочетания в двудольном графе. Паросочетанием (ПС) называется подмножество ребер M ⊆ U, не имеющих общих концов. Причем каждое ребро ui∈U смежно одному ребру из М. Также можно сказать, что паросочетание (ПС) - это множество независимых ребер. Максимальное паросочетание (МПС) – это паросочетание М, содержащее максимально возможное число ребер. Приведем эвристику построения МПС на основе анализа специальной матрицы смежности, и построения в ней «параллельных диагоналей». Каждая из таких диагоналей является паросочетанием исследуемого графа. Очевидно, при наличии всех единиц по главной диагонали матрицы - построено максимальное паросочетание. Полученные диагонали можно представить в виде амплитуды. Для дальнейших исследований оракул выберет оптимальную амплитуду и на основе суперпозиции с другими диагоналями будет построено максимальное паросочетание. Исходные данные алгоритма: двудольный граф G=(A,B;U), | A|, | B|, матрица смежности.

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

Сформулируем гипотезу. Главная диагональ матрицы R, полностью заполненная элементами, соответствует МПС. Суммарное число единиц соответствует суммарному числу ребер МПС. Каждая единица главной диагонали определяет ребро МПС. Доказательство следует из способа построения специальной матрицы по заданному двудольному графу, т.к. каждой вершине из X1 главной диагонали ставится в соответствие одна и только одна вершина из X2. Отметим, что перед работой алгоритма необходимо упорядочить вершины двудольного графа по возрастанию элементов. На основе этой гипотезы построен алгоритм определения МПС в двудольном графе.

  1. Определить вершины подмножеств X1 и X2 двудольного графа G.
  2. Упорядочим вершины X1 и X2.
  3. Построить специальную матрицу R и определить в ней главную диагональ.
  4. Если главная диагональ заполнена элементами полностью, то построено МПС и переход к шагу 7. Если нет, то переход к 5.
  5. В матрице R определить все диагонали и выбрать диагональ с наибольшим числом элементов. Если таких диагоналей несколько, то выбирается любая.
  6. Выполняется процедура агрегации и преобразования на основе генетических операторов. В результате строится МПС.
  7. Конец работы алгоритма.

Время работы алгоритма зависит от размера анализируемой матрицы. В задачах на графах размер входа часто измеряется не одним числом, а двумя (число вершин n и число ребер m графа). Время работы разработанных алгоритмов в лучшем случае имеет порядок роста n т.е. О(n).

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

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

Рис.15.  Связь компонентов комплексного подхода выбора эффективного алгоритма

В работе приведена общая структурная схема инструментальной среды СППР на основе ИПА (рис. 16).

Рис. 16. Структурная схема  инструментальной среды СППР на основе ИПА 

Она состоит из следующих частей: блока выбора типа ИПА; блока выбора целевой функции; блок ввода настроек параметров и операторов; блока знаний, содержащей процедурные и декларативные знания о предметной области ПР; блока данных; блока ЭС; блока внешней среды; блока адаптации; блок работы выбранных алгоритмов с учетом настроек; блока выдачи результатов. Опишем теперь результаты экспериментальных исследований и приведем сравнительные количественные и качественные характеристики для всех приведенных задач принятия решений на графовых моделях в САПР. При построении комплекса программ использовались пакеты Borland C++, Builder, Visual C++. Отладка и тестирование проводилось на ЭВМ типа IBM PC c процессором Pentium-IV, с ОЗУ 2Гб. Для адекватного сравнения использовались стандартные оценки по производительности различных систем (бенчмаркам), представленными ведущими фирмами мира.

Эксперименты показали, что не всегда увеличение вероятностей операторов в БА повышает качество найденных решений. Очевидно, что существует определенное значение вероятности операторов, соответствующее оптимальному значению ЦФ.

Проанализируем зависимость времени работы алгоритма и значения ЦФ от числа элементов модели для серии опытов конструкторского проектирования. При этом вероятность всех операторов остается постоянной. Проведем эксперименты на десяти случайно сгенерированных схемах с количеством вершин и рёбер от 500 до 5000. Построим таблицу (см. таблицу 1). В таблице приведены данные для компоновки блоков схем на кристалле. В первом столбце указывается количество элементов схемы. Далее на каждом шаге эксперимента фиксируется значение ЦФ и время работы t. Размер популяции фиксирован и равен количеству элементов рассматриваемой модели, согласно стратегии генерации стартовой популяции. Далее подсчитаем среднее значение ЦФ, а также среднее время работы для каждой схемы.

Таблица 1. Зависимость времени работы алгоритма и значения ЦФ от числа элементов модели.

|X|=|U|

БА, Ni = 400

ЦФср

tср

N зап.

1

2

3

4

5

6

7

8

9

10

500

ЦФ

10

11

10

12

12

10

10

12

10

12

10,9

tраб., с

2,172

2,235

2,172

2,266

2,172

2,204

2,266

2,328

2,406

2,406

2,63

2000

ЦФ

70

69

70

72

67

70

69

74

69

73

70,3

tраб., с

12

8,156

8,203

8,253

10,78

8,297

9,453

8,719

8,156

8,188

9,021

3000

ЦФ

117

115

108

117

114

110

111

114

107

114

112,7

tраб., с

20,74

16,58

17,41

19,17

18,16

16,89

18,22

17,39

19,69

18,36

18,261

4000

ЦФ

160

153

157

153

150

153

157

153

160

158

155,4

tраб., с

30,16

30,03

30,55

32,83

29,79

28,91

29,2

30,66

36,79

28,88

30,78

5000

ЦФ

203

200

196

204

206

203

202

202

194

202

201,2

tраб., с

46,13

46,14

46,11

45,89

45,97

46

46

45,99

45,86

46,69

46,078

Из экспериментов следует, что время решения при компоновке практически линейно зависит от числа элементов. При этом временная сложность алгоритмов (ВСА), полученная на основе экспериментов, практически совпадает с теоретическими исследованиями, и для рассмотренных тестовых задач компоновки в лучшем случае ВСА ~ O(n).

Опишем исследование бионического алгоритма размещения.

В качестве изменяемых параметров выступают вероятности операторов, численность общей популяции, число итераций поиска. После нескольких запусков алгоритма получаем окончательное размещение. Графики работы бионического алгоритма размещения показаны на рис.17,18.

Рис.17. График зависимости времени решения от числа элементов

Рис.18. График зависимости значения ЦФ от числа итераций

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

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

В приложении даны копии актов использования и внедрения.

Заключение

    1. Проведен анализ и классификация систем поддержки принятия решений. Сформулирована постановка задачи принятия решений в САПР. Приведено описание новой модифицированной интеллектуальной системы поддержки принятия решений. Основное преимущество заключается в использовании интегрированной целевой функции, трехуровнего моделирования и взаимодействия с внешней средой.
    2. Описаны и проанализированы модифицированные методы вывода и поиска решений в продукционных системах на фреймах и семантических сетях. Это позволяет построить иерархическую систему вывода, действующую по принципу «матрешки». Показана связь между механизмами принятия решений и генетическими алгоритмами. Это позволяет применить теорию эволюционного моделирования и бионических алгоритмов для построения эффективных систем поддержки принятия решений в САПР.
    3. Предложено использование динамических экспертных систем в СППР. Это сделано для введения ЛПР в систему обратной связи с внешней средой. Такой механизм позволяет частично принимать решение в реальном масштабе времени при проектировании.
    4. Разработаны структурные схемы модифицированных моделей эволюции, на их основе построены архитектуры поиска при принятии решений в САПР. Это позволяет строить алгоритмы принятия решений с локальными оптимумами за полиномиальное время.
    5. Построена новая модель эволюции Шмальгаузена, и на ее основе разработан генетический алгоритм. Он эффективно используется для решения оптимизационных задач проектирования. Преимуществом эволюции Шмальгаузена является моделирование части этапов микроэволюции и макроэволюции, и использование ее для повышения качества принятия решений.
    6. Разработаны новые архитектуры решения задач принятия решений на основе алгоритмов, инспирированных природными системами. Это позволяет расширить область поиска данных без увеличения времени работы и сократить преждевременную сходимость алгоритмов, повысить эффективность и качество получаемых решений при проектировании.
    7. Проведен синтез алгоритмов принятия решений при  компоновке блоков (разбиении графовых моделей). Это позволяет повысить качество проектирования и сократить временные затраты при принятии решений.
    8. Разработаны новые комбинированные подходы на основе алгоритмов проектирования, инспирированных природными системами, для размещения  стандартных блоков (вершин графовых моделей) систем на кристалле. Сформулированы новые критерии поиска. Это позволяет проектировать микро- и наносистемы с учетом комплексных критериев.
    9. Построены бионические, квантовые и комплексные алгоритмы определения таких инвариантов графовой модели принятия решений, как независимые и доминирующие множества. Это позволяет определять эффективные стандартные блоки при проектировании систем на кристалле. Разработаны квантовые алгоритмы раскраски, построения клик, гамильтоновых циклов и независимых множеств на основе графовых моделей. Это позволяет создавать новую архитектуру проектирования на основе комбинированных алгоритмов.
    10. Построены новые алгоритмы определения максимальных паросочетаний в графовой модели на основе биоинспирированных алгоритмов, позволяющие находить наборы максимальных паросочетаний в двудольных графах. Время работы в наилучших случаях имеет порядок роста O(n), где n – число вершин графа.        
    11. Реализация биоинспирированных алгоритмов при решении задач САПР показала преимущество по сравнению со стандартными тестовыми методами. Управление процессом бионического поиска при проектировании позволяет находить оптимальные параметры. Из приведенных статистических данных следует, что в общем случае время решения линейно зависит от количества генераций, и временная сложность алгоритмов ориентировочно составляет O((nlogn) - (n3)).
    12. Анализ экспериментов позволяет отметить, что бионические алгоритмы требуют больших затрат времени, но позволяют получать набор локально-оптимальных решений и, в частном случае, оптимальных решений. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов оптимизационных задач проектирования и их поведение для графов различной структуры. Проведенные комплексные исследования показали улучшение работы предложенных комплексных алгоритмов бионического поиска по сравнению с известными методами. Улучшение составило по качеству от 15% до 40%, а по времени от 10% до 25% в зависимости от вида оптимизационных задач.

Основные результаты диссертации опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

  1. Курейчик В.В., Курейчик В.М., Сороколетов П.В. Анализ и обзор моделей эволюции. Известия РАН. Теория и системы управления, 2007, №5. С. 114-126.
  2. Курейчик В.В., Сороколетов П.В. Новые структуры генетических операторов. Известия высших учебных заведений. Электромеханика, 2006г. №5 С.41 – 44.
  3. Курейчик В.В., Сороколетов П.В. Принятие решений в неопределенных условиях в задачах проектирования радиоэлектронной аппаратуры. Известия высших учебных заведений. Северо-Кавказский регион. Технические науки, 2007, №1. С. 19-24.
  4. Курейчик В.В., Сороколетов П.В. Новая технология квантового поиска. Известия высших учебных заведений. Электромеханика, 2007, №3. С. 48-52.
  5. Курейчик В.В., Сороколетов П.В., Хабарова И.В. Инструментальная среда эволюционного моделирования. Программные продукты и системы, 2006. № 4. С. 1-2.
  6. Курейчик В.В., Сороколетов П.В. Генетический поиск при построении связывающих деревьев. Программные продукты и системы, 2007. № 4. С. 31-32.
  7. Сороколетов П.В. Генетические операторы мутации на основе чисел Фибоначчи Известия ТРТУ, №3, 2004. С.197-198.
  8. Курейчик В.В., Сороколетов П.В. Композитные бионические алгоритмы в компоновке блоков. Известия ТРТУ, 2006. №8(63). С. 41 – 46.
  9. Сороколетов П.В. Извлечение экспертных знаний в ИСАПР. Известия ТРТУ, 2006. №8(63). С. 36 – 41.
  10. Курейчик В.В., Сороколетов П.В. О построении интеллектуальных систем поддержки принятия решений. Известия ТРТУ, 2006-2007гг. №9 С. 97 – 100.
  11. Сороколетов П.В. К вопросу построения динамических экспертных систем. Известия ТРТУ, 2007, №1(73). С. 32 –  35.
  12. Балюк Л.Б., Курейчик В.В., Сороколетов П.В. Перспективная технология интегрированного поиска в САПР. Известия ЮФУ. Технические науки, 2007, №2(77). С. 18 – 25.
  13. Гречин И.В., Сороколетов П.В. Проектирование вычислительного комплекса для принятия решений. Известия ЮФУ. Технические науки, 2007, №2(77). С. 191 – 195.
  14. Курейчик В.В., Сороколетов П.В. Математические модели эволюции в САПР. Известия ЮФУ. Технические науки, 2008, №4(81). С. 12-16.
  15. Сороколетов П.В. Принципы и нечеткие алгоритмы анализа моделей принятия решений. Известия ЮФУ. Технические науки, 2008, №4(81). С. 111-115.
  16. Курейчик В.В., Сороколетов П.В. Концептуальная модель представления решений в генетических алгоритмах. Известия ЮФУ. Технические науки, 2008, №9(86). С. 7-12.
  17. Курейчик В.В., Сороколетов П.В., Щеглов С.Н. Анализ современного состояния автоматизированных систем приобретения и представления знаний. Известия ЮФУ. Технические науки, 2008, №9(86). С. 120-125.
  18. Сороколетов П.В. Построение интеллектуальных систем поддержки принятия решений. Известия ЮФУ. Технические науки, 2009, № 4 (93), С. 117-124.
  19. Зубакин В.А., Сороколетов П.В. Когнитивный подход к решению проблемы сопоставимости в системах управления комплексными рисками. М.: Экономика природопользования, №1,  2006. С. 83-88.

Монографии

  1. Гладков Л.А., Курейчик В.В., Курейчик В.М., Сороколетов П.В. Биоинспирированные методы в оптимизации. –М.: Физматлит, 2009. – 384 с.
  2. Курейчик В.В.,. Сороколетов П.В. Композитные методы разбиения графовых моделей. -Таганрог: Изд-во ТРТУ, 2006 – 140с.
  3. Гречин И.В., Курейчик В.В.,. Курейчик В.М, Сороколетов П.В. Элементы динамических экспертных систем. -Таганрог: Изд-во ТРТУ, 2007 – 123с.
  4. Коляда А.В., Курейчик В.В., Курейчик В.М., Лебедев Б.К., Лебедев О.Б., Неупокоева Н.В., Сороколетов П.В. Разработка методов и алгоритмов принятия решений при проектировании на основе квантовых вычислений. - Таганрог: Изд-во ТТИ ЮФУ, 2007. – 162 с.
  5. Курейчик В.В., Сороколетов П.В., Хабарова И.В. Эволюционные модели с динамическими параметрами. - Таганрог: Изд-во ТТИ ЮФУ,2007, 116 с.
  6. Гладков Л.А, Кравченко Ю.А., Курейчик В.В., Курейчик В.М., Лебедев Б.К., Лебедев О.Б., Нужнов Е.В., Полупанов А.А., Сороколетов П.В. и др. Интеллектуальные системы проектирования СБИС на основе эволюционных методов. - Таганрог: Изд-во ТТИ ЮФУ, 2008.-184 с.
  7. Гладков Л.А., Кравченко Ю.А., Курейчик В.В, Курейчик В.М, Лебедев Б.К., Лебедев В.Б., Лебедев О.Б., Нужнов Е.В., Полупанов А.А., Сороколетов П.В. Разработка бионических методов и алгоритмов поиска оптимальных решений при проектировании.- Таганрог: Изд-во ТТИ ЮФУ, 2008.- 244 с.
  8. Гладков Л.А., Курейчик В.В., Курейчик В.М., Лебедев Б.К., Лебедев В.Б., Лебедев О.Б., Сороколетов П.В. Методы и алгоритмы принятия решений на основе бионического поиска. – Таганрог: изд-во ТТИ ЮФУ, 2009. – 137с.
  9. Бова В.В., Гладков Л.А., Кравченко Ю.А., Курейчик В.В., Курейчик В.М., Нужнов Е.В., Рогозов Ю.И., Свиридов А.С., Сороколетов П.В., Щеглов С.Н. Технологии интеллектуального анализа и извлечения данных на основе принципов эволюционного моделирования. Таганрог: изд-во ТТИ ЮФУ, 2009. – 124с.
  10. Бова В.В., Гладков Л.А., Сороколетов П.В. и др. Модели и методы представления знаний в интеллектуальных системах поддержки принятия решений. Таганрог: изд-во ТТИ ЮФУ, 2010.-114с.

Публикации по теме диссертации в других изданиях

  1. Сороколетов П.В. Мир на пороге четвертой информационной революции: концепция технологии передачи знаний. Информационно-аналитический журнал "Система", М.: Изд-во АФК «Система», №4, 2004. С. 20-24.
  2. Сороколетов П.В. Методы адаптации в задачах компоновки. Перспективные информационные технологии и интеллектуальные системы. -Таганрог, №1 (17), 2004. С.29-32.
  3. Сороколетов П.В. Коммутационные модели блоков ЭВА. Перспективные информационные технологии и интеллектуальные системы.-Таганрог, №2 (18), 2004, С.46-53.
  4. Курейчик В.В., Сороколетов П.В. Использование экспертных систем при построении моделей компоновки блоков. Труды десятой национальной конференции по искусственному интеллекту с международным участием КИИ–2006.- М.: Физматлит, 2006. Т.3. С. 1092 – 1099.
  5. Сороколетов П.В. Анализ, проблемы и состояние моделей представления знаний в системах принятия решений. Перспективные информационные технологии и интеллектуальные системы, Таганрог, №4 (28)/ 2006, – С. 15 – 22.
  6. Сороколетов П.В. Анализ, проблемы и состояние моделей эволюции. Перспективные информационные технологии и интеллектуальные системы, Таганрог, №3 (27), 2006. С 39-48.
  7. Гречин И.В., Сороколетов П.В. К вопросу о построении архитектуры интеллектуальной экспертной системы. Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS’07) и «Интеллектуальные САПР» (CAD-2007).- М.: Физматлит, 2007,. С. 8 – 14.
  8. Курейчик В.В., Сороколетов П.В. Архитектуры и стратегии принятия решений. Сборник трудов международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте». – М.: Физматлит, 2007. Т.2– с.397-406.
  9. Kureichik V.V.,. Kureichik V.M, Sorokoletov P.V. Analysis and a Survey of Evolutionary  Models. Journal of Computer and Systems Sciences International, 2007, Vol.46, №5, pp.779-791.
  10. Курейчик В.В., Сороколетов П.В. Проблемы использования экспертных систем при принятии решений. Интеллектуальные системы. - М.: Физматлит, 2007.- С.131-152.
  11. Курейчик В.В.,.Сороколетов П.В. Структура интегрированной инструментальной подсистемы генетического поиска. Труды Международных научно-технических конференций «Интеллектуальные системы» и «Интеллектуальные САПР». -М.: Физматлит, 2008, Т.1. С. 80-85.
  12. Kureichik V.V., Sorokoletov P.V. Structure of the integrated tool subsystem of genetic search. Proceedings of the International Scientific Conferences “Intelligent Systems” and “Intelligent CAD’s ”. -Moscow: Physmathlit, 2008. vol. 4. pp. 31.
  13. Курейчик В.М., Сороколетов П.В. Модифицированная модель эволюции Шмальгаузена. Перспективные информационные технологии и интеллектуальные системы.- Таганрог, №3-4 (35-36)/ 2008, – С. 1 – 20.
  14. Отчет о НИР по теме: «Разработка интеллектуальных систем проектирования для решения задач разбиения СБИС на основе эволюционных методов». № госрегистрации 01200612017 .- Таганрог, 2007. – 164с.
  15. Сороколетов П.В. Анализ и проблемы построения моделей в задачах принятия решений. Интеллектуальные системы. - М.: Физматлит, 2010.- с.180-191.

Личный вклад диссертанта в работы, опубликованные в соавторстве:

[1,14,21,38,42] - анализ и построение моделей эволюции.

[2,16] – новые алгоритмы построения генетических операторов.

[3,10] - структура интеллектуальных систем поддержки принятия решений.

[4,9,12,22,24,26-28,43] - новые архитектуры интегрированного, бионического и квантового поиска в САПР.

[5,13,40,41] - элементы инструментальной среды и вычислительного комплекса для принятия решений.

[6] - генетический алгоритм построения связывающих деревьев.

[17,29,30] - анализ автоматизированных систем представления знаний.

[19] - когнитивный подход при принятии решений в условиях комплексных рисков.

[23,25,34,37-39] - элементы динамических экспертных систем и алгоритмы при принятии решений.

Соискатель  П.В. Сороколетов 




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.