Pemecah Analog Untuk Menemukan Solusi Terbaik Masalah NP-Hard

• Para peneliti membangun sistem baru yang dapat memecahkan masalah pengoptimalan diskrit klasik, yang disebut MaxSAT.
• Pemecah analog ini berkinerja lebih baik daripada komputer digital, dan dapat diperluas ke masalah pengoptimalan lainnya juga.

Komputer digital saat ini melakukan sebagian besar tugas dengan baik. Mereka sempurna untuk perhitungan tertentu, pengolah kata, penjelajahan web, dan seni grafis. Tetapi karena mereka mengandalkan kode biner — 0s dan 1s — mereka tidak ideal untuk menyelesaikan semua masalah.

Komputasi digital hampir mencapai potensi maksimalnya, dan itulah sebabnya beberapa matematikawan mulai tertarik untuk menghidupkan kembali komputasi analog. Ini dapat membantu memajukan komputasi di luar kerangka kerja digital.

Baru-baru ini, para peneliti di Universitas Notre Dame dan Universitas Babes-Bolyai, Rumania, mengembangkan pemecah analog baru yang dapat mengevaluasi solusi terbaik untuk masalah NP-hard.

NP-hard problem berarti tidak ada algoritma yang dapat menyelesaikan masalah dalam waktu polinomial. Waktu yang dibutuhkan untuk mendapatkan solusi meningkat secara eksponensial dengan ukuran masalah. Biasanya, masalah ini terkait dengan pencitraan medis, bioinformatika, pelipatan protein, dan penjadwalan.

Para peneliti menguji pemecah analog mereka pada berbagai masalah NP-hard, dan mereka menemukan bahwa metode baru ini berpotensi menghasilkan solusi yang lebih baik dalam waktu yang lebih singkat.

Mengapa Komputasi Analog?

Komputer analog sangat populer di pertengahan abad ke-20. Setiap administrasi dan perusahaan besar yang peduli dengan masalah dinamika memiliki pusat komputasi analog raksasa. Mereka digunakan untuk meluncurkan roket ke luar angkasa, memandu senjata di kapal perang, dan mensimulasikan dinamika pesawat.

Tidak seperti komputer digital, komputer analog menggunakan data non-diskrit seperti tegangan, berat, kecepatan, suhu, dan tekanan. Dan karena menggunakan nilai kontinu, mereka kebal terhadap noise kuantisasi.

Komputer analog dapat dirancang untuk memecahkan berbagai masalah. Mereka dapat langsung melakukan operasi matematika. Misalnya, untuk mengurangi 8 dari 3, komputer analog mengurangi voltase yang sesuai dengan nilai tersebut, lalu segera memberikan output yang benar.

Mereka dapat digunakan untuk operasi waktu nyata dan komputasi simultan. Dalam kasus masalah analog, mereka dapat memberikan wawasan tentang masalah dan kesalahan. Dan karena mereka tidak memerlukan kuantisasi, mereka sempurna untuk modulasi/demodulasi sinyal dan kontrol motor kecepatan tinggi.

Referensi:Komunikasi Alam | doi:10.1038/s41467-018-07327-2 | Universitas Notre Dame

Namun, komputer digital mengambil alih pasar pada 1980-an. Mereka cukup fleksibel, cepat dan lebih akurat dalam melakukan tugas-tugas umum. Saat algoritme yang efisien muncul, kinerjanya menjadi lebih baik.

Komputer AMF665D analog antik | Kredit gambar:Francis Massen / YouTube 

Tetapi komputer digital, termasuk yang modern, tidak dapat menyelesaikan masalah NP-hard dengan variabel besar. Kesulitan dengan sebagian besar masalah optimasi adalah Anda tidak dapat menentukan apakah solusi tersebut optimal. Memastikan bahwa tidak ada solusi yang lebih baik sama sulitnya dengan masalah itu sendiri.

Pemecah Analog Dengan Performa Tinggi

Sistem dinamis waktu kontinu yang baru dapat memecahkan masalah pengoptimalan diskrit klasik, yang disebut MaxSAT. Metode ini bergantung pada satu set deterministik persamaan diferensial biasa dan teknik heuristik untuk memprediksi kemungkinan bahwa solusi optimal telah dievaluasi oleh waktu analog t.

Dalam sirkuit analog, kemacetan von Neumann dihilangkan:sirkuit itu sendiri bertindak sebagai prosesor dan memori. Sebaliknya, menerapkan pendekatan pada komputer digital memerlukan penggunaan algoritma integrator persamaan diferensial biasa yang mendiskritkan persamaan waktu kontinu dan menyelesaikannya langkah demi langkah sambil menangani kesalahan.

Dalam bentuk digital, pemecah tidak bekerja secara efisien karena dinamika mengembangkan beberapa ribu persamaan diferensial biasa yang digabungkan, yang merupakan proses integrasi yang memakan waktu.

Baca:Fakta Paling Menarik Tentang Komputer Quantum

Dan karena pendekatan ini menggunakan karakter umum, pendekatan ini juga dapat diperluas ke masalah pengoptimalan lainnya. Peneliti berencana untuk merancang dan membuat perangkat berdasarkan pendekatan baru ini.