[PYTHON] Löse dein eigenes Labyrinth mit DQN
Löse dein eigenes Labyrinth mit DQN
Ich habe versucht, mein eigenes Labyrinth mit Deep Q Network (sogenanntes DQN) zu lösen.
Das Programm ist da. https://github.com/shibuiwilliam/maze_solver
Überblick
DQN ist eine Art des Verstärkungslernens, bei dem ein neuronales Netzwerk verwendet wird, um die optimale Strategie auszuwählen. Das Folgende ist eine Referenz zur Erklärung des Verstärkungslernens und des neuronalen Netzwerks.
- Stärkung des Lernens Stärkung des Lernens von null auf tief - Qiita
- neurales Netzwerk Erfahren Sie mehr über die Prinzipien der künstlichen Intelligenz im TensorFlow-Tutorial-Qiita
Reinforcement Learning ist eine Technologie, die in Spielen und in der Robotersteuerung verwendet wird. Wenn jedoch ein Spieler (auch ein Agent) eine Aktion gegen eine Situation (Status) ausführt, ändert sich die Situation und die Belohnung für diese Aktion (Belohnung). ) Ist ein Modell zu bekommen. Wiederholen von Aktionen für Situationen Spieler versuchen, die Belohnungen zu maximieren.
Dieses Mal werde ich mein eigenes Labyrinth für die Situation verwenden. Das Labyrinth wird automatisch vom Programm generiert, sieht aber so aus.
Bei 10x10 ist S der Startpunkt und 50 das Ziel. Es ist von einer Wand (#) umgeben und nur Kacheln (-1, 0) mit internen Nummern können passieren. Auch innerhalb der Wand können mit # gekennzeichnete Kacheln nicht passieren. Die Zahlen auf den Kacheln sind Punkte (Belohnungen für verbessertes Lernen). -1 ist 1 Punkt minus, 0 Punkt ist unverändert und das Ziel ist 50 Punkte. Die Spieler wollen die Punkte maximieren und das Ziel erreichen.
Dieses Mal haben wir die folgenden drei Logiken implementiert, damit der Spieler das Ziel erreicht.
- A-Stern-Algorithmus
- Q-Learning
- Deep Q-network（DQN）
Der Umriss von jedem ist wie folgt.
A-Stern-Algorithmus
Die Erklärung für den A-Stern-Algorithmus ist hier sehr einfach zu verstehen. Durchsuche das Labyrinth mit Python <Antworterklärung> - Leicht mysteriös. A* - Wikipedia
Einfach ausgedrückt wird die Entfernung vom Startpunkt zum aktuellen Standort und vom aktuellen Standort zum Ziel gemessen und die Route mit der kürzesten Entfernung ausgewählt. Im Labyrinth wird jede Entfernung als euklidische Entfernung berechnet.
Es ist eine Gleichung, die im Satz von Pitagolas (Satz von drei Quadraten) erscheint.
Unter Verwendung des A-Stern-Algorithmus wird die kürzeste Entfernung priorisiert, um das Labyrinth zu lösen. Es gibt kein Konzept für Punkte oder Belohnungen. Daher ist im Labyrinth dieser Regel die Belohnung tendenziell niedrig, während das Labyrinth schnell gelöst wird.
Hier ist der Weg vom Start zum Ziel, wenn Sie ihn mit A-Stern lösen. Die Route, die ich genommen habe, ist blau.
Ich werde die kürzeste Strecke in dem Labyrinth zurücklegen, das ich dieses Mal benutzt habe, aber die Belohnung ist mit 44 Punkten niedrig. -1 oder was auch immer, streben Sie die kürzeste Entfernung an.
Q-learning Als nächstes kommt das Q-Lernen. [Q learning-Wikipedia](https://ja.wikipedia.org/wiki/Q learning) Stärkung des Lernens ab Python - Qiita
Q-Lernen ist eine Allzweckmethode, die für andere Zwecke als die Labyrinthsuche verwendet werden kann. Es ist eine Art maschinelles Lernen, und ein Modell wird erstellt, indem die Situation und das eigene Verhalten als Trainingsdaten und die Belohnung als Zielvariable verwendet werden. Erstellen Sie ein Vorhersagemodell der Belohnungen für Maßnahmen, die je nach Situation ergriffen werden. Die Belohnungsprognose wird nach folgender Formel berechnet.
$ Q (s, a) $ ist der erwartete Wert der Belohnung für die Ausführung der Aktion $ a $ in der Situation $ s $. $ α $ ist die Lernrate und $ γ $ ist der Belohnungsabzinsungssatz. $ Q (s ', a') $ ist der erwartete Wert der Belohnung für die Ausführung der Aktion $ a '$ in der nächsten Situation $ s' $ der Situation $ s $. Nehmen Sie den maximal erwarteten Wert von $ Q (s ', a') $ mit $ max $ und multiplizieren Sie ihn mit dem Abzinsungssatz von $ γ $. $ r $ ist die Belohnung für die Ausführung der Aktion $ a $ in der Situation $ s $.
Das Merkmal des Q-Lernens besteht darin, dass durch wiederholte Berechnung dieser Formel der erwartete Belohnungswert $ Q (s, a) $ und der erwartete Wert $ r + γmaxQ (s ', a') $ näher gebracht werden (als Ergebnis $ Q). (s, a) ← Q (s, a) + 0 $ konvergieren). Beim Q-Lernen erhalten Sie zunächst eine Kombination aus Zustand, Aktion und Belohnung, indem Sie diese ausreichend oft wiederholen. Mit dieser Eingabe wird die obige Formel wiederholt berechnet, um den erwarteten Wert der Belohnung $ Q (s, a) $ abzuleiten, der der tatsächlichen Situation entspricht.
Q-Learning zielt darauf ab, die Belohnungen zu maximieren. In diesem Labyrinth ist das Ziel die maximale Belohnung. Wenn Sie also das Labyrinth mit Q-Lernen lösen, gelangen Sie schnell zum Ziel, während Sie die -1-Kachel meiden. So sieht es aus.
Gehen Sie so weit wie möglich durch die 0-Kacheln und erreichen Sie das Ziel in kürzester Entfernung. Die Belohnung beträgt 48,0, was höher als der A-Stern ist.
DQN DQN ist eine Kombination aus Q-Learning und Deep Learning. Wir werden ein neuronales Netzwerk mit der Situation $ s $ und der Aktion $ a $ als Eingangsvariablen und $ r + γmaxQ (s ', a') $ aufbauen, die beim Q-Lernen als Zielvariablen erscheinen. Aktion $ a, die die Belohnung $ r $ für den Zustand $ s $ maximiert, indem $ r + γmaxQ (s ', a') $ von $ s $, $ a $ angenähert und Fehler minimiert werden Es wird derjenige sein, der $ ableitet.
DQN unterscheidet sich von einem normalen neuronalen Netzwerk dadurch, dass das Programm Lehrerdaten für überwachtes Lernen generiert. Lehrerdaten werden zum Erlernen des neuronalen Netzwerks benötigt, aber in DQN werden die Aktion $ a $ für den Staat $ s $ und seine Belohnung $ r $ durch tatsächliches Handeln akkumuliert. Bei Eingabevariablen und Zielvariablen wird die Kombination von $ s $, $ a $ und $ r $ durch Wiederholen der Aktion aufgezeichnet, und das Lernen wird basierend auf dem über einem bestimmten Niveau angesammelten Speicher durchgeführt. Es heißt Experience Replay, lernt aber aus der Kombination von $ s $, $ a $, $ r $, erstellt ein Vorhersagemodell und wiederholt die Aktion auf $ s $, $ a $, $ Der Fluss besteht darin, die Kombination von r $ zu erhalten und das Vorhersagemodell zu modifizieren. Dies ist ein Artikel, der sich für Experience Replay einsetzt. https://pdfs.semanticscholar.org/9cd8/193a66cf53143cbba6ccb0c7b9c2ebf2452b.pdf Diese Erklärung ist auf Japanisch leicht zu verstehen. Geschichte von DQN + Deep Q-Network in Chainer - Qiita Ich werde einen Teil zitieren:
Eingabe: Daten $ D $ bestehend aus vielen Stichproben ($ s $, $ a $, $ r $, $ s '$) Ausgabe: Q-Funktion nach dem Training von $ Q_ {\ theta_N} (s, a) $
k=0 - Initialisieren Sie den neuronalen Netzwerkparameter $ \ theta_0 $
- Wiederholen: Wiederholen Sie $ N-1 $ mal
- Extrahieren Sie $ M $ Samples aus den Daten $ D $
- Basierend auf $ M $ Samples Lehrersignal $ {\ rm {Ziel}} ^ t = r_t + \ gamma \ max_ {a '} Q_ {\ theta_k} (s_t', a ') $ und Erstellen Sie die Eingabe $ (s_t, a_t) $ ($ t = 1,2, ..., M $)
- Basierend auf dem erstellten Lehrersignal $ {\ rm {target}} ^ t $ und geben Sie $ (s_t, a_t) $ ein Minimieren Sie den Fehler $ L_ \ theta $ zwischen $ Q_ \ theta (s, a) $ und dem Lehrersignal durch eine Gradientenmethode Machen. Wenn das Lernen konvergiert und bestimmte Bedingungen erfüllt sind, ist das Ergebnis $ \ theta_ {k + 1} $
- $ k \ leftarrow k + 1 $
- Gibt $ Q_ {\ theta_N} (s, a) $ zurück
Das neuronale Netzwerk ist in Keras geschrieben. Das Modell sieht so aus.
Nur DQN wird das Programm tragen. Das vollständige Programm finden Sie hier. https://github.com/shibuiwilliam/maze_solver
Unten sind die Agenten. Es besteht aus einem neuronalen Netzwerkmodell, einem Speicher zum Speichern von Zuständen / Aktionen / Belohnungen, einer Aktionsauswahl und einer Erfahrungswiedergabe. Die Klassenvariable "epsilon" ist die Wahrscheinlichkeit, zufällige Aktionen auszuführen. Dieser Wert nimmt mit fortschreitendem Training mit "e_decay" ab. "e_min" ist der Mindestwert für "epsilon". Schließlich werden Sie sich gemäß dem Vorhersagemodell optimal verhalten, aber zunächst werden Sie sich zufällig verhalten und eine Stichprobe erstellen.
class DQN_Solver:
def __init__(self, state_size, action_size):
self.state_size = state_size # list size of state
self.action_size = action_size # list size of action
self.memory = deque(maxlen=100000) # memory space
self.gamma = 0.9 # discount rate
self.epsilon = 1.0 # randomness of choosing random action or the best one
self.e_decay = 0.9999 # epsilon decay rate
self.e_min = 0.01 # minimum rate of epsilon
self.learning_rate = 0.0001 # learning rate of neural network
self.model = self.build_model() # model
self.model.summary() # model summary
# model for neural network
def build_model(self):
model = Sequential()
model.add(Dense(128, input_shape=(2,2), activation='tanh'))
model.add(Flatten())
model.add(Dense(128, activation='tanh'))
model.add(Dense(128, activation='tanh'))
model.add(Dense(1, activation='linear'))
model.compile(loss="mse", optimizer=RMSprop(lr=self.learning_rate))
return model
# remember state, action, its reward, next state and next possible action. done means boolean for goal
def remember_memory(self, state, action, reward, next_state, next_movables, done):
self.memory.append((state, action, reward, next_state, next_movables, done))
# choosing action depending on epsilon
def choose_action(self, state, movables):
if self.epsilon >= random.random():
# randomly choosing action
return random.choice(movables)
else:
# choosing the best action from model.predict()
return self.choose_best_action(state, movables)
# choose the best action to maximize reward expectation
def choose_best_action(self, state, movables):
best_actions = []
max_act_value = -100
for a in movables:
np_action = np.array([[state, a]])
act_value = self.model.predict(np_action)
if act_value > max_act_value:
best_actions = [a,]
max_act_value = act_value
elif act_value == max_act_value:
best_actions.append(a)
return random.choice(best_actions)
# this experience replay is going to train the model from memorized states, actions and rewards
def replay_experience(self, batch_size):
batch_size = min(batch_size, len(self.memory))
minibatch = random.sample(self.memory, batch_size)
X = []
Y = []
for i in range(batch_size):
state, action, reward, next_state, next_movables, done = minibatch[i]
input_action = [state, action]
if done:
target_f = reward
else:
next_rewards = []
for i in next_movables:
np_next_s_a = np.array([[next_state, i]])
next_rewards.append(self.model.predict(np_next_s_a))
np_n_r_max = np.amax(np.array(next_rewards))
target_f = reward + self.gamma * np_n_r_max
X.append(input_action)
Y.append(target_f)
np_X = np.array(X)
np_Y = np.array([Y]).T
self.model.fit(np_X, np_Y, epochs=1, verbose=0)
if self.epsilon > self.e_min:
self.epsilon *= self.e_decay
In Experience Replay werden der aktuelle Status, das Verhalten, die Belohnung und der nächste Status, das optimale Verhalten und die Belohnung zum Lernen an das neuronale Netzwerk übergeben. Nähert sich dem erwarteten Wert für das aktuelle Verhalten.
Dies ist Modelltraining. "Episoden" ist die Anzahl der Trainings und "Zeiten" ist die Anzahl der Samples (Suchvorgänge) in einer Episode. Probenahme → Training wird 1000 x 20000 Mal wiederholt. Wenn Sie jedoch mitten in der Probenahme das Ziel erreichen, wird die Probenahme unterbrochen.
Passen Sie die Anzahl der Proben und Schulungen an die Werte von "epsilon" und "e_decay" an. Wenn die Abtastung ("Zeiten") niedrig ist, gibt es nicht genügend Abtastdaten, die wiedergegeben werden können, und wenn die Anzahl der Trainings ("Episoden") niedrig ist, trainiert das neuronale Netzwerk das Modell nicht. Der "epsilon" -Wert nimmt mit jeder "Episode" ab. Wenn dieser Wert also nicht gemäß "e_decay" klein genug ist, verhält er sich während der Stichprobe und des Modells weiterhin zufällig, egal wie gut das Modell ist. Nicht beurteilbar.
Der Wert dieser Seite wird entsprechend der Größe des Labyrinths angepasst. Wenn es 10x10 ist, könnte ein Modell mit diesem numerischen Wert generiert werden. Wenn die Größe jedoch groß ist, endet das Training, bevor die Anzahl der Stichproben ausreicht, und es wird ein voreingenommenes Modell erstellt.
# train the model
state_size = 2
action_size = 2
dql_solver = DQN_Solver(state_size, action_size)
# number of episodes to run training
episodes = 20000
# number of times to sample the combination of state, action and reward
times = 1000
for e in range(episodes):
state = start_point
score = 0
for time in range(times):
movables = maze_field.get_actions(state)
action = dql_solver.choose_action(state, movables)
reward, done = maze_field.get_val(action)
score = score + reward
next_state = action
next_movables = maze_field.get_actions(next_state)
dql_solver.remember_memory(state, action, reward, next_state, next_movables, done)
if done or time == (times - 1):
if e % 500 == 0:
print("episode: {}/{}, score: {}, e: {:.2} \t @ {}"
.format(e, episodes, score, dql_solver.epsilon, time))
break
state = next_state
# run experience replay after sampling the state, action and reward for defined times
dql_solver.replay_experience(32)
Nachfolgend finden Sie die Ergebnisse des Trainings. Es wird alle 500 Folgen ausgegeben. Punktzahl ist die Belohnung für die Episode, e ist epsilon und @ ist die Anzahl der Proben. Eine kleine Anzahl von @ bedeutet, dass Sie mitten in der Stichprobe punkten.
episode: 0/20000, score: 5.0, e: 1.0 @ 100
episode: 500/20000, score: 19.0, e: 0.95 @ 86
episode: 1000/20000, score: 14.0, e: 0.9 @ 82
episode: 1500/20000, score: 24.0, e: 0.86 @ 56
episode: 2000/20000, score: -9.0, e: 0.82 @ 138
episode: 2500/20000, score: 26.0, e: 0.78 @ 76
episode: 3000/20000, score: 20.0, e: 0.74 @ 84
episode: 3500/20000, score: 42.0, e: 0.7 @ 24
episode: 4000/20000, score: 44.0, e: 0.67 @ 22
episode: 4500/20000, score: 45.0, e: 0.64 @ 24
episode: 5000/20000, score: 46.0, e: 0.61 @ 36
episode: 5500/20000, score: 33.0, e: 0.58 @ 32
episode: 6000/20000, score: 43.0, e: 0.55 @ 32
episode: 6500/20000, score: 48.0, e: 0.52 @ 24
episode: 7000/20000, score: 38.0, e: 0.5 @ 34
episode: 7500/20000, score: 45.0, e: 0.47 @ 28
episode: 8000/20000, score: 43.0, e: 0.45 @ 42
episode: 8500/20000, score: 43.0, e: 0.43 @ 24
episode: 9000/20000, score: 45.0, e: 0.41 @ 28
episode: 9500/20000, score: 45.0, e: 0.39 @ 28
episode: 10000/20000, score: 48.0, e: 0.37 @ 20
episode: 10500/20000, score: 44.0, e: 0.35 @ 22
episode: 11000/20000, score: 46.0, e: 0.33 @ 24
episode: 11500/20000, score: 45.0, e: 0.32 @ 22
episode: 12000/20000, score: 48.0, e: 0.3 @ 26
episode: 12500/20000, score: 45.0, e: 0.29 @ 18
episode: 13000/20000, score: 47.0, e: 0.27 @ 18
episode: 13500/20000, score: 41.0, e: 0.26 @ 24
episode: 14000/20000, score: 47.0, e: 0.25 @ 16
episode: 14500/20000, score: 47.0, e: 0.23 @ 14
episode: 15000/20000, score: 47.0, e: 0.22 @ 14
episode: 15500/20000, score: 48.0, e: 0.21 @ 14
episode: 16000/20000, score: 46.0, e: 0.2 @ 18
episode: 16500/20000, score: 44.0, e: 0.19 @ 20
episode: 17000/20000, score: 48.0, e: 0.18 @ 14
episode: 17500/20000, score: 45.0, e: 0.17 @ 20
episode: 18000/20000, score: 48.0, e: 0.17 @ 18
episode: 18500/20000, score: 48.0, e: 0.16 @ 20
episode: 19000/20000, score: 46.0, e: 0.15 @ 18
episode: 19500/20000, score: 48.0, e: 0.14 @ 16
Wenn sich die Episode wiederholt, steigt die Punktzahl, Epsilon fällt ab und die Anzahl der Proben nimmt ab. Sie können sehen, dass es zu einem guten Modell zusammengefasst wird.
Ich werde versuchen, das Labyrinth mit dem Modell zu lösen, das ich gemacht habe.
# try the model
state = start_point
score = 0
steps = 0
while True:
steps += 1
movables = maze_field.get_actions(state)
action = dql_solver.choose_best_action(state, movables)
print("current state: {0} -> action: {1} ".format(state, action))
reward, done = maze_field.get_val(action)
maze_field.display(state)
score = score + reward
state = action
print("current step: {0} \t score: {1}\n".format(steps, score))
if done:
maze_field.display(action)
print("goal!")
break
Das Ergebnis ist das gleiche wie beim Q-Lernen. Was sie suchen, ist dasselbe, und ich frage mich, ob es ein Labyrinth dieser Größe gibt.
abschließend
Ich wollte DQN berühren und verglich dann die Labyrinth-Suchalgorithmen. Es war gut, dass DQN funktioniert hat und es hat Spaß gemacht. Der schwierigste Teil war das Schreiben eines Labyrinthprogramms, das mit beiden Algorithmen verwendet werden kann, aber manchmal habe ich immer noch unlösbare Labyrinthe (Ziele werden durch Wände blockiert), aber ich bin müde, daher werde ich die Korrektur verschieben. tat. Außerdem dauert es einige Zeit, um die DQN-Parameter anzupassen. Ich überprüfe es gerade in einem 20x20-Labyrinth, also lade ich es erneut hoch, wenn dies abgeschlossen ist.
Recommended Posts