Algoritma Q-Learning 6

Algoritma Q-Learning adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur optimal dengan poin tertinggi.

Diasumsikan ada sebaran titik titik tidak beraturan dalam sebuah grafik
Tidak semua titik terhubung satu sama lain, melainkan hanya melalui jalur-jalur tertentu saja
Dan setiap jalur memiliki poin sendiri-sendiri
Tentukan Jalur optimal yang harus diambil dari titik awal ke titik tujuan dengan poin maksimal
Dalam kasus ini, diasumsikan hanya ada 6×6 = 36 titik, dengan jalur sbb
-1 = tidak memiliki jalur, 0 = ada jalur, dan 100 = ada jalur dan mendapat poin

Index setiap baris dan kolom dimulai dari angka 0, sehingga ada baris 0 sampai 5 dan kolom 0 sampai 5
Contoh1: matriks(1,3) bernilai 0, artinya terdapat jalur dari titik awal 1 ke titik tujuan 3 dengan poin 0
Contoh2: matriks(4,0) bernilai 0, artinya terdapat jalur dari titik awal 4 ke titik tujuan 0 dengan point 0
Contoh3: matriks(2,0) bernilai -1, artinya tidak terdapat jalur dari titik awal 2 ke titik tujuan 0
Contoh4: matriks(2,5) bernilai 100, artinya terdapat jalur dari titik awal 2 ke titik tujuan 5 dengan point 100

Langkah pertama adalah memasukkan data-data yang digunakan.
Tentukan ukuran Matriks Q
Diasumsikan dalam kasus ini, ukuran matriks adalah 6

Private Const UkuranMatriksQ As Integer = 6

Tentukan koefisien Gamma
Koefisien Gamma digunakan untuk perhitungan poin pada Matriks Q
Nilai koefisien gamma berkisar antara 0 sampai 1

Private Const KoefisienGamma As Double = 0.8

Tentukan Banyak iterasi yang digunakan dalam sekali proses
Semakin besar nilainya, semakin akurat hasilnya, tetapi semakin lama perhitungannya

Private Const n As Integer = 10

Tentukan urutan prioritas State Awal
Jadi perhitungan titik Matriks tidak dilakukan secara urut (0,1,2,3,4,5) tetapi mengikuti urutan state

Private StateAwal As Integer() = New Integer() {1, 3, 5, 2, 4, 0}

Tentukan Poin Hadiah (sesuai dengan tabel diatas)
-1 = tidak memiliki jalur, 0 = ada jalur, dan 100 = ada jalur dan mendapat poin.

Private Poin As Integer(,) = New Integer(,) {{-1, -1, -1, -1, 0, -1}, _
										  {-1, -1, -1, 0, -1, 100}, _
										  {-1, -1, -1, 0, -1, -1}, _
										  {-1, 0, 0, -1, 0, -1}, _
										  {0, -1, -1, 0, -1, 100}, _
										  {-1, 0, -1, -1, 0, 100}}

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan proses perulangan, dimulai dari State Awal (poin 1a – 1b)

For j As Integer = 0 To n - 1
	For i As Integer = 0 To UkuranMatriksQ - 1
		StateSekarang = StateAwal(i)
		. . .

1a. Lakukan pengecekan ke semua state sampai state tujuan tercapai.
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 1a1 – 1a2)

Do
	CekStateTujuan()
Loop Until StateSekarang = 5

Memasuki perhitungan pada fungsi CekStateTujuan

1a1. Cari State Acak berikutnya yang terhubung dengan State ini

Do While isValid = False
	KemungkinanStateBerikutnya = CInt(Int((UkuranMatriksQ * Rnd()) + 0))
	If Poin(StateSekarang, KemungkinanStateBerikutnya) > -1 Then
		isValid = True
	End If
Loop

1a2. Jika pada matriks poin dengan posisi (state sekarang, state acak) terdapat poin,
maka isi Matriks Q untuk posisi ini dengan Koefisien Gamma * nilai maksimum untuk state acak tersebut
Penjelasan lebih lanjut tentang fungsi NilaiMaks akan dijelaskan pada perhitungan dibawah ini (poin 1a2a – 1a2b)

