アナログソルバーがNP困難最適化問題でデジタルコンピュータを上回る

今日のデジタルコンピュータはほとんどのタスクをうまくこなします。特定の計算、ワープロ、ウェブサーフィン、グラフィックアートには最適です。しかし、バイナリコード（0と1）に依存しているため、すべての問題を解くのに理想的ではありません。

デジタルコンピューティングはほぼ最大ポテンシャルに達しており、そのため一部の数学者がアナログコンピューティングの復活に関心を持ち始めています。これはデジタルフレームワークを超えて計算を前進させるのに役立ちます。

最近、ノートルダム大学とルーマニアのバベシュ・ボリャイ大学の研究者たちが、NP困難問題の最良解を評価できる新しいアナログソルバーを開発しました。

NP困難問題とは、多項式時間で問題を解くアルゴリズムが存在しないことを意味します。解に到達するのに必要な時間は問題サイズに指数関数的に増加します。通常、これらの問題は医療画像、バイオインフォマティクス、タンパク質折りたたみ、スケジューリングに関連しています。

研究者たちは幅広いNP困難問題でアナログソルバーをテストし、この新手法がより少ない時間でより良い解に導く可能性があることを発見しました。

アナログコンピュータは20世紀半ばに非常に人気がありました。動力学の問題に関わるすべての大規模行政機関と企業が巨大なアナログコンピューティングセンターを持っていました。ロケットの宇宙打ち上げ、戦艦の兵器誘導、航空機ダイナミクスのシミュレーションに使用されました。

デジタルコンピュータとは異なり、アナログコンピュータは電圧、重量、速度、温度、圧力などの非離散データを使用します。連続値を使用するため、量子化ノイズに対して免疫があります。

アナログコンピュータは多様な問題を解くように設計できます。直接的に数学的演算を実行できます。たとえば、3から8を引く場合、アナログコンピュータはそれらの値に対応する電圧を引き、即座に正しい出力を提供します。

リアルタイム操作と同時計算に使用できます。アナログ問題の場合、問題とエラーの洞察を提供できます。量子化を必要としないため、信号変調/復調と高速モーター制御に最適です。

参照: Nature Communications | doi:10.1038/s41467-018-07327-2 | ノートルダム大学

しかし、デジタルコンピュータが1980年代に市場を制しました。一般的なタスクを実行するのに十分な柔軟性、速度、精度がありました。効率的なアルゴリズムが登場するにつれ、性能はさらに向上しました。

ビンテージアナログAMF665Dコンピュータ | Image credit: Francis Massen / YouTube

しかし、現代のデジタルコンピュータを含め、大規模変数を持つNP困難問題を解くことはできません。ほとんどの最適化問題の難しさは、解が最適かどうかを判断できないことです。これ以上良い解がないことを保証するのは、問題自体と同じくらい困難です。

新しい連続時間力学システムは、MaxSATと呼ばれる典型的な離散最適化問題を解けます。この手法は、決定論的な常微分方程式のセットと、アナログ時間tで最適解が評価された可能性を予測するヒューリスティック技術に依存します。

アナログ回路ではフォン・ノイマンのボトルネックが排除されます：回路自体がプロセッサとメモリとして機能します。一方、デジタルコンピュータでアプローチを実装するには、常微分方程式積分アルゴリズムを使用し、連続時間方程式を離散化してステップバイステップで解きながらエラーを処理する必要があります。

デジタル形式では、ダイナミクスが数千の結合常微分方程式を進化させるため、時間のかかる積分プロセスになるためソルバーは効率的に動作しません。

このアプローチは一般的な特性を使用するため、他の最適化問題にも拡張可能です。研究者たちはこの新アプローチに基づいてデバイスを設計・構築する計画です。

産業技術