Résoudre des problèmes d'optimisation combinatoire avec un système neuromorphique
Grâce à une nouvelle méthode d'optimisation mise en œuvre dans un réseau de neurones créé sur une puce électronique, des scientifiques du laboratoire Intégration du matériau au système et de l'université de Tokyo ont montré que des problèmes combinatoires jusqu'ici impossibles à résoudre par des ordinateurs conventionnels pourraient être traités en temps et ressources limités.
De nombreux systèmes, qu'il s'agisse de protéines, d'un portefeuille de placements financiers, ou d'un système modélisé par la physique statistique (verre de spins), peuvent être décrits comme un ensemble complexe d'éléments en interaction, dont on veut trouver la configuration qui minimise l'énergie totale. Un problème analogue à celui posé par des calculs d'optimisation combinatoire, comme par exemple l'organisation optimale des trajets d'un voyageur de commerce. Or, quand la taille du système augmente, ces problèmes deviennent rapidement impossibles à traiter par les ordinateurs conventionnels.
Une étude menée en collaboration par le laboratoire Intégration du matériau au système (IMS, CNRS/Université de Bordeaux/Bordeaux INP) et l'université de Tokyo1 , publiée dans la revue Communications Physics, a montré qu'une nouvelle méthode d'optimisation pourrait limiter la croissance du temps de résolution avec la complexité du système, et permettrait de résoudre des problèmes jusqu'ici insolubles.
Dans ces problèmes d'optimisation, l'état du système est représenté par un ''paysage énergétique'' comportant des ''vallées'' (des minima d'énergie) vers lesquelles tend l'énergie du système, comme une balle descend vers le point le plus bas d'un terrain. Cependant, les méthodes classiquement utilisées pour modéliser l'évolution du système (méthodes dites de relaxation) sont peu efficaces pour des systèmes complexes, car le ''paysage énergétique'' comprend des minima locaux qui empêchent d'atteindre rapidement la solution optimale.
La nouvelle méthode proposée s'inspire des réseaux de neurones. Baptisée « Contrôle chaotique de l'amplitude » (Chaotic amplitude control, CAC), elle permet d'atteindre des états d'énergie optimaux beaucoup plus rapidement. L'équipe de l'IMS a implémenté cette méthode, en utilisant un réseau neuromorphique, sur un système électronique numérique basse consommation de type FPGA (Field programmable gate array). Les FPGA, dans lesquels la mémoire est distribuée avec les unités de traitement, ont l'intérêt de paralléliser les calculs de manière similaire à un réseau de neurones. Les tests réalisés avec ces implémentations montrent que le temps nécessaire pour atteindre une solution optimale croît moins vite avec la complexité du système qu'en utilisant les méthodes d'optimisation traditionnelles.
Les scientifiques veulent maintenant évaluer la méthode du CAC sur des problèmes dix à cent fois plus complexes que ceux qu'ils ont pu traiter avec leur FPGA. En collaboration avec la société NTT, ils vont l'implémenter sur des circuits plus puissants, et en utilisant de multiples FPGA, afin d'obtenir un haut degré de parallélisation du calcul.
Par ailleurs, le contrôle chaotique de l'amplitude pourrait aussi faciliter la compréhension de certaines fonctions du cerveau humain. Des études vont être réalisées, en collaboration avec des spécialistes en neurosciences, sur la modélisation de l'apprentissage chez les nouveaux-nés.
Représentation schématique de la puce neuromorphique pour l'optimisation combinatoire, dont la mémoire est distribuée avec chaque unité de traitement, comme dans un réseau de neurones biologiques constitué de neurones reliés par des synapses.
© Communications Physics (2021) 4:266
Références :
Scaling advantage of chaotic amplitude control for high-performance combinatorial optimization
Timothée Leleu, Farad Khoyratee, Timothée Levi, Ryan Hamerly, Takashi Kohno & Kazuyuki Aihara
Communications Physics volume 4, Article number: 266 (2021)
https://doi.org/10.1038/s42005-021-00768-0
Article disponible sur la base d'archives ouvertes : Arxiv
- 1 En collaboration avec l’International research laboratory (IRL) Laboratory for Integrated Micro Mechatronics Systems (LIMMS, CNRS/Université de Tokyo) à Tokyo et le Research Laboratory of Electronics du MIT (Etats-Unis).