Найти

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

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

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

  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).