[PYTHON] Ich habe versucht, die optimale Route des Traumlandes durch (Quanten-) Tempern zu finden

Einführung

Traumland ... Ja, es ist Tokyo Disneyland, bekannt als das Königreich der Träume und der Magie.

Ich bin sicher, Sie haben es einmal besucht, aber an Feiertagen ist es ziemlich voll, nicht wahr? In einem solchen Fall sind Wartezeit und Reisedistanz die Belastungen im Traumland.

Es wäre ideal, wenn es einen Kurs gäbe, der die Wartezeit und die Reisedistanz verkürzen würde. Wenn Sie jedoch selbst denken möchten, müssen Sie den Ort und die Wartezeit einer Vielzahl von Attraktionen genau erfassen.

Es ist ärgerlich, also scheint es meine Träume zu brechen, aber ich habe eine Web-App erstellt, die die Route des Traumlandes optimiert. Es gibt verschiedene Optimierungsmethoden, aber ich habe gerade das Quantenglühen ausprobiert, mit dem ich mich in meiner Abschlussarbeit befasse.

Wenn Sie es zuerst versuchen möchten, klicken Sie bitte hier! https://tdr-planner.web.app/ Der Optimierungsprozess dauert ca. 30 Sekunden. Warten Sie also eine Weile m (_ _) m

Glossar

Es werden viele Fachbegriffe erscheinen, daher werde ich sie grob im Voraus erläutern.

Quantencomputer

Quantencomputer werden grob in die folgenden zwei Typen eingeteilt.

Methode	Charakteristisch
Gate-Methode	Allzweck und kann alle Arten von Quantenberechnungen realisieren (Allzweckmaschine)
Steigende Modellmethode	Spezialisiert auf Kombinationsoptimierungsprobleme (dedizierte Maschine)

Auf den ersten Blick scheint die Allzweck-Gate-Methode überlegen zu sein, aber die Berechnungen, die garantiert schnell sind, sind immer noch begrenzt.

Dieses Mal werden wir Disneys Kursoptimierungsproblem als ein Kombinationsoptimierungsproblem betrachten und es unter Verwendung der Zing-Modellmethode lösen.

Problem der Kombinationsoptimierung

Das ** Kombinationsoptimierungsproblem **, das vom Quantencomputer vom Typ Zing-Modell behandelt werden kann, ist wie folgt.

Das Problem der Kombinationsoptimierung besteht darin, den Wert (die Kombination) der Variablen, die den besten Index (Wert) ergibt, unter vielen Optionen ** unter verschiedenen Einschränkungen zu finden.

Zitiert aus Annealing Cloud Web

In der obigen Quelle befindet sich ein konkretes Beispiel, sodass es leichter zu verstehen ist, wenn Sie darauf verweisen.

In dem Problem, mit dem wir uns in dieser Zeit befassen, werden wir die Kombination finden, die aus der großen Anzahl von Kombinationen, wie man die Attraktionen umrundet, am befriedigendsten ist.

Steigendes Modell

Meine Spezialität nahm plötzlich zu, aber ich werde es erklären, weil es unvermeidlich ist.

Der Quantencomputer vom Typ Rising Model ist eine dedizierte Maschine, die sich auf Kombinationsoptimierungsprobleme spezialisiert hat, sodass die Eingabe auf eine bestimmte Form beschränkt ist. Das Eingabeformat ist ein in der statistischen Dynamik verwendetes Modell, das als ** ing-Modell ** bezeichnet wird.

Wenn Sie es in Form eines Zing-Modells in einen Quantencomputer (Zing-Modellmethode) eingeben, wird nach einer Kombination von Variablen gesucht, die die Energie dieses Modells minimiert.

Die konkrete Energieformel wird wie folgt ausgedrückt.

H = \sum_{i \neq j}J_{ij}\sigma_{i}\sigma_{j} + \sum_{i}h_{i}\sigma_{i}\quad(\sigma = \pm 1)

Plötzlich kommt eine komplizierte Formel heraus, was? Ich fühle mich. Ich bin nicht zuversichtlich in die theoretische Erklärung, deshalb werde ich sie hier weglassen. Beachten Sie jedoch, dass ** $ H $ durch ein Polynom bis zur 2. Ordnung von $ \ sigma $ ** dargestellt wird.

