Entfernungsmatrix zwischen Präfekturbüros

Finden Sie die Abstandsmatrix zwischen den Präfekturbüros anhand des Breiten- und Längengrads der Präfekturbüros.

import numpy as np
from scipy.spatial import distance

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

Erstellen Sie eine Funktion zur Visualisierung der Matrix mit einer Farbkarte.

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()

Wenn die erhaltene Distanzmatrix visualisiert wird

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

Diese Distanzmatrix wird in dieser Analyse für zwei Zwecke verwendet.

• Eine ist die Berechnung der Entfernung von Ihrem aktuellen Standort zu Ihrem Ziel, Naha.
• Die andere ist die Berechnung der Gesamtstrecke vom Startpunkt von Sapporo zum aktuellen Standort.

Agent

Beim intensiven Lernen wird das zu lernende "Gehirn" als "Agent" </ b> bezeichnet. Der Agent erfasst die Aktionsoptionen, die ergriffen werden können, und passt das Gewicht der Beurteilung dieser Aktion durch Lernen an.

Aktionsoptionen können Sie Theta nehmen

Die Variable Theta (θ, Theta) soll die Aktionsoptionen darstellen, die zu diesem Zeitpunkt ergriffen werden können. In der Graphentheorie repräsentiert es eine "Seite" (die Verbindung zwischen Eckpunkten). Berechnen wir.

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

Mit dem Obigen kann die Nummer der Stadt neben der Stadt $ i $ durch "theta_zero [i]" erhalten werden.

Wahrscheinlichkeitsteil der zu ergreifenden Maßnahmen

Die Variable pi (π, pi) soll die Wahrscheinlichkeit der zu diesem Zeitpunkt ergriffenen Maßnahme darstellen. In der Graphentheorie repräsentiert es "Seitengewichte". Beim erweiterten Lernen wird dieses "pi" als "Richtlinie" </ b> bezeichnet und optimiert.

Betrachten Sie zunächst als Anfangswert den Fall, in dem mehrere Optionen vorhanden sind und eine davon mit derselben Wahrscheinlichkeit zufällig ausgewählt wird.

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)

Auf diese Weise wird der Anfangswert von "pi" pi_zero erhalten.

pi_zero = normalize_pi(theta_zero)

Lassen Sie uns pi_zero visualisieren.

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

Beachten Sie, dass pi_zero keine symmetrische Matrix ist. Zum Beispiel gibt es eine Seite von Sapporo nach Aomori und eine Seite von Aomori nach Sapporo, aber die Gewichte sind nicht gleich. Dies liegt daran, dass es in dieser Grafik nur eine Option von Sapporo zur nächsten Stadt gibt, aber es gibt mehrere Optionen von Aomori zur nächsten Stadt.

Über "Verhalten" und "Zustand"

Beim verstärkten Lernen werden "Verhalten" und "Zustand" getrennt behandelt. Durch Auswahl einer bestimmten Aktion in einem bestimmten Zustand wechselt sie in einen anderen Zustand.

Die in diesem Artikel behandelten Beispiele sind Sonderfälle, in denen nicht zwischen "Verhalten" und "Zustand" unterschieden werden muss. Mit anderen Worten, "Staat" bezieht sich auf die "Stadt zu dieser Zeit", "Aktion" bezieht sich auf die "nächste Stadt" und das ist der nächste "Staat". Der Code ist einfacher, da Sie nicht zwischen Aktionen und Status unterscheiden müssen.

Zielloser Spaziergang

Versuchen wir zunächst eine Reise durch Japan mit dieser Richtlinie "pi" immer noch "pi_zero". Sobald Sie eine Stadt erreicht haben, ist es ein zufälliger Spaziergang, der zufällig entscheidet, in welche Stadt Sie als nächstes gehen möchten.

Wählen Sie wahrscheinlich die nächste Aktion

Erstellen Sie eine Funktion, die die nächste Stadt gemäß der in der Richtlinie pi angegebenen Wahrscheinlichkeit auswählt.

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

Zum Beispiel wird gemäß "pi_zero" die nächste Stadt in Tokio (Nr. 12) wie folgt berechnet.

get_next(12, pi_zero)

13

Natürlich ändert sich das Ergebnis bei jeder Ausführung, da es zufällig entschieden wird.

Suche durch zufälligen Spaziergang

Lassen Sie uns nun nach dem Zufallsprinzip suchen.

def explore(pi, start=0, goal=46): #Start ist 0 (Sapporo), Ziel ist 46 (Naha)
    route = [start] #Liste zum Einfügen des Reiseverlaufs
    town = start
    while True:
        next_town = get_next(town, pi) #Bestimmen Sie die nächste Stadt
        if next_town in route: #Wenn Sie dieselbe Stadt zweimal besuchen
            break #Spiel ist aus

        route.append(next_town) #Fügen Sie der Geschichte die nächste Stadt hinzu

        if next_town == goal: #Am Ziel ankommen
            break #Herzliche Glückwünsche
        else: #Noch kein Ziel
            town = next_town #Stellen Sie "nächste Stadt" als "aktuelle Position" ein

    return route

