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

Полупанова Елена Евгеньевна

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

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

АВТОРЕФЕРАТ

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

005049179

Таганрог —2012

005049179

Работа выполнена в Южном федеральном университете

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

Курейчик Владимир Викторович

Официальные оппоненты: Ковалев Сергей Михайлович

доктор технических наук, профессор ФГБОУ ВПО Ростовский Государственный Университет Путей Сообщения, кафедра «Автоматики и телемеханики на ж/д транспорте», профессор

Витиска Николай Иванович доктор технических наук, профессор ФГБОУ ВПО Таганрогский Государственный Педагогический Институт имени А.П. Чехова, кафедра «Информатики», профессор

Ведущая организация: ФГБОУ ВПО Кубанский государственный

университет.

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

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

Автореферат разослан 8 <

Ученый секретарь диссертационного совета Д 21 доктор технических наук, проф'

Целых А.Н.

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

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

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

В связи с трудностями создания общей математической модели, комплексно учитывающей все конструкторско-технологической особенности производства, не представляется возможным предложить алгоритм поиска оптимального конструктивного решения в едином цикле проектирования СБИС. Разработка и реализация алгоритмов и методов решения отдельных задач этапа конструкторского проектирования до сих пор остаётся актуальной проблемой. Решение этой проблемы неотъемлемо связано с развитием систем автоматизированного проектирования. К таким алгоритмам можно отнести методы эволюционного поиска и генетические алгоритмы (ГА). В последние годы широкое распространение также получили алгоритмы, основанные на роевом интеллекте (Swarm-based optimization algorithms (SOAs)). Эволюционные методы, генетические алгоритмы и алгоритмы роевого интеллекта являются одним из фундаментальных направлений научных исследований в области случайно-направленного поиска. Часто для сложной задачи необходимо найти любое решение, удовлетворяющее заданным ограничениям, поэтому целью биоинспирированных (эволюционно-генетических) алгоритмов (БА) является нахождение наилучшего решения поставленной задачи.

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

Таким образом, актуальность работы состоит в разработке новых алгоритмов и методов биоинспирированного поиска задачи разбиения схем при проектировании СБИС, позволяющих улучшить показатели качества, трудоёмкости и времени работы ЭВМ.

Цель работы состоит в разработке и исследовании биоинспирированных алгоритмов для решения задачи разбиения схем при проектировании СБИС.

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

1) анализ задачи разбиения при автоматизированном проектировании;

2) обоснование выбора математической модели схем для решения поставленной задачи;

3) теоретические исследования эволюционных, генетических алгоритмов, а также алгоритмов роевого интеллекта, ориентированных на решение задачи разбиения схем при проектировании СБИС;

4) построение модифицированных генетических процедур для решения задачи разбиения схем при проектировании СБИС;

5) построение новых архитектур биоинспирированного поиска ориентированных на решение задачи разбиения схем при проектировании СБИС;

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

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

Научная новизна диссертационной работы заключается в том, что:

1) разработана трёхуровневая архитектура биоинспирированного эволюци-онно-генетического поиска с динамическими параметрами, оптимизирующая процесс эволюционно-генетического поиска;

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

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

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

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

Положения выносимые на защиту:

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

2) процедуры локального улучшения и преодоления преждевременной сходимости биоинспирированного алгоритма;

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

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

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

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

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

3) биоинспирированный алгоритм и программа для разбиения СБИС, созданная в среде объектно-ориентированного программирования Borland С++ Builder™ 6.0.

Реализация результатов работы. Материалы диссертационной работы использованы в г/б № 12354 (1.04.01) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», г/б № 12355 (12.8.08) «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений», грант РФФИ № 12388 (№ 08 - 01 - 00473) «Разработка теории и принципов решения задач проектирования, оптимизации и принятия решений на основе биоинспирированных нечетких генетических и эволюционных методов», грант РФФИ № 12382 (№ 09- 01 - 00492) «Разработка общей теории и когнитивных принципов эволюционных вычислений», грант РФФИ № 12386 (№ 09- 01 - 00509) «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе бионического моделирования», грант РФФИ № 12383 (№ 09 - 07 - 00318) «Разработка новых принципов извлечения знаний на основе распределенных алгоритмов генетического программирования и роевого интеллекта», РНП № 2.1.2.1652 «Разработка теории и когнитивных принципов принятия решений на основе распределённых алгоритмов, инспирированных природными системами».

Теоретические и практические результаты работы прошли апробацию на научных семинарах (с 2008 по 2011гг., ТТИ ЮФУ), VI Всероссийской научно-практической конференции студентов, аспирантов и молодых учёных «МОЛОДЕЖЬ XXI ВЕКА —БУДУЩЕЕ РОССИЙСКОЙ НАУКИ» (г. Ростов-на-Дону, 2009), Международных научно-технических конференциях «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР» (CAD-2008) (Дивноморское, 2008 г.), Молодёжной научно-технической конференции «Интеллектуальные системы - 2009» («ИС-2009») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09» (Дивноморское, 2009 г.), Молодёжной научно-технической конференции «Интеллектуальные системы - 2010» («ИС-2010») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT 10» (Дивноморское, 2010 г.).

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

Работа содержит 136 стр., включая 46 рис., 15 табл., список использованных источников из 91 наименования, 12 стр. приложений, 3 акта об использовании и 1 свидетельство о регистрации программы для ЭВМ.

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

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

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

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

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

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

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

Во второй главе предложена архитектура биоинспирированного алгоритма.

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

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

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

В параграфе 2.4 предлагается в качестве методики формирования стартового множества решений использовать алгоритм колонии пчёл (Artificial Bee Colony (ABC)). Работа ABC — алгоритма зависит от следующих основных параметров:

1) общее число пчёл (ЛО;

2) общее число участков (т);

3) число элитных участков (е);

4) число пчёл-исследователей (п);

5) число пчёл-разведчиков(/-);

6) число пчёл (Г) на остальных (т е) участках;