Geben Sie beim Lösen den Koeffizienten von $ \ sigma $ im Matrixformat ein und suchen Sie nach der Kombination von $ \ sigma $, die $ H $ minimiert. Derzeit besteht das erste Ziel der Lösung mit einem Quantencomputer darin, es mit einem Polynom von maximalem Grad 2 von $ \ sigma $ auszudrücken.

QUBO

QUBO ist ein weiteres Modell, das dem Rising-Modell ähnlich ist, und die Energie wird durch die folgende Formel ausgedrückt.

H = \sum_{i \neq j}J_{ij}x_{i}x_{j} + \sum_{i}h_{i}x_{i}\quad(x \in 0,1)

Der einzige Unterschied zum Rising-Modell besteht darin, dass die Variable von $ \ sigma $, das $ \ pm 1 $ benötigt, durch $ x $, das $ 0,1 $ benötigt, ersetzt wurde.

QUBO wird für diese Disney-Kursoptimierung verwendet.

Rauer Fluss

Formulieren Sie Disneys Kursoptimierung als Kombinationsoptimierungsproblem in QUBO
Lösen Sie tatsächlich mit einem (Quanten-) Computer
Versuchen Sie, daraus eine Webanwendung zu machen

Problem Formulierung

Bei der Formulierung des Problems werden wir die folgende Abbildung berücksichtigen.

Die Kreise in der obigen Abbildung entsprechen der Binärvariablen $ x_ {i, j} \ (1 \ leq i, j \ leq 4) $ in QUBO. "Welche Attraktion soll verwendet werden?" Entspricht der Zeile und "Welche Attraktion verwendet werden soll" entspricht der Spalte. $ i $ Gibt an, ob die Attraktion $ j $ als Matrix verwendet werden soll.

Im Fall der obigen Abbildung wird der Kurs in der Reihenfolge Haunted Mansion → Poohs Honigjagd → Space Mountain → Splash Mountain ausgedrückt.

Ich denke nur an 4 Attraktionen, aber es gibt 65536 Kombinationen von 4 × 4 = 16 $ x $ in 2 bis zur 16. Potenz. Der Quantencomputer findet die Kombination von $ x $, die die in QUBO gezeigte Energie $ H $ aus diesen 65536-Kombinationen minimiert, und gibt sie im Matrixformat zurück, wie in der obigen Abbildung gezeigt. Ich werde.

Mit anderen Worten, wenn der Ausdruck, der $ H $ im idealen Kurs minimiert, mit $ x $ (zweiter Ordnung oder weniger) ausgedrückt werden kann, kann er von einem Quantencomputer optimiert werden. Wenn Sie an $ H $ denken, betrachten Sie im Allgemeinen die objektiven und eingeschränkten Begriffe als die Begriffe, aus denen $ H $ besteht.

Artikel	Rolle
Zielsetzung	Der Zielbegriff, den Sie maximieren oder minimieren möchten. Stellen Sie so ein, dass der Wert umso kleiner ist, je besser das Ergebnis ist.
Zwang	Die Mindestlaufzeit, wenn die Einschränkung erfüllt ist. Wenn die Einschränkung verletzt wird, wird der Wert als Strafe auf groß gesetzt.

Danach betrachten wir $ H $ basierend auf ↑. Die Anzahl der verwendeten Attraktionen (Anzahl der Zeilen) und die Anzahl der Attraktionen (Anzahl der Spalten) werden jedoch auf $ n bzw. m $ verallgemeinert. (In der Abbildung ist der Einfachheit halber $ n = m = 4 $)

Zweck

Am Anfang erwähnte ich, dass ich die Wartezeit und die Reisedistanz verkürzen wollte, so dass dies der Zweck zu sein scheint, aber wenn ich tatsächlich nach Disneyland gehe, glaube ich nicht, dass es Leute gibt, die sagen: "Ich möchte insgesamt innerhalb von 3 Stunden warten!"

In Wirklichkeit denke ich, der Zweck ist "Ich möchte viele Attraktionen fahren!" Qualität und Quantität müssen jedoch berücksichtigt werden. Ich möchte nicht zehnmal zu Minnies Haus gehen, weil die Wartezeit kurz ist. Daher legen wir für jede Attraktion 10 Zufriedenheitsstufen fest und zielen darauf ab, die Gesamtzufriedenheit zu maximieren.

Unter der Annahme, dass das Zufriedenheitsniveau der Attraktion $ j $ $ s_j \ \ (1 \ leq j \ leq n, 1 \ leq s_j \ leq 10) $ ist, ist das Gesamtzufriedenheitsniveau $ S $ wie folgt.

