Разработка и исследование генетических алгоритмов типизации элементов СБИС на основе изоморфного вложения графов тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Силютин, Денис Сергеевич

• Силютин, Денис Сергеевич
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Силютин, Денис Сергеевич

ВВЕДЕНИЕ.

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 % в сравнении с качеством решения задачи многоуровневым генетическим алгоритмом.

Список литературы диссертационного исследования кандидат технических наук Силютин, Денис Сергеевич, 2004 год

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с.:ил.