Een analoge oplosser om de beste oplossing voor NP-moeilijke problemen te vinden

• Onderzoekers bouwen een nieuw systeem dat een wezenlijk probleem met discrete optimalisatie kan oplossen, genaamd MaxSAT.
• Deze analoge oplosser presteert beter dan digitale computers en kan ook worden uitgebreid naar andere optimalisatieproblemen.

De huidige digitale computers voeren de meeste taken goed uit. Ze zijn perfect voor bepaalde berekeningen, tekstverwerking, websurfen en grafische kunst. Maar omdat ze afhankelijk zijn van binaire code — nullen en enen — zijn ze niet ideaal om alle problemen op te lossen.

Digitaal computergebruik heeft bijna zijn maximale potentieel bereikt en daarom zijn sommige wiskundigen geïnteresseerd geraakt in het nieuw leven inblazen van analoog computergebruik. Het kan helpen om de berekening verder te brengen dan het digitale raamwerk.

Onlangs hebben onderzoekers van de Universiteit van Notre Dame en Babes-Bolyai University, Roemenië, een nieuwe analoge oplosser ontwikkeld die de beste oplossingen voor 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 grootte van het probleem. Meestal worden deze problemen geassocieerd met medische beeldvorming, bio-informatica, eiwitvouwing en planning.

Onderzoekers hebben hun analoge oplosser getest op een breed scala aan NP-harde problemen, en ze ontdekten dat deze nieuwe methode het potentieel heeft om in minder tijd tot betere oplossingen te leiden.

Waarom analoge computers?

Analoge computers waren in het midden van de 20e eeuw enorm populair. Elke grote administratie en elk bedrijf dat zich bezighield met problemen in de dynamiek had een gigantisch analoog rekencentrum. Ze werden gebruikt om raketten de ruimte in te lanceren, wapens op slagschepen te leiden en de dynamiek van vliegtuigen te simuleren.

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

Analoge computers kunnen worden ontworpen om een ​​verscheidenheid aan problemen op te lossen. Ze kunnen direct wiskundige bewerkingen uitvoeren. Om bijvoorbeeld 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 worden gebruikt voor realtime bewerkingen en gelijktijdige berekeningen. Bij analoge vraagstukken kunnen zij inzicht geven in de problemen en fouten. En omdat ze geen kwantisering nodig hebben, zijn ze perfect voor signaalmodulatie/demodulatie en snelle motorbesturing.

Referentie:Nature Communications | doi:10.1038/s41467-018-07327-2 | Universiteit van Notre Dame

In de jaren tachtig namen digitale computers echter de markt over. Ze waren voldoende flexibel, snel en nauwkeuriger in het uitvoeren van algemene taken. Toen er efficiënte algoritmen kwamen, werden hun prestaties nog beter.

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

Maar digitale computers, ook 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. Ervoor zorgen dat er geen betere oplossing is, is net zo moeilijk als het probleem zelf.

Analoge oplosser met hoge prestaties

Het nieuwe dynamische systeem met continue tijd kan een typisch discreet optimalisatieprobleem oplossen, MaxSAT genaamd. De methode is gebaseerd op een deterministische set gewone differentiaalvergelijkingen en een heuristische techniek voor het voorspellen van de waarschijnlijkheid dat de optimale oplossing is geëvalueerd door analoge tijd t.

In analoge schakelingen wordt de von Neumann-bottleneck geëlimineerd:de schakeling zelf fungeert als processor en geheugen. Implementatie van de aanpak op digitale computers vereist daarentegen het gebruik van een gewoon integratoralgoritme voor differentiaalvergelijkingen dat de continue-tijdvergelijkingen discretiseert en stap voor stap oplost terwijl fouten worden verwerkt.

In digitale vorm presteert de oplosser niet efficiënt omdat de dynamiek duizenden gekoppelde gewone differentiaalvergelijkingen ontwikkelt, wat een tijdrovend integratieproces is.

Lees:Meest interessante feiten over kwantumcomputers

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