Найти

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

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

  В.И. Данильченко , В.В. Бова , М. М. Семенова , С.В. Игнатьева , М. Б. Шайлиев

  2026-02-27

  Аннотация ▼

  Рассматривается одна из важных комбинаторных задач оптимизации – задача трехмерной упаковки. Оптимизация трехмерной упаковки снижает затраты и повышает эффективность логистики, что делает ее актуальной для промышленности. В работе проанализированы классические подходы, такие как жадные алгоритмы и динамическое программирование, а также широко применяемые методы, включая эволюционные алгоритмы и локальный поиск. Анализ существующих методов, включая жадный поиск, динамическое программирование, эволюционные алгоритмы и локальный поиск, позволил выявить их ключевые характеристики и определить подходящие области применения. В контексте данного анализа представлен обзор ключевых методов, доминировавших в определенные исторические периоды. Анализ включает рассмотрение условий применения различных методов, их эффективности для определенных типов задач, а также их преимуществ и ограничений. Представлен многоуровневый алгоритм поиска, который объединяет преимущества традиционных и современных методов оптимизации. Многоуровневый алгоритм позволяет улучшить точность решения задачи упаковки за счет динамической настройки параметров. Разработан программный комплекс для решения задачи оптимизации трехмерной упаковки с использованием биоинспирированных алгоритмов. Проведен вычислительный эксперимент на тестовых примерах (бенчмарках). Качество упаковки, полученное, на основе разработанного комбинированного биоинспирированного алгоритма, в среднем на 7 % превосходит результаты упаковки, полученные с использованием известных алгоритмов, а время решения меньше от 7% до 25%, что говорит об эффективности предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае временная сложность алгоритмов O(n²), в худшем случае – O(n³).

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

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

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

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

  Е. В. Данильченко , В. И. Данильченко , В. М. Курейчик

  2022-05-26

  Аннотация ▼

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