Renforcer l'apprentissage Apprendre d'aujourd'hui

Désormais, vous voyagerez de Sapporo à Hokkaido à Naha à Okinawa. Avec apprentissage par renforcement.

Cette traversée du Japon a les deux objectifs suivants.

Et je voudrais appliquer les règles suivantes.

  • Une ville qui a été visitée une fois ne sera plus jamais visitée. </ b> Si vous faites une erreur et visitez la même ville deux fois, le jeu est terminé.

Ne devrions-nous pas utiliser la méthode de recherche graphique?

Oui c'est vrai. Il peut être facilement trouvé en utilisant la méthode de recherche graphique. Pour plus d'informations

S'il te plait regarde. Mais ici, le but est de commencer à apprendre à renforcer l'apprentissage à partir d'aujourd'hui.

Données de localisation du bureau de la préfecture du Japon

Utilisé dans Graph Theory Basics et Graph Theory Basics with matplotlib Animation Les données suivantes sont utilisées.

Latitude / longitude de la capitale préfectorale

Téléchargez les données de latitude / longitude de l'emplacement du bureau préfectoral.

import urllib.request
url = 'https://raw.githubusercontent.com/maskot1977/ipython_notebook/master/toydata/location.txt'
urllib.request.urlretrieve(url, 'location.txt') #Télécharger les données
('location.txt', <http.client.HTTPMessage at 0x110e78ba8>)

Chargez les données téléchargées.

import pandas as pd
location = pd.read_csv('location.txt').values
pd.DataFrame(location)
0 1 2
0 Sapporo 43.0642 141.347
1 Aomori 40.8244 140.74
2 Morioka 39.7036 141.153
3 Sendai 38.2689 140.872
... ... ... ...
44 Miyazaki 31.9111 131.424
45 Kagoshima 31.5603 130.558
46 Naha 26.2125 127.681

47 rows × 3 columns

Visualisons les données lues.

%matplotlib inline
import matplotlib.pyplot as plt
plt.figure(figsize=(11, 9))
plt.scatter(location[:, 2], location[:, 1])
for city, y, x in location:
    plt.text(x, y, city, alpha=0.5, size=12)
plt.grid()

output_4_1.png

Marcher entre les bureaux de la préfecture

Il existe des données sur Google Maps pour savoir combien d'heures il faut pour se déplacer entre les capitales préfectorales à pied (si vous ne pouvez pas vous déplacer à pied, vous devez utiliser un ferry). Téléchargez ceci.

url = 'https://raw.githubusercontent.com/maskot1977/ipython_notebook/master/toydata/walk.txt'
urllib.request.urlretrieve(url, 'walk.txt')
('walk.txt', <http.client.HTTPMessage at 0x1220b8a58>)

Chargez les données téléchargées.

walk = pd.read_csv('walk.txt', sep='\s+')
walk
Town1 Town2 Hour Ferry
0 Sapporo Aomori 55 True
1 Akita Aomori 36 NaN
2 Akita Sendai 45 NaN
3 Akita Niigata 52 NaN
... ... ... ... ...
96 Nagasaki Kumamoto 18 NaN
97 Nagasaki Saga 20 NaN
98 Kagoshima Naha 26 NaN

99 rows × 4 columns

cette? Je viens de remarquer que la section Kagoshima-Naha n'est pas un ferry ... eh bien, cela n'affecte pas cette analyse des données. Visualisons ici la relation entre les villes obtenue.

plt.figure(figsize=(11, 9))
for city, y, x in location:
    plt.text(x, y, city, alpha=0.4, size=8)
    
for w in walk.values:
    t1 = np.where(location[:, 0] == w[0])[0][0]
    t2 = np.where(location[:, 0] == w[1])[0][0]
    n1, y1, x1 = location[t1]
    n2, y2, x2 = location[t2]
    plt.plot([x1, x2], [y1, y2])
    
plt.scatter(location[:, 2], location[:, 1])
plt.grid()

output_12_0.png

La ville où se trouve ce bureau préfectoral s'appelle "top" </ b>, la ligne entre les villes s'appelle "side" </ b> et les sommets sont directement reliés par les côtés. Appelons-le adjacent </ b>. J'ai des données sur le temps de marche entre les villes, mais par souci de simplicité, j'utiliserai les informations sur les «côtés» dans l'analyse ultérieure, mais pas les données sur le temps de marche.

Matrice de distance entre les emplacements des bureaux préfectoraux

Trouvez la matrice de distance entre les bureaux préfectoraux à partir de la latitude et de la longitude des bureaux préfectoraux.

