Une nouvelle approche pour résoudre les problèmes d’optimisation à l’aide des machines Boltzmann

Une nouvelle approche pour résoudre les problèmes d'optimisation à l'aide des machines Boltzmann

Gauche : utilisation de la logique numérique pour effectuer à la fois la phase de calcul avant (vérification) et inverse (solution). En haut à droite : l’échantillonneur recherche de manière probabiliste les meilleures solutions dans l’espace. En bas à droite : Une application importante est la résolution de facteurs pour les nombres premiers, un problème au cœur de la cryptographie moderne, et généralement considéré comme insoluble. Crédit : Patel, Canoza et Salahuddin.

Les machines d’Ising sont des architectures informatiques non conventionnelles basées sur des principes physiques, du nom du physicien allemand Ernst Ising. Ces dernières années, ils se sont révélés être des outils particulièrement prometteurs pour résoudre des problèmes d’optimisation combinatoire (CO) et créer des modèles artificiels du cerveau.

Une équipe de chercheurs du groupe de Sayeef Salahuddin, professeur distingué TSMC d’EECS à l’Université de Californie à Berkeley, a récemment exploré en profondeur le potentiel des machines Ising pour trouver des solutions à des problèmes d’optimisation complexes. Leur article le plus récent, publié dans Électronique naturelleont introduit une nouvelle machine d’Ising composée de nombreuses machines de Boltzmann restreintes (RBM), qui s’est avérée capable d’obtenir des résultats remarquables sur des tâches d’optimisation combinatoire complexes.

“Ces dernières années, beaucoup de travail a été consacré aux machines Ising pour accélérer les problèmes d’optimisation, sur lesquels notre travail s’appuie”, a déclaré à TechXplore Saavan Patel, l’auteur principal qui a réalisé l’étude. “Les principaux objectifs de notre étude étaient de montrer comment l’apprentissage automatique et l’accélération matérielle peuvent s’intégrer dans le cadre des machines Ising et accélérer les problèmes d’optimisation d’une manière inspirée par la logique numérique.”

Les machines de Boltzmann restreintes (RBM) sont des modèles génératifs et stochastiques basés sur des réseaux de neurones artificiels. Ces modèles peuvent très bien capturer des corrélations complexes et des schémas de distribution dans de grandes quantités de données d’entrée.

Les RBM reposent sur des activations binaires, contournant les multiplications matrice-vecteur directes qui sont généralement les plus exigeantes en termes de calcul pour les réseaux d’apprentissage en profondeur. Dans leur étude, Patel et ses collègues ont exploité cette caractéristique unique des modèles pour augmenter la vitesse à laquelle leur machine pouvait résoudre les problèmes d’optimisation.

“Notre algorithme fonctionne en utilisant les principes de base de la logique numérique d’une nouvelle manière”, a expliqué Patel. “Habituellement, les portes numériques ne fonctionnent que dans le sens direct, mais en utilisant des modèles graphiques probabilistes et l’apprentissage automatique, nous avons montré des moyens de les faire fonctionner en sens inverse. En utilisant ce principe, nous concevons nos circuits numériques probabilistes de manière à résoudre le sens direct. (“Cet ensemble d’entrées est-il une solution valide ?” ou “Qu’est-ce que 191 x 223 ?”), mais parce que le système est réversible, il peut également répondre au problème inverse beaucoup plus difficile (“Quels sont tous les ensembles d’entrées qui produire une solution valide ?” et “Que sont A et B tels que A x B = 42593 ?” ).”

La machine qu’ils ont développée a permis à Patel et à ses collègues de résoudre une variété de problèmes d’optimisation différents. Essentiellement, leur circuit fonctionne en évaluant initialement différentes solutions existantes, puis en essayant d’identifier lui-même de nouvelles solutions. Contrairement à d’autres solutions proposées précédemment, la plate-forme des chercheurs combine des approches de cartographie des problèmes, l’apprentissage automatique et des solutions matérielles.

“Grâce à notre approche logique numérique, nous avons pu montrer que nous pouvions résoudre deux types de problèmes” difficiles “”, a déclaré Patel. “Le premier est la satisfiabilité booléenne, qui constitue l’épine dorsale des problèmes d’optimisation combinatoire, et le second est le problème de factorisation d’entiers qui est à la base de l’algorithme de cryptographie RSA utilisé par les ordinateurs modernes. Le but était de montrer que cet outil fonctionne, et nous avons montré que nous pouvions résoudre des problèmes de factorisation plus importants que les méthodes proposées précédemment.”

Lors des premières évaluations, la machine créée par cette équipe de chercheurs a obtenu des résultats très prometteurs, résolvant des problèmes complexes d’optimisation combinatoire et de factorisation d’entiers. De plus, le matériel de support présenté dans le document pourrait trouver des solutions aux problèmes 10 000 fois plus rapidement qu’un processeur conventionnel.

À l’avenir, les machines d’Ising comme celle introduite par Patel et ses collègues pourraient être utilisées pour résoudre plus rapidement et plus efficacement un large éventail de problèmes complexes du monde réel, y compris les problèmes liés à la logistique ou à la fabrication, les problèmes de routage et la rupture de cryptographie. Dans leurs prochaines études, les chercheurs tenteront de faire évoluer leur machine afin qu’elle puisse effectuer des tâches d’optimisation de plus en plus volumineuses et complexes. De plus, ils aimeraient évaluer son potentiel pour résoudre d’autres types de problèmes.

“Nous concevons des systèmes FPGA plus grands et plus efficaces pour résoudre des problèmes plus importants, ainsi que des ASIC”, a ajouté Patel. “En termes de nouveaux domaines de problèmes, nous avons étudié des cartographies pour les problèmes de routage (comme le problème du voyageur de commerce), les problèmes de communication (comme le codage LDPC), les problèmes quantiques (comme la recherche de l’état fondamental des systèmes moléculaires) et d’autres problèmes d’optimisation ( par exemple, des solutions pour les problèmes MAX-CUT). Il y a beaucoup de nouvelles frontières pour ces systèmes et nous sommes ravis d’explorer de nouveaux espaces ! Notre objectif est de toujours résoudre les problèmes les plus difficiles, plus rapidement et de manière plus efficace.


Un nouveau processeur qui résout des problèmes mathématiques notoirement complexes


Plus d’information:
Saavan Patel et al, Machines de Boltzmann restreintes synthétisées logiquement et accélérées par le matériel pour l’optimisation combinatoire et la factorisation d’entiers, Électronique naturelle (2022). DOI : 10.1038 / s41928-022-00714-0

© 2022 Réseau Science X

Citation: Une nouvelle approche pour aborder les problèmes d’optimisation à l’aide de machines Boltzmann (2022, 28 mars) récupéré le 28 mars 2022 sur https://techxplore.com/news/2022-03-approach-tackle-optimization-problems-boltzmann.html

Ce document est soumis au droit d’auteur. En dehors de toute utilisation loyale à des fins d’étude ou de recherche privée, aucune partie ne peut être reproduite sans l’autorisation écrite. Le contenu est fourni seulement pour information.