Dieser Artikel ist der 13. Tag von Furukawa Lab Advent_calendar. Dieser Artikel wurde von einem Studenten des Furukawa Lab als Teil seines Lernens geschrieben. Der Inhalt kann mehrdeutig sein oder der Ausdruck kann leicht abweichen.

Einführung

Hallo zusammen Kennen Sie das Problem der reisenden Verkäufer? Es ist eine Art häufiges Problem bei der Kombinationsoptimierung, aber in diesem Artikel möchte ich über einen traurigen Fall schreiben, als ich versuchte, das Problem des reisenden Verkäufers richtig zu lösen. Zunächst ist der Rundungsfehler beängstigend. Da es eine Geschichte war, als ich Anfänger im Programm war, hoffe ich, dass Sie sie mit einer geringen Hürde in allem lesen können.

Patrouillenverkäufer Problem

Zunächst möchte ich das Problem der reisenden Verkäufer erläutern. Das Problem der reisenden Verkäufer ist "das Problem, die kürzeste Entfernung zu finden, um zum Ausgangspunkt zurückzukehren, nachdem alle Städte einmal durchquert wurden". In Anbetracht der vier Städte A, B, C und D, wie in der folgenden Abbildung gezeigt, ist die kürzeste Entfernung wie folgt. In diesem Fall ist die Anzahl der Städte gering und die Anordnung einfach, sodass die kürzeste Entfernung sofort gefunden werden kann. Wenn jedoch die Anzahl der Städte etwas zunimmt, ist die kürzeste Entfernung nicht auf einen Blick erkennbar.

Tatsächlich ist die Anzahl der Kombinationen der Besuchsreihenfolge von Städten (Anzahl von Städten-1)! Wenn es sich also um 30 Städte oder 40 Städte handelt, gibt es eine große Anzahl von Besuchsaufträgen, so dass es sehr schwierig ist, alle Besuchsaufträge zu überprüfen. Ist schwierig, nicht wahr? Daher habe ich versucht, dieses Problem der Kombinationsoptimierung angemessen zu lösen, um eine gute Lösung zu finden.

SA-Methode

Die orthodoxste Allzweckmethode zur Lösung von Kombinationsoptimierungsproblemen ist die SA-Methode (Simulated-an-Earing). Übersetzt ins Japanische ist es eine Grillmethode. Die Glühmethode setzt die Energiefunktion $ E $. Die Energiefunktion ist in diesem Fall die Gesamtentfernung, die alle Städte umrundet und zum Ausgangspunkt zurückkehrt. Wir werden die Reihenfolge der Besuche in den Städten ändern, damit sich diese Gesamtentfernung verringert.

In diesem Fall ist der Gesamtabstand länger als vor dem Austausch. Daher möchte ich diese Ersetzung ablehnen, aber bei der SA-Methode wird die Ersetzung auch dann übernommen, wenn die Entfernung mit der in der folgenden Formel angegebenen Wahrscheinlichkeit lang wird.

p=\exp \left\{-\frac{1}{T}\left(E_{t+1}-E_{t}\right)\right\}

Hier ist $ T $ in der Formel ein Parameter namens Temperatur, der als Rauschen wirkt. Je größer $ T $ ist, desto einfacher ist es, Ersatz zu übernehmen. Wenn der Abstand infolge des Ersetzens kleiner wird, wird er mit einer Wahrscheinlichkeit von 1 übernommen. Diese Methode wird als Metropolenmethode bezeichnet.

Um den bisherigen Ablauf zusammenzufassen

Ändern Sie die Reihenfolge der Besuche
Entscheiden Sie, ob Sie die Metropolis-Methode ersetzen möchten Wiederholen Sie dies danach für die Anzahl der Städte und machen Sie einen Schritt. Es wird sein.

Darüber hinaus wird bei der SA-Methode die Temperatur $ T $ gemäß der Anzahl der Schritte durch die folgende Formel allmählich verringert.

T_{t+1}=\alpha T_{t}

Außerdem nimmt $ \ alpha $ den Wert $ 0 <\ alpha <1 $ als Indikator dafür, wie schnell die Temperatur sinkt.

