Pemecah Analog Ungguli Komputer Digital pada Optimasi NP-Hard

• Peneliti membangun sistem baru yang dapat menyelesaikan masalah optimasi diskret klasik, disebut MaxSAT.
• Pemecah analog ini berkinerja lebih baik daripada komputer digital, dan dapat diperluas ke masalah optimasi lainnya juga.

Komputer digital saat ini melakukan sebagian besar tugas dengan baik. Ia sempurna untuk komputasi tertentu, pengolahan kata, penjelajahan web, dan seni grafis. Namun, karena mereka bergantung pada kode biner — 0 dan 1 — mereka tidak ideal untuk menyelesaikan semua masalah.

Komputasi digital hampir telah mencapai potensi maksimalnya, dan inilah mengapa beberapa ahli matematika mulai tertarik untuk mengangkat kembali komputasi analog. Ini dapat membantu memajukan komputasi di luar kerangka digital.

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

Masalah NP-hard berarti tidak ada algoritma yang dapat menyelesaikan masalah dalam waktu polinomial. Waktu yang diperlukan untuk mencapai solusi meningkat secara eksponensial dengan ukuran masalah. Biasanya, masalah ini terkait dengan citra medis, bioinformatika, lipatan protein, dan penjadwalan.

Peneliti menguji pemecah analog mereka pada berbagai masalah NP-hard, dan mereka menemukan bahwa metode baru ini memiliki potensi untuk menghasilkan solusi yang lebih baik dalam waktu yang lebih singkat.

Mengapa Komputasi Analog?

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

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

Komputer analog dapat dirancang untuk menyelesaikan berbagai masalah. Mereka dapat langsung melakukan operasi matematika. Misalnya, untuk mengurangi 8 dari 3, komputer analog mengurangi tegangan yang sesuai dengan nilai-nilai tersebut, dan kemudian segera memberikan output yang benar.

Mereka dapat digunakan untuk operasi real-time dan komputasi simultan. Dalam 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 berkecepatan tinggi.

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

Namun, komputer digital menguasai pasar pada tahun 1980-an. Mereka cukup fleksibel, cepat dan lebih akurat dalam melakukan tugas umum. Seiring hadirnya algoritma yang efisien, kinerja mereka menjadi lebih baik lagi.

Komputer analog vintage AMF665D | Kredit citra: Francis Massen / YouTube

Tapi 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(nya) optimal. Memastikan tidak ada solusi yang lebih baik sama sulitnya dengan masalah itu sendiri.

Pemecah Analog dengan Kinerja Tinggi

Sistem dinamis waktu kontinu baru dapat menyelesaikan masalah optimasi diskret klasik, disebut MaxSAT. Metode ini bergantung pada himpunan deterministik persamaan diferensial biasa dan teknik heuristik untuk memprediksi kemungkinan bahwa solusi optimal telah dievaluasi oleh waktu analog t.

Dalam sirkuit analog, kendala von Neumann dihilangkan: sirkuit itu sendiri berfungsi sebagai prosesor dan memori. Menerapkan pendekatan ini pada komputer digital, di sisi lain, memerlukan penggunaan algoritma integrator persamaan diferensial biasa yang diskritkan persamaan waktu continuo dan menyelesaikannya secara bertahap sambil menangani kesalahan.

Dalam bentuk digital, pemecah tidak berkinerja dengan efisien karena dinamika berkembang beberapa ribuan persamaan diferensial biasa yang berpasangan, yang merupakan proses integrasi yang memakan waktu.

Baca: Fakta Paling Menarik tentang Komputer Kuantum

Dan karena pendekatan ini menggunakan karakter umum, ia dapat diperluas ke masalah optimasi lainnya juga. Para peneliti berencana untuk merancang dan membangun perangkat berdasarkan pendekatan baru ini.