import numpy as np
from scipy.spatial import distance

dist_mat = distance.cdist(location[:, 1:], location[:, 1:], metric='euclidean') #Distance euclidienne

Créez une fonction pour visualiser la matrice avec une carte de couleurs.

import pandas as pd
def visualize_matrix(matrix):
    plt.figure(figsize=(12, 10))
    plt.imshow(matrix, interpolation='nearest', cmap=plt.cm.coolwarm)
    plt.colorbar()
    tick_marks = np.arange(len(matrix))
    plt.xticks(tick_marks, matrix.columns, rotation=90)
    plt.yticks(tick_marks, matrix.columns)
    plt.tight_layout()

Lorsque la matrice de distance obtenue est visualisée

visualize_matrix(pd.DataFrame(dist_mat, columns=location[:, 0]))

output_8_0.png

Cette matrice de distance est utilisée à deux fins dans cette analyse.

  • L'un est le calcul de la distance entre votre position actuelle et votre destination, Naha.
  • L'autre consiste à calculer la distance totale parcourue entre le point de départ de Sapporo et l'emplacement actuel.

Agent

Dans l'apprentissage intensif, le «cerveau» à apprendre est appelé «agent» </ b>. L'agent saisit les options d'action qui peuvent être prises et ajuste le poids du jugement de cette action par l'apprentissage.

Options d'action que vous pouvez prendre Theta

La variable thêta (θ, thêta) représentera les options d'action qui peuvent être prises à ce moment. En théorie des graphes, il représente un «côté» (la connexion entre les sommets). Calculons.

import numpy as np
theta_zero = np.full((len(location), len(location)), np.nan)

for w in walk.values:
    i = np.where(location[:, 0] == w[0])[0][0]
    j = np.where(location[:, 0] == w[1])[0][0]
    theta_zero[i, j] = 1
    theta_zero[j, i] = 1

Avec ce qui précède, le numéro de la ville adjacente à la ville $ i $ peut être obtenu par theta_zero [i].

Tarte des probabilités des actions à entreprendre

La variable pi (π, pi) représente la probabilité de l'action entreprise à ce moment-là. En théorie des graphes, il représente des "poids latéraux". Dans l'apprentissage amélioré, ce pi est appelé une " politique "</ b> et sera optimisé.

Tout d'abord, comme valeur initiale, considérons le cas où il y a plusieurs options et l'une d'elles est sélectionnée au hasard avec la même probabilité.

def normalize_pi(theta):
    [m, n] = theta.shape
    pi = np.zeros((m, n))
    for i in range(0, m):
        pi[i, :] = theta[i, :] / np.nansum(theta[i, :])
        
    return np.nan_to_num(pi)

De cette façon, la valeur initiale de pi`` pi_zero est obtenue.

pi_zero = normalize_pi(theta_zero)

Visualisons «pi_zero».

visualize_matrix(pd.DataFrame(pi_zero, columns=location[:, 0]))

output_19_0.png

Notez que «pi_zero» n'est pas une matrice symétrique. Par exemple, il y a un côté de Sapporo à Aomori et un côté d'Aomori à Sapporo, mais les poids ne sont pas les mêmes. En effet, dans ce graphique, il n'y a qu'une seule option de Sapporo à la ville voisine, mais il existe plusieurs options d'Aomori à la ville suivante.

À propos du "comportement" et de "l'état"

Dans l'apprentissage par renforcement, «comportement» et «état» sont traités séparément. À la suite de la sélection d'une certaine action dans un certain état, il passe à un état différent.

Les exemples traités dans cet article sont des cas particuliers où il n'est pas nécessaire de faire la distinction entre «comportement» et «état». En d'autres termes, «état» se réfère à la «ville à ce moment-là», «action» se réfère à la «ville suivante», et c'est le prochain «état». Le code est plus simple car vous n'avez pas à faire la distinction entre les actions et les états.

Marche aléatoire

Tout d'abord, essayons un voyage à travers le Japon avec cette politique pi encore pi_zero. Une fois que vous atteignez une ville, c'est une promenade aléatoire qui décide au hasard dans quelle ville aller.

Choisissez probablement l'action suivante

Créez une fonction qui sélectionne la ville suivante en fonction de la probabilité indiquée par la politique «pi».

def get_next(town, pi):
    return np.random.choice(range(len(pi)), p=pi[town, :])

Par exemple, selon «pi_zero», la prochaine ville de Tokyo (n ° 12) est calculée comme suit.

get_next(12, pi_zero)
13

Bien sûr, le résultat changera à chaque exécution car il est décidé au hasard.

