Аналоговый решатель для поиска лучшего решения NP-сложных проблем

• Исследователи создают новую систему, которая может решить типичную задачу дискретной оптимизации, которая называется MaxSAT.
• Этот аналоговый решатель работает лучше, чем цифровые компьютеры, и его также можно расширить для решения других задач оптимизации.

Современные цифровые компьютеры хорошо справляются с большинством задач. Они идеально подходят для определенных вычислений, обработки текста, веб-серфинга и графики. Но поскольку они полагаются на двоичный код - нули и единицы - они не идеальны для решения всех проблем.

Цифровые вычисления почти достигли своего максимального потенциала, и поэтому некоторые математики начали проявлять интерес к возрождению аналоговых вычислений. Это может помочь продвинуть вычисления за рамки цифровых технологий.

Недавно исследователи из Университета Нотр-Дам и Университета Бабеш-Бойяи, Румыния, разработали новый аналоговый решатель, который может оценивать лучшие решения NP-сложных задач.

NP-сложная задача означает, что не существует алгоритма, который мог бы решить проблему за полиномиальное время. Время, необходимое для достижения решения, увеличивается экспоненциально с увеличением размера проблемы. Обычно эти проблемы связаны с медицинской визуализацией, биоинформатикой, сворачиванием белков и составлением расписания.

Исследователи протестировали свой аналоговый решатель на широком спектре NP-сложных проблем и обнаружили, что этот новый метод может привести к лучшим решениям за меньшее время.

Почему аналоговые вычисления?

Аналоговые компьютеры были чрезвычайно популярны в середине 20 века. У каждой крупной администрации и компании, занимающейся проблемами динамики, был гигантский центр аналоговых вычислений. Они использовались для запуска ракет в космос, управления оружием на линкорах и моделирования динамики самолетов.

В отличие от цифровых компьютеров, аналоговые компьютеры используют недискретные данные, такие как напряжение, вес, скорость, температура и давление. А поскольку они используют непрерывные значения, они невосприимчивы к шуму квантования.

Аналоговые компьютеры могут быть разработаны для решения множества задач. Они могут напрямую выполнять математические операции. Например, чтобы вычесть 8 из 3, аналоговые компьютеры вычитают напряжения, которые соответствуют этим значениям, и затем немедленно выдают правильный результат.

Их можно использовать для операций в реальном времени и одновременных вычислений. В случае аналоговых проблем они могут предоставить информацию о проблемах и ошибках. А поскольку они не требуют квантования, они идеально подходят для модуляции / демодуляции сигнала и управления высокоскоростным двигателем.

Ссылка:Nature Communications | doi:10.1038 / s41467-018-07327-2 | Университет Нотр-Дам

Однако цифровые компьютеры захватили рынок в 1980-х годах. Они были достаточно гибкими, быстрыми и точными в выполнении общих задач. По мере появления эффективных алгоритмов их производительность становилась еще лучше.

Старинный аналоговый компьютер AMF665D | Изображение предоставлено:Фрэнсис Массен / YouTube

Но цифровые компьютеры, в том числе современные, не могут решать NP-сложные задачи с большими переменными. Сложность большинства задач оптимизации заключается в том, что вы не можете определить, является ли решение оптимальным. Убедиться, что нет лучшего решения, так же сложно, как и сама проблема.

Аналоговый решатель с высокой производительностью

Новая динамическая система с непрерывным временем может решать типичную задачу дискретной оптимизации, называемую MaxSAT. Этот метод основан на детерминированном наборе обыкновенных дифференциальных уравнений и эвристическом методе прогнозирования вероятности того, что оптимальное решение было оценено за аналоговое время t.

В аналоговых схемах устраняется узкое место фон Неймана:сама схема действует как процессор и память. С другой стороны, реализация подхода на цифровых компьютерах требует использования алгоритма интегратора обыкновенных дифференциальных уравнений, который дискретизирует уравнения с непрерывным временем и решает их шаг за шагом, обрабатывая ошибки.

В цифровой форме решающая программа не работает эффективно, потому что динамика складывается из нескольких тысяч связанных обыкновенных дифференциальных уравнений, что является трудоемким процессом интегрирования.

Прочтите:самые интересные факты о квантовых компьютерах

А поскольку в подходе используются общие символы, его можно распространить и на другие задачи оптимизации. Исследователи планируют разрабатывать и создавать устройства на основе этого нового подхода.