Авторефераты по всем темам  >>  Авторефераты по техническим специальностям  

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

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

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

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

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

АВТОРЕФЕРАТ

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

Таганрог - 2012

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

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

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

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

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

ФГБОУ ВПО Ростовский Государственный Университет Путей Сообщения

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

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

ФГБОУ ВПО Таганрогский Государственный

Педагогический Институт имени А.П. Чехова

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

образовательное учреждение высшего

профессионального образования Кубанский

государственный университет.

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

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

Автореферат разослан 8 локтября  2012 г.

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

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

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

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

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

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

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

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

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

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

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

1. анализ задачи разбиения при автоматизированном проектировании;
2. обоснование выбора математической модели схем для решения поставленной задачи;
3. теоретические исследования эволюционных, генетических алгоритмов, а также алгоритмов роевого интеллекта, ориентированных на решение задачи разбиения схем при проектировании СБИС;
4. построение модифицированных генетических процедур для решения задачи разбиения схем при проектировании СБИС;
5. построение новых архитектур биоинспирированного поиска ориентированных на решение задачи разбиения схем при проектировании СБИС;
6. экспериментальные исследования разработанных алгоритмов и методов, а также их сравнение с известными аналогами.

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

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

1. разработана трёхуровневая архитектура биоинспирированного эволюционно-генетического поиска с динамическими параметрами, оптимизирующая процесс эволюционно-генетического поиска;
2. разработан биоинспирированный алгоритм решения задачи разбиения, основанный на трёхуровневой архитектуре и использующий три алгоритма: алгоритма колонии пчёл, алгоритма генетического поиска и алгоритма эволюционного поиска;
3. на основе методов роевого интеллекта разработан алгоритм колонии пчёл, используемый в качестве методики формирования стартовой популяции хромосом, позволяющий повысить сходимость биоинспирированного алгоритма и сократить время поиска решений;
4. разработан алгоритм генетического поиска с новыми модифицированными процедурами для генетических операторов (кроссинговера, мутации, инверсии), зависящими от значений динамических параметров, повышающих устойчивость генетического поиска и качество получаемых решений;
5. разработан алгоритм эволюционного поиска, в состав которого входят эволюционные процедуры локального улучшения и преодоления преждевременной сходимости алгоритма.

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

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

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

1. методика поиска решений, которая позволяет улучшить практические результаты по сходимости алгоритма, в связи с учётом математических и статистических закономерностей при распределении элементов;
2. новая архитектура биоинспирированного эволюционно-генетического поиска с динамическими параметрами, с помощью которой удалось оптимизировать процесс эволюционно-генетического поиска;
3. биоинспирированный алгоритм и программа для разбиения СБИС, созданная в среде объектно-ориентированного программирования BorlandаC++а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. рассматривается методика кодирования решений задачи разбиения. В качестве системы кодирования решений используется кодирование, основанное на местоположении (локусе) гена в хромосоме. Внутренняя структура хромосомы будет определяться исходя из требований задачи распределения элементов и содержаться в матрице распределений  . Состав хромосомы определяется только принадлежностью вершин гиперграфа H частям разбиения.

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

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

1)аобщее число пчёл (N);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

АВС= (N, m, е, n, r, l, S, О, I),                               (1.2)

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

ГА = (P,  S, МК, ЦФ, ОГР, ГО, ОР, T, pi, L).                       (1.4)

Здесь:

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

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

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

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

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

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

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

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

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

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

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

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

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

Pа=аP1а+аP2, (1.5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации по теме диссертации

I. Публикации в центральных изданиях, включенных в перечень периодических изданий ВАК РФ

1. КурносовааЕ.Е. Об одном подходе к построению интегрированных алгоритмов // Известия ЮФУ. Технические науки. Тематический выпуск Интеллектуальные САПР. Таганрог, 2008. С - 104-107.
2. Курносова Е.Е., Полупанов А.А. Методы повышения качества решений в эволюционно-генетических алгоритмах // Известия ЮФУ. Технические науки. Тематический выпуск Интеллектуальные САПР. Таганрог: Изд-во ТТИ ЮФУ, 2009. - № 7 (108). - С. 41-46.
3. КурейчикаВ.В., ПолупановааЕ.Е.аЭволюционная оптимизация на основе алгоритма колонии пчёл // Известия ЮФУ. Технические науки. Тематический выпуск Интеллектуальные САПР. Таганрог: Изд-во ТТИ ЮФУ, 2009. - 6с.
4. ПолупановааЕ.Е.аЭкспериментальные исследования интегрированного алгоритма компоновки // Известия ЮФУ. Технические науки. Тематический выпуск Интеллектуальные САПР. Таганрог: Изд-во ТТИ ЮФУ, 2010. - № 7 (108). - С. 96-100.

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

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

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

6. ПолупановаА.А., ПолупановааЕ.Е. Обзор современных методов и алгоритмов решения задачи компоновки // Труды Конгресса по интеллектуальным системам и информационным технологиям AIS-ITТ11. Научное издание в 4-х томах. М.: Физматлит, 2011. Т.3. С. - 295-301.
7. Гончаров А.М., Курейчик  В. В., Полупанов А. А., Полупанова Е.Е Экспериментальные исследования алгоритма компоновки на основе поведения пчелиного роя // Труды Конгресса по интеллектуальным системам и информационным технологиям УAIS- ITТ11Ф. Научное издание в 4-х томах. . М.: Физматлит, 2011. С. - 133-138.
8. ПолупановаА.А., ПолупановааЕ.Е. Эвристический эволюционно-генетический алгоритм // Труды Конгресса по интеллектуальным системам и информационным технологиям AIS-ITТ10. Научное издание в 4-х томах. М.: Физматлит, 2010. Т.3. С.а83-89.
9. КурейчикаВ.В., Полупанов А.А., Полупанова Е.Е.  Экспериментальные исследования пчелиного алгоритма генерации стартового множества решений // Труды Конгресса по интеллектуальным системам и информационным технологиям У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. - С. - 62Ц66.
14. . Курейчик В.В. КурносовааН.Е., ПолупановааЕ.Е. Программная реализация интегрированного алгоритма компоновки // Электронное периодическое издание Информатика, вычислительная техника и инженерное образование № 1(3), 2011. - - 3Ц9.

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

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

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

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

Р 02205665 от 23.06.1997г.	Подписано к печати  27. 09. 2012аг.
Формат 60х84 1/16	Печать офсетная.
Бумага офсетная.	Усл.п.л. - 1
Заказ № а 132а	Тираж 100 экз.

___________________________________й___________________________________

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

Таганрог, 28, ГСП 17А, Некрасовский, 44

Типография Южного федерального университета

Таганрог, 28, ГСП 17А, Энгельса, 1

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям