ALNS

alns es una implementación general, bien documentada y probada de la metaheurística de búsqueda adaptativa de grandes vecindarios (ALNS) en Python. ALNS es un algoritmo que se puede utilizar para resolver problemas difíciles de optimización combinatoria. El algoritmo comienza con una solución inicial. Luego el algoritmo itera hasta que se cumple un criterio de parada. En cada iteración, se selecciona un operador de destrucción y reparación, que transforma la solución actual en una solución candidata. Luego, esta solución candidata se evalúa mediante un criterio de aceptación y el esquema de selección de operadores se actualiza en función del resultado de la evaluación.

Instalación alns

El paquete alns depende de numpy y matplotlib . Se puede instalar de la forma habitual como

 pip install alns

Además, para permitir esquemas de selección de operadores más avanzados utilizando algoritmos de bandidos de múltiples brazos, se puede instalar alns con la dependencia MABWiser opcional:

 pip install alns[mabwiser]

Empezando

La documentación está disponible aquí. Si es nuevo en metaheurísticas o ALNS, puede resultarle útil leer la página de introducción a ALNS.

La biblioteca alns proporciona el algoritmo ALNS y varios criterios de aceptación, esquemas de selección de operadores y criterios de parada. Para resolver su propio problema, debe proporcionar lo siguiente:

• Un estado de solución para su problema que implementa una función objective() .
• Una solución inicial.
• Uno o más operadores de destrucción y reparación adaptados a su problema.

Una plantilla de código de "inicio rápido" está disponible aquí.

Ejemplos

Proporcionamos varios cuadernos de ejemplo que muestran cómo se puede utilizar la biblioteca ALNS. Estos incluyen:

• El problema del viajante (TSP), aquí. Resolvemos una instancia de 131 ciudades usando heurísticas de destrucción y reparación muy simples.
• El problema de enrutamiento de vehículos capacitados (CVRP), aquí. Resolvemos una instancia con 241 clientes utilizando una combinación de un operador de reparación codicioso y un operador de destrucción de eliminación de subcadena inducida por holgura .
• El problema del stock de corte (CSP), aquí. Resolvemos una instancia con 180 vigas en 165 tamaños distintos en solo un número muy limitado de iteraciones.
• El problema de programación de proyectos con recursos limitados (RCPSP), aquí. Resolvemos una instancia con 90 trabajos y 4 recursos utilizando varios operadores diferentes y técnicas de mejora de la literatura.
• El problema del taller de flujo de permutación (PFSP), aquí. Resolvemos una instancia con 50 trabajos y 20 máquinas. Además, demostramos múltiples funciones avanzadas de ALNS, incluido el ajuste automático del criterio de aceptación y la adición de búsqueda local para los operadores de reparación. También demostramos cómo se pueden ajustar los parámetros de ALNS.

Finalmente, el cuaderno de características ofrece una descripción general de varias opciones disponibles en el paquete alns . En el cuaderno utilizamos estas diferentes opciones para resolver un problema de mochila de juguete 0/1. El cuaderno es un buen punto de partida cuando quieras utilizar diferentes esquemas, criterios de aceptación o de parada. Está disponible aquí.

Contribuyendo

Estamos muy agradecidos por cualquier contribución que esté dispuesto a hacer. Eche un vistazo aquí para comenzar. Si su objetivo es realizar un cambio importante, es útil discutir el cambio primero en una nueva edición de GitHub. ¡Siéntete libre de abrir uno!

Obteniendo ayuda

No dudes en abrir un problema o un nuevo hilo de discusión aquí en GitHub. No nos envíe correos electrónicos con preguntas, problemas de modelado o ejemplos de código. Es mucho más fácil discutirlos a través de GitHub que por correo electrónico. Al escribir su problema o discusión, siga las instrucciones aquí.

Cómo citar alns

Si utiliza alns en su investigación, considere citar el siguiente artículo:

Wouda, NA y L. Lan (2023). ALNS: una implementación en Python de la metaheurística de búsqueda adaptativa de grandes vecindades. Revista de software de código abierto , 8(81): 5028. https://doi.org/10.21105/joss.05028

O usando la siguiente entrada 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 } 
}