Ein analoger Solver, um die beste Lösung für NP-schwere Probleme zu finden

• Forscher entwickeln ein neues System, das ein grundlegendes diskretes Optimierungsproblem namens MaxSAT lösen kann.
• Dieser analoge Solver bietet eine bessere Leistung als digitale Computer und kann auch auf andere Optimierungsprobleme ausgeweitet werden.

Heutige digitale Computer erledigen die meisten Aufgaben gut. Sie sind perfekt für bestimmte Berechnungen, Textverarbeitung, Web-Surfen und Grafik geeignet. Da sie jedoch auf Binärcode angewiesen sind – 0 und 1 – sind sie nicht ideal, um alle Probleme zu lösen.

Das digitale Computing hat sein maximales Potenzial fast erreicht, und deshalb haben einige Mathematiker begonnen, sich für die Wiederbelebung des analogen Computing zu interessieren. Es kann dazu beitragen, die Berechnung über den digitalen Rahmen hinaus voranzutreiben.

Kürzlich haben Forscher der University of Notre Dame und der Babes-Bolyai University, Rumänien, einen neuen analogen Solver entwickelt, der die besten Lösungen für NP-schwere Probleme evaluieren kann.

NP-hartes Problem bedeutet, dass es keinen Algorithmus gibt, der das Problem in polynomieller Zeit lösen kann. Die Zeit, die benötigt wird, um zur Lösung zu gelangen, nimmt mit der Problemgröße exponentiell zu. Normalerweise sind diese Probleme mit medizinischer Bildgebung, Bioinformatik, Proteinfaltung und Terminplanung verbunden.

Forscher haben ihren analogen Löser an einer Vielzahl von NP-schweren Problemen getestet und festgestellt, dass diese neue Methode das Potenzial hat, in kürzerer Zeit zu besseren Lösungen zu führen.

Warum Analog Computing?

Analoge Computer waren Mitte des 20. Jahrhunderts äußerst beliebt. Jede große Verwaltung und Firma, die sich mit Dynamikproblemen beschäftigt, hatte ein riesiges analoges Rechenzentrum. Sie wurden verwendet, um Raketen in den Weltraum zu schleudern, Waffen auf Schlachtschiffen zu lenken und die Dynamik von Flugzeugen zu simulieren.

Im Gegensatz zu digitalen Computern verwenden analoge Computer nicht diskrete Daten wie Spannung, Gewicht, Geschwindigkeit, Temperatur und Druck. Und da sie kontinuierliche Werte verwenden, sind sie immun gegen Quantisierungsrauschen.

Analoge Computer können so gestaltet werden, dass sie eine Vielzahl von Problemen lösen. Sie können mathematische Operationen direkt ausführen. Um beispielsweise 8 von 3 zu subtrahieren, subtrahieren Analogcomputer Spannungen, die diesen Werten entsprechen, und liefern dann sofort die richtige Ausgabe.

Sie können für Echtzeitoperationen und gleichzeitige Berechnungen verwendet werden. Bei analogen Problemen können sie Einblicke in die Probleme und Fehler geben. Und da sie keine Quantisierung erfordern, eignen sie sich perfekt zur Signalmodulation/-demodulation und zur Hochgeschwindigkeits-Motorsteuerung.

Referenz:Naturkommunikation | doi:10.1038/s41467-018-07327-2 | Universität Notre Dame

In den 1980er Jahren eroberten jedoch digitale Computer den Markt. Sie waren bei der Durchführung allgemeiner Aufgaben ausreichend flexibel, schnell und genauer. Mit der Einführung effizienter Algorithmen wurde ihre Leistung noch besser.

Ein alter analoger AMF665D-Computer | Bildnachweis:Francis Massen / YouTube 

Aber digitale Computer, einschließlich der modernen, können keine NP-schweren Probleme mit großen Variablen lösen. Die Schwierigkeit bei den meisten Optimierungsproblemen besteht darin, dass Sie nicht feststellen können, ob die Lösung(en) optimal sind. Sicherzustellen, dass es keine bessere Lösung gibt, ist genauso schwierig wie das Problem selbst.

Analoger Solver mit hoher Leistung

Das neue zeitkontinuierliche dynamische System kann ein grundlegendes diskretes Optimierungsproblem namens MaxSAT lösen. Das Verfahren beruht auf einem deterministischen Satz gewöhnlicher Differentialgleichungen und einer heuristischen Technik zur Vorhersage der Wahrscheinlichkeit, dass die optimale Lösung durch die analoge Zeit t bewertet wurde.

In analogen Schaltungen ist der von Neumann-Engpass beseitigt:Die Schaltung selbst fungiert als Prozessor und Speicher. Die Implementierung des Ansatzes auf Digitalcomputern erfordert andererseits die Verwendung eines gewöhnlichen Integratoralgorithmus für Differentialgleichungen, der die zeitkontinuierlichen Gleichungen diskretisiert und sie Schritt für Schritt löst, während Fehler behandelt werden.

In digitaler Form funktioniert der Solver nicht effizient, da die Dynamik mehrere Tausend gekoppelter gewöhnlicher Differentialgleichungen entwickelt, was ein zeitaufwändiger Integrationsprozess ist.

Lesen:Die interessantesten Fakten über Quantencomputer

Und da der Ansatz allgemeine Zeichen verwendet, kann er auch auf andere Optimierungsprobleme ausgedehnt werden. Die Forscher planen, Geräte basierend auf diesem neuen Ansatz zu entwerfen und zu bauen.