На правах рукописи
БАЛЮК Любовь Владимировна
РАЗРАБОТКА И ИССЛЕДОВАНИЕ
ИНТЕГРИРОВАННЫХ АЛГОРИТМОВ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ НА ОСНОВЕ МЕТОДОВ ЭВОЛЮЦИОННОГО МОДЕЛИРОВАНИЯ
Специальности: 05.13.12 – Системы автоматизации проектирования, 05.13.17 – Теоретические основы информатики
Автореферат
диссертации на соискание ученой степени
кандидата технических наук
Таганрог 2007
Работа выполнена в Южном федеральном университете.
Научный руководитель: доктор технических наук, профессор
Курейчик Владимир Викторович.
Научный консультант: кандидат технических наук, доцент
Нужнов Евгений Владимирович.
Официальные оппоненты: доктор технических наук, профессор
Ковалев Сергей Михайлович (Ростовский государственный университет путей и сообщений, г. Ростов-на-Дону),
кандидат технических наук, доцент
Родзин Сергей Иванович (Технологический институт Южного федерального университета в г. Таганроге).
Ведущая организация: Федеральное государственное унитарное предприятие «Таганрогский научно-исследовательский институт
связи», г. Таганрог.
Защита диссертации состоится 4 июля 2007 г. в 1420 на заседании диссертационного совета Д 212.208.22 при Южном федеральном университете по адресу: 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406.
С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.
Автореферат разослан « 1 » июня 2007 г.
Ученый секретарь
диссертационного совета Д 212.208.22,
д октор технических наук, профессор Целых А.Н.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Использование достижений современной микроэлектроники при производстве интегральных схем (ИС), больших и сверхбольших ИС (БИС и СБИС), систем на кристалле, привело к изменению требований к основным характеристикам проектируемых на их основе электронных вычислительных средств (ЭВС).
Большой вклад в разработку и исследование интеллектуальных систем автоматизированного проектирования (САПР) ЭВС внесли В.И. Анисимов, Б.В. Баталов, Д.И. Батищев, А.М. Бершадский, Л.С. Берштейн, Ю.Х. Вермишев, В.М. Курейчик, В.В. Курейчик, Н.Я. Матюхин, А.Н. Мелихов, И.П. Норенков, В.А. Селютин, Ш. Айкерс, М. Бреуэр, Н. Шервани и многие другие.
Применение на этапе проектирования САПР разного уровня способствует повышению степени интеграции БИС на уровне узлов и блоков ЭВС. Сегодня БИС способны выполнять сложнейшие наборы функций, содержат более миллиона транзисторов на кристалле, а сами геометрические размеры транзисторов сократились до 0.18 мкм и менее.
Среди типовых задач этапа конструкторского проектирования БИС размещение их элементов и трассировка соединений являются наиболее проблемными. Обычный состав БИС насчитывает несколько сотен логических блоков, и размещаемая схема обычно занимает до 80% ее площади. В условиях современного развития информационных технологий, многие алгоритмы автоматизированного проектирования не справляются с решением или требуют много процессорного времени для поиска эффективных решений.
Таким образом, выбор оптимальных решений и характеристик при синтезе конструкций ЭВС является затруднительным в связи со сложной системой начальных условий и ограничений, а также в связи с экспоненциальным ростом вычислительной сложности алгоритмов. Поэтому при решении задач конструкторского синтеза ЭВС для снижения размерности выполняются различные способы декомпозиции задачи.
В этой связи диссертационная работа посвящена решению актуальной и важной научно-технической проблемы: разработке и исследованию новых и развитию существующих алгоритмов решения задачи размещения фрагментов БИС, обеспечивающих не только достижение требуемых результатов, но и поднимающих процесс исследования на высокий уровень, не требующий от ученых-исследователей навыков в области программирования.
Данная работа является развитием результатов исследований, проводимых на кафедре САПР Таганрогского технологического института Южного федерального университета в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» (2006 – 2008 гг.) на тему «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».
Цель диссертационной работы состоит в разработке и исследовании интегрированных алгоритмов размещения элементов (фрагментов и групп фрагментов БИС) на основе методов эволюционного моделирования. Для достижения поставленной цели в работе были решены следующие основные задачи:
Построена архитектура интегрированного бионического поиска решения задачи размещения фрагментов БИС.
Разработаны бионические алгоритмы размещения.
Построены модифицированные генетические операторы.
В качестве методов решения поставленных задач в диссертационной работе использовались элементы теорий множеств, алгоритмов, графов, а также методы и средства эволюционного моделирования, генетического поиска, теории вычислительных систем, параллельного и объектно-ориентированного программирования.
Научная новизна работы заключается в решении задачи размещения фрагментов БИС на основе интегрированного подхода. В работе:
Построена архитектура интегрированного поиска решений задачи размещения фрагментов БИС, основанного на методах эволюционного моделирования.
Разработаны новые и модифицированные методы эволюционного моделирования, позволяющие частично решать проблемы предварительной сходиомсти алгоритмов.
Разработан модифицированный алгоритм Ant Colony размещения фрагментов БИС, позволяющий получать множество квазиоптимальных решений.
Построены новые и модифицированные операторы генетического поиска, ориентированные на задачи автоматизированного конструкторского проектирования и позволяющие сокращать область поиска.
Разработаны стратегия интегрированного поиска на основе заданных критериев оптимизации с использованием параллельных вычислений и механизм синхронизации полученных решений на всех этапах поиска (оператор миграции).
К числу наиболее важных научных результатов диссертации относятся:
новая интегрированная архитектура процесса размещения фрагментов и/или групп фрагментов БИС, основанная на методах эволюционного моделирования;
новая модифицированная архитектура алгоритма Ant Colony для решения задачи размещения фрагментов БИС;
новые и усовершенствованные операторы генетического поиска на основе «Золотого сечения», кодов Хаффмана, метода «Простых чисел», обеспечивающие уменьшение времени поиска.
Практическая ценность работы заключается в реализации программного комплекса «In4Placement», использование которого позволяет на 10-30% ускорить процесс синтеза сложных систем, повысить качество размещения на 29% по сравнению с существующими аналогами, благодаря использованию интегрированного подхода к решению задачи размещения. Данная среда позволяет автоматизировать процесс размещения, сделать его доступным для специалистов различных областей науки, не обладающих навыками программирования.
Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Технологического института Южного федерального университета «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска» и «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».
Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при преподавании следующих дисциплин: «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».
Апробация основных теоретических и практических результатов работы. Результаты диссертации докладывались и обсуждались на Всероссийских и Международных научно-технических конференциях: «Интеллектуальные САПР», (г. Таганрог, 2003 - 2005 гг.); VII Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», (г. Таганрог, 2004г.); II Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г. Таганрог, 2004 г.); Международная конференция «Интеллектуальные системы (IEEE AIS’04)», (с. Дивноморское, 2004 г.); III Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г. Таганрог, 2005 г.); 1 ежегодная научная конференция студентов и аспирантов базовых кафедр ЮНЦ РАН, (г. Ростов-на-Дону, 2005 г.), Международная конференция «Интеллектуальные системы (IEEE AIS’05)», (с. Дивноморское, 2005 г.); Международная конференция «Интеллектуальные системы (IEEE AIS’06)», (с. Дивноморское, 2006 г.); Международная научно-техническая конференция «Интеллектуальные САПР», (г. Таганрог, 2006 г.).
Получено свидетельство об официальной регистрации программы для ЭВМ № 2006613139, 2006 г.
Публикации. По теме диссертационной работы опубликовано 10 печатных работ, сделано 4 доклада на Всероссийских и Международных научно-технических конференциях.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 157 страницах, содержит 51 рисунок, 4 таблицы, 112 наименований библиографии и приложения.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении дано обоснование актуальности темы диссертационной работы, описаны цель работы и основные научные положения, выносимые на защиту, определены круг задач, объект и предмет исследования, указаны методы исследования, показаны научная новизна и практическая значимость, а так же подтверждены достоверность полученных результатов.
В первой главе рассмотрены основные проблемы и перспективы решения задач размещения, приведена постановка задачи размещения фрагментов БИС. Решаемая в диссертационной работе дискретная задача размещения может быть сформулирована следующим образом. На прямоугольную конструкцию накладывается Декартова система координат с осями s и t, определяющая граф Gr, задающий собой координатную решетку.
Задача размещения сводится к отображению заданного графа-модели G=(X,U) схемы в решетку Gr таким образом, чтобы множество вершин  ,  , графа G размещалось в узлах решетки, число которых конечно, а также соблюдался интегрированный критерий Compl(G), представляющий собой интегрированную целевую функцию (ЦФ):
 (1)
