Найти

Результаты поиска

• РАЗРАБОТКА МОДИФИЦИРАВАННЫХ МЕТОДОВ И МОДЕЛЕЙ ПОИСКОВОЙ АДАПТАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПЛАНИРОВАНИЯ СБИС

  О.Б. Лебедев , А.А. Жиглатый , Е.О. Лебедева

  2021-12-24

  Аннотация ▼

  В работе для решения задачи планирования СБИС разработан поисковый алгоритм
  на основе модифицированного метода муравьиной колонии. Задача формирования плана
  СБИС сводится к задаче формирования соответствующего польского выражения. Разра-
  ботанный метод синтеза польского выражения включает построение дерева разрезов,
  выбор типов разрезов (H или V), идентификацию и ориентацию модулей. Эволюционирую-
  щая популяция разбита на пары агентов. Каждый член популяции – пара агентов, рабо-
  тающих совместно. При этом конструктивные алгоритмы A1 и A2, используемые аген-
  тами пары различаются. Задача, решаемая алгоритмом А1, формулируется как задача
  поиска взаимно однозначного отображения Fk=M*→P множества модулей M c выбранны-
  ми ориентациями, |M*|=|M| в множество P позиций шаблона Sh. Фактически решение за-
  ключается в выборе на графе G1 подмножества ребер E*1E1, входящих в соответствующее отображение Fk. В алгоритме A2 в качестве модели пространства поиска реше-
  ний для выбора типа, последовательности и места расположения разрезов в шаблоне Sh
  разработан граф G2=(X, E2). X={(x1i,x2i)|i=1,2,…,n} множество вершин графа G2, соот-
  ветствует множеству P потенциальных позиций шаблона Sh для возможного размещения
  в них имен символов разрезов. Каждая потенциальная позиция piP шаблона Sh моделиру-
  ется двумя альтернативными вершинами (x1i,x2i). Выбор при размещении разрезов верши-
  ны x1i указывает на то, что в позицию pi помещен разрез типа V, выбор вершины x2i – ука-
  зывает на то, что в позицию pi помещен разрез типа H. Каждая итерация l общего алго-
  ритма включает начальный и три основных этапа. Начальный этап заключается в сле-
  дующем. Обнуляются матрицы ко-эволюционной памяти КЭП*1 и КЭП*2. На первом этапе
  каждая пара агентов dk=(a1k, a2k): – конструктивными алгоритмами A1 и A2 синтезирует
  свое решение Wk=(E1k
  *,Sk); – формируется польское выражение Shk, соответствующее
  решению Wk; – на базе Shk формируется дерево разрезов Tk; – на базе Tk формируется план
  Rk и рассчитывается оценка решения Fk; – агенты откладывают (добавляют) феромон в
  ячейки матриц коллективной эволюционной памяти КЭП*1 и КЭП*2, соответствующие
  ребрам решения Wk=(E1k
  *,Sk) в графах поиска решений G1 и G2 в количестве пропорциональном оценке решения Fk. На втором этапе феромон, накопленный в КЭП*1 и КЭП*2
  агентами популяции на итерации l, добавляется в КЭП1 и КЭП2. На третьем этапе осу-
  ществляется испарение феромона на ребрах графов G1 и G2. Тестовые испытания под-
  твердили эффективность предложенного метода. Временная сложность алгоритма, по-
  лученная экспериментальным путем, совпадает с теоретическими исследованиями и для
  рассмотренных тестовых задач составляет О(n2).

• БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ РЕШЕНИЯ ИНВАРИАНТНЫХ ГРАФОВЫХ ЗАДАЧ

  О.Б. Лебедев , А.А. Жиглатый

  2022-11-01

  Аннотация ▼

  Предлагается биоинспирированный метод решения набора инвариантных комбина-
  торно-логических задач на графах: формирования паросочетания графа, выделения внут-
  ренне-устойчивого множества вершин, выделения клики графа. Описывается модифициро-
  ванная парадигма муравьиной колонии использующая, в отличие от канонического метода,
  механизмы формирования решений на модели пространства поиска в виде звездного графа.
  Задача формирования в графе внутренне-устойчивого множества вершин может быть
  сформулирована, как задача разбиения. На начальном этапе на всех ребрах звездного графа
  H откладывается одинаковое (небольшое) количество феромона ξ/m, где m=|E|. Процесс
  поиска решений итерационный. Каждая итерация l включает три этапа. Агенты облада-
  ют памятью. На каждом шаге t в памяти агента ak имеется количество феромона фj(t),
  отложенного на каждом ребре графа H. На первом этапе каждый агент ak популяции
  конструктивным алгоритмом находит решение Ur
  0k, рассчитывает оценку решения
  ξk(Ur
  0k) и значение степени пригодности полученного агентом решения φk (количество фе-
  ромона, соответствующее оценке). На втором этапе, после полного формирования всеми
  агентами решений на текущей итерации, феромон ωj, накопленный в j-ой ячейке в буфер-
  ном массиве КЭПб, добавляется в каждую j-ю ячейку основного массива Q2={qj|j=1,2,…,m}
  коллективной эволюционной памяти КЭПo. На третьем этапе происходит общее испаре-
  ние феромона на множестве ребер E звездного графа H. Временная сложность алгоритма,
  полученная экспериментальным путем, совпадает с теоретическими исследованиями и для
  рассмотренных тестовых задач составляет О(n2).

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

  О. Б. Лебедев, А.А. Жиглатый

  2023-02-17

  Аннотация ▼

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