7) начальный размер пространства для поиска, т.е. размер участков вместе с их окрестностями (5);

8) размер окрестности (О);

9) максимальное число итераций (I).

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

Таким образом, пчелиный алгоритм можно описать следующей последовательностью операций, показанной на рисунке 1.1:

Начала

Г1 - I -,

| Создание начальной популяции пчел 2 Определение месторасположения

источников нестара

' —

Оценка Цф пчел в популяции в соответствии

_с найденными нми Участками_

г- 4--I .

_Ранжирование пчел в популяции_

Выбор элитных участков г для поиска _решений в их окрестности_

["Задание размера окрестности для поиска О |

Рис. 1.1 Схема работы алгоритма колонии пчёл

1 ° В соответствии с постановкой задачи разбиения и исходными данными формируется популяция пчёл (хромосом).

2е Отправка пчёл-исследователей. Определение месторасположения источников нектара V,. Для каждой пчелы случайным образом задаётся начальная позиция х,\

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

4° Выбор пчёл с лучшими значениями ЦФ с каждого источника;

5° Если решение на исследуемом участке не улучшается с течением нескольких итераций переход к п.6, иначе п.З;

6° Отправка пчёл-разведчиков, осуществляющих случайный поиск и оценка

их ЦФ;

7° Формирование новой популяции пчёл, в состав которой будут входить как пчелы с лучшими значениями ЦФ с элитных участков, так и пчелы со случайными значениями ЦФ;

8° Конец работы алгоритма.

В параграфе 2.4 приводится упрощенная схема биоинспирированного алгоритма. БА представляет собой кортеж:

БЛ = <АВС, ГА, ЭА, ГВ, ОР, критерии останова>, (1.1)

В приведенной формуле 1.1:

АВС= (N, т, е, п, г, I, S, О, I), (1.2)

ЭА = (Р, N, МК, ЦФ, ОГР, ОМ, ОР, Т, pi, L). (1.3)

ГА - (Р, S, МК, ЦФ, ОГР, ГО, ОР, Т, pi, L). (1.4)

Здесь:

ABC - алгоритм пчелиной колонии, БА, ГА и ЭА - соответственно биоинспи-рированный, генетический и эволюционный алгоритмы разбиения, ГВ - генетический всплеск, ОР - оператор репродукции, Р - популяция альтернативных решений, N, S -динамические параметры, определяющие число запусков ГА и ЭА, соответственно, МК - метод кодирования хромосомы (альтернативного решения), ОГР- ограничения задачи разбиения, ГО - генетические операторы, Т - число поколений или генераций алгоритма, pi е Р — хромосома, a L — длина хромосомы.

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

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

В третьей главе осуществляется разработка биоинспирированного алгоритма разбиения.

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

Основным в эволюционном алгоритме является оператор мутации (ОМ), используемый в качестве процедуры локального улучшения. Локальное улучшение осуществляется в отношении перспективных хромосом-потомков, имеющих после крос-синговера и рекомбинации наилучшие значения целевой функции Р. Суть данного метода заключается в выполнении не менее 5 попыток улучшения Р с помощью микромутаций. Микромутация заключается в замене значений некоторых генов в родительской хромосоме на значения из диапазона номеров эвристик, т.е. М1 или М2. Если попытка оказывается неуспешной, то вновь гарантируется выполнение не менее Б-1 попыток. После чего осуществляется выбор Р хромосом нового поколения из наиболее перспективных хромосом, полученных путём применения генетических операторов. Другими словами, процесс локальное улучшение М1 останавливается по прошествии 5 неудачных попыток улучшить Р. Таким образом, параметр 5 используется для определения глубины микромутации (локального поиска).

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

В параграфе 3.2 разработана схема генетического алгоритма с динамическими параметрами. Для определения числа попыток выполнения генетических операторов используется параметр Ы, т.е. если при первом выполнении кроссинговера или инверсии получаются потомки с худшими, чем у хромосомы-родителя значениями целевой функции (ЦФ), то в наихудшем случае ГО выполнится N раз.

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

На начальном этапе работы алгоритма выполняется первая эвристика отбора Э1: производится оценка целевых функций для всех хромосом в стартовой популяции и фиксируется среднее значение К1=ЦФср. После этого, производится отбор хромосом, значение ЦФ которых соответствует условию ЦФ>К1. Процедура выполняется, пока 50-70% решений не будут удовлетворять заданному условию.

Далее начинается этап генетического поиска. Применение ГО к хромосомам стартовой популяции осуществляется согласно значению динамического параметра N. В начале работы генетического алгоритма для каждого ГО задается значение параметра Ы, где N - некоторое натуральное число из диапазона 4 < N < Р , Р — мощность стартового множества решений, а N кратно двум, т.к., например, в реализации оператора кроссинговера, участвует пара хромосом. Эти хромосомы как раз и будут иметь возможность участвовать в процедуре генетического поиска. Таким образом, для каждого ГО мощность подмножества хромосом участвующих в процессе генетического поиска может быть разной и равняется N для текущей генерации алгоритма. Из популяции мощностью N случайным образом выбираются хромосомы для выполнения ГО. Инициализация параметра N производится заново после каждой генерации ГО, поскольку после выполнения ГО этот параметр изменяется.

Ё[ализ поступивших данных задачи и кодирование решений

Э2 | Задание К2=Цфтпах-ЦФср+соп51

28 Заполнение

оставшейся Р из Р2

Копирование Р1 в Р

т

эз

с

Нет

29 Формирование новой _популяции Р =Р1+Р2

Формирование подпопуляции размера И.

Принудительная мутация _М2_

| Формирование новой популяции |

С

Конец

3

Рис. 1.2 Архитектура эвристического эволюционно-генетического алгоритма

Необходимо заметить, что для отбора решений в стартовую и последующие популяций используется процедура генетического "всплеска". Суть данной процедуры заключается в том, что популяция делится на две подпопуляции Р1 и Р2, причём в первой PI, размер которой задаётся в начале работы алгоритма, располагаются хромосомы с максимальным значением ЦФ, а во второй популяции Р2 хромосомы, сгенерированные случайным образом. Размер второй популяции вычисляется относительно первой, а размер общей популяции равен:

Р = Р1+Р2, (1.5)

Далее выполняется локальное улучшение Ml. Суть операций, выполняемых на данном этапе поиска, заключается в замене значений некоторых генов в родительских хромосомах на случайные значения. После чего из наиболее перспективных мутированных хромосом (популяция Р1) и хромосом, сгенерированных случайно (популяция Р2) формируется Р хромосом нового поколения. Локальное улучшение Ml заканчивается после S случившихся подряд неудачных попыток. При этом глубина локального поиска S задаётся динамически, т.е. это случайное число из диапазона от 1 до 5 (1 <S<5).

Эвристика 32 начинает свою работу с генерации порога К2 = ЦФтах -ЦФср + const, при этом ЦФср < К2 < ЦФтах. После чего начинается отбор решений в популяцию потомков по правилам, аналогичным правилам, используемых в Э1.

В основу третьей эвристики ЭЗ положена процедура принудительной мутации М2. Суть её заключается в том, что если по истечении S попыток улучшить F при помощи процедуры Ml не удалось, т.е. не найдено решение с ЦФ лучшей, чем у «лучшего» родителя, то по окончании работы алгоритма, заносятся все потомки с «худшими» значениями ЦФ.

Таким образом, в предложенном алгоритме в рамках "вариативного метода" применяются эвристики Э1, Э2 и ЭЗ. В Э1 фигурирует постоянный порог К1 = const. В Э2 величина порога К2, где К1 < К2, зависит от максимального значения ЦФ на данном этапе поиска, т.е. К2 — адаптивный порог. В ЭЗ основное внимание уделяется процедуре локального улучшения М2, суть которой заключается в улучшении потомков полученной популяции путём принудительных микромутаций.

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

В параграфе 4.1 осуществляется обзор основных пунктов меню разработанного программного продукта.

Параграф 4.2 излагает основные цели проводимых исследований, а именно:

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

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

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

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

в качестве значения в неё записывается номер части разбиения, которой она принадлежит.

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

В параграфе 4.6 осуществляется оценка полученных экспериментальных данных. По результатам исследований биоинспирированного алгоритма разбиения (БАР) в сравнении с ПГА определены диапазоны оптимальных значений параметров эволю-ционно-генетического поиска. Опытным путём доказано, что применение различных модификаций использования генетических операторов в биоинспирированном алгоритме, приводит к улучшению (увеличению) среднего значения целевой функции в популяции на 5.5% для ОК на 1,9% для ОМ и на 4% для ОИ для серии опытов. Разработанный БАР, позволяет получать решения лучше, чем ПГА. Для различных гиперграфов, увеличение наилучшей ЦФ составляет в среднем 3.3%, при этом предложенный БАР находит оптимальное решение за меньшее число итераций, т.е. эффективнее на 15,3%, но для этого ему требуется больше времени в среднем в 5 раз, чем для ПГА.

Оценена эффективность применения разработанного АВС-алгоритма, используемого в качестве генератора стартового множества решений. Доказано, что для различных гиперграфов, среднее увеличение максимальной ЦФ составляет от 5% до 15%, а среднее увеличение минимальной ЦФ от 3%— 19%. Таким образом, АВС-алгоритм позволяет повысить качество решений стартовой популяции, получает хорошие решения в задачах большой размерности, сокращая общее время работы алгоритма. Алгоритм колонии пчёл обладает линейной сложностью, т.е. прост в реализации и не требует больших вычислительных затрат.

В параграфе 4.7 результаты работы разработанного БАР прошли сравнение с известными аналогами (бенчмарками).

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

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

В приложении № 2 рассмотрен пример работы биоинспирированного алгоритма разбиения гиперграфа Н = (X, Е), = |£| = 4Она 2 части, приведено сравнение с аналогами, а также интерфейс программного обеспечения.

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

В диссертационной работе проведены следующие теоретические и практические исследования:

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

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

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

3) для повышения качества решений, на начальном этапе работы биоинспири-рованного алгоритма, предложено использовать ABC — алгоритм роевого интеллекта. Для отбора решений в стартовую и последующие популяций используется «вариативный метод», состоящий из модифицированных эвристик отбора альтернативных решений: Э1, Э2, ЭЗ;

4) предложен генетический алгоритм с модифицированными процедурами, для генетических операторов, зависящими от динамических параметров, позволяющих повысить устойчивость генетического поиска и качество получаемых решений. Для преодоления преждевременной сходимости применяется процедура «генетического всплеска». Предложен алгоритм эволюционного поиска, в состав которого входят эволюционные процедуры локального улучшения и преодоления преждевременной сходимости алгоритма (М1 и М2);

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

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

