ALNS

alns é uma implementação geral, bem documentada e testada da metaheurística adaptativa de pesquisa de grande vizinhança (ALNS) em Python. ALNS é um algoritmo que pode ser usado para resolver problemas difíceis de otimização combinatória. O algoritmo começa com uma solução inicial. Então o algoritmo itera até que um critério de parada seja atendido. Em cada iteração, são selecionados operadores de destruição e reparo, que transformam a solução atual em uma solução candidata. Esta solução candidata é então avaliada por um critério de aceitação e o esquema de seleção do operador é atualizado com base no resultado da avaliação.

Instalando alns

O pacote alns depende de numpy e matplotlib . Pode ser instalado da maneira usual como

 pip install alns

Além disso, para permitir esquemas de seleção de operadores mais avançados usando algoritmos multi-armed bandit, alns pode ser instalado com a dependência opcional MABWiser:

 pip install alns[mabwiser]

Começando

A documentação está disponível aqui. Se você é novo em metaheurísticas ou ALNS, pode se beneficiar lendo a introdução à página ALNS.

A biblioteca alns fornece o algoritmo ALNS e vários critérios de aceitação, esquemas de seleção de operadores e critérios de parada. Para resolver seu próprio problema, você deve fornecer o seguinte:

• Um estado de solução para o seu problema que implementa uma função objective() .
• Uma solução inicial.
• Um ou mais operadores de destruição e reparo adaptados ao seu problema.

Um modelo de código de "início rápido" está disponível aqui.

Exemplos

Fornecemos vários cadernos de exemplo mostrando como a biblioteca ALNS pode ser usada. Estes incluem:

• O problema do caixeiro viajante (TSP), aqui. Resolvemos uma instância de 131 cidades usando heurísticas muito simples de destruição e reparo.
• O problema de roteamento de veículos capacitados (CVRP), aqui. Resolvemos uma instância com 241 clientes usando uma combinação de um operador de reparo ganancioso e um operador de destruição de remoção de substring induzida por folga .
• O problema do corte de estoque (CSP), aqui. Resolvemos uma instância com 180 feixes em 165 tamanhos distintos em apenas um número muito limitado de iterações.
• O problema de agendamento de projetos com restrição de recursos (RCPSP), aqui. Resolvemos uma instância com 90 jobs e 4 recursos usando diversos operadores e técnicas de aprimoramento diferentes da literatura.
• O problema do fluxo de permutação (PFSP), aqui. Resolvemos uma instância com 50 jobs e 20 máquinas. Além disso, demonstramos vários recursos avançados do ALNS, incluindo o ajuste automático do critério de aceitação e a adição de pesquisa local para operadores de reparos. Também demonstramos como é possível ajustar os parâmetros do ALNS.

Por fim, o caderno de recursos oferece uma visão geral das diversas opções disponíveis no pacote alns . No caderno usamos essas diferentes opções para resolver o problema da mochila 0/1 do brinquedo. O caderno é um bom ponto de partida para quando você deseja usar diferentes esquemas, critérios de aceitação ou de parada. Está disponível aqui.

Contribuindo

Estamos muito gratos por qualquer contribuição que você esteja disposto a fazer. Por favor, dê uma olhada aqui para começar. Se você pretende fazer uma grande mudança, é útil discutir a mudança primeiro em uma nova edição do GitHub. Sinta-se à vontade para abrir um!

Obtendo ajuda

Sinta-se à vontade para abrir um problema ou um novo tópico de discussão aqui no GitHub. Por favor, não nos envie e-mails com perguntas, problemas de modelagem ou exemplos de código. É muito mais fácil discutir isso via GitHub do que por e-mail. Ao escrever seu problema ou discussão, siga as instruções aqui.

Como citar alns

Se você usar alns em sua pesquisa, considere citar o seguinte artigo:

Wouda, NA e L. Lan (2023). ALNS: uma implementação em Python da metaheurística adaptativa de busca em grandes vizinhanças. Journal of Open Source Software , 8(81): 5028. https://doi.org/10.21105/joss.05028

Ou, usando a seguinte entrada do 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 } 
}