Введение 3
Постановка задачи 5
1. Обзорный раздел по предметной области 6
1.1. Задача о рюкзаке 6
1.2. Квадратичная Неограниченная Бинарная Оптимизация ... 7
1.3. Приближение рюкзака при помощи QUBO 8
1.4. Расширенный Метод Множителей Лагранжа 9
2. Разработка алгоритма 11
2.1. Теория 11
2.2. Метрики 12
3. Методика проведения экспериментов 15
3.1. Бенчмарк 15
3.2. Оптимизатор параметров 15
3.3. Эксперименты 15
4. Результаты 17
4.1. Результаты экспериментов 17
4.2. Выводы 22
Заключение 23
Благодарность 24
Список литературы 25
Задачи оптимизации играют важную роль в различных областях науки и техники. Одной из известных задач является задача о рюкзаке, которая встречается в таких приложениях, как планирование ресурсов, логистика, проектирование сетей и инвестиционные портфели. В задаче о рюкзаке необходимо выбрать из набора предметов подмножество таким образом, чтобы их суммарный вес не превышал заданное ограничение, а суммарная стоимость была максимальной.
Задача о рюкзаке является NP-полной, что означает, что с увеличением размера задачи время ее решения классическими методами возрастает экспоненциально. Это создает значительные проблемы при решении крупных экземпляров задачи, особенно в реальных приложениях, где точность и время решения критически важны. Классические методы оптимизации, такие как динамическое программирование, жадные алгоритмы и методы ветвей и границ, начинают плохо справляться с большими размерами задачи из-за высоких вычислительных затрат.
В связи с этими трудностями все больше внимания уделяется квантово- вдохновленным вычислениям, которые предлагают потенциальные преимущества в решении сложных задач оптимизации. Квантовые вычисления и квантово-вдохновленные методы, такие как QUBO (Quadratic Unconstrained Binary Optimization) и модели Изинга, способны эффективно находить решения для задач оптимизации, используя свойства квантовых систем. Эти методы моделируют задачи в виде энергетических состояний квантовых систем и используют квантовые флуктуации для поиска глобального минимума.
На сегодняшний день уже существуют несколько технологий и платформ, реализующих квантовые и квантово-вдохновленные вычисления. Например, компания D-Wave предлагает квантовые компьютеры на основе квантового отжига, которые специально предназначены для решения задач оптимизации [1]. Также IBM [2] и Google разрабатывают квантовые процессоры, которые могут использоваться для различных задач, включая оптимизацию. Квантовые вдохновленные вычисления, такие как алгоритмы, работающие на классических компьютерах, но использующие идеи из квантовой механики, также демонстрируют значительные успехи.
Данная работа направлена на исследование новых методов и алгоритмов, которые могут значительно улучшить эффективность решения задачи о рюкзаке и, возможно, других задач оптимизации.
В ходе работы были выполнены следующие задачи
• Была написана библиотека для загрузки и проверки квадратичной задачи о многомерном рюкзаке с несколькими вариантами выбора.
• Для задачи о рюкзаке разработан гибридный алгоритм решения на основе классических и квантово-вдохновленных методов.
• Произведен анализ работы реализованного алгоритма по сравнению c жадным алгоритмом.
• Разработанный алгоритм на основе ADMM в среднем показывает лучшие результаты по сравнению с жадным алгоритмом.
• Разработанное экспериментальное окружение позволяет проверить и повторять результаты.
Таким образом в выпускной квалификационной работе проведено исследование усиления алгоритмов оптимизации с использованием квантово- вдохновленных вычислений, что является актуальным результатом для решения широкого класса производственных задач в различных индустриях.
Содержание бакалаврской работы - Исследование усиления алгоритмов оптимизации с использованием квантово-вдохновленных вычислений на примере задачи о рюкзаке
Выдержки из бакалаврской работы - Исследование усиления алгоритмов оптимизации с использованием квантово-вдохновленных вычислений на примере задачи о рюкзаке