В результате комплексного исследования было выявлено, что показали улучшения работы биоинспирированного алгоритма разбиения по сравнению с ПГА достигают 3,3% в зависимости от вида задачи. Предложенный БАР находит оптимальные решения за меньшее число итераций, т.е. эффективнее на 15,3%.

В качестве генератора стартовой популяции хромосом БАР использовался АВС-алгоритм. Результаты тестирования, показали, что для различных гиперграфов, среднее увеличение максимальной ЦФ составляет от 5% до 15%, а среднее увеличение минимальной ЦФ от 3%- 19%. Таким образом, АВС-алгоритм позволяет повысить качество решений стартовой популяции, получает хорошие решения в задачах большой размерности, сокращая общее время работы БАР.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ I. Публикации в центральных изданиях, включенных в перечень периодических

изданий ВАК РФ

1. Курносова Е.Е. Об одном подходе к построению интегрированных алгоритмов // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог, 2008. С - 104-107.

2. Курносова Е.Е., Полупанов A.A. Методы повышения качества решений в эволюционно-генетических алгоритмах // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, 2009.-№7(108).-С. 41-46.

3. Курейчик В.В., Полупанова Е.Е. Эволюционная оптимизация на основе алгоритма колонии пчёл // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, 2009.

4. Полупанова Е.Е. Экспериментальные исследования интегрированного алгоритма компоновки // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, 2010. - № 7 (108).-С. 96-100.

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

