Skip to content
Logo csisimple

C Si Simple

Le réseau de connaissances pour les Pros !

Primary Menu
  • Technologie
  • Ordinateurs
  • Intelligence Artificielle
  • Home
  • Ordinateurs
  • La nature peut aider à résoudre les problèmes d’optimisation
  • Ordinateurs

La nature peut aider à résoudre les problèmes d’optimisation

5 novembre 2019 7 min read

Les meilleurs ordinateurs numériques d’aujourd’hui luttent encore pour résoudre, dans un délai pratique, une certaine classe de problèmes : les problèmes d’optimisation combinatoire, ou ceux qui impliquent de passer au peigne fin un large éventail de possibilités pour trouver la meilleure solution. Les ordinateurs quantiques ont le potentiel de s’attaquer à ces problèmes, mais l’augmentation du nombre de bits quantiques dans ces systèmes demeure un obstacle.

Aujourd’hui, les chercheurs du MIT Lincoln Laboratory ont mis au point une méthode alternative, basée sur l’analogique, pour accélérer le calcul de ces problèmes. Notre ordinateur fonctionne en  » informatisant avec la physique  » et utilise la nature elle-même pour aider à résoudre ces problèmes difficiles d’optimisation « , explique Jeffrey Chou, co-auteur principal d’un article sur le cet ouvrage publié dans Nature’s Rapports scientifiques. « Il est fait de composants électroniques standard, ce qui nous permet de faire évoluer notre ordinateur rapidement et à moindre coût en tirant parti de l’industrie existante des puces électroniques. »

Le problème d’optimisation combinatoire le plus connu est peut-être celui du vendeur itinérant. Le problème consiste à trouver le chemin le plus court qu’un vendeur peut prendre à travers un certain nombre de villes, en commençant et en finissant par la même ville. Cela peut sembler simple avec seulement quelques villes, mais le problème devient exponentiellement difficile à résoudre à mesure que le nombre de villes augmente, enlisant même les meilleurs supercalculateurs. Pourtant, les problèmes d’optimisation doivent être résolus quotidiennement dans le monde réel ; les solutions sont utilisées pour planifier les quarts de travail, minimiser les risques financiers, découvrir les médicaments, planifier les expéditions, réduire les interférences sur les réseaux sans fil, et bien plus encore.

« On sait depuis très longtemps que les ordinateurs numériques sont fondamentalement mauvais pour résoudre ce type de problèmes « , explique Suraj Bramhavar, également co-auteur principal. « De nombreux algorithmes qui ont été conçus pour trouver des solutions doivent sacrifier la qualité de la solution sur l’autel du temps. Trouver la solution optimale absolue prend un temps déraisonnablement long quand la taille du problème augmente. » Trouver de meilleures solutions et le faire en beaucoup moins de temps pourrait faire économiser des milliards de dollars aux industries. Ainsi, les chercheurs ont cherché de nouvelles façons de construire des systèmes conçus spécifiquement pour l’optimisation.

Trouver le rythme

La nature aime optimiser l’énergie ou atteindre ses objectifs de la manière la plus efficace et la plus distribuée possible. Ce principe peut être observé dans la synchronisation de la nature, comme les cellules cardiaques qui battent ensemble ou les bancs de poissons qui ne font qu’un. De même, si vous placez deux pendules sur la même surface, quel que soit le moment où les pendules individuelles sont mises en mouvement, elles seront éventuellement bercées dans un rythme synchronisé, atteignant leur sommet en même temps mais se déplaçant dans des directions opposées (ou déphasées). Ce phénomène a été observé pour la première fois en 1665 par le scientifique néerlandais Christiaan Huygens. Ces horloges sont un exemple d’oscillateurs couplés, disposés de telle sorte que l’énergie peut être transférée entre eux.

« Nous avons essentiellement construit une version électronique programmable de ce système (réglage de l’horloge) à l’aide d’oscillateurs non linéaires couplés « , explique M. Chou. vidéo YouTube de métronomes présentant un phénomène similaire. « L’idée est que si vous mettez en place un système qui code le paysage énergétique de votre problème, alors le système va naturellement essayer de minimiser l’énergie en synchronisant et, ce faisant, va s’installer sur la meilleure solution. Nous pourrons alors lire cette solution. »

