adaptive large neighbourhood search
v0.2
Esta é uma implementação de C ++ somente para cabeçalho do algoritmo de busca de vizinhos (paralelos) Adaptive Grandehhod, criado por Ropke e Pinger. O código é vagamente baseado na implementação original que Stefan Ropke compartilhou comigo.
A estrutura original do ALNS foi desenvolvida neste artigo:
@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 }
}Essa implementação também inclui vários critérios de aceitação, pois foram introduzidos no artigo uma comparação de critérios de aceitação para a grande busca de vizinhança adaptativa metaheurística (pré -impressão). Se você usar este software, cite este último papel da seguinte forma:
@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 }
}As funções são minuciosamente documentadas no código, usando sintaxe doxygen. Como essa é uma estrutura metaheurística, o usuário deve implementar as partes específicas do problema. Em termos de código, isso significa que o usuário precisa fornecer os componentes descritos abaixo.
O usuário deve implementar:
getInstanceSize() que retorna o tamanho da instância (por exemplo, o número de vértices em uma instância de TSP).getCost() retornando um custo para minimizar (por exemplo, a duração de um tour de TSP).InitialSolutionCreator para produzir uma solução inicial para o problema. Uma vez que isso esteja no local, o usuário pode criar uma instância do objeto PALNS . Por exemplo:
auto alns = PALNS<TSPInstance, TSPSolution>{instance}; Onde TSPInstance é a classe modelando a instância do problema e TSPSolution é a classe modelando a solução do problema. O usuário deve fornecer pelo menos as funções mencionadas acima. Por exemplo:
std:: uint32_t TSPInstance::getInstanceSize () const {
return this -> numberOfVertices ;
}
double TSPSolution::getCost () const {
return this -> tourLength ;
}Além disso, como o método ALNS começa a partir de uma solução concreta, o usuário deve fornecer um criador de solução inicial:
struct TSPRandomSolutionCreator : InitialSolutionCreator<TSPSolution, TSPInstance> {
TSPSolution create_initial_solution ( const TPSInstance& instance, std::mt19937& mt) {
return TSPSolution::shuffled_vertices (mt);
}
} Para reprodutibilidade, o criador da solução inicial pode usar um gerador de números pseudo-aleatórios aprovado pela estrutura ALNS, do tipo std::mt19937 (do cabeçalho <random> ).
Os métodos de destruição e reparo derivarão, respectivamente, das classes base DestroyMethod e RepairMethod . Uma classe herdadora do DestroyMethod deve implementar dois métodos:
void destroy_solution(Solution sol&, std::mt19937& mt) , que leva uma solução por referência (e um prng, se você precisar) e a destrói no local.std::unique_ptr<DestroyMethod<Solution>> clone() const , que retorna um unique_ptr à classe base DestroyMethod clonando o método de destruição. Da mesma forma, uma classe herdadora do RepairMethod deve implementar:
void repair_solution(Solution& sol, std::mt19937& mt) , que leva uma solução (destruída) por referência (e um prng, se precisar) e o repara no local.std::unique_ptr<RepairMethod<Solution>> clone() const , que retorna um unique_ptr para o RepairMethod da classe base que clona o método de reparo.Por exemplo:
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>>();
}
}; O usuário pode escolher entre usar um dos critérios de aceitação predefinidos ou a implementação de sua própria herdeira da classe Base AcceptanceCriterion . Uma maneira útil de monitorar o algoritmo e executar ações não padronizadas durante o processo de solução é fornecer um objeto de visitante que herda do AlgorithmVisitor . O visitante do algoritmo deve implementar os seguintes retornos de chamada:
on_algorithm_start , que é chamado antes da primeira iteração ALS.on_prerun_end , que é chamado quando a pré-corrida é concluída (consulte os parâmetros da seção abaixo).on_iteration_end , que é chamado no final de cada iteração.on_many_iters_without_improvement , que é chamado após um número definido pelo usuário de iterações consecutivas sem melhorar a melhor solução (consulte os parâmetros da seção abaixo). Todos os parâmetros da estrutura metaheurística são definidos por Params.json . Eles são descritos abaixo:
prerun-iterations : o número de iterações iniciais que o algoritmo pode usar para tentar auto-ajustar os parâmetros de aceitação automaticamente. Isso não é obrigatório e pode ser definido como zero.total-iterations : Um limite rígido para o número de iterações.timeout-s : Um limite rígido no tempo da CPU do algoritmo.iters-without-improvement-max : Um limite rígido para o número de iterações consecutivas sem melhorias na melhor solução. Ele termina a corrida mais cedo quando preso em uma situação de paisagem plana .iters-without-improvement-alarm : Se definido, e se o usuário fornecer um visitante de algoritmo, após essas iterações consecutivas, chamaremos o método de on_many_iters_without_improvement do visitante. O usuário pode usar esse mecanismo para tentar escapar do ótimo local. Por exemplo, pode aplicar um método de destruição mais forte ou uma heurística de diversificação.iterations-without-syncing-threads : na versão paralela do algoritmo, esse é o número de iterações durante as quais os threads não sincronizam as informações e se comportam como cópias independentes do algoritmo ALNS. Após a sincronização do thread, os pesos de aceitação/destruição e a solução atual são compartilhados.prob-return-to-best-known : a cada iteração, a solução mais conhecida substituirá a solução atual por essa probabilidade. Zero é um bom padrão, mas o usuário pode definir um valor mais alto para favorecer a intensificação em relação à diversificação.acceptance-criterion : um dos critérios de aceitação predefinidos. Os valores possíveis estão listados nos valores (não utilizados) de chave acceptance-criterion-possible-values .acceptance-params-base : Alguns dos parâmetros de aceitação variam durante o curso da execução do algoritmo. Esse parâmetro, que pode levar time dos valores e iterations especificam se o limite de tempo ( timeout-s ) ou o limite de iterações ( total-iterations ) deve ser considerado estimar quando a execução terminará.scores : esses são os multiplicadores usados para atualizar as pontuações de destruição/reparo em cada iteração. Os usuários devem fornecer quatro multiplicadores:global-best se a nova solução for melhor que a melhor solução anterior, caso contrárioimproved se a nova solução for melhor que a solução atual, caso contrárioaccepted se a nova solução foi aceita pelo critério de aceitação.decay , determina a rapidez com que os três valores acima afetam as pontuações dos métodos. Um padrão são um pouco menos de 1,0, para garantir que as pontuações mudem sem problemas.parameter-tuning-file : Se executar o ajuste dos parâmetros, este é o nome do arquivo em que os resultados serão salvos.results-log-basename : Nome da base para os arquivos de resultado. A seguir, listamos parâmetros em relação aos critérios de aceitação. Instamos os usuários a se referirem ao papel dos critérios de aceitação para entender melhor o papel de cada parâmetro e a terminologia usada abaixo. O artigo também apresenta os melhores parâmetros ajustados em uma ampla variedade de problemas resolvidos.
init-ratio-50p : soluções muito piores que as atuais são aceitas com 50% de probabilidade no início da execução.end-ratio-50p : Soluções muito piores que as atuais são aceitas com 50% de probabilidade no final da execução.end-ratio-50p-refers-to-initial : Se definido como true , na descrição do end-ratio-50p substitua "Current One" pelo "inicial inicial". Em outras palavras, sempre avalie a qualidade de novas soluções em comparação com a solução inicial e não com a solução atual.temperature-decrease-is-linear : se for true , a diminuição do início para a temperatura final é linear, caso contrário, é exponencial. Uma diminuição exponencial é o padrão na literatura simulada de recozimento, mas uma diminuição linear é recomendada em nosso artigo.reheating : se deve reiniciar a temperatura em determinados intervalos.reheating-coefficient : por quanto aumentar a temperatura, se reheating for true .reheating-times : quantas vezes aumentar a temperatura durante a corrida.magic-number-exponent : o chamado "Número Mágico" da implementação original de Ropke e Pissinger (veja a referência acima).start-threshold : limiar no início da corrida.end-threshold : limiar no final da corrida.threshold-decrease-is-linear : se o limiar diminui linearmente ( true ) ou exponencialmente ( false ) entre os valores de partida e final.initial-water-level-ratio : Multiplicador para o custo da solução inicial, para obter o nível inicial da água.water-level-decrease-pct : diminuição percentual do nível da água, a cada iteração.start-deviation : Desvio máximo permitido no início da corrida.end-deviation : desvio final máximo no final da corrida.deviation-decrease-is-linear : se o desvio diminui linearmente ( true ) ou exponencialmente ( false ) entre os valores de partida e final.list-size : tamanho da lista de aceitação tardia.allow-non-worsening : se deve sempre aceitar uma nova solução não esgotada.initial-water-level-ratio : Multiplicador para o custo da solução inicial, para obter o nível inicial da água. gap-to-increase-water-level : Limite de limiar para reiniciar o nível da água. water-level-increase-pct : porcentagem da diferença da solução, pela qual o nível da água aumenta durante o aumento das fases. water-level-decrease-exp-factor : fator exponencial (delta em nosso papel) para usar ao diminuir o nível da água.start-probability : Probabilidade de aceitação no início da execução.end-probability : probabilidade de aceitação no final da corrida.probability-decrease-is-linear : se a probabilidade diminui linearmente ( true ) ou exponencialmente ( false ) entre os valores de partida e final. Este software está licenciado sob a versão 3 da GNU License 3. Consulte LICENSE de arquivo para obter mais informações.