Recherche par marche aléatoire

Maintenant, recherchons par marche aléatoire.

def explore(pi, start=0, goal=46): #Le départ est 0 (Sapporo), l'objectif est 46 (Naha)
    route = [start] #Liste pour mettre l'histoire de voyage
    town = start
    while True:
        next_town = get_next(town, pi) #Déterminez la prochaine ville
        if next_town in route: #Si vous visitez la même ville deux fois
            break #Jeu terminé

        route.append(next_town) #Ajouter la prochaine ville à l'histoire

        if next_town == goal: #Arriver au but
            break #Toutes nos félicitations
        else: #Pas encore un objectif
            town = next_town #Définir "ville suivante" comme "position actuelle"

    return route

Commencez une marche aléatoire selon pi_zero

route = explore(pi_zero)
route
[0, 1, 2, 3, 4, 5]

C'est aléatoire, donc bien sûr, le résultat changera à chaque exécution. S'il est difficile d'imaginer uniquement le numéro de la ville, il sera plus facile d'imaginer si vous le convertissez en nom de ville comme suit.

[location[i, 0] for i in route]
['Sapporo', 'Aomori', 'Morioka', 'Sendai', 'Akita', 'Yamagata']

Dans cet exemple, le jeu est terminé car j'ai marché de Sapporo à Yamagata et j'ai sélectionné par erreur une ville visitée à la destination suivante.

Au fait, pouvons-nous vraiment atteindre de Sapporo à Naha avec une promenade aussi aléatoire?

Index d'évaluation des résultats de recherche

Créons un moyen d'évaluer la qualité des résultats de recherche. Calculez la distance directe entre votre position actuelle et votre destination (Naha) et la distance totale parcourue entre votre emplacement de départ (Sapporo) et votre position actuelle.

def evaluate(route, goal=46):
    dist_goal = dist_mat[route[-1], goal]
    len_route = sum([dist_mat[route[i], route[i + 1]] for i in range(len(route) - 1)])
    return [dist_goal, len_route]

dist_goal est la" distance directe de votre position actuelle à votre destination (Naha) ", et len_route est la" distance totale de votre point de départ (Sapporo) à votre position actuelle ".

Ensuite, c'est un exemple d'exécution.

route = explore(pi_zero)
[location[i, 0] for i in route], evaluate(route)
(['Sapporo', 'Aomori'], [19.597025248636594, 2.3205099949149073])

Dans cet exemple, le jeu est terminé car j'ai choisi le chemin de Sapporo à Aomori et de retour d'Aomori à Sapporo. La distance entre l'emplacement actuel (Aomori) et la destination (Naha) est «19,597025248636594», et la distance entre le point de départ (Sapporo) et l'emplacement actuel (Aomori) est «2,3205099949149073».

Le but d'un voyage à travers le Japon est de trouver un itinéraire où ce dist_goal est nul, puis de trouver celui avec le plus petit len_route. Un len_route plus court n'est pas une bonne chose.

À partir de maintenant, je vais essayer le jeu de passer de Sapporo à Naha plusieurs fois, mais lorsque j'obtiens un certain résultat, créons une fonction pour juger si c'est la meilleure à ce jour.

best_dist_goal = 1000000 #Initialiser une valeur incroyablement élevée
best_len_route = 1000000 #Initialiser une valeur incroyablement élevée

def is_best_ever():
    if best_dist_goal >= dist_goal: #Meilleur dist_Si égal ou inférieur à la valeur de l'objectif
        if best_dist_goal > dist_goal: #Meilleur dist du passé_Si inférieur à la valeur de l'objectif
            return True #Le meilleur
        elif best_len_route > len_route: #Meilleur len du passé_S'il est inférieur à la valeur de l'itinéraire
            return True #Le meilleur
        else:
            return False #Pas le meilleur
    else:
        return False #Pas le meilleur

Exécution de la recherche

Maintenant que nous sommes prêts, nous allons répéter la recherche de marche aléatoire 50 000 fois.

%%time #Mesurer le temps d'exécution
pi = pi_zero.copy() #Initialisation de pi
theta = theta_zero.copy() #initialisation de theta

best_dist_goal = 1000000 #Initialiser une valeur incroyablement élevée
best_len_route = 1000000 #Initialiser une valeur incroyablement élevée

dist_goal_history0 = [] # dist_histoire du but
len_route_history0 = [] # len_historique de l'itinéraire
best_route0 = [] #Meilleur itinéraire