5. Курносова Е.Е., Курейчик В.В. Программа компоновки технических элементов конструкций на основе бионических методов. Свидетельство о государственной регистрации программы для ЭВМ №2008615026, 2008.

III. Публикации в других изданиях

6. Полупанов A.A., Полупанова Е.Е. Обзор современных методов и алгоритмов решения задачи компоновки // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT' 11». Научное издание в 4-х томах. М.: Физматлит, 2011. -Т.З. С. -295-301.

7. Гончаров A.M., Курейчик В. В., Полупанов А. А., Полупанова Е.Е Экспериментальные исследования алгоритма компоновки на основе поведения пчелиного роя // Труды Конгресса по интеллектуальным системам и информационным технологиям "AIS- IT'11". Научное издание в 4-х томах. . М.: Физматлит, 2011. С, - 133-138.

8. Полупанов A.A., Полупанова Е.Е. Эвристический эволюционно-генетический алгоритм // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'10». Научное издание в 4-х томах. М.: Физматлит, 2010. - Т.З. - С. 83-89.

9. Курейчик В.В., Полупанов A.A., Полупанова Е.Е. Экспериментальные исследования пчелиного алгоритма генерации стартового множества решений // Труды Конгресса по интеллектуальным системам и информационным технологиям "AIS- IT'10". Научное издание в 4-х томах. . М.: Физматлит, 2010 . - С. 58-62.

10. Курейчик В.В., Курносова Е.Е. Методы формирования стартовой популяции решений // Труды международных научно-технических конференций «Интеллектуальные системы» (AIS'09) и «Интеллектуальные САПР» (CAD-2009). Научное издание в 4-х томах. М.: Физматлит, 2009. С. - 195-198.

11. Курносова Е.Е. Интегрированный алгоритм поиска оптимальных решений в задачах оптимизации // Труды Конгресса по интеллектуальным системам и информационным технологиям "AIS- IT'08". Научное издание в 4-х томах. М.: Физматлит, 2008. С. - 193-197.

12. Курносова Е.Е. Разработка бионических методов и принципов поиска оптимальных решений в задаче компоновки / тезис // VI Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «МОЛОДЕЖЬ XXI ВЕКА —БУДУЩЕЕ РОССИЙСКОЙ НАУКИ», г. Ростов-на-Дону, 2009.

13. Курносова Е. Е., Полупанов А. А. Методы повышения качества решений в эволюционно-генетических алгоритмах // Электронное периодическое изда-

ние «Информатика, вычислительная техника и инженерное образование» № 1(1), 2010. - http://digital-mag.tti.sfedu.ru. С. - 62-66.

14. . Курейчик В.В. Курносова Н.Е., Полупанова Е.Е. Программная реализация интегрированного алгоритма компоновки // Электронное периодическое издание «Информатика, вычислительная техника и инженерное образование» № 1(3), 2011. - ЬПр://(^йа1-та§.Ш.8Геёи.ги.С. - 3-9.

Личный вклад диссертанта в работы, опубликованные в соавторстве:

[3, 4, 13] — разработка методов повышающих качество получаемых решений биоинспирированного алгоритма;

[5, 6, 9] - разработка алгоритмов, позволяющих оптимизировать процесс поиска решений задачи разбиения;

[7, 8, 10, 14] - экспериментальные исследования разработанных алгоритмов, позволяющие доказать способность разработанных методов получать оптимальные решения с большей степенью эффективности по сравнению с аналогами.

ЛР 02205665 от 23.06.1997г. Подписано к печати 27. 09. 2012 г. Формат 60x84 1/16 Печать офсетная. Бумага офсетная. Усл.п.л. - 1

Заказ № 132 Тираж 100 экз.

_©_

Издательство Южного федерального университета

Таганрог, 28, ГСП 17А, Некрасовский, 44 Типография Южного федерального университета Таганрог, 28, ГСП 17А, Энгельса, 1

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

Введение.

Глава 1 Анализ алгоритмов и методов решения задачи разбиения при проектировании СБИС.

1.1 Классификация алгоритмов разбиения.

1.2 Построение математической модели для задачи разбиения.

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

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

1.5 Выводы.

Глава 2 Применение методов биоинспирированного поиска для решения задачи разбиения схем при проектировании СБИС.

2.1 Разработка биоинспирированных методов и принципов разбиения схем при проектировании СБИС.

2.2 Методика кодирования информации в биоинспирированном алгоритме.

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

2.4 Формирование начального множества решений методом колонии пчел.

2.5 Схема биоинспирированного алгоритма разбиения элементов СБИС.

2.6 Выводы.

Глава 3 Построение биоинспирированного алгоритма поиска оптимальных решений в задаче разбиения.

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

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

3.3 Разработка эвристического биоинспирированного алгоритма разбиения элементов СБИС.

3.4 Выводы

Глава 4 Разработка программной реализации и экспериментальное исследование биоинспирированного алгоритма поиска оптимальных решений в задаче разбиения.

4.1 Обзор основных пунктов меню разработанной программы разбиения схем

4.2 Цель проведения экспериментальных исследований.

4.3 Формат входного файла.

4.4 Формат выходного файла гиперграфа.

4.5 Порядок проведения экспериментальных исследований.

4.6 Оценка результатов проведенных исследований.

4.6.1 Результаты применения генетических операторов.

4.6.2 Результаты экспериментальных исследований АВС-алгоритма.

4.6.3 Результаты исследований для разработанного алгоритма (БАР).

4.7. Сравнение разработанного биоинспирированного алгоритма с аналогами .110 4.8 Выводы.

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

