КО-ЭВОЛЮЦИОННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ НА ОСНОВЕ ВЗАИМОДЕЙСТВИЯ СУБПОПУЛЯЦИЙ, ОТЛИЧАЮЩИХСЯ СТРАТЕГИЯМИ ПОИСКА
Аннотация
Разработана новая методология и метод размещения элементов СБИС, отличающиеся тем, что решение задачи размещения основывается на использовании фиксированного порядка выбора позиций, ориентированного на эффективное решение задачи размещения, и эвристиче- ской процедуры распределения элементов по позициям, позволяющие снизить общую трудоем- кость, и повысить качество решения. Процесс формирования списка позиций на коммутацион- ном поле осуществляется с использованием механизмов волнового алгоритма. В основу выбора окончательного списка положен принцип построения маршрута с минимальной оценкой сум- марной линейной длины расстояний между позициями маршрута. Для решения задачи разме- щения разработан поисковый алгоритм на основе модифицированного метода муравьиной ко- лонии. Для исключения преждевременной сходимости и локализации глобального экстремума задачи разработка алгоритма производилась на основе ко-эволюционного подхода. Архитекту- ра ко-эволюционного алгоритма размещения разработана на основе парадигмы муравьиного алгоритма. В пространстве поиска субпопуляции параллельно реализуют четыре стратегии оптимизации. В работе процесс ко-эволюции реализован на основе взаимодействия субпопуля- ций, отличающихся стратегиями поиска. Отличительной особенностью используемого ко- эволюционного подхода является то, что субпопуляции решений фактически являются вирту- альными. Процесс ко-эволюции реализуется одной популяцией агентов Z путем последователь- ного формирования и слияния, виртуальных субпопуляций решений в одну популяцию. В работе решение задачи размещения направлено на повышение трассируемости посредством минимизации ресурсов, требуемых для реализации соединений. Существенный вклад в минимизацию пространственной и временной сложности поисковой процедуры внесли: использование вирту- альными субпопуляциями общей эволюционной памяти, общего графа поиска решений, форми- рование единой интерпретации решения в виде маршрута на полном ориентированном графе с бинарными ориентированными ребрами. Тестирование производилось на бенчмарках 19s, PrimGA1, PrimGA2. Результаты по сравнению с существующими алгоритмами улучшены на 7-8%. Вероятность получения глобального оптимума составила 0.96. В среднем решения отличаются от оптимального менее, чем на 1.5%. Временная сложность алгоритма при фик- сированных значениях размера популяции и количества генераций составляет О(n). Общая вре- менная сложность гибридного алгоритма составляет О(n2)–О(n3).