for itera in range(50000): #Répétez 50000 fois
    route = explore(pi) #chercher
    dist_goal, len_route = evaluate(route) #Évaluation
    dist_goal_history0.append(dist_goal) #Record
    len_route_history0.append(len_route) #Record
    
    if is_best_ever(): #Si le meilleur du passé
        best_dist_goal = dist_goal #Meilleur dist_goal
        best_len_route = len_route #Meilleur len_route
        best_route0 = route #Meilleur itinéraire
CPU times: user 10 s, sys: 118 ms, total: 10.2 s
Wall time: 11.8 s

Résultats de recherche

Créez une fonction pour visualiser le résultat. Tout d'abord, une fonction qui visualise la distribution du dist_goal`` len_route obtenu

def draw_histgrams(dist_goal_history, len_route_history):
    plt.figure(figsize=(max(len_route_history) / 4, max(dist_goal_history) / 4))
    x_max = max(dist_goal_history + len_route_history)
    ax = plt.subplot(2,1,1)
    ax.hist(dist_goal_history, label='dist_goal', bins=20)
    ax.set_xlim([0, x_max])
    ax.grid()
    ax.legend()
    ax = plt.subplot(2,1,2)
    ax.hist(len_route_history, label='len_route', bins=20)
    ax.set_xlim([0, x_max])
    ax.grid()
    ax.legend()
draw_histgrams(dist_goal_history0, len_route_history0)

output_35_0.png

En partant de Sapporo, il est difficile d'atteindre Naha. Si vous avez de la chance, vous pouvez y arriver. Vous pouvez voir qu'il existe de nombreux cas où le jeu est terminé au début de la recherche.

Ensuite, regardons la relation de dist_goal`` len_route.

def draw_scatter(dist_goal_history, len_route_history):
    plt.figure(figsize=(max(len_route_history) / 4, max(dist_goal_history) / 4))
    plt.scatter(len_route_history, dist_goal_history, alpha=0.5)
    plt.ylabel('dist_goal')
    plt.xlabel('len_route')
    plt.ylim([0, max(dist_goal_history) + 1])
    plt.xlim([0, max(len_route_history) + 1])
    plt.grid()
    plt.show()
draw_scatter(dist_goal_history0, len_route_history0)

output_37_0.png

Vous pouvez voir que nous n'avons pas atteint Naha, et même si le jeu est terminé au même endroit, il existe un large éventail de distances de voyage (différents itinéraires sont sélectionnés).

Ensuite, voyons comment dist_goal`` len_route a changé.

def visualize_history(history, interval=50, window=50):
    plt.plot(range(0, len(history), interval),  #Maximum global
             [np.array(history)[:i].max() for i in range(len(history)) if (i%interval) == 1], label='max')
    plt.plot(range(window, len(history)+window, interval), 
             [np.array(history)[i:i + window].mean() for i in range(len(history)) if (i%interval) == 1], 
             label='mean(recent)') #Moyenne des intervalles récents
    plt.plot(range(0, len(history), interval), 
             [np.array(history)[:i].mean() for i in range(len(history)) if (i%interval) == 1], label='mean') #Valeur moyenne globale
    plt.plot(range(0, len(history), interval), 
             [np.array(history)[:i].min() for i in range(len(history)) if (i%interval) == 1], label='min') #Minimum global
    plt.legend()
    plt.grid()
    plt.show()
visualize_history(dist_goal_history0)

output_39_0.png

dist_goal met parfois à jour la valeur minimale, mais elle n'atteint pas Naha. Et quel que soit le nombre de fois que vous répétez la recherche, la valeur moyenne ne s'améliorera pas. C'est naturel parce que je n'ai rien appris.

visualize_history(len_route_history0)

output_40_0.png

De même, len_route met parfois à jour la valeur maximale, mais elle n'atteint pas Naha, et la valeur moyenne ne s'améliore pas quel que soit le nombre de fois que la recherche est répétée. C'est naturel parce que je n'ai rien appris.

Enfin, affichons le meilleur itinéraire trouvé dans cette promenade aléatoire.

def draw_route(route):
    plt.figure(figsize=(11, 9))
    for i in route:
        plt.text(location[i, 2], location[i, 1], location[i, 0], alpha=0.4, size=12)
    plt.grid()
    plt.plot([location[i][2] for i in route], [location[i][1] for i in route])
    plt.ylabel('latitude')
    plt.xlabel('longitude')
    plt.show()
draw_route(best_route0)

output_42_0.png

J'ai essayé très fort, mais je n'ai pu atteindre que Saga. Si vous avez de la chance, vous pouvez atteindre Naha. Mais tu ne l'apprends pas.

Méthode du gradient de politique