S = \sum_{j=1}^{m}\sum_{i=1}^{n}s_{j}x_{i,j}

In der Abbildung sieht es so aus.

Dieses Mal besteht der Zweck darin, die Gesamtzufriedenheit zu maximieren. Da jedoch der Zielterm so festgelegt werden muss, dass der Wert kleiner wird, wenn das Ergebnis besser ist, ist der Zielterm $ H_ {Ziel} $ der invertierte Code. Festlegen als.

H_{aim} = -\sum_{j=1}^{m}\sum_{i=1}^{n}s_{j}x_{i,j}

Einschränkung A.

Was passiert nach der Festlegung der Ziele, wenn wir sie vorerst nur optimieren? Es besteht eine hohe Wahrscheinlichkeit, dass eine solche Lösung erhalten wird.

Korrekt. Die Zufriedenheit wird maximiert, wenn Sie alle verwenden. Dies bedeutet jedoch, dass Sie 4 Attraktionen gleichzeitig nutzen und der Kurs noch nicht eingerichtet wurde.

Aus diesem Grund haben wir eine Einschränkung festgelegt, dass ** die gleichzeitige Nutzung mehrerer Attraktionen verboten ist **. Dies bedeutet, dass auf jeder Linie immer nur ein blauer Kreis steht. Diese Einschränkung ist eine One-Hot-Einschränkung, die in QUBO häufig vorkommt und durch die folgende Formel ausgedrückt wird.

H_{a} = \sum_{i=1}^{n}\left(1-\sum_{j=1}^{m}x_{i,j}\right)^2

In der Abbildung sieht es so aus.

In der obigen Abbildung befinden sich zwei blaue Kreise in der zweiten Zeile und $ H_ {a} = 1 $ aufgrund einer Einschränkungsverletzung. Wenn die Bedingung erfüllt ist, hat $ H_ {a} $ einen Mindestwert von 0.

Einschränkung B.

Was ist, wenn wir mit dem Ziel und der Einschränkung A optimieren? Sie werden wahrscheinlich eine solche Lösung erhalten. (* Zahlen in Klammern sind Zufriedenheitsstufen)

Obwohl es durch Einschränkung A als Kurs festgelegt wurde, ist es ein kühner Kurs mit 4 aufeinanderfolgenden Splash Mountains. Es ist nur natürlich, dass Splash Mountain die höchste Zufriedenheit aufweist. Egal wie beliebt die Attraktion ist, viermal zu fahren ist kein guter Kurs.

Wenn Sie die Attraktion mehrmals verwenden, legen Sie daher eine Einschränkung fest, dass die Zufriedenheit bei jeder Verwendung um 3 verringert wird. Wenn Sie beispielsweise Splash Mountain dreimal verwenden, nimmt Ihre Zufriedenheit ab, z. B. 10 zum ersten Mal, 7 zum zweiten Mal und 4 zum dritten Mal. Auf diese Weise ist die dritte Zufriedenheitsstufe 4, sodass Space Mountain (6) und Haunted Mansion (5) ausgewählt werden.

Obwohl es sich um eine Einschränkung handelt, wird der objektive Term $ H_ {aim} $ geändert, da er mit der Berechnung der Gesamtzufriedenheit zusammenhängt.

Die Richtlinie besteht darin, die Gesamtzufriedenheit einer Attraktion zu berechnen und für alle Attraktionen zusammenzufassen. Die Häufigkeit, mit der eine bestimmte Attraktion $ a $ verwendet wird, ist $ k_ {a} $

k_{a}=\sum_{i=1}^{n}x_{i,a}

Es wird sein. Da der Zufriedenheitsgrad der Attraktion $ a $ bei jeder Verwendung um 3 abnimmt, kann sie als Gleichheitssequenz mit dem ersten Term $ s_a $ tolerance-3 angesehen werden, und die Summe $ S_ {a} $ wird durch die folgende Formel ausgedrückt. Ich werde. (Summe der Gleichheitssequenzen)

S_{a}=\frac{1}{2}k_{a}(2s_{a}+(k_{a}-1)\times(-3))= k_{a}(s_{a} - \frac{3}{2}k_{a} + \frac{3}{2})

Es sieht so aus, wenn Sie Splash Mountain dreimal verwenden.

Diese Summe aller Attraktionen ist also die totale Zufriedenheit

S = \sum_{j=1}^{m}S_{j} = \sum_{j=1}^{m} \left( \sum_{i=1}^{n}x_{i,j} \left( s_j-\frac{3}{2}\sum_{i=1}^{n}x_{i,j}+\frac{3}{2} \right) \right)