В настоящее время наибольшее распространение при создании сложных объектов получили методы машинного (автоматизированного) проектирования. Поскольку компьютеры перестали быть редкостью, методы автоматизированного проектирования переходят в разряд инструментов, пользоваться которыми может каждый. В таких условиях технической оснащенности инженер должен обладать навыками математического и программного моделирования, а также решения задач разработки и эксплуатации аппаратуры с помощью ЭВМ. В связи с этим в промышленности широко используются различные системы автоматизированного проектирования (САПР), осуществляющие проектирование печатных плат (lili), гибридных интегральных схем (ГИС), микросборок (МБС) и других подобных конструктивов.

На этапе синтеза взаимодействие человека и ЭВМ происходит в интерактивном режиме. Основные недостатки такого подхода:

1) получение далёких от оптимальных решений;

2) возможности человека в решении задач синтеза сужаются в связи с усложнением проектируемых изделий;

3) возрастают затраты вычислительных ресурсов.

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

К основным критериям эффективности моделей, методов и алгоритмов автоматизированного проектирования относятся:

1) точность решения задач;

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

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

Критерий электромагнитотепловой совместимости элементов является основным критерием разбиения схемы. На основе данного критерия определяется область допустимых разбиений схемы, на которой, в свою очередь, базируются другие критерии. Такими критериями могут быть: число типов модулей (ячеек, элементов), функциональная полнота блоков, длина задержки сигнала, параметры теплообмена между элементами в модуле, несовместимость элементов отдельных типов друг с другом , вследствие чего необходимо их распределения в разные блоки и др. Очевидно, что число внешних связей между элементами схемы играет большую роль при определении надёжности радиоэлектронной аппаратуры (РЭА). Поэтому минимизация числа внешних связей между отдельными блоками является наиболее распространенным критерием. В результате выполнения этого критерия упрощается конструкция СБИС, повышается надёжность схемы, минимизируется число взаимных наводок и т.д. [2]. Оптимизация этого критерия позволяет значительно сократить затраты и трудоёмкость этапа разбиения в общем цикле проектирования СБИС.

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

Основной результат решения задачи трассировки - конструктивная реализация связей между элементами.

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

Развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС нашло отражение в работах Норенкова И.П., Казеннова Г.Г., Шервани Н., Бершадского A.M., Курейчика В.М., Морозова К.К., Селютина В.А., и др. В большинстве своём разрабатываемые алгоритмы, программы и пакеты направлены на формирования базового плана кристалла (оптимизацию разбиения, размещения разногабаритных объектов) и на оптимизацию этапа трассировки соединений по критерию минимизации длины связей и занимаемой площади [3 - 5]. Из-за тесной взаимосвязи задач конструкторского проектирования и большой размерности каждой из них, а также появления новых направлений в технологии изготовления СБИС, появляется необходимость в разработке новых, методик и алгоритмов для решения данного класса задач. Для решения NP-полных задач, в которых оптимальное решение возможно найти только методами полного перебора непрерывно разрабатываются новые алгоритмы, позволяющие получать эффективные решения за приемлемое время. К таким алгоритмам можно отнести методы эволюционного поиска и генетические алгоритмы (ГА), развитие которых началось в начале 1970 гг., но только сейчас стало приоритетным в отношении других методов. В последние годы широкое распространение также получили алгоритмы, основанные на роевом интеллекте (Swarm-based optimization algorithms (SOAs)).

Поскольку данные алгоритмы и методы способны обрабатывать множество решений многокритериальной задачи одновременно, их широко применяют для решения задач в самых различных областях [6 - 25], в том числе для решения задач проектирования СБИС.

Над развитием стратегий эволюционного поиска работали такие учёные, как: Холланд Д.Х., Гольдберг Д.Е., Батищев Д.И., Букатова И.Л., Курейчик В.М., Норенков И.П., Растригин Л.А. и др. Эволюционные методы, генетические алгоритмы и алгоритмы роевого интеллекта являются одним из фундаментальных направлений научных исследований в области случайно-направленного поиска. Часто для сложной задачи необходимо найти любое решение, удовлетворяющее заданным ограничениям, поэтому целью биоинспирированных (эволюционно-генетических) алгоритмов является нахождение наилучшего, а не оптимального варианта разбиения. При этом применение других методов становится невозможным, вследствие чрезвычайной сложности решаемой задачи.

Таким образом, АКТУАЛЬНОСТЬ работы состоит в разработке новых алгоритмов и методов биоинспирированного поиска задачи разбиения схем при проектировании СБИС, позволяющих улучшить показатели качества, трудоёмкости и времени работы ЭВМ.

ЦЕЛЬ работы состоит в разработке и исследовании биоинспирированных алгоритмов для решения задачи разбиения схем при проектировании СБИС.

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

1) анализ задачи разбиения при автоматизированном проектировании;

2) обоснование выбора математической модели схем для решения поставленной задачи;

3) теоретические исследования эволюционных, генетических алгоритмов, а также алгоритмов роевого интеллекта, ориентированных на решение задачи разбиения схем при проектировании СБИС;

4) построение модифицированных генетических процедур для решения задачи разбиения схем при проектировании СБИС;

5) построение новых архитектур биоинспирированного поиска ориентированных на решение задачи разбиения схем при проектировании СБИС;

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

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

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в том, что:

1) разработана трёхуровневая архитектура биоинспирированного эволюционно-генетического поиска с динамическими параметрами, оптимизирующая процесс эволюционно-генетического поиска;

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

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

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

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

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

1) Методика поиска решений, которая позволяет улучшить практические результаты по сходимости алгоритма, в связи с учетом математических и статистических закономерностей при распределении элементов.

2) Новая архитектура биоинспирированного эволюционно-генетического поиска с динамическими параметрами, с помощью которой удалось оптимизировать процесс эволюционно-генетического поиска.

