[PYTHON] J'ai essayé de trouver l'itinéraire optimal du pays des rêves par recuit (quantique)

introduction

Dreamland ... Oui, c'est Tokyo Disneyland, connu sous le nom de Royaume des rêves et de la magie.

Je suis sûr que vous l'avez visité une fois, mais il y a beaucoup de monde en vacances, n'est-ce pas? Dans un tel cas, le temps d'attente et la distance parcourue sont les fardeaux du pays des rêves.

Ce serait idéal s'il y avait un cours qui réduirait le temps d'attente et la distance parcourue. Cependant, lorsqu'il s'agit de penser par vous-même, il est nécessaire de saisir avec précision l'emplacement et le temps d'attente d'un grand nombre d'attractions.

C'est ennuyeux, donc cela semble briser mes rêves, mais j'ai fait une application web qui optimise l'itinéraire du pays des rêves. Il existe différentes méthodes d'optimisation, mais je viens d'essayer le recuit quantique dont je parle dans ma thèse de fin d'études universitaire.

Si vous souhaitez l'essayer en premier, cliquez ici! https://tdr-planner.web.app/ Le processus d'optimisation prendra environ 30 secondes, veuillez donc patienter un peu m (_ _) m

Glossaire

De nombreux termes techniques apparaîtront, je vais donc les expliquer à peu près à l'avance.

Ordinateur quantique

Les ordinateurs quantiques sont à peu près classés dans les deux types suivants.

méthode	Fonctionnalité
Méthode de porte	Usage général et peut réaliser toutes sortes de calculs quantiques (machine à usage général)
Méthode du modèle ascendant	Spécialisé dans les problèmes d'optimisation des combinaisons (machine dédiée)

À première vue, la méthode de la porte polyvalente semble supérieure, mais les calculs garantis rapides sont encore limités.

Cette fois, nous allons considérer le problème d'optimisation des cours de Disney comme un problème d'optimisation de combinaison et le résoudre en utilisant la méthode du modèle Zing.

Problème d'optimisation de combinaison

Le ** problème d'optimisation de combinaison ** qui peut être traité par l'ordinateur quantique de type modèle Zing est le suivant.

Le problème de l'optimisation des combinaisons est de trouver la valeur (combinaison) de la variable qui donne le meilleur indice (valeur) parmi de nombreuses options ** sous diverses contraintes.

Extrait de Annealing Cloud Web

Il y a un exemple concret dans la source ci-dessus, il sera donc plus facile à comprendre si vous y faites référence.

Dans le problème auquel nous sommes confrontés cette fois, nous trouverons la combinaison la plus satisfaisante parmi le grand nombre de combinaisons pour faire le tour des attractions.

Modèle en hausse

Ma spécialité s'est soudainement développée, mais je vais l'expliquer car c'est incontournable.

L'ordinateur quantique de type modèle Rising est une machine dédiée qui se spécialise dans les problèmes d'optimisation de combinaison, de sorte que l'entrée est limitée à une forme spécifique. Le format d'entrée est un modèle utilisé en dynamique statistique appelé le ** modèle d'ingénierie **.

Lorsque vous le saisissez dans un ordinateur quantique (méthode du modèle Zing) sous la forme d'un modèle Zing, cela ressemble à une combinaison de variables qui minimise l'énergie de ce modèle.

La formule énergétique concrète est exprimée comme suit.

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

Soudain, une formule compliquée sort, quoi? Je me sens. Je ne suis pas sûr de l'explication théorique, je vais donc l'omettre ici. Sachez simplement que ** $ H $ est représenté par un polynôme allant jusqu'au 2ème ordre de $ \ sigma $ **.

Lors de la résolution, entrez le coefficient de $ \ sigma $ au format matrice, et il recherchera la combinaison de $ \ sigma $ qui minimise $ H $. Pour le moment, le premier objectif de la résolution avec un ordinateur quantique est de l'exprimer avec un polynôme de degré maximum 2 de $ \ sigma $.

QUBO

QUBO est un autre modèle similaire au modèle Rising, et l'énergie est exprimée par la formule suivante.

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

La seule différence avec le modèle Rising est que la variable a été remplacée de $ \ sigma $, qui prend $ \ pm 1 $, à $ x $, ce qui prend $ 0,1 $.