Es wird sein. Legen Sie wie bei Erstes Ziel festlegen den invertierten Code als Ziel fest.

H_{aim}= -\sum_{j=1}^{m} \left( \sum_{i=1}^{n}x_{i,j} \left( s_j-\frac{3}{2}\sum_{i=1}^{n}x_{i,j}+\frac{3}{2} \right) \right)

Einschränkung C.

Was passiert, wenn Sie mit den neu festgelegten Zielen optimieren? Das Folgende ist ein Beispiel für die optimale Lösung.

Nachdem der Kurs ziemlich anständig geworden ist, lassen Sie uns über die zurückgelegte Strecke nachdenken. Die Positionsbeziehung jeder Attraktion und der Verlauf in der obigen Abbildung sind wie folgt.

Da es sich um ein schematisches Diagramm handelt, unterscheidet es sich von der tatsächlichen Positionsbeziehung, aber die Größenbeziehung der Verfahrstrecke wird korrekt ausgedrückt. Wenn die Reihenfolge von Space Mountain und Haunted Mansion umgekehrt wird, ist die Reisedistanz kürzer.

Wie oben erwähnt, ist es ideal, die Fahrstrecke zu verkürzen, aber es ist nicht realistisch, die Gesamtfahrstrecke innerhalb von 〇〇m zu halten.

Legen Sie daher eine Einschränkung fest, dass die insgesamt erforderliche Zeit innerhalb von XX Stunden liegt **. Wenn Sie die Reisezeit und die Wartezeit berechnen und diese Einschränkung ausdrücken, maximieren Sie die Gesamtzufriedenheit innerhalb einer begrenzten Zeit, sodass die Reisezeit und die Wartezeit natürlich verkürzt werden sollten.

Beim Ausdrücken dieser Einschränkung werden die folgenden drei definiert.

Geplante Aufenthaltszeit (Minuten): $ t_ {max} $ --Attraktion $ j $ Kosten (= Wartezeit + erforderliche Zeit) (Minuten): $ c_ {j} \ (1 \ leq j \ leq n) $
Reisezeit (Minuten) zwischen zwei Attraktionen $ i, j $: $ d_ {i, j} \ (1 \ leq i, j \ leq n) $

Teilen Sie die Gesamtreisezeit in ** "Gesamtkosten der zu verwendenden Attraktionen" ** + ** "Gesamtreisezeit" **.

Erstens können die Gesamtkosten der zu verwendenden Attraktion $ C $ wie folgt ausgedrückt werden wie Erstes festgelegtes Ziel. Ich habe gerade die Zufriedenheit $ s $ durch die Kosten $ c $ ersetzt.

C = \sum_{j=1}^{m}\sum_{i=1}^{n}c_{j}x_{i,j}