3) Биоинспирированный алгоритм и программа для разбиения СБИС, созданная в среде объектно-ориентированного программирования Borland С++ Builder™ 6.0.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Материалы диссертационной работы использованы в Г/б № 12354 (1.04.01) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», Г/б № 12355 (12.8.08) «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений», грант РФФИ № 12388 (№ 08 - 01 - 00473) «Разработка теории и принципов решения задач проектирования, оптимизации и принятия решений на основе биоинспирированных нечетких генетических и эволюционных методов», грант РФФИ № 12382 (№ 09- 01 - 00492) «Разработка общей теории и когнитивных принципов эволюционных вычислений», грант РФФИ № 12383 (№ 09 - 07 -00318) «Разработка новых принципов извлечения знаний на основе распределенных алгоритмов генетического программирования и роевого интеллекта», грант РФФИ №12389 (№10-01-00115) «Разработка теории и принципов построения интеллектуальных интегрированных подсистем в задачах проектирования и управления», РНП 2.1.2.1652 «Разработка теории и когнитивных принципов принятии решений на основе распределенных алгоритмов, инспирированных природными системами».

Теоретические и практические результаты работы прошли АПРОБАЦИЮ на научных семинарах (с 2008 по 2011 гг., ТТИ ЮФУ), VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «МОЛОДЕЖЬ XXI ВЕКА — БУДУЩЕЕ РОССИЙСКОЙ НАУКИ» (г. Ростов-на-Дону, 2009), Международных научно-технических конференциях "Интеллектуальные системы" (AIS'08) и "Интеллектуальные САПР" (CAD-2008) (Дивноморское, 2008 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2009» («ИС-2009») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09» (Дивноморское, 2009 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2010» («ИС-2010») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'10» (Дивноморское, 2010 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2011» («ИС-2011») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT' 11» (Дивноморское, 2011 г.).

ПУБЛИКАЦИИ. По теме диссертации опубликовано 14 печатных работ.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырёх глав, заключения, и

Заключение

В диссертационной работе проведены следующие теоретические и практические исследования:

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

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

3) Для повышения качества решений, на начальном этапе работы биоинспирированного алгоритма, предложено использовать ABC - алгоритм роевого интеллекта. Для отбора решений в стартовую и последующие популяций используется «вариативный метод», состоящий из модифицированных эвристик отбора альтернативных решений: Э1, Э2, ЭЗ.

4) Предложен генетический алгоритм с модифицированными процедурами, для генетических операторов, зависящими от динамических параметров, позволяющих повысить устойчивость генетического поиска и качество получаемых решений. Для преодоления преждевременной сходимости применяется процедура «генетического всплеска». Предложен алгоритм эволюционного поиска, в состав которого входят эволюционные процедуры локального улучшения и преодоления преждевременной сходимости алгоритма (М1 и М2).

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

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

7) В результате комплексного исследования было выявлено, что улучшение работы биоинспирированного алгоритма разбиения по сравнению с ПГА составляет 3,3%. Предложенный БАР находит оптимальное решение за меньшее число итераций, т.е. эффективнее на 15,3%.

8) В качестве генератора стартовой популяции хромосом БАР использовался АВС-алгоритм. Результаты тестирования, показали, что для различных гиперграфов, среднее увеличение максимальной ЦФ составляет от 5% до 15%, а среднее увеличение минимальной ЦФ от 3%-19%. Таким образом, АВС-алгоритм позволяет повысить качество решений стартовой популяции, получает хорошие решения в задачах большой размерности, сокращая общее время работы БАР.

1. Норенков И. П., Арутюнян Н.М. Эволюционные методы в задачах выбора проектных решений // Электронное научно-техническое издание "Наука и образование", 2007.URL: http://technomag.edu.ru/doc/68376.html.

2. Норенков, И. П. Основы автоматизированного проектирования. М.: Изд-во МГТУ имени Н.Э. Баумана, 2006. 360 с.

3. Wei Y.C., Cheng С.К. "A two-level two-way Partitioning Algorithm", Tech. report CH2924-9, University of California, San Diego, IEEE, 1990.

4. Ching-Wei Yeh, Chung-Kuan Cheng, Ting-Ting Y. Lin. "A general purpose multiple way Partitioning Algorithm", 28th ACM/IEEE Design Automation Conference, paper 25/1, pp.421-425., 1991.

5. Karypis G., Aggarwal R., Kumar V., and Shekhar S. Multilevel hypergraph partitioning: Application in VLSI domain. In Proceedings of the Design and Automation Conference, 2002.

6. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 2003.

7. Whitley L. D. An executable model of a simple genetic algorithm // In Whitley L.D. (ed): Foundations of Genetic Algorithms 2. Morgan Kaufmann, 2001.

8. Goldberg D.E., Kalyanmoy D. A comparative analysis of selection schemes used in genetic algorithms. In Rawlings G.(Ed.). Foundations of Genetic Algorithms. Indiana University. Mogan Kaufmann, San Mateo, С A, 1991.

9. Chen L. Chang Y., "Solve the vehicle routing problem with time windows via a genetic algorithm," Discrete and continuous dynamical systems supplement, C. 240-249, 2007.

10. Курейчик B.B., Курейчик B.M. Перспективные технологии для решения оптимизационных задач. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.1. М.: Физматлит, 2003, с 59-67.

11. Курейчик B.M. Генетические алгоритмы: Состояние. Проблемы. Перспективы. Теория и системы управления РАН. Москва. N 1, 2000, с.144-160.

12. Caldwell W.K. Mic Cut Partitioning With Functional Replication for Technology - Mapped Circuits Using Minimum Area Over hed. -//-V.21, №4, april 2002, pp. 491 -496.

13. Lieng J., Thulasiraman K. A Genetic Algorithm for Channel Routing in VLSI Circuits. Evolutionary Computation, 1(4), MIT, 1994. pp. 293-311.

14. Курейчик B.M. Генетические алгоритмы и их применение: Монография. Таганрог: Изд-во ТРТУ, 2002.

15. Чернышев Ю.О., Курейчик В.В. Генетические алгоритмы размещения / XXII International School And Conference On Computer Aided Design, CAD-95, Gurzuff, 1995. c. 329-330.