If Poin(StateSekarang, KemungkinanStateBerikutnya) >= 0 Then
	Q(StateSekarang, KemungkinanStateBerikutnya) = CInt(Poin(StateSekarang, KemungkinanStateBerikutnya) + (KoefisienGamma * NilaiMaks(KemungkinanStateBerikutnya, False)))
	StateSekarang = KemungkinanStateBerikutnya
End If

Memasuki perhitungan pada fungsi NilaiMaks

1a2a. Pada Matriks Q untuk deret inputan State, cari nilai tertinggi pada matriks Q
Lakukan perulangan sampai tidak ditemukan lagi state dengan nilai yang lebih tinggi dari yang sekarang

Do Until isSelesai
	isDitemukanNilaiBaru = False
	For i = 0 To UkuranMatriksQ - 1
		If i <> nilaiTerbaik Then
			If Q(State, i) > Q(State, nilaiTerbaik) Then
				nilaiTerbaik = i
				isDitemukanNilaiBaru = True
			End If
		End If
	Next i

	If isDitemukanNilaiBaru = False Then
		isSelesai = True
	End If
Loop

1a2b. jika parameter isIndex adalah True, maka fungsi ini akan mengembalikan indeks dari State Tujuan pada matriks Q jika parameter isIndex adalah False, maka fungsi ini akan mengembalikan poin pada matriks Q itu sendiri

If isIndex = True Then
	NilaiMaks = nilaiTerbaik
Else
	NilaiMaks = Q(State, nilaiTerbaik)
End If

2. Lakukan perhitungan pada semua state sesuai dengan urutan state yang sudah ditentukan (poin 2a – 2c)

For i As Integer = 0 To UkuranMatriksQ - 1
	StateSekarang = StateAwal(i)
	. . .

2a. Lakukan perhitungan pencarian titik berikutnya sampai titik tujuan tercapai (poin 2a1 – 2a2)

Do
. . .
Loop Until StateSekarang = 5

2a1. Hitung nilai maksimal yang dapat diraih dari state yang terpilih
Penjelasan tentang fungsi NilaiMaks sudah dijelaskan pada perhitungan diatas.

stateBaru = NilaiMaks(StateSekarang, True)

2a2. Catat state yang paling baik untuk digunakan pada perhitungan selanjutnya

StateSekarang = stateBaru

Hasil akhir adalah: (klik untuk perbesar gambar)

* Penjelasan jawaban jalur optimal pada gambar tersebut
Contoh1: Lihat jawaban untuk jalur 3 (1, 5)
Pertama-tama, lihat matriks Q pada baris ke 3 (0, 398, 254, 0, 398, 0)
Nilai tertinggi pada baris tersebut adalah pada kolom 1 dan 4 (masing-masing bernilai 398)
Karena nilai urutan StateAwal adalah 1, 3, 5, 2, 4, 0, maka kolom 1 yang diambil
Kemudian lihat nilai matriks Q pada baris ke 1 (0, 0, 0, 318, 0, 498)
Nilai tertinggi pada baris tersebut adalah pada kolom 5 (498)
Karena state tujuan adalah 5 maka tujuan sudah tercapai, sehingga jawaban akhir adalah 1 dan 5

Contoh2: Lihat jawaban untuk jalur 0 (4, 5)
Pertama-tama, lihat matriks Q pada baris ke 0 (0, 0, 0, 0, 398, 0)
Nilai tertinggi pada baris tersebut adalah pada kolom 4 (398)
Kemudian lihat nilai matriks Q pada baris ke 4 (318, 0, 0, 318, 0, 498)
Nilai tertinggi pada baris tersebut adalah pada kolom 5 (498)
Karena state tujuan adalah 5 maka tujuan sudah tercapai, sehingga jawaban akhir adalah 4 dan 5

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.