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

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

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

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

1.2. Постановка задачи разбиения схем при проектировании СБИС.

1.3. Учт тепловых характеристик.

1.4. Классификация методов и алгоритмов решения поставленной задачи

1.5. Выводы.

2. ПРИМЕНЕНИЕ МЕТОДОВ ГЕНЕТИЧЕСКОГО ПОИСКА ДЛЯ РЕШЕИЯ ЗАДАЧИ РАЗБИЕНИЯ СХЕМ ПРИ ПРОЕКТИРОВАНИИ СБИС

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

методов
2.2. Элементы генетических алгоритмов.
2.3. Структура генетического алгоритма.
2.4, Выбор методики кодирования информации
. 2.5. Селекция
2.6. Основные генетические операторы
2.6.1. Оператор кроссинговера.
2.6.2. Оператор мутации.
2.6.3. Оператор инверсии
2.7. Выводы.
3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАЗБИЕНИЯ С ЭЛЕМЕНТАМИ АДАПТАЦИИ ГАСЭА.
3.1. Структурная схема ГАСЭА для разбиения схем при проектировании
3.2. Элементы адаптации в ГАСЭА.
3.3. Генератор хромосом содержащих группы вершин ГХСЯ.
3.4. Модифицированные процедуры, применяемые для ГО.
3.5. Блок локального улучшения решений
3.6. Блок анализа преждевременной сходимости и критерия остановки алгоритма
3.7. Блок адаптации алгоритма
3.8. Теоретические оценки алгоритма
3.9. Выводы
4. РАЗРАБОТКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ И ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМА РАЗБИЕНИЯ
СХЕМ ПРИ ПРОЕКТИРОВАНИИ СБИС. I
4.1. Разработка основных пунктов меню программного обеспечен ия
.4.2. Формат входного файла гиперграфа.
4.3. Формат выходного файла решения
4.4. Цель экспериментального исследования
4.5. Этапы экспериментальных исследований
4.6. Результаты экспериментальных исследований.
4.6.1. Результаты исследований для блока модифицированных генетических операторов.
4.6.2. Результаты исследований для проблемноориентированного генератора стартовой популяции ГХСЯ
. 4.6.3. Результаты исследований для разработанного алгоритма ГАСЭА
4.7. Сравнение полученных экспериментальных данных ГАСЭА с
. результатами аналогов
4.8. Выводы,
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Определены теоретические оценки временной и пространственной сложности разработанного алгоритма. В ЧЕТВЕРТОЙ ГЛАВЕ приведено описание экспериментальных исследований ГАСЭА. Выполнена статистическая обработка полученных экспериментальных данных. Определены диапазоны оптимальных значений параметров генетического поиска. Оценена эффективность применения разработанного проблемно-ориентированного генератора стартовой популяции решений. Выполнено сравнение результатов работы разработанного ГАСЭА с известными аналогами. Представлено описание программного обеспечения для генерации, решения и исследования, различных гиперграфовых моделей схем для задачи разбиения схем при проектировании СБИС. В приложениях приведены копии актов об использовании, графический интерфейс программного обеспечения, примеры решения задачи разбиения схем для стандартных тестовых схем. При проектировании электронной аппаратуры (БИС, СБИС, блоков ЭВА и т. Выбор способа определяет адекватность математической модели реальному объекту, удобство проектирования, затраты машинной памяти на представление моделей, лёгкость оценки полученных результатов и т. Теория . Язык теории графов удобен при проведении различных исследований в таких областях как теоретическая физика, химия, биология, экономика, социология, лингвистика, теория игр, комбинаторная оптимизация [5]. Практическая роль графов особенно возросла за последние годы в связи с интенсивным развитием таких направлений, как автоматизированные системы планирования, проектирования и управления, разработка и создание . Это объясняется тем, что использование графов сокращает объём вычислений по сравнению с обычными методами и, сохраняя наглядность описания объектов (конструкций), позволяет строить компактные и удобные для реализации на ЭВМ алгоритмы преобразований и оптимизации. При проектировании конструкций ЭВА (заказных, полузаказных СБИС и др. Такое представление объекта отличается высокой наглядностью, позволяет сосредоточить внимание на наиболее существенных связях, находить оптимальное решение задач проектирования. Этот способ задания моделей называется графовым. При анализе конструкций ЭВА применяют в основном неориентированные графы. Принципиальная электрическая схема интерпретируется графом, в котором каждому конструктивному элементу ставится в однозначное соответствие вершина, а электрическим связям — рёбра графа. Это позволяет абстрагироваться от конкретных схем и, перейдя к их математическим моделям — графам, разрабатывать эффективные методы поиска конструктивных оптимальных решений. В конструкторском проектировании, наряду с неориентированными графами, используют ориентированные, у которых рёбра имеют определённое . Ниже рассмотрим каждую из ' этих моделей. При построении графовой модели схемы (БИС, СБИС) вершинам графа, как правило, соответствуют компоненты (элементы) схемы, а связи между ними отображаются посредством рёбер графа рис. Граф С = (Х, Ц), X = {х; | / = I, 2, . Г= {и, |у = 1, 2, . С (ке {2,3,. Рёбра, соединяющие одну и ту же пару вершин, называются кратными (рис. Для процесса конструирования необходима нумерация элементов, поэтому для моделей систем проектирования используются только помеченные графы. Граф называют помеченным, если его вершины отличаются одна от другой различными метками, например х1, х2,. Многие задачи автоматизации конструирования удобно решать при использовании матричной формы задания графа. Квадратную таблицу /? О в противном случае. Очевидно, что для рассматриваемых графов Гц = /у/ и для задания графа достаточно использовать половину матрицы Я. Матрица смежности для графа С, изображенного на рис. Строки и столбцы матрицы Я соответствуют вершинам графа Є. На пересечении х1у строки и Хр столбца находится элемент /*,у, соответствующий числу рёбер, соединяющих вершины ЛГ/ и Хр Заметим, что строки и столбцы матрицы Я также можно нумеровать числами натурального ряда, соответствующими индексам помеченных вершин графа. Петли в графе изображаются элементами Г/у = гу/, расположенными по главной диагонали матрицы Я.