QUBO sera utilisé pour cette optimisation de cours Disney.

Écoulement brutal

Formuler l'optimisation des cours de Disney comme un problème d'optimisation de combinaison dans QUBO
Résoudre en fait avec un ordinateur (quantique)
Essayez d'en faire une application Web

Formulation du problème

En formulant le problème, nous envisagerons d'utiliser la figure suivante.

Les cercles de la figure ci-dessus correspondent à la variable binaire $ x_ {i, j} \ (1 \ leq i, j \ leq 4) $ dans QUBO. «Quelle attraction utiliser» correspond à la ligne, et «Quelle attraction utiliser» correspond à la colonne. $ i $ Représente s'il faut utiliser l'attraction $ j $ comme matrice.

Dans le cas de la figure ci-dessus, le cours est exprimé dans l'ordre: Haunted Mansion → Pooh's Honey Hunt → Space Mountain → Splash Mountain.

Je ne pense qu'à 4 attractions, mais il y a 65536 combinaisons de 4 × 4 = 16 $ x $ en 2 à la 16e puissance. L'ordinateur quantique trouve la combinaison de $ x $ qui minimise l'énergie $ H $ indiquée par QUBO à partir de ces 65536 combinaisons et la renvoie au format matriciel comme indiqué dans la figure ci-dessus. Je vais.

En d'autres termes, si l'expression qui minimise $ H $ dans le cours idéal peut être exprimée en utilisant $ x $ (second ordre ou moins), elle peut être optimisée par un ordinateur quantique. Généralement, quand vous pensez à $ H $, vous pensez aux termes d'objectif et de contrainte comme les termes qui composent $ H $.

Article	rôle
Objectif	Le terme cible que vous souhaitez maximiser ou minimiser. Réglez de sorte que meilleur est le résultat, plus la valeur est petite.
Contrainte	Le terme minimum si la contrainte est satisfaite. Si la contrainte est violée, la valeur est définie pour être grande comme pénalité.

Après cela, nous considérerons $ H $ basé sur ↑. Cependant, le nombre d'attractions utilisées (nombre de lignes) et le nombre d'attractions (nombre de colonnes) sont généralisés à $ n et m $, respectivement. (Dans la figure, pour plus de commodité, $ n = m = 4 $)

Objectif

Au début, j'ai mentionné que je voulais raccourcir le temps d'attente et la distance parcourue, donc cela semble être le but, mais quand je vais réellement à Disneyland, je ne pense pas qu'il y ait des gens qui disent: "Je veux attendre dans les 3 heures au total!"

En réalité, je pense que le but est "Je veux faire beaucoup d'attractions!" Cependant, la qualité ainsi que la quantité doivent être considérées. Je ne veux pas aller 10 fois chez Minnie car le temps d'attente est court. Par conséquent, nous fixons 10 niveaux de satisfaction pour chaque attraction et visons à ** maximiser la satisfaction totale **.

Si le niveau de satisfaction de l'attraction $ j $ est $ s_j \ \ (1 \ leq j \ leq n, 1 \ leq s_j \ leq 10) $, le niveau de satisfaction totale $ S $ est le suivant.

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

Cela ressemble à ceci sur la figure.

Cette fois, le but est de maximiser le niveau de satisfaction totale, mais comme le terme objectif doit être défini de sorte que la valeur devienne plus petite à mesure que le résultat est meilleur, le terme objectif $ H_ {aim} $ est le code inversé. Définir comme.

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

Contrainte A

Maintenant que les objectifs sont décidés, que se passe-t-il si on les optimise pour l'instant? Il y a une forte probabilité qu'une telle solution soit obtenue.

C'est vrai. La satisfaction sera maximisée si vous les utilisez tous. Cependant, cela signifie que vous utiliserez 4 attractions en même temps et que le parcours n'a pas été établi.

Par conséquent, nous avons défini une restriction ** selon laquelle l'utilisation de plusieurs attractions en même temps est interdite **. Cela signifie qu'il n'y a toujours qu'un seul cercle bleu sur chaque ligne. Cette contrainte est une contrainte one-hot qui apparaît fréquemment dans QUBO et est exprimée par la formule suivante.

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

Cela ressemble à ceci sur la figure.

