adaptive large neighbourhood search
v0.2
Il s'agit d'une implémentation C ++ d'en-tête uniquement de l'algorithme de recherche Adaptif Adaptive Adaptive Neighbourhhod, conçu par Ropke et Pisinger. Le code est vaguement basé sur l'implémentation originale que Stefan Ropke a aimablement partagé avec moi.
Le cadre ALNS d'origine a été développé dans cet article:
@article { ropke_2006 ,
title = { An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows } ,
author = { Ropke, Stefan and Pisinger, David } ,
year = 2006 ,
journal = { Transportation Science } ,
volume = 40 ,
number = 4 ,
pages = { 455--472 } ,
doi = { 10.1287/trsc.1050.0135 }
}Cette mise en œuvre comprend également plusieurs critères d'acceptation, car ils ont été introduits dans le document une comparaison des critères d'acceptation pour la grande recherche de quartier adaptative Metaheuristic (préimpression). Si vous utilisez ce logiciel, veuillez citer ce dernier article comme suit:
@article { ALNS_Acceptance_Criteria ,
title = { A comparison of acceptance criteria for the {Adaptive Large Neighbourhood Search} metaheuristic } ,
author = { Santini, Alberto and Ropke, Stefan and Hvattum, Lars Magnus } ,
journal = { {Journal of Heuristics} } ,
volume = 24 ,
issue = 5 ,
pages = { 783--815 } ,
year = 2018 ,
doi = { 10.1007/s10732-018-9377-x }
}Les fonctions sont complètement documentées dans le code, en utilisant la syntaxe de doxygen. Parce qu'il s'agit d'un cadre métaheuristique, l'utilisateur doit implémenter les pièces spécifiques au problème. En termes de code, cela signifie que l'utilisateur doit fournir les composants décrits ci-dessous.
L'utilisateur doit mettre en œuvre:
getInstanceSize() qui renvoie la taille de l'instance (par exemple, le nombre de sommets dans une instance TSP).getCost() renvoyant un coût pour minimiser (par exemple, la durée d'une tournée TSP).InitialSolutionCreator pour produire une solution initiale au problème. Une fois celle-ci en place, l'utilisateur peut créer une instance de l'objet PALNS . Par exemple:
auto alns = PALNS<TSPInstance, TSPSolution>{instance}; Lorsque TSPInstance est la classe modélisant l'instance problématique et TSPSolution est la classe modélisant la solution de problème. L'utilisateur doit fournir au moins les fonctions mentionnées ci-dessus. Par exemple:
std:: uint32_t TSPInstance::getInstanceSize () const {
return this -> numberOfVertices ;
}
double TSPSolution::getCost () const {
return this -> tourLength ;
}De plus, comme la méthode ALNS commence à partir d'une solution en béton, l'utilisateur doit fournir un créateur de solution initial:
struct TSPRandomSolutionCreator : InitialSolutionCreator<TSPSolution, TSPInstance> {
TSPSolution create_initial_solution ( const TPSInstance& instance, std::mt19937& mt) {
return TSPSolution::shuffled_vertices (mt);
}
} Pour la reproductibilité, le créateur de solution initial peut utiliser un générateur de nombres pseudo-aléatoires passé par le cadre ALNS, de type std::mt19937 (à partir de l'en-tête <random> ).
Les méthodes de détruire et de réparation dériveront respectivement des classes de base DestroyMethod et RepairMethod . Une classe héritée de DestroyMethod met en œuvre deux méthodes:
void destroy_solution(Solution sol&, std::mt19937& mt) , qui prend une solution par référence (et un PRNG, si vous en avez besoin) et le détruit en place.std::unique_ptr<DestroyMethod<Solution>> clone() const , qui renvoie unique_ptr à la classe de base DestroyMethod cloner la méthode de détruire. De même, une classe héritée de RepairMethod doit mettre en œuvre:
void repair_solution(Solution& sol, std::mt19937& mt) , qui prend une solution (détruite) par référence (et un PRNG, si vous en avez besoin) et la répare en place.std::unique_ptr<RepairMethod<Solution>> clone() const , qui renvoie unique_ptr à la classe de base RepairMethod Clonage de la méthode de réparation.Par exemple:
struct RandomDestroy : public DestroyMethod <TSPSolution> {
void destroy_solution (TSPSolution& solution, std::mt19937& mt) {
std::bernoulli_distribution d ( 0.1 );
for ( const auto & v : solution. visited_vertices ()) {
if ( d (mt)) {
solution. queue_vertex_removal (v);
}
}
solution. remove_queued_vertices ();
}
std::unique_ptr<DestroyMethod<TSPSolution>> clone () const {
return std::make_unique<DestroyMethod<TSPSolution>>();
}
};
struct GreedyRepair : public RepairMethod <TSPSoution> {
void repair_solution (Solution& sol, std::mt19937& mt) {
for ( const auto & v : solution. missing_vertices ()) {
solution. insert_vertex_in_best_position (v);
}
}
std::unique_ptr<RepairMethod<TSPSolution>> clone () const {
return std::make_unique<RepairMethod<TSPSolution>>();
}
}; L'utilisateur peut choisir entre l'utilisation des critères d'acceptation prédéfinis ou la mise en œuvre de son propre héritage de la classe de base AcceptanceCriterion . Une façon pratique de surveiller l'algorithme et d'effectuer des actions non standard pendant le processus de solution consiste à fournir un objet visiteur qui hérite de AlgorithmVisitor . Le visiteur de l'algorithme doit implémenter les rappels suivants:
on_algorithm_start qui est appelé avant la première itération ALNS.on_prerun_end qui est appelé lorsque le pré-run est terminé (voir les paramètres de la section ci-dessous).on_iteration_end qui est appelé à la fin de chaque itération.on_many_iters_without_improvement qui est appelé après un nombre défini par l'utilisateur d'itérations consécutives sans améliorer la meilleure solution (voir les paramètres de section ci-dessous). Tous les paramètres du framework métaheuristique sont définis par Params.json de fichier d'édition. Ils sont décrits ci-dessous:
prerun-iterations : Le nombre d'itérations initiales que l'algorithme peut utiliser pour tenter de réprimer automatiquement les paramètres d'acceptation. Ce n'est pas obligatoire et peut être réglé sur zéro.total-iterations : une limite difficile sur le nombre d'itérations.timeout-s : une limite dure au temps du CPU de l'algorithme.iters-without-improvement-max : une limite dure au nombre d'itérations consécutives sans amélioration de la meilleure solution. Il met fin à la course tôt lorsqu'il est coincé dans une situation de paysage plat .iters-without-improvement-alarm : si défini, et si l'utilisateur fournit un visiteur d'algorithme, après ces nombreuses itérations consécutives, nous appellerons la méthode on_many_iters_without_improvement . L'utilisateur peut utiliser ce mécanisme pour essayer d'échapper à l'optima local. Par exemple, il peut appliquer une méthode de détruire plus forte ou une heuristique de diversification.iterations-without-syncing-threads : Dans la version parallèle de l'algorithme, il s'agit du nombre d'itérations pendant lesquelles les threads ne synchronisent pas les informations et ne se comportent pas comme des copies indépendantes de l'algorithme ALNS. Lors de la synchronisation des threads, les poids d'acceptation / détruire et la solution actuelle sont partagés.prob-return-to-best-known : à chaque itération, la solution la plus connue remplacera la solution actuelle par cette probabilité. Zero est un bon défaut, mais l'utilisateur peut définir une valeur plus élevée pour favoriser l'intensification par rapport à la diversification.acceptance-criterion : L'un des critères d'acceptation prédéfinis. Les valeurs possibles sont répertoriées dans les acceptance-criterion-possible-values .acceptance-params-base : Certains des paramètres d'acceptation varient au cours de l'algorithme RUN. Ce paramètre, qui peut prendre time valeurs et iterations spécifie si la limite de temps ( timeout-s ) ou la limite d'itérations ( total-iterations ) doit être considérée comme estimé lorsque la course sera terminée.scores : Ce sont les multiplicateurs utilisés pour mettre à jour les scores de détruire / réparation à chaque itération. Les utilisateurs doivent fournir quatre multiplicateurs:global-best si la nouvelle solution est meilleure que la meilleure solution précédente, sinonimproved si la nouvelle solution est meilleure que la solution actuelle, sinonaccepted si la nouvelle solution a été acceptée par le critère d'acceptation.decay , détermine à quelle vitesse les trois valeurs ci-dessus affectent les scores des méthodes. Un défaut sain d'esprit est juste un peu moins de 1,0, pour garantir que les scores changent en douceur.parameter-tuning-file : Si vous effectuez un réglage des paramètres, c'est le nom de fichier où les résultats seront enregistrés.results-log-basename : Nom de Basen pour les fichiers de résultats. Dans ce qui suit, nous énumérons les paramètres relatifs aux critères d'acceptation. Nous exhortons les utilisateurs à se référer au document des critères d'acceptation pour mieux comprendre le rôle de chaque paramètre et la terminologie utilisée ci-dessous. Le document présente également les paramètres les mieux réglés sur une grande variété de problèmes résolus.
init-ratio-50p : Solutions bien pires que celles actuelles sont acceptées avec une probabilité de 50% au début de la course.end-ratio-50p : solutions bien pires que celles actuelles sont acceptées avec une probabilité de 50% à la fin de la course.end-ratio-50p-refers-to-initial : Si défini sur true , dans la description du end-ratio-50p remplacez "Current One" par "Initial One". En d'autres termes, évaluez toujours la qualité des nouvelles solutions par rapport à la solution initiale et non à la solution actuelle.temperature-decrease-is-linear : si elle est true , la diminution du début à la température finale est linéaire, sinon elle est exponentielle. Une diminution exponentielle est la norme dans la littérature de recuit simulé, mais une diminution linéaire est recommandée dans notre article.reheating : s'il faut réintégrer la température à certains intervalles.reheating-coefficient : par combien augmenter la température, si reheating est true .reheating-times : Combien de fois augmenter la température pendant la course.magic-number-exponent : Le soi-disant "numéro magique" de la mise en œuvre originale de Ropke et Pissinger (voir référence ci-dessus).start-threshold : Seuil au début de la course.end-threshold : SEURSHOLD À LA FIN DE LA RUNE.threshold-decrease-is-linear : si le seuil diminue linéairement ( true ) ou exponentiellement ( false ) entre les valeurs de début et de fin.initial-water-level-ratio : multiplicateur au coût de la solution initiale, pour obtenir le niveau d'eau initial.water-level-decrease-pct : diminution du pourcentage du niveau d'eau, à chaque itération.start-deviation : déviation maximale autorisée au début de la course.end-deviation : écart final maximal à la fin de la course.deviation-decrease-is-linear : si l'écart diminue linéairement ( true ) ou exponentiellement ( false ) entre les valeurs de début et de fin.list-size : taille de la liste des acceptances tardives.allow-non-worsening : s'il faut toujours accepter une nouvelle solution non montée en puissance.initial-water-level-ratio : multiplicateur au coût de la solution initiale, pour obtenir le niveau d'eau initial. gap-to-increase-water-level : Écart de seuil pour réintégrer le niveau de l'eau. water-level-increase-pct : pourcentage de la différence de solution, par laquelle le niveau d'eau augmente pendant les phases d'augmentation. water-level-decrease-exp-factor : facteur exponentiel (delta dans notre article) à utiliser lors de la diminution du niveau de l'eau.start-probability : probabilité d'acceptation au début de la course.end-probability : probabilité d'acceptation à la fin de la course.probability-decrease-is-linear : si la probabilité diminue linéairement ( true ) ou exponentiellement ( false ) entre les valeurs de début et de fin. Ce logiciel est concédé sous licence GNU Public License version 3. Voir LICENSE de fichier pour plus d'informations.