Wenn Sie die Temperatur auf diese Weise senken, ist es wahrscheinlicher, dass ein Austausch erfolgt, wenn die Anzahl der Schritte gering ist, und ein Austausch ist weniger wahrscheinlich, wenn die Anzahl der Schritte groß ist, dh am Ende des Spiels. Dann kann die erste Person aussteigen, selbst wenn sie in eine lokale Lösung fällt, und die letzte Person wird aktualisiert, damit sie genau entscheiden kann. Dies ist darauf zurückzuführen, dass die Festigkeit von Stahl erhöht wird, indem beim Schmieden von einer hohen Temperatur ausgegangen wird und dieser allmählich abgekühlt wird, weshalb er als Backmethode bezeichnet wird. Diese Methode ist sehr vielseitig bei Kombinationsoptimierungsproblemen.

Algorithmus Rebellion

Nun, hier wollte ich reden. Ich habe versucht, das Problem des Handlungsreisenden mit der oben genannten Bräunungsmethode zu lösen. Der Algorithmus selbst ist einfach, so dass ich ihn sofort erstellen konnte. Deshalb habe ich versucht, es mit einem sehr einfachen Stadtlayout zu testen. Das einfachste Stadtlayout ist wahrscheinlich kreisförmig.

Dieses Mal möchte ich über die Prämisse dieses Stadtlayouts sprechen. Übrigens ist als Überprüfung das Verfahren der Backmethode

Ändern Sie die Reihenfolge der Besuche
Entscheiden Sie, ob Sie die Metropolis-Methode ersetzen möchten Wiederholen Sie dies danach für die Anzahl der Städte und machen Sie einen Schritt. Es war. Lassen Sie uns zunächst die Reihenfolge der Besuche in der Stadt ändern. Der Anfangswert wird als geeignete Zufallszahl angegeben.

Sie sehen auf einen Blick, dass dies nicht der kürzeste Weg ist. Als nächstes entscheiden wir uns für die Stadt, die ersetzt werden soll. Dies wird auch durch Zufallszahlen entschieden, aber zu dieser Zeit verwendete ich die Sprache C, also durch Multiplizieren der gleichmäßigen Verteilung, die den Wert von $ 0 <x <1 $ ausgibt, mit der Anzahl der Städte $ N $ (int-Typ), $ 0 Ich habe eine Zufallszahl vom Typ int von <x <N-1 $ generiert. Dies war die Ursache der Rebellion.

Eine Simulation wurde unter Verwendung einer Zufallszahl durchgeführt, die diese selbst erstellte Ganzzahl ausgibt. Anfangs war die Anzahl der Schritte ungefähr 100, aber es funktioniert gut genug. Es wurde 600 Mal ersetzt. Aber eines Tages passierte ein Vorfall. Ich beschloss, 10000 Schritte (60.000-maliges Ersetzen) zufällig zu versuchen, und drehte die Simulation um. Ich habe dieses Ergebnis. Ich fand es seltsam. Ich dachte, etwas stimmte nicht, als der Gesamtabstand unter dem theoretischen Wert ausgegeben wurde, der durch manuelle Berechnung der Koordinaten erhalten wurde. Das ist natürlich, weil ** die Stadt verschwunden ist **. Darüber hinaus ist dieses Ergebnis nicht reproduzierbar und eine Stadt verschwindet, zwei Städte verschwinden und nichts verschwindet. Wenn Sie an das Programmieren gewöhnt sind, denken Sie vielleicht sofort, dass "das Ergebnis nicht reproduzierbar ist = die Zufallszahl ist schlecht", aber zu diesem Zeitpunkt habe ich angefangen und bin in meinem Kopf stecken geblieben. Am Ende der Geschichte hatte ich sogar eine Täuschung wie ein bestimmtes Skynet und sagte: "Beurteilt der Algorithmus nicht, dass die Stadt verschwinden sollte, um die kürzeste Entfernung zu erreichen?"

Ochi

Wie einige von Ihnen vielleicht bemerkt haben, war die Ursache, dass 1 selbst aufgrund des Rundungsfehlers in dem Teil ausgegeben wurde, der eine einheitliche Zufallszahl von $ 0 <x <1 $ ausgibt. Wenn 1 ausgegeben wird, wird es durch die N-te Stadt ersetzt. Da das c-Spracharray von 0 gezählt wird, wird das Array von 0 bis N-1 vorbereitet, sodass das N-te Array nicht existiert. Durch den Erwerb und die Ersetzung von nichts verschwand die Stadt.

