Найти

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

• ПРОГРАММНАЯ ПОДСИСТЕМА ДЛЯ РЕШЕНИЯ NP-СЛОЖНЫХ КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ НА ГРАФАХ

  В.В. Курейчик , Вл. Вл. Курейчик

  2021-07-18

  Аннотация ▼

  Работа посвящена созданию программной подсистемы для решения NP- трудных и
  NP-сложных комбинаторно-логических задач на графах. В статье приведено описание
  комбинаторно-логических задач на графах. Для эффективного их решения предлагаются
  новые многоуровневые архитектуры поиска, такие как простая комбинированная, парал-
  лельная комбинированная, двухуровневая, интегрированная и гибридная. Данные архитек-
  туры основаны на методах, инспирированных природными системами. Ключевым отличием данных архитектур является разделение поиска на два или три уровня и применение на
  них различных алгоритмов эволюционного моделирования и биоинспирированного поиска.
  Это позволяет получать наборы квазиоптимальных решений выполнять параллельную
  обработку и частично устранять проблему преждевременной сходимости. В статье при-
  ведено подробное описание разработанной программной подсистемы и ее модулей. В каче-
  стве модулей в подсистеме имеется пять разработанных архитектур и набор разрабо-
  танных алгоритмов эволюционного моделирования и биоинспирированного поиска, таких
  как эволюционный, генетический, пчелиный, муравьиный, светлячковый и обезьяний. Благо-
  даря модульной структуре в подсистеме имеется возможность конструировать более 50
  различных вариантов комбинаций поиска. Это позволяет использовать все достоинства
  методов биоинспирированной оптимизации для эффективного решения NP-сложных ком-
  бинаторно-логических задач на графах. Для подтверждения эффективности разработан-
  ной программной подсистемы был проведен вычислительный эксперимент на тестовых
  примерах. Проведенные серии тестов и экспериментов показали преимущество использо-
  вания программного продукта для решения комбинаторно-логических задач на графах
  большой размерности, по сравнению с известными алгоритмами, что говорит о перспек-
  тивности применения такого подхода. Временная сложность разработанных алгоритмов
  в лучшем случае O(nlogn), в худшем случае – О(n3).

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

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

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