Starten Sie einen zufälligen Spaziergang gemäß pi_zero

route = explore(pi_zero)
route

[0, 1, 2, 3, 4, 5]

Es ist zufällig, daher ändert sich das Ergebnis natürlich mit jedem Lauf. Wenn es schwierig ist, sich nur die Städtenummer vorzustellen, ist es einfacher, sich vorzustellen, wenn Sie sie wie folgt in den Städtenamen konvertieren.

[location[i, 0] for i in route]

['Sapporo', 'Aomori', 'Morioka', 'Sendai', 'Akita', 'Yamagata']

In diesem Beispiel ist das Spiel beendet, weil ich von Sapporo nach Yamagata gelaufen bin und fälschlicherweise eine besuchte Stadt am nächsten Ziel ausgewählt habe.

Können wir mit einem so zufälligen Spaziergang wirklich von Sapporo nach Naha gelangen?

Bewertungsindex der Suchergebnisse

Lassen Sie uns einen Weg finden, um die Qualität der Suchergebnisse zu bewerten. Berechnen Sie die direkte Entfernung von Ihrem aktuellen Standort zu Ihrem Ziel (Naha) und die Gesamtentfernung von Ihrem Abflugort (Sapporo) zu Ihrem aktuellen Standort.

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" ist die "direkte Entfernung von Ihrem aktuellen Standort zu Ihrem Ziel (Naha)" und "len_route" ist die "Gesamtreiseentfernung von Ihrem Abflugort (Sapporo) zu Ihrem aktuellen Standort".

Dann ist es ein Ausführungsbeispiel.

route = explore(pi_zero)
[location[i, 0] for i in route], evaluate(route)

(['Sapporo', 'Aomori'], [19.597025248636594, 2.3205099949149073])

In diesem Beispiel ist das Spiel vorbei, weil ich den Weg von Sapporo nach Aomori und zurück von Aomori nach Sapporo gewählt habe. Die Entfernung vom aktuellen Standort (Aomori) zum Ziel (Naha) beträgt "19.597025248636594", und die Entfernung vom Abfahrtsort (Sapporo) zum aktuellen Standort (Aomori) beträgt "2.3205099949149073".

Das Ziel einer Reise durch Japan ist es, eine Route zu finden, bei der dieses "dist_goal" Null ist, und dann die mit der kleinsten "len_route" zu finden. Kürzere len_route ist keine gute Sache.

Von nun an werde ich das Spiel des Wechsels von Sapporo nach Naha viele Male versuchen, aber wenn ich ein bestimmtes Ergebnis erhalte, erstellen wir eine Funktion, um zu beurteilen, ob es das bisher beste ist.

best_dist_goal = 1000000 #Initialisieren Sie einen unglaublich großen Wert
best_len_route = 1000000 #Initialisieren Sie einen unglaublich großen Wert

def is_best_ever():
    if best_dist_goal >= dist_goal: #Beste dist_Wenn gleich oder kleiner als der Zielwert
        if best_dist_goal > dist_goal: #Best dist der Vergangenheit_Wenn weniger als der Zielwert
            return True #Das Beste überhaupt
        elif best_len_route > len_route: #Beste Länge der Vergangenheit_Wenn es kleiner als der Routenwert ist
            return True #Das Beste überhaupt
        else:
            return False #Nicht das beste
    else:
        return False #Nicht das beste

Suchausführung

Jetzt, da wir bereit sind, wiederholen wir die Suche nach zufälligen Spaziergängen 50.000 Mal.

%%time #Ausführungszeit messen
pi = pi_zero.copy() #Initialisierung von pi
theta = theta_zero.copy() #Initialisierung von Theta

best_dist_goal = 1000000 #Initialisieren Sie einen unglaublich großen Wert
best_len_route = 1000000 #Initialisieren Sie einen unglaublich großen Wert

dist_goal_history0 = [] # dist_Geschichte des Ziels
len_route_history0 = [] # len_Routenverlauf
best_route0 = [] #Beste Route

for itera in range(50000): #50.000 Mal wiederholen
    route = explore(pi) #Suche
    dist_goal, len_route = evaluate(route) #Auswertung
    dist_goal_history0.append(dist_goal) #Aufzeichnung
    len_route_history0.append(len_route) #Aufzeichnung
    
    if is_best_ever(): #Wenn das Beste aus der Vergangenheit
        best_dist_goal = dist_goal #Beste dist_goal
        best_len_route = len_route #Beste len_route
        best_route0 = route #Beste Route

CPU times: user 10 s, sys: 118 ms, total: 10.2 s
Wall time: 11.8 s

Suchergebnisse