где:
L_Kr(G) – длина критических связей (длина гамильтоновых цепей в графе);
L_GA(G) – величина суммарной длины соединений стремилась к минимуму;
N_Kr>0 и N_GA=0 – условие оптимизации ЦФ, основанное на соблюдении критерия длин критических связей;
N_Kr=0 и N_GA>0 – условие оптимизации ЦФ, основанное на выполнении критерия суммарной длины соединений;
N_Kr>0 и N_GA>0 – условие оптимизации ЦФ, основанное на одновременном соблюдении критериев длин критических связей и суммарной длины соединений;
α, β – коэффициенты полезности вышеуказанных критериев, которые определяются на основании конструкторского опыта или экспертных оценок;
Compl_Kr(G) – комплексный критерий оценки качества размещения на основе длин критических связей, определяющийся формулой:
 (2)
В диссертационной работе под критической связью понимается гамильтонова цепь – гамильтонов цикл без возвращения в стартовую вершину. Пройдя по всем вершинам графовой модели КС один раз и достигнув конечной, мы не будем возвращаться в исходную – исключим из рассмотрения последнюю итерацию алгоритма AC. Такая модификация AC позволит свести поиск критических связей к определению гамильтоновых цепей в неориентированном конечном графе.
Суммарная длина (весовая функция) рассчитывается по формуле «достроенной» критической связи:
 (3)
