Analoge Oploser Presteert Beter Dan Digitale Computers Bij NP-Harde Optimalisatie

• Onderzoekers bouwen een nieuw systeem dat een kwintessenieel discrete optimalisatieprobleem kan oplossen, MaxSAT genoemd.
• Deze analoge oploser presteert beter dan digitale computers, en kan uitgebreid worden naar andere optimalisatieproblemen.

Tegenwoordig presteren digitale computers de meeste taken goed. Ze zijn perfect voor bepaalde berekeningen, tekstverwerking, websurfen, en grafische kunsten. Maar aangezien ze vertrouwen op binaire code — 0'en en 1'en — zijn ze niet ideaal voor het oplossen van alle problemen.

Digtale computing heeft bijna zijn maximaal potentieel bereikt, en dat is waarom sommige wiskundigen geïnteresseerd zijn geraakt in het herlevven van analoge computing. Het kan helpen de berekening vooruitbrengen buiten het digitale kader.

Onlangs hebben onderzoekers van de University of Notre Dame en Babes-Bolyai University, Roemenië, een nieuwe analoge oploser ontwikkeld die de beste oplossingen van NP-harde problemen kan evalueren.

NP-hard probleem betekent dat er geen algoritme is dat het probleem in polynomiale tijd kan oplossen. De tijd die nodig is om tot de oplossing te komen, neemt exponentieel toe met de probleemgrootte. Meestal zijn deze geassocieerd met medische imaging, bio-informatica, proteinvouwing, en planning.

Onderzoekers testten hun analoge oploser op een breed scala aan NP-harde problemen, en vonden dat deze nieuwe methode het potentieel heeft om tot betere oplossingen in minder tijd te leiden.

Waarom Analog Computing?

Analoge computers waren extreem populair in de midden-20e eeuw. Elk groot bestuur en bedrijf dat te maken had met problemen in dynamica had een reusachtig analog computing centrum. Ze werden gebruikt om raketten in de ruimte te lanceren, wapens op slachtschepen te sturen, en vliegtuigdynamica te simuleren.

In tegenstelling tot digitale computers, gebruiken analoge computers niet-discrete data zoals spanning, gewicht, snelheid, temperatuur, en druk. En aangezien ze continue waarden gebruiken, zijn ze immuun voor kwantiseringsruis.

Analoge computers kunnen ontworpen worden om een verscheidenheid aan problemen op te lossen. Ze kunnen direct wiskundige operaties uitvoeren. Bijvoorbeeld, om 8 van 3 af te trekken, trekken analoge computers spanningen af die overeenkomen met die waarden, en leveren dan onmiddellijk de juiste output.

Ze kunnen gebruikt worden voor real-time operaties en gelijktijdige berekening. In het geval van analoge problemen, kunnen ze inzichten in de problemen en fouten bieden. En aangezien ze geen kwantisering vereisen, zijn ze perfect voor signaalmodulatie/demodulatie en hoge-snelheid motorcontrole.

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

Echter, digitale computers namen de markt over in de jaren '80. Ze waren voldoende flexibel, snel en nauwkeuriger in het uitvoeren van algemene taken. Als efficiënte algoritmes erbij kwamen, werd hun prestatie nog beter.

Een vintage analoge AMF665D computer | Afbeelding credit: Francis Massen / YouTube

Maar digitale computers, inclusief de moderne, kunnen NP-harde problemen met grote variabelen niet oplossen. De moeilijkheid met de meeste optimalisatieproblemen is dat u niet kunt bepalen of de oplossing(en) optimaal is. Zeker weten dat er geen betere oplossing is, is net zo moeilijk als het probleem zelf.

Analoge Oploser Met Hoge Prestaties

Het nieuwe continue-tijd dynamische systeem kan een kwintessenieel discrete optimalisatieprobleem oplossen, MaxSAT genoemd. De methode steunt op een deterministische set van gewone differentiaalvergelijkingen en een heuristische techniek voor het voorspellen van de waarschijnlijkheid dat de optimale oplossing geëvalueerd is door analoge tijd t.

In analoge circuits wordt de von Neumann bottleneck geëlimineerd: het circuit zelf fungeert als processor en geheugen. Het implementeren van de benadering op digitale computers, aan de andere kant, vereist het gebruik van een gewone differentiaalvergelijkingen integrator-algoritme dat de continue-tijd vergelijkingen discretiseert en ze stap voor stap oplost tijdens het afhandelen van fouten.

In digitale vorm presteert de oploser niet efficiënt omdat de dynamica enkele duizenden gekoppelde gewone differentiaalvergelijkingen evolueert, wat een tijdrovend integratieproces is.

Lees ook: Meest Interessante Feiten Over Quantum Computers

En aangezien de benadering algemene karakters gebruikt, kan het uitgebreid worden naar andere optimalisatieproblemen ook. De onderzoeker plannen om apparaten te ontwerpen en bouwen op basis van deze nieuwe benadering.