Un solveur analogique pour trouver la meilleure solution aux problèmes NP-Hard

• Les chercheurs créent un nouveau système capable de résoudre un problème d'optimisation discrète par excellence, appelé MaxSAT.
• Ce solveur analogique fonctionne mieux que les ordinateurs numériques et peut également ê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 sur le Web et les arts graphiques. Mais comme ils reposent sur du code binaire - des 0 et des 1 - ils ne sont pas idéaux pour résoudre tous les problèmes.

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

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

Un problème NP-difficile signifie qu'il n'y a pas d'algorithme qui puisse résoudre le problème en temps polynomial. Le temps nécessaire pour trouver la solution augmente de façon exponentielle avec la taille du problème. Habituellement, ces problèmes sont associés à l'imagerie médicale, à la bioinformatique, au repliement des protéines et à la planification.

Les chercheurs ont testé leur solveur analogique sur un large éventail 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 disposait d'un gigantesque centre de calcul analogique. Ils étaient utilisés pour lancer des fusées dans l'espace, guider les 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 telles que 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 divers problèmes. Ils peuvent effectuer directement des opérations mathématiques. Par exemple, pour soustraire 8 de 3, les ordinateurs analogiques soustraient les tensions qui correspondent à ces valeurs, puis fournissent immédiatement la sortie correcte.

Ils peuvent être utilisés pour des opérations en temps réel et des calculs simultanés. 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 du signal et le contrôle moteur à grande vitesse.

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

Cependant, les ordinateurs numériques ont conquis le marché dans les années 1980. Ils étaient suffisamment flexibles, rapides et plus précis dans l'exécution de tâches générales. Avec l'arrivée d'algorithmes efficaces, leurs performances se sont encore améliorées.

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 à hautes performances

Le nouveau système dynamique en temps continu peut résoudre un problème d'optimisation discret par excellence, 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 fait office de processeur et de mémoire. La mise en œuvre de l'approche sur des ordinateurs numériques, d'autre part, 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 fonctionne pas efficacement car la dynamique évolue sur plusieurs milliers d'équations différentielles ordinaires couplées, ce qui est un processus d'intégration fastidieux.

Lire :Faits les plus intéressants sur les ordinateurs quantiques

Et puisque l'approche utilise des caractères généraux, elle peut également être étendue à d'autres problèmes d'optimisation. Le chercheur prévoit de concevoir et de fabriquer des appareils basés sur cette nouvelle approche.