SOM und reisender Verkäufer Problem

Ab diesem Zeitpunkt wird es eine ganz andere Geschichte sein, aber kürzlich habe ich das Problem der reisenden Verkäufer erneut versucht, daher möchte ich die Ergebnisse dort veröffentlichen. Dieses Mal habe ich versucht, das Problem des Handlungsreisenden mit SOM zu lösen. SOM sind sehr einfach Beobachtungsdaten $ \ mathbf {Y} = (\ mathbf {y} _1, \ mathbf {y} _2, ... \ mathbf {y} _N) \ in \ mathbb {R} ^ {D × N} $ und latente Variablen

$ \ mathbf {X} = (\ mathbf {x} _1, \ mathbf {x} _2, ... \ mathbf {x} _K) \ in \ mathbb {R} ^ {M × K} $ So schätzen Sie die Zuordnung $ \ mathbf {f}: \ mathbb {R} ^ {M} → \ mathbb {R} ^ {D} $

Für den detaillierten Algorithmus gibt es Dokument, das von einem Professor in unserem Labor geschrieben wurde. Ich bin glücklich. Wenn Sie beispielsweise 3D-Daten und latenten 2D-Raum angeben, erhalten Sie ein solches Ergebnis.

Die Abbildung links zeigt die Beobachtungsdaten und die Abbildung, und die Abbildung rechts zeigt den latenten Raum.

Bei zweidimensionalen Daten und eindimensionalem latenten Raum wird ein solches Ergebnis erzeugt. Klicken Sie hier für ein Bild mit dem Endergebnis ああああああ.gif

Die angegebenen Daten sind übrigens die Koordinatendaten von 48 Städten in den USA mit der Bezeichnung att48. Es ist irgendwie bedauerlich. Ich habe das Gefühl, dass ich es schaffen kann. Der Engpass hierbei ist, dass Start- und Endpunkt nicht miteinander verbunden sind. Wenn Sie das können, sind Sie fertig. Daher werde ich eine latente Variable angeben, die den Startpunkt und den Endpunkt verbindet. Ja, wir platzieren latente Variablen in einem Kreis auf dem latenten Raum. Hier ist der Quellcode und das Ausführungsergebnis von SOM mit kreisförmigen latenten Variablen.

from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
import numpy as np
from numpy.random import*
import matplotlib.animation as anm
import math
import random

%matplotlib nbagg
fig = plt.figure(1,figsize=(6, 4))
ax1 = fig.add_subplot(121)
ax2 = fig.add_subplot(122)
class som():
    def __init__(self,N,K,sigmin,sigmax,r,w,zeta):
        self.N = N
        self.K = K
        self.sigmin = sigmin
        self.sigmax = sigmax
        self.r = r
        self.w = w
        self.zeta = zeta
        self.hist =[]
        self.hist2 = []
        self.hist3 = []
        self.sigma=0
    def fit(self,T):
        for i in range(T):
            #print(i)
            if i==0 :
                self.kn=np.random.randint(self.K,size=(self.N))
            #if i%10 == 0 :
            #    self.sigma = self.sigma+0.5
            self.sigma=max(self.sigmax-(i/self.r)*(self.sigmax-self.sigmin),self.sigmin)
            #print(self.kn.shape)
            self.test = (self.zeta[self.kn][None,:,:]-self.zeta[:,None,:])**2
            #print("self,test=",self.test.shape)
            #print("self,zeta=",self.zeta[self.kn][None,:,:].shape)
            #print("self,zeta=",self.zeta[:,None,:].shape)
            self.h_kn= np.exp(-1/(2*self.sigma**2)*np.sum((self.zeta[self.kn][None,:,:]-self.zeta[:,None,:])**2,axis=2))
            #print(self.h_kn)
            self.g_k = np.sum(self.h_kn,axis=1)
            self.y_test =(1/(self.g_k[:,None]))*self.h_kn @ self.w 
            #print("y_test:{}",self.y_test.shape)
            self.kn= np.argmin(np.sum((self.w[:,None,:]-self.y_test[None,:,:])**2,axis=2),axis=1)
            self.X1=np.reshape(self.y_test,(K,2))
            self.hist.append(self.X1)
            self.hist2.append(self.kn)
            self.hist3.append(self.sigma)
            print(self.sigma)
        print(np.array(self.hist).shape)
        return self.hist,self.hist2,self.hist3
            #self.hist.setdefault('y',[]).append(self.y_test) 
            #self.hist.setdefault('k',[]).append(self.kn) 
    #def history(self):
        #return self.hist
