adaptive large neighbourhood search
v0.2
이것은 Ropke와 Pisiser가 고안 한 (평행 한) 적응 형 대형 이웃 검색 알고리즘의 헤더 전용 C ++ 구현입니다. 이 코드는 Stefan Ropke가 나와 친절하게 공유 한 원래 구현을 기반으로 느슨하게입니다.
원래 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 }
}이 구현에는 논문에 소개 된 다중 수용 기준도 포함되어 있으며, 적응 형 대형 인근 검색 메타 습관 (Preprint)에 대한 수락 기준의 비교. 이 소프트웨어를 사용하는 경우이 마지막 논문을 다음과 같이 인용하십시오.
@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 }
}기능은 Doxygen 구문을 사용하여 코드에 철저히 문서화됩니다. 이것은 Metaheuristic 프레임 워크이므로 사용자는 문제 별 부품을 구현해야합니다. 코드 측면에서, 이는 사용자가 아래에 설명 된 구성 요소를 제공해야 함을 의미합니다.
사용자는 다음을 구현해야합니다.
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);
}
} 재현성을 위해, 초기 솔루션 제작자는 std::mt19937 ( <random> 헤더에서)의 ALNS 프레임 워크를 통과하는 의사 랜덤 번호 생성기를 사용할 수 있습니다.
파괴 및 수리 방법은 각각 기본 클래스에서 DestroyMethod 와 RepairMethod 에서 도출됩니다. DestroyMethod 에서 상속되는 클래스는 두 가지 방법을 구현해야합니다.
void destroy_solution(Solution sol&, std::mt19937& mt) 은 참조 (및 필요한 경우 prng, prng)로 솔루션을 가져 와서 그것을 파괴합니다.std::unique_ptr<DestroyMethod<Solution>> clone() const , 이는 Destrove Method를 복제하는 기본 클래스 DestroyMethod 에 unique_ptr 을 반환합니다. 마찬가지로, RepairMethod 에서 나온 클래스는 다음을 구현해야한다.
void repair_solution(Solution& sol, std::mt19937& mt) 은 참조 (및 필요한 경우 PRNG, PRNG)에 의해 (파괴 된) 솔루션을 가져 와서 수리합니다.std::unique_ptr<RepairMethod<Solution>> clone() const RepairMethod unique_ptr예를 들어:
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 최상의 솔루션을 개선하지 않고 사용자 정의 연속 반복 후에 호출됩니다 (아래 섹션 매개 변수 참조). Metaheuristic 프레임 워크의 모든 매개 변수는 파일 편집 Params.json 설정합니다. 아래에 설명되어 있습니다.
prerun-iterations : 알고리즘이 수락 매개 변수를 자동 조정하는 데 사용할 수있는 초기 반복 수. 이것은 의무적이지 않으며 0으로 설정할 수 있습니다.total-iterations : 반복 횟수에 대한 단단한 제한.timeout-s : 알고리즘의 CPU 시간에 대한 단단한 제한.iters-without-improvement-max : 최상의 솔루션을 개선하지 않고 연속 반복 수에 대한 어려운 제한. 평평한 조경 상황에 갇혀있을 때 일찍 달리기를 종료합니다.iters-without-improvement-alarm : 설정된 경우, 사용자가 알고리즘 방문자를 제공하는 경우,이 많은 연속 반복 후에는 방문자의 on_many_iters_without_improvement 메소드를 호출합니다. 사용자는이 메커니즘을 사용하여 로컬 Optima를 시도하고 탈출 할 수 있습니다. 예를 들어, 더 강한 파괴 방법 또는 다각화 휴리스틱을 적용 할 수 있습니다.iterations-without-syncing-threads : 알고리즘의 병렬 버전에서 스레드가 정보를 동기화하지 않고 ALNS 알고리즘의 독립적 인 사본처럼 작동하는 반복 횟수입니다. 스레드 동기화시 허용/파괴 가중치 및 현재 솔루션이 공유됩니다.prob-return-to-best-known : 각각의 반복시 가장 잘 알려진 솔루션은 현재 솔루션을이 확률로 대체합니다. 0은 좋은 기본이지만 사용자는 다각화에 대한 강화에 선호하는 값을 높일 수 있습니다.acceptance-criterion : 사전 정의 된 수락 기준 중 하나. 가능한 값은 (미사용) 매개 변수 키 acceptance-criterion-possible-values 에 나열되어 있습니다.acceptance-params-base : 수락 매개 변수 중 일부는 알고리즘 실행 과정에서 다릅니다. 값 time 과 iterations 소요될 수있는이 매개 변수는 시간 제한 ( timeout-s ) 또는 반복 제한 ( total-iterations )이 실행이 끝날 때를 추정하도록 고려해야하는지 지정합니다.scores : 이들은 각 반복에서 파괴/수리 점수를 업데이트하는 데 사용되는 승수입니다. 사용자는 4 개의 승수를 제공해야합니다.global-best .improved 경우accepted .decay 위의 세 값이 방법의 점수에 얼마나 빨리 영향을 미치는지 결정합니다. SANE 기본값은 1.0 미만으로 점수가 원활하게 변경되도록합니다.parameter-tuning-file : 매개 변수 튜닝을 수행하는 경우 결과가 저장되는 파일 이름입니다.results-log-basename : 결과 파일의베이스 이름. 다음에서는 수락 기준과 관련된 매개 변수를 나열합니다. 우리는 사용자가 각 매개 변수의 역할과 아래에 사용 된 용어를 더 잘 이해하기 위해 수락 기준 논문을 참조 할 것을 촉구합니다. 이 논문은 또한 해결 된 다양한 문제에 비해 최상의 조정 된 매개 변수를 제시합니다.
init-ratio-50p : 솔루션은 현재보다 훨씬 나쁘다.end-ratio-50p : 솔루션이 현재보다 훨씬 나빠질 수 있습니다.end-ratio-50p-refers-to-initial : true 로 설정된 경우 end-ratio-50p 의 설명에서 "현재 One"을 "초기"로 바꾸십시오. 다시 말해, 현재 솔루션이 아닌 초기 솔루션과 비교하여 항상 새로운 솔루션의 품질을 평가하십시오.temperature-decrease-is-linear : true 이라면 시작에서 종말 온도로의 감소는 선형입니다. 그렇지 않으면 지수입니다. 지수 감소는 시뮬레이션 된 어닐링 문헌의 표준이지만, 우리 논문에서 선형 감소가 권장됩니다.reheating : 특정 간격으로 온도를 다시 확대할지 여부.reheating-coefficient : reheating 이 true 이라면 온도를 얼마나 많이 늘릴 정도로reheating-times : 달리기 동안 온도를 늘리는 몇 번.magic-number-exponent : Ropke와 Pissinger의 독창적 인 구현의 소위 "매직 번호"(위 참조 참조).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 참조하십시오.
