Hybrid Discrete Grey Wolf Optimization Approach for solving Spectrum Assignment Problem in Elastic Optical Networks

技術要約：弾性光ネットワークにおけるスペクトル割り当てのためのハイブリッド離散グレーウルフ最適化

問題提起
本論文は、弾性光ネットワーク（EON）におけるルーティングおよびスペクトル割り当て（RSA）という広範な課題の中の、スペクトル割り当て（SA）サブ問題に対処するものである。高帯域幅アプリケーションによるトラフィックの増大に伴い、従来の固定グリッド波長分割多重化（WDM）ネットワークは不十分になりつつある。EONは、より小さな粒度を用いた柔軟なスペクトル割り当てを通じて、この解決策を提供する。しかし、RSA問題は、特に大規模ネットワークにおいてはNP困難であり、以下の3つの重要な制約を同時に満たす必要がある。

1. スペクトル連続性（Spectrum Continuity）: 周波数スロットのインデックスは、パス上のすべての物理リンクにおいて同一でなければならない。
2. スペクトル隣接性（Spectrum Contiguity）: 割り当てられた帯域幅は、断片化のない、隣接する周波数スロットの連続したブロックを形成しなければならない。
3. 非重複（Non-overlapping）: あるリンク上の周波数スロットは、一度に一つの接続要求のみに供することができる。

本研究の具体的な目的は、ネットワークの容量と効率を高めるために、大規模光ネットワークにおける周波数スロット（FS）の総利用量を最小化することである。

手法
著者らは、シミュレーテッド・アニーリング（SA）を統合したハイブリッド離散グレーウルフ最適化（GWO）、すなわち SA-GWO を提案している。

• グレーウルフ最適化（GWO）: 基本となるアルゴリズムは、グレーウルフの社会的な階層構造と狩りの行動（アルファ、ベータ、デルタ、オメガ）を模倣する。これは、その強力なグローバル探索能力ゆえに選択されている。しかし、著者らは、標準的なGWOは、特に探索空間が大きい場合、早期収束や局所解へのトラップに陥る可能性があると指摘している。
• 離散化への適応: SA問題は連続変数ではなくリクエストの離散的な順序付けを伴うため、著者らはGWOを適応させている。彼らは、標準的なベクトルベースの距離計算を、解のベクトル（リクエストの置換）間の非類似性を測定するためのハミング距離に置き換えた。
• シミュレーテッド・アニーリング（SA）とのハイブリッド化: 標準的なGWOの限界に対処するため、SAをGWOのポジション更新メカニルズムに組み込んでいる。
  • アルファ、ベータ、デルタのリーダーのみに基づいて決定論的にウルフの位置を更新するのではなく、アルゴリズムはハミング距離に比例した**スワップ・ミューテーション（入れ替え変異）**を用いて、各ウルフの近傍解を生成する。
  • この新しい解の採否にはメトロポリス基準に従う。新しい解がより優れたものであれば、それは受理される。もし劣るものであれば、確率 $P = e^{-\Delta E/T}$ （ここで $\Delta E$ は適合度の差、$T$ は現在の温度）で受理される。
  • この確率的な採否により、アルゴリズムは局所解を脱出することができ、GWO単独よりも探索（exploration）と活用（exploitation）をより効果的にバランスさせることができる。
• 評価: 解は、ガードバンド要件を含むDSA（Distance Spectrum Assignment）モデルの制約に従い、使用される最大周波数スロット数に基づいて評価される。

主な貢献

1. アルゴリズムの革新: EONにおける離散的なスペクトル割り当て問題に特化したハイブリッド・メタヒューリスティック（SA-GWO）の開発。
2. メカニズムの統合: 探索プロセスを精緻化し、早期収束を防ぐために、GWOのポジション更新フェーズにシミュレーテッド・アニーリングを統合したこと。
3. 離散定式化: 連続的なベクトル演算ではなく、ハミング距離とスワップ・ミューテーションを用いた、離散的な組合せ最適化のためのGWOの適応。

実験結果
提案されたSA-GWOアルゴリズムは、以下の条件で評価された。

• トポロジー: NetworkXおよびMatplotlibといったPythonライブラリを使用して生成された、ノード数が14から25の範囲のランダムグラフや完全グラフを含む、様々な合成グラフ。
• 比較: 結果は、標準的な二段階アルゴリズム（Two-Phase algorithm）、標準的なG算法（GWO）、および（小規模なインスタンスに対して）CPLEX 12.9.0ソルバーによって生成された最適解と比較された。

知見:

• 中小規模グラフ（14–19ノード）: SA-GWOアルゴリズムは、標準的な二段階参照アルゴリズムを大幅に上回った。多くの場合、CPLEXで見出された最適解に非常に近い結果を出した。
• 大規模グラフ（20–25ノード）: SA-GWOはCPLEXの最適解には到達しなかったものの（NP困難な問題においてこれは予想されることである）、標準的なGWOアルゴリズムよりも優位性を示し、使用される最大周波数スロット数を減少させた。
• スケーラビリティ: ハイブリッド・アプローチは、グラフのサイズが増大するにつれて複雑さが増しても堅牢であることを証明した。一方で、標準的なGWOは、ハイブリッド版と比較して大きな性能格差を示した。

意義と主張
本論文は、提案されたSA-GWOアプローチが、周波数スロットの割り当てを最適化することで、ネットワーク容量を効果的に向上させることを主張している。主な意義は、グローバル探索とローカル活用のより良いバランスを実現するアルゴリズムの能力にある。シミュレーテッド・アニーリングを組み込むことで、本手法は、大規模なRSA問題において一般的な問題である局所解へのトラップのリスクを軽減する。

著者らは、ハイブリッド技術が、伝統的なアプローチと比較してスペクトル断片化を大幅に最小化し、リソース利用を最大化すると結論付けている。彼らは、この研究を、厳密な手法（CPLEXのような）が計算量的に困難になる複雑かつ大規模なRSA問題を解決するための、高品質なヒューリスティックな代替案としてのステップとして位置づけている。

今後の展望
著者らは、以下の方向性を含む将来の研究を控えめに概説している。

• リアルタイムのトラフィック需要を処理するための動的スペクトル割り当てシナリオへの拡張。
• 消費電力とレイテンシに同時に対処するための多目的最適化の調査。
• 予測的なスペクトル割り当てを改善するための、機械学習ベースのヒューリスティックの統合の探求。