adaptive large neighbourhood search
v0.2
Это только заголовок реализация C ++ (параллельного) адаптивного алгоритма поиска с большим соседством, разработанным Ropke и Pisinger. Код основан на оригинальной реализации, которую Стефан Ропке любезно поделился со мной.
Оригинальная структура ALNS была разработана в этой статье:
@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 }
}Эта реализация также включает в себя множество критериев принятия, так как они были введены в статье сравнения критериев принятия для адаптивного крупного поиска по соседству с метахевристом (препринт). Если вы используете это программное обеспечение, пожалуйста, укажите эту последнюю статью следующим образом:
@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 }
}Функции тщательно задокументированы в коде, используя синтаксис доксигена. Поскольку это метахевристическая структура, пользователь должен реализовать детали для конкретной проблемы. С точки зрения кода, это означает, что пользователю необходимо предоставить компоненты, описанные ниже.
Пользователь должен реализовать:
getInstanceSize() , который возвращает размер экземпляра (например, количество вершин в экземпляре TSP).getCost() возвращающим затрат на минимизацию (например, продолжительность тура TSP).InitialSolutionCreator для получения начального решения проблемы. Как только это на месте, пользователь может создать экземпляр объекта PALNS . Например:
auto alns = PALNS<TSPInstance, TSPSolution>{instance}; В тех случаях, когда TSPInstance - это моделирование класса. Проблемный экземпляр, а TSPSolution - это класс моделирование решения проблемы. Пользователь должен предоставить хотя бы функции, упомянутые выше. Например:
std:: uint32_t TSPInstance::getInstanceSize () const {
return this -> numberOfVertices ;
}
double TSPSolution::getCost () const {
return this -> tourLength ;
}Более того, поскольку метод ALNS начинается с конкретного решения, пользователь должен предоставить начальный создатель решения:
struct TSPRandomSolutionCreator : InitialSolutionCreator<TSPSolution, TSPInstance> {
TSPSolution create_initial_solution ( const TPSInstance& instance, std::mt19937& mt) {
return TSPSolution::shuffled_vertices (mt);
}
} Для воспроизводимости начальный создатель решения может использовать генератор псевдо-рэндома, переданный в рамках ALNS, типа std::mt19937 (из заголовка <random> ).
Методы уничтожения и ремонта будут происходить, соответственно, из базовых классов DestroyMethod и RepairMethod . Класс, унаследовавший от DestroyMethod должен реализовать два метода:
void destroy_solution(Solution sol&, std::mt19937& mt) , которое принимает решение по ссылке (и PRNG, если вам это нужно) и уничтожает его на месте.std::unique_ptr<DestroyMethod<Solution>> clone() const , который возвращает unique_ptr в базовый класс DestroyMethod клонирующий метод уничтожения. Точно так же класс, наследующий от RepairMethod должен реализовать:
void repair_solution(Solution& sol, std::mt19937& mt) , который принимает (разрушенное) решение по ссылке (и PRNG, если вам это нужно) и ремонтирует его на месте.std::unique_ptr<RepairMethod<Solution>> clone() const , который возвращает unique_ptr в базовый класс RepairMethod клонирующий метод ремонта.Например:
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>>();
}
}; Пользователь может выбрать между использованием одного предварительно определенных критериев принятия или реализации своего собственного наследства от базового класса AcceptanceCriterion . Приятного способа мониторинга алгоритма и выполнения нестандартных действий во время процесса решения-это предоставление объекта для посетителя, который наследует от AlgorithmVisitor . Посетитель алгоритма должен реализовать следующие обратные вызовы:
on_algorithm_start , который называется перед первой итерацией ALNS.on_prerun_end , который вызывается, когда предварительный заряд закончен (см. Параметры раздела ниже).on_iteration_end , который называется в конце каждой итерации.on_many_iters_without_improvement , который называется после определенного пользователя числа последовательных итераций без улучшения наилучшего решения (см. Параметры раздела ниже). Все параметры метахевристической структуры установлены файл редактирования Params.json . Они описаны ниже:
prerun-iterations : Количество начальных итераций, которые алгоритм может использовать для попытки автоматической настройки параметров принятия. Это не обязательно и может быть установлено на ноль.total-iterations : жесткий ограничение на количество итераций.timeout-s : жесткий ограничение на время процессора алгоритма.iters-without-improvement-max : жесткий ограничение на количество последовательных итераций без улучшения к лучшему решению. Это заканчивает бег рано, когда застрял в плоской ландшафтной ситуации.iters-without-improvement-alarm : если установлено, и если пользователь предоставляет посетителя алгоритма, после этого многих последовательных итераций мы позвоним в метод посетителя on_many_iters_without_improvement . Пользователь может использовать этот механизм, чтобы попытаться избежать локальных оптимистов. Например, он может применять более сильный метод уничтожения или эвристику диверсификации.iterations-without-syncing-threads в параллельной версии алгоритма это количество итераций, в ходе которых потоки не синхронизируют информацию и ведут себя как независимые копии алгоритма ALNS. После синхронизации потока используются веса принять/уничтожить и текущее решение.prob-return-to-best-known : на каждой итерации наиболее известное решение заменит текущее решение на эту вероятность. Ноль является хорошим дефолтом, но пользователь может установить более высокое значение, чтобы поддержать интенсификацию над диверсификацией.acceptance-criterion : один из предопределенных критериев принятия. Возможные значения перечислены в (неиспользованном) клавишах параметра acceptance-criterion-possible-values .acceptance-params-base : некоторые из параметров принятия варьируются в ходе запуска алгоритма. Этот параметр, который может принимать значения time и iterations указывает, следует ли рассматриваться как ограничение по времени ( timeout-s ) или ограничение итераций ( total-iterations ), чтобы оценить, когда прогон будет закончен.scores : Это множители, используемые для обновления результатов уничтожения/ремонта на каждой итерации. Пользователи должны предоставить четыре множителя:global-best , если новое решение лучше, чем предыдущее лучшее решение, в противном случаеimproved если новое решение лучше текущего решения, в противном случаеaccepted , если новое решение было принято по критерию принятия.decay , определяет, насколько быстро вышеупомянутые три значения влияют на оценки методов. Сумма дефолта составляет чуть менее 1,0, чтобы убедиться, что результаты изменяются плавно.parameter-tuning-file : при выполнении настройки параметров это имя файла, где будут сохранены результаты.results-log-basename : базовое имя для файлов результатов. В следующем мы перечисляем параметры относительно критериев принятия. Мы призываем пользователей обратиться к документу критериев принятия, чтобы лучше понять роль каждого параметра и терминологию, используемой ниже. В статье также представлены лучшие настроенные параметры в самых разных решениях.
init-ratio-50p : решения, гораздо хуже, чем текущие, принимаются с вероятностью 50% в начале прогона.end-ratio-50p : решения, гораздо хуже, чем текущие, принимаются с вероятностью 50% в конце прогона.end-ratio-50p-refers-to-initial : если установить на true , в описании end-ratio-50p замените «Current One» с «начальным». Другими словами, всегда оценивайте качество новых решений по сравнению с начальным решением, а не с текущим решением.temperature-decrease-is-linear : если true , уменьшение от начала до конечной температуры является линейным, в противном случае оно является экспоненциальным. Экспоненциальным уменьшением является стандартом в литературе с моделируемой отжигом, но в нашей статье рекомендуется линейное уменьшение.reheating : решать температуру с определенными интервалами.reheating-coefficient : сколько, чтобы повысить температуру, если reheating true .reheating-times : сколько раз, чтобы повысить температуру во время пробега.magic-number-exponent : так называемое «магическое число» оригинальной реализации Ропке и Писсингера (см. Ссылку выше).start-threshold : порог в начале пробега.end-threshold : порог в конце пробега.threshold-decrease-is-linear : уменьшается ли порог линейно ( true ) или экспоненциально ( false ) между значениями начала и конечной.initial-water-level-ratio : множитель до стоимости начального решения, чтобы получить начальный уровень воды.water-level-decrease-pct : процентное снижение уровня воды на каждой итерации.start-deviation : максимально допустимое отклонение в начале прогона.end-deviation : максимальное конечное отклонение в конце прогона.deviation-decrease-is-linear : уменьшается ли отклонение линейно ( true ) или экспоненциально ( false ) между значениями начала и конечной.list-size : размер списка позднего приема.allow-non-worsening : всегда принимать новое решение, не соблюдение.initial-water-level-ratio : множитель до стоимости начального решения, чтобы получить начальный уровень воды. gap-to-increase-water-level : пороговый разрыв, чтобы переоценить уровень воды. water-level-increase-pct : процент разницы в растворах, с помощью которого уровень воды увеличивается на этапах увеличения. water-level-decrease-exp-factor : экспоненциальный коэффициент (дельта в нашей статье) для использования при снижении уровня воды.start-probability : вероятность принятия в начале прогона.end-probability : вероятность принятия в конце прогона.probability-decrease-is-linear : уменьшается ли вероятность линейно ( true ) или экспоненциально ( false ) между начальными и конечными значениями. Это программное обеспечение лицензировано в соответствии с общедоступной лицензионной версией GNU 3. См. LICENSE файла для получения дополнительной информации.
