ALNS

alns adalah implementasi metaheuristik pencarian lingkungan besar adaptif (ALNS) yang umum, terdokumentasi dengan baik, dan teruji dengan Python. ALNS merupakan algoritma yang dapat digunakan untuk menyelesaikan permasalahan optimasi kombinatorial yang sulit. Algoritma dimulai dengan solusi awal. Kemudian algoritme melakukan iterasi hingga kriteria penghentian terpenuhi. Dalam setiap iterasi, operator penghancuran dan perbaikan dipilih, yang mengubah solusi saat ini menjadi solusi kandidat. Kandidat solusi ini kemudian dievaluasi berdasarkan kriteria penerimaan, dan skema pemilihan operator diperbarui berdasarkan hasil evaluasi.

Menginstal alns

Paket alns bergantung pada numpy dan matplotlib . Ini dapat diinstal dengan cara biasa seperti

 pip install alns

Selain itu, untuk mengaktifkan skema pemilihan operator yang lebih canggih menggunakan algoritma multi-strategi, alns dapat diinstal dengan ketergantungan MABBiser opsional:

 pip install alns[mabwiser]

Memulai

Dokumentasi tersedia di sini. Jika Anda baru mengenal metaheuristik atau ALNS, Anda mungkin mendapat manfaat dari membaca halaman pengantar ALNS.

Pustaka alns menyediakan algoritma ALNS dan berbagai kriteria penerimaan, skema pemilihan operator, dan kriteria penghentian. Untuk mengatasi masalah Anda sendiri, Anda harus menyediakan yang berikut ini:

• Status solusi untuk masalah Anda yang mengimplementasikan fungsi objective() .
• Solusi awal.
• Satu atau lebih operator penghancuran dan perbaikan yang disesuaikan dengan masalah Anda.

Templat kode "mulai cepat" tersedia di sini.

Contoh

Kami menyediakan beberapa contoh buku catatan yang menunjukkan bagaimana perpustakaan ALNS dapat digunakan. Ini termasuk:

• Masalah travelling salesman (TSP), di sini. Kami menyelesaikan contoh 131 kota menggunakan heuristik penghancuran dan perbaikan yang sangat sederhana.
• Masalah perutean kendaraan berkapasitas (CVRP), di sini. Kami memecahkan sebuah contoh dengan 241 pelanggan menggunakan kombinasi operator perbaikan yang serakah, dan operator penghancuran penghapusan substring yang disebabkan oleh kelonggaran .
• Masalah pemotongan stok (CSP), di sini. Kami menyelesaikan sebuah instance dengan 180 balok dengan 165 ukuran berbeda hanya dalam jumlah iterasi yang sangat terbatas.
• Masalah penjadwalan proyek dengan keterbatasan sumber daya (RCPSP), di sini. Kami menyelesaikan sebuah instance dengan 90 pekerjaan dan 4 sumber daya menggunakan sejumlah operator berbeda dan teknik peningkatan dari literatur.
• Masalah toko aliran permutasi (PFSP), di sini. Kami menyelesaikan sebuah instance dengan 50 pekerjaan dan 20 mesin. Selain itu, kami mendemonstrasikan beberapa fitur canggih ALNS, termasuk penyesuaian otomatis kriteria penerimaan dan menambahkan pencarian lokal ke operator perbaikan. Kami juga mendemonstrasikan bagaimana seseorang dapat menyetel parameter ALNS.

Terakhir, fitur-fitur notebook memberikan gambaran tentang berbagai pilihan yang tersedia dalam paket alns . Di buku catatan kami menggunakan opsi berbeda ini untuk memecahkan masalah mainan 0/1-ransel. Buku catatan ini merupakan titik awal yang baik ketika Anda sendiri ingin menggunakan skema, kriteria penerimaan, atau penghentian yang berbeda. Ini tersedia di sini.

Berkontribusi

Kami sangat berterima kasih atas kontribusi apa pun yang ingin Anda berikan. Silakan lihat di sini untuk memulai. Jika Anda ingin membuat perubahan besar, sebaiknya diskusikan perubahan tersebut terlebih dahulu di edisi GitHub yang baru. Jangan ragu untuk membukanya!

Mendapatkan bantuan

Jangan ragu untuk membuka terbitan atau rangkaian diskusi baru di sini di GitHub. Harap jangan mengirim email kepada kami dengan pertanyaan, masalah pemodelan, atau contoh kode. Hal ini jauh lebih mudah untuk didiskusikan melalui GitHub daripada melalui email. Saat menulis masalah atau diskusi Anda, harap ikuti petunjuk di sini.

Cara mengutip alns

Jika Anda menggunakan alns dalam penelitian Anda, mohon pertimbangkan untuk mengutip makalah berikut:

Wouda, NA, dan L. Lan (2023). ALNS: implementasi Python dari metaheuristik pencarian lingkungan besar yang adaptif. Jurnal Perangkat Lunak Sumber Terbuka , 8(81): 5028. https://doi.org/10.21105/joss.05028

Atau, menggunakan entri BibTeX berikut:

 @article { Wouda_Lan_ALNS_2023 , 
  doi = { 10.21105/joss.05028 } , 
  url = { https://doi.org/10.21105/joss.05028 } , 
  year = { 2023 } , 
  publisher = { The Open Journal } , 
  volume = { 8 } , 
  number = { 81 } , 
  pages = { 5028 } , 
  author = { Niels A. Wouda and Leon Lan } , 
  title = { {ALNS}: a {P}ython implementation of the adaptive large neighbourhood search metaheuristic } , 
  journal = { Journal of Open Source Software } 
}