где:
 - расстояние между вершинами  и  графа G, отождествленными с узлами i и j решетки;
 - число кратных ребер между этими вершинами.
Выходная информация представляет собой список S, T координат на КП для всех модулей.
Требование оптимизации: Compl(G) min, т.е. чтобы весовая функция была наименьшей для всевозможных способов отождествления вершин графа и узлов решетки.
Пространство решений – множество всех целых чисел. Ограничения:
2n10000, где n – число вершин в графе G;
 , если  ,
 , если  ,
>0, элементы в силу геометрических ограничений не могут накладываться друг на друга.
Отмечено, что при решении задач размещения фрагментов БИС необходимо использовать модели, учитывающие предварительные знания о решаемых задачах.
Приведены модифицированная классификация и краткий обзор существующих методов и критериев оценки качества эффективности размещения. Указано, что перспективна разработка совместных генетических и поисковых алгоритмов, позволяющих решать проблемы предварительной сходимости и получать наборы эффективных решений.
Во второй главе рассмотрены принципы решения задач размещения фрагментов БИС. Построена архитектура интегрированного поиска, обеспечивающая поддержку следующих действий:
анализ графовой модели коммутационной схемы, полученной на этапе выполнения предыдущего шага конструкторского проектирования (решения задачи компоновки), с использованием модифицированного алгоритма Ant Colony (MAАС);
создание начальных популяций альтернативных решений размещения фрагментов БИС на основе результатов выполнения п. 1;
реализация методов эволюционного моделирования в соответствие с выбранным критерием оценки качества размещения:
реализация быстрого эволюционного поиска (использование оператора мутации);
выполнение генетического поиска (использование различных генетических операторов);
адаптация полученных решений к внешней среде на основе метаэволюции (использование оператора миграции);
вывод окончательного размещения и переход на следующий шаг конструкторского проектирования – решение задачи трассировки.
Сформулированы генетические и эволюционные стратегии размещения, приведена стратегия параллельного поиска при решении задачи размещения фрагментов БИС, который может быть сегментирован как набор процессов, каждый из которых выполняется отдельно и (при необходимости) осуществляет взаимодействие с другими процессами. Предложены модифицированные архитектуры «соподчинения» для реализации параллельного интегрированного поиска.
Разработаны модифицированные операторы кроссинговера, мутации, инверсии, селекции, рекомбинации, позволяющие асимптотически определять число перспективных решений, переходящих в следующую генерацию.
Приведена технология преобразования популяции при переходе из одной итерации поиска в другую, позволяющая закреплять квазиоптимальные решения, на основе использования разработанного оператора миграции.
В третьей главе разработан интегрированный алгоритм, представленный на рис. 1.
Рис 1. Структурная схема интегрированного алгоритма размещения фрагментов БИС
Он основан на использовании методов эволюционного моделирования: модифицированного алгоритма Ant Colony (МАAC), усовершенствованного бионического поиска для решения задачи размещения фрагментов БИС. Здесь:
N_GA – число итераций генетического алгоритма размещения фрагментов БИС,
Nmax – число итераций интегрированного алгоритма,
t – текущая итерация интегрированного алгоритма,
N_om – число итераций эволюционного алгоритма размещения,
Compl – значение комплексного критерия оценки качества размещения,
N_Kr – число критических связей,
L_Kr(G) – длина критических связей в графовой модели схемы.
Модификация алгоритма Ant Colony (AC) используется как блок анализа перед моделированием модифицированного бионического поиска. Далее выполняется коррекция размещения на основе выбранных критериев оценки качества двумерного размещения: суммарной длины соединений и длин критических связей в графовой модели коммутационной схемы. Коррекция заключается в выделении и размещении «строительных блоков» и и/или фрагментов БИС, не входящих в сформированные строительные блоки (СБ).
Представленный алгоритм позволяет получать наборы квазиоптимальных решений задачи размещения за полиномиальное время.
Разработаны и описаны эвристики сжатия коммутационных схем большой размерности на основе выделения СБ.
Эвристика 1 эффективна при небольшом числе (n<1000) вершин графовой модели КС и заключается в том, что:
вершины, соединенные ребрами с меньшей длиной, в линейке располагаются на максимальном расстоянии,
вершины, соединенные ребрами с максимальными весами объединяются в блоки и не модифицируются генетическими операторами.
Когда КС задана в виде графа решетки, возможно упрощение за счет иерархической процедуры сжатия графа, проводимой до моделирования ИА. Граф решетки на основе известных методов превращается в линейку. При этом размер графа резко уменьшается.
Эвристика 1 позволяет повысить быстродействие предложенного автором интегрированного алгоритма и при количестве вершин графа n<1000. При этом первые w<<n (w=1, 2,…, n) вершин графа группируются в строительные блоки, фиксируются в линейке на основе эвристики 1. Остальные (n–w) вершин графа размещаются на основе эволюционной части модифицированного бионического алгоритма. Отметим, что величину w задает экспертная подсистема размещения.
Эвристика 2 выполняется, если количество вершин больше 1000, и состоит в следующем:
графовая модель схемы сжимается, превращаясь в «горизонтальную» линейку за счет модификации связей между строительными блоками;
каждый строительный блок представляет собой «вертикальную» линейку;
на основе использования генетических операторов осуществляется размещения каждой линейки в отдельности.
При размещении СБ в виде групп фрагментов БИС, в отличие от отдельных вершин в линейке, появляется возможность прогнозировать размещение на шаг вперед, что повышает точность размещения и быстродействие предложенного алгоритма. Прогноз осуществляется на основе эвристик 1 и 2. Результат окончательного размещения зависит от эффективности сжатия графовой схемы, выбора критерия оценки качества размещения (стратегия «поиск-эволюция-поиск» или «эволюция-поиск-эволюция») и операторов интегрированного поиска.
Предложенная структура параллельного интегрированного алгоритма (ИА) показана на рис. 2.
Рис. 2. Структура параллельного интегрированного алгоритма
Выработан механизм обмена данными в структурах параллельного и последовательно-параллельного алгоритмов. При этом для каждого альтернативного варианта предлагается проводить процесс эволюции, начиная с предварительного сжатия модели и заканчивая размещением фрагментов БИС внутри блоков. Предусматривается несколько вариантов реализации этих процедур на основе последовательных, последовательно-параллельных и параллельных стратегий путем иерархического управления. Временная сложность алгоритма является полиномиальной.
Рассмотрены примеры сжатия коммутационной схемы и работы предложенного интегрированного алгоритма размещения на тестовых задачах.
В четвёртой главе описаны цель и основные задачи программного комплекса решения задач размещения, компоненты разработанной программной реализации предложенного в работе интегрированного алгоритма на основе методов эволюционного моделирования (модифицированного бионического, эволюционного, генетического поиска и алгоритма AC).
Графический интерфейс пользователя программного комплекса «In4Placement» представлен на рис. 3.
Рис. 3. Графический интерфейс пользователя программного комплекса «In4Placement»
Программный комплекс для решения задач размещения фрагментов БИС, включает построение подсистем ввода данных, управления, моделирования, вывода и представления результатов работы алгоритма.
Реализованный программный комплекс является гибким, легко настраиваемым. Графическое представление зависимостей ЦФ и времени от варьируемых параметров интегрированного поиска позволяет оценить быстродействие и практическую эффективность реализованных в системе алгоритмов.
Здесь же приведены результаты вычислительного эксперимента при анализе разработанного алгоритма на тестовых примерах. Произведено сравнение разработанного алгоритма с существующими аналогами решения задач размещения фрагментов БИС. Наиболее значимые результаты вычислительного эксперимента отражает следующий фрагмент таблицы.
Таблица (фрагмент)
Сравнительный анализ эффективности размещения при использовании различных алгоритмов
Столбцы приведенного фрагмента таблицы описывают: первый – номер эксперимента (тестовой задачи), второй – число генераций алгоритмов, значения ЦФ рассматриваемых тестовых задач и времени моделирования ИА, параллельного интегрированного алгоритма (ПИА), последовательного алгоритма (ПА), итерационного алгоритма (ИтА) и генетического алгоритма (ГА) далее парами соответственно.
Исходя из приведенных в таблице результатов экспериментальных исследований, можно сделать вывод, что предложенная в работе параллельная стратегия использования интегрированного алгоритма позволяет: получать набор квазиоптимальных решений, является гибкой, обладает высоким быстродействием (15%-30%) на одних и тех же входных данных. ВСА≈O(n2).
Все это говорит об эффективности рассматриваемого метода по сравнению с существующими аналогами.
В заключении сформулированы основные выводы и результаты диссертационной работы.
В приложении приведены акты об использовании результатов диссертационной работы.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
В ходе выполнения диссертационной работы получены результаты:
На основе анализа существующих методов размещения обоснована актуальность разработки интегрированных алгоритмов, обеспечивающих получение квазиоптимальных решений за полиномиальное время.
Сформулированы стратегии и принципы, построена архитектура интегрированного поиска на основе методов эволюционного моделирования, позволяющих эффективно управлять поиском, повышать быстродействие системы, получать квазиоптимальные решения за полиномиальное время.
Предложены новые и усовершенствованные генетические операторы, обеспечивающие уменьшение времени поиска.
Разработан и реализован модифицированный алгоритм Ant Colony, позволяющий частично решить проблему предварительной сходимости и существенно увеличить быстродействие интегрированного алгоритма размещения фрагментов БИС.
Разработана параллельная стратегия интегрированного поиска на основе модифицированного алгоритма Ant Colony и бионического поиска, обеспечивающая распараллеливание вычислений.
Предложен механизм обмена данными в структуре параллельного поиска на основе оператора миграции, позволяющий синхронизировать решения на всех этапах поиска.
Разработан программный комплекс, позволяющий проводить сравнительный анализ предложенного алгоритма с существующими, на основе выполнения тестовых задач.
Выполнены тестирование и обработка экспериментальных данных, что позволило уточнить теоретические оценки временной сложности разработанных алгоритмов размещения. Проведенные исследования показали улучшение предложенных алгоритмов по качеству размещения на 29% и времени решения от 10% до 30% по сравнению с известными методами.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
Балюк Л.В. Исследование влияния генетических алгоритмов на точность модели». Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР». Материалы Международной научно-технической конференции «Интеллектуальные САПР». Таганрог: Изд-во ТРТУ, 2003, №2(31). – 329 с.
Балюк Л.В., Курейчик В.В. Вероятностный генетический алгоритм Ant Colony и его приложение для решения задач (на примере задачи о коммивояжере). Труды Международных научно-технических конференций «Интеллектуальные системы» (IEEE AIS’04) и «Интеллектуальные САПР (CAD-2004)». – М.: Изд-во Фихматлит, 2004, т.1. Тираж 250 экз. с. 53-65.
Балюк Л.В., Курейчик В.В. Исследование возможностей, предоставляемых вероятностными генетическими алгоритмами, для решения комбинаторных задач. Труды VII Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления». – Таганрог: Изд-во ТРТУ, 2004. Тираж 700 экз. с. 89 – 90.
Балюк Л.В. Исследование возможностей, предоставляемых вероятностным генетическим алгоритмом Ant Colony, для решения задачи о коммивояжере. Труды II Всероссийской научной конференции молодых ученых, аспирантов и студентов. «Информационные технологии, системный анализ и управление». – Таганрог: Изд-во ТРТУ, 2004. Тираж 80 экз. с. 74-76.
Балюк Л.В. Исследование влияния бивариантных генетических алгоритмов на точность определения модели. Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Материалы международной научно-технической конференции "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2005, №3(47). с. 220 – 221.
Балюк Л.В. Исследование возможностей оптимизации комбинированных алгоритмов решения задачи размещения. III Всероссийская научная конференция молодых учёных и аспирантов «Информационные технологии, системный анализ и управление». Таганрог: Изд-во ТРТУ, 2005. с. 113 – 116.
Балюк Л.В. Исследование влияния бивариантных генетических алгоритмов на точность построения моделей. Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS’05) и «Интеллектуальные САПР» (CAD-2005). Научное издание в 3-х томах. – М.: Изд-во Физико-математической литературы, 2005, Т.1. с. 20 – 22.
Балюк Л.В. Сравнительный анализ возможностей вероятностного генетического алгоритма Ant Colony c алгоритмами полного перебора с симметричной матрицами для решения задачи о коммивояжере. Материалы первой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН.
Балюк Л.В. Возможности комбинированных стратегий решения задачи размещения разногабаритных элементов СБИС. Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS’06) и «Интеллектуальные САПР» (CAD-2006). Научное издание в 3-х томах. – М.: Изд-во Физико-математической литературы, 2006, Т.1. с. 552-557.
Балюк Л.В. Генетические алгоритмы решения задачи размещения элементов СБИС. Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2006. №8 (63). – с. 66-72.
В работах [2, 3], опубликованных в соавторстве, лично автору принадлежат следующие результаты - модификация вероятностного генетического алгоритма Ant Colony для решения задачи размещения фрагментов БИС с установленным критерием минимизации взвешенной длины соединений графового эквивалента электрической схемы. Изначально данный подход был разработан для решения задачи коммивояжера. На основе проведенных исследований были усовершенствованы значения входных параметров данного алгоритма, позволившие получить эффективное решение поставленной задачи за минимальное, по сравнению с существующими аналогами, время.
Соискатель Л.В. Балюк
Т ип. ТТИ ЮФУ Заказ № _______ тир. _______ экз.
|