Il est maintenant temps de commencer à renforcer l'apprentissage </ b>. La méthode d'apprentissage par renforcement semble être grossièrement divisée en Méthode de gradient de politique </ b> et Méthode d'itération de valeur </ b>. Commençons par la méthode du gradient de politique.

Mettre à jour la politique pi

L'itinéraire obtenu peut être évalué comme bon ou mauvais du point de vue de "la proximité du point final de l'itinéraire par rapport au but". Mettez à jour la politique pi de sorte que plus la distance par rapport à l'objectif est courte, plus vous avez de chances de choisir un avantage sur ce chemin pour une exploration future.

def update_pi(pi, route, goal=46, eta=0.1): #Eta (η),eta) est le taux d'apprentissage
    new_pi = pi.copy() #Copier le tableau numpy
    for i in range(len(route) - 1): #Pour chaque côté de l'itinéraire
        town1 = route[i] #Ville d'origine du côté i
        town2 = route[i + 1] #Ville au bout du côté i
        new_pi[town1, town2] +=  eta / (dist_mat[route[-1], goal] + 1)
        #Plus le point final de l'itinéraire est proche de l'objectif, plus le score est élevé
    
    return normalize_pi(new_pi) #Mettre à jour pi

La raison d'utiliser normalize_pi à la fin est d'ajuster la somme des valeurs de ligne à 1,0.

Exécution de la recherche

Maintenant, commençons la recherche.

%%time
pi = pi_zero.copy()

best_dist_goal = 1000000
best_len_route = 1000000

dist_goal_history1 = []
len_route_history1 = []
best_route1 = []
for itera in range(50000):
    route = explore(pi)
    dist_goal, len_route = evaluate(route)
    dist_goal_history1.append(dist_goal)
    len_route_history1.append(len_route)
        
    pi = update_pi(pi, route)
    
    if is_best_ever():
        best_dist_goal = dist_goal
        best_len_route = len_route
        best_route1 = route
CPU times: user 59.9 s, sys: 340 ms, total: 1min
Wall time: 1min 1s

Résultats de recherche

Voici un exemple des résultats. Les résultats varieront d'une exécution à l'autre et, dans certains cas, vous risquez de ne pas atteindre votre destination, Naha, même après 50 000 sessions d'apprentissage.

La distribution du dist_goal`` len_route résultant est très différente de la distribution par marche aléatoire. Le nombre d'arrivées à la destination Naha a augmenté de manière écrasante.

draw_histgrams(dist_goal_history1, len_route_history1)

output_46_0.png

La relation de dist_goal`` len_route est la suivante.

draw_scatter(dist_goal_history1, len_route_history1)

output_47_0.png

L'histoire de dist_goal. Il a atteint la destination Naha beaucoup plus tôt que la promenade aléatoire, et après cela, il est devenu plus facile d'atteindre la destination.

visualize_history(dist_goal_history1)

output_48_0.png

Ce sont les 5000 premières fois dans l'histoire de dist_goal.

visualize_history(dist_goal_history1[:5000])

output_49_0.png

De même, l'historique de len_route.

visualize_history(len_route_history1)

output_50_0.png

Ce sont les 5000 premières fois dans l'histoire de len_route.

visualize_history(len_route_history1[:5000])

output_51_0.png

Voici la sortie comme le meilleur itinéraire. Vous pouvez voir que celui le plus proche de l'itinéraire le plus court est sélectionné. Un seul est regrettable. Je vais à Kumamoto depuis Fukuoka via Saga. J'aurais dû me diriger directement de Fukuoka à Kumamoto sans passer par Saga.

draw_route(best_route1)

output_52_0.png

Enregistrez la politique résultante pi comme alias pi_pg.

pi_pg = pi.copy()

Visualisez cette politique pi_pg

visualize_matrix(pd.DataFrame(pi_pg, columns=location[:, 0]))

output_54_0.png

La route absolument importante est rouge. Par exemple, une fois arrivé à Kagoshima, il ne peut y avoir que Naha ensuite. Il est absolument inutile de sélectionner autre chose que cela (Kumamoto, Miyazaki). C'est une bonne représentation de cela.

Vous pouvez ainsi vérifier son évolution par rapport à la valeur initiale.

visualize_matrix(pd.DataFrame(pi_pg - pi_zero, columns=location[:, 0]))

output_55_0.png

Les endroits qui ne sont pas importants n'ont pas beaucoup changé. Par exemple, les régions de Shikoku et Kanto ne semblent pas être très importantes.

Méthode Epsilon-Greedy

