Le laboratoire de science des données
Recuit d’inspiration quantique avec C# ou Python
Dr. James McCaffrey de Microsoft Research explique une nouvelle idée qui modifie légèrement le recuit simulé standard en empruntant des idées à la mécanique quantique.
Le but d’un problème d’optimisation combinatoire est de trouver le meilleur ordre d’un ensemble d’éléments discrets. Un défi d’optimisation combinatoire classique est le problème du voyageur de commerce (TSP). Pour TSP, vous souhaitez trouver l’ordre dans lequel visiter un ensemble de villes afin que la distance totale parcourue soit minimisée.
L’une des techniques les plus anciennes et les plus simples pour résoudre les problèmes d’optimisation combinatoire est appelée recuit simulé. Une idée relativement nouvelle consiste à modifier légèrement le recuit simulé standard en empruntant une ou plusieurs idées à la mécanique quantique. Ceci est parfois appelé recuit d’inspiration quantique. Notez que les algorithmes d’inspiration quantique n’utilisent pas de matériel informatique quantique. Les algorithmes d’inspiration quantique ne sont que des modifications d’algorithmes classiques existants et ils fonctionnent sur du matériel standard.
Une bonne façon de voir où va cet article est de jeter un coup d’œil à la capture d’écran d’un programme de démonstration dans Figure 1. La démo met en place un problème synthétique où il y a 40 villes, étiquetées de 0 à 39. La distance entre les villes est conçue de sorte que le meilleur itinéraire commence à la ville 0, puis visite chaque ville dans l’ordre. La distance totale de l’itinéraire optimal est de 39,0.
La démo définit des paramètres de recuit d’inspiration quantique de max_iter = 20_000, start_temperature = 100_000.0, alpha = 0,9990 et pct_tunnel = 0,10. Le recuit d’inspiration quantique est un processus itératif et max_iter est le nombre maximal de fois que la boucle de traitement s’exécutera. Les paramètres start_temperature et alpha contrôlent la manière dont la partie classique de l’algorithme de recuit explore les voies de solution possibles. Le paramètre pct_tunnel contrôle la fréquence d’utilisation de la partie d’inspiration quantique de l’algorithme.
La démo met en place une estimation initiale aléatoire du meilleur itinéraire comme [ 7, 34, 21 . . 9, 10 ]. Après avoir itéré 20 000 fois, la démo signale le meilleur itinéraire trouvé comme [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 16, 19, 18, 15, 14, 13, 12, 10, 11, 17, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39 ]. La distance totale requise pour visiter les villes dans cet ordre est de 61,5 et la solution est donc proche, mais pas aussi bonne que la solution optimale. Les 10 premières villes et les 20 dernières villes sont visitées dans le bon ordre mais les 10 villes du milieu ne sont pas visitées correctement.
Cet article suppose que vous avez une connaissance intermédiaire ou supérieure d’un langage de programmation de la famille C, de préférence C# ou Python, mais ne suppose pas que vous savez quoi que ce soit sur le recuit simulé. Le code source complet du programme de démonstration est présenté dans cet article, et le code est également disponible dans le téléchargement du fichier d’accompagnement.
Comprendre le recuit simulé classique
Le recuit d’inspiration quantique est une légère adaptation du recuit simulé classique. Supposons que vous ayez un problème d’optimisation combinatoire avec seulement cinq éléments, et où le meilleur ordre/permutation est [B, A, D, C, E]. Une approche primitive serait de commencer par une permutation aléatoire telle que [C, A, E, B, D] puis échangez à plusieurs reprises des paires d’éléments sélectionnées au hasard jusqu’à ce que vous trouviez le meilleur ordre. Par exemple, si vous permutez les éléments à [0] et [1]la nouvelle permutation est [A, C, E, B, D]. Vous répétez la génération de nouvelles permutations jusqu’à ce que vous trouviez un bon résultat.
Cette approche par force brute fonctionne s’il n’y a que quelques éléments dans la permutation du problème, mais échoue même pour un nombre modéré d’éléments. Pour le problème de démonstration avec n = 40 villes, il y en a 40 ! permutations possibles = 40 * 39 * 38 * . . * 1 = 815 915 283 247 897 734 345 611 269 596 115 894 272 000 000 000. Même si vous pouviez examiner un milliard de solutions candidates par seconde, vérifier toutes les permutations vous prendrait environ 9 000 000 000 000 000 000 000 000 000 d’années, ce qui est beaucoup plus long que l’âge estimé de l’univers (environ 14 000 000 000 d’années).
Pour comprendre le recuit d’inspiration quantique, vous devez d’abord comprendre le recuit simulé classique. Exprimé en pseudo-code, le recuit simulé classique est :
make a random initial guess permutation
set a large initial temperature
loop many times
swap two randomly selected elements of the curr guess
compute error of proposed candidate solution
if proposed solution is better than curr solution then
accept the proposed solution
else if proposed solution is worse then
sometimes accept solution anyway, based on curr temp
end-if
decrease temperature value slightly
end-loop
return best solution found
En échangeant deux éléments sélectionnés au hasard de la solution actuelle, une solution proposée adjacente est créée. La solution proposée adjacente sera similaire à la supposition actuelle, de sorte que le processus de recherche n’est pas complètement aléatoire. Une bonne solution actuelle conduira probablement à une bonne nouvelle solution proposée.
En acceptant parfois une solution proposée qui est pire que la supposition actuelle, vous pouvez éviter de vous retrouver piégé dans une solution bonne mais pas optimale. La probabilité d’accepter une solution moins bonne est donnée par :
accept_p = exp((err - adj_err) / curr_temperature)
où exp() la fonction mathématique exp(), err est l’erreur associée à la supposition actuelle, adj_err est l’erreur associée à la solution adjacente proposée et curr_temperature est une valeur telle que 1000.0.
Dans le recuit simulé, la valeur de température commence par une valeur élevée, telle que 1000000,0, puis est lentement réduite à chaque itération. Au début de l’algorithme, lorsque la température est grande, accept_p sera grand (proche de 1) et l’algorithme passera souvent à une solution moins bonne. Cela permet d’examiner de nombreuses permutations. Tard dans l’algorithme, lorsque la température est petite, accept_p sera petit (proche de 0) et l’algorithme passera rarement à une solution pire.
La réduction de température est contrôlée par la valeur alpha. Supposons que la température actuelle = 1000,0 et alpha = 0,90. Après la prochaine itération de traitement, la température devient 1000,0 * 0,90 = 900,0. Après la prochaine itération, la température devient 900,0 * 0,90 = 810,0. Après une troisième itération, la température devient 810,0 * 0,90 = 729,0. Etc. Des valeurs plus petites d’alpha diminuent la température plus rapidement.
Ajout d’un tunnel d’inspiration quantique
Le recuit d’inspiration quantique ajoute une légère touche au recuit simulé classique. En mécanique quantique, il existe une idée appelée effet tunnel quantique. En bref, et de manière très lâche, une particule quantique passera généralement de son état d’énergie actuel à un état d’énergie inférieur adjacent. Lorsqu’une particule rencontre une barrière potentielle, elle sera généralement bloquée, mais traversera parfois la barrière vers un état non adjacent.
Cet effet tunnel quantique peut être utilisé pour améliorer le recuit simulé classique. Les idées clés sont présentées dans le graphique Figure 2. Dans le recuit simulé classique pour TSP, les états sont des permutations de villes. Si vous passez uniquement de l’état actuel à un état adjacent (lorsque l’ordre d’une seule paire de villes est modifié), vous pouvez rester bloqué à une erreur minimale locale. Si vous autorisez le tunneling, vous pouvez faire un grand saut pour vous échapper et revenir sur la bonne voie pour trouver l’état avec l’erreur minimale globale.
Ainsi, l’effet tunnel d’inspiration quantique signifie simplement permettre parfois à une solution candidate d’être plus éloignée de la solution actuelle. Ceci peut être réalisé en échangeant plus que deux villes. Par exemple, si vous échangez 10 paires de villes sélectionnées au hasard, la permutation résultante sera plus éloignée de la permutation source que si vous échangez une seule paire de villes sélectionnées au hasard.
Au début de l’algorithme, lors de la création d’une solution candidate, vous pouvez échanger de nombreuses paires de villes, générant un candidat éloigné de la permutation actuelle. Plus tard dans l’algorithme, vous échangez moins de paires de villes. Exprimé en pseudo-code :
set pct_tunnel (comme 0.10) boucle plusieurs fois p = random in [0.0, 1.0)
if p < pct_tunnel then (do tunneling)
set num_swaps = large, based on pct iterations left
else
set num_swaps = 1 (no tunneling)
end-if
create candidate solution using num_swaps
apply classical annealing
end-loop
return best solution found
The Python version of the function that creates a candidate permutation-solution is:
def adjacent(route, n_swaps, rnd):
n = len(route)
result = np.copy(route)
for ns in range(n_swaps):
i = rnd.randint(n)
j = rnd.randint(n)
tmp = result[i]
résultat[i] = résultat[j]
résultat[j] = tmp renvoie le résultat
Le paramètre route est la solution actuelle. Le paramètre n_swaps spécifie le nombre de paires de villes à permuter lors de la création de la solution candidate. Le paramètre rnd est un objet générateur de nombres aléatoires local.
Une version C# équivalente de la fonction est :
static int[] Adjacent(int[] route, int numSwaps, Random rnd)
{
int n = route.Length;
int[] result = (int[])route.Clone();
for (int ns = 0; ns < numSwaps; ++ns) {
int i = rnd.Next(0, n);
int j = rnd.Next(0, n);
int tmp = result[i];
result[i] = result[j];
result[j] = tmp;
}
return result;
}
Le paramètre clé est le nombre de paires de villes à permuter. Le programme de démonstration calcule cela comme le pourcentage d'itérations restantes multiplié par le nombre total de villes. Par exemple, pour n = 40 villes, si max_iterations = 1000 et l'itération actuelle est de 300, alors il reste 700 / 1000 = 0,70 des itérations restantes, et le nombre d'échanges serait de 0,70 * 40 = 28.
Le programme de démonstration
Le programme complet de démonstration de recuit d'inspiration quantique utilisant Python, avec quelques modifications mineures pour économiser de l'espace, est présenté dans Liste 1. J'indente en utilisant deux espaces plutôt que les quatre espaces standard. Le caractère barre oblique inverse est utilisé pour la continuation de ligne afin de décomposer les longues instructions. Vous pouvez trouver une version C# équivalente du programme de démonstration sur mon blog.
Liste 1 : Le programme de recuit quantique pour le langage Python TSP
# tsp_quantum_annealing.py
# traveling salesman problem
# quantum inspired simulated annealing
# Python 3.7.6 (Anaconda3 2020.02)
import numpy as np
def total_dist(route):
d = 0.0 # total distance between cities
n = len(route)
for i in range(n-1):
if route[i] < route[i+1]:
d += (route[i+1] - route[i]) * 1.0
else:
d += (route[i] - route[i+1]) * 1.5
return d
def error(route):
n = len(route)
d = total_dist(route)
min_dist = n-1
return d - min_dist
def adjacent(route, n_swaps, rnd):
# tunnel if n_swaps > 1
n = len(route)
result = np.copy(route)
for ns in range(n_swaps):
i = rnd.randint(n); j = rnd.randint(n)
tmp = result[i]
result[i] = result[j]; result[j] = tmp
return result
def my_kendall_tau_dist(p1, p2):
# p1, p2 are 0-based lists or np.arrays
n = len(p1)
index_of = [None] * n # lookup into p2
for i in range(n):
v = p2[i]; index_of[v] = i
d = 0 # raw distance = number pair misorderings
for i in range(n):
for j in range(i+1, n):
if index_of[p1[i]] > index_of[p1[j]]:
d += 1
normer = n * (n - 1) / 2.0
nd = d / normer # normalized distance
return (d, nd)
def solve_qa(n_cities, rnd, max_iter, start_temperature,
alpha, pct_tunnel):
curr_temperature = start_temperature
soln = np.arange(n_cities, dtype=np.int64) # [0,1,2, . . ]
rnd.shuffle(soln)
print("Initial guess: ")
print(soln); print("")
err = error(soln)
iter = 0
interval = (int)(max_iter / 10)
num_swaps = n_cities
best_soln = np.copy(soln)
best_err = err
while iter < max_iter and err > 0.0:
# while iter < max_iter:
# pct left determines n_swaps determines distance
pct_iters_left = (max_iter - iter) / (max_iter * 1.0)
if pct_iters_left < 0.00001:
pct_iters = 0.00001
p = rnd.random() # [0.0, 1.0]
if p < pct_tunnel: # tunnel
num_swaps = (int)(pct_iters_left * n_cities)
if num_swaps < 1:
num_swaps = 1
else: # no tunneling
num_swaps = 1
adj_route = adjacent(soln, num_swaps, rnd)
adj_err = error(adj_route)
if adj_err < best_err:
best_soln = np.copy(adj_route)
best_err = adj_err
if adj_err < err: # better route so accept
soln = adj_route; err = adj_err
else: # adjacent is worse
accept_p = np.exp((err - adj_err) / curr_temperature)
p = rnd.random()
if p < accept_p: # accept anyway
soln = adj_route
err = adj_err
# else don't accept worse route
if iter % interval == 0:
(dist, nd) = my_kendall_tau_dist(soln, adj_route)
print("iter = %6d | " % iter, end="")
print("dist curr to candidate = %8.4f | "
% nd, end="")
print("curr_temp = %12.4f | "
% curr_temperature, end="")
print("error = %6.1f " % best_err)
if curr_temperature < 0.00001:
curr_temperature = 0.00001
else:
curr_temperature *= alpha
iter += 1
return best_soln
def main():
print("nBegin TSP using quantum inspired annealing ")
num_cities = 40
print("nSetting num_cities = %d " % num_cities)
print("nOptimal solution is 0, 1, 2, . . " +
str(num_cities-1))
print("Optimal solution has total distance = %0.1f "
% (num_cities-1))
rnd = np.random.RandomState(6)
max_iter = 20_000 # 120000 finds optimal solution
start_temperature = 100_000.0
alpha = 0.9990
pct_tunnel = 0.10
print("nQuantum inspired annealing settings: ")
print("max_iter = %d " % max_iter)
print("start_temperature = %0.1f "
% start_temperature)
print("alpha = %0.4f " % alpha)
print("pct_tunnel = %0.2f " % pct_tunnel)
print("nStarting solve() ")
soln = solve_qa(num_cities, rnd, max_iter,
start_temperature, alpha, pct_tunnel)
print("Finished solve() ")
print("nBest solution found: ")
print(soln)
dist = total_dist(soln)
print("nTotal distance = %0.1f " % dist)
print("nEnd demo ")
if __name__ == "__main__":
main()
.