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

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

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

ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

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

РАЗРАБОТКА И ИССЛЕДОВАНИЕ КОМПОЗИТНЫХ АЛГОРИТМОВ КОМПОНОВКИ БЛОКОВ ЭВА

Специальность: 05.13.12 - системы автоматизации проектирования Автореферат на соискание ученой степени кандидата технических наук

Таганрог - 2004г.

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

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

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

Официальные оппоненты: заслуженный деятель науки РФ,

доктор технических наук, профессор Чернышев Ю.О.

кандидат технических наук, доцент Тарасов В.Б.

Ведущая организация: РОСНИИ информационных технологий и

автоматизации проектирования г. Москва

Зашита состоится «8» октября 2004 г. в 14-30 на заседании диссертационного совета Д 212.259.03 при Таганрогском государственном радиотехническом университете по адресу: 347928, г. Таганрог, пер. Некрасовский 44, ауд.Д-406.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан «25» августа 2004 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Целых А.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Большой вклад в разработку и исследование интеллектуальных САПР внесли В.И. Анисимов, Б.В.Баталов, Д.И.Батищев, A.M. Бершадский, Л.С. Берштейн, Ю.Х. Вермишев, Г.Г. Казенов, В.П.Корячко, В.М. Курейчик, Н.Я. Матюхин, А.Н.Мелихов, И.П. Норенков, Г.Г. Рябов, В.А. Селютин, Ш. Айкерс, М. Бреуэр, Н. Шервани и многие другие.

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

РОС НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