16. Cohoon J.P. and Paris W.D. Genetic placement. IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.6, № 6, 1987. pp. 956-964.

17. Goodman, E. Tetelbaum, A. and Kureichik, V. (1994). A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems. Case Center Technical Report #940702, Michigan State University

18. Смирнова O.B. Модели эволюции в задачах компоновки схем ЭВА. Перспективные информационные технологии интеллектуальные системы, №1 (19), 2002, с.47-49.

19. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика. РАН, №10. Москва, 2001, стр.174-187.

20. Лебедев Б.К. Канальная трассировка на основе генетических процедур. Известия ТРТУ, №3. Таганрог, 1997. 53-60 с.

21. Лебедев Б.К. Планирование СБИС методом генетического поиска. Известия ТРТУ. Интеллектуальные САПР. Таганрог, Изд-во ТРТУ, 1999, №3. 119-126 с.

22. Vose M. D., Liepins G. E. Punctuated equilibria in genetic search // Complex Systems, 2001. no. 5, pp. 31-44.

23. Батищев Д.И., Власов C.E., Булгаков И.В. Плотное размещение разногабаритных объектов на плоскости с помощью генетических алгоритмов. XXIII International School and Conference on Computer Aided Design. Yalta-Gurzuff, 1996. 354 c.

24. Полупанов A.A., Полупанова E.E. Обзор современных методов и алгоритмов решения задачи компоновки // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'l 1». Научное издание в 4-х томах. М.: Физматлит, 2011. Т.З.

25. Ильин В.Н., Фролкин В.Т., Бутко А.И. и др.; «Автоматизация схемотехнического проектирования: Учебное пособие для вузов». Москва. : «Радио и связь», 2002.

26. Курейчик, В. М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио и связь, 1990.

27. Емельянов, В. В. Теория и практика эволюционного моделирования. М.: Физматлит, 2003.

28. Sherwani, N. A. Algorithms for VLSI Physical Design Automation. -Boston: Kluwer Academic Publishers, 1995. 538 p.

29. Karypis G., Kumar V. A coarse-grain parallel multilevel k-way partitioningalgorithm. In Proceedings of the eighth SIAM conference on Parallel

30. Processing for Scientific Computing, 2003.

31. Гладков JI. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы, учеб. пособие для. Ростов на - Дону: Ростиздат, 2004.

32. Лахути Д.Г. Садовский В.Н., Финн В.К. Эволюционная эпистемология и логика социальных наук: Карл Поппер и его критики. М.: Эдиториал УРСС, 2000.

33. Хедрик Ф. Генетика популяций. М.: Техносфера, 2003.

34. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика. РАН, №10. Москва, 2001.-стр. 174-187.

35. Тарасов В.Б. Интеллектуальные системы в проектировании. Новости ИИ, №4. 1993. - с.24 - 67.

36. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. М.: Эдиториал УРСС, 2002. -352с

37. Курносова Е.Е. Об одном подходе к построению интегрированных алгоритмов // Известия ЮФУ, Интеллектуальные САПР. Таганрог, 2008. с. 104.

38. Мищенко, М. Н. Бионический метод размещения элементов схем ЭВА // Перспективные информационные технологии интеллектуальные системы, №2 (22), 2005. с. 34 - 36.

39. Karaboga, D. An idea based on honey bee swarm for numerical optimization // Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

40. Субботин C.A., Олейник Ан.А., Олейник Ал.А. Интеллектуальные мультиагентные методы (Swarm Intelligence), часть III // Фрагмент рабочих материалов монографии. с. 35 - 52.

41. Курейчик В.В., Курносова Е.Е. Методы формирования стартовойпопуляции решений // Труды международных научно-техническихконференций «Интеллектуальные системы» (AIS'09) и

42. Курейчик В.В., Полупанова Е.Е. Эволюционная оптимизация на основе алгоритма колонии пчёл // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, 2009.

43. Goldberg D. Е. Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publishing Company Inc., 1989. - 442p.

44. Курейчик В. M. Генетические алгоритмы и их применение, монография. Таганрог: Изд-во ТРТУ, 2002.

45. Гладков Л. А., Курейчик В.В. , Курейчик В.М. Генетические алгоритмы, под ред. В.М. Курейчика. М.: Физматлит, 2006. 320 с.

46. Курейчик В.В. , Полупанов А.А. Эволюционные методы разбиения схем на основе адаптивных генетических процедур, монография. Таганрог: Изд-во ТТИ ЮФУ, 2007. 160 с.

47. Secanina, L. Evolutionary design of digital circuits: where are current limits? // Proceedings of the first NASA/ESA conference on adaptive hardware and systems. 2006.

48. Конушин А. Эволюционные нейросетевые модели с незаданным заранее числом связей. www.ict.edu.ru/ft/002414/numlevol.pdf

49. Vose M.D. Modeling simple genetic algorithms // In Whitley L.D. (ed): Foundations of Genetic Algorithms 2. Morgan Kaufmann, 2003.

50. Stoica A. Evolvable hardware for autonomous systems // CEC-2004. -Tutorial.Portland, Oregon.

51. Miller, J. F. Job D., Vassilev V. K. Principles in the Evolutionary Designof Digital Circuits. Genetic Programming and Evolvable Machines. Part I.

52. Netherlands: Kluwer Academic Publishers, 2000. 1. - pp.7-35.

53. Курейчик В. M. , Зинченко JI. А. Эволюционное моделирование с динамическим изменением параметров // Труды VII национальной конференции по искусственному интеллекту. М.: Физматлит, 2000. с. 516-523.

54. Сороколетов П.В. Курейчик В.В. Концептуальная модель представления решений в генетических алгоритмах. Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР», №. 9, с. 7-12, 2008.