Als nächstes beträgt die Gesamtreisezeit $ D $ [Travelling Salesman Problem](http://blog.brainpad.co.jp/entry/2017/04/20/160000#%E4%BE%8B3-%E5%B7 % A1% E5% 9B% 9E% E3% 82% BB% E3% 83% BC% E3% 83% AB% E3% 82% B9% E3% 83% 9E% E3% 83% B3% E5% 95% 8F Es kann wie folgt ausgedrückt werden wie% E9% A1% 8C). (Ich habe aufgegeben, weil es schwierig war, sich in der Abbildung auszudrücken ... Wenn Sie verstehen möchten, überprüfen Sie bitte das Problem mit dem reisenden Verkäufer.)

D = \sum_{t=1}^{n-1}\sum_{i=1}^{m}\sum_{j=1}^{m}d_{i,j}x_{t,i}x_{t+1,j}

Stellen Sie die Differenz zwischen der Gesamtreisezeit $ (C + D) $ und der geschätzten Aufenthaltszeit $ t_ {max} $ als Einschränkung $ H_ {b} $ ein.

H_{b}=\sum_{j=1}^{m}\sum_{i=1}^{n}c_{j}x_{i,j}+\sum_{t=1}^{m-1}\sum_{i=1}^{n}\sum_{j=1}^{n}d_{i,j}x_{t,i}x_{t+1,j} -t_{max}

$ H_ {b} $ dient als Einschränkung, da sich der Wert als Strafe erhöht, wenn die insgesamt erforderliche Zeit die geplante Aufenthaltszeit überschreitet. Je kürzer die Gesamtreisezeit ist, desto kleiner ist jedoch $ H_ {b} $, sodass es einfacher ist, einen Kurs mit einer kürzeren Gesamtreisezeit zu wählen. Dies wird mit den später beschriebenen Hyperparametern angepasst.

Einschränkung D.

Optimiert durch Hinzufügen der Einschränkung $ H_ {b} $ sieht es so aus.

Sie sind gekommen, um zuerst zu Haunted Mansion zu gehen, wenn Sie die Entfernung richtig berücksichtigen. Ich mache mir jedoch Sorgen, dass Splash Mountain weiter bestehen wird.

Wenn Sie aus Computersicht ununterbrochen fahren, beträgt die Reisezeit zwischen ihnen 0. Wenn Sie sie also mehrmals verwenden, ist sie ununterbrochen. Auch wenn es in Ordnung ist, zweimal zu fahren, sollten Sie nach Möglichkeit ein kontinuierliches Fahren vermeiden.

Legen Sie daher eine Einschränkung fest, dass ** dieselbe Attraktion nicht nacheinander verwendet werden soll **. Dies entspricht der Tatsache, dass blaue Kreise in Spaltenrichtung nicht benachbart sind und wird durch die folgende Formel ausgedrückt.

H_{c} = \sum_{j=1}^{m}\sum_{i=1}^{n-1}x_{i,j}x_{i+1,j}

In der Abbildung sieht es so aus.

In der obigen Abbildung gibt es einen Teil, in dem in der ersten Spalte ein blauer Kreis benachbart ist, und $ H_ {c} = 1 $ aufgrund einer Einschränkungsverletzung. Wenn die Bedingung erfüllt ist, hat $ H_ {c} $ einen Mindestwert von 0.

Einschränkung E.

Da ich bisher vier Attraktionen in Betracht gezogen habe, wird es plötzlich zu einem Kurs wie Splash Mountain. Aber im eigentlichen Kurs muss man vom Eingang aus eintreten und zum Eingang zurückkehren.

Daher werden wir eine Einschränkung festlegen, die ** den Eingang am Anfang und Ende des Kurses ** verwendet. Der Eingang wird auch als Attraktion betrachtet und als Reihe hinzugefügt. Die Zufriedenheit wird auf 0 gesetzt, da es nicht erforderlich ist, sie in der Mitte des Kurses zu verwenden. Angenommen, der Eingang befindet sich in der ersten Spalte, wird diese Einschränkung durch die folgende Formel ausgedrückt.

H_{d} = 2 - x_{1,1} - x_{n,1}

In der Abbildung sieht es so aus. Wenn das erste $ (x_ {1,1}) $ und das letzte $ (x_ {5,1}) $ in der ersten Spalte blaue Kreise sind, ist die Bedingung erfüllt.

Wenn die Bedingung erfüllt ist, hat $ H_ {d} $ einen Mindestwert von 0.

Formulierungszusammenfassung

Es ist lange her, aber jetzt suche ich einen ziemlich vernünftigen Kurs. Die Formulierung für Disneys Kursoptimierung ist unten zusammengefasst.

Eingabedaten

Variable	Inhalt
n	Anzahl der in einem Kurs genutzten Attraktionen (wie viele möchten Sie fahren)
m	Anzahl der Sehenswürdigkeiten (Tokyo Disneyland: 34）
t_{max}	Geplante Aufenthaltszeit(Protokoll)
s_{j}	SehenswürdigkeitenjBefriedigung(1 \leq j \leq n, 1 \leq s_{j} \leq 10)
c_{j}	SehenswürdigkeitenjKosten(Protokoll)　(1 \leq j \leq n)
d_{i,j}	Sehenswürdigkeiteni,jReisezeit zwischen(Protokoll)　(1 \leq i,j \leq n)

Zweck

Maximale Zufriedenheit

Zwang

Verwenden Sie nicht mehrere Attraktionen gleichzeitig --Wenn Sie die Attraktion mehrmals nutzen, verringert sich die Zufriedenheit bei jeder Nutzung um 3.
Gesamtzeit innerhalb der geplanten Aufenthaltszeit erforderlich
Die kontinuierliche Nutzung derselben Attraktion ist verboten --Verwenden Sie den Eingang zu Beginn und am Ende des Kurses

Energiefunktion

\begin{align}
H_{aim}&=-\sum_{j=1}^{m}\left(\sum_{i=1}^{n}x_{i,j}\left(s_j-\frac{3}{2}\sum_{i=1}^{n}x_{i,j}+\frac{3}{2}\right)\right) \\
H_{a}&=\sum_{i=1}^{n}\left(1-\sum_{j=1}^{m}x_{i,j}\right)^2 \\
H_{b}&=\sum_{j=1}^{m}\sum_{i=1}^{n}c_{j}x_{i,j}+\sum_{t=1}^{n-1}\sum_{i=1}^{m}\sum_{j=1}^{m}d_{i,j}x_{t,i}x_{t+1,j} -t_{max} \\
H_{c}&=\sum_{j=1}^{m}\sum_{i=1}^{n-1}x_{i,j}x_{i+1,j} \\
H_{d}&=2- x_{1,1}-x_{n,1}
\end{align}

Die endgültige Energiefunktion $ H $ sieht folgendermaßen aus: $ \ Alpha, \ beta, \ gamma, \ delta $ sind positive Hyperparameter, die Einschränkungsgewichte darstellen.

H = H_{aim} + \alpha H_{a} + \beta H_{b} + \gamma H_{c} + \delta H_{d}

Versuchen Sie mit (Quanten-) Computer zu lösen

Lösen wir es tatsächlich mit der formulierten Energiefunktion. Dieses Mal konzentrieren wir uns auf 10 beliebte Attraktionen, die durch Dogmatismus und Vorurteile ausgewählt wurden.

Bereiten Sie zunächst die folgenden Eingabedaten vor.

Für die Wartezeit habe ich auf die Website hier verwiesen. Verwendet die durchschnittliche tägliche Wartezeit für jede Attraktion bei normaler Überlastung von Samstag bis Sonntag. (Wartezeit, aber Zeitreihendaten, die sich von Moment zu Moment ändern, können zur Vereinfachung der Berechnung jederzeit ausgeführt werden. Wir gehen von einer konstanten Wartezeit aus.) Die erforderliche Zeit wird auf der offiziellen Website von Disney angegeben. Die Kosten sind Wartezeit + benötigte Zeit und Zufriedenheit ist mein Favorit.

Ich war in Schwierigkeiten, weil ich die Daten zur Reisezeit zwischen den Attraktionen nicht finden konnte, aber ein Freund, der Disney liebt, hat zusammengearbeitet und die Entfernung zwischen den Attraktionen berechnet. Auf die Frage, wie es berechnet wurde, sagte er, dass er den Verzweigungspunkt jeder Attraktion und Passage als Knoten in Google Maps festgelegt und die kürzeste Entfernung mit der Dyxtra-Methode gefunden habe. Da es einige Passagen gibt, die nur die Darsteller nur mit Google Maps passieren können, ist es das erste Mal, dass nur eine Karte der Passagen erstellt wird, die Gäste basierend auf Google Maps passieren können. Es ist beängstigend, Wissenschaft Disney zu mögen ... ↑ Eine Karte, die von einem Freund erstellt wurde, um die kürzeste Entfernung zwischen den Sehenswürdigkeiten in Dyxtra zu finden. Weiß jemand, dass es Disneyland ist, wenn man sich das ansieht ...

Nachdem die Eingabedaten fertig sind, konvertieren Sie sie in das Format, das in den Quantencomputer eingegeben werden soll. Ursprünglich gelang es mir, $ H $ zu erweitern, um eine Koeffizientenmatrix (QUBO-Matrix) der Terme erster und zweiter Ordnung von $ x $ zu erstellen, aber diesmal habe ich eine QUBO-Matrix mit gut lesbarem Code generiert. Ich habe die Python-Bibliothek pyqubo verwendet.

import numpy as np
import pandas as pd
from pyqubo import Array, Sum, Num, Constraint, Placeholder

cost_data = pd.read_csv('tdl_cost.csv')
distance_data = pd.read_csv('tdl_distance.csv', header=None)

s = cost_data['value'].to_numpy()
c = cost_data['cost'].to_numpy()
d = (distance_data / 80).to_numpy() #Fahrzeit bei einer Gehgeschwindigkeit von 80 m / min(Protokoll)Konvertieren zu
n = 12
m = len(c)
t_max = 60 * 12
x = Array.create('x', (n, m), 'BINARY')

#Zielsetzung
H_aim = -Sum(0, m, lambda j: Sum(0, n, lambda i: x[i,j]) * (s[j] - 1.5 * Sum(0, n, lambda i: x[i,j]) + 1.5))

#Die gleichzeitige Nutzung mehrerer Attraktionen ist verboten
H_a = Constraint(Sum(0, n, lambda i: (1 - Sum(0, m, lambda j: x[i,j])) ** 2), 'alpha')

#Gesamtreisezeit innerhalb der geplanten Aufenthaltszeit
C = Sum(0, m, lambda j: Sum(0, n, lambda i: (c[j] * x[i,j])))
D = Sum(0, n-1, lambda t: Sum(0, m, lambda i: Sum(0, m, lambda j: (d[i,j] * x[t,i] * x[t+1,j]))))
H_b = Constraint(C + D - t_max, 'beta')

#Die kontinuierliche Nutzung derselben Attraktion ist verboten
H_c = Constraint(Sum(0, m, lambda j: Sum(0, n-1, lambda i: x[i,j] * x[i+1,j])), 'gamma')

#Verwenden Sie den Eingang am Anfang und Ende des Kurses
H_d = Constraint(2 - x[0,0] - x[n-1,0], 'delta')

#Energiefunktion(Ich habe auch die Ziele gewichtet)
H = 30 * H_aim + Placeholder('alpha') * H_a + Placeholder('beta') * H_b + Placeholder('gamma') * H_c + Placeholder('delta') * H_d

#Beschränkte gewichtete Hyperparameter
params = {
    'alpha': 60,
    'beta': 2,
    'gamma': 60,
    'delta': 100
}

#Generieren Sie eine QUBO-Matrix
model = H.compile()
qubo, offset = model.to_qubo(feed_dict=params)

Sie können das optimierte Ergebnis erhalten, indem Sie das in der letzten Zeile erzeugte Qubo auf den Quantencomputer werfen. Es gibt eine Maschine namens D-Wave als Quantencomputer, die allgemein verwendet werden kann, aber D-Wave hat eine Einschränkung des QUBO-Modells, die gelöst werden kann, sodass dieses Problem nicht geeignet ist. Hmm.

Dieses Mal habe ich Fujitsu Digital Annealer für die universitäre Forschung verwendet. Der digitale Annealer besteht aus digitalen Schaltungen, die von Quantenphänomenen inspiriert sind, und ist nicht gerade ein Quantencomputer. Es heißt also: "Ich habe versucht, durch Quantenglühen den optimalen Weg für das Traumland zu finden", aber es tut mir leid, dass es sich um einen Titelbetrug handelt (_ \ ) m Bitte beachten Sie, dass es sich um eine Simulation des Quantenglühens m ( _) m handelt

Code, der Digital Annealer verwendet, kann nicht veröffentlicht werden, da er eine private Bibliothek verwendet. Das Ergebnis ist jedoch wie folgt.

Die Gesamtreisezeit beträgt mehr als 10 Minuten, ist aber akzeptabel. Das Einstellen der Hyperparameter sollte es verbessern. Ich habe nicht nur Poohs Honigjagd verwendet, aber es ist ein vernünftiges Ergebnis, weil es die vierthöchsten Kosten, aber die niedrigste Zufriedenheit sind.

Wenn ich den Kurs auf die Disney-Karte zeichne, sieht er wie folgt aus. Der Pfeil ist eine gerade Route, daher ist er nicht genau, aber er ist zu einem mageren Kurs geworden, der durch den Park führt.

Internetanwendung

Ich hatte einen Disney-liebenden Freund, der mit mir zusammengearbeitet hat, um die Gültigkeit des Kurses zu überprüfen, aber jedes Mal, wenn ich die Eingabe auf dem lokalen PC änderte und neu berechnete, war es schwierig, das Ergebnis zu senden, sodass ich daraus eine Webanwendung machte Ich versuchte es.

https://tdr-planner.web.app/

Es gibt auch Disney Sea-Daten, sodass Sie sowohl Land als auch Meer ausprobieren können!

Backend

Ich habe Google Cloud-Funktionen verwendet, da ich nur eine einfache API benötige, die die Optimierungsverarbeitung durchführt und den Kurs zurückgibt.

Es ist im Grunde dasselbe wie die Python-Implementierung von [hier](#solve with a Quantum Computer), Zufriedenheit $ (s) $, Anzahl der verwendeten Attraktionen $ (m) $, geschätzte Aufenthaltszeit $ (t_ { max}) $ wird von einer HTTP-Anfrage eingegeben.

Es ist der wesentliche Glühprozess, aber ich musste mir eine Alternative überlegen, weil ich in meiner privaten Anwendung keine Forschungsmaschine verwenden konnte. Zum Glück ist SA (Simulated Annealing) in pyqubo implementiert, daher habe ich dies für Cloud-Funktionen verwendet.

Mit dem folgenden Code können Sie die generierte QUBO-Matrix einfach simulieren.

Dies ist natürlich kein Quantenglühen m (_ \ _) m

from pyqubo import solve_qubo

raw_solution = solve_qubo(qubo)
decoded_solution, broken, energy = model.decode_solution(raw_solution, vartype='BINARY', feed_dict=params)

Das in ↑ erhaltene Ergebnis ist gut geformt und in eine API umgewandelt, die den folgenden json zurückgibt.

{
    "totalScore": 72.0,
    "totalAttractionTime": 699,
    "totalTravelTime": 26,
    "totalTime": 725
    "course": [
        {
            "attraction": "Eingang",
            "attractionId": 0,
            "waitingTime": 0,
            "requiredTime": 0.0,
            "startTime": "09:00",
            "endTime": "09:00",
            "x": 655,
            "y": 830
        },
        {
            "attraction": "Monster AG",
            "attractionId": 31,
            "waitingTime": 85,
            "requiredTime": 4.0,
            "startTime": "09:02",
            "endTime": "10:31",
            "x": 815,
            "y": 740
        },
        {
            "attraction": "Weltraumberg",
            "attractionId": 33,
            "waitingTime": 87,
            "requiredTime": 3.0,
            "startTime": "10:35",
            "endTime": "12:05",
            "x": 1005,
            "y": 600
        },
        ...
        {
            "attraction": "Eingang",
            "attractionId": 0,
            "waitingTime": 0,
            "requiredTime": 0.0,
            "startTime": "21:13",
            "endTime": "21:13",
            "x": 655,
            "y": 830
        }
    ]
}

Vorderes Ende

Ich brauchte nur das Eingabeformular für Zeit und Zufriedenheit und die Möglichkeit, die API aufzurufen, um die Ergebnisse anzuzeigen. Daher habe ich es mit Nuxt + Vuetify, das ich in letzter Zeit häufig sehe, schnell geschafft und es als SPA auf Firebase gehostet. (Favicon ist Nuxt und es ist ein wenig peinlich, weil es ein Gefühl von Vuetify vermittelt ...) Idealerweise wollte ich eine Route auf Disneys offizieller Karte zeichnen. Als ich mich vorerst mit dem Tokyo Disney Resort in Verbindung setzte, war es normalerweise NG. Es sollte jedoch Disney heißen, und er antwortete auch höflich auf die verspielten College-Studenten, die mich baten, das offizielle Kartenbild zu verwenden.

Bitte veröffentlichen Sie das Kartenbild von Tokyo Disneyland Sea nicht auf der Website von Einzelpersonen. Wir entschuldigen uns für die Unannehmlichkeiten, dass wir Ihnen eine solche Antwort geben, obwohl Sie uns kontaktiert haben, aber bitte verstehen Sie.

abschließend

Da ich in meiner Abschlussarbeit Quantenglühen mache, war meine ursprüngliche Motivation, verschiedene Probleme der Kombinationsoptimierung zu lösen und mich daran zu gewöhnen. Ich habe dieses Problem jedoch eingestellt, weil ich dachte, es wäre schön, ein realistisches und interessantes Problem zu haben, wenn ich es trotzdem lösen könnte.

Zuerst wollte ich es so leicht wie eine Pause von meiner Abschlussarbeit machen, aber mein Freund arbeitete erstaunlich mit mir zusammen (der Person, die die Entfernung berechnet hat), und das Ergebnis war anständiger, als ich es mir vorgestellt hatte. Ich dachte, ich würde es zusammenhalten.

Da Disney tatsächlich kompliziertere Elemente enthält, werden die folgenden Probleme als Anwendung angehäuft.

Die Wartezeit wird nicht als Zeitreihendaten behandelt (die gleiche Wartezeit wird unabhängig von Ihrer Uhrzeit verwendet).
Nicht über einen schnellen Pass nachdenken ――Wir betrachten nichts anderes als Attraktionen wie Mittag- und Abendessen sowie Shows

Kurz gesagt, es ist immer noch eine verdammte App, also denke ich darüber nach, sie in meiner Freizeit weiterzuentwickeln.

Wir suchen nach anderen Problemen, die mit dem Quantenglühen gelöst werden können. Wenn Sie also interessante Ideen haben, schreiben Sie diese bitte in die Kommentare!