Найти

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

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

  Д.В. Заруба , Э.В. Кулиев , Д. Ю. Запорожец , М. М. Семенова

  2021-11-14

  Аннотация ▼

  Статья посвящена решению новых актуальных проблем, возникших в условиях со-
  временного развития информационных и нанометровых технологий в области проектиро-
  вания, а также разработке новых инновационных методов, обеспечивающих получение
  эффективных решений за полиномиальное время. В статье рассматривается проблема
  решения NP-сложных задач. Приведено описание процедуры измерения сложности задачи.
  Описаны особенности NP- трудных и NP-сложных комбинаторно-логических задач. При-
  ведены основные различия между задачами, а также проблемы, с которыми приходится
  сталкиваться при решении такого вида задач. Представлена общая схема принятия реше-
  ний, состоящая из формулировки проблемы; принятие решения; сигнала в автоматических
  системах и обратной связи. На втором этапе (формирование и выбор вариантов решений)
  решение основывается на биоинспирированном алгоритме поиска решений задачи комми-
  вояжёра. Для решения поставленной задачи был разработан модифицированный биоинспи-
  рированный алгоритм, основанный на поведении муравьиной колонии. В отличие от других
  методов оптимизации, метаэвристические алгоритмы могут находить глобальные опти-
  мальные решения для задач, где существует много локальных решений из-за их случайного
  характера. Эти причины привели к широкому использованию таких алгоритмов при реше-
  нии различных задач оптимизации. Биоинспирированные алгоритмы становятся новой
  революцией в области решений оптимизационных задач. Представлена постановка задачи
  коммивояжера, а также решение поставленной задачи на основе муравьиного алгоритма.
  Алгоритмы, такие как генетические алгоритмы и PSO могут быть очень полезными, но
  они все еще имеют некоторые недостатки в решении проблем мультимодальной оптими-
  зации. Эти алгоритмы способны находить оптимальные решения независимо от физиче-
  ской природы проблемы. В рамках экспериментальных исследований был произведен анализ
  работы биоинспирированных алгоритмов: алгоритм стаи летучих мышей бактериальный
  алгоритм и муравьиный алгоритм.

• МУРАВЬИНЫЙ АЛГОРИТМ НА PYTHON

  Д.Ю. Зорькин , Л.В. Самофалова , Н.В. Асанова

  2025-01-30

  Аннотация ▼

  Данное исследование посвящено анализу и оптимизации муравьиного алгоритма для решения за-
  дачи коммивояжёра, являющейся классической NP-трудной проблемой комбинаторной оптимизации.
  Основная цель работы – экспериментальная оценка влияния параметров алгоритма на качество и эф-
  фективность поиска приближённых решений, а также разработка рекомендаций по их адаптивной
  настройке. В качестве тестового набора данных использован стандартный граф Berlin52 из библио-
  теки TSPLIB, содержащий координаты 52 городов с известным оптимальным маршрутом длиной
  7542 единицы. Эксперименты проводились в среде Python с использованием библиотеки ACO-Pants,
  реализующей муравьиный алгоритм. Была выполнена серия из 10 запусков с фиксированными парамет-
  рами: количество муравьёв (20), число итераций (100), коэффициенты влияния феромонов (α=1.0) и
  расстояний (β=2.0), а также скорость испарения феромонов (ρ=0.5). Результаты показали среднее
  отклонение от оптимума в 1.85%, с лучшим найденным решением 7675.23 (отклонение 1.67%). Для
  повышения эффективности алгоритма исследованы адаптивные механизмы динамической настройки
  параметров: линейное увеличение α (до 2.0) и уменьшение β (до 3.0), снижение ρ (до 0.3), а также рост
  числа муравьёв (до 30). Это позволило сократить среднее отклонение до 1.70% и повысить стабиль-
  ность решений. Особое внимание уделено анализу баланса между исследованием новых маршрутов и
  эксплуатацией накопленных данных. Установлено, что увеличение количества муравьёв улучшает ка-
  чество решений, однако после 30 агентов прирост эффективности снижается. Динамическая коррек-
  тировка параметров предотвращает преждевременную сходимость к локальным минимумам и уско-
  ряет поиск глобально оптимальных путей. Визуализация динамики сходимости подтвердила быстрое
  уменьшение длины маршрута на первых 20 итерациях с последующей стабилизацией. Практическая
  значимость работы заключается в демонстрации гибкости муравьиного алгоритма для задач мар-
  шрутизации в логистике и сетевом планировании. Результаты показывают, что ACO превосходит
  универсальные методы (например, генетические алгоритмы) по вычислительной эффективности для
  TSP. Разработанные рекомендации по настройке параметров могут быть применены для масштаби-
  рования алгоритма на графы большей размерности. Исследование подчёркивает важность адаптив-
  ных подходов в метаэвристической оптимизации и открывает перспективы для дальнейшего улучше-
  ния алгоритма за счёт гибридизации с другими методами.

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

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

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