55. Гладков JI. А. , Зинченко JI. А., Курейчик В. В., Курейчик В. М., Лебедев Б. К., Нужнов Е. В., Сорокин С. Н. Методы генетического поиска. Научное издание. Таганрог: Изд-во ТРТУ, 2002. 122 с.

56. Курейчик В. В Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. Таганрог: Изд-во ТРТУ, 2001.

57. Potts J.С., Giddens Т., Yadav S. The Development and Evaluation of a improved Genetic Algorithm Based on Migration and Artificial Selection, IEEE Transactions on systems, man, and cybernetics. January 1994. -Vol.24, No.l.-pp. 73-86.

58. Herrera F., Lozano M. Adaptive Genetic Algorithms, based on Fuzzy Techniques. Granada, Spain, 1996. - pp. 775-780.

59. Батищев Д. И. Генетические алгоритмы решения экстремальных задач // Учебное пособие. Воронеж, 1995. 69 .

60. Davis L.D. Handbook of Genetic Algorithms // Van Nostrand Reinold. -New York, 1991.

61. Goldberg D. E., Kalyanmoy D. A. Comparative analysis of selection schemes used in genetic algorithms // In Rawlings G.(Ed.). Foundations of Genetic Algorithms. Indiana University. - Mogan Kaufmann, San Mateo, CA, 1991.

62. Курейчик B.B. Мищенко M. H. Бионический метод определения путей оптимальной длины в графовых моделях // III-й Международный научно

63. Генетические алгоритмы. URL: http://www.tspu.tula.ru/ivt/oldsite/umr/ ealg/w3c.html.

64. Норенков И. П., Косачевский О. Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации // Электронное научно-техническое издание "Наука и образование", 2005. URL: http://technomag.edu.ru/doc/56533.html.

65. Полупанов A.A., Полупанова Е.Е. Эвристический эволюционно-генетический алгоритм // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'IO». Научное издание в 4-х томах. М.: Физматлит, 2010. Т.З. - С. 83-89.

66. Митропольский А.К. Техника статистических исследований. М., "Наука", 1971. 576 с.: ил

67. Останин А.Н. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента // Учеб. Пособие. Минск: Вышэйшая школа., 1989. 218 с.: ил.

68. Львовский E.H. Статистические методы построения эмпирических формул // Учеб. пособие для втузов. М.: Высшая школа, 1988. 239 с.

69. Адлер Ю.П. Введение в планирование эксперимента. М.: Металлургия, 1969. 157 е.: ил.

70. Ежов И.И., Скороход A.B., Ядренко М.И. Элементы комбинаторики. М.: Наука, 1977. 264 с.

71. Гроппен В.О. Принципы оптимизации комбинаторных процедур. Ростов-на-Дону: Издательство РГУ, 1988. 195 е.: ил.

72. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.

73. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. М.: Наука, 1986. 544 е.: ил.

74. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений. М.: Физматгиз, 1962. 349 с.

75. Андерсон Т. Введение в многомерный статистический анализ/ Пер. с англ. Кичатова Ю.Ф. М.: Физматгиз, 1963. 500 е.: ил.

76. Большое Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 1965.464 с.

77. Гурский Е.И. Теория вероятностей с элементами математической статистики. М.: Высшая школа, 1971. 328 с.

78. Гренандер У. Случайные процессы и статистические выводы / Пер. с англ. и доп. Яглоба А.М. М.: Изд-во иностранной лит., 1961. 167 с.

79. Даймонд С. Статистика в науке / Пер. с англ. А.Л. Дружининой М.: Статистика, 1970. 155 с.

80. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

81. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Нижний Новгород, Нижегородский госуниверситет, 1994.

82. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с

83. Полупанова Е.Е. Экспериментальные исследования интегрированного алгоритма компоновки // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, 2010. - № 7 (108). - С. 96-100.

84. Thang Nguyen Bui, Byung-Ro Moon "GRCA: A Hybrid Genetic Algorithm for Circuit Ratio-Cut Partitioning". IEEE Transactions on computer-aided design of integrated circuits and systems, vol. 17, No.3, March 1998, pp. 193-204.

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

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

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

88. Зам. зав. кафедрой САПР по научной работе, д.т.н., проф.1. Б.К. Лебедев1. УТВЕРЖДАЮ» ПО НИДТТИЮФУ1. В. М. Курейчик 2012г.1. АКТ

89. Об использовании результатов кандидатской диссертации Полупановой Е.Е. в учебном процессе Южного федерального университета

90. Указанные результаты используются при чтении следующих курсов на кафедре САПР: «Автоматизация конструкторского и технологического проектирования»; «Методы оптимизации»; «Эволюционное моделирование и генетические алгоритмы».

91. Внедрение в учебный процесс ряда теоретических и практических результатов диссертационной работы Полупановой Е.Е. позволило повысить качество подготовки специалистов в области САПР и информационных технологий.

92. Начальник учебного отдела УМУ

93. Декан ФАВТ, д.т.н., профессор

94. Зам. зав. кафедрой САПР по учебной работе

95. Черный С.А. Вишняков Ю.М. Нужнов Е.В.1. РОС cutí ШСЛЛ ШДЖАЦ,FШ1. SS S м S йvC -ЧШВ1. Ш Ш й ЙШ Ш1. СВИДЕТЕЛЬСТВОо государственной регистрации программы мя ')ВМ2008615026

96. Программа компоновки технических элементов конструкций на основе бионических методов11раиоо6далате.'п.(ли): Федеральное государственное образовательное учреждение вгнешего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» (Я11)

97. Лвтор(ы): Курносова Елена Евгеньевна, Курейчик Владимир Викторович (ЯП)1. Заявка № 2008613928

98. Дата поступления 26 августа 2008 г.

99. Зарегистрировано в Рсестре программ для ЭВМ17 октября 2008 г.ч—>1. Ч ^

100. Руководитель Федеральной службы по интеллектуальной собственности, патентам и товарным знакам1. Б П. Симонов

101. Ш>ш ш $ ш WWWWWWm т WWWWWWWWWWWm mWWWWWWmW^