Le prototype du laboratoire est un type de machine Ising, un ordinateur basé sur un modèle en physique qui décrit un réseau d’aimants dont chacun a une orientation magnétique « spin » qui ne peut pointer que vers le haut ou le bas. L’orientation finale de chaque pirouette dépend de son interaction avec toutes les autres pirouettes. Les interactions spin-spin individuelles sont définies avec un poids d’accouplement spécifique, qui indique la force de leur connexion. Le but d’une machine Ising est de trouver, grâce à un réseau de force d’accouplement spécifique, la configuration correcte de chaque rotation, vers le haut ou vers le bas, qui minimise l’énergie globale du système.

Mais comment une machine Ising peut-elle résoudre un problème d’optimisation ? Il s’avère que les problèmes d’optimisation peuvent être mappés directement sur le modèle Ising, de sorte qu’un ensemble de spins avec certains poids de couplage peut représenter chaque ville et les distances entre eux dans le problème du vendeur itinérant. Ainsi, trouver la configuration de pirouettes la moins énergivore dans le modèle Ising se traduit directement dans la solution pour l’itinéraire le plus rapide du vendeur. Cependant, résoudre ce problème en vérifiant individuellement chacune des configurations possibles devient prohibitif lorsque les problèmes atteignent des tailles même modestes.

Au cours des dernières années, des efforts ont été déployés pour construire des machines quantiques qui correspondent au modèle d’Ising, dont la plus remarquable est celle de la société canadienne D-Wave Systems. Ces machines peuvent offrir un moyen efficace de rechercher le grand espace de solution et de trouver la bonne réponse, bien qu’elles fonctionnent à des températures cryogéniques.

Le système du laboratoire effectue une recherche similaire, mais en utilisant des oscillateurs électroniques simples. Chaque oscillateur représente une rotation dans le modèle d’Ising, et prend également une phase binaire, où les oscillateurs qui sont synchronisés, ou en phase, représentent la configuration « spin up » et ceux qui sont déphasés représentent la configuration « spin down ». Pour configurer le système afin de résoudre un problème d’optimisation, le problème est d’abord mis en correspondance avec le modèle Ising, le traduisant en poids de couplage programmables reliant chaque oscillateur.

Avec les masses d’accouplement programmées, les oscillateurs peuvent fonctionner comme le bras de balancier de chaque horloge qui se déclenche. Le système se détend alors naturellement à son état énergétique global minimum. La lecture électronique de la phase finale de chaque oscillateur, représentant « spin up » ou « spin down », présente la réponse à la question posée. Lorsque le système s’est heurté à plus de 2 000 problèmes d’optimisation aléatoires, il a trouvé la bonne solution 98 % du temps.

Auparavant, les chercheurs de l’Université de Stanford a fait la démonstration d’une machine Ising qui utilise des lasers et de l’électronique pour résoudre des problèmes d’optimisation. Ce travail a révélé le potentiel d’une accélération significative par rapport à l’informatique numérique bien que, selon Chou, le système puisse être difficile et coûteux à mettre à l’échelle pour des tailles plus grandes. L’objectif de trouver une solution de rechange plus simple a enflammé les recherches du laboratoire.

Mise à l’échelle

Le circuit d’oscillateur individuel que l’équipe a utilisé dans sa démonstration est semblable aux circuits que l’on trouve à l’intérieur des téléphones cellulaires ou des routeurs Wi-Fi. Un ajout qu’ils ont fait est une architecture de barre transversale qui permet à tous les oscillateurs du circuit d’être directement couplés les uns aux autres. « Nous avons trouvé une architecture qui est à la fois évolutive pour la fabrication et qui peut permettre une connectivité complète à des milliers d’oscillateurs « , explique M. Chou. Un système entièrement connecté permet de l’adapter facilement à une grande variété de problèmes d’optimisation.

« Ce travail du Lincoln Laboratory utilise de manière innovante une architecture à barres transversales dans la construction d’une machine Ising analogique-électronique « , explique Peter McMahon, professeur adjoint de physique appliquée et d’ingénierie à l’Université Cornell qui n’a pas participé à ces recherches. « Il sera intéressant de voir comment les développements futurs de cette architecture et de cette plate-forme se dérouleront. »

