Annealing Simulasi — Optimasi Probabilistik
- Tahun
- 1983
- Jenis
- Probabilistic metaheuristic / local search
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Annealing simulasi adalah metaheuristik pencarian lokal probabilistik yang diperkenalkan oleh Kirkpatrick, Gelatt, dan Vecchi pada tahun 1983.
Metode ini memodelkan proses annealing fisik dalam metalurgi — di mana suatu material dipanaskan lalu didinginkan perlahan untuk mencapai keadaan kristal berenergi rendah — dan menggunakan analogi ini untuk keluar dari optimum lokal dalam masalah optimasi kombinatorial dan kontinu.
Intuisi di balik metode
Bayangkan mencoba menemukan titik terendah di lanskap berbukit sambil ditutup matanya. Pencarian yang murni serakah selalu melangkah menuruni bukit dan terjebak di lembah pertama yang ditemukannya — yang mungkin bukan yang terdalam. Annealing simulasi memperkenalkan keacakan yang terkontrol: di awal, ketika 'suhu' tinggi, algoritma bersedia sesekali melangkah ke atas, menerima solusi yang lebih buruk secara kebetulan. Seiring suhu menurun sesuai jadwal pendinginan, algoritma menjadi semakin selektif, konvergen pada suatu solusi. Kesediaan untuk menerima pergerakan yang lebih buruk pada suhu tinggi inilah yang memungkinkan metode ini keluar dari optimum lokal yang dangkal dan menjelajahi lanskap dengan lebih menyeluruh.
Sejarah
Annealing simulasi diperkenalkan oleh Kirkpatrick, Gelatt, dan Vecchi dalam makalah penting mereka tahun 1983 di Science, yang menarik analogi eksplisit antara annealing termodinamika padatan dan optimasi kombinatorial. Gagasan yang sama diajukan secara independen oleh Cerny (1985) dalam konteks masalah pedagang keliling. van Laarhoven dan Aarts (1987) memberikan perlakuan teoritis yang ketat pertama, membuktikan sifat konvergensi di bawah berbagai jadwal pendinginan. Sejak itu metode ini menjadi salah satu metaheuristik yang paling banyak dipelajari dan diterapkan, digunakan di seluruh desain teknik, riset operasi, tata letak VLSI, dan penyetelan hyperparameter machine learning.
Kapan digunakan
Annealing simulasi dapat diterapkan pada masalah apa pun di mana struktur lingkungan dapat didefinisikan di atas ruang solusi, terlepas dari apakah fungsi objektif dapat diturunkan, cembung, atau bahkan dinyatakan secara analitis. Sangat cocok untuk masalah kombinatorial (penjadwalan, perutean, masalah graf) dan optimasi kotak hitam kontinu. Tidak diperlukan data pelatihan atau asumsi normalitas. Jadwal pendinginan dan struktur lingkungan harus disesuaikan dengan masalah; menjalankan kurang dari sekitar 1.000 iterasi berisiko konvergensi prematur ke optimum lokal, dalam hal ini pencarian lokal deterministik yang lebih sederhana harus lebih disukai.
Batasan dan pertimbangan
- Kualitas solusi sensitif terhadap jadwal pendinginan; jadwal yang buruk dapat menghasilkan hasil yang tidak lebih baik dari pencarian acak.
- Struktur lingkungan harus dirancang untuk setiap kelas masalah, yang membutuhkan keahlian domain.
- Konvergensi ke optimum global membutuhkan pendinginan yang sangat lambat dalam praktik, membuat waktu eksekusi lama untuk jaminan kualitas tinggi.
- Tidak memanfaatkan informasi gradien atau struktural, sehingga metode berbasis gradien mengunggulinya pada masalah yang mulus dan dapat diturunkan.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Dapat keluar dari optimum lokal melalui penerimaan probabilistik solusi yang lebih buruk, tidak seperti hill-climbing murni.
- Berlaku untuk hampir semua jenis masalah — kombinatorial, kontinu, campuran — selama struktur lingkungan didefinisikan.
- Tidak memerlukan informasi gradien dan tidak peduli dengan struktur matematis fungsi objektif.
- Memiliki jaminan teoritis konvergensi ke optimum global di bawah pendinginan yang cukup lambat (Hajek 1988).
- Beberapa hiperparameter: suhu awal, laju pendinginan, dan struktur lingkungan.
Penerapan
- Masalah penjadwalan dan penyusunan jadwal kombinatorial di mana ruang solusi terlalu besar untuk pencarian menyeluruh.
- Masalah pedagang keliling dan masalah perutean kendaraan dalam logistik dan riset operasi.
- Tata letak sirkuit VLSI dan perencanaan lantai chip dalam teknik elektro.
- Pelipatan protein dan masalah konformasi molekuler dalam biologi komputasi.
- Optimasi hyperparameter untuk model machine learning ketika informasi gradien tidak tersedia.
- Masalah alokasi dan penugasan sumber daya dalam teknik dan ilmu manajemen.
Cara kerjanya
Cara kerjanya
Algoritma dimulai dengan solusi awal — titik layak apa pun di ruang pencarian — dan suhu awal yang tinggi. Solusi awal bisa acak atau spesifik masalah; suhu awal biasanya diatur cukup tinggi sehingga hampir semua solusi tetangga akan diterima di awal.
Solusi tetangga dihasilkan dengan menerapkan perubahan acak kecil (sebuah 'pergerakan') pada solusi saat ini. Struktur lingkungan harus disesuaikan dengan masalah: untuk masalah penjadwalan, pergerakan mungkin menukar dua tugas; untuk fungsi kontinu, pergerakan mungkin menambahkan gangguan acak kecil pada vektor parameter saat ini.
Perbedaan nilai objektif antara solusi baru dan solusi saat ini dihitung. Jika solusi baru lebih baik, solusi tersebut selalu diterima. Jika lebih buruk, solusi tersebut diterima dengan probabilitas yang menurun seiring dengan besarnya kerusakan dan suhu saat ini — biasanya exp(−ΔE / T). Penerimaan probabilistik ini adalah mekanisme inti yang mencegah konvergensi prematur.
Setelah setiap iterasi (atau setelah sejumlah pergerakan tetap pada suhu yang sama), suhu dikurangi sesuai dengan jadwal pendinginan — umumnya jadwal geometris T ← α·T di mana α sedikit di bawah 1. Pilihan jadwal pendinginan sangat memengaruhi kualitas solusi: pendinginan terlalu cepat menjebak pencarian dalam optimum lokal; pendinginan terlalu lambat membuang waktu komputasi.
Algoritma berhenti ketika suhu turun di bawah ambang batas minimum, jumlah iterasi maksimum tercapai, atau solusi tidak membaik selama jumlah langkah yang ditentukan. Solusi terbaik yang ditemui sepanjang seluruh eksekusi — bukan hanya keadaan akhir — dikembalikan sebagai hasil.
Kesalahan umum
- Menjalankan iterasi terlalu sedikit (sekitar di bawah 1.000) mencegah jadwal pendinginan berfungsi dengan baik dan membuat pencarian terjebak dalam optimum lokal — lebih pilih tabu search atau pencarian lokal deterministik jika waktu eksekusi sangat terbatas.
- Menetapkan suhu awal terlalu rendah berarti algoritma segera berperilaku seperti pencarian serakah dan kehilangan kemampuannya untuk keluar dari optimum lokal.
- Menetapkan laju pendinginan terlalu agresif (misalnya, α di bawah 0,9) menyebabkan konvergensi prematur; verifikasi kualitas solusi akhir dengan memulai ulang dari beberapa solusi awal.
- Menerapkan pergerakan lingkungan yang dirancang untuk satu jenis masalah ke masalah yang berbeda dapat membuat pergerakan menjadi tidak layak atau tidak berarti — selalu verifikasi bahwa setiap tetangga yang dihasilkan adalah solusi yang valid.
- Melaporkan hanya keadaan akhir daripada solusi terbaik yang pernah dilihat selama eksekusi dapat melewatkan optimum sebenarnya yang ditemukan pada langkah perantara.
Pertanyaan yang sering diajukan
Bagaimana cara memilih jadwal pendinginan?
Jadwal geometris T ← α·T dengan α antara 0,90 dan 0,99 adalah titik awal yang paling umum. Pendekatan praktis adalah mengatur suhu awal cukup tinggi sehingga sekitar 80% pergerakan diterima di awal, lalu menurunkannya hingga kurang dari 1% pergerakan ke atas diterima. Jika kualitas solusi akhir buruk, perlambat laju pendinginan (tingkatkan α); jika waktu eksekusi terlalu lama, percepat. Selalu jalankan algoritma beberapa kali dari solusi awal yang berbeda untuk menilai ketahanan.
Bagaimana annealing simulasi berbeda dari algoritma genetik atau optimasi kawanan partikel?
Annealing simulasi mempertahankan satu solusi dan menjelajahi lingkungan melalui gangguan acak, menerima solusi yang lebih buruk secara probabilistik. Algoritma genetik dan optimasi kawanan partikel mempertahankan populasi solusi dan menggunakan crossover, mutasi, atau pergerakan kawanan untuk mengembangkan populasi. Annealing simulasi umumnya lebih sederhana untuk diimplementasikan untuk masalah dengan struktur lingkungan yang alami, sementara metode berbasis populasi bisa lebih efektif untuk masalah kontinu berdimensi tinggi.
Apakah optimum global dijamin?
Secara teoritis ya, dengan syarat suhu menurun cukup lambat (pendinginan logaritmik). Dalam praktik, pendinginan seperti itu tidak layak secara komputasi, sehingga algoritma menemukan solusi yang mendekati optimal. Kualitas hasil meningkat dengan pendinginan yang lebih lambat dan lebih banyak iterasi, tetapi tidak ada jaminan waktu terbatas. Menjalankan beberapa restart dan menyimpan solusi terbaik yang ditemukan adalah cara praktis untuk meningkatkan kepercayaan diri.
Kapan saya harus memilih tabu search atau algoritma genetik sebagai gantinya?
Pilih tabu search ketika Anda membutuhkan pencarian deterministik yang dipandu memori yang menghindari kunjungan ulang solusi baru-baru ini dan dapat mengeksploitasi struktur masalah secara efisien dalam waktu yang lebih singkat. Pilih algoritma genetik atau optimasi kawanan partikel ketika masalahnya berdimensi tinggi dan kontinu, atau ketika populasi solusi yang beragam diperlukan untuk memetakan lanskap optimum. Annealing simulasi adalah pilihan default yang kuat untuk masalah kombinatorial dengan struktur lingkungan yang jelas dan ketika kesederhanaan implementasi penting.
Metode terkait
Sumber
Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
Buka referensi DOIDisalin.van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.
ISBN: 9789027725431Disalin.