автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка и исследование генетических алгоритмов типизации элементов СБИС на основе изоморфного вложения графов

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

СИЛЮТИН Денис Сергеевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ТИПИЗАЦИИ ЭЛЕМЕНТОВ СБИС НА ОСНОВЕ ИЗОМОРФНОГО ВЛОЖЕНИЯ ГРАФОВ

Специальность 05.13.12 — «системы автоматизации проектирования» 05.13.17 - «теоретические основы информатики»

АВТОРЕФЕРАТ

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

Таганрог 2004

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

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

заслуженный деятель науки РФ, д-р техн. наук, проф. В.М. Курейчик

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

заслуженный изобретатель РФ, д-р техн. наук А.В. Маргелов

Официальные оппоненты:

д-р техн. наук, проф. В. П. Карелин,

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

Ведущее предприятие:

Международный научно-технический центр РИА, г. Армавир.

Защита состоится "_2 " июля 2004 г. В 14° часов на заседании диссертационного совета Д 212.259.03 по защите диссертаций при Таганрогском Государственном Радиотехническом Университете по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406

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

Автореферат разослан " 30

мая

2004 г.

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

А. Н. Целых

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

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

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

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

Задача распознавания изоморфного вложения графов является NP-полной, и, как следствие, невозможна разработка алгоритма, позволяющего находить точное оптимальное решение за приемлемое время. Поэтому с точки зрения повышения эффективности САПР, представляет интерес разработка новых алгоритмов и методов проектирования, для NP-полных задач. К таковым можно отнести методы эволюционного моделирования, которые были разработаны, как новое направление, в начале 1970 гг., но только сейчас имеют приоритет в отношении других методов. Значительный вклад в области эволюционного моделирования внесли: Goldberg D.E., Holland J.H., Батищев Д.И., Букатова И.Л., Курейчик В.М. и многие другие ученые.

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

Целью диссертационной работы является разработка и исследование методов типизации схем СБИС путем распознавания изоморфного вложения графов на основе эволюционного моделирования. Основная задача состоит в разработке алгоритма типизации элементов схем при проектировании СБИС

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

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

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

- проведен анализ задачи типизации и определение ее места в общей задаче конструкторского проектирования СБИС с применением комплексных САПР, а также анализ и обоснование выбора математической модели схемы для разрабатываемого генетического алгоритма типизации на основе распознавания изоморфного вложения графов;

- выполнен анализ принципов и схемы работы генетических алгоритмов, методики кодирования решений, а также основных генетических операторов и их модификаций с точки зрения их пригодности для решения задачи типизации;

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

- разработан многоуровневый генетический алгоритм типизации элементов СБИС на основе генетического алгоритма распознавания изоморфного вложения графов;

- предложена концепция генетического поиска оптимального решения задачи - типизации элементов СБИС на основе агентно-ориентированного подхода;

- разработана структура многоагентной системы генетического поиска оптимального решения задачи типизации элементов СБИС с элементами адаптации на основе обучающейся системы классификаторов;

- выполнено экспериментальное исследование эффективности разработанных алгоритмов распознавания изоморфного вложения графов и типизации элементов СБИС, а также сравнение с известными алгоритмами.

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

Научная новизна диссертационной работы заключается в:

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

- разработке многоуровневого генетического алгоритма типизации элементов СБИС, а также модификации жадного алгоритма локального улучшения целевой функции.

- разработке структуры многоагентной системы управления поиском оптимального решения задачи типизации элементов СБИС на основе

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

Практическую ценность работы представляют:

- генетический алгоритм и программы распознавания изоморфизма и изоморфного вложения графов;

- многоуровневый генетический алгоритм и программа типизации элементов СБИС;

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

- результаты исследований эффективности разработанных алгоритмов.

Реализация результатов работы. Основные теоретические и

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

Основные положения, выносимые на защиту:

- эвристическая процедура инициализации популяции для формирования базового решения;

- модификация жадного алгоритма, локального улучшения ЦФ, учитывающая специфику решаемой задачи;

- концепция применения генетических алгоритмов и общей схемы функционирования многоуровневого алгоритма типизации элементов СБИС на основе распознавания изоморфизма графов;

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

Апробация работы и публикации. Основные теоретические и практические результаты работы представлены на 1У,У Всероссийских научных конференциях с международным участием молодых ученых и аспирантов (г. Таганрог, 2001 - 2002 гг.), Международной конференции «Интеллектуальные САПР» (СЛБ-2002, СЛБ-2003) (г. Геленджик, 2002 -

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

2004 гг.).

По теме диссертации опубликовано 8 печатных работ.

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

приложений. Работа содержит 163 страницы, включая 42 рисунка, 5 таблиц, список использованных источников из 131 наименования, 8 страниц приложений и актов об использовании.

СОДЕРЖАНИЕ РАБОТЫ-

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

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

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

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

1) формирование групп равноинвариантных вершин;

2) проверка на уникальность вершины в хромосоме;

3) проверка на совпадение смежности;

4) проверка уникальности позиции вершины в

хромосоме во всей популяции.