a=0.1
c=-0.1
N=48#Die Anzahl der Daten
D=2#Anzahl der Dimensionen von Daten
L=1#Anzahl der Dimensionen des latenten Raums
K=300#Anzahl der Knoten
T=100
zeta=np.zeros((K,2))
distance = 0
sigmax=5.0#Anfangswert von Sigma
sigmin=0.01#Mindestwert von Sigma
latent_space=np.random.normal
r=T-5#Neigung
rad = np.linspace(-np.pi, np.pi, K)
zetax = np.sin(rad)+1
zetay = np.cos(rad)+1
zeta[:,0] = zetax
zeta[:,1] =zetay
train_data = np.loadtxt('att48.txt')
w = np.reshape(train_data,(48,D))
i=0
SOM = som(N,K,sigmin,sigmax,r,w,zeta)
kekka,k,sigma = SOM.fit(T)
kekka = np.array(kekka)
k = np.array(k)
sigma = np.array(sigma)
#print(k.shape)
for i in range(K):
    #print(("x1",kekka[T-1,i,0]))
    #print(("x2",kekka[T-1,i+1,0]))
    #print(("y1",kekka[T-1,i,1]))
    #print(("y2",kekka[T-1,i+1,1]))
    #print(("x_delta",kekka[T-1,i,0]-kekka[T-1,i+1,0]))
    #print(("y_delta",kekka[T-1,i,1]-kekka[T-1,i+1,1]))
    if(i==K-1):
        distance += np.sqrt(abs(kekka[T-1,i,0]-kekka[T-1,0,0])**2+abs(kekka[T-1,i,1]-kekka[T-1,0,1])**2)
    else:
        distance += np.sqrt(abs(kekka[T-1,i,0]-kekka[T-1,i+1,0])**2+abs(kekka[T-1,i,1]-kekka[T-1,i+1,1])**2)
    #print("delta",np.sqrt(abs(kekka[T-1,i,0]-kekka[T-1,i+1,0])**2+abs(kekka[T-1,i,1]-kekka[T-1,i+1,1])**2))
    print(distance)
#print(kekka.shape)
def update(i, zeta,w):
#for i in range(T):
    print(i)
    ax1.cla()
    ax2.cla()
    ax1.scatter(w[:,0],w[:,1],s=100,color='r')
    ax1.scatter(kekka[i,:,0],kekka[i,:,1],color = 'k',marker = '*')
    ax1.plot(kekka[i,:,0],kekka[i,:,1],color='k')
    ax1.plot(kekka[i,:,0].T,kekka[i,:,1].T,color='k')
    ax2.scatter(zeta[k[i,:]][:,0],zeta[k[i,:]][:,1],c=w[:,0])
    ax1.set_xlabel("X_axis")
    ax1.set_ylabel("Y_axis")
    ax2.set_title('latentspace')
    ax2.set_xlabel("X_axis")
    ax2.set_ylabel("Y_axis")

ani = anm.FuncAnimation(fig, update, fargs = (zeta,w), interval = 100, frames = T-1,repeat = False)


ani.save("RSom_TSP_Node300.gif", writer = 'imagemagick')

Wenn es sich um ein GIF handelt, verschwindet das Endergebnis sofort, sodass ich auch ein Bild vorbereite. es ist hier

Es fühlt sich wirklich gut an. Die Berechnungszeit ist schnell, also denke ich, dass es eine ziemlich gute Linie ist. Danach denke ich, dass es noch besser ist, wenn wir durch Hinzufügen von Rauschen aus der lokalen Lösung herauskommen können.