СЯ«к|( рг ОЭ 209 акт

ЭВА с полиномиальной временной сложностью является актуальной и важной задачей.

Цель диссертационной работы состоит в разработке и исследовании композитных алгоритмов компоновки блоков ЭВА.

Достижение указанной цели предполагает решение следующих основных задач:

• Построение универсальных и специализированных моделей для этапа конструкторского проектирования ЭВА.

• Построение многоуровневых архитектур бионического поиска для компоновки блоков ЭВА.

• Разработка композитных методов и алгоритмов компоновки.

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

Научная новизна работы заключается в решении задач компоновки блоков ЭВА, основанном на композитных методах и алгоритмах, использующих бионические принципы. В работе:

1. Построена многоуровневая архитектура композитных методов разбиения графов на части применительно к компоновке блоков ЭВА.

2. Разработаны новые композитные, бионические и поисковые алгоритмы компоновки, позволяющие получать множество локальных оптимумов.

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

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

Решение поставленных задач позволяет автору защищать следующие новые научные результаты:

1. Многоуровневую архитектуру подсистемы принятия решений при компоновке, основанную на бионических принципах.

2. Модифицированные генетические операторы на основе множества Кантора, дихотомического деления, чисел Фибоначчи и «золотого сечения».

3. Генетические алгоритмы, основанные на «жадных» стратегиях и операторах, позволяющие, в отличие от существующих методов компоновки, находить множество квазиоптимальных решений.

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

Практическая ценность результатов диссертационной работы определяется созданием комплекса алгоритмов компоновки блоков ЭВА, позволяющих использовать разработанные математические модели, стратегии, концепции, принципы, методы и эвристики, отвечающие конкретным задачам управления жизненным циклом продукции. Разработана программная среда для решения задач компоновки. При построении комплекса программ. использовались пакеты Borland C++, Builder, Visual C++. Отладка- и тестирование- проводились на ЭВМ типа IBM PC с процессорами Intel Pentium-IV и AMD Atlon-2500 с ОЗУ объемом 640Мб. Проведенные экспериментальные исследования показали преимущество композитных поисковых и генетических алгоритмов для решения задач компоновки блоков ЭВА по сравнению с известными методами. Время получения лучших результатов компоновки соответствует полиномиальному времени O(nlogn)-O(n2), которое требуют эффективные - итерационные алгоритмы.

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

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

Апробация основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на семинаре "Новая информационная технология и проблемы управления" (г.Москва, 1990г.), VI Всесоюзной научно-технической школы "Интеллектуальные банки данных". (г.Тбилиси, 1990г.), международных научно-технических конференциях «Интеллектуальные САПР» (г.Дивноморск 2002-2004гг.), на международных конференциях «Интеллектуальные системы» (г.Дивноморск, 2003, 2004гг.) и на научных семинарах Северо-Кавказкого Научного Центра Высшей Школы (г. Ростов-на-Дону, Таганрог, 2003,2004г.г.).

Публикации. Результаты диссертации отражены в 9 печатных работах.

Структура и объём диссертационной работы. Диссертационная

работа состоит из введения, четырёх разделов, заключения, списка литературы и приложения. Работа содержит 176 стр., а также 40 рис., список литературы из 112 наименований, 2 стр. приложений и актов об использовании.

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

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

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

Приведена модифицированная постановка задачи разбиения графа в = (X, и), где X представляет множество вершин графа, и - множество ребер на

части B|, В2,..., Bs, такие, что Bt n В2 n... n Bs = 0, и В| и В2 и... и В$ = В, удовлетворяющего трем условиям и ограничениям: (VB¡ е В) (В * 0),

(VB¡, Bj g В) ([B¡ * Bj X¡ n Xj = 0]a[(U¡ n U¡ = U ¡j)v(U¡ n Uj = 0)]), Ú в,. B,\ju,.u,\j X,- x,p,.,|= кы Критерий для разбиения графа G запишется так:

К =jt ¿ t-l 1-1

где Kg - суммарное число связей между частями B¡ и Bj", s - количество частей в разбиении; К - суммарное количество ребер при разбиении графа на части.

Цель разбиения графа- на части заключается в минимизации; суммарного количества внешних ребер К. Оптимизационную задачу разбиения графа на части запишем в виде кортежа длины три: <М, D, К>, где М - пространство решений; D-ограничения, выделяющие -в М область допустимых решений М'сМ; К - критерий оптимизации. Требование оптимизации: Математическая модель оптимизационной задачи

разбиения графа на части состоит из трех составляющих: целевой функции (К), ограничений на число вершин и число частей разбиения.и граничных условий (0<П|, n2,..., n¡,..., п<оо).

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

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

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

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

Компоненты управления Иерархическая база знаний

Подсистема организации кооперативного поведения Знания о принятии решения

глобальные планы и цели

Подсистема планирования Знания о процессах планирования

локальные планы и мели

Компоэитъые алгоритмы Модели внешней среды Фрагменты реализации

\ /

ЭС

Интерфейс с внешним миром

Рис.1. Многоуровневая архитектура композитных методов разбиения графов

Базисная структура композитного генетического алгоритма для решения задач разбиения графа и гиперграфа на части описывается следующим образом:

I. Препроцессор:

1. Реализация поисковых и жадных стратегий для получения

локального оптимума.

II. Реализация генетического алгоритма:

1. Создание начальной популяции альтернативных решений компоновки блоков ЭВА (1=0).

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

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

4. Реализация модифицированных генетических операторов.

5. Если заданный критерий компоновки достигнут, то переход на шаг 10, если нет, то шаг 6.

6. Рекомбинация родителей и потомков для создания новой генерации.

7. Редукция, т.е. приведение размера популяции к заданному виду.

8. Получена новая популяция альтернативных решений. Переход к следующей генерации

III. Постпроцессор

1. Проверка выполнения критерия остановки. Если он не достигнут, то возврат к II.

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

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

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

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

дихотомии (ОКД). Он основан на частичной перестановке элементов родительских альтернативных решений (хромосом) для получения потомков с лучшими значениями целевой функции (ЦФ).

1. Пусть заданы две родительские хромосомы длины Ь.

2. Делим хромосому (отрезок Ь) пополам (при нечетном размере хромосомы в любую часть берется большее ближайшее число генов).

3. Точка разрыва определяет точку ОКД.

4. Получаем две новых хромосомы-потомка.

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

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

Вероятность выживания альтернативного решения с лучшим значением ЦФ после второго и последующих шагов оператора определится по формуле: р,(8) [ОКД]= 1-2/Ы,

где Ь - длина хромосомы. Эффективность метода дихотомии экспоненциально растет с ростом числа хромосом.

Построение оператора мутации Фибоначчи (ОМФ) реализуется за счет аналогичного методу дихотомии механизма перебора точек разрыва. Приведен нечеткий алгоритм построения ОМФ, ориентированный на задачу компоновки. В заданной популяции хромосом выбирается родительская хромосома (альтернативное решение) длины Ь с наименьшим значением ЦФ.

1. В выбранной хромосоме определяем точку разрыва. Она соответствует третьему числу ряда Фибоначчи.

2. Производим реализацию ОМФ и получаем новую хромосому-потомка.

3. Вычисляем значение ЦФ хромосомы-потомка. Если получено решение, удовлетворяющее заданным конструкторским ограничениям на компоновку, то конец работы алгоритма.

4. Далее в качестве точки ОМФ выбираем 4, 5,... числа ряда Фибоначчи и переходим к пункту 3. Алгоритм оканчивает работу по достижению заданного критерия или когда номер числа ряда Фибоначчи

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

Вероятность выживания альтернативного решения с лучшим значением ЦФ после реализации оператора вычисляется по формуле:

р^хомф^ мл,-!.

Остальные модифицированные генетические операторы на основе рассмотренных методов строятся аналогично. Преимущество этих методов состоит в том, что при их использовании увеличивается вероятность «выживания» альтернативных решений с лучшим значением ЦФ, и каждая новая генерация генетических алгоритмов приводит к сокращению интервала неопределенности.

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

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

ВСА = 0(КР2 1оЙ2 Ир), где - размер популяции альтернативных решений.

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

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

Для разбиения графа на части используются идеи построения минимального внешне устойчивого (доминирующего) подмножества.

Рис.2. Структура композитного алгоритма

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

реальная оценка ВСА находится между 0(nlog2n) и О(п').

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

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

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

1. В графе выделить максимальный двудольный подграф.

2. Определить вершины подмножеств двудольного подграфа и упорядочить их.

3. Построить специальную матрицу и определить в ней главную диагональ.

4. Если главная диагональ заполнена элементами полностью, то построено максимальное паросочетание и переход к шагу 8. Если нет, то переход к 5.

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

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

7. Для оставшихся ребер графа на основе случайной эвристики строится дополнительное подмножество и путем объединения с паросочетанием двудольной части определяется максимальное паросочетание графа.

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

В четвертом разделе описана программная среда для решения задач компоновки. При построении комплекса программ использовались пакеты

Borland C+ + , Builder, Visual C+ + . Отладка и тестирование проводились на ЭВМ типа IBM PC с процессорами Intel Pentium-IV и AMD Atlon-2500 с ОЗУ объемом 640Мб.

Проведены экспериментальные исследования по данным алгоритмам на тестовых примерах. Определены сочетания используемых параметров для разработанных алгоритмов. На основе результатов экспериментов для каждого алгоритма- даны рекомендации параметров (размер популяции, вероятности применения генетических операторов, число удаляемых элементов и др.), обеспечивающих возможность получения набора локальных решений. Отмечено, что применение композитного алгоритма для решения задачи нахождения максимального паросочетания в двудольном графе уменьшает время нахождения решения в 2-3 раза по сравнению с алгоритмом поиска решений в графе общего вида. Например, на разбиение композитным алгоритмом тестовой коммутационной модели ЭВА, содержащей 1000 элементов и 3000 связей, на 5 блоков по 200 элементов в каждом, затрачено 161 секунд работы программы и ЦФ ориентировочно равна 220 связям.

Композитные генетические алгоритмы при разбиении графов на части показали преимущество по сравнению с существующими методами. Управление процессом генетического поиска при разбиении позволяет находить оптимальные параметры и повысить качество решений ориентировочно на 10% - 20%.

Заключение

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

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

3. Построена ориентированная на задачу разбиения графа модификация базовой структуры генетического поиска. Разработан алгоритм компоновки блоков ЭВА на основе модифицированной раскраски

графа. Временная сложность алгоритма лежит в пределах полиномиальной зависимости.

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

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

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

7. Проведены экспериментальные исследования по данным алгоритмам на тестовых примерах. На основе результатов экспериментов для каждого алгоритма даны рекомендации параметров (размер популяции, вероятности применения генетических операторов, число удаляемых элементов и др.), обеспечивающих возможность получения набора локально-оптимальных решений за полиномиальное время. Эти результаты на ориентировочно на 10% - 20% лучше, чем полученные существующими алгоритмами.

Список используемых источников

1. Сороколетов П.В. Коммутационные модели блоков ЭВА. Перспективные информационные технологии интеллектуальные системы, №2 (18), 2004, с.46-53.

2. Курейчик В.В., Сороколетов П.В. Эволюционные алгоритмы разбиения графов и гиперграфов. Известия ТРТУ,№3,2004, с.23-32.

3. Сороколетов П.В. Моделирование фреймов на основе функций и механизма сохранения PRTVATE-переменных в языке Clipper. «Разработка и исследование АРМ лингвиста для создания экспертной системы по анализу текстов. Проектирование АРМ лингвиста». Инв. №208, 1.-М.: МФ ЦИПК, 1989.

4. Сороколетов П.В. Спектральные методы для распознавания и классификации символьных объектов. Материалы 2-й конференции по компьютерной лингвистике. Тарту ЭССР, 1989, с.56-58.

5. Сороколетов П.В. Концепция диалоговой системы формализованных процедур извлечения экспертных знаний. Тезисы докладов отраслевого

Р 165 22

семинара "Новая информационная технология и проблемы у правления".-М: ЦНИИатоминформ, 1990, с.78-80.

6. Сороколетов П.В. Модель представления знаний как стереотип мышления инженера знаний - разработчика экспертной системы. Экспертные системы в научных исследованиях, автоматизации проектирования и производства. Материалы II Всесоюзного научно-технического семинара. - М.: МФ ЦИПК, 1990, с. 12-19.

7. Ганночка А.В., Сороколетов П.В. Построение и использование баз знаний в среде СУБД типа ёБЛ8Е. Тезисы докладов VI Всесоюзной научно-технической школы "Интеллектуальные банки данных".-Тбилиси ГССР, 1990, с. 16-18.

8. Сороколетов П.В. Методы адаптации в задачах компоновки. Перспективные информационные технологии интеллектуальные системы, №1 (17), 2004, с.29-32

9. Сороколетов П.В. Генетические операторы мутации на основе чисел Фибоначчи. Известия ТРТУ,№3,2004, с. 197-198.

В работах, опубликованных в соавторстве, автору принадлежат следующие результаты: [2] - принципы и основные идеи построения алгоритмов; [7] - гибридная модель представления знаний, основанная на сочетании фреймового и продукционного подхода.

/П.В. Сороколетов/

ВВЕДЕНИЕ.

1. АНАЛИЗ И СОСТОЯНИЕ ПРОБЛЕМЫ КОМПОНОВКИ БЛОКОВ ЭВА.

1.1 Коммутационные модели блоков ЭВА.

1.2 Постановка задачи компоновки.

1.3 Анализ существующих алгоритмов разбиения графов и гиперграфов на части.

1.4 Выводы.

2. РАЗРАБОТКА ПОИСКОВЫХ МЕТОДОВ КОМПОНОВКИ БЛОКОВ ЭВА.,.

2.1 Использование экспертных систем при построении моделей компоновки блоков.

2.2 Разработка архитектуры, стратегии и принципов компоновки блоков.

2.3 Построение модифицированных генетических операторов.

2.4 Выводы.

3. РАЗРАБОТКА КОМПОЗИТНЫХ АЛГОРИТМОВ КОМПОНОВКИ БЛОКОВ ЭВА.

3.1. Разработка алгоритмов компоновки на основе раскраски графов.

3.2. Построение параллельно-последовательных алгоритмов компоновки на основе определение независимых и доминирующих подмножеств.

3.3. Разработка композитного алгоритма компоновки на основе сжатия и построения паросочетаний графа.

3.4. Выводы.

4. АНАЛИЗ ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ РАЗРАБОТАННЫХ АЛГОРИТМОВ.

4.1. Краткие сведения об инструментальной среде компоновки блоков ЭВА.

4.2. Цель и средства экспериментальных исследований.

4.3. Результаты экспериментальных исследований.

4.4. Выводы.

В настоящее время создание комплексных систем поддержки жизненного цикла изделий определяется прогрессом науки и техники. Основой таких систем являются подсистемы компьютерного интегрированного производства (КИП). В компьютерные системы для автоматизации жизненного цикла продукции включаются системы автоматизации проектирования (CAIIP(CAD)), автоматизированные системы технологической подготовки производства (АСТПП(САМ)), автоматизированные системы управления технологическими процессами (АСУТП(САЕ)). Воплощением концепции информационной поддержки жизненного цикла изделий являются CALS- технологии [1-5]. Стратегией CALS-технологий является создание единого информационного пространства для всех составляющих жизненного цикла изделий, включая пользователя как элемент внешней среды. CALS-технологии позволяют композитно решать проблемы проектирования, конструирования, технологии изготовления и обеспечения качества продукции. В общей проблеме КИП важное место отводится САПР [6-14]. В настоящее время перспективными являются разработки интеллектуальных САПР, способных обучаться в процессе проектирования и принимать решение в неопределенных и нечетких условиях.

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

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

Большой вклад в разработку и исследование ИСАПР внесли В.И. Анисимов, Б.В.Баталов, Д.И.Батищев, A.M. Бершадский, JI.C. Берштейн, Ю.Х. Вермишев, В.М. Глушков, Ж.Н.Зайцева, Г.Г. Казенов, В.П.Корячко, В.М. Курейчик, Н.Я. Матюхин, А.Н.Мелихов, А.И. Петренко, И.П. Норенков, Г.Г. Рябов, В.А. Селютин, Ш. Айкерс, М. Бреуэр, Н. Шервани и многие другие.

На этапе конструкторского проектирования решаются задачи компоновки блоков, размещения, трассировки и верификации [6-20].

Решение задачи компоновки определяет качество и эффективность всего процесса конструкторского проектирования. Известно, что ЭВА, РЭА и т.п. строится по блочному принципу. В связи с этим в конструкциях ЭВА выделяют ряд структурных иерархических уровней. Элементы структурных уровней называют конструктивными модулями или блоками. Например, на этапе конструкторского проектирования ЭВА выделяют пять уровней: интегральная микросхема, типовой элемент замены (ТЭЗ), панель, блок, стойка, шкаф, вычислительный комплекс. Задачи компоновки на любом уровне тесно связаны между собой и их решение позволяет повысить качество изделий в САПР [7,8,12,14-20]. Задача компоновки состоит в объединении модулей низшего уровня в модули более высокого уровня по заданному критерию или множеству критериев при наличии ограничений и граничных условий.

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

Цель диссертационной работы состоит в разработке и исследовании композитных алгоритмов компоновки блоков ЭВА.

Достижение указанной цели предполагает решение следующих основных задач:

• Построение универсальных и специализированных моделей для этапа конструкторского проектирования ЭВА.

• Построение многоуровневых архитектур бионического поиска для компоновки блоков ЭВА.

• Разработка композитных методов и алгоритмов компоновки.

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

Научная новизна работы заключается в решении задач компоновки блоков ЭВА, основанном на композитных методах и алгоритмах, использующих бионические принципы. В работе:

1. Построена многоуровневая архитектура композитных методов разбиения графов на части применительно к компоновке блоков ЭВА.

2. Разработаны новые композитные, бионические и поисковые алгоритмы компоновки, позволяющие получать множество локальных оптимумов.

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

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

Решение поставленных задач позволяет автору защищать следующие новые научные результаты:

1. Многоуровневую архитектуру подсистемы принятия решений при компоновке, основанную на бионических принципах.

2. Модифицированные генетические операторы на основе множества Кантора, дихотомического деления, чисел Фибоначчи и «золотого сечения».

3. Генетические алгоритмы, основанные на «жадных» стратегиях и операторах, позволяющие, в отличие от существующих методов компоновки, находить множество квазиоптимальных решений.

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

Практическая ценность результатов диссертационной работы определяется созданием комплекса алгоритмов компоновки блоков ЭВА, позволяющих использовать разработанные математические модели, стратегии, концепции, принципы, методы и эвристики, отвечающие конкретным задачам управления жизненным циклом продукции. Разработана программная среда для решения задач компоновки. При построении комплекса программ использовались пакеты Borland С++, Builder, Visual С++. Отладка и тестирование проводились на ЭВМ типа IBM PC с процессорами Intel Pentium-IV и AMD Atlon-2500 с ОЗУ объемом 640Мб. Проведенные экспериментальные исследования показали преимущество композитных поисковых и генетических алгоритмов для решения задач компоновки блоков ЭВА по сравнению с известными методами. Время получения лучших результатов компоновки соответствует полиномиальному времени

0(nlogn)-0(n ), которое требуют эффективные итерационные алгоритмы.

Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском государственном радиотехническом университете: грант РФФИ № 01-0100044 «Эволюционное проектирование с адаптацией»; грант РФФИ на проведение фундаментальных исследований в области технических наук № 02-01-01275 «Разработка теории и принципов эволюционного проектирования на основе многоагентных подходов»; госбюджетная работа по заказу Минобразования РФ «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений».

Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском государственном радиотехническом университете в цикле лекций и практических занятий по курсам «автоматизация конструкторского и технологического проектирования», «CALS- и CASE-технологии», «Методы оптимизации» и «Эволюционное моделирование и генетические алгоритмы».

Апробация основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на семинаре "Новая информационная технология и проблемы управления" (г.Москва, 1990г.), VI Всесоюзной научно-технической школы "Интеллектуальные банки данных". (г.Тбилиси, 1990г.), международных научно-технических конференциях «Интеллектуальные САПР» (г.Дивноморск 2002-2004гг.), на международных конференциях «Интеллектуальные системы» (г.Дивноморск,

2003, 2004гг.) и на научных семинарах Северо-Кавказкого Научного Центра Высшей Школы (г. Ростов-на-Дону, Таганрог, 2003, 2004г.г.).

Публикации. Результаты диссертации отражены в 9 печатных работах.

Структура и объём диссертационной работы. Диссертационная работа состоит из введения, четырёх разделов, заключения, списка литературы и приложения. Работа содержит 176 стр., а также 64 рис., расположенных 34 стр., список литературы из 112 наименований, 2 стр. приложений и актов об использовании.

4.4. Выводы

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

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

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

4. Композитные генетические алгоритмы при разбиении графов на части показали преимущество по сравнению с существующими методами. Управление процессом генетического поиска при разбиении позволяет находить оптимальные параметры и повысить качество решений ориентировочно на 10%. - 20%.

Заключение

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

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

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

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

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

5. Разработан композитный алгоритм реализации стратегии «поиск-эволюция»для разбиения графа. Он использует идеи сжатия графа, построения максимального паросочетания и распаковки графа для получения качественных результатов разбиения за полиномиальное время.

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

7. Композитные генетические алгоритмы при разбиении графов на части показали преимущество по сравнению с существующими методами. Управление процессом генетического поиска при разбиении позволяет находить оптимальные параметры и повысить качество решений ориентировочно на 10%. - 20%.

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

1. Норенков И.П. Принципы построения и структура САПР. М.: Высшаяшкола,

2. Норенков И.П., Кузьмик П.К. Информационная поддержка наукоемкихизделии 3. Колчин986.

3. CALS-технологии. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. А.Ф. и др. Управление жизненным циклом продукции. М.: АнархаСис, 2002.

4. Евгеньев Г.Б. и др. CASE- технология создания многоагентных САПР изделий машиностроения. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 41-46.

5. Грувер М., Зимерс Э. САПР и автоматизация производства. М.: Мир,19$7.

6. Норенков И.П. Основы автоматизированного проектирования. -М.: Изд-во МГТУ имени Н.Э.Баумана, 2000.-360с.

7. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. М.: Энергоатомиздат, 1987.

8. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио и связь, 1990.

9. Норенков И.П., Маничев В.Б. САПР ЭВА. М.: Высшая школа, 1983.

10. Гридин В.Н. Теоретические основы построения базовых адаптируемыхкомпонентов САПР МЭА. М.: Наука, 1989.

11. Вермишев Ю.Х. Основы автоматизированного проектирования. М.:1. Радио и связь, 1988.

12. Sherwani Naveed. Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Boston/Dordrecht/London, 1995.

13. Малышев Н.Г., Мицук H.B. Основы оптимального управления процессами автоматизированного проектирования. М.: Энергоатомиздат,

14. Морозов К.К. и др. Методы разбиения схем РЭА на конструктивно законченные части. М.: Советское радио, 1978.

15. Справочник конструктора РЭА. Общие принципы конструирования. Под ред. Р.Г. Варламова. М.: Советское радио, 1980.

16. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированноепроектирование конструкций РЭА. М.: Радио и связь, 1983.

17. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. Саратов: Изд-во СГУ, 1993.

18. Петухов Г.А., Смолич Г.Г., Юлин Б.И. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом. М.: Радио и связь, 1987.

19. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.

20. Автоматизация проектирования БИС. В 6 кн. Под ред. Г.Г. Казеннова. М.: Высшая школа, 1990.

21. Кормен Т., Лейзерсон И., Ривест Р. Алгоритмы: построения и анализ. М.: МЦМО,2000.

22. Панадимитриу X., Стайниц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1983.

23. Гладков Л.А., Курейчик В.В., Курейчик В.М. Основы теории алгоритмов / под ред. В.М. Курейчика. Учебное пособие по курсу «Математическая логика и теория алгоритмов». Таганрог. ТРТУ, 2002.-82с.

24. Харари Ф. Теория графов. М.: Мир, 1977.

25. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

26. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000.

27. Иванов Б.Н. Дискретная математика. М.: Лаборатория базовых знаний, 2001.

28. Зыков А.А. Основы теории графов. М.: Наука, 1987.

29. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. Львов: Вища шк., 1981.

30. Петренко А.И. Тетельбаум А.Я. Модели электронных устройств при решении конструкторских задач. Кибернетика,№2,1978, с.47-54.

31. Глушань В.М. Графовые модели представления вычислительных алгоритмов. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 133-138.

32. Баталов Б.В., Щемелинин В.М. Проектирование топологии интегральных схем на ЭВМ. М.: Машиностроение, 1979.

33. Нильсон Н. Принципы искусственного интеллекта.- М: Радио и связь, 1985. 376 с.

34. Сороколетов П.В. Коммутационные модели блоков ЭВА. Перспективные информационные технологии интеллектуальные системы, №2 (18), 2004, с.46-53.

35. Мелихов А.Н., Берштейн JI.C. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов на-Дону. Изд-во РГУД981.

36. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990.

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

38. Гатчин Ю.А., Коробейников А.Г. Методы представления математических моделей в САПР при концептуальном и инфологическом моделировании. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 35-41.

39. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: Физматлит,2003.

40. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. Воронеж: Изд-во ВГУ, 1997.

41. Курицкий Б.Я. Оптимизация вокруг нас. Л.: Машиностроение, 1989.

42. Алексеев О.В. и др. Автоматизация проектирования радиоэлектронных средств. М.: Высшая школа,2000.

43. Чернышев Ю.О., Яценко О. В. Определение нечеткости в задачах оптимизации функционально распределенных систем обработки данных и подходы к ее решению. IEEE AIS-02, CAD-2002. Интеллектуальные системы, интеллектуальные САПР, М.: Физматлит, 2002, с. 74-78.

44. Курейчик В.В., Курейчик В.М. Перспективные технологии для решения оптимизационных задач. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.1, М.: Физматлит, 2003, с 59-67.

45. Karypis G., Aggarwal R., Kumar V., and Shekhar S. Multilevel hypergraph partitioning: Application in VLSI domain. In Proceedings of the Design and Automation Conference, 1997.

46. Karypis G., Kumar V. A coarse-grain parallel multilevel k-way partitioning algorithm. In Proceedings of the eighth SIAM conference on Parallel Processing for Scientific Computing, 1997.

47. Karypis G., Kumar V. hMETIS 1.5: A hypergraph partitioning package. Technical report, Department of Computer Science, University of Minnesota, 1998. Available on the WWWat URL http://www.cs.umn.edu/.metis.

48. Alpert C.J. et all. Hypergraph Partitioning with Fixed Vertices. -//-V.19, №2, February 2002, pp. 267 271.

49. Wolfe G., Wong J.L. and Potkonjak M.Watermarking Graph Partitioning Solutions. IEEE Transactions on CAD of Integrated Circuits and systems, V. 21, №10, October 2002, pp. 1196 1204.

50. Мак W.K. Mic Cut Partitioning With Functional Replication for Technology - Mapped Circuits Using Minimum Area Over hed. -//-V.21, №4, april 2002, pp. 491 -496.

51. Caldwell A.E., Kahng A.B. and Markov I. L. Optimall Portitioners and End -Case Placers for Standard Cell Layout. -//-V.19, №11, November 2000, pp. 1304- 1313.

52. Kernighan В., Lin S. An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech.J., vol 49, Feb 1970, pp. 291-307.

53. Fiduccia C., Mattheyses R. A linear time heuristics for improving network partitions. Proceedings 19th АСМЛЕЕЕ Design automation conference, 1982, pp. 175-181.

54. Saab. Y. A new effective and efficient multi-level partitioning algorithm. Proceedings Design, Automation and Test in Europe Conference 2000, Paris, France, 27-30 March 2000, pp.112-116.

55. Хакен Г. Тайны природы. М.: Институт компьютерных исследований, 2003.

56. Дарвин Ч. Происхождение видов путем естественного отбора. М.: «Тайдекс Ко», 2003.

57. Эволюционная эпистемология и логика социальных наук: Карл Поппер и его критики// Составление Д.Г. Лахути, В.Н. Садовского, В.К. Финна. М.: Эдиториал УРСС, 2000.

58. Хедрик Ф. Генетика популяций. М.: Техносфера, 2003.

59. Holland John Н., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975.

60. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989.

61. Handbook of Genetic Algorithms. Edited by Lawrence Davis. USA: Van Nostrand Reinhold, New York, 1991.

62. Эволюционные вычисления и генетические алгоритмы. Составители Гудман Э.Д., Коваленко А.П. Обозрение прикладной и промышленной математики. М.: Изд-во ТВП, 1966.

63. Батищев Д.А. Генетические алгоритмы решения экстремальных задач. Воронеж: Изд-во ВГТУ, 1995.

64. Курейчик В.М. Генетические алгоритмы и их применение: Монография. -Таганрог: Изд-во ТРТУ, 2002.

65. Курейчик В.В. Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. -Таганрог: Изд-во ТРТУ, 2001.

66. Курейчик В.М. Генетические алгоритмы. Обзор и состояние. Новости искусственного интеллекта, №3, 1998, с. 14-64.

67. Курейчик В.М. Генетические алгоритмы: Состояние. Проблемы. Перспективы. Теория и системы управления РАН, Москва, N 1, 1999, с. 144-160.

68. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика. РАН, №10, Москва, 2001, стр. 174187.

69. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа// Известия АН. Теория и системы управления, № 5, 1999, с.79-87.

70. Плеханов А.С. Компонентное разбиение в совместном проектировании аппаратно-программных средств на основе масштабируемых моделей IEEE AIS-02, CAD-2002. Интеллектуальные системы, интеллектуальные САПР, М.: Физматлит, 2002, с. 349-350.

71. Курейчик В.В.,Сороколетов П.В. Эволюционные алгоритмы разбиения графов и гиперграфов. Известия ТРТУ,№3, 2004, с.23-32.

72. Смирнова О.В. Модели эволюции в задачах компоновки схем ЭВА. Перспективные информационные технологии интеллектуальные системы, №1 (19), 2002, с.47-49.

73. Frohlich N., Glockel V., Fleischmann J. A new partitioning method for parallel simulation of VLSI circuits on transistor level. Proceedings Design,

74. Automation and Test in Europe Conference, 2000, Paris, France, 27-30 March 2000, pp.679-685.

75. Wei Y.C., Cheng C.K. A two-level two-way partitioning algorithm, Tech. report CH2924-9, University of California, San Diego, IEEE, 1990.

76. Ching-Wei Yeh, Chung-Kuan Cheng, Ting-Ting Y. Lin. A general purpose multiple way partitioning algorithm. Proceedings 28th ACM/IEEE Design Automation Conference, paper 25/1, 1991, pp.421-425.

77. Bui T. N., Moon B. R. Genetic algorithm and graph partitioning, IEEE Trans. Comput., vol.45, 1996, pp. 841-855.

78. Chandrasekharam R., Subhramanian and chadhurys. Genetic algorithms for node partitionaly problem and application in VLSI design. IEEE Proc-E, Vol.140, No.5, September, 1993. pp. 167 178.

79. Kling R.M., Banerjee P.: Placement by Simulated Evolution. IEEE Trans, on CAD, Vol.8, No.3, 1989. pp. 245-256.

80. Kling R.M. and Baneijee P. Empirical and Theoretical Studies of the Simulated Evolution Method applied to standard Cell Placement. IEEE Trans, on CAD, Vol.10, No.10, 1991. pp. 1303-1315.

81. Дубинин Н.П. Избранные труды, T.l. Проблемы гена и эволюции. М.: Наука,2000.

82. Редько В .Г. Эволюционная кибернетика. -М.: Наука, 2001.

83. Попов Э. В. и др. Статические и динамические экспертные системы. М.: Финансы и статистика, 1996.

84. Попов Э.В. Экспертные системы реального времени. Открытые системы №2(10), 1995. http://kiryushin.boom.ru/docs/esrv.htm.

85. Осипов Г.С. Приобретение знаний интеллектуальными системами. М.: Наука, 1997.

86. Микони С.В. Взаимодействие БЗ и системы выбора. Интеллектуальное управление: новые информационные технологии в задачах управления, М.: Наука, 1999,с.68-72.

87. Джексон П. Введение в экспертные системы. М.: Издательский дом «Вильяме», 2001.

88. Дейт К. Введение в системы баз данных (седьмое издание).-М.: Вильяме. 2001.

89. Уотермен О. Руководство по экспертным системам. М.: Мир, 1989.

90. Искусственный интеллект: В 3 кн. Кн. 1. Системы общения и экспертные системы. Справочник / Под ред. Э.В. Попова. М.: Радио и связь, 1990.

91. Искусственный интеллект: В 3 кн. Кн. 2. Модели и методы . Справочник / Под ред. Д.А. Поспелова. М.: Радио и связь, 1990.

92. Тарасов В.Б. Интеллектуальные системы в проектировании. Новости ИИ, №4,1993, с.24-67.

93. Аверкин А.Н. и др. Приобретение и формализация знаний. Искусственный интеллект. М.: Радио и связь, 1990.

94. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. -М.: Эдиториал УРСС, 2002. -352с.

95. Сороколетов П.В. Спектральные методы для распознавания и классификации символьных объектов. Доклады 2-й конференции по компьютерной лингвистике. Тарту ЭССР, 1989, с.56-58.

96. Сороколетов П.В. Концепция диалоговой системы формализованных процедур извлечения экспертных знаний. Тезисы докладов отраслевого семинара "Новая информационная технология и проблемы управления". М.: ЦНИИатоминформ, 1990, с.78-80.

97. Ганночка А.В., Сороколетов П.В. Построение и использование баз знаний в среде СУБД типа dBASE/ЛГезисы докладов VI Всесоюзной научно-технической школы "Интеллектуальные банки данных". 7-8 марта 1990 г., пос. Бакуриани ГССР. Тбилиси, 1990, с.16-18.

98. Kelly G. The Psychology of Personal Constructs. Vols 1 and 2. Norton, New York, 1955.

99. Непейвода H.H. Прикладная логика. Издание 2-е. Новосибирск, изд-во Новосибирского университета, 2000.

100. Luger G. Artificial Intelligence: Structures and Strategies for Complex Problem Solving. Fourth Edition. Addison-Wesley Publishing Company, 2002.

101. Сороколетов П.В. Методы адаптации в задачах компоновки //Перспективные информационные технологии интеллектуальные системы, №1 (17), 2004, с.29-32.

102. Сороколетов П.В. Генетические операторы мутации на основе чисел Фибоначчи. Известия ТРТУ,№3, 2004, с. 197-198.

103. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС. Таганрог, Изд-во ТРТУ, 2000.

104. Берштейн Л.С., Карелин В.П., Целых А.Н. Модели и методы принятия решений в интегрированных ИС. Ростов-на -Дону, изд-во РГУД999.

105. Юб.Комарцова Л.Г., Максимов А.В. Нейрокомпьютеры. М.: Изд-во МГТУ, 2002.

106. Цетлин М.Л. Исследования по теории автоматов и моделирование биологических систем.- М.: Наука, 1969.

107. Курейчик В.М., Мухлаев А.В. Моделирование адаптации в алгоритмах синтеза топологии электронных систем. Программные продукты и системы,№3, 2000, с. 13-16.

108. Нейман Ю. Вводный курс теории вероятностей и математической статистики. М.: Наука, 1968.

109. Хабарова И.В. Разработка среды эволюционного моделирования с динамическими параметрами DYNGEN. // Известия ТРТУ. 2002.№3, с.227.