автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка и исследование подсистемы биоинспирированного поиска оптимальных решений в САПР

Запорожец Дмитрий Юрьевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ПОДСИСТЕМЫ БИОИНСПИРИРОВАННОГО ПОИСКА ОПТИМАЛЬНЫХ РЕШЕНИЙ В

САПР

05.13.12-Системы автоматизации проектирования (вычислительная техника и информатика)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 I нии 2015

Таганрог, 2015

005564262

005564262

Работа выполнена на кафедре систем автоматизированного проектирования Института компьютерных технологий и информационной безопасности ФГАОУ ВО «Южный федеральный университет» (ЮФУ).

Научный руководитель:

Официальные оппоненты:

Курейчик Владимир Викторович, доктор технических наук, профессор, ФГАОУ ВО «Южный федеральный университет», кафедра систем автоматизированного проектирования, зав. кафедрой

Гатчин Юрий Арменакович, доктор технический наук, профессор, СПб НИУ ИТМО, кафедра проектирования и безопасности компьютерных систем, зав. кафедрой

Ведущая организация:

Береза Андрей Николаевич, кандидат технических наук, доцент, филиал ДГТУ в г. Шахты, кафедра информационных систем и радиотехники Института сферы обслуживания и предпринимательства, доцент кафедры

ФГБОУ ВПО «Волгоградский государственный технический университет»

Защита состоится «17» декабря 2015 г. в 16-00 часов на заседании диссертационного совета Д212.208.22 при ФГАОУ ВО «Южный федеральный университет» по адресу: 347928, Россия, Ростовская обл., г. Таганрог, ГСП-17А, пер. Некрасовский, 44, аудитория Д-406.

С диссертацией можно ознакомиться в зональной научной библиотеке ФГАОУ ВО ЮФУ им. Ю. А. Жданова, расположенной по адресу: 344103, г. Ростов-на-Дону, ул. Пушкина, 148, а также на библиотечном портале ЮФУ http://hub.sfedu.ru/diss/announcements/

Автореферат разослан «АР » С^ьУл^АЛ 2015 г.

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

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

А.Н. Целых

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

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

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

Основным средством достижения этих целей при проектировании СБИС являются системы автоматизированного проектирования.