Dans la figure ci-dessus, il y a deux cercles bleus sur la deuxième ligne et $ H_ {a} = 1 $ en raison d'une violation de contrainte. Si la contrainte est remplie, $ H_ {a} $ aura une valeur minimale de 0.

Contrainte B

Et si nous optimisions avec l'objectif et la contrainte A? Vous obtiendrez probablement une solution comme celle-ci. (* Les nombres entre parenthèses sont des niveaux de satisfaction)

Bien qu'il soit établi comme un parcours par la contrainte A, c'est un parcours audacieux avec 4 montagnes de splash consécutives. Il est naturel que Splash Mountain ait le plus haut niveau de satisfaction. Cependant, quelle que soit la popularité de l'attraction, ce n'est pas un bon parcours à parcourir quatre fois.

Par conséquent, si vous utilisez l'attraction plusieurs fois, définissez une contrainte selon laquelle le niveau de satisfaction diminuera de 3 à chaque fois que vous l'utiliserez. Par exemple, si vous utilisez Splash Mountain 3 fois, votre satisfaction diminuera, par exemple 10 pour la première fois, 7 pour la deuxième fois et 4 pour la troisième fois. De cette façon, le troisième niveau de satisfaction est de 4, donc Space Mountain (6) et Haunted Mansion (5) seront sélectionnés.

Bien que ce soit une contrainte, le terme objectif $ H_ {aim} $ est modifié car il est lié au calcul de la satisfaction totale.

La politique est de calculer le niveau de satisfaction totale d'une attraction et de le résumer pour toutes les attractions. Le nombre de fois qu'une certaine attraction $ a $ est utilisée $ k_ {a} $ est

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

Ce sera. Puisque le niveau de satisfaction de l'attraction $ a $ diminue de 3 à chaque fois qu'il est utilisé, il peut être considéré comme une séquence d'égalité avec le premier terme $ s_a $ tolérance-3, et le total $ S_ {a} $ est exprimé par la formule suivante. Je vais. (Somme de la séquence d'égalité)

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

Cela ressemble à ceci lorsque vous utilisez Splash Mountain trois fois.

Cette somme de toutes les attractions est la satisfaction totale, donc

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)

Ce sera. Comme pour Premier objectif défini, définissez le code inversé comme objectif.

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)

Contrainte C

Que se passe-t-il si vous optimisez en utilisant les objectifs nouvellement définis? Voici un exemple de la solution optimale.

Maintenant que le parcours est devenu assez décent, pensons à la distance parcourue. La relation de position de chaque attraction et le parcours dans la figure ci-dessus sont les suivantes.

Puisqu'il s'agit d'un diagramme schématique, il diffère de la relation de position réelle, mais la relation de grandeur de la distance parcourue est correctement exprimée. Si l'ordre de Space Mountain et Haunted Mansion est inversé, la distance parcourue sera plus courte.

Comme mentionné ci-dessus, il est idéal de raccourcir la distance parcourue, mais il n'est pas réaliste de vouloir spécifiquement maintenir la distance totale parcourue à moins de 〇〇m.

Par conséquent, définissez une contrainte selon laquelle le temps total requis est de XX heures **. Si vous calculez le temps de trajet et le temps d'attente et exprimez cette contrainte, vous maximiserez la satisfaction totale dans un temps limité, donc le temps de trajet et le temps d'attente doivent être naturellement raccourcis.

En exprimant cette contrainte, les trois suivants sont définis.

Durée de séjour prévue (minutes): $ t_ {max} $ --Attraction $ j $ cost (= temps d'attente + temps requis) (minutes): $ c_ {j} \ (1 \ leq j \ leq n) $ --Temps de trajet (minutes) entre deux attractions $ i, j $: $ d_ {i, j} \ (1 \ leq i, j \ leq n) $

Divisez la durée totale du trajet en ** «coût total des attractions à utiliser» ** + ** «durée totale du trajet» **.

Premièrement, le coût total de l'attraction à utiliser $ C $ peut être exprimé comme suit de la même manière que Premier objectif défini. Je viens de remplacer la satisfaction $ s $ par le coût $ c $.

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

Ensuite, le temps de trajet total $ D $ est [Problème de voyageur de commerce](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 Il peut être exprimé comme suit de la même manière que% E9% A1% 8C). (J'ai abandonné car c'était difficile à exprimer dans la figure ... Si vous voulez comprendre, veuillez vérifier le problème du voyageur de commerce)

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

Définissez la différence entre le temps de trajet total $ (C + D) $ et le temps de séjour estimé $ t_ {max} $ comme contrainte $ H_ {b} $.

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} $ sert de contrainte car la valeur augmente comme pénalité si la durée totale requise dépasse la durée de séjour prévue. Cependant, plus le temps de trajet total est court, plus le $ H_ {b} $ sera petit, il sera donc plus facile de choisir un parcours avec un temps de trajet total plus court. Ceci sera ajusté avec les hyper paramètres décrits plus loin.

