авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 |

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

-- [ Страница 1 ] --

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

Баринов Сергей Владимирович

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

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

Специальность:

05.13.12 – системы автоматизации проектирования

АВТОРЕФЕРАТ

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

кандидата технических наук

Таганрог – 2008

Работа выполнена в Технологическом институте Южного федерального университета в г. Таганроге.

Научный руководитель: заслуженный деятель науки РФ,

доктор технических наук,

профессор Курейчик В.М.

Официальные оппоненты: доктор технических наук, профессор

Витиска Николай Иванович

(Таганрогский государственный

педагогический институт, г. Таганрог)

доктор технических наук, профессор

Ковалев Сергей Михайлович

(Ростовский государственный университет

путей сообщения, г. Ростов-на-Дону)

Ведущая организация: Федеральное государственное

унитарное предприятие Таганрогский НИИ

Связи.

Защита состоится «28» августа 2008 г. в 14:20 на заседании диссертационного совета Д 212.208.22 при Южном федеральном университете по адресу: 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан «14» июля 2008 г.

Ученый секретарь

диссертационного совета Д 212.208.22,

доктор технических наук, профессор Целых А.Н.

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

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

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

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

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

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

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

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

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

1. Новая архитектура процесса разбиения схем, основанная на методах эволюционного моделирования и многоуровневой парадигме.

2. Новые и усовершенствованные механизмы генетического поиска: учет «времени жизни» хромосом в популяции, применение принципов Парето оптимизации и распараллеливание процесса поиска.

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

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

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

6. Новый проблемно-ориентированный генератор начальной популяции на основе получения оптимальных строительных блоков.

7. Усовершенствованные операторы генетического поиска на основе фигурных чисел, обеспечивающие уменьшение времени поиска.

Научная новизна работы.

1. Предложена новая многоуровневая архитектура процесса разбиения схем с учетом временных задержек на основе методов эволюционного моделирования.

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

3. Предложен модифицированный генетический алгоритм на основе модели эволюции Ч. Дарвина, использующий принципы Парето оптимизации.

4. Представлены новые и усовершенствованные алгоритмы свертки гиперграфа на основе нахождения сжатия гиперребер, агрегации фракталов.

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

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

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

1. Архитектура эволюционного поиска для решения задач разбиения схем на фрагменты с учетом временных задержек.

2. Усовершенствованные операторы генетического поиска для решения задачи разбиения схем.

3. Программный комплекс «PGAComplex» решения задачи разбиения схем с учетом временных задержек.

Реализация результатов работы. Результаты работы внедрены в научно-исследовательских работах, выполняемых на кафедре САПР ТТИ ЮФУ.

Апробация работы. Основные результаты диссертационной работы обсуждались и были одобрены на Всероссийских научно-технических конференциях «Проблемы разработки перспективных микроэлектронных систем» (2005-2006 гг.), Международных научно-технических конференциях «Интеллектуальные САПР» (п. Дивноморское, 2005 - 2007 гг.), международной конференции «Интеллектуальные системы (IEEE AIS’06)» (п. Дивноморское, 2005г.), международной молодежной научно-технической конференции "Интеллектуальные системы в науке, технике, образовании, бизнесе" (п. Дивноморское, 2007 г.), IV-й Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте»(г. Коломна, 2007 г.),.

Публикации. Результаты диссертации отражены в 9 печатных работах.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы. Работа содержит 155 страниц, включая 55 рисунков, 15 таблиц, список литературы из 106 наименований, 5 страниц приложений с актами об использовании работы.

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

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

В ПЕРВОЙ ГЛАВЕ приводится общая постановка задачи разбиения схем на фрагменты по критерию суммарного количества межблочных связей и анализ существующих алгоритмов разбиения схем.

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

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

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

Необходимо разбить множество вершин на непустых и непересекающихся подмножеств :

.

На каждое подмножестве накладывается следующее ограничение:

, где

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

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

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