Эффективность работы алгоритмов эволюционного моделирования во многом зависит также и от построения целевой функции. За степень приспособленности ¥(г) (ЦФ) каждой хромосомы г в случае задачи распознавания изоморфного вложения графов можно принять:

(1)

п

где 11 — число вершин изоморфного подграфа О', представленного хромосомой г1; а п-число вершин графа О (количество генов в хромосоме).

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

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

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

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

Глуб:

та поиска

рама кулю?

Вершена ксголкзуетсх?

Рис. 1. Модификация жадного алгоритма локального улучшения ЦФ.

Для решения задачи типизации на

основе

распознавания

изоморфного вложения графов, предлагается следующий многоуровневый генетический алгоритм (рис. 2).

Процедура формирования подграфа Ог (на первом уровне г=0) для сравнения на изоморфизм состоит из следующих этапов(Х0 - множество вершин графа Оисх):

а) образование групп Г равноинвариантных вершин (инвариантными являются веса вершин и их локальная степень);

б) удаление из исходного множества вершин Хг - тех, что образуют группы Г инвариантных вершин единичной мощности;

в) ранжирование оставшихся групп Г по - возрастанию мощности образующих их подмножеств вершин;

г) выбор любой вершины из минимальной (оставшейся после удаления единичных) по мощности группы Г1 вершины и помещение ее в Нисх;

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

Для инициализации начальной популяции и последующей работы алгоритма из исходного множества вершин удаляются вершины аналогично процедуре формирования Ог, а затем и те, что образуют граф Ог. Рассматривая полученное подмножество вершин Хг' как исходное, аналогично к раз выполняется операция заполнения хромосом Н1, Н2, .., Нк, где к - число хромосом в популяции. При этом используются группы Г' образованные вершинами

Расчет ЦФ хромосомы Ц состоит в последовательном сравнении веса и степени вершин, имеющих одинаковое расположение в хромосомах Нисх и Н,. С точки зрения практического применения задачи типизации, существует необходимость проверки наличия смежности для каждой вершины в хромосоме Н1 с любой хотя бы одной, отличной от вершиной в хромосоме Н,.

При этом последовательное сравнение степеней вершин происходит только после совпадения весов в хромосомах Нис„ и Щ и только в случае совпадения и весов и степеней происходит проверка наличия смежности. В случае несовпадения весов .¡-го гена Нип[ с Н; далее сравнение не происходит, что справедливо и при сравнении степеней. Такой метод позволяет сократить временную сложность расчета ЦФ и повысить эффективность ГА.

С учетом выше сказанного, предлагается следующая ЦФ оценки популяции для ГА типизации:

Рис. 2. Многоуровневый генетический алгоритм типизации элементов СБИС.

где w - количество совпавших весов (меток) вершин, р - количество совпавших степеней, количество смежных вершин в хромосоме, a g -количество последовательно соединенных вершин в хромосоме.

Если ЦФ(Н) на некотором шаге ГА равна 1 - это значит, что найдены изоморфные графы, которые являются подграфами исходного графа GHCX и необходимо применение алгоритма достройки Go.

В качестве алгоритма достройки Gr предлагается использовать жадный алгоритм, основанный на применении следующих правил для выбора вершины из Хг" (Хг' за вычетом вершин составляющих Щ):

а) выбрать вершину х, из минимальной неединичной группы Г";

б) вершина х, должна быть смежной с одной из вершин Gr.

Если правило 2 не выполнилось, то рассмотреть следующую по

возрастанию группу Г", иначе правило 1 отбрасывается и делается попытка использовать правило 2 в качестве единственного. Если после этого выполнить правило 2 также не удалось, то дальнейшая достройка Gr невозможна и необходимо проверить следующий критерий останова:

Если Хг образует группы,. Г только единичной мощности, то конец; работы алгоритма, иначе хромосома Н;, представляющая граф изоморфный графу Gr, сохраняется как граф Gr'. Далее из множества вершин Хг убираются вершины, принадлежащие графам Gr' и Gr, что образует множество вершин Хж, которое является исходным для дальнейшего рассмотрения и переход к инициализации новой популяции.

Предложенный алгоритм типизации элементов СБИС позволяет находить приемлемое по качеству решение для большинства практических задач, в виде набора групп изоморфных подграфов, представляющих собой объединение элементов СБИС (простейшие элементы типа И-НЕ, ИЛИ-НЕ -ранг 1) ранга 1 в более крупные элементы ранга 1+1. Что позволяет повысить эффективность алгоритмов комплексных систем автоматизации конструкторского проектирования. При этом для поиска оптимального решения необходимо некоторое количество раз, применять алгоритм, а затем выбрать оптимальное. Это обусловлено тем, что для наращивания используются не все возможные вершины, и, соответственно, часть решений не рассматривается. Так для повышения эффективности алгоритмов компоновки, путем предварительного решения задачи типизации элементов СБИС, при выборе оптимального решения задачи типизации, дополнительно необходимо учитывать критерии оптимальности и ограничения компоновки, такие как:

- число межузловых соединений или внешних выводов на блоках (число соединений между группами изоморфных подграфов);

- задержки в распространении сигналов;

