Algoritma SA (Simulated Annealing) 16


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)menggorengmerebusmencetakmenyaringmencucimemotong
karyawan A1575000
karyawan B039700
karyawan C0071170
karyawan D0001339
karyawan E500055



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

Dim data(jumlahKaryawan - 1)() As Double
data(0) = New Double() {15, 7, 5, 0, 0, 0}
data(1) = New Double() {0, 3, 9, 7, 0, 0}
data(2) = New Double() {0, 0, 7, 11, 7, 0}
data(3) = New Double() {0, 0, 0, 13, 3, 9}
data(4) = New Double() {5, 0, 0, 0, 5, 5}



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

Const jumlahKaryawan As Integer = 5

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

Const jumlahPekerjaan As Integer = 6

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

Dim iterasi As Integer = 0
Dim maksIterasi As Integer = 1000000

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

Dim suhuSekarang As Double = 10000.0

* 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

Dim alpha As Double = 0.995

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan solusi acak untuk digunakan sebagai solusi awal

Dim solusi(jumlahPekerjaan - 1) As Integer
For t = 0 To jumlahPekerjaan - 1
	'Ambil nilai w secara acak
	Dim w As Integer = rnd.Next(0, jumlahKaryawan)
	' pastikan karyawan ke w dapat melakukan pekerjaan ke t
	Do While data(w)(t) = 0.0
		w += 1
		If w > jumlahKaryawan - 1 Then
			w = 0
		End If
	Loop
	solusi(t) = w
Next t

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

Dim energi As Double = HitungEnergi(solusi, data)

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

solusiBerikutnya = KemungkinanSolusiBerikutnya(solusi, data)
energiSolusiBerikutnya = HitungEnergi(solusiBerikutnya, data)

* 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

Private Function KemungkinanSolusiBerikutnya(ByVal solusiSekarang() As Integer, ByVal data()() As Double) As Integer()
	Dim jumlahKaryawan As Integer = data.Length
	Dim jumlahPekerjaan As Integer = data(0).Length
	Dim solusi(jumlahPekerjaan - 1) As Integer

	' Tentukan pekerjaan secara acak 
	Dim pekerjaan As Integer = rnd.Next(0, jumlahPekerjaan)
	' Tentukan karyawan secara acak
	Dim karyawan As Integer = rnd.Next(0, jumlahKaryawan)
	' Pastikan karyawan acak tersebut mampu melakukan pekerjaan acak yang didefinisikan sebelumnya
	Do While data(karyawan)(pekerjaan) = 0.0
		karyawan += 1
		If karyawan > jumlahKaryawan - 1 Then
			karyawan = 0
		End If
	Loop

	solusiSekarang.CopyTo(solusi, 0)
	solusi(pekerjaan) = karyawan
	Return solusi
End Function

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

Private Function HitungEnergi(ByVal solusi() As Integer, ByVal data()() As Double) As Double
	Dim hasil As Double = 0.0
	For t = 0 To solusi.Length - 1
		Dim karyawan As Integer = solusi(t)
		Dim waktu As Double = data(karyawan)(t)
		hasil += waktu
	Next t

	'Jangan lupa menghitung tambahan waktu jika seorang karyawan melakukan lebih dari 1 pekerjaan
	Dim jumlahKaryawan As Integer = data.Length
	Dim jumlahPekerjaan(jumlahKaryawan - 1) As Integer
	For t = 0 To solusi.Length - 1
		Dim karyawan As Integer = solusi(t)
		jumlahPekerjaan(karyawan) += 1
		If jumlahPekerjaan(karyawan) > 1 Then
			hasil += 5
		End If
	Next t
	Return hasil
End Function

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

If energiSolusiBerikutnya < energiTerbaik Then
	solusiTerbaik = solusiBerikutnya
	energiTerbaik = energiSolusiBerikutnya

	Console.WriteLine("Iterasi ke " & iterasi & ", pada suhu " & suhuSekarang.ToString("F2") & " derajat")
	Console.Write("Solusi terbaik yang baru: ")
	For i = 0 To solusiTerbaik.Length - 1
		Console.Write(solusiTerbaik(i) & " ")
	Next i
	Console.Write(", dengan Nilai Energi = " & energiTerbaik.ToString("F2") & vbCrLf)
End If

5. Tentukan nilai acak sebagai nilai pembanding penerimaan solusi baru

Dim p As Double = rnd.NextDouble()

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

Dim kemungkinanPenerimaanSolusiBaru As Double = 0
If energiSolusiBerikutnya < energi Then
	kemungkinanPenerimaanSolusiBaru = 1.0
Else
	kemungkinanPenerimaanSolusiBaru = Math.Exp((energi - energiSolusiBerikutnya) / suhuSekarang)
End If

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

If kemungkinanPenerimaanSolusiBaru > p Then
	solusi = solusiBerikutnya
	energi = energiSolusiBerikutnya
End If

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

suhuSekarang = suhuSekarang * alpha
iterasi += 1

Hasil akhir adalah: (klik untuk perbesar gambar)

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 *

