Найти

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

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

  М.А. Ганжур , Б.К. Лебедев , О.Б. Лебедев

  21-37

  2025-10-01

  Аннотация ▼

  Целью работы является разработка и исследование методов биоинспирированного поиска для решения задач одномерной упаковки в одинаковые контейнеры на базе эффективных алгоритмов кодирования и декодирования решений, композитного критерия и двухуровневой структуры эволюционной памяти. В работе предложена структура упорядоченного кода упаковки одномерных элементов в одинаковые контейнеры главное достоинство которого заключается в том, что одному решению упаковки соответствует один код и наоборот. Поисковая процедура базируется на модифицированной метаэвристике муравьиного алгоритма. На каждой итерации алгоритм одномерной упаковки имеет многостадийную структуру. Стадии выполняются последовательно одна за другой, начиная с первой. Каждая стадия С_k включает процедуры, выполняемые агентом z_k. Число стадий равно числу агентов в популяции плюс заключительная стадия итерации. Основная задача, решаемая конструктивным алгоритмом на стадии С_k, заключается в построении кода R_k упаковки множества элементов X в одинаковые контейнеры. Стадия делится на периоды по числу формируемых агентом z_k  списков X_jк. Период делится на этапы. На каждом периоде последовательно по этапам решаются следующие задачи: агент z_k конструктивным алгоритмом формирует набор R_k упорядоченных списков X_jк одномерной упаковки в одинаковые контейнеры; рассчитываются оценки f_jk упаковки каждого контейнера O_j элементами списка <X_jк>; рассчитывается количество λ_jk феромона, пропорциональное оценке f_jk; рассчитывается оценка W_k=∑_i(f_jk) одномерной упаковки множества элементов X в H одинаковых контейнеров; производится отложение феромона на ребрах графа G, соответствующих списку X_jк в ячейки накопительной матрицы памяти E второго уровня. После формирования всеми агентами z_k популяции Z упорядоченных списков R_k, накопленный феромон добавляется в основную матрицу памяти Φ первого уровня. Для каждого R_k рассчитывается общий показатель F_k качества упаковки множества элементов X. Заключительная операция на итерации ‒ испарение феромона на ребрах графа G и фиксация z_k c лучшим F_k. Проведены экспериментальные исследования заключающиеся в выяснении качества работы метода на тестовых наборах большой размерности. Для сравнения разработанного алгоритма с известными методами и с приближенными алгоритмами авторами было выбрано несколько групп бенчмарок из различных источников

• БИОИНСПИРИРОВАННЫЙ ПОИСК В ПОЛНОМ ГРАФЕ СОВЕРШЕННОГО ПАРОСОЧЕТАНИЯ МАКСИМАЛЬНОЙ МОЩНОСТИ

  Б. К. Лебедев , О.Б. Лебедев , М. А. Ганжур , М. И. Бесхмельнов

  2025-01-30

  Аннотация ▼

  Разработана реконфигурируемая архитектура гибридной многоагентной системы поиска
  решений, базирующиеся на парадигмах роевых алгоритмов. Реконфигурируемая архитектура пу-
  тем настройки позволяет реализовать следующие методы гибридизации: высокоуровневую и низ-
  коуровневую гибридизацию вложением, типа препроцессор/постпроцессор, ко-алгоритмическую
  на базе одного или нескольких типов алгоритмов. Предложена методология синтеза совершенного
  паросочетания минимального веса в полном графе, основанная на базовых принципах гибридизации
  поисковых. эволюционных процедур. В работе агентами роя являются трансформирующиеся хро-
  мосомы, являющиеся генотипами решения. В качестве кода решения используется упорядоченный
  список множества вершин графа. Разработана структура упорядоченного кода паросочетания
  главное достоинство которого заключается в том, что одному решению (паросочетанию) соот-
  ветствует один код и наоборот. Определены свойства упорядоченного кода и разработаны алго-
  ритмы кодирования и декодирования. Работа гибридной системы начинается с генерации роем
  пчел случайным образом произвольного множества отличающихся друг от друга решений в виде
  исходного множества хромосом. Ключевой операцией пчелиного алгоритма является исследование
  перспективных решений и их окрестностей в пространстве поиска. Разработан метод формиро-
  вания окрестностей решений с регулируемой степенью подобия и близости между ними. На по-
  следующих этапах работы многоагентной системы выполняется поиск решений процедурами,
  построенными на основе гибридизации роевого и муравьиного алгоритмов. Отличительной осо-
  бенностью гибридизации является сохранение автономии гибридизируемых алгоритмов. Отме-
  тим, что для представления решений в алгоритмах используется единая структура данных, что
  упрощает стыковку разработанных процедур. Предлагается подход к построению модифициро-
  ванной парадигмы роя трансформирующихся хромосом. Поиск решений выполняющая в аффинном
  пространстве. В процессе поиска осуществляется перманентные трансформации (переход) хро-
  мосом в состояния с лучшим значением целевой функции решения (градиентная стратегия). Про-
  цесс поиска решений итерационный. На каждой итерации осуществляется трансформация (пере-
  ход) хромосом в состояния с лучшими значениями целевой функции решения. Целью трансформа-
  ции хромосомы, тяготеющей к лучшей хромосоме, в новое состояние является минимизация сте-
  пени различия, путем изменения взаимного расположения элементов в упорядоченном списке, что
  соответствует увеличению веса аффинной связи. Обновленные после трансформации хромосомы
  являются, в свою очередь, базовыми точками в последующих трансформациях. В результате экс-
  периментов было установлено, что показатели качества разработанных алгоритмов имеют бо-
  лее высокие значения чем в работах, представленных в литературе