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

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.