Contrairement à la "méthode de gradient de politique" ci-dessus, la méthode Epsilon-Greedy introduite ici et l'apprentissage Q introduit ensuite sont appelés "Value Iteration Method" </ b>. ..

Dans la méthode d'itération de valeur, la politique semble être appelée "Q" au lieu de "π" pour une raison quelconque. Alors que «pi» commence par une probabilité égale parfaite, «Q» commence par une probabilité aléatoire non égale.

Politique Q

def generate_Q(theta): #Générez des probabilités aléatoires inégales à partir des choix que vous pouvez faire
    [m, n] = theta.shape
    Q = np.zeros((m, n))
    rand = np.random.rand(m, n)
    for i in range(m):
        for j in range(n):
            if theta[i, j] == 1:
                Q[i, j] = rand[i, j]
        
    return normalize_pi(Q)

Génère une valeur initiale Q_zero pour une politique non uniforme Q

Q_zero = generate_Q(theta_zero)

Visualisez le "Q_zero" généré.

visualize_matrix(pd.DataFrame(Q_zero, columns=location[:, 0]))

output_59_0.png

C'est la différence entre «Q_zero» et «pi».

visualize_matrix(pd.DataFrame(Q_zero - pi_zero, columns=location[:, 0]))

output_60_0.png

Comment choisir la prochaine action

Dans la méthode du gradient de politique, l'action suivante get_next a été sélectionnée au hasard selon la probabilité indiquée par la politique pi. Dans la méthode d'itération de valeur, l'action suivante get_next est réécrite comme suit.

def get_next(town, Q, epsilon=0.1):
    if np.random.rand() < epsilon:
        return np.random.choice(range(len(Q)), p=Q[town, :])
    else:
        return np.nanargmax(Q[town, :])

En d'autres termes, nous introduisons un nouveau paramètre «epsilon», qui provoque le cas où l'action est sélectionnée au hasard selon la probabilité indiquée par la politique «Q», et le cas où la politique «Q» sélectionne l'action avec la valeur maximale. Initialement, ʻepsilon` définit une valeur élevée. En d'autres termes, il existe de nombreuses possibilités de faire des choix aléatoires. Après cela, réduisez progressivement «epsilon» pour réduire le risque de faire des choix aléatoires.

Récompense