- ограничение на совместную работу модулей (i-l)-гo уровня и.т.д.

В данной работе поиск оптимального решения задачи типизации элементов СБИС осуществляется без учета дополнительных критериев и

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

Теоретическая оценка временной сложности разработанного многоуровневого генетического алгоритма типизации составляет:

где ¡3 - величина, зависящая от числа поколений, длины хромосомы, а также количества уровней алгоритма (запусков алгоритма с уменьшением размерности задачи, в результате формирования групп изоморфных подграфов на предыдущем уровне), п - число вершин в графа, Л/ - размер популяции.

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

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

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

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

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

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

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

1) применение различных методов селекции в алгоритме типизации дает сравнимые по качеству решения;

2) элитизм является эффективным дополнением селекции;

3) применение эвристической процедуры инициализации популяции повышает качество решений задачи типизации;

4) жадный алгоритм локального улучшения ЦФ повышает сходимость алгоритма;

5) средние, значения вероятностей использования генетических операторов, при которых многоуровневый алгоритм типизации работает наиболее эффективно, составляют: 0.78 - для оператора кроссинговера, 0.26 — жадного алгоритма, 0.03 - мутации.

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

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

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

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

В приложении приводятся акты об использовании результатов диссертационной работы

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

3) На основе генетического алгоритма распознавания изоморфного вложения графов разработан; многоуровневый генетический алгоритм типизации элементов СБИС.

4) Разработана структура многоагентной системы управления поиском оптимального решения задачи типизации элементов СБИС на основе многоуровневого генетического алгоритма типизации, состоящая из интеллектуального агента-координатора, множества поисковых агентов и адаптационного агента.

5) Разработан механизм адаптации многоагентной системы управления генетическим поиском оптимального решения задачи типизации элементов СБИС на основе обучающейся системы классификаторов.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Курейчик В.М., Силютин Д.С. Система генетических алгоритмов определения изоморфизма графов и гиперграфов // IV Всероссийская научная конференция с международным участием молодых ученых и аспирантов. Тезисы докладов. Таганрог: Изд - во ТРТУ, 2001. С. 94-95

2. Силютин Д.С. Алгоритм определения изоморфизма графов // Труды Международных конференций «Искусственные интеллектуальные системы»(1ЕЕЕ Л18'02) и «Интеллектуальные САПР» (СЛБ-2002). Научное издание.-М.: Издательство Физматлит, 2002. С. 389-394.

3. Силютин Д.С. Алгоритм определения изоморфизма графов, основанный на использовании чисел смежности с подмножествами // V Всероссийская научная конференция с международным участием молодых

<М- 1 38 36

ученых и аспирантов. Тезисы докладов. - Таганрог: Изд - во ТРТУ, 2002.С. 90-92

4. Силютин Д.С. Применение многоагентных технологий в организации генетического поиска изоморфной подстановки // Перспективные информационные технологии и интеллектуальные системы. 2003 №2(14), С. 48-54, http://pitis.tsure.ru/filesl4/l l.pdf.

5. Denis S. Silyutin. Genetic search of graph isomorphism controlled by multi-agent system // Proceedings of the International Scientifics Conferences "Intellegent Systems (IEEE AIS'03)" and "Intellegent CADS(CAD-2003)". Scientific publications in 3 volumes 2003. P. 202.

6. Силютин Д.С. Специфика организации генетического поиска изоморфной подстановки графов // Перспективные информационные технологии и интеллектуальные системы. 2003 №4(16), С. 100-103, http://pitis.tsure.ru/filesl6/14.pdf.

7. Силютин Д.С. Многоагентная система управления ГП изоморфной подстановки // Труды Международных конференций «Искусственные интеллектуальные системы»(1ЕЕЕ AIS'03) и «Интеллектуальные САПР» (CAD-2003). Научное издание.-М.: Издательство Физматлит, 2003. С. 457463.

8. Силютин Д.С. Агентно-ориентированый подход к управлению генетическим поиском подстановки изоморфизма графов// Известия ТРТУ №2. Тематический выпуск «Материалы Всероссийской научно-технической конференции с участием зарубежных представителей «Интеллектуальные САПР». - Таганрог: Изд - во ТРТУ, 2003. С. 134-139.

Личный вклад автора в работе [1], опубликованной в соавторстве -предложена система алгоритмов определения изоморфизма графов.

Соискатель Силютин Д.С.

ВВЕДЕНИЕ.

1. АНАЛИЗ АЛГОРИТМОВ ТИПИЗАЦИИ ЭЛЕМЕНТОВ СБИС.

1.1 Постановка и анализ задачи типизации элементов СБИС.

1.2 Анализ и выбор математических моделей схем для задачи типизации

1.3 Постановка и анализ задачи типизации элементов СБИС на основе распознавания изоморфного вложения графов.

1.4 Обзор существующих алгоритмов распознавания изоморфного вложения графов.

1.5 Генетические алгоритмы как метод повышения эффективности алгоритмов распознавания изоморфного вложения графов.

1.5.1 Символьная модель.

1.5.2 Стратегии селекции и рекомбинации.

1.5.3 Основные генетические операторы.