Contrainte D

Optimisé en ajoutant la contrainte $ H_ {b} $, cela ressemble à ceci.

Vous êtes venu pour aller à Haunted Mansion en premier, compte tenu de la distance correctement. Cependant, je crains que Splash Mountain continue.

D'un point de vue informatique, si vous roulez en continu, le temps de trajet entre eux sera de 0, donc si vous l'utilisez plusieurs fois, il sera continu. Même si vous pouvez rouler deux fois, vous voulez éviter de rouler en continu si possible.

Par conséquent, définissez une restriction selon laquelle ** la même attraction ne doit pas être utilisée consécutivement **. Cela correspond au fait que les cercles bleus ne sont pas adjacents dans la direction de la colonne et s'exprime par la formule suivante.

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

Cela ressemble à ceci sur la figure.

Dans la figure ci-dessus, il y a une partie où un cercle bleu est adjacent dans la première colonne, et $ H_ {c} = 1 $ en raison d'une violation de contrainte. Si la contrainte est remplie, $ H_ {c} $ aura une valeur minimale de 0.

Contrainte E

Depuis que j'ai envisagé quatre attractions jusqu'à présent, cela devient soudainement un parcours comme Splash Mountain. Mais dans le cours réel, vous devez entrer par l'entrée et revenir à l'entrée.

Par conséquent, nous allons définir une contrainte qui ** utilise l'entrée au début et à la fin du cours **. L'entrée est également considérée comme une attraction et ajoutée comme une rangée. La satisfaction est mise à 0 car il n'est pas nécessaire de l'utiliser au milieu du cours. En supposant que l'entrée se trouve dans la première colonne, cette contrainte est exprimée par la formule suivante.

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

Cela ressemble à ceci sur la figure. Si le premier $ (x_ {1,1}) $ et le dernier $ (x_ {5,1}) $ de la première colonne sont des cercles bleus, la contrainte est satisfaite.

Si la contrainte est satisfaite, $ H_ {d} $ aura une valeur minimale de 0.

Résumé de la formulation

Cela fait longtemps, mais maintenant je recherche une voie assez raisonnable. La formulation de l'optimisation des cours de Disney est résumée ci-dessous.

Des données d'entrée

variable	Contenu
n	Nombre d'attractions utilisées dans un parcours (combien vous voulez monter)
m	Nombre d'attractions (Tokyo Disneyland: 34）
t_{max}	Temps de séjour prévu(Minutes)
s_{j}	Attractionsjla satisfaction(1 \leq j \leq n, 1 \leq s_{j} \leq 10)
c_{j}	AttractionsjCoût(Minutes)　(1 \leq j \leq n)
d_{i,j}	Attractionsi,jTemps de trajet entre(Minutes)　(1 \leq i,j \leq n)

Objectif

--Maximiser la satisfaction totale

Contrainte

N'utilisez pas plusieurs attractions en même temps
Si vous utilisez l'attraction plusieurs fois, le niveau de satisfaction diminuera de 3 à chaque fois que vous l'utiliserez.
Temps total requis dans le temps de séjour prévu
L'utilisation continue de la même attraction est interdite --Utiliser l'entrée au début et à la fin du cours

Fonction énergétique

\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}

La fonction d'énergie finale $ H $ ressemble à ceci: $ \ Alpha, \ beta, \ gamma, \ delta $ sont des hyperparamètres positifs qui représentent des poids de contrainte.

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

Essayez de résoudre avec un ordinateur (quantique)

Résolvons-le en fait en utilisant la fonction d'énergie formulée. Cette fois, nous nous concentrerons sur 10 attractions populaires sélectionnées par le dogmatisme et les préjugés.

