adaptive large neighbourhood search
v0.2
Ini adalah implementasi C ++ yang header dari algoritma pencarian tetangga besar adaptif (paralel), yang dirancang oleh Ropke dan Pisinger. Kode ini secara longgar didasarkan pada implementasi asli yang dibagikan oleh Stefan Ropke dengan saya.
Kerangka kerja ALNS asli dikembangkan dalam makalah ini:
@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 }
}Implementasi ini juga mencakup beberapa kriteria penerimaan, karena mereka diperkenalkan dalam makalah perbandingan kriteria penerimaan untuk pencarian lingkungan besar adaptif Metaheuristik (preprint). Jika Anda menggunakan perangkat lunak ini, silakan kutip makalah terakhir ini sebagai berikut:
@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 }
}Fungsi didokumentasikan secara menyeluruh dalam kode, menggunakan sintaks doxygen. Karena ini adalah kerangka kerja metaheuristik, pengguna harus menerapkan bagian-bagian khusus masalah. Dalam hal kode, ini berarti bahwa pengguna perlu menyediakan komponen yang dijelaskan di bawah ini.
Pengguna harus menerapkan:
getInstanceSize() yang mengembalikan ukuran instance (misalnya, jumlah simpul dalam instance TSP).getCost() mengembalikan biaya untuk meminimalkan (misalnya, panjang tur TSP).InitialSolutionCreator untuk menghasilkan solusi awal untuk masalah. Setelah ini di tempat, pengguna dapat membuat instance objek PALNS . Misalnya:
auto alns = PALNS<TSPInstance, TSPSolution>{instance}; Di mana TSPInstance adalah pemodelan kelas contoh masalah dan TSPSolution adalah kelas pemodelan solusi masalah. Pengguna harus menyediakan setidaknya fungsi yang disebutkan di atas. Misalnya:
std:: uint32_t TSPInstance::getInstanceSize () const {
return this -> numberOfVertices ;
}
double TSPSolution::getCost () const {
return this -> tourLength ;
}Selain itu, karena metode ALNS dimulai dari solusi konkret, pengguna harus menyediakan pencipta solusi awal:
struct TSPRandomSolutionCreator : InitialSolutionCreator<TSPSolution, TSPInstance> {
TSPSolution create_initial_solution ( const TPSInstance& instance, std::mt19937& mt) {
return TSPSolution::shuffled_vertices (mt);
}
} Untuk reproduksibilitas, pencipta solusi awal dapat menggunakan generator nomor pseudo-acak yang dilewati oleh kerangka kerja ALNS, dari tipe std::mt19937 (dari header <random> ).
Metode hancur dan perbaikan masing -masing akan diturunkan, dari kelas -kelas dasar DestroyMethod dan RepairMethod . Kelas yang mewarisi dari DestroyMethod harus menerapkan dua metode:
void destroy_solution(Solution sol&, std::mt19937& mt) , yang mengambil solusi dengan referensi (dan prng, jika Anda membutuhkannya) dan menghancurkannya di tempat.std::unique_ptr<DestroyMethod<Solution>> clone() const , yang mengembalikan unique_ptr ke kelas dasar DestroyMethod mengkloning metode hancur. Demikian pula, kelas yang mewarisi dari RepairMethod harus diterapkan:
void repair_solution(Solution& sol, std::mt19937& mt) , yang mengambil solusi (hancur) dengan referensi (dan prng, jika Anda membutuhkannya) dan memperbaikinya di tempat.std::unique_ptr<RepairMethod<Solution>> clone() const , yang mengembalikan unique_ptr ke kelas dasar RepairMethod yang mengkloning metode perbaikan.Misalnya:
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>>();
}
}; Pengguna dapat memilih antara menggunakan satu kriteria penerimaan yang telah ditentukan, atau mengimplementasikan warisannya sendiri dari AcceptanceCriterion kelas dasar. Cara praktis untuk memantau algoritma dan melakukan tindakan non-standar selama proses solusi adalah dengan memberikan objek pengunjung yang mewarisi dari AlgorithmVisitor . Pengunjung algoritma harus mengimplementasikan panggilan balik berikut:
on_algorithm_start yang disebut sebelum iterasi ALNS pertama.on_prerun_end yang dipanggil ketika pra-lari selesai (lihat parameter bagian di bawah).on_iteration_end yang dipanggil di akhir setiap iterasi.on_many_iters_without_improvement yang dipanggil setelah jumlah iterasi berturut-turut yang ditentukan pengguna tanpa meningkatkan solusi terbaik (lihat parameter bagian di bawah). Semua parameter dari kerangka kerja metaheuristik ditetapkan pengeditan file Params.json . Mereka dijelaskan di bawah ini:
prerun-iterations : Jumlah iterasi awal yang dapat digunakan algoritma untuk mencoba untuk mengotorkan parameter penerimaan. Ini tidak wajib dan dapat diatur ke nol.total-iterations : Batas keras pada jumlah iterasi.timeout-s : Batas keras pada waktu CPU dari algoritma.iters-without-improvement-max : batas keras pada jumlah iterasi berturut-turut tanpa perbaikan solusi terbaik. Ini mengakhiri lari lebih awal ketika terjebak dalam situasi lanskap datar .iters-without-improvement-alarm : Jika diatur, dan jika pengguna memberikan pengunjung algoritma, setelah banyak iterasi berturut-turut, kami akan memanggil metode pengunjung on_many_iters_without_improvement . Pengguna dapat menggunakan mekanisme ini untuk mencoba dan menghindari optima lokal. Misalnya, itu dapat menerapkan metode hancur yang lebih kuat, atau heuristik diversifikasi.iterations-without-syncing-threads : Dalam versi paralel dari algoritma, ini adalah jumlah iterasi di mana utas tidak menyinkronkan informasi dan berperilaku seperti salinan independen dari algoritma ALNS. Setelah sinkronisasi utas, bobot menerima/menghancurkan dan solusi saat ini dibagi.prob-return-to-best-known : Pada setiap iterasi, solusi yang paling terkenal akan menggantikan solusi saat ini dengan probabilitas ini. Nol adalah default yang baik, tetapi pengguna dapat menetapkan nilai yang lebih tinggi untuk mendukung intensifikasi daripada diversifikasi.acceptance-criterion : Salah satu kriteria penerimaan yang telah ditentukan sebelumnya. Nilai-nilai yang mungkin tercantum dalam acceptance-criterion-possible-values parameter (tidak digunakan).acceptance-params-base : Beberapa parameter penerimaan bervariasi selama menjalankan algoritma. Parameter ini, yang dapat mengambil nilai time dan iterations menentukan jika batas waktu ( timeout-s ) atau batas iterasi ( total-iterations ) harus dipertimbangkan untuk memperkirakan kapan menjalankan akan berakhir.scores : Ini adalah pengganda yang digunakan untuk memperbarui skor hancur/perbaikan di setiap iterasi. Pengguna harus memberikan empat pengganda:global-best jika solusi baru lebih baik dari solusi terbaik sebelumnya, jika tidakimproved jika solusi baru lebih baik dari solusi saat ini, jika tidakaccepted jika solusi baru diterima oleh kriteria penerimaan.decay , menentukan seberapa cepat tiga nilai di atas mempengaruhi skor metode. Default waras hanya sedikit kurang dari 1,0, untuk memastikan bahwa skor berubah dengan lancar.parameter-tuning-file : Jika melakukan penyetelan parameter, ini adalah nama file di mana hasilnya akan disimpan.results-log-basename : Basename untuk file hasil. Di berikut ini kami mencantumkan parameter relatif terhadap kriteria penerimaan. Kami mendesak pengguna untuk merujuk ke makalah kriteria penerimaan untuk lebih memahami peran setiap parameter, dan terminologi yang digunakan di bawah ini. Makalah ini juga menyajikan parameter yang disetel terbaik pada berbagai masalah yang diselesaikan.
init-ratio-50p : Solusi ini jauh lebih buruk daripada yang saat ini diterima dengan probabilitas 50% pada awal pelarian.end-ratio-50p : Solusi ini jauh lebih buruk daripada yang saat ini diterima dengan probabilitas 50% pada akhir menjalankan.end-ratio-50p-refers-to-initial : Jika diatur ke true , dalam deskripsi end-ratio-50p mengganti "saat ini" dengan "awal". Dengan kata lain, selalu evaluasi kualitas solusi baru dibandingkan dengan solusi awal dan bukan dengan solusi saat ini.temperature-decrease-is-linear : Jika true , penurunan dari awal ke suhu akhir linier, jika tidak itu eksponensial. Penurunan eksponensial adalah standar dalam literatur anil simulasi, tetapi penurunan linier direkomendasikan dalam makalah kami.reheating : Apakah akan menabrak kembali suhu pada interval tertentu.reheating-coefficient : Dengan berapa banyak untuk meningkatkan suhu, jika reheating true .reheating-times : Berapa kali untuk meningkatkan suhu selama berjalan.magic-number-exponent : Yang disebut "nomor ajaib" dari implementasi asli Ropke dan Pissinger (lihat referensi di atas).start-threshold : Ambang batas pada awal pelarian.end-threshold : Ambang batas di akhir pelarian.threshold-decrease-is-linear : apakah ambang batas menurun secara linier ( true ) atau secara eksponensial ( false ) antara nilai awal dan akhir.initial-water-level-ratio : Pengganda dengan biaya solusi awal, untuk mendapatkan level air awal.water-level-decrease-pct : Persentase penurunan ketinggian air, pada setiap iterasi.start-deviation : Maksimal diizinkan penyimpangan pada awal pelarian.end-deviation : Deviasi akhir maksimum di akhir pelarian.deviation-decrease-is-linear : Apakah penyimpangan menurun secara linier ( true ) atau secara eksponensial ( false ) antara nilai awal dan akhir.list-size : Ukuran Daftar Penerimaan Akhir.allow-non-worsening : Apakah akan selalu menerima solusi baru yang tidak melumpuhkan.initial-water-level-ratio : Pengganda dengan biaya solusi awal, untuk mendapatkan level air awal. gap-to-increase-water-level : Threshold Gap untuk meningkatkan kembali ketinggian air. water-level-increase-pct : Persentase perbedaan larutan, yang dengannya level air meningkat selama fase peningkatan. water-level-decrease-exp-factor : Faktor eksponensial (delta di kertas kami) untuk digunakan saat mengurangi ketinggian air.start-probability : Probabilitas penerimaan pada awal menjalankan.end-probability : Probabilitas penerimaan di akhir pelarian.probability-decrease-is-linear : apakah probabilitas menurun secara linier ( true ) atau secara eksponensial ( false ) antara nilai awal dan akhir. Perangkat lunak ini dilisensikan di bawah GNU Public License Version 3. Lihat LICENSE File untuk informasi lebih lanjut.
