Algoritma Q-Learning 4


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

-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

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

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

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

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

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


Langkah-langkah penggunaan algoritma ini adalah

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

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)

Memasuki perhitungan pada fungsi CekStateTujuan

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

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)

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

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

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

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

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


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd13a

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


Tinggalkan sebuah komentar

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

4 pemikiran di “Algoritma Q-Learning