adaptive large neighbourhood search
v0.2
Esta es una implementación de C ++ solo de encabezado del algoritmo de búsqueda de vecinos grandes (paralelos) grandes, ideado por Ropke y Pisinger. El código se basa libremente en la implementación original que Stefan Ropke ha compartido amablemente conmigo.
El marco ALNS original se desarrolló en este documento:
@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 }
}Esta implementación también incluye criterios de aceptación múltiple, ya que se introdujeron en el documento una comparación de los criterios de aceptación para el Metaheurística de búsqueda de vecindario grande adaptativo (preimpresión). Si usa este software, cite este último artículo de la siguiente manera:
@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 }
}Las funciones se documentan completamente en el código, utilizando la sintaxis de Doxygen. Debido a que este es un marco metaheurista, el usuario debe implementar las partes específicas del problema. En términos de código, esto significa que el usuario necesita proporcionar los componentes descritos a continuación.
El usuario debe implementar:
getInstanceSize() que devuelve el tamaño de la instancia (por ejemplo, el número de vértices en una instancia de TSP).getCost() que devuelve un costo para minimizar (por ejemplo, la duración de un recorrido por TSP).InitialSolutionCreator para producir una solución inicial al problema. Una vez que esto está en el lugar, el usuario puede crear una instancia del objeto PALNS . Por ejemplo:
auto alns = PALNS<TSPInstance, TSPSolution>{instance}; Donde TSPInstance es la clase que modela la instancia del problema y TSPSolution es el modelador de clases de la solución del problema. El usuario debe suministrar al menos las funciones mencionadas anteriormente. Por ejemplo:
std:: uint32_t TSPInstance::getInstanceSize () const {
return this -> numberOfVertices ;
}
double TSPSolution::getCost () const {
return this -> tourLength ;
}Además, debido a que el método ALNS comienza desde una solución concreta, el usuario debe suministrar un creador de solución inicial:
struct TSPRandomSolutionCreator : InitialSolutionCreator<TSPSolution, TSPInstance> {
TSPSolution create_initial_solution ( const TPSInstance& instance, std::mt19937& mt) {
return TSPSolution::shuffled_vertices (mt);
}
} Para la reproducibilidad, el creador de soluciones inicial puede usar un generador de números pseudo-aleatorios que pasa por el marco ALNS, de Tipo std::mt19937 (desde el encabezado <random> ).
Los métodos de destrucción y reparación se derivarán, respectivamente, de las clases base DestroyMethod y RepairMethod . Una clase que hereda de DestroyMethod implementará dos métodos:
void destroy_solution(Solution sol&, std::mt19937& mt) , que toma una solución por referencia (y un prng, si lo necesita) y la destruye en el lugar.std::unique_ptr<DestroyMethod<Solution>> clone() const , que devuelve un unique_ptr a la clase base DestroyMethod clonando el método Destroy. Del mismo modo, una clase heredadora de RepairMethod implementará:
void repair_solution(Solution& sol, std::mt19937& mt) , que toma una solución (destruida) por referencia (y un PRNG, si lo necesita) y la repara en el lugar.std::unique_ptr<RepairMethod<Solution>> clone() const , que devuelve un unique_ptr a la clase base RepairMethod clonando el método de reparación.Por ejemplo:
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>>();
}
}; El usuario puede elegir entre usar uno los criterios de aceptación predefinidos o implementar su propio heredero de la clase base AcceptanceCriterion . Una forma útil de monitorear el algoritmo y realizar acciones no estándar durante el proceso de solución es proporcionar un objeto de visitante que hereda del AlgorithmVisitor . El visitante del algoritmo debe implementar las siguientes devoluciones de llamada:
on_algorithm_start , que se llama antes de la primera iteración ALNS.on_prerun_end , que se llama cuando se termina el prejuicio (consulte los parámetros de la sección a continuación).on_iteration_end que se llama al final de cada iteración.on_many_iters_without_improvement , que se llama después de un número de iteraciones consecutivas definidas por el usuario sin mejorar la mejor solución (consulte los parámetros de la sección a continuación). Todos los parámetros del marco metaheurístico se establecen el archivo de edición Params.json . Se describen a continuación:
prerun-iterations : el número de iteraciones iniciales que el algoritmo puede usar para intentar autoengar los parámetros de aceptación. Esto no es obligatorio y se puede establecer en cero.total-iterations : un límite difícil en el número de iteraciones.timeout-s : un límite difícil en el tiempo de la CPU del algoritmo.iters-without-improvement-max : un límite difícil en el número de iteraciones consecutivas sin mejorar la mejor solución. Termina la carrera temprano cuando está atrapado en una situación de paisaje plano .iters-without-improvement-alarm : si se establece, y si el usuario proporciona un visitante de algoritmo, después de esto muchas iteraciones consecutivas llamaremos el método de visitante on_many_iters_without_improvement . El usuario puede usar este mecanismo para intentar escapar de Optima Local. Por ejemplo, puede aplicar un método de destrucción más fuerte o una heurística de diversificación.iterations-without-syncing-threads : en la versión paralela del algoritmo, este es el número de iteraciones durante las cuales los hilos no sincronizan información y se comportan como copias independientes del algoritmo ALNS. Tras la sincronización de subprocesos, se comparten los pesos de aceptación/destrucción y la solución actual.prob-return-to-best-known : en cada iteración, la solución más conocida reemplazará la solución actual con esta probabilidad. Zero es un buen valor predeterminado, pero el usuario puede establecer un valor más alto para favorecer la intensificación sobre la diversificación.acceptance-criterion : uno de los criterios de aceptación predefinidos. Los valores posibles se enumeran en los acceptance-criterion-possible-values .acceptance-params-base : algunos de los parámetros de aceptación varían durante el curso de la ejecución del algoritmo. Este parámetro, que puede tomar time de los valores y iterations especifican si el límite de tiempo ( timeout-s ) o el límite de iteraciones ( total-iterations ) deben considerarse estimar cuándo terminará la ejecución.scores : estos son los multiplicadores utilizados para actualizar los puntajes de destrucción/reparación en cada iteración. Los usuarios deben proporcionar cuatro multiplicadores:global-best si la nueva solución es mejor que la mejor solución anterior, de lo contrarioimproved si la nueva solución es mejor que la solución actual, de lo contrarioaccepted si la nueva solución fue aceptada por el criterio de aceptación.decay , determina qué tan rápido los tres valores anteriores afectan los puntajes de los métodos. Un valor predeterminado sano es solo un poco menos de 1.0, para garantizar que los puntajes cambien sin problemas.parameter-tuning-file : si realiza la sintonización de parámetros, este es el nombre de archivo donde se guardarán los resultados.results-log-basename : Basename para los archivos de resultados. A continuación, enumeramos los parámetros en relación con los criterios de aceptación. Instamos a los usuarios a que se refieran al documento de criterios de aceptación para comprender mejor el papel de cada parámetro y la terminología que se utiliza a continuación. El documento también presenta los mejores parámetros sintonizados en una amplia variedad de problemas resueltos.
init-ratio-50p : las soluciones tan peores que las actuales se aceptan con una probabilidad del 50% al comienzo de la ejecución.end-ratio-50p : las soluciones tan peores que la actual se aceptan con una probabilidad del 50% al final de la ejecución.end-ratio-50p-refers-to-initial : si se establece en true , en la descripción de end-ratio-50p reemplaza "actual uno" con "uno inicial". En otras palabras, siempre evalúe la calidad de las nuevas soluciones en comparación con la solución inicial y no con la solución actual.temperature-decrease-is-linear : si es true , la disminución desde la temperatura del inicio hasta el final es lineal, de lo contrario es exponencial. Una disminución exponencial es el estándar en la literatura de recocido simulado, pero se recomienda una disminución lineal en nuestro trabajo.reheating : si volver a aumentar la temperatura a ciertos intervalos.reheating-coefficient : por cuánto aumentar la temperatura, si reheating es true .reheating-times : cuántas veces aumentar la temperatura durante la ejecución.magic-number-exponent : el llamado "número mágico" de la implementación original de Ropke y Pissinger (ver referencia anterior).start-threshold : umbral al comienzo de la ejecución.end-threshold : umbral al final de la carrera.threshold-decrease-is-linear : si el umbral disminuye linealmente ( true ) o exponencialmente ( false ) entre los valores de inicio y finalización.initial-water-level-ratio : multiplicador al costo de la solución inicial, para obtener el nivel de agua inicial.water-level-decrease-pct : disminución porcentual del nivel del agua, en cada iteración.start-deviation : la desviación máxima permitida al comienzo de la ejecución.end-deviation : desviación final máxima al final de la ejecución.deviation-decrease-is-linear : si la desviación disminuye linealmente ( true ) o exponencialmente ( false ) entre los valores de inicio y finalización.list-size : tamaño de la lista de aceptación tardía.allow-non-worsening : si siempre aceptar una nueva solución que no es de inicio.initial-water-level-ratio : multiplicador al costo de la solución inicial, para obtener el nivel de agua inicial. gap-to-increase-water-level : brecha umbral para volver a aumentar el nivel del agua. water-level-increase-pct : porcentaje de la diferencia de solución, por el cual el nivel de agua aumenta durante las fases de aumento. water-level-decrease-exp-factor : factor exponencial (delta en nuestro papel) para usar al disminuir el nivel de agua.start-probability : probabilidad de aceptación al comienzo de la ejecución.end-probability : probabilidad de aceptación al final de la ejecución.probability-decrease-is-linear : si la probabilidad disminuye linealmente ( true ) o exponencialmente ( false ) entre los valores de inicio y finalización. Este software tiene licencia bajo la Licencia Pública de GNU Versión 3. Consulte LICENSE de archivo para obtener más información.
