マグノニック組合せ装置を用いた巡回セールスマン問題の解決

Scientific Reports volume 13、記事番号: 11708 (2023) この記事を引用

207 アクセス

メトリクスの詳細

巡回セールスマン問題 (TSP) は、多くの実際のアプリケーションに不可欠な意思決定問題です。 現在、この問題は、ブール型アーキテクチャを利用したデジタル コンピュータで、多数の可能なルートを 1 つずつチェックすることで解決されています。 この作業では、TSP ソリューション用の特殊なタイプのハードウェアについて説明します。 これは、アクティブなリング回路に接続された磁気部品と電気部品で構成されるマグノニック組み合わせデバイスです。 位相シフタ、周波数フィルタ、および減衰器で構成される磁気メッシュ内には、多数の可能な伝播ルートが存在します。 位相シフターは TSP の都市を模倣し、都市間の距離は信号の減衰でエンコードされます。 周波数フィルターのセットにより、異なる周波数の波が異なるルートを通って伝播します。 動作原理は古典的な波の重ね合わせに基づいています。 考えられるすべてのルートから並行して到来する多数の波があり、さまざまな位相シフトと振幅減衰が蓄積されます。 ただし、電気部品によって増幅されるのは、一定の位相シフトを蓄積した波だけです。 最小の伝播損失を持つ波が最初に増幅されます。 このタイプのデバイスは、波が一度にすべての可能なルートを移動するセールスマンに似ている TSP ソリューションに適しています。 4 都市と 6 都市の TSP ソリューションを示す数値モデリングの結果を示します。 また、4 つの都市での TSP ソリューションの実験データも紹介します。 プロトタイプのデバイスは、磁気移相器/フィルター、同軸ケーブル、スプリッター、減衰器、広帯域アンプなどの市販のコンポーネントで構築されています。 3 つの異なる都市間距離セットに対して都市間の最短ルートを検索する例が 3 つあります。 提案されたアプローチは、より多くの都市を含む TSP に拡張可能です。 物理的な限界と課題についても説明します。

TSP は、最もよく知られた組み合わせ最適化問題の 1 つです1。 これは次のように言えます。「都市のリストと各都市間の距離を考慮して、各都市を 1 回ずつ訪問し、元の都市に戻る最短ルートを見つけます。」 これは非決定的な多項式時間ハードウェア (NP ハード) 問題であり、最適なルートを取得する保証がなく、多項式時間でそれを解決するための正確なアルゴリズムも存在しないことを意味します。 TSP は、輸送 2、スケジューリング 3、ゲノミクス 4 などのさまざまな実際の応用において重要です。 数学的には、\(\left\{{c}_{1},{c}_{2},\dots ,{c}_{n という名前の \(n\) 個の都市のセットが与えられたものとして定義できます。 }\right\}\)、順列 \(\left\{{\sigma }_{1},{\sigma }_{2},\dots ,{\sigma }_{n!}\right\} \)。 目的は、ツアー内の都市間のすべてのユークリッド距離の合計が最小になるように \({\sigma }_{i}\) を選択することです。 TSP は、図 1 に示すような無向重み付きグラフとしてモデル化できます。都市はグラフの頂点、パスはグラフのエッジ、パスの距離はエッジの重みです。 TSP は、考えられるすべての \(\left(n-1\right)!/2\) のルートを 1 つずつチェックすることで解決できます。 少数の都市について考えられるすべてのルートをチェックするのは比較的簡単です。 たとえば、4 つの都市を含む TSP には \(\left(4-1\right)!/2=3\) のルートがあります。 可能なルートの数は \(n\) 階乗に比例して増加するため、従来のコンピューティング デバイスを使用して多数の都市を解決することが困難になります。

4 つの都市を含む TSP の無向加重グラフ。 都市はグラフの頂点、パスはグラフのエッジ、パスの距離はエッジの重みです。

TSP ソリューション用の特別なハードウェアを構築する試みがいくつかありました 5、6。 たとえば、6 都市 TSP はコホーネン型光ネットワークを使用して解決されました6。 しかし、これらのアプローチはいずれも実用的なデバイスにはなりませんでした。 最近では、人工知能 (AI) で使用されるさまざまな最適化技術が TSP7 に適用されています。 これは TSP ソリューションを大幅に高速化する可能性がありますが、従来のハードウェアに実装されている根本的な利点を提供することはできません。