Разработка и исследование комплексного гибридного генетического алгоритма разбиения схем

• Автор: Дуккардт, Александр Николаевич
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Таганрог
• Количество страниц: 152 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

1 АНАЛИЗ АЛГОРИТМОВ И МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ РАЗБИЕНИЯ СХЕМ

1.1 Анализ и выбор математической модели .

1.2 Постановка задачи разбиения схем

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

1.4 Выводы

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

ДЛЯ ЗАДАЧИ РАЗБИЕНИЯ СХЕМ.

2.1 Отличие методов генетического поиска от других методов оптимизации

2.2 Структура генетического алгоритма

2.3 Кодирование информации для задачи разбиения схем.
2.3.1 Структура хромосом и принципы декодирования на основе назначения гиперребер в узлы
2.3.2 Структура хромосом и принципы декодирования на основе рекурсивного применения процедуры дихотомического разбиения
2.4 Г енетические операторы
2.5 Выводы.
3 РАЗРАБОТКА КОМПЛЕКСНОГО ГИБРИДНОГО
ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАЗБИЕНИЯ СХЕМ
3.1 Структурная схема комплексного гибридного генетического алгоритма разбиения схем
3.2 Блок генерации начальной популяции.
3.3 Блок модифицированных Генетических Операторов
3.4 Блок анализа преждевременной сходимости и критерия остановки
алгоритма.
3.5 Блок локального улучшения решений
3.6 Блок альтернативного декодирования решений.
3.7 Блок адаптации генетического поиска.
3.8 Теоретические оценки алгоритма
3.9 Выводы
4 РАЗРАБОТКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ И
ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМА
РАЗБИЕНИЯ ЭЛЕМЕНТОВ СБИС.
4.1 Цель вычислительного эксперимента
4.2 Планирование вычислительного эксперимента
4.3 Результаты вычислительного эксперимента
4.4 Выводы .
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Работа выполнена в рамках приоритетного национального проекта «Образование». АПРОБАЦИЯ основных теоретических и практических результатов работы. Результаты диссертации докладывались и обсуждались на Всероссийских и Международных научно-технических конференциях: «Интеллектуальные САПР», (г. Таганрог, - гг. VII Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», (г. Таганрог, г. Информационные технологии, системный анализ и управление», (г. Таганрог, г. III Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г. Таганрог, г. Международная научно-техническая конференция «Интеллектуальные САПР», (г. Таганрог, г. ПУБЛИКАЦИИ. По теме диссертации опубликовано 6 печатных работ. СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырёх глав, заключения, и списка использованных источников. Работа содержит 9 стр. СОДЕРЖАНИЕ РАБОТЫ. ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, сформулированы цели, дано общее описание выполненной работы. В ПЕРВОЙ ГЛАВЕ приведена постановка задачи разбиения СБИС на основе гиперграфовой математической модели, по критерию минимизации суммарного количества гиреррёбер между подграфами и временной задержки прохождения сигнала. Рассмотрены существующие алгоритмы и методы решения задачи разбиения СБИС, выявлены их достоинства и недостатки. ВО ВТОРОЙ ГЛАВЕ рассмотрены методы генетического поиска применяемые для решения поставленной задачи. Показаны преимущества методов генетического поиска при решении ЫР-полных задач относительно других оптимизационных методов. Обоснован выбор общей схемы последовательного генетического поиска. Рассмотрена универсальная по постановке задачи методика кодирования информации и выявлены ее основные недостатки. Разработаны методы кодирования и декодирования хромосом для решения поставленной задачи. Рассмотрены и выбраны основныетенетические операторы* используемые для решения поставленной задачи. Приведена структурная схема разработанного алгоритма. Определены теоретические оценки временной и пространственной сложности разработанного алгоритма. В ЧЕТВЕРТОЙ ГЛАВЕ приведено описание экспериментальных исследований разработанного алгоритма. Выполнена статистическая обработка полученных экспериментальных данных. Проделанные расчёты позволили подтвердить полученные ранее теоретические оценки временной и пространственной сложности разработанного алгоритма. Определены диапазоны оптимальных значений параметров генетического поиска. Выполнено сравнение результатов работы разработанного алгоритма с известными аналогами. Представлено описание программного обеспечения для генерации, решения и исследования, различных гиперграфовых моделей схем для разбиения СБИС. В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы. В приложениях приведены копии актов об использовании, примеры решения задачи разбиения для стандартных тестовых схем. Анализ и выбор математической . При проецировании электронной аппаратуры (БИС, СБИС, блоков ЭВА и т. Модель - является упрощенным представлением реальности. Хорошая модель всегда включает элементы, существенно влияющие на результат, и не включает те, которые малозначимы на данном уровне абстракции. Каждая система может быть описана с разных точек зрения, для чего используются различные модели, каждая из которых является семантически замкнутой абстракцией системы. Модель может быть структурной, подчеркивающей организацию системы, или поведенческой, то есть отражающей ее динамику. Модели помогают нам понять сложную систему, поскольку мы не можем воспринять ее как единое целое. Процесс создание модели называется моделированием. Чем больше и сложнее система, тем большее значение приобретает моделирование при ее разработке. Моделируя, мы сужаем проблему, заостряя внимание в данный момент только на одном аспекте, который важен на данном уровне абстракции.