В настоящее время при разработке СБИС выполняется общепринятая последовательность этапов проектирования: системная спецификация, функциональное проектирование, алгоритмическое проектирование, конструкторское проектирование, верификация, технологическое проектирование (изготовление кристаллов (чипов), сборка, тестирование и контроль.

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

Большой вклад в разработку и исследование интеллектуальных САПР, эволюционного моделирования и биоинспирированного поиска внесли Д.И. Батищев, A.M. Бершадский, JI.C. Берштейн, Г.Г. Казенов, В.М. Курейчик, А.Н. Мелихов, Ю.А. Гатчин, Д. Холланд, И.П. Норенков, Г.Г. Рябов, Н. Шервани, Ю.О. Чернышев, А.П. Карпенко, В.Н. Гридин, И.Л Букатова и многие другие.

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

Для достижения сформулированной цели в диссертации были поставлены следующие основные задачи:

1. Сформулировать общие принципы разработки методов и алгоритмов биоинспирированной оптимизации.

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

3. Построить модель организации подсистемы биоинспирированного поиска.

4. Разработать атомарные поисковые процедуры (АПП) на основе генетического, эволюционного, муравьиного, пчелиного и бактериального алгоритма.

5. Разработать гибридный биоинспирированный алгоритм размещения фрагментов СБИС с использованием построенной подсистемы биоинспирированного поиска.

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

Разработанные в рамках данной диссертационной ¡ работы, положения подтверждаются результатами экспериментальных исследований,.. .

Научная новизна работы состоит в следующем. . . г. . -

1. Разработана подсистема биоинспирированного поиска для решения задач конструкторского проектирования СБИС, основанная на моделировании поведения биологических видов и позволяющая сократить время реализации алгоритмов для решения различных задач автоматизированного проектирования (пункт 4 паспорта специальности 05.13.12).

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

3. Разработан модуль создания новых механизмов оптимизации, основанных на использовании методов генетического поиска, для уменьшения времени, затрачиваемого на разработку алгоритмов оптимизации при решении задач конструкторского проектирования СБИС (пункт 3 паспорта специальности 05.13.12).

4. Разработаны эволюционный, генетический, . муравьиный, пчелиный и бактериальный • алгоритмы решения задачи размещения фрагментов СБИС, позволяющие находить наборы оптимальных и квазиоптимальных решений за полиномиальное время (пункт 3 паспорта специальности 05.13.12).

5. Построен новый гибридный алгоритм решения задачи размещения фрагментов СБИС. с использованием разработанной подсистемы биоинспирированного поиска, позволяющий эффективно решать задачу размещения фрагментов СБИС за полиномиальное время (пункт 3 паспорта специальности 05.13.12).

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

Реализация и внедрение результатов работы. Результаты диссертационной работы использовались в ряде НИОКР, выполненных в Институте компьютерных

технологий и информационной безопасности Южного Федерального университета, направленных на решение задач конструкторского проектирования. К наиболее важным результатам следует отнести:

1. Участие в реализации гранта РФФИ №13-01-00371 «Разработка теории и принципов построения интеллектуальных систем проектирования для решения задач разбиения СБИС на основе биоинспирированных методов».

2. Участие в реализации гранта РФФИ №14-07-00829 «Разработка комплекса гибридных моделей, методов и алгоритмов поддержки принятия решений для интеллектуальных информационных систем транспортной логистики».

3. Участие в реализации гранта РФФИ №15-01-05669 «Разработка основ теории и принципов построения иерархических клиент-серверных архитектур для реализации быстродействующих подсистем конструкторского проектирования СБИС».

4. Участие в реализации гранта РФФИ №12-01-31356 «Разработка теоретических основ и принципов размещения компонентов СБИС на основе адаптивных процедур».

5. Участие в реализации ГБ 213.01-11/2014-56ПЧ на выполнение проектной работы в части государственного задания МИНОБРНАУКИ России в сфере научной деятельности.

Материалы диссертации внедрены в учебный процесс кафедры систем автоматизированного проектирования Южного федерального университета.

Апробация. Основные результаты, представленные в диссертационной работе, обсуждались на международных, всероссийских и региональных научных конференциях: конгрессе по интеллектуальным системам и информационным технологиям «AIS-lT'll» (Дивноморское, 2011г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2011» («ИС-2011»), X Всероссийская научная конференция молодых ученых аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2012г.), конгресс по интеллектуальным системам и информационным технологиям «AIS-IT'12» (Дивноморское, 2012г.), конгрессе по интеллектуальным системам и информационным технологиям «IS-IT'14» (Дивноморское, 2014г.), конгрессе по интеллектуальным системам и информационным технологиям «IS-IT'15» (Дивноморское, 2015г.).

Публикации. По теме диссертационной работы опубликовано 19 печатных работ, в числе которых 10 - в изданиях, рекомендованных ВАК РФ; 3 - в изданиях, индексируемых в базе данных Scopus; 4 Свидетельства о государственной регистрации программ для ЭВМ.

Структура и объем работы. Диссертационная работа включает следующие разделы: введение, четыре раздела и заключение, изложенные на 147 страницах, содержит 55 рисунков, 8 таблиц, 115 наименований библиографии и приложение.

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

В первом разделе диссертационной работы рассмотрены основные современные тенденции в развитии технологий проектирования и производства СБИС. Приведена классификация различных типов СБИС и описаны их основные

характеристики. В работе исследованы маршруты проектирования СБИС, описаны их основные шаги, подробно рассмотрен этап конструкторского проектирования.

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

Пусть Х1, ..., Хц размещаемые на коммутационном поле фрагменты СБИС, каждый Х;|1 < « < N. задается геометрическими размерами: высотой ^ и шириной N = {п, | 1 = 1,ш} - список цепей, соединяющих фрагменты. Ь| - длина цепи каждая П; | I = 1,т. Задача размещения заключается в нахождении прямоугольных областей на коммутационном поле для каждого размещаемого элемента из В и определяется множеством областей Я = {г, | 1 = 1, п) таким, что каждый блок располагается в соответствующей прямоугольной области таким образом, что л имеет высоту Ь; и ширину и координаты щ,

г( =< и(|(<,и'1,А( >, (1)

Каждая цепь п, - представляется в виде последовательного списка соединения элементов цепи (кортежа).

п( = </?„,),КП( Ей, (2)

где - подмножество областей из Я, входящих в состав цепи п(.

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

Запишем критерий следующим образом:

РОО = £/(*/). ,(3)

где N - множество размещенных фрагментов, щ - ¡-ая цепь, ш = [N1 - количество цепей.

|Я(|-1

Пщ) = ¿¡=2 (4)

¡=1

где й(?}, ?у+1) - расстояние между двумя соседними фрагментами цепи.

(5)

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

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

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

Стандартизированное описание АПП

Рисунок 1 - Модуль создания новых механизмов оптимизации

Вводится понятие «Атомарная поисковая процедура» (АПП) - это алгоритм, имеющий унифицированное описание (интерфейс) и принимающий на вход закодированное решение и возвращающий на выходе одно или несколько квазиоптимальных закодированных решений. Интерфейс АПП (АППИНТ) может быть описан следующим образом:

АППИНТ = (id, solution, objectiveFunction.attributesList),

где ¡'¿-идентификатор алгоритма; solution — начальное закодированное решение; objectiveFunction - целевая функция; attributeList - список атрибутов, необходимых для работы алгоритма, например, в качестве атрибута может выступать число итераций.

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

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

позволяющие сократить время выполнения алгоритма в целом за счет генерации только приемлемых решений.

<гЬаг^ Ы>"1пОД«1Ро1|Л"/>

(йм 1(1»" юахг?1оы" р»г«Л»"11Ш:1»1Ро1гЛ" сМЫ="ЬееА1еогКЬтЯ1о*"> «иЬПом 1<1="ЬееД1^Р1<:1и|Р1он" сНШг'ЬееАХеоггНм»") <5еагсЬ х<1«"ЬееА1еогИЬ|Пв 5о1и±1оп=*1п111в15о1и110п( о^есУуеРипс±1ап»иса1си1аЬа()-а«г1Ьи1мигЫш«ега^оп=1ве,Ь1ос1р=10,Ьте5=500" </5иЬ«ст»

рагег^вмЬееА1вор1ЪЬ»Р1ома> <5еагсН 1<1»"Е»1е«сА^огШ1" »в11Л1оп»"гв$и11(ЬевА^огНИ)"

</сиЬПон>

</Пон>

</а1вог!Йт>

Рисунок 2 - Пример стандартизированного ХМЬ-описания

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

Построенная подсистема биоинспирированного" поиска была использована для разработки иерархического алгоритма решения одной из задач конструкторского проектирования - размещение фрагментов СБИС.

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

Для конструирования эффективных гибридных поисковых процедур решения задачи размещения фрагментов СБИС был разработан комплекс АПП, составляющих основу будущего гибридного алгоритма. Среди них автор выделил: модифицированный эволюционный алгоритм, основанный на моделировании эволюционных процессов в живой природе и использовании модифицированного оператора мутации; модифицированный генетический алгоритм, использующий специфичные методы скрещивания альтернативных решений для получения легальных решений; модифицированный муравьиный алгоритм, основанный на применении классического муравьиного поиска с запретами (табу-лист); модифицированный пчелиный алгоритм, использующий известную парадигму «разделяй и властвуй» для разделения всего пространства поиска на части и осуществления параллельного поиска в каждой части; модифицированный бактериальный алгоритм, впервые примененный для решения задачи размещения фрагментов СБИС.

Рисунок 3 — Схема работы подсистемы биоинспирированного поиска

Идея бактериального алгоритма размещения фрагментов СБИС, представленного на рисунке 4, состоит в моделировании поведения бактерии Е.соН.

Рисунок 4 — Схема работы алгоритма размещения фрагментов СБИС на основе бактериальной оптимизации

Жизненный цикл бактерии состоит из следующих действий: 1. В нейтральной среде поиск выполняется путем чередования кувырков и прямолинейного движения.

2. В среде, содержащей питательные вещества (атграктанты), перемещение осуществляется по градиенту аттрактанта, т.е. бактерия стремится в более благоприятную окружающую среду.

3. В среде, содержащей вредные вещества (репелленты), бактерия движется в направлении противоположном градиенту репеллента, и, таким образом, избегает попадания в неблагоприятную окружающую среду.

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

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

1. Задается начальная точка агента.

2. Генерируется шаг агента на заданном отрезке целых чисел.

3. Производится движение агента на заданное количество шагов.

4. Выполняется парная перестановка между начальным и конечным положением агента. Вычисляется приращение ЦФ.

5. Значение приращения прибавляется к значению оценки «здоровья» агента.

6. Если приращение отрицательно, агент меняет направление движения.

7. Если здоровье агента меньше 0, для текущего решения поиск прекращается.

Пример движения агента с начальным индексом 3 с шагом 4 представлен на

рисунке 5.

------------- ,-------- .-----------

Значения 1 6 -1 3 9 -2 8 >г 5 7 "Щ 4 2

Индекс 1 2 4 5 6 ¡■■7у 8 1: 9 10 11 12 13 14 15 16 щ

Рисунок 5 — Пример движения агента

Механизм репродукции заключается в следующих шагах:

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

2. Дублирование первой половины решений. Альтернативные решения, которые попали в первую половину отсортированного списка, копируются и помещаются в текущую популяцию.

3. Для копий произвольно меняется индекс начального расположения агента, значение «здоровья» гена приравнивается к начальному значению Н0.

Механизм уничтожения включает 4 следующих шага.

1. Удаляются все альтернативные решения, со значением «здоровья» агента меньшим, либо равным 0.

2. Популяция сортируется по возрастанию значения «здоровья» агентов.

3. Если после удаления текущие размер популяции < то произвольно генерируется недостающее количество решений (Ы8 - М5сиг)

4. Если после удаления текущий размер популяции Ы8сиг>Ы5, то продолжается удаление альтернативных решений с наименьшим значением «здоровья» до тех пор, пока N5"" не станет равным N3.

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

( Начало

Бактериальный алгоритм 1 (5) I Бактериальный алгоритм 2 (5) I - ■ • - | Бактериальный алгоритм N (5) [

I I I

Пчелиный алгоритм 1 (1) | Пчелиный алгоритм 2 (1) I Пчелиный алгоритм N (1) |

I I I

[ Эволюционный алгоритм 1 (2) | | Эволюционный алгоритм 2 (2) [-■ - | Эволюционный алгоритм N (2) |

Выбор решения

С

Конец

3

Рисунок 6 - Результат работы подсистемы генерации алгоритмов

Его идея состоит в параллельном запуске блока из трех алгоритмов: пчелиного, бактериального и эволюционного. Альтернативное решение имеет вид: <5,1,2,-2,-2>.

Пример работы разработанного алгоритма размещения фрагментов СБИС, представленного на рисунке 6, рассмотрен на тестовой схеме, изображенной на рисунке 7. Для упрощения примера, фрагменты схемы СБИС представлены в виде прямоугольных областей. Список цепей задан множеством кортежей: С{с,<1,6,15,5,4,11>, с2<2,7,8,9,10>, с3<3,5,4,14,13>, с4<6,15,12,16>, с5<7,1 6,3,6,15>, с6<17Л8,1,6,9>, с7<9,19,5,4>, с8<1 1,7,6,10>, с9<6,8,2,12>, с10<7,5,3,2>}. Автором полностью описан каждый шаг работы параллельного гибридного алгоритма. Оценка качества полученных решений производилась на основе выражения 3.

Результат работы представлен на рисунке 8._

1

15 16

19

12

10

11 12 13

14

17

18

19

Рисунок 7 — Тестовая схема

Рисунок 8 - Результат работы гибридного параллельного алгоритма

В четвертом разделе представлена программная реализация подсистемы биоинспирированного поиска оптимальных решений в САПР в виде клиент-серверного приложения реализованного на языке программирования JAVA. Основные окна изображены на рисунке 9.

актирование: Para&t aTaoitthm

'ШШ^ШШШШШШШШ.

Серии экспериментов

Серий: [ып benchmark Параметр: iitneas

Рисунок 9 - Основные окна подсистемы биоинспирированного поиска

В качестве примера работы модуля экспорта автором был приведен процесс интеграция разработанной подсистемы биоинспирированного поиска с открытой САПР К>САО, предназначенной для разработки печатных плат. Имплементирована ОЬЬ-обертка для скомпилированной в виде ]аг-файла библиотеки по спецификации системы КьСАБ. Так как САПР «¡-САП предназначена для работы с печатными платами, разработанный алгоритм был применен для размещения компонентов блока отсечки ультразвукового дефектоскопа. Результаты размещения с использованием алгоритмов, встроенного в систему Кл-САО и гибридного алгоритма представлены на

Рисунок 10 - Результат размещения алгоритмов, встроенного в систему Ki-CAD

Рисунок 11 - Результат размещения гибридного алгоритма

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

многоуровневых поисковых механизмов, и результатов полученных с помощью известных разработанных алгоритмов. Результаты вычислительного эксперимента, приведенные в таблице 1 и на рисунке 12, показали преимущество предложенного в работе подхода к решению задач размещения по сравнению с существующими аналогами на 9,76%.

Тестовые схемы

s

0

•a

s s -2

4 -4

Ш -6

s

s V -8

3 « -10

CL s -12

D. s -14

<5^

' /

# ,

<V <5

Рисунок 12 - Приращение длины проводников

Тестовые схемы Capo 8.6 Feng Shui 2.0 Dragon 2.23 Гибридный алгоритм

Название • Число элементов длина, м длина, м длина, м длина, м 1 приращение длины (Capo 8.6), м приращение длины (Capo 8.6), % приращение длины (Feng Shui 2.0), м приращение длины (Feng Shui 2.0), % приращение длины (Dragon 2.23), м приращение длины (Dragon 2.23), %

ibmOl 12752 4,97 4,87 4,42 4,32 -0,65 -13,08 -0,55 -11,3 -0,1 -2,26

ibm02 19601 15,23 14,38 13,57 13,4 -1,86 -12,21 -1,01 -7,02 -0,2 -1,47

ibm03 23136 14,06 12,84 12,33 12,0 -2,05 -14,58 -0,83 -6,46 -0,32 -2,60

ibm04 27507 18,13 16,69 15,41 14,8 -3,28 -18,09 -1,84 -11,0 -0,56 -3,63

ibm05 29347 44,73 37,3 36,38 36,1 -8,61 -19,25 -1,18 -3,16 -0,26 -0,71

ibm06 32498 21,96 20,27 20,38 19,0 -2,95 -13,43 -1,26 -6,22 -1,37 -6,72

ibm07 45926 36,06 31,5 29,97 28,3 -7,73 -21,44 -3,17 -10,1 -1,64 -5,47

ibm08 51309 37,89 34,14 32,2 30,0 -7,87 -20,77 -4,12 -12,1 -2,18 -6,77

ibm09 53395 30,28 29,86 28,1 26,9 -3,43 -11,33 -3,01 -10,1 -1,25 -4,45

ibmlO 69429 61,25 57,99 . 57,2 55 -6Д5 -10,20 -2,99 -5,16 -2,2 -3,85

ibmll 70558 46,45 43,28 40,77 37,1 -9,33 -20,09 -6,16 -14,2 -3,65 -8,95

ibml2 71076 81,55 75,91 71,03 69,1 -12,4 -15,24 -6,79 -8,9 -1,91 -2,69

ibml3 84199 56,47 54,09 50,57 47,2 -9,24 -16,36 -6,86 -12,7 -3,34 -6,60

В заключение диссертационной работы изложены основные выводы и результаты диссертационной работы.

В приложении даны копии актов внедрения, Свидетельства об официальной регистрации программы для ЭВМ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

7. Проведены серии экспериментальных исследований, которые позволили эмпирически подтвердить оценки временной и пространственной сложности. Проведенные эксперименты показали, что качество полученных решений на 9,76% превосходит результаты размещения, полученные с использованием известных алгоритмов Capo 8.6, Feng Shui 2.0, Dragon 2.23.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Основные положения диссертации опубликованы в 19 работах и 4 свидетельствах о государственной регистрации программ для ЭВМ, в том числе:

Статьи в ведущих научных журналах и изданиях, рекомендованных ВАК

РФ:

1. Запорожец Д.Ю., Курейчик В.В. Роевой алгоритм в задачах оптимизации // Известия ЮФУ. Технические науки. 2010. № 7 (108). С. 28-32.

2. Запорожец Д.Ю., Курейчик В.В. Современные проблемы при размещении элементов СБИС // Известия ЮФУ. Технические науки. 2011. № 7 (120). С. 68-73.

3. Заруба Д.В., Лежебоков A.A. Об одном способе кодирования решения для задачи размещения // Известия ЮФУ. Технические науки. 2012. № 11 (136). С. 183-; 188.

4. Запорожец Д.Ю., Заруба Д.В:; Курейчик В.В. Применение генетического алгоритма решения: задачи' трехмерной упаковки // Известия ЮФУ. Технические науки. 2012. № 7 (132). С. 8-14. , .

5. Запорожец Д.Ю., Курейчик В.В. Гибридный алгоритм решения задач транспортного типа // Известия ЮФУ. Технические науки. 2013. № 7 (144). С. 80-85. :

6.'Запорожец Д.Ю:, Кудаев А.Ю., Лежебоков А.А-. Многоуровневый алгоритм решения задачи параметрической оптимизации на основе биоинспирированных эвристик// Известия Кабардино-Балкарского научного центра РАН.2013. № 4 (54). С. 21-28.

7. Запорожец Д.Ю., Курейчик В.В., Заруба Д.В. Муравьиный алгоритм определения критических связей в СБИС // Проблемы разработки перспективных микрб- и наноэлектронных систем (МЭС). 2014. № 2. С. 107-112.

8. Запорожец Д.Ю., Курейчик В.В., Заруба Д.В. Иерархический подход при размещении компонентов СБИС // Известия ЮФУ. Технические науки. 2014. №7 (156). С. 75-84.

'9. Запорожец Д.Ю., Кулиев Э.В., Ксалов A.M., Кудаев А.Ю., Коков A.A., Ошхунов М.М. Биоинспирированный поиск при решении задачи размещения компонентов СБИС // Известия Кабардино-Балкарского научного центра РАН. 2014. № 6 (62). С. 58-65.

10. Запорожец Д.Ю., Курейчик В.В., Заруба Д.В. Биоинспирированный алгоритм компоновки блоков ЭВА на основе модифицированной раскраски графа // Известия ЮФУ. Технические науки. 2015. № 4 (165). С. 6-14.

Публикации в изданиях, индексируемых в базе данных Scopus;

11. Zaporozhets D.Yu., Kureichik V.V., Zaruba D.V. Hybrid bionic algorithms for solving problems of parametric optimization // World Applied Sciences Journal, 23 (8), pp. 1032-1036. (2013)

12. Zaporozhets D.Yu., Kureichik V.V., Zaruba D.V. Representation of solutions in genetic VLSI placement algorithms // Proceedings of IEEE East-West Design and Test Symposium, EWDTS 2014.

13. Zaporozhets D.Yu., Kureichik V.V., Zaruba D.V. Hierarchical approach for VLSI components placement // Advances in Intelligent Systems and Computing, 347, pp. 79-87.(2015)

Публикации в других изданиях: • -

14. Запорожец Д.Ю., Курейчик В.В. Применение роевого алгоритма для решения задачи размещения элементов СБИС // Информатика, вычислительная техника и инженерное образование. 2010. № 1. С. 13-18

15. Запорожец Д.Ю., Курейчик В.В. Гибридный алгоритм в задачах оптимизации // Труды конгресса по интеллектуальным системам и информационным технологиям «IS- IT'l 1». Научное издание в 4-х томах. - М.: Физматлит, 2011. - Т.З. -С.181-186

16. Запорожец Д.Ю. Об одном роевом алгоритме // Неделя науки - 2011: Материалы научных работ. - Таганрог: Изд-во ТТИ ЮФУ, 2011. С. 60-63

17. Запорожец Д.Ю., Заруба Д.В., Курейчик В.В. Использование методов эволюционной оптимизации для решения задач трехмерной упаковки // Информатика, вычислительная техника и инженерное образование. 2012. № 2 (9). С. 1-9.

18. Запорожец Д.Ю., Курейчик В.В. Гибридный алгоритм размещения разногабаритных элементов СБИС // X Всероссийская научная конференция молодых ученых аспирантов и студентов «Информационные технологии, системный анализ и управление». Таганрог: Изд-во ТТИ ЮФУ, 2012. - Т. 1. - С. 61 -65

19. Запорожец Д.Ю., Кулиев Э.В., Купов И.О. Разработка гибридного алгоритма размещения элементов СБИС // Труды конгресса по интеллектуальным системам и информационным технологиям «18-1Т'14». Научное издание в 4-х томах. - М.: Физматлит, 2014. - Т.З. - С. 68-73

Свидетельства о регистрации программ на ЭВМ:

20. Свидетельство о государственной регистрации программы для ЭВМ №2012610327, 2011 «Программа размещения блоков СБИС на основе многоуровневой оптимизации»

21. Свидетельство о государственной регистрации программы для ЭВМ № 2012610328,2012 «Программа размещения блоков СБИС на основе роевого метода»

22. Свидетельство о государственной регистрации программы для ЭВМ №2013614650, 2013 «Программа размещения блоков СБИС гибридным алгоритмом, основанным на эволюционных эвристиках и поведении колонии муравьев»

23. Свидетельство о государственной регистрации программы для ЭВМ № 2014617923, 2014 «Программная реализация гибридного алгоритма размещения фрагментов схемы СБИС»

Личный вклад автора. В работах:

[1,7,14,16] - автором разработаны биоинспирированные алгоритмы решения оптимизационных задач.

[2] - автором выделены основные проблемы при размещении фрагментов СБИС и предложены пути их решения

[3,12] - автором предложены механизмы представления альтернативных решений для задачи размещения фрагментов СБИС

[5,6,8,11,13,15,18,19] - автором разработаны гибридные биоинспирированные алгоритмы решения задач оптимизации, в том числе и размещения фрагментов СБИС.

Научному руководителю д.т.н., профессору Курейчику В.В. принадлежит постановка задачи диссертационной работы, участие в обсуждении и интерпретации результатов экспериментальных исследований.

Запорожец Дмитрий Юрьевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ПОДСИСТЕМЫ БИОИНСПИРИРОВАННОГО ПОИСКА ОПТИМАЛЬНЫХ РЕШЕНИЙ В

САПР

Автореферат Подписано в печать «18» сентября 2015 Формат 60^84 1 /16 Бумага офсетная. Ризография. Усл. печ. л. 1,0. Уч.-изд. л. 1,6. Тираж 100 экз. Заказ

Отпечатано в Секторе обеспечения полиграфической продукцией кампуса в г. Таганроге отдела полиграфической, корпоративной и сувенирной продукции ИПК КИБИ МЕДИА ЦЕНТРА ЮФУ. ГСП, 17А, Таганрог, 28, Энгельса, 1. Тел. (8634) 37-17-17