16 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.

    • pip Penulis

      Pada skrip tersebut saya gunakan variabel pembangkit bilangan acak dengan menggunakan seed sehingga seharusnya hasilnya akan tetap sama. Jika hasilnya berubah2 maka menurut saya tidak apa-apa asalkan perhitungannya sudah benar.

  • sari

    bisa dijelaskan tidak bagaimana cara mendapatkan nilai energi awal (solusi awal) pada saat dibangkitkan bilangan acak.. energi 29.00 darimana?

    • pip Penulis

      Cara perhitungan energi dilakukan pada fungsi yang saya tampilkan diantara nomor 3 dan 4.

      Solusi awal ditentukan dengan cara memasangkan pekerja / karyawan pada tugas yang tersedia secara acak dengan catatan bahwa pekerja tersebut harus dapat melakukan pekerjaan yang dimaksud. Disini didapatkan solusi yaitu 4 0 0 2 2 3 artinya:
      Pekerjaan pertama (menggoreng) diberikan pada karyawan kelima
      Pekerjaan kedua (merebus) dan ketiga (mencetak) diberikan pada karyawan pertama
      Pekerjaan keempat (menyaring) dan kelima (mencuci) diberikan pada karyawan ketiga
      Pekerjaan keenam (memotong) diberikan pada karyawan keempat

      NIlai energi didapatkan dengan menjumlahkan waktu yang diperlukan oleh masing-masing karyawan untuk melakukan pekerjaan tersebut. Dengan mengacu pada tabel waktu pekerjaan karyawan maka nilai energinya adalah: 5 + 7 + 5 + 11 + 7 + 9 = 44

      Tetapi terdapat kondisi tambahan bahwa apabila seorang pekerja melakukan pekerjaan berturutan maka pekerja tersebut membutuhkan waktu tambahan untuk beralih dari pekerjaan sebelumnya menuju pekerjaan berikutnya. Dalam contoh diatas karyawan pertama dan ketiga melakukan pekerjaan berurutan sebanyak 1 kali sehingga waktu pekerjaan bertambah sebanyak 5 * 2 = 10 menit. Dengan kata lain nilai energi akhir adalah 44 + 10 = 54.

      * Sepertinya terdapat kesalahan pada screenshot yang terlampir sehingga anda menjadi bingung dengan perhitungan diatas. Saya sudah membetulkan tampilan screenshot tersebut agar menampilkan output yang sebenarnya.

      • Dedi bram

        Mau tanya, energi pada simulated annealing ini apakah sama dengan fitness pada algoritma genetika?. Lalu random numbernya ini rangenya dari 0-1 ?. Lalu apakah hasil dari math.exp itu rangenya pasti 0-1 juga? Saya coba hasilnya selalu jauh diatas 1

        • pip Penulis

          Ya, betul. Yang dimaksud dengan energi pada algoritma ini adalah Kurang lebih sama seperti nilai fitness pada algoritma genetika.

          Bilangan acak tidak selalu bernilai 0 – 1 karena bergantung dari cara pemanggilan fungsi bilangan acak tersebut. rnd.NextDouble memang melakukan pembangkitan bilangan pecahan antara 0 – 1, tetapi dalam skrip diatas juga digunakan rnd.Next dimana nilai acak dibangkitkan secara bilangan bulat dari angka 0 sampai dengan jumlah karyawan – 1.

          Hasil dari Math.EXP akan selalu berada di rentang 0 – 1. Pada saat saya jalankan skrip ini kembali, nilainya tidak pernah lebih dari satu.

  • athir

    Cara perhitungan energi dilakukan pada fungsi yang saya tampilkan diantara nomor 3 dan 4.
    Solusi awal ditentukan dengan cara memasangkan pekerja / karyawan pada tugas yang tersedia secara acak dengan catatan bahwa pekerja tersebut harus dapat melakukan pekerjaan yang dimaksud. Disini didapatkan solusi yaitu 4 0 0 2 2 3 artinya:
    Pekerjaan pertama (menggoreng) diberikan pada karyawan kelima
    Pekerjaan kedua (merebus) dan ketiga (mencetak) diberikan pada karyawan pertama
    Pekerjaan keempat (menyaring) dan kelima (mencuci) diberikan pada karyawan ketiga
    Pekerjaan keenam (memotong) diberikan pada karyawan keempat
    NIlai energi didapatkan dengan menjumlahkan waktu yang diperlukan oleh masing-masing karyawan untuk melakukan pekerjaan tersebut. Dengan mengacu pada tabel waktu pekerjaan karyawan maka nilai energinya adalah: 5 + 7 + 5 + 11 + 7 + 9 = 44
    Tetapi terdapat kondisi tambahan bahwa apabila seorang pekerja melakukan pekerjaan berturutan maka pekerja tersebut membutuhkan waktu tambahan untuk beralih dari pekerjaan sebelumnya menuju pekerjaan berikutnya. Dalam contoh diatas karyawan pertama dan ketiga melakukan pekerjaan berurutan sebanyak 1 kali sehingga waktu pekerjaan bertambah sebanyak 5 * 2 = 10 menit. Dengan kata lain nilai energi akhir adalah 44 + 10 = 54.

    Selamat Pagi
    saya Athir
    admin bolehkah di contohkan perhitungannya dari awal satu iterasi saja?

    solusi yaitu 4 0 0 2 2 3 maksudnya gimana ya?
    kenapa mempunya arti begini?
    Pekerjaan pertama (menggoreng) diberikan pada karyawan kelima
    Pekerjaan kedua (merebus) dan ketiga (mencetak) diberikan pada karyawan pertama
    Pekerjaan keempat (menyaring) dan kelima (mencuci) diberikan pada karyawan ketiga
    Pekerjaan keenam (memotong) diberikan pada karyawan keempat ?

    mohon penjabarannya admin
    terima kasih

    • pip Penulis

      Jumlah karyawan ada 5 buah, tetapi dalam sistem perancangan skrip, indeks pertama tidak dimulai dari angka 1 melainkan dari angka 0. Sehingga solusi awal 4-0-0-2-2-3 berarti karyawan ke 5-1-1-3-3-4, yang jika dijabarkan dalam bentuk kalimat akan menghasilkan kesimpulan seperti yang saya tuliskan diatas.