Optimisasi Flow Pada Gudang Menggunakan Q-Learning – Part 3

by

Setelah mempelajari teori pada modul sebelumnya, kita akan implementasikan dalam Python.

Untuk development Anda bisa menggunakan Anaconda, namun lebih disarankan menggunakan Google Colabs karena semua library sudah disediakan.

Pertama import library yang digunakan.

import numpy as np

Setting parameter yang digunakan.

gamma = 0.75
alpha = 0.9

Langkah selanjutnya adalah mendefinisikan environment yang terdiri dari state, action dan rewards.

location_to_state = {'A': 0,
                     'B': 1,
                     'C': 2,
                     'D': 3,
                     'E': 4,
                     'F': 5,
                     'G': 6,
                     'H': 7,
                     'I': 8,
                     'J': 9,
                     'K': 10,
                     'L': 11
                     }

actions = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

R = np.array([[0,1,0,0,0,0,0,0,0,0,0,0],
              [1,0,1,0,0,1,0,0,0,0,0,0],
              [0,1,0,0,0,0,1,0,0,0,0,0],
              [0,0,0,0,0,0,0,1,0,0,0,0],
              [0,0,0,0,0,0,0,0,1,0,0,0],
              [0,1,0,0,0,0,0,0,0,1,0,0],
              [0,0,1,0,0,0,1000,1,0,0,0,0],
              [0,0,0,1,0,0,1,0,0,0,0,1],
              [0,0,0,0,1,0,0,0,0,1,0,0],
              [0,0,0,0,0,1,0,0,1,0,1,0],
              [0,0,0,0,0,0,0,0,0,1,0,1],
              [0,0,0,0,0,0,0,1,0,0,1,0]])

Berikutnya kita implementasikan Q-Learning.

Pertama inisialisasi Q-Values, dengan membuat matrix of Q-Values dengan nilai 0.

Dimana rows menunjukan current states st, columns menunjukan actions pada state berikutnya st+1, dan cells akan berisi nilai Q-Values Q(st, at)

Q = np.array(np.zeros([12,12]))

Kemudian kita implementasikan Q-Learning process, Setiap t ≥ 1 , lakukan for loop 1000 iterations untuk menjalankan kode berikut

  1. memilih random state st dari 12 kemungkinan.
  2. Jalankan random action untuk menuju ke state berikutnya dengan memeriksa R(st, at) > 0.
  3. Ketika sampai pada state berikutnya st+1 kita mendapatkan reward R(st, at)
  4. Kemudian hitung Temporal Difference TDt(st, at)
  5. Update Q-value menggunakan Bellman Equation:
    Qt(st, at) = Qt−1(st, at) + αTDt(st, at)
for i in range(1000):
  current_state = np.random.randint(0,12)
  playable_actions = []
  for j in range(12):
    if R[current_state, j] > 0:
      playable_actions.append(j)
  next_state = np.random.choice(playable_actions)
  TD = R[current_state, next_state] + gamma*Q[next_state, np.argmax(Q[next_state,])] - Q[current_state, next_state]
  Q[current_state, next_state] = Q[current_state, next_state] + alpha*TD

Anda dapat mendapatkan code berikut untuk melihat isi Q-Values

print("Q-Values:")
print(Q.astype(int))

Berikut hasil yang akan ditampilkan. Nilai bisa sedikit berbeda antara tutorial dan code Anda, namun lokasi nilai akan sama.

Q-Values:
[[   0 1688    0    0    0    0    0    0    0    0    0    0]
 [1267    0 2249    0    0 1266    0    0    0    0    0    0]
 [   0 1688    0    0    0    0 3000    0    0    0    0    0]
 [   0    0    0    0    0    0    0 2251    0    0    0    0]
 [   0    0    0    0    0    0    0    0  714    0    0    0]
 [   0 1688    0    0    0    0    0    0    0  951    0    0]
 [   0    0 2249    0    0    0 3998 2249    0    0    0    0]
 [   0    0    0 1689    0    0 3000    0    0    0    0 1688]
 [   0    0    0    0  536    0    0    0    0  951    0    0]
 [   0    0    0    0    0 1266    0    0  714    0 1266    0]
 [   0    0    0    0    0    0    0    0    0  951    0 1688]
 [   0    0    0    0    0    0    0 2250    0    0 1267    0]]

Langkah berikutnya adalah membuat fungsi untuk mencari optimal route.

Pertama kita perlu lakukan mapping data lokasi, karena fungsi akan menerima huruf untuk menunjukan lokasi.

