ALNS

alns est une implémentation générale, bien documentée et testée de la métaheuristique de recherche adaptative à grand voisinage (ALNS) en Python. ALNS est un algorithme qui peut être utilisé pour résoudre des problèmes d’optimisation combinatoire difficiles. L'algorithme commence par une solution initiale. Ensuite, l'algorithme itère jusqu'à ce qu'un critère d'arrêt soit satisfait. A chaque itération, un opérateur de destruction et de réparation est sélectionné, qui transforme la solution actuelle en solution candidate. Cette solution candidate est ensuite évaluée par un critère d'acceptation, et le schéma de sélection d'opérateur est mis à jour sur la base du résultat de l'évaluation.

Installation alns

Le package alns dépend de numpy et matplotlib . Il peut être installé de la manière habituelle comme

 pip install alns

De plus, pour permettre des schémas de sélection d'opérateurs plus avancés utilisant des algorithmes de bandit multi-armés, alns peut être installé avec la dépendance facultative MABWiser :

 pip install alns[mabwiser]

Commencer

La documentation est disponible ici. Si vous êtes nouveau dans les métaheuristiques ou l'ALNS, vous pourriez bénéficier de la lecture de la page d'introduction à l'ALNS.

La bibliothèque alns fournit l'algorithme ALNS et divers critères d'acceptation, schémas de sélection des opérateurs et critères d'arrêt. Pour résoudre votre propre problème, vous devez fournir les éléments suivants :

• Un état de solution pour votre problème qui implémente une fonction objective() .
• Une première solution.
• Un ou plusieurs opérateurs de destruction et de réparation adaptés à votre problématique.

Un modèle de code « quickstart » est disponible ici.

Exemples

Nous fournissons plusieurs exemples de cahiers montrant comment la bibliothèque ALNS peut être utilisée. Ceux-ci incluent :

• Le problème du voyageur de commerce (TSP), ici. Nous résolvons une instance de 131 villes en utilisant des heuristiques très simples de destruction et de réparation.
• Le problème de tournées de véhicules capacitaires (CVRP), ici. Nous résolvons une instance avec 241 clients en utilisant une combinaison d'un opérateur de réparation gourmand et d'un opérateur de destruction de sous-chaîne induit par le jeu .
• Le problème du stock de coupe (CSP), ici. Nous résolvons une instance comportant 180 poutres de 165 tailles distinctes en un nombre très limité d'itérations.
• Le problème de planification de projet avec ressources limitées (RCPSP), ici. Nous résolvons une instance avec 90 tâches et 4 ressources en utilisant un certain nombre d'opérateurs différents et de techniques d'amélioration issues de la littérature.
• Le problème du flux de permutation (PFSP), ici. Nous résolvons une instance avec 50 tâches et 20 machines. De plus, nous démontrons plusieurs fonctionnalités avancées d'ALNS, notamment l'ajustement automatique du critère d'acceptation et l'ajout d'une recherche locale pour les opérateurs de réparation. Nous montrons également comment régler les paramètres ALNS.

Enfin, le carnet de fonctionnalités donne un aperçu des différentes options disponibles dans le package alns . Dans le cahier, nous utilisons ces différentes options pour résoudre un problème de sac à dos jouet 0/1. Le cahier est un bon point de départ lorsque vous souhaitez utiliser vous-même différents schémas, critères d'acceptation ou d'arrêt. Il est disponible ici.

Contribuer

Nous sommes très reconnaissants pour toute contribution que vous êtes prêt à apporter. Veuillez jeter un oeil ici pour commencer. Si vous envisagez d'apporter un changement important, il est utile d'en discuter d'abord dans un nouveau numéro GitHub. N'hésitez pas à en ouvrir un !

Obtenir de l'aide

N'hésitez pas à ouvrir un problème ou un nouveau fil de discussion ici sur GitHub. Veuillez ne pas nous envoyer de questions, de problèmes de modélisation ou d'exemples de code par e-mail. Il est beaucoup plus facile d’en discuter via GitHub que par e-mail. Lorsque vous rédigez votre problème ou votre discussion, veuillez suivre les instructions ici.

Comment citer l' alns

Si vous utilisez alns dans vos recherches, pensez à citer l'article suivant :

Wouda, NA et L. Lan (2023). ALNS : une implémentation Python de la métaheuristique de recherche adaptative dans un grand quartier. Journal des logiciels open source , 8(81) : 5028. https://doi.org/10.21105/joss.05028

Ou, en utilisant l'entrée BibTeX suivante :

 @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 } 
}