La machine Ising prototype du laboratoire utilise quatre oscillateurs. L’équipe travaille actuellement à l’élaboration d’un plan pour adapter le prototype à un plus grand nombre d’oscillateurs, ou « nœuds », et le fabriquer sur une carte de circuit imprimé. « Si nous pouvons atteindre, disons, 500 nœuds, il y a une chance que nous puissions commencer à concurrencer les ordinateurs existants, et à 1 000 nœuds, nous pourrions être en mesure de les battre « , dit Bramhavar.

L’équipe voit une voie claire vers la mise à l’échelle parce que la technologie est basée sur des composants électroniques standard. C’est aussi extrêmement bon marché. Toutes les pièces de leur prototype se trouvent dans un laboratoire d’électrotechnique de premier cycle et ont été achetées en ligne pour environ 20 $.

« Ce qui m’excite, c’est la simplicité « , ajoute Bramhavar. « On s’attend à ce que les ordinateurs quantiques démontrent des performances étonnantes, mais les défis scientifiques et techniques nécessaires à leur mise à l’échelle sont assez difficiles. Démontrer ne serait-ce qu’une petite fraction des gains de performance envisagés avec les ordinateurs quantiques, mais en utilisant le matériel de l’industrie électronique existante, serait un énorme bond en avant. Exploiter le comportement naturel de ces circuits pour résoudre des problèmes réels présente une alternative très convaincante pour ce que pourrait être la prochaine ère de l’informatique. »

Continue Reading

Previous: Les robots autotransformateurs bloquent, sautent, tournent, retournent et s’identifient les uns les autres.
Next: Le système empêche les drones rapides de s’écraser dans des endroits peu familiers.

Articles Liés

L’initiative du MIT pour l’énergie accorde huit subventions de fonds d’amorçage pour les premières étapes de la recherche sur l’énergie du MIT 7 min read
  • Ordinateurs

L’initiative du MIT pour l’énergie accorde huit subventions de fonds d’amorçage pour les premières étapes de la recherche sur l’énergie du MIT

1 juillet 2020
medical-equipment-4099432_1920 Améliorer l’équité en matière de santé dans le monde en aidant les cliniques à faire plus avec moins 7 min read
  • Ordinateurs

Améliorer l’équité en matière de santé dans le monde en aidant les cliniques à faire plus avec moins

26 juin 2020
audience-1835431_1280 Identifier une mélodie en étudiant le langage corporel d’un musicien 4 min read
  • Ordinateurs

Identifier une mélodie en étudiant le langage corporel d’un musicien

26 juin 2020
Lancement du programme MIT-Takeda | MIT News 5 min read
  • Ordinateurs

Lancement du programme MIT-Takeda | MIT News

19 juin 2020
doctor-563428_1280 Apporter le pouvoir prédictif de l’intelligence artificielle aux soins de santé 7 min read
  • Ordinateurs

Apporter le pouvoir prédictif de l’intelligence artificielle aux soins de santé

19 juin 2020
Le MIT et Toyota publient un ensemble de données innovatrices pour accélérer la recherche sur la conduite autonome 4 min read
  • Ordinateurs

Le MIT et Toyota publient un ensemble de données innovatrices pour accélérer la recherche sur la conduite autonome

18 juin 2020

Articles récents

  • L’initiative du MIT pour l’énergie accorde huit subventions de fonds d’amorçage pour les premières étapes de la recherche sur l’énergie du MIT
  • Améliorer l’équité en matière de santé dans le monde en aidant les cliniques à faire plus avec moins
  • Identifier une mélodie en étudiant le langage corporel d’un musicien
  • Lancement du programme MIT-Takeda | MIT News
  • Apporter le pouvoir prédictif de l’intelligence artificielle aux soins de santé

Catégories

  • Entreprises
  • Intelligence Artificielle
  • Ordinateurs
  • Technologie
  • Magazine W30
  • Contact
Copyright © All rights reserved. | Magnitude by AF themes.