Найти

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

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

  В. В. Курейчик, А. Е. Глущенко

  2020-07-20

  Аннотация ▼

  Рассмотрена одна из важных комбинаторных задач оптимизации – задача трехмер-
  ной упаковки разногабаритных элементов в объеме. Она относится к классу NP- сложных
  и трудных оптимизационных задач. В работе приведена и описана постановка задачи трех-
  мерной упаковки в объеме, введена комбинированная целевая функция учитывающая все огра-
  ничения. В связи со сложностью данной задачи предлагается многоуровневый подход заклю-
  чающийся в разделение задачи трехмерной упаковки на 3-и подзадачи и решения каждой под-
  задачи в строгом порядке. При этом для каждой из подзадач определен уникальный набор
  объектов, не повторяющихся в остальных подзадачах. Для реализации многоуровневого под-
  хода авторами разработан комбинированный биоинспирированный алгоритм, основанный на
  эволюционном и генетическом поиске. Такой подход позволяет значительно сократить время
  получения результата, частично решить проблему предварительной сходимости алгоритмов
  и получить наборы квазиотимальных решений за полиномиальное время. Разработан про-
  граммный комплекс и реализованы на ЭВМ алгоритмы автоматизированной трехмерной
  упаковки на основе комбинированного биоинспирированного поиска. Проведен вычисли-
  тельный эксперимент на тестовых примерах (бенчмарках). Качество упаковки, получен-
  ное, на основе разработанного комбинированного биоинспирированного алгоритма, в сред-
  нем на 5 % превосходит результаты упаковки, полученные с использованием известных
  алгоритмов, а время решения меньше от 5 % до 20 %, что говорит об эффективности
  предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить
  теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае вре-
  менная сложность алгоритмов O(n2), в худшем случае – O(n3).

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

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

  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. Проведены экспериментальные исследования заключающиеся в выяснении качества работы метода на тестовых наборах большой размерности. Для сравнения разработанного алгоритма с известными методами и с приближенными алгоритмами авторами было выбрано несколько групп бенчмарок из различных источников