Réseaux de neurones graphiques inspirés de la physique pour résoudre des problèmes d’optimisation combinatoire

Réseaux de neurones graphiques inspirés de la physique pour résoudre des problèmes d'optimisation combinatoire

Visualisation d’un exemple de solution à l’instance de problème de référence Maximum Cut G81, à partir de l’ensemble de données Gset. Crédit : Schuetz, Brubaker & Katzgraber.

Les problèmes d’optimisation combinatoire sont des problèmes complexes avec un ensemble discret mais large de solutions possibles. Certains des exemples les plus connus de ces problèmes sont le voyageur de commerce, le bin-packing et les problèmes de planification des ateliers.

Des chercheurs de l’Amazon Quantum Solutions Lab, qui fait partie des laboratoires de technologies informatiques intelligentes et avancées d’AWS, ont récemment développé un nouvel outil pour résoudre les problèmes d’optimisation combinatoire, basé sur les réseaux de neurones graphiques (GNN). L’approche développée par Schuetz, Brubaker et Katzgraber, publiée dans Intelligence des machines naturellespourrait être utilisé pour optimiser une variété de problèmes du monde réel.

“Notre travail a été très inspiré par les besoins des clients”, a déclaré à TechXplore Martin Schuetz, l’un des chercheurs qui a mené l’étude. “Dans notre travail quotidien au Amazon Quantum Solutions Lab, nous interagissons avec de nombreux clients dans divers secteurs verticaux au cours de leur parcours pour se préparer au quantum, c’est-à-dire se préparer à un avenir où cette technologie émergente sera commercialement viable. La plupart des cas d’utilisation des clients impliquent une combinaison problèmes d’optimisation.”

Dans le contexte des services aux consommateurs, les problèmes d’optimisation combinatoire peuvent prendre de nombreuses formes différentes. Deux exemples notables de ces problèmes sont les problèmes d’optimisation de portefeuille dans la finance et les tâches de planification d’ateliers dans la fabrication. Le terme optimisation de portefeuille fait référence au processus par lequel on sélectionne le meilleur portefeuille ou la meilleure répartition des actifs pour une situation spécifique parmi un ensemble de portefeuilles disponibles.

Les problèmes de planification de l’atelier de travail, d’autre part, se produisent dans les cas où un ensemble de travaux ou de tâches doit être effectué et où il existe un ensemble limité de ressources/outils pour effectuer ces tâches. Dans ces cas, on pourrait demander de trouver un calendrier optimal qui utilise les outils disponibles pour effectuer les tâches en aussi peu de temps que possible.

Comme la technologie quantique en est encore à ses premiers stades de développement, les chercheurs ont essayé de développer des outils d’optimisation qui ne reposent pas entièrement sur les ordinateurs quantiques, du moins jusqu’à ce que ces ordinateurs soient devenus commercialement viables. Dans leur article, Schuetz et ses collègues ont ainsi introduit une technique d’optimisation basée sur les GNN inspirée de la physique.

“Compte tenu de leur évolutivité inhérente, les GNN inspirés de la physique peuvent être utilisés aujourd’hui pour résoudre approximativement (à grande échelle) des problèmes d’optimisation combinatoire avec des modèles natifs quantiques, tout en aidant nos clients à se préparer au quantique en utilisant la représentation mathématique que les dispositifs quantiques comprennent”, dit Brubaker.

L’approche développée par Schuetz et ses collègues identifie d’abord l’hamiltonien (c’est-à-dire la fonction de coût) qui code les problèmes d’optimisation spécifiques que l’on essaie de résoudre. Ensuite, il associe les variables de décision correspondantes aux nœuds d’un graphe.

“Notre idée clé est alors de définir les problèmes d’optimisation combinatoire comme des tâches de classification de nœuds non supervisées dans lesquelles le GNN apprend les attributions de couleur (en d’autres termes, de spin ou de variable) pour chaque nœud”, a expliqué Schuetz. “À cette fin, le GNN est formé de manière itérative via une fonction de perte personnalisée qui code le problème d’optimisation spécifique d’intérêt, dans une correspondance biunivoque avec l’hamiltonien d’origine, offrant ainsi un choix de principe pour la fonction de perte du GNN.”