1.5.4 Модели генетических алгоритмов.

1.5.5 Общая схема генетического алгоритма.

При создании современной электронной аппаратуры большое значение приобретают эффективные методы автоматизированного проектирования, которые позволяют создавать высоконадёжные СБИС в короткие сроки и при сравнительно низких затратах. Тенденция к росту степени интеграции СБИС приводит к существенному увеличению трудоёмкости проектирования, что вызывается ростом размерности решаемых при проектировании задач [1-5].

Производство интегральных схем разбивается на три этапа: проектирование, изготовление, тестирование. В виду значительной сложности ни один из этих этапов не может быть выполнен без средств автоматизированного проектирования [2, 6].

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

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

В настоящее время при создании и анализе структурных математических моделей схем используется аппарат теории графов. Это дает возможность строить математически обоснованные алгоритмы проектирования, находить простые и высококачественные решения, рационально и эффективно использовать ЭВМ [8, 9]. В качестве математических моделей схем используют специальные графы и гиперграфы, позволяющие адекватно отражать набор отношений, характерных для элементов СБИС [10-14]. Использование гиперграфов позволяет более точно и компактно описывать проектируемую схему, а также строить эффективные локально-оптимальные и точные алгоритмы решения исследуемых задач. Выбор математической модели для задачи типизации, когда требуется выделение изоморфных подграфов в моделирующем графе, зависит от размерности задачи.

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

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

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

Основная особенность ГА состоит в том, что анализируется не одно решение, а некоторое подмножество квазиоптимальных решений, называемых "хромосомами" или стрингами. Это подмножество носит название "популяция". Для каждой хромосомы должна быть вычислена целевая функция F{ri), называемая эволюционной, где п - число элементов в хромосоме. Такие функции вычисляют относительный вес каждой хромосомы в популяции. В каждой популяции хромосомы могут подвергаться действиям различных операторов. При этом происходят процессы, аналогичные действиям, которые имеют место в естественной генетике. К основным операторам относят: кроссинговер (ОК), инверсию (ОИ), мутацию (ОМ), транслокацию (ОТ) и сегрегацию (ОС) [16-23].

Достоинства ГА, в сравнении с другими подходами к решению задач комбинаторной оптимизации, заключаются в том, что они начинают работать с несколькими начальными решениями, позволяют легко распараллеливать процесс поиска, а также позволяют избежать попадания в локальные оптимумы, при этом комбинируя и наследуя элементы наиболее качественных решений [24 - 26].

Ввиду вышеизложенного, разработка алгоритмов, позволяющих найти приемлемое по качеству и по трудоёмкости решение задач типизации частей схем в комплексных САПР, является АКТУАЛЬНОЙ ПРОБЛЕМОЙ, стоящей перед разработчиками САПР и представляет научный и практический интерес.

ЦЕЛЬЮ диссертационной работы является разработка и исследование генетических алгоритмов типизации схем СБИС на основе изоморфного вложения графов, позволяющих находить оптимальные и квазиоптимальные решения задачи.

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

1) Анализ задачи типизации и определение ее места в общей задаче конструкторского проектирования СБИС с применением комплексных САПР, а также анализ и обоснование выбора математической модели схемы для разрабатываемого генетического алгоритма типизации на основе распознавания изоморфного вложения графов.

2) Анализ принципов и схемы работы ГА, а также основных генетических операторов и их модификаций с точки зрения их пригодности для решения задачи типизации.

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

4) Разработка алгоритма типизации элементов СБИС на основе генетического алгоритма распознавания изоморфного вложения графов и схемы применения генетических операторов.

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

6) Разработка концепции генетического поиска оптимальных решений задачи типизации элементов СБИС, на основе агентно-ориентированного подхода.

7) Теоретическая оценка быстродействия и эффективности разработанных алгоритмов типизации элементов СБИС.

8) Проведение имитационного программного моделирования (экспериментов).

Для решения поставленных задач использовались следующие МЕТОДЫ ИССЛЕДОВАНИИ: элементы высшей математики, теории графов и гиперграфов, алгоритмов, статистических вычислений, генетического поиска, теории многоагентных систем.

ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ диссертационной работы:

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

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

3) На основе генетического алгоритма распознавания изоморфного вложения графов разработан многоуровневый генетический алгоритм типизации элементов СБИС.

4) Разработана структура многоагентной системы управления поиском оптимального решения задачи типизации элементов СБИС на основе многоуровневого генетического алгоритма типизации, состоящая из интеллектуального агента-координатора, множества поисковых агентов и адаптационного агента.

5) Разработан механизм адаптации многоагентной системы управления генетическим поиском оптимального решения задачи типизации элементов СБИС на основе обучающейся системы классификаторов.

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

ОСНОВНЫЕ ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ:

1) Процедура инициализации популяции с применением эвристики для формирования базового решения.

2) Модификация жадного алгоритма локального улучшения ЦФ, учитывающая специфику решаемой задачи.

3) Концепция применения ГА и общей схемы функционирования многоуровневого генетического алгоритма типизации элементов СБИС на основе распознавания изоморфизма графов.

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

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

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

- генетический алгоритм и программа распознавания изоморфизма и изоморфного вложения графов;

