ALNS

alns — это общая, хорошо документированная и протестированная реализация метаэвристики адаптивного поиска в больших окрестностях (ALNS) в Python. ALNS — это алгоритм, который можно использовать для решения сложных задач комбинаторной оптимизации. Алгоритм начинается с начального решения. Затем алгоритм повторяется до тех пор, пока не будет выполнен критерий остановки. На каждой итерации выбираются операторы уничтожения и восстановления, которые преобразуют текущее решение в возможное решение. Это потенциальное решение затем оценивается по критерию приемки, и схема выбора оператора обновляется на основе результатов оценки.

Установка alns

Пакет alns зависит от numpy и matplotlib . Его можно установить обычным способом, как

 pip install alns

Кроме того, чтобы включить более продвинутые схемы выбора оператора с использованием алгоритмов многорукого бандита, можно установить alns с дополнительной зависимостью MABWiser:

 pip install alns[mabwiser]

Начиная

Документация доступна здесь. Если вы новичок в метаэвристике или ALNS, вам может быть полезно прочитать введение к странице ALNS.

Библиотека alns предоставляет алгоритм ALNS и различные критерии приемки, схемы выбора операторов и критерии остановки. Для решения вашей проблемы вам необходимо предоставить следующее:

• Состояние решения вашей проблемы, реализующее функцию objective() .
• Первоначальное решение.
• Один или несколько операторов по уничтожению и ремонту, адаптированных к вашей проблеме.

Шаблон кода «быстрого запуска» доступен здесь.

Примеры

Мы предоставляем несколько примеров блокнотов, показывающих, как можно использовать библиотеку ALNS. К ним относятся:

• Задача коммивояжера (TSP) здесь. Мы решаем пример 131 города, используя очень простую эвристику разрушения и восстановления.
• Задача маршрутизации мощных транспортных средств (CVRP) здесь. Мы решаем случай с 241 клиентом, используя комбинацию жадного оператора восстановления и оператора уничтожения , вызванного удалением подстроки .
• Проблема сокращения запасов (CSP) здесь. Мы решаем задачу со 180 балками более 165 различных размеров всего за очень ограниченное количество итераций.
• Проблема планирования проектов с ограниченными ресурсами (RCPSP) здесь. Мы решаем пример с 90 заданиями и 4 ресурсами, используя ряд различных операторов и методов улучшения из литературы.
• Задача перестановочного потока (PFSP) здесь. Решаем случай с 50 заданиями и 20 машинами. Кроме того, мы демонстрируем множество расширенных функций ALNS, включая автоматическую настройку критерия приемки и добавление локального поиска для операторов ремонта. Мы также демонстрируем, как можно настроить параметры ALNS.

Наконец, в блокноте функций представлен обзор различных опций, доступных в пакете alns . В тетради мы используем эти разные варианты для решения игрушечной задачи о рюкзаке 0/1. Блокнот является хорошей отправной точкой, когда вы хотите самостоятельно использовать различные схемы, критерии приемки или остановки. Он доступен здесь.

Содействие

Мы очень благодарны за любой вклад, который вы готовы сделать. Пожалуйста, посмотрите здесь, чтобы начать. Если вы намерены внести большие изменения, полезно сначала обсудить это изменение в новом выпуске GitHub. Смело открывайте!

Получение помощи

Не стесняйтесь открыть проблему или новую ветку обсуждения здесь, на GitHub. Пожалуйста, не пишите нам по электронной почте с вопросами, проблемами моделирования или примерами кода. Их гораздо проще обсудить через GitHub, чем по электронной почте. При написании вопроса или обсуждения следуйте инструкциям здесь.

Как цитировать alns

Если вы используете alns в своих исследованиях, пожалуйста, рассмотрите возможность цитирования следующей статьи:

Вуда, Н. А. и Л. Лан (2023). ALNS: реализация адаптивной метаэвристики поиска в больших окрестностях на языке Python. Журнал программного обеспечения с открытым исходным кодом , 8(81): 5028. https://doi.org/10.21105/joss.05028.

Или, используя следующую запись BibTeX:

 @article { Wouda_Lan_ALNS_2023 , 
  doi = { 10.21105/joss.05028 } , 
  url = { https://doi.org/10.21105/joss.05028 } , 
  year = { 2023 } , 
  publisher = { The Open Journal } , 
  volume = { 8 } , 
  number = { 81 } , 
  pages = { 5028 } , 
  author = { Niels A. Wouda and Leon Lan } , 
  title = { {ALNS}: a {P}ython implementation of the adaptive large neighbourhood search metaheuristic } , 
  journal = { Journal of Open Source Software } 
}