Une fois le GNN formé, l’équipe a projeté les valeurs finales pour les affectations de nœuds souples qu’elle a produites aux affectations de classes dures. Cela leur a finalement permis de résoudre approximativement des problèmes d’optimisation combinatoire à grande échelle.

L’approche proposée par Schuetz et ses collègues présente plusieurs avantages par rapport aux autres méthodes pour résoudre les problèmes d’optimisation combinatoire. Plus particulièrement, leur méthode est hautement évolutive, ce qui signifie qu’elle pourrait être utilisée pour optimiser par calcul des problèmes complexes avec des centaines de millions de nœuds.

“Notre optimiseur GNN est basé sur une relation mathématique directe et générale entre les hamiltoniens de spin d’Ising prototypiques et la fonction de perte différentiable avec laquelle nous entraînons le GNN, fournissant ainsi un cadre unificateur pour une large classe de problèmes d’optimisation combinatoire et ouvrant la puissante boîte à outils de physique aux approches modernes d’apprentissage en profondeur », a déclaré Brubaker. “En fusionnant des concepts de la physique avec des outils d’apprentissage automatique modernes, nous proposons un solveur simple, générique et robuste qui ne repose pas sur des fonctions de perte artisanales.”

Remarquablement, l’approche conçue par Schuetz et ses collègues peut résoudre approximativement les problèmes d’optimisation sans avoir besoin d’étiquettes de formation, qui sont une exigence clé pour toutes les méthodes d’apprentissage supervisé. Comme la technique présente des problèmes d’optimisation comme des hamiltoniens d’Ising, elle peut également fonctionner nativement sur du matériel quantique.

“Nous fournissons un cadre unificateur et interdisciplinaire pour les problèmes d’optimisation qui intègre les connaissances de la physique et les outils de l’apprentissage en profondeur moderne”, a expliqué Schuetz. “Avec ce cadre, nous avons à notre disposition un outil qui s’applique largement aux problèmes canoniques NP-difficiles ; les exemples les plus importants incluent la coupe maximale, la couverture minimale des sommets, les problèmes d’ensemble indépendants maximaux, ainsi que les verres de spin d’Ising.”

À l’avenir, la nouvelle méthode basée sur GNN introduite par cette équipe de chercheurs pourrait être utilisée pour résoudre une variété de problèmes d’optimisation complexes et réels. Comme il est intrinsèquement évolutif, Amazon Quantum Solutions Lab et AWS prévoient de le proposer à leurs clients comme un outil qui pourrait faciliter leur transition vers les technologies quantiques. En fait, leur technique pourrait permettre aux clients d’aborder à la fois les problèmes liés à des cas d’utilisation spécifiques dans un cadre de modélisation quantique natif, à la fois à petite échelle et à une échelle pertinente pour l’industrie.

“À l’avenir, nous continuerons à rechercher des questions de recherche conceptuelles, théoriques et plus appliquées. D’une part, nous avons plusieurs idées sur la façon d’améliorer et d’étendre les capacités de l’optimiseur GNN proposé, et d’autre part, il y a de nombreux cas d’utilisation appliqués que nous pouvons essayer de résoudre avec ce nouvel outil. Nous continuerons à utiliser les commentaires des clients pour nous aider à guider et à prioriser notre programme de recherche », a déclaré Katzgraber.


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


Plus d’information:
Martin JA Schuetz et al, Optimisation combinatoire avec des réseaux de neurones graphiques inspirés de la physique, Intelligence des machines naturelles (2022). DOI : 10.1038/s42256-022-00468-6

© 2022 Réseau Science X

Citation: Réseaux de neurones graphiques inspirés de la physique pour résoudre les problèmes d’optimisation combinatoire (2022, 25 mai) récupéré le 25 mai 2022 sur https://techxplore.com/news/2022-05-physics-inspired-graph-neural-networks-combinatorial.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.