Untuk menjelaskan fungsi route, kita gunakan contoh mencari route dari lokasi E ke lokasi G:

  1. Inisialisasi lokasi start, dalam hal ini lokasi E.
  2. Ambil informasi state dari lokasi E, dengan melihat variable location_to_state mapping s0 = 4.
  3. Pada row dari index s0 = 4 pada matrix Q-Values, kita dapatkan maximum Q-Value (703).
  4. Kolom ini memiliki index 8, jadi action berikutnya adalah index 8 yang akan membawa kita ke state berikutnya st+1 = 8.
  5. Ambil lokasi dari state 8 menggunakan variable state_to_location mapping, yaitu lokasi I. Tambahkan informasi ini pada list yang akan berisi optimal path.
  6. Ulangi 5 langkah diatas dari starting location baru yaitu I, sampai kita sampai di lokasi tujuan akhir yaitu G.

Karena tidak diketahui ada berapa lokasi dari lokasi start ke lokasi akhir, kita harus lakukan looping ke 5 langkah diatas, dan berhenti ketika sudah sampai di lokasi akhir

state_to_location = {state: location for location, state in location_to_state.items()}

def route(starting_location, ending_location):
  route = [starting_location]
  next_location = starting_location
  while (next_location != ending_location):
    starting_state = location_to_state[starting_location]
    next_state = np.argmax(Q[starting_state,])
    next_location = state_to_location[next_state]
    route.append(next_location)
    starting_location = next_location
  return route

Jika kita panggil fungsi diatas dengan memasukan argument starting location dan ending location.

print("Route:")
route('E', 'G')

Akan mengembalikan optimal route seperti berikut

Route:
['E', 'I', 'J', 'K', 'L', 'H', 'G']

Berikut isi code lengkapnya

import numpy as np

gamma = 0.75
alpha = 0.9

location_to_state = {'A': 0,
                     'B': 1,
                     'C': 2,
                     'D': 3,
                     'E': 4,
                     'F': 5,
                     'G': 6,
                     'H': 7,
                     'I': 8,
                     'J': 9,
                     'K': 10,
                     'L': 11
                     }

actions = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

R = np.array([[0,1,0,0,0,0,0,0,0,0,0,0],
              [1,0,1,0,0,1,0,0,0,0,0,0],
              [0,1,0,0,0,0,1,0,0,0,0,0],
              [0,0,0,0,0,0,0,1,0,0,0,0],
              [0,0,0,0,0,0,0,0,1,0,0,0],
              [0,1,0,0,0,0,0,0,0,1,0,0],
              [0,0,1,0,0,0,1000,1,0,0,0,0],
              [0,0,0,1,0,0,1,0,0,0,0,1],
              [0,0,0,0,1,0,0,0,0,1,0,0],
              [0,0,0,0,0,1,0,0,1,0,1,0],
              [0,0,0,0,0,0,0,0,0,1,0,1],
              [0,0,0,0,0,0,0,1,0,0,1,0]])

Q = np.array(np.zeros([12,12]))

for i in range(1000):
  current_state = np.random.randint(0,12)
  playable_actions = []
  for j in range(12):
    if R[current_state, j] > 0:
      playable_actions.append(j)
  next_state = np.random.choice(playable_actions)
  TD = R[current_state, next_state] + gamma*Q[next_state, np.argmax(Q[next_state,])] - Q[current_state, next_state]
  Q[current_state, next_state] = Q[current_state, next_state] + alpha*TD

state_to_location = {state: location for location, state in location_to_state.items()}

def route(starting_location, ending_location):
  route = [starting_location]
  next_location = starting_location
  while (next_location != ending_location):
    starting_state = location_to_state[starting_location]
    next_state = np.argmax(Q[starting_state,])
    next_location = state_to_location[next_state]
    route.append(next_location)
    starting_location = next_location
  return route


print("Route:")
route('E', 'G')

Anda juga bisa mengakses file Google Colab dari program diatas di https://colab.research.google.com/drive/1LbBnDu6XMF1KQHXrpCfHZIyoUpvbIzh_?usp=sharing

Kode diatas masih sederhana, hanya menentukan route terpendek dari satu lokasi ke lokasi lainnya.

Masih dapat dikembangkan misalnya, terdapat sistem tambahan yang memiliki list prioritas pengambilan barang. Dalam proses pencarian route terpendek, AI dapat membandingkan apakah lebih baik route terpendek, atau memilih route yang sedikit lebih jauh, namun melewati prioritas lebih rendah berikutnya.

Silakan bereksperimen.

Sharing is caring:

Leave a Comment