Commencez par préparer les données d'entrée suivantes.

Pour le temps d'attente, je me suis référé au site ici. Utilise le temps d'attente quotidien moyen pour chaque attraction sur les niveaux de congestion normale du samedi au dimanche. (Le temps d'attente, mais les données de séries chronologiques qui changent d'instant en instant, sont effectuées à tout moment pour la simplicité du calcul, nous supposons un temps d'attente constant.) Le temps requis sera celui affiché sur le site officiel de Disney. Le coût est le temps d'attente + le temps requis, et la satisfaction est mon préféré.

Lorsque j'ai eu des problèmes parce que je ne trouvais pas les données sur le temps de trajet entre les attractions, un ami qui aime Disney a coopéré et a calculé la distance entre les attractions. Lorsqu'on lui a demandé comment cela avait été calculé, il a dit qu'il avait défini le point de branchement de chaque attraction et passage comme un nœud sur Google Maps et avait trouvé la distance la plus courte par la méthode Dyxtra. De plus, comme il y a certains passages que seuls les acteurs peuvent traverser avec seulement Google Maps, c'est la première fois de faire une carte des seuls passages que les invités peuvent traverser sur la base de Google Maps. C'est effrayant d'aimer la science Disney ... ↑ Une carte créée par un ami pour trouver la distance la plus courte entre les attractions de Dyxtra. Est-ce que quelqu'un sait que c'est Disneyland en regardant ça ...

Maintenant que les données d'entrée sont prêtes, convertissez-les au format à entrer dans l'ordinateur quantique. À l'origine, j'ai réussi à étendre $ H $ pour créer une matrice de coefficients (matrice QUBO) des termes du premier et du deuxième ordre de $ x $, mais cette fois j'ai généré une matrice QUBO avec un code hautement lisible. J'ai utilisé la bibliothèque python pyqubo.

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() #Temps de trajet en supposant une vitesse de marche de 80 m / min(Minutes)Convertir en
n = 12
m = len(c)
t_max = 60 * 12
x = Array.create('x', (n, m), 'BINARY')

#Objectif
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))

#L'utilisation de plusieurs attractions en même temps est interdite
H_a = Constraint(Sum(0, n, lambda i: (1 - Sum(0, m, lambda j: x[i,j])) ** 2), 'alpha')

#Durée totale du trajet pendant la durée de séjour prévue
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')

#L'utilisation continue de la même attraction est interdite
H_c = Constraint(Sum(0, m, lambda j: Sum(0, n-1, lambda i: x[i,j] * x[i+1,j])), 'gamma')

#Utilisez l'entrée au début et à la fin du cours
H_d = Constraint(2 - x[0,0] - x[n-1,0], 'delta')

#Fonction énergétique(J'ai également pondéré les objectifs)
H = 30 * H_aim + Placeholder('alpha') * H_a + Placeholder('beta') * H_b + Placeholder('gamma') * H_c + Placeholder('delta') * H_d

#Hyperparamètres pondérés par contraintes
params = {
    'alpha': 60,
    'beta': 2,
    'gamma': 60,
    'delta': 100
}

#Générer une matrice QUBO
model = H.compile()
qubo, offset = model.to_qubo(feed_dict=params)

Vous pouvez obtenir le résultat optimisé en lançant le qubo généré dans la dernière ligne vers l'ordinateur quantique. Il existe une machine appelée D-Wave en tant qu'ordinateur quantique qui peut être généralement utilisé, mais D-Wave a une limitation sur le modèle QUBO qui peut être résolue, donc ce problème ne convient pas. Hmm.

Cette fois, j'ai utilisé Fujitsu Digital Annealer utilisé dans la recherche universitaire. Le recuit numérique est composé de circuits numériques inspirés des phénomènes quantiques, et n'est pas exactement un ordinateur quantique. Donc, il dit: "J'ai essayé de trouver la route optimale pour le pays des rêves par recuit quantique", mais je suis désolé c'est une arnaque au titre m (_ \ ) m Veuillez reconnaître qu'il s'agit d'une simulation de recuit quantique m ( _) m

Le code qui utilise Digital Annealer ne peut pas être publié car il utilise une bibliothèque privée, mais le résultat est le suivant.