- многоуровневый генетический алгоритм и программа типизации элементов СБИС;

- структура многоагентной системы управления генетическим поиском оптимального решения задачи типизации на основе многоуровневого генетического алгоритма;

- результаты исследований эффективности разработанных алгоритмов.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в научно-исследовательской работе «Новые стратегии обучения нейронных сетей на основе вероятностных алгоритмов эволюционного поиска» №12392 по гранту Министерства образования РФ (шифр Е02-2.0-44), а также научно-исследовательской работе, выполненной по гранту Российского фонда фундаментальных исследований № 03-01-00336, Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций и в цикле лабораторных работ по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования». АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на IV,V Всероссийской научной конференция с международным участием молодых ученых и аспирантов (г. Таганрог, 2001 - 2002 гг.), Международной конференции «Интеллектуальные САПР» (CAD-2002, CAD-2003) (г. Геленджик, 2002 - 2003 гг.), Всероссийской научно-технической конференции с участием зарубежных представителей «Интеллектуальные САПР» (г. Таганрог, 2003 - 2004 гг.).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 8 печатных работах. СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав, заключения, и списка использованных источников. Работа содержит 164 стр., включая 35 рис., 3 табл., список использованных источников из 131 наименований и двух приложений, включающих акты об использовании. СОДЕРЖАНИЕ РАБОТЫ.

Выводы и рекомендации

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

2. Выполнено сравнение разработанного многоуровневого генетического алгоритма с одним из известных [2] приближенных эвристических алгоритмов типизации элементов СБИС. Экспериментально подтверждено, что применение разработанного алгоритма позволяет от 5% до 12% сократить время решения задачи типизации. Разброс значений комплексной оценки качества решений у сравниваемых алгоритмов составляет не более 2%.

3. Разработанная многоагентная система управления генетическим поиском оптимального решения задачи типизации на основе многоуровневого генетического алгоритма позволяет более чем в 100 раз сократить время решения, в сравнении с полным перебором. Положительный эффект составляет повышение значения комплексной оценки качества решения задачи типизации на 10-20 % в сравнении с качеством решения многоуровневым генетическим алгоритмом. на

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

На основе генетического алгоритма распознавания изоморфного вложения графов разработан многоуровневый генетический алгоритм типизации элементов СБИС, позволяющий получить качественные решения на 5-12% быстрее приближенного эвристического алгоритма. Для поиска оптимального решения предложена процедура многократного запуска алгоритма многоуровневого генетического алгоритма типизации с различными исходными данными в пределах временных ограничений. Разработана структура многоагентной системы управления поиском оптимального решения задачи типизации элементов СБИС на основе многоуровневого генетического алгоритма типизации, состоящая из интеллектуального агента-координатора, множества поисковых агентов и адаптационного агента. Интеллектуальный агент-координатор реализует «островную» модель генетического алгоритма, основанную на методе конкурирующих точек. Поисковые агенты, каждый из которых реализует многоуровневый генетический алгоритм типизации из окрестностей точек поиска, предоставляют агенту-координатору решения для комплексной оценки качества и из них выбирается оптимальное. В течение работы каждый поисковый агент взаимодействует с адаптационным агентом, который регулирует численность популяции для оптимальной работы многоуровневого генетического алгоритма. Разработан механизм самоадаптации многоагентной системы управления генетическим поиском оптимального решения задачи типизации элементов СБИС на основе обучающейся системы классификаторов. Классификаторы представляют собой закодированный набор параметров поисковых агентов. Предложен механизм управления численностью поисковых агентов на основе процедуры иерархического группирования, который позволяет уменьшить время поиска оптимального решения. Практическая реализация многоагентной системы управления генетическим поиском оптимального решения задачи типизации в виде пакета программ, позволяет более чем в 100 раз сократить время решения задачи, в сравнении с полным перебором, а также получить положительный эффект в виде повышения значения комплексной оценки качества решения задачи типизации на 10-20 % в сравнении с качеством решения задачи многоуровневым генетическим алгоритмом.

1. Петренко А.И., СынчукП.П., Тетельбаум А.Я. и др. Автоматизация проектирования БИС. - Киев: Виша школа, 1983.

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

3. Курейчик В. М. Оптимизация в САПР: Учебное пособие.Таганрог, ТРТУ, 1998.

4. Разработка САПР. / Под ред. А.В. Петрова М.: Радио и связь, 1986.

5. Системы автоматизированного проектирования: В 9-ти кн. Кн. 6. Автоматизация конструкторского и технологического проектирования. Учебное пособие для втузов. / Под ред. Норенкова И.П. М.: Высшая школа, 1986.

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

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

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

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

10. Мелихов А.Н., Берштейн J1.C. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов-на-Дону: издательство Ростовского университета, 1981. - 112 с.

11. Berge С. Graphes et hypergraphes. Dunod, // Paris, 1970.

12. Зыков A.A. Гиперграфы // Успехи математических наук. М. 1979, т.29, вып.6.

13. Горбатов В.А. Теория частично упорядоченных систем. М., 1976.

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

