Содержание к диссертации
Введение
1 Анализ и состояние проблемы размещения компонентов СБИС 13
1.1 Анализ проблемы размещения компонентов СБИС 13
1.1.1 Развитие полузаказных матричных СБИС 13
1.1.2 Иерархический подход к проектированию ЭВА 13
1.2 Построение математической модели задачи размещения 16
1.3 Постановка задачи размещения компонентов СБИС 20
1.4 Классификация и анализ методов размещения 25
1.4.1 Классификация традиционных методов размещения 25
1.4.2 Анализ методов эволюционного моделирования 30
1.4.3 Анализ модели муравьиной колонии 31
1.4.4 Анализ модели пчелиного роя 33
1.5 Выводы 37
2 Разработка модели адаптивного поведения биологических систем 38
2.1 Архитектура модифицированного гибридного алгоритма размещения 38
2.2 Построение схемы гибридного поиска 41
2.3 Построение модифицированной структуры гибридного поиска 43
2.4 Метод биоинспирированного поиска 46
2.5 Разработка гибридного двухуровневого подхода размещения компонентов СБИС 51
2.6 Модели адаптивного поведения биологических систем 55
2.6.1 Метод пчелиной колонии 55
2.6.2. Алгоритм работы колонии пчел 59
2.6.3 Метод генетического алгоритма 61
2.7 Разработка модифицированного генетического оператора 66
2.8 Мпогоагентный подход к описанию разработанных моделей 70
2.9 Выводы 74
3 Разработка модифицированного гибридного алгоритма размещения компонентов СБИС 75
3.1 Модифицированный гибридный алгоритм размещения компонентов СБИС 75
3.2 Гибридный алгоритм размещения компонентов СБИС 78
3.3 Модель модифицированного гибридного алгоритма размещения компонентов СБИС 81
3.4 Разработка генетического алгоритма размещения компонентов СБИС 86
3.5 Применение гибридного механизма для решения задач размещения компонентов СБИС 89
3.6 Разработка роевого алгоритма размещения 95
3.6.1 Формирование окрестности поиска методом колонии пчел 100
3.7 Процедура кодирования -декодирования 102
3.8 Выводы 106
4 Программная реализация и экспериментальные исследования модифицированного гибридного алгоритма в задаче размещения 107
4.1 Цели экспериментальных исследований 107
4.2 Описание программного комплекса 108
4.3 Результаты экспериментальных исследований 119
4.3.1 Определение временной сложности разработанного гибридного алгоритма 121
4.4 Выводы 125
Заключение 127
Список использованной литературы 129
Приложение 141
- Построение математической модели задачи размещения
- Разработка гибридного двухуровневого подхода размещения компонентов СБИС
- Применение гибридного механизма для решения задач размещения компонентов СБИС
- Определение временной сложности разработанного гибридного алгоритма
Введение к работе
Актуальность темы. Одной из сложнейших и наиболее важных задач при создании средств микроэлектронной техники является синтез топологий СБИС. Синтез - создание проектного решения в виде его конструктивных особенностей, функциональной или структурной. Отличительной особенностью современного этапа является высокая сложность и размерность проектирования устройств. Методы автоматизированного проектирования, технологической подготовки проектирования и конструирования позволяют создавать в короткие сроки и при сравнительно низких затратах высоконадежные сверхбольшие интегральные схемы (СБИС).
Проектирование СБИС производится на нанометровом диапазоне, что требует новых методов и подходов.
В последнее время активно развивается научное направление Natural Computing, основанное на принципах природных механизмов принятия решений и включающее генетические алгоритмы, нейросетевые вычисления, муравьиные алгоритмы, метод роящихся частиц, табуированный поиск и др. АСО-алгоритмы обладают способностью находить более высококачественные решения за приемлемое время.
Современные ЭВА на основе ССБИС и СБИС реализуют качественное решение проблемы межсоединений на всех уровнях. Этап конструкторского проектирования является важным этапом автоматизации СБИС, включающий в себя: типизацию, компоновку, размещение, планирование кристалла, сжатие, трассировку и верификацию.
В настоящее время, создание алгоритмов, позволяющие найти приемлемое по трудоемкости и качеству решение задачи размещения, является важной и актуальной проблемой, стоящей перед разработчиками САПР.
Цель диссертационной работы. Целью диссертационной работы является разработка и исследование методов размещения компонентов СБИС нанометрового диапазона на основе моделей адаптивного поведения биологических систем.
Достижение поставленной цели предполагает решение следующих основных задач:
Обзор и анализ существующих алгоритмов размещения компонентов СБИС. Выбор математической модели задачи размещения компонентов СБИС.
Разработка модели адаптивного поведения колонии пчел, адаптированные на решение задачи размещения компонентов СБИС.
Разработка обобщенной архитектуры модифицированного гибридного алгоритма размещения компонентов СБИС.
Разработка роевого алгоритма размещения компонентов СБИС на основе построенной модели адаптивного поведения.
Построение гибридной схемы поиска решений задачи размещения с использованием разработанных алгоритмов, позволяющей повысить качество полученных решений.
Создание программного комплекса, использующего разработанные алгоритмы размещения.
Проведение экспериментальных исследований разработанных алгоритмов, для выявления оптимальных управляющих параметров и определение их эффективности.
Методы исследования в диссертации основаны на использовании теории графов и гиперграфов, элементов теории статистических вычислений, элементов теории множеств, теории комбинаторной оптимизации, генетических алгоритмов, биологических систем, теории алгоритмов и теории эволюционного моделирования.
Научная новизна диссертационной работы заключается в следующем:
Разработана обобщенная архитектура модифицированного гибридного алгоритма размещения компонентов СБИС в нанометровом диапазоне, обеспечивающая нахождение оптимальных решений за приемлемое время.
Построена модифицированная модель адаптивного поведения пчелиной колонии применительно к задачи размещения, отличающаяся принципами формирования окрестностей.
Разработаны механизмы интеграции моделей эволюционной адаптации и адаптивного поведения пчелиной колонии, позволяющие организовывать гибридные процедуры поиска.
Построена гибридная схема поиска решений задачи размещения с использованием разработанных алгоритмов, позволяющая повысить качество полученных решений.
Разработаны модифицированные алгоритмы размещения компонентов СБИС на основе генетического, эволюционного и роевого алгоритмов, позволяющие получать множество квазиоптимальных решений.
Разработана двухуровневая архитектура эволюционного алгоритма размещения компонентов СБИС.
Решение поставленных задач позволяет автору защищать следующие новые научные результаты:
Архитектура модифицированного гибридного поиска решений на основе интеграции механизмов генетического, эволюционного и роевого алгоритмов, обеспечивающая сбалансированный учет их достоинств.
Гибридная схема поиска решений задачи размещения компонентов СБИС, обеспечивающая учет изменяющихся условий окружающей среды.
Модифицированные алгоритмы размещения компонентов СБИС на основе генетических, эволюционных и роевых алгоритмов, способствующие повышению качества и скорости получения решений.
Механизмы интеграции моделей эволюционной адаптации и адаптивного поведения пчелиной колонии.
Модифицированная модель адаптивного поведения пчелиной колонии, позволяющая улучшить результаты по сравнению с использованием отдельных алгоритмов.
Практическая ценность результатов диссертационной работы основывается на создании программного комплекса, позволяющего применять
Рисунок 9 - Гистограмма сравнения качества решения,
В таблице 4 приведено сравнение результатов работы модифицированного гибридного алгоритма с бенчмарками.
На основе экспериментальных данных, можно судить, что разработанные модифицированные алгоритмы показали преимущество по сравнению с итерационным и последовательным алгоритмами, качество решений удалось повысить на 15-25%. Гибридный алгоритм улучшил решение задачи размещения на 7-12% по результатам сравнения с бенчмарками
В їаключении изложены основные выводы и результаты диссертационной работы.
В приложении даны копии актов об использовании результатов.
Определена временная сложность разработанного гибридного алгоритма. Таблица 1 Результаты экспериментальных исследований для ЮООитераций
В таблице 2 и на рисунке 8.отображены показатели зависимости времени работы алгоритмов от размера схемы.
Таблица 2 Зависимость времени работы алгоритмов от размера схемы
Чікло элементов схемы
Рисунок 8 - Зависимости времени работы алгоритмов от количества элементов схемы.
В таблице 3 и на рисунке 9 отображена эффективность работы разработанного гибридного алгоритма.
Таблица 3 Определение эффективности алгоритмов
разработанные модифицированные алгоритмы для решения задачи размещения компонентов СБИС.
При разработке программного комплекса применялись пакеты программ в среде Borland С++ Builder 6.0. Тестирование и отладка разработанного программного комплекса проводились на ЭВМ типа IBM PC с процессором Intel Core ІЗ. Экспериментальные данные разработанных алгоритмов превосходят данные известных алгоритмов, а также позволяют получать квазиоптимальные решения за полиномиальное время
Реализация результатов работы. Основные результаты диссертационной работы использованы в НИР № 301.38-11/2013-14 «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе методов и моделей адаптивного поведения биологических систем», а также в Грант РФФИ (№ 12 - 07 - 00058) «Разработка теоретических основ информационных технологий поддержки принятия решений при оптимизации и проектировании на основе методов, инспирированных природными системами», Грант РФФИ (№ 12 - 01 - 00100) «Разработка теории и принципов коллективного интеллекта на основе моделей адаптивного поведения муравьиной колонии для решения оптимизационных задач», Грант РФФИ № 12381 (№ 10 - 07 - 00055) «Разработка теории и принципов поиска решений в экспертных системах на основе методов и моделей адаптивного поведения биологических систем», Грант РФФИ № (№ 11- 07 - 00064) «Разработка теории и принципов создания интегрированных методов интеллектуального анализа данных для реализации на высокопроизводительных вычислительных системах», Грант РФФИ № 12388 (№ 11 - 01 - 00975) «Разработка теории и принципов управления точностью решения комбинаторно- логических задач на основе методов искусственного интеллекта и принятия решений».
Материалы диссертации использованы в учебном процессе на кафедре САПР в Таганрогском технологическом институте Южного федерального университета в цикле лекций и практических занятий по курсам «Автоматизация конструкторского и технологического проектирования», «Методы оптимизации» и «Эволюционное моделирование и генетические алгоритмы».
Апробация работы. Основные результаты диссертационной работы обсуждались и были одобрены на научных семинарах (с 2009 по 2012 гг., ТТИ ЮФУ), VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «МОЛОДЕЖЬ XXI ВЕКА — БУДУЩЕЕ РОССИЙСКОЙ НАУКИ» (г.Ростов-на-Дону, 2009), Молодежной научно- технической конференции «Интеллектуальные системы - 2009» («ИС-2009») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09» (Дивноморское, 2009 г.), Молодежной научно- технической конференции «Интеллектуальные системы - 2010» («ИС-2010») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-ІТ'ІО» (Дивноморское, 2010 г.), Молодежной научно- технической конференции «Интеллектуальные системы - 2011» («ИС-2011») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'12» (Дивноморское, 2012 г.).
Публикации. Результаты диссертации отражены в 13 печатных работах, в числе которых 2 - в изданиях, рекомендованных ВАК.
Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 147 страницы, а также 58 рисунков, 6 таблиц, список литературы из 107 наименований, 7 страниц приложений, в числе которых акты об использовании результатов диссертационной работы.
Построение математической модели задачи размещения
Большое значение с ростом сложности и размерности изготавливаемых СБИС, в конструкторском проектировании приобретает качество размещения элементов интегральных схем. Используя несколько тысяч компонентов СБИС получить качественное решение невозможно ручными методами. Задача размещения, остается актуальной и проблематичной, даже при уменьшении размерности задачи за счет декомпозиции элементов на блоки. Данная задача содержит сложный комбинаторный характер и нахождение ючного решения затруднено, поэюму для ее решения использую I формальные математические модели и алгоритмы [2-10].
Сформулируем тривиальную задачу размещения. Дано множесіво элементов (модулей) с расположенными на них выводами;
коммутационное поле (КП), па котором должны размета і вся элементы;
электрическая принципиальная схема, связывающая выводы элементов
Позиции для элементов на коммутационном поле буду і располаї аіься с посюянпым «шаюм» по вертикали и по горизонтали. Задача размещения опредсляеі для каждого элемента такие позиции па КП, при коюрых оптимизируется показатель качества [15]. Основной задачей размещения заключается в обеспечении благоприятных условий для последующих ірассировки и минимизации общей длины соединений. Минимизация общей длины соединений необходима для уменьшения временных задержек, возникающих в длинных цепях, что приводит к увеличению скорое 1 и обрабоїки информации [15].
На разных зіапах проектирования используют разные математические модели Эю об вменяется тем, что при решении задачи конструкторскою проектирования используют различные подходы, которые с различной точное 1ыо описывают одни и те же параметры.
Математическая модель - это совокупность математических обьскюв (чисел, переменных, векторов, множеств и т.п.) и отношений между ними, коюрая адекватно отображает некоторые свойства проектируемою техническою обьскта [27] К маїемаїическим моделям предъявляются следующие іребования
предеіавление начального обьекіа в просюй форме,
возможность перехода or одной математической модели к друї ой, 01 предеіавлсния обьекга к математической модели и обраню;
небольшой обьём занимаемой памяти для храпения информации о модели,
анализ математического аппарат для использования различных маїсмаїических моделей;
просюїа использования и дальнейшего функционирования
В сосіав любой схемы СБИС входит набор базовых элсменюв, связанных между собой определенным образом. Принимая во внимания данный факюр, схему можно прсдставиїь некоторым множссівом элсменюв аг, alt ai ап соединенных между собой цепями и з миожесіва R
Одной из іиироко востребованных математических моделей являє і ся і инерірафовая модель. Гиперграфовая математическая модель содержа і елыю онисывае і объекты и используется для создания алюри і мов консіруировапия, легко обрабатываемых па ЭВМ Исходя из вышесказанною, рассмотрим задачу размещения компонешов СЬИС па основе і иперграфовой математической модели [15, 27, 28, 29]
Счиїаюі, чю гиперграф Z = (N,M) задай, если задано множесіво вершин /V = /Vx U N2 и множество ребер М = {т1тг тк] , \N\ = I, \М\ =к Для каждого гиперребра устанавливается гюдмножеспзо вершин, 1С, VY Є {1,2, .,/ :} гу Є Nlt, где N/ соотвеїсівусі множесіву блоков комму іациоппой схемы, a N? - подмножсспзу входов и выходов комму і ациоппой схемы.
Условная коммутационная схема преде тавлена па рисунке 2 Сюиі оімеїиіь, чю Xy-Aj -блоки; ere5 - внешние связи; к\, к2 - вход и выход схемы, COOIBCICLBCHHO. Каждому гиперребру соотвеїсгвуюі элемешы схемы, соединенные одной электрической цепью.
Сложность алгоршмов решения задачи размещения гипсрірафовои маїсмаїической модели обьяснясіся сгрукіурой гиперграфа («плавающими» ребрами). Одними из главных достоиисів гиперграфовой модели являє і ся і очное определение главных конструктивных парамеїров усфойсіва, а іакже переход OL коммутационной схемы к маїемашческой модели не вызывает затруднений [15,27].
Учитывая тот факг, чго в коммутационной схеме содержится большое число разве пшённых цепей, т. о наиболее адекватной формой представления будет маїрица цепей, коюрая обозначается С=\си\т/, где f - наибольшее число контактов блоков, т - число элементов схемы 27] В )юм случае, с і рокам матрицы С соответствуют номера блоков, а столбцам номера кош актов. Гогда, номер ребра гиперграфа (цепи) подходящего к /-му коніакту /-і о элемента ставится па пересечении /-й сіроки и j-\ о сюлбца Одним и І недостатков матрица цепей является содержание избыючпои информации Но, тем не менее, данная информация удобна для оперирования с помощью ЭВМ
Проанализировав приведенные рассуждения, вьпекаеі вывод, о необходимое і и применения гиперграфовой математической модели для решения задачи размещения схем при проектировании СБИС I аким образом, для решения задачи размещения схем при проектировании СЬИС будем использовать гиперграфовую математическую мо/юль [15
Разработка гибридного двухуровневого подхода размещения компонентов СБИС
Рассмотрим гибридный двухуровневый алгориїм к исследованию окрсспіосіи поиска решений. Основная идея алгориіма заключается в последовательной рабоїе генеіического и зволюциоипої о алюриімов При гснсіическом поиске эволюционирует код обьекіа (хромосомы). В свою очередь, эволюционный алгориїм рабоїасі на основе с эволюционных преобразований обьекіа. Вводя в рабоїу двухуровневою подхода эволюционный алгориїм, уменьшается доля случаиносіи и увеличивасіся факюр направленности с адаптацией «жадного» алюриіма (оператора)
Под понятием «жадный» опера юр подразумевается языковая конструкция, позволяющая создавать новые альтернативные решения па основе выбора па каждой итерации оптимального значения целевой функции «Жадный» оператор может быть реалиювап как на двух и более хромосомах, іак и па всей популяции.
На рисунке 11 представим работу гибридною двухуровневою эволюционного алгоритма па основе интеграции гепеїическою — эволюционной) алюриімов поиска оптимальных решений задачи размещения компонентов СБИС в наиомсіровом диапазоне В основе эволюционных алюри шов (ЭА) лежа і принципы есіесівснпою зволюциоппоїо оібора. В настоящее время применяеіся 01 ромное количееіво ЭА, оіличающиеся формированием механизмов, а Laioice мзолюциоппых процедур и моделей предеіавлепия данных.
В эволюционном алгорише в роли основных элемеиюв применяются не оїдельиьіе особи (обьекіьі), а популяция лих обьекшв. На первом іпаїс создаеіся популяция обьекгов. Последующий процесс формирования решений предсіавляеі последоваїельиосіь циклов. На каждой иіерации производиіся оценка популяции индивидов. Н основе полученных данных формируеіся новая популяция решений. Эволюционный алюри ш прскращасіся pa6oLy, если на некоторой иіерации зволюции сформирована популяция, удовлеіворяющая заданным криіериям осіапова.
Эволюционный процесс основывается на выборе в новую популяцию «лучших» решений, полученных пуіем выживания из более МП01 очисленноїо поіомсіва.
Рабоїа двухуровневого алюри іма поиска ошимальпых решений начинается с посіуплепия основных данных, необходимые для рабо і ы алюриіма. К іаким данным опюсяіся парамеїрьі, описывающие коммуіационньїй блок или схему (количееіво элемеиюв, количееіво связей, количееіво внешних связей) Далее создасіся начальная популяция, размер ко юрой являемся входным посюяниым парамеїром, задаваемым пользоізаіелем, определяется и рассчиїьіваеіся значение ЦФ. Далее на основе і снеіичсского алюриіма формируеіся популяция лучших решений. На следующем шаге в работе применяется направленный эволюционный алюриім. Процессу эволюционный преобразований подвсргасіся каждый индивидуум популяции, полученный па сіадии генетическою поиска При лом преобразования направленный па получение лучшею решения. После рабоїьі мзолюционпой адашации, формирусіся список лучший решений В случаи, если максимальное число иіерации больше іекущего номера хромосомы, ю переходим к блоку гснеіического алгориша, і с к блоку формирование популяции на основе ГА. Если же максимальное число иіераций меньше іекуіцею номера хромосомы, і о конец рабоїьі алюри і ма
На каждой итерации примеияеіся два механизма получения новых членов популяции. Первый механизм - сіаидаршьій подход получения новых членов (решений) на основе генетических операторов (кроссиш овер, муіация и і.д). Вюрой механизм свяшн с оібором лучших решений применяя мсюды эволюционной адаптации.
В іаком алгориімс введен адашивиый филыр, оісскающий решения с ни жим значением ЦФ.
Таким образом, разрабоїаппьій модифицированный іибридпьій алгориїм обладает двухуровневой структурой. На первом уровне осуіцесівляеіся поиск использую медленный, по более ТОЧНЫЙ ІСНСТИЧССКИИ алюриїм, временная сложное і ь котрого па одной і операции приблизительно равен 0(п) - 0(п ). На втором уровне улучшаюіся перспективные хромосы, применяя быстрый эволюционный алюриїм, временная сложпосіь которого одной іеиерации приблизительно равна 0(п) Следуеі оімсіить, что поиск решений производи іся одновременно множеством решений. Из вышесказанного следует, что разрабоїанпая двухуровневая сірукіура позволяеі обьединять решения из различных области
Применение гибридного механизма для решения задач размещения компонентов СБИС
На основе описанного выше механизма предложим алі ори їм размещения элемспюв СБИС. Имееіся множесіво элемспюв и цепей Элемешы расположены в линейки. Линейки расположены па мопіажной плоскости. Пример іакого расположения указан на рисунке 27.
Формализуем пекоюрые понятия. Разработанная архиіекіура поиска рабо і асі с іаким попяшем, как число агентов (N). При решении задачи размещения элемспюв СБИС данное понятие ассоциируется с числом различных размещений элементов па монтажной плоское і и Іаким образом, аісні — множесіво координаї всех злеменюв схемы Число алыернажвных решений (S) - число наиболее перспекжвных различных размещений элемспюв. Таким образом, па нулевой итерации из одною начальною размещения необходимо получи і ь S различных размещений. Для эюго список цепей сортируется по возрасіапию количссіва коніакюв в цепи. Отсортированный список цепей па 10 злеменюв и 10 цепей показан в таблице 1. {П_1, Е_2, ..., Е_10} — номера элемспюв, {N_l, N_2, . ., N_10} - номера цепей. Данный список разбивасіся на S равных обласісй.
Гаким образом, каждая обласіь предсіавляеі собой (M/S) цепей, і це М - общее число цепей. Сооївеїсівсино в каждую область назначается N/S аіспіов. Каждый агеш получается путем одной парной нересіановки элемепюв, входящих в пепь из текущей области. То есть, если цепь N_l принадлежит области s_l, а элементы Ь_4 и Е_6 принадлежат цени N_l, ю один из аіенюв будет получен путем перестановки местами элементов Е_4 и Г_6. Если парные перестановки в рамках одной цепи невозможны, і о допускаются парные перестановки в рамках одной области Далее рассчитывается целевая функция для всех агентов. Из і-ой области в буфер решений перемещается один наиболее оптимальный агеш. После нулевой иіерации имеем S различных размещений элементов.
Первый іпаї іибридного поиска подразумевает рабоїу алюриіма. основанного па поведении колонии пчел. То есть для всех S размещении рассчитывается число агентов па основании значения целевой функции На данном шаїс под числом аісптов понимается размер начальной популяции В, для будущих ЭЛ и ГА. где F, - значение ЦФ для іекущего решения; E,s=0 j сумма значении целевой функции для всех решений из буфера решений, К - ко)ффициені расширения популяции. Коэффициеш К применяется при необходимоеIи пропорционально увеличить размеры популяций ЭЛ и ГЛ для более детального поиска.
Число иіерации ЭА и ГЛ іакже рассчитывается па основе значений целевой функции Максимально возможное число итераций 1тач для ЭЛ и ГЛ задаеіся лицом принимающим решение. На каждой итерации іибрицпою поиска для каждою ЭА и ГА число иіерации І, рассчиїьівасіся следующим образом і — vs P max (6)
В юрой шаг разделяется па два зіапа: эволюционный алюри їм и існеіический алгориім. Сначала производиіся поиск с помощью )волюционноі о алгориіма. Если хоія бы одно решение зволюциошюю алюриіма удовлеіворяеі условию R, і о данное решение переметає і ся в буфер решений. Процесс поиска в іскуіцей обласіи на данной иіерации заверите іся. Если же условие R не удовлетворено, і о в рабо і у всі упас і іепеїический алюри їм. С помощью условия R проверяемся, на какую величину в процентом соошошении эволюционный алюриїм улучшил значение целевой функции. Если зіа величина больше заданной, і о условие удовлеіворясіся. Всрояпюсть получения оптимальных решений с помощью і спеїического алгориіма выше, позі ому нецелесообразно испольюваїь правило R после завершения рабоїьі данного алюриіма Опишем использующийся ГСПС1ИЧССКИЙ алгориім. Оімеїим, чіо в рамках данной рабо і ы ЭЛ идешичеп ГЛ. Единсівепиое различие сосюиі в юм, чю ЭЛ не используеі операіор кроссинговсра. По) і ому подробно опишем сірукіуру і спеїического алгориіма.
Оімеїим, чю геисіический поиск іакже разбиваеіся па два мана На первом лапе производиіся іепеїический поиск в линейках. Па рисунке 28 предсіавлепа линейка, содержащая 8 злеменюв.
После Dioio проверяется условие осіапова алгориіма. В данной рабоїе условием осіапова могу і являїься: заданное число итераций, заданное значение целевой функции, время выполнения алгориіма. Если кршерий осіапова не досіигнуї, ю процесс поиска продолжасіея иіерационпо цо получения квазиопіимального решения. Блаюдаря использованию іибридпою подхода, сосюящего из ірех зіапов, и распараллеливанию процесса поиска сущесівеппо сокраіцаеіся верояпюсіь попадания в локальные ошимумы Разрабоїаниая иерархическая модель поиска позволяеі зффекіивно использовать выделенное время и операіивную памяіь
Определение временной сложности разработанного гибридного алгоритма
Определим временную сложность разработанного гибридного алгоритма. Зададим следующие параметры алгоритмов:
1. Генетический алгоритм (ГА): число итераций 3000, численность популяции - 100, количество перестановок элементов на одной итерации 20% от размера схемы (количества элементов схемы), вероятность оператора кроссинговера - 85%, вероятность оператора мутации - 20%, вероятность инверсии - 55%;
2. Эволюционный алгоритм (ЭА): число итераций - 3000, размер популяции - 100, вероятность ОК - 85%, вероятность ОМ - 20%, селекция -случайная, отбор - элитный;
3. Роевой алгоритм: число итераций - 3000, количество агентов -20, начальное количество агентов - разведчиков - 10, максимальное количество итераций - 1000, ограничение максимального количества агентов - разведчиков - 100, уровень миграций - средний;
4. гибридный алгоритм: число итераций - 3000, размер популяции -100, вероятность ОК - 85%, вероятность ОМ - 20%, селекция - случайная, отбор элитный, количество агентов 20, начальное количество агентов - разведчиков - 10, ограничение максимального количества агентов -разведчиков - 100, уровень миграций - средний;
Проанализировав выходные данные, автором отмечается, что временная сложность разработанного модифицированного гибридного алгоритма не выходит за пределы полиномиальной зависимости, и может быть выражена формулой: 0(aN )- 0(3N ), где N - число элементов схемы (размер решаемой задачи).
Проведем анализ зависимости времени работы от количества итераций алгоритмов. Исследования проводились на различных тестовых примерах, размер популяции равен 50 особям, вероятность ОК - 85%, ОМ - 20%), количество колоний ГА - 4, уровень миграций - средний. Усредненные результаты экспериментов отражены в таблице 4 и на рисунке 57.
Проанализировав полученные данные из таблицы и гистограммы, можно судить что, применение генетических и эволюционных алгоритмов целесообразнее на задачах малой размерности (до 2000 элементов), а при решении задачи размещения в размерности, приближенной к промышленным объёмам (более 5000 элементов), эффективным является гибридный алгоритм.
Одним из важных этапов при анализе алгоритмов, является проведение анализа на основе сравнения результатов с известными бенчмарками.
На основе анализа результатов, можно судить, что разработанный гибридный алгоритм в двух случаях улучшил результаты представленного алгоритма и (Dragon и Flow) и ещё в двух показал превосходство над обоими алгоритмами (таблица 6).
