WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

«Раздел I. Эволюционное моделирование, генетические и бионические алгоритмы УДК 621.3.049.771.14:004.023 Э.В. Кулиев, А.А. Лежебоков ЭФФЕКТИВНЫЙ СПОСОБ КОДИРОВАНИЯ РЕШЕНИЯ ...»

Информатика, вычислительная техника и инженерное образование. – 2013. № 1 (12)

Раздел I. Эволюционное моделирование, генетические

и бионические алгоритмы

УДК 621.3.049.771.14:004.023

Э.В. Кулиев, А.А. Лежебоков

ЭФФЕКТИВНЫЙ СПОСОБ КОДИРОВАНИЯ РЕШЕНИЯ ДЛЯ ЗАДАЧИ

РАЗМЕЩЕНИЯ КОМПОНЕТОВ СБИС*

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

Размещение; генетический алгоритм; пчелиный алгоритм; кодирование; декодирование; программная реализация E.V. Kuliev, A.A. Lezhebokov

EFFICIENT WAY CODING SOLUTIONS FOR THE PLACEMEN PROBLEM

OF COMPONENTS VLSI

This paper describes a method of encoding – decoding solutions for the problem of component placement VLSI evolutionary computation methods have been studies to determine the effectiveness of the proposed method of coding solutions and select the cut points for the modified genetic operators. The results allow to conclude that the proposed method is more efficient encoding of the classical approach of 6-9%.



Accommodation; genetic algorithm; bee algorithm, coding, decoding, software implementation.

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

Это связано, в первую очередь, с тем, что эта задача является NP-полной, и разработать универсальный алгоритм, позволяющий находить точное оптимальное решение за приемлемое время затруднительно [1, 2]. Появление новых более совершенных средств вычислительной техники, дающих мощные вычислительные ресурсы, а также повышенные требования к проектируемым устройствам, все это является побудительной причиной разработки новых алгоритмов решения задачи размещения.

Научное направление Natural Computing, интенсивно развивающееся в последнее время, основано на принципах природных механизмов принятия решений * Работа выполнена при частичной поддержке РФФИ (проект 12-01-31356).

Информатика, вычислительная техника и инженерное образование. – 2013. № 1 (12) и включает генетические алгоритмы, нейросетевые вычисления, клеточные автоматы, муравьиные алгоритмы, метод роящихся частиц, табуированный поиск и др.

[3, 4, 6]. ACO-алгоритмы обладают способностью находить более высококачественные решения за приемлемое время В [5] приводится описание модифицированного алгоритма размещения на основе моделирования адаптивного поведения пчелиной колонии, авторами была предложена гибридная схема поиска решений задачи размещения на основе модифицированных алгоритмов, позволяющая управлять процессом поиска для получения более качественных решений. В данной работе рассматривается способ кодирования – декодирования решений для задачи размещения компонентов СБИС методами эволюционных вычислений.

Кодирование решения. В генетическом алгоритме решение представляется хромосомой, которая является линейной последовательностью генов. Хромосома соответствует определенному упорядочиванию вершин гиперграфа, описывающего схему проектируемого устройства. Обычно число генов в хромосоме (иначе говоря – размер хромосомы) равно числу вершин в графе [2].

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

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

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

–  –  –

Рис. 1. Способ кодирования решения задачи размещения Информатика, вычислительная техника и инженерное образование. – 2013. № 1 (12) Новый подход к кодированию хромосомы для задачи размещения заключается в следующем.

Каждому гену хромосомы ставится в соответствие определнный статус:

фиксированный элемент (позиция элемента, который кодируется текущим геном, является постоянной, и в процессе выполнения генетических операторов ген не меняет своего значения, то есть положения в решетке);

свободный элемент (элемент, который не инцидентен ни одной цепи, такие элементы размещаются в самую последнюю очередь);

максимально-связный элемент (элемент с максимальной локальной степенью);

элемент цепи критического пути (элемент, который принадлежит цепи, входящей в критический путь схемы).

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

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

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

В случае решения задачи размещения с описанной методикой кодирования хромосом, предлагается выбирать случайным образом точки разреза в местах (генах) перехода на новую строку решетки. Аналогичным образом будут выбираться точки разреза при выполнении оператора мутации (ОМ).

Для хромосом больших размеров применяется такой же подход, но используются операторы с множеством точек разреза. Вероятность выживания хромосомыпотомка после выполнения модифицированного одноточечного проблемноориентированного оператора кроссинговера (ПООК), может быть выражена формулой (L – длина хромосомы, N – число участков между точками скрещивания):

N P(s)[ ПОOK] 1 L 1.

На рис. 2 представлен пример выбора точек разреза для ОК или ОМ.

Информатика, вычислительная техника и инженерное образование. – 2013. № 1 (12)

–  –  –

Для хромосом больших размеров применяется такой же подход, но используются операторы с множеством точек разреза. Вероятность выживания хромосомыпотомка после выполнения модифицированного одноточечного проблемноориентированного оператора кроссинговера (ПООК), может быть выражена формулой (L – длина хромосомы, N – число участков между точками скрещивания):





N P( s )[ ПОOK] 1.

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

Для сравнения были выбраны алгоритмы со следующими характеристиками:

эволюционный алгоритм (ЭА): число итераций – 1000, размер популяции – 500, вероятность ОК – 80%, вероятность ОМ – 10%, селекция – случайная, отбор – элитный, способ кодирования – классический, критерий – суммарная длина связей;

гибридный алгоритм (ГбрА): число итераций – 1000, размер колонии – 500, количество колоний – 4, уровень миграций – средний, способ кодирования – предложенный выше, критерий – суммарная длина связей.

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

–  –  –

Рис. 3. Зависимость качества ЦФ от способа кодирования Заключение. Результаты исследований позволяют сделать вывод о том, что предложенный способ кодирования является эффективнее классического подхода на 6-9%. Использование предложенного подхода к кодированию в совокупности с гибридной схемой поиска позволяет эффективно управлять поиском и получать квазиоптимальные решения за полиномиальное время.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Лебедев Б.К., Лебедев В.Б. Размещение на основе метода пчелиной колонии // Известия ЮФУ. Технические науки. – № 12 (113). – С. 12-19.

Курейчик В.В., Родзин С.И. О правилах представления решений в эволюционных алгоритмах // Известия ЮФУ. Технические Науки. – 2010. – № 7 (108). C. 13-21.

Курейчик В.В., Запорожец Д.Ю. Роевой алгоритм в задачах оптимизации // Известия 3.

ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 28-32.

Курейчик В.В., Курейчик Вл.Вл. Архитектура гибридного поиска при проектировании 4.

// Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 22-27 Кулиев Э.В., Лежебоков А.А. О гибридном алгоритме размещения компонентов СБИС 5.

// Известия ЮФУ. Технические науки. – 2012. – № 11 (136). С. 188-193.

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

Научно-технический журнал. – Ростов н/Д: Изд-во РГУПС, 2011. – № 3. – С. 91-96.

Кулиев Эльмар Валерьевич Федеральное государственное автономное образовательное учреждение высшего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ», Таганрог, Россия 347928, Таганрог, Ростовская область, ГСП-17А, пер. Некрасовский, 44 Тел.: 8(8634) 37-16-51.

E-mail: elmar_2005@mail.ru Кафедра систем автоматизированного проектирования; аспирант

Информатика, вычислительная техника и инженерное образование. – 2013. № 1 (12)

Лежебоков Андрей Анатольевич Федеральное государственное автономное образовательное учреждение высшего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ», Таганрог, Россия E-mail: legebokov@gmail.com 347928, г. Таганрог, Некрасовский, 44.

Тел.:8(8634) 37-16-51.

Кафедра систем автоматизированного проектирования, к.т.н., ассистент.

Kuliev Elmar Valerievich Autonomous federal state institution of higher professional education "Southern Federal University", Taganrog, Russia 347928, Taganrog, GSP-17A, per. Nekrasovskij, 44 Phone: 8(8634) 37-16-51.

E-mail: elmar_2005@mail.ru Department of Computer Aided Design Lezhebokov Andrey Anatolyevich Autonomous federal state institution of higher professional education "Southern Federal University", Taganrog, Russia E-mail: legebokov@gmail.com 44, Nekrasovskiy, Taganrog, 347928, Russia.

Phone: 8(8634) 37-16-51.

The Department of Computer Aided Design, PhD, assistant.





Похожие работы:

«Тематический раздел: Теоретическая и компьютерная химия. Полная исследовательская публикация Подраздел: Физическая органическая химия. Регистрационный код публикации: 11-27-14-1 Публикация доступна для обсуждения в рамках ф...»

«ПРОГРАММА вступительного экзамена по ПРИКЛАДНОЙ ИНФОРМАТИКЕ в магистратуру по направлению "Прикладная информатика"ВВЕДЕНИЕ Основу программы составили ключевые положения курсов программы подготовки бакалавров по направлению "Прикладная информати...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОУ ВПО "АЛТАЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ" ПРОГРАММА Вступительного экзамена по прикладной информатике в магистратуру по направлению "Прикладная и...»

«ПРОГРАММНЫЕ СИСТЕМЫ: ТЕОРИЯ И ПРИЛОЖЕНИЯ ISSN 2079-3316 № ?, 2014, c. ??–?? УДК 519.612.2 Р. А. Ахметшин, И. И. Газизов, А. В. Юлдашев Комбинированный подход к построению параллельного предобуславливателя для решения задачи фильтрации углеводородов в пористой среде на...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

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