15. Алексеев В. Б., Носов В. А. NP-полные задачи и их полиномиальные варианты. Обозрение прикладной и промышленной математики, 1997, т. 4, вып. 2, С. 165-193.

16. Holland J. Adaptation in natural and artificial systems. // University of Michigan Press Ann Arbor, USA, 1975.

17. Goldberg D.E. Genetic Algorithm in Search // Optimization & Machine Learning, Addison-Westley, 1989.

18. Davis L (Ed). Handbook of Genetic Algorithms. // Van Nostrand Reinhoed, NewJork, USA, 1991.

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

20. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs // Springer-Verlag, 1992.

21. Курейчик B.M. Генетические алгоритмы и их применение в САПР, Интеллектуальные САПР. // Межведомственный тематический научный сборник, Таганрог, 1995, С. 7-11.

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

23. Курейчик В. М. Оптимизация в САПР: Учебное пособие.Таганрог, ТРТУ, 1998.

24. Курейчик В.В. Концепция оптимизации на основе моделирования эволюции // Новые информационные технологии. Разработка и аспекты применения. Таганрог: изд-во ТРТУ, 2000;С. - 49-51.

25. Mitchell М. An Introdution to Genetic Algoriphms. MIT Press, Cambridge, Mass, 1996.

26. A1 Geist, Adam Beguelin, Jack Dongarra, Weicheng Jiang, Robert Manchek, Vaidy Sunderam. PVM: Parallel Virtual Mashine. A users' guide and tutorial for networked parallel computing. // MIT press, 2000.

27. Комплекс общеотраслевых руководящих методических материалов по созданию АСУ и САПР. М.:статистика, 1980, с. 76-90.

28. Быстродействующие матричные БИС и СБИС. Теория и проектирование / Под общей редакцией Файзулаева Б.Н. и Шагурина И.П. М.: Радио и связь, 1989.

29. Колосов Г.Е. Об одной задаче управления численностью популяции. // Изв. РАН. Теории и системы управления под № 2, 1995.

30. Автоматизация проектирования М., РАН, 1-6, 1977, 1978.

31. Шалыто А.А. Использование граф-схем и графов переходов при программной реализации алгоритмов логического Управления. // Автоматика и телемеханика. С-пб, 1996. N6, С. 148-158.

32. Зыков А. А. Теория конечных графов.- Новосибирск: Наука, 1969,- 378с.

33. Деньдобренько Б.Н., Малика А.С. Автоматизация конструирования РЭА: Учебник для вузов. М.: Радио и связь, 1986. - 192 с.

34. Петренко А.И., Тетельбаум А.Я. Формальное конструирование электронно-вычислительной аппаратуры. -М.: Сов. Радио, 1979. 255с.

35. Карелин В.П., Миронов Б.Н. Алгоритм случайного направленного поиска изоморфного вложения графов на автоматной модели // Однородные цифровые вычислительные и интегрирующие структуры. Таганрог, 1976. Вып. 6. С. 24-33.

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

37. Мелихов А.Н., Карелин В.П. Методы распознавания изоморфизма и изоморфного вложения четких и нечетких графов: Учебное пособие. Таганрог ТРТУД995.

38. Ковалев А.В. Разработка и исследование методов проектирования цифровых заказных СБИС. Автореферат диссертации на соискание учёной степени кандидата технических наук. — Таганрог: ТРТУ, 2001.

39. Земляченко В.Н., Корнеенко Н.М., Тышкевич Р.И. Проблема изоморфизма графов // Зап. науч. семинаров ЛОМИ. JL: Наука. Ленингр. отд-ние, 1972.-Т. 118.-С. 83-158.

40. Петросян В. Г., Петросян Т. В. Методы перебора в решении физических задач // Информатика и образование. 1996. 3 с. 73-83.

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

42. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.

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

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

45. Харари Ф. Теория графов. М.: Мир, 1973. 300 е., ил.

46. Татт У. Теория графов. М.: Мир, 1988. 424 е., ил.

47. Оре О. Теория графов. М.: Наука, 1980. 336.

48. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. // Новосибирск: Наука, 1990, 515 с.

49. Скоробогатов В.Н. О распознавании изоморфизма неориентированных графов // Вычислительные системы. Новосибирск, 1968. Вып. 33. С. 3-10.

50. Сэлтон Г. Автоматическая обработка, хранение, и поиск информации. М.: Сов. радио, 1973. 506 с.

51. Васин В.О. Алгоритм установления изоморфизма графов // Автоматизация логического проектирования цифровых устройств. Киев, 1974. С. 133-146.

52. Каляев А.В., Мелихов А.Н., Курейчик В.М., и др. // Автоматизация проектирования вычислительных структур. Ростов н/Д: Изд-во РГУ, 1983. 224 с.

53. Cornel D. G., Gotlieb C. G. An efficient algoriphm for graph isomorphism // J. of the assotiation for computing machinery, 1970. V. 17, N.l P. 51-64.

54. Петренко А.И., Курейчик B.M., Тетельбаум А.Я. и др. Автоматизация проектирования больших и сверхбольших интегральных схем. // Зарубежная радиоэлектроника, 1981, № 6, С. 47 - 66.