Le temps de trajet total est supérieur à 10 minutes, mais c'est acceptable. Le réglage des hyperparamètres devrait l'améliorer. Je n'ai pas utilisé uniquement la chasse au miel de Pooh, mais c'est un résultat raisonnable car c'est le quatrième coût le plus élevé mais la satisfaction la plus faible.

Lorsque je dessine le parcours sur la carte Disney, il ressemble à ce qui suit. La flèche est un itinéraire rectiligne, donc ce n'est pas précis, mais c'est devenu un parcours maigre qui fait le tour du parc.

application Web

J'avais un ami amoureux de Disney qui a coopéré avec moi pour vérifier la validité du cours, mais à chaque fois que je changeais l'entrée sur le PC local et que je recalculais, il était difficile d'envoyer le résultat, alors j'en ai fait une application Web Je l'ai essayé.

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

Il existe également des données Disney Sea pour que vous puissiez essayer à la fois Terre et Mer!

Back end

J'ai utilisé Google Cloud Functions car je n'ai besoin que d'une API simple qui effectue le traitement d'optimisation et renvoie le cours.

C'est fondamentalement la même chose que l'implémentation python de [here](#solve with a quantum computer), satisfaction $ (s) $, nombre d'attractions utilisées $ (m) $, temps de séjour estimé $ (t_ { max}) $ est une entrée de la requête HTTP.

C'est le processus de recuit essentiel, mais j'ai dû penser à une alternative car je ne pouvais pas utiliser une machine de recherche dans mon application privée. Heureusement, SA (Simulated Annealing) est implémenté dans pyqubo, donc je l'ai utilisé sur Cloud Functions.

Vous pouvez facilement simuler la matrice QUBO générée avec le code suivant.

Bien sûr, ce n'est pas un recuit quantique 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)

Le résultat obtenu dans ↑ est bien mis en forme et transformé en une API qui renvoie le json suivant.

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

l'extrémité avant

Je n'avais besoin que du formulaire de saisie de temps et de satisfaction et de la possibilité d'accéder à l'API pour afficher les résultats.Je l'ai donc fait rapidement avec Nuxt + Vuetify, que je vois souvent récemment, et je l'ai hébergé en tant que SPA sur Firebase. (Favicon c'est Nuxt et c'est un peu gênant car ça donne une impression de Vuetify ...) Idéalement, je voulais dessiner un itinéraire sur la carte officielle de Disney. Quand j'ai contacté Tokyo Disney Resort pour le moment, c'était normalement NG. Cependant, il devrait s'appeler Disney, et il a également répondu poliment aux étudiants ludiques qui m'ont demandé d'utiliser l'image de la carte officielle.

Veuillez vous abstenir d'afficher l'image de la carte de la mer de Tokyo Disneyland sur le site Web des particuliers. Nous sommes désolés pour le désagrément que nous vous donnerons une telle réponse même si vous nous avez contactés, mais comprenez bien.

en conclusion

Puisque je fais du recuit quantique dans ma thèse de fin d'études, ma motivation initiale était de résoudre divers problèmes d'optimisation des combinaisons et de m'y habituer. Cependant, j'ai posé ce problème parce que je pensais que ce serait bien d'avoir un problème réaliste et intéressant si je pouvais le résoudre quand même.

Au début, j'avais l'intention de le faire aussi légèrement qu'une interruption de ma thèse de fin d'études, mais mon ami a coopéré avec moi de manière étonnante (la personne qui a calculé la distance), et le résultat était plus décent que je ne l'avais imaginé. J'ai pensé que je garderais ça ensemble.

Étant donné que Disney réel implique des éléments plus complexes, les problèmes suivants sont empilés en tant qu'application.

Le temps d'attente n'est pas traité comme des données de série chronologique (le même temps d'attente est utilisé quelle que soit l'heure à laquelle vous allez)
Ne pas considérer le passage rapide ――Nous ne considérons rien d'autre que les attractions telles que le déjeuner, le dîner et les spectacles

Bref, c'est toujours une putain d'appli, donc je pense la faire évoluer pendant mon temps libre.

Nous recherchons d'autres problèmes à résoudre avec le recuit quantique, donc si vous avez des idées intéressantes, écrivez-les dans les commentaires!