ВО ВТОРОЙ ГЛАВЕ проанализированы основные положения теории генетического поиска, показаны преимущества методов эволюционного моделирования по сравнению с традиционными эвристическими методами решения NP - полных задач. Выделены принципы эволюционного поиска, ориентированные на решение задачи разбиения схем на фрагменты.

Предложена модифицированная форма представления и кодирования исходных данных. В данном случае альтернативное решение(хромосома) представляется в виде последовательности размера . Позиции представляют исходное множество объектов разбиения. Дополнительные позиции служат для кодирования разделителей. Например, разбиение 7 элементов на 3 куска кодируется следующим образом: (1,2,8,3,4,5,9,6,7). Множество {8, 9} представляет разделители полученного разбиения. Предложенный метод кодирования позволяет избежать нелегальных решений, в частности отсутствия некоторых кусков разбиения. Однако, возможно дублирование объектов разбиения после применения генетических операторов. Это может оказаться полезным в случае решения задачи разбиения схем с дублированием элементов.

Рассмотрены и предложены модифицированные модели эволюций Ч. Дарвина и Ж. Ламарка.

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

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

Величина ЦФ хромосом определяется следующим образом. Для недоминантных хромосом значение ЦФ умножается на коэффициент :

, , где

- число хромосом в текущей популяции Парето, над которыми доминирует хромосома , - общее число хромосом в популяции. Значение ЦФ доминантной хромосомы умножается на параметр :

, где

- сумма значений устойчивости Парето-оптимальных хромосом, которые доминируют над хромосомой .

После этапа определения ЦФ хромосом, обе популяции объединяются для применения проблемно-ориентированных генетических операторов.

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

Значение возраста каждой хромосомы устанавливается после инициализации всех хромосом перед применением ГО. Время жизни хромосомы не изменяется в течение всего процесса эволюции. Таким образом, размер популяции после одной итерации равен:

, где

- размер популяции поколения , - размер популяции поколения , -популяция потомков поколения , - число хромосом, которые «умирают» в течение генерации .

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

, где

- «время жизни» хромосомы , и - соответственно минимальное и максимальное заданное «время жизни», - ЦФ хромосомы, , и - соответственно минимальное, максимальное и среднее значение ЦФ популяции. Если среднее значение ЦФ популяции больше ЦФ хромосомы, то «время жизни» вычисляется согласно выражению a). В противном случае вычисляется выражение b).

Кроме этого предлагается модифицированный механизм селекции на основе распределения Больцмана. Этот закон используется в моделировании отжига. Метод основан на турнирной селекции. Выбор хромосом для дальнейших преобразований основан на следующем выражении:

,где

- вероятность выбора хромосомы в «турнир» индивидов, - значение ЦФ хромосомы, параметр определяет толерантность ГА, как и температура в моделировании отжига.

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

Разработана многопопуляционная архитектура эволюционного поиска для получения оптимальных решений задачи разбиения схем. В предлагаемой архитектуре из исходной популяции хромосом выделяется четыре подпопуляции. В качестве структуры взаимодействия между подпопуляциями(топологии) выбрана структура тетраэдра. Миграция хромосом происходит по закону «утечки мозгов», т.е. когда популяцию покидают хромосомы с лучшими значениями ЦФ. Кроме качественных характеристик, эффективность миграции зависит от количества хромосом, участвующих в обмене, а также частоты возникновения миграции. Оптимальная частота миграции в данном случае определяется выражением , где - степень топологии (степень предложенной топологии равна 3).

Общая разработанная архитектура генетического алгоритма разбиения схем показана на рис. 1.

Внесенные улучшения в базовую структуру генетического поиска предназначены для сокращения времени работы алгоритма и сжатия поискового пространства.

Рис.1 Архитектура генетического алгоритма разбиения схем

В ТРЕТЬЕЙ ГЛАВЕ описана многоуровневая архитектура поиска, позволяющая эффективно использовать разработанные генетические алгоритмы.

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

Для этапа свертки гиперграфа разработаны два алгоритма: метод свертки на основе сжатия гиперребер, а также алгоритм свертки гиперграфа на основе агрегации фракталов.



Pages:   || 2 |
 





 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.