Разработка и исследование гибридных методов размещения фрагментов СБИС с учётом трассируемости соединений

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

Содержание

Список иллюстраций.

Введение

Глава 1 Анализ и состояние проблемы размещения и трассировки соединений.

1.1 Состояние и проблемы современного проектирования СБИС.

1.2 Общая постановка задачи размещения.

1.3 Классификация и анализ методов размещения

1.4 Анализ критериев задач размещения

1.5 Анализ возможных алгоритмов оценки трассируемости

1.6 Выводы.

Глава 2 Методы решения многокритериальных задач оптимизации

2.1 Решение многокритериальной задачи размещения с учтом трассируемости.
2.2 Градиентные методы решения задач многокритериальной оптимизации .
2.3 Генетические и эволюционные методы решения задачи размещения с учтом трассируемости соединений.
2.4 Нечткие генетические алгоритмы, ориентированные на решение задачи размещения.
2.5 Адаптация параметров ГА к специфике решаемой задачи с использованием нечеткого контроллера.
2.6 Выводы.
Глава 3 Разработка алгоритма решения задачи размещения с учетом
трассируемости соединений
3.1 Постановка задачи размещения с учетом трассируемости соединений
3.2 Целевая функция и ограничения
3.3 Разработка гибридного генетического алгоритма размещения с учтом трассируемости.
3.4 Разработка гибридного нечткого генетического алгоритма
3.5 Кодирование и декодирование решения
3.6 Разработка нечтких операторов.
3.7 Методы улучшения решения
3.8 Выводы
Глава 4 Экспериментальные исследования разработанной программы
4.1 Теоретическая оценка разработанной программы
4.2 Цели экспериментов
4.3 Описание программной среды
4.4 Результаты экспериментальных исследований.
4.5 Выводы
Заключение.
Список литературы


В настоящее время эволюционные и генетические алгоритмы широко используют для решения ряда сложных задач оптимизации. Благодаря своему разнообразию подходов к нахождению решений, генетические алгоритмы представляют собой весьма эффективное средство решения задач оптимизации и проектирования. Такое направление, как синергетика, изучает универсальные закономерности процессов самоорганизации, эволюции и кооперации. Ее цель состоит в построении общей теории сложных систем, обладающих особыми свойствами и характеристиками: множество неоднородных компонентов, кооперативное поведение компонентов, рас пределе нноегь и т. Особое место в синергетике занимают вопросы спонтанного образования упорядоченных структур различной природы в процессах взаимодействия, когда исходные системы находятся в неустойчивых состояниях. Синергетику можно кратко охарактеризовать как «комплекс наук о возникающих системах». Новым этапом развития теории генетических алгоритмов стали гибридные системы. Они основаны на совмещении таких теорий, как генетические алгоритмы, нечеткие системы и нейронные сети. Существуют различные способы гибридизации этих трёх подходов. ГА, для работы генегических операторов или для построения критериев окончания работы Г А. Также для решения различных «сложных» задач всё чаще используются способы, основанные на применении методов искусственного интеллекта. Одним из новых направлений в вычислительном интеллекте является мультиагентные методы интеллектуальной оптимизации, базирующиеся на моделировании коллективного интеллекта, использовании принципов инспирированных в природными системами. Коллективная система способна решать сложные динамические задачи по выполнению совместной работы, которая не могла бы выполняться каждым элементом системы в отдельности в разнообразных средах без внешнего управления, конгроля или координации. В таких случаях говорят о роевом интеллекте (Swarm intelligence) как о методе моделирования кооперативного поведения. Очень многие работы, в основном западных исследователей, направлены на разработку гибридных систем. В настоящее время существуют в основном нейро-нечеткие системы. Однако число разработок в области создания гибридных нечетко-генетических, нейро-генетических и нейро-нечетко-генетических систем постоянно растет. Нечеткие генетические алгоритмы с успехом применяют в современных средствах автоматизации проектирования изделий электронной техники, которая содержит сложнейшие электронные системы. Анализ последних научных публикаций позволяет сделать вывод, что в процессе конструкторского проектирования СБИС особую роль занимают два этапа проектирования, размещение и трассировка. Задача размещения решается методами учитывающие нечёткие значения и возможную неточность в поставленной задаче. Учитывая полученную оценку трассируемости соединений, можно получить наилучший результат при решении задачи размещения. Следовательно, разработка алгоритма, позволяющего одновременно найти приемлемое по качеству и по трудоёмкости эффективное решение задачи размещения с учетом трассируемости соединений, является АКТУАЛЬНОЙ задачей, стоящей перед разработчиками САПР. ЦЕЛЬЮ диссертационной работы является разработка новых и модифицированных методов и алгоритмов решения задачи размещения с учетом трассируемости на основе нечетких генетических алгоритмов, позволяющих производить расчёты на основе вещественных чисел и нечётких правил. Постановка задачи алгоритма размещения с учетом трассируемости соединений. Разработка структурной схемы процесса гибридного генетического поиска для решения задачи размещения с учётом трассируемости. Создание новых структур и принципов кодирования и декодирования альтернативных решений на основе вещественных чисел. Разработка и модификация стратегий моделирования популяции. Разработка математической модели логического контроллера. Исследование оценки качества целевой функции. Для решения поставленных задач используют следующие МЕТОДЫ ИССЛЕДОВАНИЙ: теория процессов проектирования, нечёткие генетические алгоритмы, вещественное кодирование, теория эволюционного моделирования.