КО-ЭВОЛЮЦИОННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ НА ОСНОВЕ ВЗАИМОДЕЙСТВИЯ СУБПОПУЛЯЦИЙ, ОТЛИЧАЮЩИХСЯ СТРАТЕГИЯМИ ПОИСКА

Аннотация

Разработана новая методология и метод размещения элементов СБИС, отличающиеся
тем, что решение задачи размещения основывается на использовании фиксированного порядка
выбора позиций, ориентированного на эффективное решение задачи размещения, и эвристиче-
ской процедуры распределения элементов по позициям, позволяющие снизить общую трудоем-
кость, и повысить качество решения. Процесс формирования списка позиций на коммутацион-
ном поле осуществляется с использованием механизмов волнового алгоритма. В основу выбора
окончательного списка положен принцип построения маршрута с минимальной оценкой сум-
марной линейной длины расстояний между позициями маршрута. Для решения задачи разме-
щения разработан поисковый алгоритм на основе модифицированного метода муравьиной ко-
лонии. Для исключения преждевременной сходимости и локализации глобального экстремума
задачи разработка алгоритма производилась на основе ко-эволюционного подхода. Архитекту-
ра ко-эволюционного алгоритма размещения разработана на основе парадигмы муравьиного
алгоритма. В пространстве поиска субпопуляции параллельно реализуют четыре стратегии
оптимизации. В работе процесс ко-эволюции реализован на основе взаимодействия субпопуля-
ций, отличающихся стратегиями поиска. Отличительной особенностью используемого ко-
эволюционного подхода является то, что субпопуляции решений фактически являются вирту-
альными. Процесс ко-эволюции реализуется одной популяцией агентов Z путем последователь-
ного формирования и слияния, виртуальных субпопуляций решений в одну популяцию. В работе
решение задачи размещения направлено на повышение трассируемости посредством минимизации ресурсов, требуемых для реализации соединений. Существенный вклад в минимизацию
пространственной и временной сложности поисковой процедуры внесли: использование вирту-
альными субпопуляциями общей эволюционной памяти, общего графа поиска решений, форми-
рование единой интерпретации решения в виде маршрута на полном ориентированном графе с
бинарными ориентированными ребрами. Тестирование производилось на бенчмарках
19s, PrimGA1, PrimGA2. Результаты по сравнению с существующими алгоритмами улучшены
на 7-8%. Вероятность получения глобального оптимума составила 0.96. В среднем решения
отличаются от оптимального менее, чем на 1.5%. Временная сложность алгоритма при фик-
сированных значениях размера популяции и количества генераций составляет О(n). Общая вре-
менная сложность гибридного алгоритма составляет О(n2)–О(n3).