NP困難問題の最良の解を見つけるためのアナログソルバー

• 研究者は、MaxSATと呼ばれる典型的な離散最適化問題を解決できる新しいシステムを構築します。
• このアナログソルバーは、デジタルコンピューターよりも優れたパフォーマンスを発揮し、他の最適化問題にも拡張できます。

今日のデジタルコンピュータは、ほとんどのタスクを適切に実行します。これらは、特定の計算、ワードプロセッシング、Webサーフィン、およびグラフィックアートに最適です。ただし、0と1のバイナリコードに依存しているため、すべての問題を解決するのに理想的ではありません。

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

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

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

研究者は、NP困難な問題の広い範囲でアナログソルバーをテストし、この新しい方法がより短い時間でより良い解決策につながる可能性があることを発見しました。

なぜアナログコンピューティングなのか？

アナログコンピュータは20世紀半ばに非常に人気がありました。ダイナミクスの問題に関心のあるすべての大企業や企業には、巨大なアナログコンピューティングセンターがありました。これらは、ロケットを宇宙に打ち上げ、戦艦で武器を誘導し、航空機のダイナミクスをシミュレートするために使用されました。

デジタルコンピュータとは異なり、アナログコンピュータは、電圧、重量、速度、温度、圧力などの非離散データを使用します。また、連続値を使用するため、量子化ノイズの影響を受けません。

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

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

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

しかし、1980年代にデジタルコンピュータが市場を引き継ぎました。それらは、一般的なタスクを実行する上で十分に柔軟で、高速で、より正確でした。効率的なアルゴリズムが登場するにつれて、そのパフォーマンスはさらに向上しました。

ビンテージアナログAMF665Dコンピューター|画像クレジット：Francis Massen / YouTube

しかし、最新のコンピューターを含むデジタルコンピューターは、大きな変数を伴うNP困難な問題を解決できません。ほとんどの最適化問題の難しさは、ソリューションが最適であるかどうかを判断できないことです。より良い解決策がないことを確認することは、問題自体と同じくらい難しいことです。