Black-box optimization using factorization and Ising machines

Cet article examine l'algorithme Factorization Machine with Quantum Annealing (FMQA), qui exploite les machines de factorisation comme modèles de substitution et les machines d'Ising pour résoudre efficacement des problèmes d'optimisation de boîte noire à grande échelle dans divers domaines, tout en fournissant les outils nécessaires et des exemples d'application pour faciliter son adoption immédiate.

L'essentiel

Imaginez que vous essayez de trouver la recette parfaite pour un gâteau, mais que vous n'avez ni livre de cuisine, ni liste d'ingrédients, et aucune idée du fonctionnement du four. Vous ne pouvez que cuire un gâteau, le goûter et obtenir une note. Si le gâteau est sec, vous obtenez une note basse ; s'il est délicieux, vous obtenez une note élevée. C'est ce que les scientifiques appellent l'Optimisation Boîte Noire. Vous essayez de trouver la meilleure « entrée » (ingrédients) pour obtenir la meilleure « sortie » (goût), mais la machine (le four) est un mystère.

Le problème est qu'il existe des milliards de combinaisons d'ingrédients possibles. Les essayer tous un par un prendrait une éternité. Essayer de deviner le prochain meilleur lot est difficile car vous ne connaissez pas les règles.

Cet article présente une nouvelle méthode ingénieuse pour résoudre ce mystère en utilisant deux outils principaux : une Machine de Devinettes Intelligente (appelée Machine de Factorisation) et un Moteur de Recherche Ultra-Rapide (appelé Machine d'Ising).

Voici comment cela fonctionne, étape par étape :

1. La Machine de Devinettes Intelligente (Le Surrogate)

Au lieu de cuire un vrai gâteau à chaque fois que vous voulez tester une recette, vous construisez un « jumeau numérique » du four. Vous cuisez quelques gâteaux, enregistrez les résultats et enseignez à un programme informatique (la Machine de Factorisation) à prédire la qualité d'une nouvelle recette basée sur les anciennes.

• L'Analogie : Pensez-y comme à un critique culinaire qui a goûté 100 gâteaux. Si vous lui dites : « J'utilise 2 œufs et 3 tasses de sucre », il peut deviner la note sans que vous ne cuisez réellement le gâteau.
• Le Problème : Même avec un critique intelligent, trouver la recette absolument meilleure parmi des milliards d'options reste un immense casse-tête. Si les ingrédients sont discrets (comme « ajouter 1 œuf » ou « ajouter 2 œufs », et non « ajouter 1,5 œuf »), le nombre de possibilités explose.

2. Le Moteur de Recherche Ultra-Rapide (La Machine d'Ising)

C'est ici que l'article devient passionnant. Les auteurs ont réalisé que la « Machine de Devinettes Intelligente » pouvait être traduite dans un langage qu'un type spécial d'ordinateur appelé Machine d'Ising comprend parfaitement.

• L'Analogie : Imaginez que la Machine d'Ising est un résolveur de labyrinthes géant et ultra-rapide. Habituellement, ces machines sont utilisées pour résoudre des énigmes complexes comme trouver le chemin le plus court pour un camion de livraison ou organiser des aimants.
• Le Tour de Magie : Les auteurs ont trouvé un moyen de transformer le problème de prédiction de la « Machine de Devinettes Intelligente » en un labyrinthe que la Machine d'Ising peut résoudre en un éclair. Au lieu que l'ordinateur devine et vérifie lentement, la Machine d'Ising trouve instantanément la combinaison d'ingrédients que le « Critique Intelligent » pense être la meilleure.

3. L'Algorithme « FMQA »

L'article appelle l'ensemble de ce processus FMQA (Machine de Factorisation avec Recuit d'Optimisation Quadratique).

• Le Flux :
  1. Cuire quelques gâteaux (rassembler des données).
  2. Entraîner le Critique Intelligent (Machine de Factorisation).
  3. Demander au Moteur de Recherche Ultra-Rapide (Machine d'Ising) de trouver la meilleure recette que le Critique peut imaginer.
  4. Cuire cette recette spécifique pour obtenir la vraie note.
  5. Retourner cette nouvelle note au Critique et répéter.

Pourquoi est-ce une grande nouvelle ?

Habituellement, trouver la meilleure recette dans une liste immense est incroyablement lent. L'article montre qu'en utilisant cette combinaison spécifique d'un « Critique » et d'un « Moteur de Recherche Ultra-Rapide », vous pouvez trouver d'excellentes solutions beaucoup plus rapidement qu'auparavant, même lorsque la liste des options est massive.

Exemples Réels de l'Article

Les auteurs n'ont pas seulement parlé de théorie ; ils ont testé cela sur de vraies « recettes » en science et en ingénierie :

• Concevoir des Super-Matériaux : Ils l'ont utilisé pour concevoir des « métamatériaux » (matériaux artificiels aux propriétés spéciales) pour refroidir des objets. Ils devaient arranger de petites tiges de différents matériaux. L'algorithme a trouvé un motif qui fonctionnait mieux que le hasard.
• Construire de Meilleures Couches : Ils ont conçu des couches de films pour des fenêtres qui laissent passer la lumière mais bloquent la chaleur. L'algorithme a déterminé l'ordre parfait des matériaux à empiler.
• Réparer les Feux de Circulation : Ils ont traité les feux de circulation comme un puzzle. L'objectif était de faire avancer les voitures plus rapidement dans une ville. L'algorithme a ajusté le timing des feux rouges et verts pour trouver un flux beaucoup plus fluide que les paramètres standards.
• Concevoir des Ailes d'Avion : Ils ont modifié la forme d'une aile pour la rendre plus efficace en vol (plus de portance, moins de traînée).
• Créer de Nouveaux Médicaments (Peptides) : Ils ont conçu de courtes chaînes de protéines (peptides) capables de tuer des bactéries sans nuire aux cellules humaines. C'est comme trouver une aiguille dans une botte de foin, mais l'algorithme en a trouvé quelques-unes qui fonctionnaient réellement lors des tests en laboratoire.

La Conclusion

L'article affirme qu'en combinant un type spécifique d'IA (la Machine de Factorisation) avec du matériel spécialisé (les Machines d'Ising), les scientifiques peuvent résoudre des problèmes de « Boîte Noire » beaucoup plus rapidement. C'est comme donner à un détective une loupe surpuissante qui met instantanément en évidence les indices les plus prometteurs, lui permettant de résoudre des crimes (ou de concevoir des matériaux) qui étaient auparavant trop complexes à élucider.

Les auteurs ont même publié des outils logiciels gratuits afin que d'autres scientifiques puissent utiliser cette combinaison « Critique Intelligent + Moteur de Recherche Ultra-Rapide » pour résoudre leurs propres énigmes difficiles.

Résumé technique

1. Énoncé du problème

L'optimisation de boîte noire (BBO) est un défi critique dans des domaines allant de la conception de matériaux et de la découverte de médicaments au réglage des hyperparamètres en apprentissage automatique. Dans la BBO, la fonction objectif $y(x)$ est une « boîte noire » où la forme fonctionnelle interne et les gradients sont inconnus ; seules les paires entrée-sortie sont disponibles.

• Le Défi : Les méthodes BBO traditionnelles, telles que l'optimisation bayésienne (BO), reposent sur des modèles de substitution (par exemple, des processus gaussiens) pour prédire les entrées optimales. Cependant, l'optimisation de la fonction d'acquisition (le critère de sélection de la prochaine entrée) devient computationnellement intraitable lorsque l'espace d'entrée est discret, de haute dimension ou combinatoire.
• Le Goulot d'étranglement : À mesure que le nombre d'entrées candidates augmente, la recherche exhaustive devient impossible (NP-difficile) et les méthodes basées sur le gradient échouent sur les variables discrètes. Les méthodes existantes peinent à explorer efficacement de grands espaces de recherche discrets pour trouver des optima globaux.

2. Méthodologie : L'algorithme FMQA

L'article propose l'algorithme FMQA (Factorization Machine with Quadratic-optimization Annealing). Cette approche combine un modèle de substitution spécifique en apprentissage automatique avec des machines d'Ising (IM) pour résoudre efficacement l'optimisation de la fonction d'acquisition.

A. Modèle de substitution : Machine de factorisation (FM)

Au lieu des processus gaussiens, FMQA utilise une Machine de factorisation (FM) comme modèle de substitution.

• Structure : La FM modélise la sortie $\bar{y}(x)$ comme un terme linéaire plus un terme d'interaction par paires :
  $$\bar{y}(x) = w_0 + \sum w_i x_i + \sum \sum \langle v_i, v_j \rangle x_i x_j$$
• Avantage : La FM peut être directement transformée en un modèle d'optimisation binaire quadratique sans contrainte (QUBO) (ou Hamiltonien d'Ising). Cela permet de résoudre le modèle de substitution lui-même comme un problème d'optimisation en utilisant des IM.
• Entraînement : Les FM sont entraînées efficacement par descente de gradient avec une complexité linéaire $O(NK)$, où$N$ est le nombre de caractéristiques et $K$ la dimension latente.

B. Moteur d'optimisation : Machines d'Ising (IM)

L'innovation centrale réside dans l'utilisation des IM pour trouver l'entrée $x$ qui maximise la fonction d'acquisition (ou minimise la prédiction négative) de la FM.

• Matériel/Logiciel : L'algorithme est agnostique quant à l'IM spécifique utilisé. Il prend en charge :
  • Recuits quantiques : par exemple, les systèmes D-Wave.
  • Recuits numériques : par exemple, le Fujitsu Digital Annealer.
  • Moteurs de recuit simulé : par exemple, le Fixstars Amplify Annealing Engine (basé sur GPU).
• Processus : La FM est convertie en QUBO $\rightarrow$ Résolue par IM pour trouver le vecteur binaire optimal $\rightarrow$ Décodée de retour dans l'espace d'entrée original.

C. Gestion des entrées non binaires (Stratégies de codage)

Puisque les IM fonctionnent sur des variables binaires, l'article détaille les méthodes de codage pour les problèmes d'optimisation généraux :

1. Variables binaires : Mappage direct (aucun codage nécessaire).
2. Variables entières :
   • Codage binaire : Représente les entiers comme des sommes de puissances de 2.
   • Codage One-Hot : Représente les entiers comme un seul '1' parmi $N$ bits (nécessite une contrainte $\sum x_i = 1$).
   • Codage par paroi de domaine : Un codage plus efficace pour les entiers qui réduit le nombre de bits par rapport au codage one-hot.
3. Structures complexes (Graphes, Chaînes, Images) :
   • Utilisation d'un Autoencodeur variationnel binaire (bVAE).
   • Le bVAE encode les entrées complexes (par exemple, les chaînes SMILES moléculaires, les images) dans un espace latent de variables binaires.
   • La FM est entraînée sur cet espace latent. L'IM optimise le vecteur binaire latent, qui est ensuite décodé vers la structure originale.

3. Contributions clés

1. Cadre algorithmique : Formalisation de l'algorithme FMQA, démontrant comment relier la BBO au matériel d'optimisation combinatoire (IM) via le substitut FM compatible QUBO.
2. Évolutivité : Démonstration que FMQA peut gérer des problèmes d'optimisation discrète à grande échelle (jusqu'à des milliers de bits) où la BO traditionnelle échoue en raison de la difficulté d'optimiser la fonction d'acquisition.
3. Écosystème logiciel : Introduction d'outils open-source pour démocratiser la technologie :
   • Paquet FMQA original : Une bibliothèque Python pour une mise en œuvre de base.
   • Amplify-BBOpt : Une bibliothèque spécialisée intégrant le SDK Fixstars Amplify, permettant aux utilisateurs de définir des variables continues et des contraintes (par exemple, one-hot) sans formulation manuelle de QUBO.
4. Étalonnage complet : Validation de l'approche à travers divers domaines, prouvant sa polyvalence au-delà des problèmes binaires simples.

4. Résultats et exemples d'application

L'article passe en revue des applications réussies dans la physique, la chimie, la science des matériaux et les sciences sociales :

• Optimisation binaire (Sans contraintes) :

  • Conception de métamatériaux : Optimisation de structures de refroidissement radiatif (24-60 bits) utilisant D-Wave 2000Q, trouvant des structures supérieures plus rapidement qu'une recherche aléatoire.
  • Matériaux en couches : Conception de films de refroidissement radiatif transparents haute performance (jusqu'à 48 bits) et de filtres spectraux à large angle, avec la fabrication réussie d'un matériau à 10 couches présentant des performances record.
  • Conception de polymères : Optimisation de polymères triblocs pour la conductivité thermique.
  • Sélection de caractéristiques : Sélection de sous-ensembles de caractéristiques optimaux pour prédire les propriétés mécaniques des polymères, surpassant LASSO.

• Optimisation binaire (Avec contraintes) :

  • Jonctions tunnel magnétiques (MTJ) : Optimisation d'arrangements atomiques avec une contrainte stricte sur le nombre d'ions spécifiques (par exemple, exactement 5 Mg et 5 Ge), utilisant des termes de pénalité dans le QUBO.
  • Configuration moléculaire : Optimisation de configurations atomistiques dans les molécules de pérylène pour la polarisabilité.
  • Évitement de résonance : Optimisation des emplacements des trous de montage sur les circuits imprimés pour maximiser la fréquence naturelle.

• Problèmes à variables entières :

  • Lasers à cristaux photoniques : Optimisation de paramètres structuraux continus (discrétisés en 44 bits) pour la puissance de sortie et la qualité du faisceau, surpassant l'optimisation par essaim de particules (PSO) et les algorithmes génétiques (GA).
  • Optimisation de forme d'aile : Optimisation de formes de profilés (100 bits) pour maximiser le rapport portance-traînée, réalisant une amélioration de 17 % par rapport à une recherche aléatoire.
  • Contrôle des feux de circulation : Optimisation de 960 variables binaires (représentant 16 intersections) pour maximiser la vitesse moyenne des véhicules dans une simulation urbaine.
  • Conception de carrosserie de véhicule : Résolution d'un benchmark multi-objectif pour les structures de véhicules avec 18 contraintes, obtenant de meilleures solutions de Pareto avec moins d'évaluations de fonction (900 contre 30 000) que NSGA-II.

• Structures complexes (bVAE) :

  • Émetteurs thermiques : Optimisation de formes topologiques 2D pour la thermophotovoltaïque utilisant un espace latent de 500 bits.
  • Conception moléculaire : Optimisation de molécules de type médicament (chaînes SMILES) pour plusieurs propriétés (LogP, QED, etc.) utilisant un espace latent de 300 bits.
  • Conception de peptides : Réalisation d'une optimisation multi-objectif pour des peptides antimicrobiens et non hémolytiques, synthétisant et validant avec succès deux nouveaux peptides.

5. Signification et perspectives

• Technologie clé pour les IM : L'article positionne FMQA comme une « application tueuse » pour les machines d'Ising, fournissant un flux de travail pratique et de bout en bout pour résoudre des problèmes BBO réels qui étaient auparavant intraitables.
• Vitesse et efficacité : En déchargeant l'optimisation de la fonction d'acquisition vers un matériel spécialisé (IM), FMQA réduit considérablement le temps de calcul nécessaire pour trouver des optima globaux dans des espaces discrets.
• Directions futures :
  • Avantage quantique : Bien qu'utilisant actuellement des recuits quantiques et numériques, le cadre est prêt pour les ordinateurs quantiques à portes (utilisant QAOA) à mesure que le nombre de qubits augmente.
  • Laboratoires autonomes : Les auteurs suggèrent d'intégrer FMQA avec des systèmes expérimentaux automatisés pour accélérer la découverte de matériaux et le développement de médicaments.
  • Évolutivité : Les travaux futurs visent à gérer des tailles de lots plus importantes et à développer des modèles de substitution d'ordre supérieur (HUBO) pour améliorer davantage la précision de prédiction et les performances des IM.

En conclusion, l'article établit FMQA comme un cadre robuste, polyvalent et hautement efficace pour l'optimisation de boîte noire, comblant efficacement le fossé entre la modélisation de substitution en apprentissage automatique et le matériel d'optimisation combinatoire.