Найти

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

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

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

  2020-07-20

  Аннотация ▼

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

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

  В.В. Курейчик , А.Э. Саак , Вл.Вл. Курейчик

  2021-07-18

  Аннотация ▼

  Рассмотрена одна из важных задач оптимизации – задача диспетчеризации. Она от-
  носится к классу NP- сложных оптимизационных задач. В работе приведена и описана
  постановка задачи диспетчеризации. Здесь массив заявок пользователей на компьютерноеобслуживание в Grid- системах моделируется протяжённой линейной полиэдралью коор-
  динатных ресурсных прямоугольников. При этом диспетчирование представляется лока-
  лизацией линейной полиэдрали в оболочку области вычислительно-временных ресурсов сис-
  темы согласно многоцелевому критерию качества применяемого назначения заявок на об-
  служивание. В связи со сложностью данной задачи для ее эффективного решения предла-
  гаются методы эволюционного моделирования. В статье предложена и описана модифи-
  цированная архитектура эволюционного поиска. В качестве модификации введены допол-
  нительно три блока. Это блок «внешней среды», блок эволюционной адаптации и блок «не-
  перспективных решений». Для ее реализации авторами разработан модифицированный
  эволюционный алгоритм, использующий в качестве отбора решений модели эволюций Ч.
  Дарвина и Ж. Б. Ламарка. Это позволяет значительно сократить время получения резуль-
  тата, частично решить проблему преждевременной сходимости алгоритма и получать
  наборы квазиоптимальных решений за полиномиальное время. Разработан программный
  модуль на языке C#. Проведен вычислительный эксперимент на тестовых примерах. Про-
  веденные экспериментальные исследования, показали, что качество решений, полученных
  на основе разработанного эволюционного алгоритма, в среднем на 5 процентов превосхо-
  дит результаты решений, полученные с использованием известных алгоритмов последова-
  тельного, начально-кольцевого и уровневого при сопоставимом времени, что говорит об
  эффективности предложенного подхода.