Nous avons également introduit le concept de récompense </ b>, et si vous atteignez votre objectif (lorsque vous atteignez l'objectif), vous obtenez 1 point, et si vous échouez (lorsque vous visitez la même ville deux fois et que le jeu est terminé) -1 Les points et la progression seront de 0 point.

Dans la méthode suivante appelée «sarsa», lors de la mise à jour de la valeur «Q» pour une certaine action (côté sur l'itinéraire), la valeur «Q» pour l'action suivante (côté suivant sur l'itinéraire) est également mentionnée. Je mettrai à jour. À ce stade, multipliez par le taux d'actualisation temporel «gamma».

def sarsa(town, Q, prev_t, next_t, reward, eta=0.1, gamma=0.9, goal=46):
    if reward == 1: #dist_mat[town, goal] == 0:
        Q[prev_t, town] = Q[prev_t, town] + eta * (reward - Q[prev_t, town])
    elif reward >= 0:
        Q[prev_t, town] = Q[prev_t, town] + eta * (reward - Q[prev_t, town] + gamma * Q[town, next_t])
    else:
        Q[prev_t, town] = Q[prev_t, town] - eta * Q[prev_t, town]
        
    return normalize_pi(Q)

En faisant cela, les récompenses gagnées sur la destination influenceront le choix des actions vers la destination. La «récompense négative» à la fin du jeu a également un effet négatif sur le choix des actions passées pour l'atteindre.

def explore_epsilon_greedy(Q, epsilon=0.1, eta=0.1, gamma=0.9, start=0, goal=46, min_epsilon=0.01):
    epsilon = max(epsilon, min_epsilon)
    route = [start]
    town = get_next(start, Q, epsilon)
    prev_t = start
    while True:
        if town in route:
            reward = -1
            Q = sarsa(town, Q, prev_t, next_t, reward, eta, gamma)
            break
        elif town == goal:
            reward = 1
            route.append(town)
            Q = sarsa(town, Q, prev_t, next_t, reward, eta, gamma)
            break
        else:
            reward = 0
            route.append(town)
            next_t = get_next(town, Q, epsilon)
            Q = sarsa(town, Q, prev_t, next_t, reward, eta, gamma)
            prev_t = town
            town = next_t
    
    return [route, Q]

Exécution de la recherche

Maintenant, commençons la recherche.

%%time
eta = 0.1 #Taux d'apprentissage
gamma = 0.9 #Taux d'actualisation du temps
epsilon = 0.5
Q = Q_zero.copy()

best_dist_goal = 1000000
best_len_route = 1000000

best_route2 = []
dist_goal_history2 = []
len_route_history2 = []
for itera in range(50000):
    epsilon = epsilon * 0.99
    route, Q = explore_epsilon_greedy(Q, epsilon, eta, gamma)
    dist_goal, len_route = evaluate(route)
    dist_goal_history2.append(dist_goal)
    len_route_history2.append(len_route)

    if is_best_ever():
        best_dist_goal = dist_goal
        best_len_route = len_route
        best_route2 = route
CPU times: user 7min 50s, sys: 948 ms, total: 7min 50s
Wall time: 7min 53s

Résultats de recherche

Voici un exemple des résultats de recherche par la méthode Epsilon-Greedy. En fait, les résultats ne sont pas très stables et peuvent changer un peu à chaque fois que vous les exécutez (essayez-le).

Premièrement, la distribution de dist_goal et len_route

draw_histgrams(dist_goal_history2, len_route_history2)

output_65_0.png

Relation entre dist_goal et len_route

draw_scatter(dist_goal_history2, len_route_history2) 

output_66_0.png

Histoire de dist_goal

L'augmentation du taux d'apprentissage «bêta» entraînera une convergence plus rapide, mais augmentera la probabilité de tomber dans une solution locale. Plus la valeur est petite, plus la convergence est lente, mais moins elle est susceptible de tomber dans une solution locale.

visualize_history(dist_goal_history2)

output_67_0.png

Les 5000 premières fois dans l'histoire de dist_goal

visualize_history(dist_goal_history2[:5000])

output_68_0.png

Histoire de len_route

visualize_history(len_route_history2)

output_69_0.png

Les 5000 premières fois dans l'histoire de len_route

visualize_history(len_route_history2[:5000])

output_70_0.png

Le parcours le plus court obtenu par la méthode Epsilon-Greedy

Encore une fois, le résultat était un peu différent du véritable itinéraire le plus court. Comparez avec les résultats obtenus par la méthode du gradient de politique.

draw_route(best_route2)

output_71_0.png

Dans la méthode du gradient de politique, la distance jusqu'à la destination Naha a été utilisée pour mettre à jour la valeur pi, afin d'apprendre un itinéraire qui satisfait simultanément" Objectif 1: Atteindre l'objectif "et" Objectif 2: Trouver l'itinéraire le plus court ". était en train de faire. Par conséquent, quel que soit le nombre de fois que vous l'exécutez, vous obtiendrez un résultat proche de l'itinéraire le plus court.

Dans cette méthode Epsilon-Greedy, la «récompense» donnée ne reflète que «si vous avez atteint l'objectif» et «si le jeu est terminé (avez-vous visité la même ville deux fois)». Par conséquent, nous allons apprendre comment «objectif 1: atteindre l'objectif», mais pas «objectif 2: trouver le chemin le plus court». Pour cette raison, il peut arriver qu'un résultat proche de l'itinéraire le plus court soit obtenu, mais en réalité, il converge souvent vers un résultat éloigné de l'itinéraire le plus court (essayez-le).

Réfléchissons à la façon de faire l'apprentissage pour "Objectif 2: Trouver le chemin le plus court" par la méthode Epsilon-Greedy (non couvert ici).

Enregistrez la valeur Q après l'entraînement avec la méthode Epsilon-Greedy comme Q_eg.

Q_eg = Q.copy()

Sa valeur est la suivante:

visualize_matrix(pd.DataFrame(Q_eg, columns=location[:, 0]))

output_73_0.png

Comparons-le avec le pi_pg obtenu par la méthode du gradient de politique.

Apprentissage Q

"Q-learning" </ b> est célèbre comme une autre méthode de méthode de répétition de valeur. C'est fondamentalement similaire à la méthode Epsilon-Greedy, avec la différence majeure étant qu'elle n'inclut pas le caractère aléatoire qui se produit lors du choix de la "prochaine action". On dit que la convergence sera plus rapide de ce montant.

Cependant, tant que j'exécute le code suivant plusieurs fois, la convergence peut être plus rapide, mais ce n'est pas toujours le cas, et je tombe souvent dans une solution locale (je n'arrive pas à atteindre la destination Naha). J'ai l'impression que ça finira.

def Q_learning(town, Q, prev_t, reward, eta=0.1, gamma=0.9, goal=46):
    if reward == 1: #dist_mat[town, goal] == 0:
        Q[prev_t, town] = Q[prev_t, town] + eta * (reward - Q[prev_t, town])
    elif reward >= 0:
        Q[prev_t, town] = Q[prev_t, town] + eta * (reward - Q[prev_t, town] + gamma * np.nanmax(Q[town, :]))
    else:
        Q[prev_t, town] = Q[prev_t, town] - eta * Q[prev_t, town]
        
    return normalize_pi(Q)
def explore_Q_learning(Q, epsilon=0.1, eta=0.1, gamma=0.9, start=0, goal=46):
    prev_t = start
    route = [start]
    town = get_next(start, Q, epsilon)
    while True:
        if town in route:
            reward = -1
            Q = Q_learning(town, Q, prev_t, reward, eta, gamma)
            break
        elif town == goal:
            reward = 1 
            route.append(town)
            Q = Q_learning(town, Q, prev_t, reward, eta, gamma)
            break
        else:
            reward = 0
            dist_goal, len_route = evaluate(route)
            if best_dist_goal > dist_goal:
                reward = 1
            route.append(town)
            next_t = get_next(town, Q, epsilon)
            Q = Q_learning(town, Q, prev_t, reward, eta, gamma)
            prev_t = town
            town = next_t
    
    return [route, Q]

Exécution de la recherche

%%time
eta = 0.1 #Taux d'apprentissage
gamma = 0.9 #Taux d'actualisation du temps
epsilon = 0.5
Q = Q_zero.copy()

best_dist_goal = 1000000
best_len_route = 1000000

best_route3 = []
dist_goal_history3 = []
len_route_history3 = []
for itera in range(50000):
    epsilon = epsilon * 0.99
    route, Q = explore_Q_learning(Q, epsilon, eta, gamma)
    dist_goal, len_route = evaluate(route)
    dist_goal_history3.append(dist_goal)
    len_route_history3.append(len_route)

    if is_best_ever():
        best_dist_goal = dist_goal
        best_len_route = len_route
        best_route3 = route
CPU times: user 9min 50s, sys: 1.41 s, total: 9min 52s
Wall time: 9min 54s

Résultats de recherche

Ceci est un exemple de résultats de recherche par Q learning. Comme avec la méthode Epsilon-Greedy, les résultats ne sont pas très stables et peuvent varier considérablement d'une exécution à l'autre (essayez-la).

Distribution de dist_goal et len_route

draw_histgrams(dist_goal_history3, len_route_history3)

output_81_0.png

Relation entre dist_goal et len_route

draw_scatter(dist_goal_history3, len_route_history3) 

output_82_0.png

Histoire de dist_goal

visualize_history(dist_goal_history3)

output_83_0.png

Les 5000 premières fois dans l'histoire de dist_goal

visualize_history(dist_goal_history3[:5000])

output_84_0.png

Histoire de len_route

visualize_history(len_route_history3)

output_85_0.png

Les 5000 premières fois dans l'histoire de len_route

visualize_history(len_route_history3[:5000])

output_86_0.png

Le chemin le plus court obtenu par Q learning

draw_route(best_route3)

output_87_0.png

Comme vous pouvez le voir clairement dans cet exemple, ce n'est pas le vrai chemin le plus court. La raison en est que, comme mentionné dans le cas de la méthode Epsilon-Greedy, en raison du problème de la conception «récompense», nous apprenons à «objectif 1: atteindre l'objectif», mais «objectif 2: trouver le chemin le plus court». C'est parce que nous n'avons pas appris pour.

De plus, comme mentionné ci-dessus, dans ma plage d'observation, l'apprentissage Q peut converger plus rapidement, mais dans de nombreux cas, il n'atteint pas la destination Naha même après avoir calculé 50000 fois. Je pense que «l'itinéraire le plus court obtenu par l'apprentissage Q» a tendance à être plus long que le «chemin le plus court obtenu par la méthode Epsilon-Greedy». La raison en est que le caractère aléatoire lors de la sélection de "l'action suivante" est supprimé, donc si vous atteignez l'objectif sur l'itinéraire sélectionné, même si l'itinéraire est long, il est possible de le changer Epsilon- Je pense que c'est parce que c'est moins que la méthode Greedy.

Q_qlearn = Q.copy()
visualize_matrix(pd.DataFrame(Q_qlearn, columns=location[:, 0]))

output_89_0.png

alors. C'est tout pour l'apprentissage par renforcement. Eh bien, Okinawa est loin.

Il y a Deep Strengthening Learning </ b> qui combine l'apprentissage profond avec cela, mais c'est une autre opportunité. Chao.

Recommended Posts