Solveur analogique surpasse les ordinateurs numériques sur l'optimisation NP-difficile

• Des chercheurs construisent un nouveau système qui peut résoudre un problème d'optimisation discrète quintessentiel, appelé MaxSAT.
• Ce solveur analogique performe mieux que les ordinateurs numériques, et peut être étendu à d'autres problèmes d'optimisation.

Les ordinateurs numériques d'aujourd'hui effectuent bien la plupart des tâches. Ils sont parfaits pour certains calculs, le traitement de texte, la navigation web et les arts graphiques. Mais comme ils reposent sur le code binaire – 0 et 1 – ils ne sont pas idéaux pour résoudre tous les problèmes.

L'informatique numérique a presque atteint son potentiel maximal, et c'est pourquoi certains mathématiciens ont commencé à s'intéresser à la renaissance de l'informatique analogique. Elle peut aider à faire avancer le calcul au-delà du cadre numérique.

Récemment, des chercheurs de l'Université Notre-Dame et de l'Université Babeș-Bolyai, Roumanie, ont développé un nouveau solveur analogique qui peut évaluer les meilleures solutions des problèmes NP-difficiles.

Problème NP-difficile signifie qu'il n'existe aucun algorithme capable de résoudre le problème en temps polynomial. Le temps requis pour atteindre la solution augmente exponentiellement avec la taille du problème. Habituellement, ces problèmes sont associés à l'imagerie médicale, la bioinformatique, le repliement des protéines et l'ordonnancement.

Les chercheurs ont testé leur solveur analogique sur une large gamme de problèmes NP-difficiles, et ils ont découvert que cette nouvelle méthode a le potentiel de conduire à de meilleures solutions en moins de temps.

Pourquoi l'informatique analogique ?

Les ordinateurs analogiques étaient extrêmement populaires au milieu du 20e siècle. Chaque grande administration et entreprise concernée par les problèmes de dynamique avait un centre de calcul analogique géant. Ils étaient utilisés pour lancer des fusées dans l'espace, guider des armes sur les cuirassés, et simuler la dynamique des avions.

Contrairement aux ordinateurs numériques, les ordinateurs analogiques utilisent des données non discrètes comme la tension, le poids, la vitesse, la température et la pression. Et comme ils utilisent des valeurs continues, ils sont immunisés contre le bruit de quantification.

Les ordinateurs analogiques peuvent être conçus pour résoudre une variété de problèmes. Ils peuvent effectuer directement des opérations mathématiques. Par exemple, pour soustraire 8 de 3, les ordinateurs analogiques soustraient les tensions correspondant à ces valeurs, et fournissent immédiatement la sortie correcte.

Ils peuvent être utilisés pour des opérations en temps réel et le calcul simultané. En cas de problèmes analogiques, ils peuvent fournir des informations sur les problèmes et les erreurs. Et comme ils ne nécessitent pas de quantification, ils sont parfaits pour la modulation/démodulation de signal et le contrôle de moteur à haute vitesse.

Référence : Nature Communications | doi:10.1038/s41467-018-07327-2 | Université Notre-Dame

Cependant, les ordinateurs numériques ont pris le marché dans les années 1980. Ils étaient suffisamment flexibles, rapides et plus précis pour effectuer des tâches générales. À mesure que des algorithmes efficaces arrivaient, leurs performances s'amélioraient encore.

Un ordinateur analogique vintage AMF665D | Crédit image : Francis Massen / YouTube

Mais les ordinateurs numériques, y compris les modernes, ne peuvent pas résoudre les problèmes NP-difficiles avec de grandes variables. La difficulté avec la plupart des problèmes d'optimisation est que vous ne pouvez pas déterminer si la ou les solutions sont optimales. S'assurer qu'il n'y a pas de meilleure solution est tout aussi difficile que le problème lui-même.

Solveur analogique à haute performance

Le nouveau système dynamique en temps continu peut résoudre un problème d'optimisation discrète quintessentiel, appelé MaxSAT. La méthode repose sur un ensemble déterministe d'équations différentielles ordinaires et une technique heuristique pour prédire la probabilité que la solution optimale ait été évaluée par le temps analogique t.

Dans les circuits analogiques, le goulot d'étranglement de von Neumann est éliminé : le circuit lui-même agit comme processeur et mémoire. Implémenter l'approche sur des ordinateurs numériques, en revanche, nécessite l'utilisation d'un algorithme d'intégration d'équations différentielles ordinaires qui discrétise les équations en temps continu et les résout étape par étape tout en gérant les erreurs.

Sous forme numérique, le solveur ne performe pas efficacement car la dynamique fait évoluer plusieurs milliers d'équations différentielles ordinaires couplées, ce qui est un processus d'intégration chronophage.

À lire : Faits les plus intéressants sur les ordinateurs quantiques

Et comme l'approche utilise des caractères généraux, elle peut être étendue à d'autres problèmes d'optimisation également. Les chercheurs prévoient de concevoir et construire des dispositifs basés sur cette nouvelle approche.