55. Курейчик В.М., Королев А.Г. Метод распознавания изоморфизма графов. «Кибернетика», АН УССР, Киев №2, 1977.

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

57. Зыков А.А. Теория конечных графов. Новосибирск: Наука, Сибирское отделение, 1969.

58. Jarmo Т. Alander An Indexed Bibliography of Genetic Algorithms: Years 1957-1993.

59. Soraya Rana. Examining the Role of Local Optima and Schema Processing in Genetic Search, 1999.

60. Darrel Whitley. A Genetic Algorithm Tutorial, 1993.

61. Курейчик B.M., Курейчик B.B. Генетический алгоритм разбиения графа. // Изв. РАН. Теории и системы управления № 4, 1999.

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

63. Никифоров A.M. Оценка качества размещения. // Известия ТРТУ № 3, 1999, С.-206-209.

64. Росс Клемент. Генетические алгоритмы: почему они работают? когда их применять? // Журнал «Компьютерра» 2002.

65. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов./Межвузовский сборник научных трудов "Высокие технологии в технике, медицине и образовании", Воронеж, ВГТУ, 1997г, С. 4-17.

66. Tobias Blickle and Lothar Thiele. A Comparison of Selection Schemes used in Genetic Algorithm, 1995, 2 Edition.

67. Back T. Evolutionary Algoriphms in Theory and Practice. // Oxford University Press, New York, 1996.

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

69. Курейчик В.М. Генетические алгоритмы. // Учебник для вузов. Таганрог. Из-во ТРТУ. 2002г.-118с.

70. Хабарова И.В., Назаренко А.А. Генетический криптоанализ блочных шифров на основе DES. // Известия ТРТУ, Таганрог, ТРТУ. 1999. № 3, С. - 154-158.

71. Practical handbook of Genetic Algorithms. Complex Coding Systems. / Edited by Lance D. Chambers. CRC Press LLC, 1999.

72. Дюк В., Самойленко A. Data Mining: Учебный курс (+CD). // СПб: Питер,2001.-368с.: ил.

73. Anderson Peter G. Permutation Based GAs and Ordered Greed. //Computer Science Department Rochester Institute of Technology, Rochester, New York,2002.

74. Eiben A.E., Raue P.E., Ruttkay Zs. Genetic Algorithms with multiparent recombination. Parallel Problem Solving from Nature III. // Berlin: Springer Verlag, (LNCS), v866, 1994, P. 78-87.

75. Курейчик В.М. Генетические алгоритмы и их применение в САПР. Междуведомственный тематический научный сборник "Интеллектуальные САПР", Выпуск 5. Таганрог, 1995.

76. Genesereth M.R, Ketchpel S.P. Communications of the Association for Computing Machinery, vol. 37, no. 7 1994, P. 48-53.

77. David E. Goldberg, Kumara Sastry. A Practical Schema Theorem for Genetic Algorithm Design and Tuning, 2001.

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

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

80. Еремеев А.В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. // Дисс. канд.физ.-мат.наук. Омск, 2000.

81. Исаев С.А. Генетические алгоритмы эволюционные методы поиска // http://saisa.chat.ru/ga/text/partl.html

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

83. Букатова И.Л. Эволюционное моделирование и его приложения. М.:Наука, 1994.

84. Курейчик B.M., Божич В.И., Хабарова И.В. Применение генетических алгоритмов в задачах криптоанализа. Криптосистемы с закрытым ключом. // Методическое пособие № 1221-2, Таганрог: ТРТУ, 2000г., 24 е.

85. Носов В.А. Комбинаторика и теория графов. М.: Изд-во МГУ, 1999.

86. Осыка А.В. Экспериментальное исследование зависимости скорости сходимости генетического алгоритма от его параметров. //Изв. РАН. Теории и системы управления № 5, 1997. с. 100-111.

87. Whitley D. Mathias К. Genetic Operators, the Fitness Landscape and the Traveling Salesman Problem // Parallel Problem Solving from Nature-PPSN, 1994.

88. Силютин Д.С. Специфика организации генетического поиска изоморфной подстановки графов // Перспективные информационные технологии и интеллектуальные системы. 2003 №4(16), С. 100-103, http://pitis.tsure.ru/files 16/14.pdf.

89. Гончаров Е.Н., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. // Сер. 2. т. 6 1999, № 1, с. 12-32.

90. Boese K.D., Kahng А.В., Muddu S. A new adaptive multi-start technique for combinatorial global optimizations. // Oper. Res. Lett. vl6, 1994, N2, P. 101106.

91. R. Poli. Introduction to Evolutionary Computation // Lectures notes. School of Computer Science, The University of Birmingham, 1996. http://www.cs.bham.ac.uk/~rmp/slidebook.

92. W.M. Spears. Adapting crossover in a genetic algorithm. // Laboratory Report, #AIC-92-025, Navy Center for Applied Research in Artificial Intelligence, (USA), 1992.

93. Korupolu M., Plaxton C., Rajaraman R. Analisys of a local search heuristic for fasility location problem Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. 1998, P. 1-10.

