Найти

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

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

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

  2020-07-20

  Аннотация ▼

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

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

  Э. В. Кулиев, А. А. Лежебоков, М. М. Семенова, В.А. Семенов

  2020-07-20

  Аннотация ▼

  Рассмотрены актуальные вопросы и проведен анализ проблемы трехмерной инте-
  грации и трехмерного моделирования, возникающей на этапе конструкторского проекти-
  рования в ходе решения задачи оптимального планирования компонентов больших и сверх-
  больших интегральных схем и корпусных устройств электронной вычислительной аппара-
  туры. Представлены и достаточно детально описаны основные преимущества примене-
  ния принципов трехмерной интеграции, позволяющие эффективно организовывать произ-
  водство персонифицированной электроники, оптимально планировать конфигурацию
  больших и сверхбольших интегральных схем с учетом тепловых и энергетических характе-
  ристик. В ходе выполнения исследований авторами разработан подход к кодированию ре-
  шений на основе интеллектуального механизма, который характеризуется наличием
  встроенных средств контроля допустимых решений. Одним из таких средств, экспери-
  ментально доказавших свою эффективность, является встроенный механизм «смертель-
  ных мутаций», учитывающий статусы генов и заранее заданные ограничения на итоговую
  конфигурацию корпуса проектируемого устройства. В работе предложен ряд общих под-
  ходов и конкретных алгоритмов решения задачи планирования, основывающихся на ре-
  зультатах исследований авторского коллектива и современных подходах к решению
  NP-полных задач. Важнейшим практически значимым результатом исследований обозна-
  ченной проблемы является разработанная программно-инструментальная платформа
  проектирования на современном кроссплатформенном языке программирования Java. Вы-
  бранная технология разработки позволяет использовать все основные достоинства со-
  временных многоядерных и многопроцессорных архитектур, по использованию программ-
  ной многопоточности для реализации параллельных схем решения комбинаторных задач.
  Программно-инструментальная платформа обладает дружественным интерфейсом, что
  позволяет эффективно управлять процессом решения задачи планирования компонентовбольших и сверхбольших интегральных схем трехмерной интеграции, путем визуализации
  ключевых показателей работы алгоритмов на графиках и в блоках текстовой статисти-
  ки. Разработанное прикладное программное обеспечение позволило провести серию вычис-
  лительных экспериментов, на основе наборов случайных данных также, как и наборах от-
  крытых данных бенчмарков для подобного рода задач. Результаты экспериментальных
  исследований позволили подтвердить теоретические оценки временной сложности и эф-
  фективности предложенных подходов и алгоритмов, в том числе генетического алгорит-
  ма, который использует предложенный в работе новый механизм кодирования решений.