Erstellen Sie eine Funktion zur Visualisierung des Ergebnisses. Erstens eine Funktion, die die Verteilung des erhaltenen "dist_goal" "len_route" visualisiert

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)

Von Sapporo aus ist es schwierig, Naha zu erreichen. Wenn Sie Glück haben, können Sie dorthin gelangen. Sie können sehen, dass es viele Fälle gibt, in denen das Spiel zu Beginn der Suche beendet ist.

Als nächstes schauen wir uns die Beziehung von dist_goal`` len_route an.

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)

Sie können sehen, dass wir Naha nicht erreicht haben, und selbst wenn das Spiel am selben Ort beendet ist, gibt es eine Vielzahl von Entfernungen (verschiedene Routen werden ausgewählt).

Als nächstes wollen wir sehen, wie sich dist_goal`` len_route geändert hat.

def visualize_history(history, interval=50, window=50):
    plt.plot(range(0, len(history), interval),  #Gesamtmaximum
             [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)') #Durchschnitt der letzten Intervallzeiten
    plt.plot(range(0, len(history), interval), 
             [np.array(history)[:i].mean() for i in range(len(history)) if (i%interval) == 1], label='mean') #Gesamtdurchschnittswert
    plt.plot(range(0, len(history), interval), 
             [np.array(history)[:i].min() for i in range(len(history)) if (i%interval) == 1], label='min') #Gesamtminimum
    plt.legend()
    plt.grid()
    plt.show()

visualize_history(dist_goal_history0)

dist_goal aktualisiert manchmal den Mindestwert, erreicht aber Naha nicht. Unabhängig davon, wie oft Sie die Suche wiederholen, wird sich der Durchschnittswert nicht verbessern. Es ist natürlich, weil ich nichts gelernt habe.

visualize_history(len_route_history0)

In ähnlicher Weise aktualisiert "len_route" manchmal den Maximalwert, erreicht jedoch nicht Naha und der Durchschnittswert verbessert sich nicht, unabhängig davon, wie oft die Suche wiederholt wird. Es ist natürlich, weil ich nichts gelernt habe.

Lassen Sie uns abschließend die beste Route anzeigen, die in diesem zufälligen Spaziergang gefunden wurde.

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)

Ich habe mich sehr bemüht, aber ich konnte nur Saga erreichen. Wenn Sie Glück haben, können Sie Naha erreichen. Aber du lernst es nicht.

Richtliniengradientenmethode

Jetzt ist es Zeit, das Lernen zu stärken </ b>. Die Methode des verstärkenden Lernens scheint grob in die Richtliniengradientenmethode </ b> und die Wertiterationsmethode </ b> unterteilt zu sein. Lassen Sie uns zunächst die Policy-Gradient-Methode ausführen.

def update_pi(pi, route, goal=46, eta=0.1): #Eta (η),eta) ist die Lernrate
    new_pi = pi.copy() #Numpy-Array kopieren
    for i in range(len(route) - 1): #Für jede Seite der Route
        town1 = route[i] #Herkunftsort der Seite i
        town2 = route[i + 1] #Stadt am Ende der Seite i
        new_pi[town1, town2] +=  eta / (dist_mat[route[-1], goal] + 1)
        #Je näher der Endpunkt der Route am Ziel liegt, desto höher ist die Punktzahl
    
    return normalize_pi(new_pi) #Aktualisiere pi

%%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

draw_histgrams(dist_goal_history1, len_route_history1)

draw_scatter(dist_goal_history1, len_route_history1)

visualize_history(dist_goal_history1)

visualize_history(dist_goal_history1[:5000])

visualize_history(len_route_history1)

visualize_history(len_route_history1[:5000])

draw_route(best_route1)

pi_pg = pi.copy()

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

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

def generate_Q(theta): #Generieren Sie ungleiche Zufallswahrscheinlichkeiten aus den Auswahlmöglichkeiten, die Sie treffen können
    [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)

Q_zero = generate_Q(theta_zero)

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

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

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, :])

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)

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]

%%time
eta = 0.1 #Lernrate
gamma = 0.9 #Zeitabzinsungssatz
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

draw_histgrams(dist_goal_history2, len_route_history2)

draw_scatter(dist_goal_history2, len_route_history2) 

visualize_history(dist_goal_history2)

visualize_history(dist_goal_history2[:5000])

visualize_history(len_route_history2)

visualize_history(len_route_history2[:5000])

draw_route(best_route2)

Q_eg = Q.copy()

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

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]

%%time
eta = 0.1 #Lernrate
gamma = 0.9 #Zeitabzinsungssatz
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

draw_histgrams(dist_goal_history3, len_route_history3)

draw_scatter(dist_goal_history3, len_route_history3) 

visualize_history(dist_goal_history3)

visualize_history(dist_goal_history3[:5000])

visualize_history(len_route_history3)

visualize_history(len_route_history3[:5000])

draw_route(best_route3)

Q_qlearn = Q.copy()

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