94. Clement R.P., Wren A. Genetic Algorithms and Bus-Driver Scheduling // Presented at the 6th International Conference for Computer-Aided Transport Scheduling, Lisbon, Portugal, 1993.

95. Youssef G. Saab, Vasant B. Rao. Fast Effective Heuristics for the Graph Bisectioning Problem // IEEE, vol.9 N1, January 1990, Transaction on computer-aided design.

96. Thang Nguyen Bui, Byung-Ro Moon. "GRCA: A Hybrid Genetic Algorithm for Circuit Ratio-Cut Partitioning". IEEE Transactions on computer-aided desighn of integrated circuits and systems, vol.17, No.3, March 1998, p. 193-204.

97. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.: Мир,- 1979.-536 с.

98. Носов В.А. Основы теории алгоритмов и анализа их сложности. М.: Изд-во МГУ, 1992.

99. Силютин Д.С. Применение многоагентных технологий в организации генетического поиска изоморфной подстановки // Перспективные информационные технологии и интеллектуальные системы. 2003 №2(14), С. 48-54, http://pitis.tsure.ni/filesl4/l l.pdf.

100. Силютин Д.С. Многоагентная система управления ГП изоморфной подстановки // труды Международных конференций «Искусственные интеллектуальные системы»(1ЕЕЕ AIS'03) и «Интеллектуальные САПР»

101. CAD-2003). Научное издание.-М.: Издательство Физматлит, 2003. С -457-463.

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

103. Chess, D. Security Considerations in Agent-based Systems // Portland, Oregon: 1st Annual Conference on Emerging Technologies and Applications in Communications (etaCOM'96), 1996.

104. Gao, Y. Cyberagent: An Integrated Mobile Agent System Based on Java // Marina del Rey, CA: Proceedings of the First International Conference on Autonomous Agents, February. 1997.

105. Ousterhout, J. K. Scripts and Agents, the New Software High Ground // New Orleans, LA: Winter USENIX Conference, http://www.smli.com/research/tcl. 1996.

106. Takeda, H., lino, K. and Nishida, T. Agent Organization and Communication with Multiple Ontologies // International Journal of Cooperative Information Systems, 1995, vol. 4, no. 4, P. 321-337.

107. White, J. E. Mobile Agents // Menlo Park, CA, AAAI Press/MIT Press, in Bradshaw, J.(ed.), Software Agents, 1996.

108. Wooldridge, M. J. and Jennings, N. R (eds.) Intelligent Agents // Proceedings of the ECAI-94 Workshop on Agent Theories, Architectures, and Languages, Berlin, Springer-Verlag, 1995, P. 2-39.

109. Bayer, D. A Learning Agent for Resource Discovery on the World Wide Web // MSC Project Dissertation, University of Aberdeen. 1995.

110. Brustoloni, J. C. Autonomous Agents: Characterization and Requirements //

111. Carnegie Mellon Technical Report CMU-CS-91-204), Pittsburgh, Carnegie Mellon University, 1991.

112. Burkhard, H. D. Agent-Oriented Programming for Open Systems // Berlin, Springer-Verlag: Proceedings of the ECAI-94 Workshop on Agent Theories, Architectures, and Languages," 1994. P. 291-306.

113. Wooldridge M., Jennings N. Intelligent Agents: Theory and Practice // Knowledge Engineering Review, 1995, V. 10, N 2, P. 115-152.

114. Nwana H.S., Ndumu D.T. An Introduction to Agent Technology // ВТ Technology Journal, 1996, V. 14, N 4, P. 55-67.

115. Wooldridge M., Jennings N. Intelligent Agents // Lecture Notes in Artificial Intelligence, 1995, v.890, P. 407.

116. Поспелов Д.А. От коллектива автоматов к мультиагентным системам // Труды Международного семинара «Распределенный искусственный интеллект и многоагентные системы» (DIAMAS'97, С-Пб. 1997), С. 319-325.

117. Тарасов В.Б. Агенты, многоагентные системы, виртуальные сообщества: стратегическое направление в информатике и искусственном интеллекте // Новости искусственного интеллекта. 1998. №2. - С. 5- 63.

118. Городецкий В.И. Многоагентные системы: основные свойства и модели координации поведения // Информационные технологии и вычислительные системы. -1998. № 1.С. 22-37.

119. Murray D. Developing Reactive Software Agents // AI Expert. 1995.

120. Сотник С. JI. Конспект лекций по курсу "Основы проектирования систем искусственного интеллекта", 1997-1998.

121. Mainner R., Manderick В., eds. Artificial Intelligence through Simulated Evolution // North Holland-Elsevier, 1992. P. 219-228.127. http://www.ai.tsi.lv/ru/ga/cfs intro.html

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

123. Meyer J.A., Wilson S. Simulation of Adaptive Behavior: from Animal to Animats. Cambridge MA: MIT Press, 1991

124. Буч Г. Объектно-ориетированный анализ и проектирование с примерами приложений на С++: Пер. с англ. 2-е издание М.: Бином, 1998.

125. Троелсен Эндрю. С# и платформа .NET. Библиотека программиста. -СПб: Питер, 2002 800с.:ил.