[PYTHON]
Darüber hinaus wird das Boltzmann-Maschinenmodell als Berechnungsmodell übernommen und die Programmierung in Python durchgeführt, um die optimale Lösung zu finden.
: blue_car: Über die Theorie der Backmethode
Die detaillierten Erklärungen der mathematischen Formeln und grundlegenden Theorien zur Backmethode, die hier aufgegriffen werden, sind im Nachschlagewerk "Optimierungsalgorithmus" (P120-) enthalten, das in der unteren "Quelle" beschrieben ist, daher werde ich sie hier weglassen. Ich möchte hauptsächlich über das Programmieren schreiben.
: blue_car: Einfaches Problem mit dem Patrouillenverkäufer
Als Problem mit reisenden Verkäufern verwenden wir dasselbe Problem, das wir hier angesprochen haben.
■ Lösen Sie das Problem des Handlungsreisenden mit dem genetischen Algorithmus (GA) und seiner Bibliothek (vcopt). https://qiita.com/ttlabo/items/9b00a29702d1205f6996
Betrachten Sie Tabelle 1, in der jede Zeile den Namen der Stadt und jede Spalte die Reihenfolge der Besuche anzeigt, wie unten gezeigt. Wenn Sie Städte in einer bestimmten Reihenfolge besuchen, ist der Wert in der Tabelle 1, andernfalls ist der Wert 0. In Tabelle 1 lautet die Reihenfolge der Patrouille beispielsweise ** Stadt E-> Stadt A-> Stadt D-> Stadt C-> Stadt B-> Stadt E ** (kehrt schließlich in die Abflugstadt zurück). Tabelle 2 definiert auch die Entfernung zwischen Städten.
Wenden Sie das Boltzmann-Maschinenmodell auf das Travelling Salesman Problem (TSP) an, das in diesen fünf Städten unterwegs ist, um das Problem zu lösen.
: blue_car: Formel der Energieformel (Hamiltonian) der Zielfunktion
Aus dem Nachschlagewerk zitiert, ist die Grundidee der Bräunungsmethode wie folgt definiert.
** Grundkonzept der Backmethode **
Zielfunktion $ f (x) $: Systemenergie (Hamiltonian) $ F (x) $ Variable $ x $: Systemstatus, der sich gemäß einer bestimmten Wahrscheinlichkeitsverteilung ändert Temperaturparameter $ T $: Variable, die die Zustandsübergangswahrscheinlichkeit steuert
Ändern Sie in diesem Zusammenhang den Temperaturparameter $ T $ schrittweise von einem hohen Wert auf einen niedrigen Wert. Suchen Sie nach dem stabilen Punkt (Mindestwert) von $ f (x) $.
Nun müssen wir die Zielfunktion Hamiltonian definieren. Hamiltonian entwickelt und formuliert so, dass die optimale Lösung gefunden werden kann, wenn der Wert zum Minimum wird. Fügen Sie beispielsweise einen Begriff hinzu, der den Hamilton-Wert erhöht, wenn Sie eine Route oder eine Verstoßbedingung wählen, die zur Lösung des Problems nicht geeignet ist. Dieser Begriff wird als Strafzeit bezeichnet.
Betrachten Sie in dieser Ausgabe Folgendes als Hamiltonian $ H $.
\begin{eqnarray}
Hamiltonian H.&=& H_A + H_B\\
H_A &=&Begriff für die Ermittlung der Entfernung zwischen Städten\\
H_B &=&Strafstrafe
\end{eqnarray}
Betrachten Sie zunächst $ H_A $. Der Abstand zwischen der Stadt $ i $ und der Stadt $ j $ sei $ d_ {i, j} $ und passe die Variable $ x $ in jede Zelle in Tabelle 1 an, um $ x_ {i, k} $ zu erhalten. Wobei $ x_ {i, k} $ die Variable ist, die bestimmt, ob die Stadt $ i $ an der $ k $ -ten Stelle besucht werden soll. Eine Variable, die beim Besuch 1 und beim Nichtbesuch 0 annimmt und als binäre Variable bezeichnet wird.
Die Gesamtroute kann berechnet werden, indem die Entfernung $ d_ {i, j} $ addiert wird, wenn die Stadt $ i $ an der $ k $ -ten Stelle besucht wird und die Stadt $ j $ an der $ k + 1 $ -ten Stelle der Reihe nach besucht wird. Das ist in Ordnung, also definieren Sie $ H_A $ wie folgt:
H_A = K_1\sum_{i=1}^{5}\sum_{j=1}^{5}\sum_{k=1}^{5}d_{i,j}x_{i,k}x_{j,k+1}… Zeremonie(1)
In der obigen Formel ist $ K_1 $ eine Konstante. Achten Sie auf den Bereich von $ k $ im dritten $ \ sum $ (Sigma-Symbol). Wenn $ k $ = 5 ist, wird $ x $, das Ziel der Sigma-Berechnung, zu $ x_ {i, 5} x_ {j, 6} $, und die sechste zu besuchende Stadt ist erforderlich. In dieser Ausgabe kehren wir in die erste Stadt zurück, die wir besucht haben (zuerst).
Da Sie nicht dieselbe Stadt nacheinander besuchen können, setzen Sie den Wert von $ d_ {i, i} $ auf einen großen Wert und bestrafen Sie, dass der Wert von $ H_A $ nicht als Lösung ausgewählt wird. .. Das heißt, setzen Sie den Wert für $ d_ {1,1} $, $ d_ {2,2} $ ,,, $ d_ {5,5} $. Stellen Sie außerdem den Abstand für den leeren Bereich unten links in Tabelle 2 ein, indem Sie die Kombination zwischen Städten berücksichtigen. Sie können es wie eine symmetrische Matrix einstellen. Daher definieren wir Tabelle 2 wie folgt neu.
Als nächstes betrachten wir $ H_B $. In Tabelle 1 enthält jede Zeile und Spalte 1 Anzahl von Einsen und 4 Anzahl von Nullen. Dies bedeutet, dass Sie dieselbe Stadt nicht mehrmals oder mehrere Städte in derselben Reihenfolge gleichzeitig besuchen. Mit anderen Worten, die Summe jeder Zeile und jeder Spalte ist immer 1. Wenn es nicht 1 ist, kann es als Strafe angesehen werden, die den Wert erhöht, und $ H_B $ wird wie folgt gesetzt.
H_B = K_2\Biggl[\sum_{i=1}^{5}\bigg(\sum_{k=1}^{5}x_{i,k}-1\bigg)^2 + \sum_{k=1}^{5}\bigg(\sum_{i=1}^{5}x_{i,k}-1\bigg)^2\Biggl]… Zeremonie(2)
In der obigen Formel sei $ K_2 $ eine Konstante.
Nachdem wir $ H_A $ und $ H_B $ definiert haben, lautet Hamiltonian $ H $:
H = K_1\sum_{i=1}^{5}\sum_{j=1}^{5}\sum_{k=1}^{5}d_{i,j}x_{i,k}x_{j,k+1} + K_2\Biggl[\sum_{i=1}^{5}\bigg(\sum_{k=1}^{5}x_{i,k}-1\bigg)^2 + \sum_{k=1}^{5}\bigg(\sum_{i=1}^{5}x_{i,k}-1\bigg)^2\Biggl]… Zeremonie(3)
: blue_car: Denken Sie an Programmalgorithmen
Wir werden einen Algorithmus erstellen, der auf dem Nachschlagewerk basiert. Betrachten Sie zunächst die folgende logische Formel, die die Grundlage des Boltzmann-Maschinenmodells bildet. Die folgende Formel heißt Gibbs-Boltzmann-Verteilung und beschreibt das Verhalten von Partikelsystemen wie Temperatur und Gas in der Physik (statistische Dynamik). $ f (x) $ ist die Energie des Systems und $ T $ ist der Parameter, der der Temperatur entspricht.
g(x,T) = \frac{1}{\sum_{x}^{}exp\big(\frac{-f(x)}{T}\big)}exp\big(\frac{-f(x)}{T}\big)… Zeremonie(4)
Bei der Berechnung des Boltzmann-Maschinenmodells wird die Temperatur $ T $ näher an 0 gebracht. Durch Annäherung an die Temperatur an 0 ist es möglich, sich einer Gleichgewichtszustandsverteilung durch den Ergod-Satz der Markov-Kette (Nachschlagewerk P123) zu nähern, und die optimale Lösung kann erhalten werden.
Hier wird die obige Temperatur $ T $ als Funktion der Zeit $ t $ wie folgt definiert. Anstatt die Temperatur zu senken, ändern Sie $ t $, um die Berechnung durchzuführen.
T(t) = \frac{k}{ln(t+2)}… Zeremonie(5)\\
(t=0,1,2,...)
In der obigen Gleichung ist $ k $ eine Konstante und $ ln $ ein natürlicher Logarithmus.
Die Energie des Systems (Hamiltonian) ändert sich jedes Mal, wenn die Temperatur T gesenkt wird. Wenn sich diese Energie ändert, stellen Sie einen Index ein, um zu bestimmen, ob diese Änderung berücksichtigt werden soll. Dieser Indikator wird als Akzeptanzwahrscheinlichkeit bezeichnet. Die Akzeptanzwahrscheinlichkeit wird aus der Gibbs-Boltzmann-Verteilungsgleichung (4) und der folgenden Akzeptanzfunktion $ F_B $ wie folgt abgeleitet (Nachschlagewerk P129). Hier ist $ A (x, y) $ die Akzeptanzwahrscheinlichkeit, $ E (x) $ oder $ E (y) $ die Energie des Systems (Hamiltonian) und $ g (x, T) $ die Gibbs-Boltzmann-Verteilungsformel. Wird besorgt. $ X $ ist der Zustand vor der Energieänderung und $ y $ ist der Zustand nach der Energieänderung.
Akzeptanzwahrscheinlichkeit A.(x,y) = F_B\bigg(\frac{g(y,T)}{g(x,T)}\bigg)\\
= \frac{1}{1+exp\big(\frac{E(y)-E(x)}{T}\big)}… Zeremonie(6)\\
Akzeptanzfunktion F._B(s) = \frac{s}{1+s}
Nachdem wir die erforderlichen Ausdrücke haben, werden wir den Algorithmus erstellen.
Berücksichtigen Sie die Anfangsbedingungen des Programms. Wie oben erwähnt, beginnt die Zeit $ t $ bei 0, erhöht sich und erhöht sich um 1. Die Inkrementierung erfolgt bei der Schleifenverarbeitung, und die Anzahl der Schleifen ist die Schleife. $ t $ wechselt von 0 zu Schleife-1.
Betrachten Sie den Anfangszustand der zweidimensionalen Array-Typvariablen $ x $ (dies ist im Python-Programm der Diktat-Typ). $ X $ ist eine Variable, die bestimmt, ob jede Stadt besucht werden soll oder nicht, und wird als Determinante bezeichnet. Es ist eine binäre Variable, die 0 oder 1 annimmt, und diesmal wird sie als zweidimensionales 5x5-Array betrachtet, wie in der folgenden Abbildung gezeigt (Indexnummer beginnt bei 0).
Initialisieren Sie dieses Entscheidungsvariablen-Array $ x $. Die Initialisierungsmethode sollte zufällig auf 0 oder 1 gesetzt werden.
Nach dem Initialisierungsprozess wird der Schleifenprozess gestartet. Dieser Schleifenprozess entspricht einer Temperatursenkung.
Die Anzahl der Schleifen wird von der variablen Schleife gehalten, es gibt jedoch keine bestimmte Anzahl. Bestimmt nach dem Betriebszustand des Programms.
Holen Sie sich zuerst die Temperatur $ T $. Die Temperatur $ T $ wird durch Gleichung (5) bestimmt.
Wählen Sie zufällig eine aus den Entscheidungsvariablen $ x $ aus. Da $ x $ ein zweidimensionales Array von 5x5-Matrizen ist, erhalten wir zufällige Koordinaten $ (i, j) $ in jeder der x- und y-Richtungen.
Invertiert den zufällig erhaltenen Wert von $ x (i, j) $. Invertieren bedeutet, den Wert von $ x (i, j) $ auf 0 zu ändern, wenn er 1 ist, und auf 1, wenn er 0 ist. Das Invertieren dieses $ x (i, j) $ wird als "Ändern des Zustands" bezeichnet. Berechnen Sie, wie sich die Energie des Systems (Hamiltonian) vor und nach der Änderung des Zustands ändert, und entscheiden Sie, ob die Änderung berücksichtigt werden soll. In diesem Programm wird ein neues zweidimensionales Array, dessen Status geändert wurde, als $ y $ gesichert.
Die Wahrscheinlichkeit, zu entscheiden, ob diese Änderung übernommen werden soll oder nicht, wird als Akzeptanzwahrscheinlichkeit bezeichnet (Nachschlagewerk P128). Die Akzeptanzwahrscheinlichkeit wird durch Gleichung (6) berechnet. Der Zustand vor der Änderung (Systemenergie) ist $ E (x) $, und der Zustand nach der Änderung ist $ E (y) $. Die Energie des Systems (Hamiltonian) wird nach Gleichung (3) berechnet.
In Bezug auf die obigen Änderungen wird akzeptiert, wenn die Akzeptanzwahrscheinlichkeit einen bestimmten Schwellenwert überschreitet, und wenn sie nicht überschreitet, wird sie nicht akzeptiert. Akzeptieren bedeutet, die Inversion eines zufällig ausgewählten $ x (i, j) $ -Werts zu akzeptieren, und nicht zu akzeptieren bedeutet, den $ x (i, j) $ -Wert unverändert zu lassen. Das Programm legt den Schwellenwert mit einer Variablen namens juri_hantei fest. Wenn dies akzeptiert wird, übertragen Sie das zweidimensionale Array $ y $ auf $ x $.
Nachdem Sie den geänderten Zustand gemäß der Akzeptanzwahrscheinlichkeit eingestellt haben, stellen Sie die Zeit mit $ t = t + 1 $ einen Schritt vorwärts.
Wiederholen Sie die obige Schleife. Die endgültige Lösung ist $ x $ am Ende der Schleife.
: blue_car: Anordnung der Algorithmen
Die obigen Algorithmen sind in der prozeduralen Reihenfolge angeordnet, wie in der folgenden Abbildung gezeigt.
sa_simulation.py
1.Variablendefinition
Anzahl der Schleifen=Auf 50000 einstellen.
Entfernung zwischen Städten di,Definiere j.
Hamiltonsche Konstante K1,Definieren Sie K2.
Konstante k zur Bestimmung der Temperatur(Gleichung 5)Ist definiert.
k1,Die Werte von k2 und k werden unter Beobachtung der Programmbewegung bestimmt.
Akzeptanzurteilsschwelle basierend auf Akzeptanzwahrscheinlichkeit juri_Definiere hantei.
juri_Der Wert von hantei wird durch Beobachten der Bewegung des Programms bestimmt.
2.Initialisieren
Zeit t=Auf 0 setzen.
Variable x(Ein zweidimensionales Array)Setze zufällig 0 oder 1 für jedes Element von.
Definieren Sie die im Programm verwendeten Funktionen.
3.Starten Sie die Schleifenverarbeitung
Formel(5)Holen Sie sich mehr Temperatur Tp.
Zufällig x[i,j]Wählen. 1 Dimension(y-Achse)Richtung i, 2D(x-Achse)In jede Richtung j
Identifiziere x zufällig[i,j]Wählen.
Gleiche Anzahl von Elementen wie x(Anzahl der Dimensionen)Mit x[i,j]Nur der Wert von(1 wenn 0, 0 wenn 1)Und
Erstellen Sie ein zweidimensionales Array y mit anderen Werten wie x.
Akzeptanzwahrscheinlichkeit(Gleichung 6)Ist berechnet.
Wenn die Akzeptanzwahrscheinlichkeit den Schwellenwert überschreitet, wird x durch y ersetzt.(Wenn nicht, lassen Sie x so wie es ist und tun Sie nichts)
t=t+Lass es 1 sein.
Kehren Sie zur Ausgangsposition der Schleife zurück.
4.Ergebnisse bekommen
Das endgültig erhaltene x wird auf dem Bildschirm als optimale Lösung angezeigt.
Berechnen Sie die Gesamtentfernung und zeigen Sie sie auf dem Bildschirm an.
: blue_car: Programmimplementierung
Die Programmierung ist diesmal wie folgt.
sa_simulation.py
import random
import math
# =====================================================================
# 1.Konstante Definition
# =====================================================================
#Anzahl der Schleifen
loop = 50000
#Definition der Entfernung
d = [
[100, 30, 30, 25, 10],
[ 30, 100, 30, 45, 20],
[ 30, 30, 100, 25, 20],
[ 25, 45, 25, 100, 30],
[ 10, 20, 20, 30, 100]
]
#Eine Dimension des zweidimensionalen Arrays x(y Richtung)Anzahl der Elemente von
len_x_y = 5
#2D des 2D-Arrays x(x Richtung)Anzahl der Elemente von
len_x_x = 5
#Hamiltonsche Konstante
k1 = 0.01
k2 = 1
#Konstante zur Temperaturbestimmung
k = 5
#Schwellenwert für die Beurteilung, ob akzeptiert werden soll oder nicht, basierend auf der Akzeptanzwahrscheinlichkeit
juri_hantei = 0.05
# =====================================================================
# 2.Initialisieren
# =====================================================================
#Zeitinitialisierung
t = 0
#Zufällig 0 für 2D-Array-Elemente,Auf 1 setzen
x = {}
for i in range(len_x_y):
for j in range(len_x_x):
x[i,j] = random.randint(0,1)
# =====================================================================
#Funktionsdefinition
# =====================================================================
#Hamiltonianer
def H(x):
HA = 0
sumA = 0
sumB = 0
for i in range(len_x_y):
for j in range(len_x_y):
for k in range(len_x_x):
k_from = k
if k == len_x_x - 1:
k_to = 0
else:
k_to = k + 1
sumA += d[i][j] * x[i,k_from] * x[j, k_to]
HA += k1 * sumA
sumB1 = 0
for i in range(len_x_y):
for k in range(len_x_x):
sumB1 += x[i,k]
sumB += sumB1 * sumB1
sumB1 = 0
sumB2 = 0
for i in range(len_x_y):
for k in range(len_x_x):
sumB2 += x[i,k]
sumB -= 2 * sumB2
sumB2 = 0
for i in range(len_x_y):
sumB += 1
sumB3 = 0
for k in range(len_x_x):
for i in range(len_x_y):
sumB3 += x[i,k]
sumB += sumB3 * sumB3
sumB3 = 0
sumB4 = 0
for k in range(len_x_x):
for i in range(len_x_y):
sumB4 += x[i,k]
sumB -= 2 * sumB4
sumB4 = 0
for k in range(len_x_x):
sumB += 1
HA += k2 * sumB
return HA
#Definition der Temperaturfunktion
def T(t):
T = k / math.log(t + 2)
return T
#Berechnung der Akzeptanzwahrscheinlichkeit
def A(x,y,T):
tmp = H(y) - H(x)
A = 1 / (1 + math.exp(tmp / T))
return A
# =====================================================================
# 3.Schleifenverarbeitung
# =====================================================================
while t < loop:
#Holen Sie sich die Temperatur
Tp = T(t)
#Wählen Sie zufällig eine aus dem zweidimensionalen Array x aus(Zufällige Koordinaten i,Holen Sie sich j)
r_i = random.randint(0,len_x_x - 1)
r_j = random.randint(0,len_x_x - 1)
#Erstellen Sie ein zweidimensionales Array y im Zustand y, wobei nur eine zufällig ausgewählte Koordinate invertiert ist.
y = {}
for i in range(len_x_y):
for j in range(len_x_x):
if i == r_i and j == r_j:
#Umkehren
y[i,j] = -1 * (x[i,j] - 1)
else:
y[i,j] = x[i,j]
#Akzeptanzwahrscheinlichkeit berechnen
juri = round(A(x,y,Tp), 2)
#Zeitvariablen und Akzeptanzwahrscheinlichkeit anzeigen
print('t=',t,'juri=',juri)
#Bestimmen Sie anhand der Akzeptanzwahrscheinlichkeit, ob akzeptiert werden soll
if juri >= juri_hantei:
x = y
print('▼ Akzeptiert.')
#Vorlaufzeit t
t = t + 1
# =====================================================================
# 4.Ergebnisanzeige(Besuchte Stadt)
# =====================================================================
print('-----Ergebnisanzeige-------')
for i in range(len_x_y):
line = ''
for j in range(len_x_x):
line += ' '
if x[i,j] == 1:
line += 'o'
else:
line += '-'
print(line)
# =====================================================================
# 5.Ergebnisanzeige(Gesamtentfernung)
# =====================================================================
#Liste der zu besuchenden Städte
city = []
for k in range(len_x_x):
for i in range(len_x_y):
if x[i,k] == 1:
city.append(i)
#Fügen Sie eine Route zurück von der zuletzt besuchten Stadt zur zuerst besuchten Stadt hinzu
city.append(city[0])
#Berechnen Sie die Gesamtentfernung
td = 0
for c in range(len(city) - 1):
td += d[city[c]][city[c+1]]
print('total distance:', td)
: blue_car: Überprüfung des Ausführungsergebnisses
Die durch das simulierte Glühverfahren erhaltene Lösung ist eine ungefähre Lösung, keine exakte Lösung. Iterieren Sie die Berechnungen, um endlich eine bessere Lösung zu finden. Diese Lösung wird als optimale Lösung bezeichnet.
Daher kann sich die optimale Lösung in Abhängigkeit von der Anzahl der Iterationen jedes Mal geringfügig unterscheiden. Wiederholen Sie die iterative Berechnung mehrmals und schließen Sie, dass die am häufigsten auftretende Lösung die endgültige optimale Lösung ist.
Die optimale Lösung war diesmal wie folgt.
Es stellte sich heraus, dass die Reihenfolge der Patrouille der Städte ab Stadt E ** E → A → D → C → B → E ** sein sollte. Wenn Stadt A der Ausgangspunkt ist, ist es übrigens A → D → C → B → E → A. Die Gesamtentfernung beträgt ** 110 **.
Die schwierigsten Punkte waren diesmal ** die Bestimmung der Variablen k1 und k2 für Hamilton, die Variablen k für die Temperatur und den Schwellenwert juri_hantei **.
Wenn die Größenbeziehung zwischen k1 und k2 nicht gut angepasst wird, funktioniert der Strafzeitraum nicht effektiv und die Lösung hat überlappende Patrouillenrouten und eine kleine Anzahl von besuchten Städten. Wenn die Temperaturvariable k nicht auf den richtigen Wert eingestellt ist, kann bei der Verarbeitung der exp-Funktion ein Überlauf auftreten oder die Akzeptanzwahrscheinlichkeit ist zu gering, um sie zu bestimmen. Durch Setzen des Schwellenwerts juri_hantei auf genau den richtigen Wert besteht die ideale Form des Verarbeitungsszenarios darin, dass die erste Hälfte der 50.000 Schleifenprozesse mehr Zustandsänderungen akzeptiert und die zweite Hälfte weniger, weil der Hamilton-Operator konvergiert hat. Ich konnte es einpassen.
das Ende
: blue_car: Quelle
■ Nachschlagewerk
"Optimierungsalgorithmus" Tomoharu Nagao [Autor] Shokodo
: blue_car: Verwandte Informationen
■ Lösen Sie mit Blueqat ein einfaches Problem mit der Scheitelpunktabdeckung https://qiita.com/ttlabo/items/b4ab222ef9c5ee99233c
■ Ein Beispiel für die Lösung des Rucksackproblems mit Blueqat https://qiita.com/ttlabo/items/537564c90056a6d56879
■ Lösen Sie das Problem des Handlungsreisenden mit dem genetischen Algorithmus (GA) und seiner Bibliothek (vcopt). https://qiita.com/ttlabo/items/9b00a29702d1205f6996
■ Lösen von Rucksackproblemen mit Googles OP-Tools - Üben Sie die Grundlagen von Problemen bei der Kombinationsoptimierung https://qiita.com/ttlabo/items/bcadc03004418f32f49d
■ [Teil 1] Was ist Optimierung? - Lernmaterialien zum Erlernen der mathematischen Optimierung https://qiita.com/ttlabo/items/e6970c6e85cce9ff4e34
: blue_car: Meinungen etc.
Wenn Sie Meinungen oder Korrekturen haben, lassen Sie es uns bitte wissen.
Recommended Posts