Algoritma SA (Simulated Annealing) 6


Algoritma SA (Simulated Annealing) adalah salah satu algoritma yang digunakan untuk penjadwalan (scheduling). Tetapi bisa juga digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai penjadwalan sistem kerja karyawan terhadap pekerjaan dengan waktu kerja paling minimal

Sebagai pengetahuan umum, cara kerja algoritma ini berdasarkan perilaku benda logam yang didinginkan. Ketika logam dipanaskan dengan suhu tinggi, atom dan molekul logam akan pecah, dan menyebabkan logam tersebut meleleh, sehingga lebih mudah untuk berubah bentuk. Pada saat logam tersebut didinginkan, maka atom dan molekul logam akan saling mengikat kembali, dan mereka akan menemukan cara untuk saling mengikat dengan energi yang paling minimal.
Sehingga dalam kasus ini, pada saat suhu tinggi, program akan lebih mudah berubah bentuk, yaitu menerima solusi lain yang tidak berkaitan dengan solusi yang ada. Sedangkan pada suhu rendah, program hanya akan berfokus pada solusi yang ada, dan mencari nilai energi minimal dari solusi tersebut.



Diasumsikan ada 5 karyawan dan 6 pekerjaan yang harus dilakukan
Pekerjaan tertentu hanya dapat dilakukan oleh karyawan tertentu dan membutuhkan waktu yang berbeda-beda
Jika seorang karyawan melakukan lebih dari 1 pekerjaan, maka untuk berpindah ke pekerjaan berikutnya akan terkena tambahan waktu untuk mempersiapkan diri
Diasumsikan data awal mengenai karyawan, pekerjaan, dan waktu adalah sebagai berikut
Angka 0 berarti karywan tersebut tidak dapat melakukan pekerjaan

(menit) menggoreng merebus mencetak menyaring mencuci memotong
karyawan A 15 7 5 0 0 0
karyawan B 0 3 9 7 0 0
karyawan C 0 0 7 11 7 0
karyawan D 0 0 0 13 3 9
karyawan E 5 0 0 0 5 5



Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data awal adalah sebagai berikut:



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah karyawan yang digunakan
Diasumsikan dalam kasus ini, jumlah karyawan ada 5 orang, yaitu karyawan A,B,C,D,E

* Tentukan jumlah pekerjaan yang ada
Diasumsikan dalam kasus ini, jumlah pekerjaan ada 6 jenis, yaitu memanaskan, mengepress, mendinginkan, membongkar, mencuci, merakit

* Tentukan banyak perulangan yang dilakukan oleh proses algoritma ini.
DIasumsikan dalam kasus ini, jumlah iterasi yang digunakan adalah 100.000

* Tentukan nilai suhu awal yang digunakan dalam proses.
DIasumsikan dalam kasus ini, nilai suhu awal adalah 10.000

* Tentukan faktor penurun suhu pada saat digunakan untuk proses berikutnya
Faktor penurun suhu berguna dalam proses perhitungan kemungkinan solusi berikutnya
Pada saat suhu tinggi (perhitungan awal), variabel solusi akan lebih mudah menerima solusi-solusi baru, agar tidak terjebak pada solusi awal yang mungkin tidak optimal
Pada saat suhu rendah (perhitungan akhir), variabel solusi tidak lagi menerima solusi baru, agar jawaban solusi tidak berubah-ubah
Diasumsikan dalam kasus ini, nilai faktor penurun suhu adalah 0.995,
artinya: untuk setiap perulangan berikutnya suhu akan berkurang sebanyak 0.005 * 10.000 = 50 derajat


Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan solusi acak untuk digunakan sebagai solusi awal

2. Tentukan nilai energi dari solusi tersebut, yaitu jumlah waktu yang digunakan masing-masing karyawan untuk melakukan pekerjaan yang ada

Lakukan proses perhitungan sebanyak jumlah perulangan dan selama suhu belum mendekati 0 derajat (poin 3 – 8)

3. Tentukan kemungkinan solusi lainnya dan hitung nilai energi untuk solusi ini

* Gunakan fungsi ini untuk menghitung kemungkinan solusi berikutnya
Tentukan pekerjaan secara acak, kemudian tentukan karyawan secara acak
Pastikan karyawan acak tersebut mampu melakukan pekerjaan acak yang didefinisikan sebelumnya
Perlu diperhatikan bahwa fungsi ini bisa mengembalikan nilai solusi yang sama persis dengan solusi yang sebelumnya.
Dengan kata lain, tidak menghasilkan solusi baru

* Gunakan fungsi ini untuk menghitung nilai energi dari sebuah solusi
Jangan lupa menghitung tambahan waktu jika seorang karyawan melakukan lebih dari 1 pekerjaan

4. Jika solusi yang ditemukan ternyata lebih baik dari solusi umum, maka ambil solusi ini sebagai solusi terbaik

5. Tentukan nilai acak sebagai nilai pembanding penerimaan solusi baru

6. Hitung probabilitas penerimaan solusi baru
Jika nilai energi solusi baru lebih dari nilai energi sekarang, maka nilai kemungkinan penerimaan solusi baru adalah 1 (pasti diterima)
Jika nilai energi solusi baru tidak lebih dari nilai energi sekarang, maka nilai kemungkinan penerimaan solusi baru akan dihitung dengan rumus exp((e − e’) / T)
Jika nilai suhu tinggi, maka rumus tersebut akan mengembalikan nilai mendekati angka 1, dan sebaliknya pada suhu rendah, maka rumus tersebut akan mengembalikan nilai mendekati angka 0

7. Jika nilai kemungkinan penerimaan solusi baru lebih dari nilai acak p, maka ambil solusi ini sebagai solusi umum terbaik

8. Turunkan suhu pada saat memasuki perulangan barikutnya, yaitu dengan rumus: suhu * alpha


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd26


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.


Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

6 pemikiran di “Algoritma SA (Simulated Annealing)

    • pip Penulis

      Bisakah anda jelaskan dibagian manakah yang terdapat error. Saya sudah melakukan tes kembali dan tidak terdapat kesalahan pada skrip ini. Beberapa laporan kesalahan yang saya terima adalah karena skrip ini dijalankan dengan menggunakan proyek bertipe windows application. Skrip ini bukanlah merupakan windows application melainkan console application

      • kamal

        saya menjalankannya di visual basic online compiler. kalau boleh bisakah anda memberikan saya source code dalam bentuk java atau php. karena ini berkaitan dengan projek saya terimakasih @pip

        • pip Penulis

          Mohon maaf saya tidak memiliki contoh skrip algoritma ini dalam bahasa lain. Tetapi skrip ini tentu saja bisa dikonversi ke dalam bahasa java atau php karena tidak bergantung pada fungsi-fungsi yang disediakan oleh visual studio. Jika tertarik menggunakan jasa saya maka silahkan menghubungi saya dengan menggunakan kontak yang dapat anda lihat pada halaman “Hubungi Kami”.

      • kamal

        tidak dapatkah saya mengirim gambar, untuk menunjukan detail errornya ?, dan saya juga ingin menunjukan hasil conversi kedalam program phpnya. apakah sudah sesuai, karena output yang di hasilkan sedikit berbeda dari gambar output yang tertera di artikel.

        • pip Penulis

          Tentu saja anda dapat melakukan hal tersebut dengan berkomunikasi melalui jalur pribadi. Silahkan menghubungi saya dengan menggunakan kontak yang dapat anda lihat pada halaman “Hubungi Kami”

          Jika output yang dihasilkan tidak sama, maka konversi anda tidak sempurna karena masih ada bagian yang kurang tepat.