Analoger Solver übertrifft Digitalcomputer bei NP-harter Optimierung

• Forscher bauen neues System, das quintessentielles diskretes Optimierungsproblem (MaxSAT) löst.
• Analoger Solver performt besser als Digitalcomputer, erweiterbar auf andere Optimierungsprobleme.

Heutige Digitalcomputer erledigen die meisten Aufgaben gut. Perfekt für bestimmte Berechnungen, Textverarbeitung, Websurfing, Grafik. Doch da sie auf Binärcode (0/1) basieren, nicht ideal für alle Probleme.

Digitalcomputing hat fast maximales Potenzial erreicht, weshalb Mathematiker analoges Computing wiederbeleben. Es kann Computation über digitalen Rahmen hinaus vorantreiben.

Forscher der University of Notre Dame und Babes-Bolyai University (Rumänien) entwickelten neuen analogen Solver, der beste Lösungen von NP-harten Problemen evaluiert.

NP-hart: Kein Algorithmus löst Problem in Polynomialzeit. Lösungszeit wächst exponentiell mit Problemgröße. Typisch für Medical Imaging, Bioinformatik, Protein-Folding, Scheduling.

Forscher testeten analogen Solver auf breitem NP-hart-Spektrum und fanden: Neue Methode potenziell bessere Lösungen in kürzerer Zeit.

Warum Analog Computing?

Analogcomputer waren Mitte 20. Jahrhundert extrem populär. Jede große Administration/Firma mit Dynamikproblemen hatte riesiges Analogrechenzentrum. Raketenstarts, Waffenzielsysteme auf Schlachtschiffen, Flugzeugdynamik-Simulation.

Im Gegensatz zu Digitalcomputern nutzen Analogcomputer nicht-diskrete Daten: Spannung, Gewicht, Geschwindigkeit, Temperatur, Druck. Durch kontinuierliche Werte immun gegen Quantisierungsrauschen.

Analogcomputer lösbar für diverse Probleme. Führen mathematische Operationen direkt aus. Beispiel: 8 von 3 subtrahieren → Analogcomputer subtrahiert entsprechende Spannungen, liefert sofort korrektes Ergebnis.

Einsetzbar für Echtzeitoperationen und simultane Computation. Bei Analogproblemen liefern sie Einblicke in Probleme/Fehler. Ohne Quantisierung perfekt für Signalmodulation/Demodulation und Hochgeschwindigkeits-Motorsteuerung.

Referenz: Nature Communications | doi:10.1038/s41467-018-07327-2 | University of Notre Dame

Digitalcomputer übernahmen 1980er den Markt. Sie waren flexibler, schneller, genauer bei allgemeinen Aufgaben. Mit effizienten Algorithmen wurde Performance noch besser.

Vintage Analogcomputer AMF665D | Bildnachweis: Francis Massen / YouTube

Aber Digitalcomputer (inkl. moderne) können NP-harte Probleme mit vielen Variablen nicht lösen. Schwierigkeit bei Optimierung: Kann nicht bestimmen, ob Lösung optimal ist. Sicherstellen, dass keine bessere Lösung existiert, genauso schwer wie Problem selbst.

Analoger Solver mit High Performance

Neues kontinuierliches dynamisches System löst quintessentielles diskretes Optimierungsproblem MaxSAT. Methode basiert auf deterministischer Menge gewöhnlicher Differentialgleichungen und heuristischer Technik zur Vorhersage Wahrscheinlichkeit, dass optimale Lösung durch analoge Zeit t evaluiert wurde.

In Analogschaltungen wird von-Neumann-Flaschenhals eliminiert: Schaltung selbst agiert als Prozessor und Speicher. Implementierung auf Digitalcomputern erfordert ODE-Integrator-Algorithmus, der kontinuierliche Gleichungen diskretisiert und schrittweise löst bei Fehlerbehandlung.

In digitaler Form performt Solver nicht effizient, da Dynamik mehrere tausend gekoppelte ODEs evolviert – zeitaufwendiger Integrationsprozess.

Weiterlesen: Interessanteste Fakten über Quantencomputer

Da Ansatz allgemeine Charaktere nutzt, erweiterbar auf andere Optimierungsprobleme. Forscher planen Geräte basierend auf neuem Ansatz zu designen und bauen.