最小脆弱性問題とは、グラフ上で特定の2頂点間に$k$本のパスの集合をペナルティが最小となるように見つける問題である。グラフの各辺にはコスト、脆弱性、容量が非負整数値として設定され、脆弱性を超える数のパスで使用されるとコストと同じだけのペナルティが発生する。また、容量を超える数のパスで使用することはできないという制約がある。この問題は、通信ネットワークの設計や信頼性の高いマルチキャスト通信などに応用できるが[1,2]、NP困難であり、一般的なグラフに対する効率的なアルゴリズムは知られていない[3]。

この問題に対し、本研究では粘菌アルゴリズムを適用する。生物に着想を得たアルゴリズムは、複雑な問題を解決するために多くの研究者の関心を集めている。その中でも、真正粘菌であるモジホコリによる経路探索のメカニズムに基づいた粘菌アルゴリズムは、様々な最適化問題に対して適用事例があるため[4,5]、最小脆弱性問題に対しても適用の可能性がある。そこで本研究では、粘菌アルゴリズムに基づく最小脆弱性問題の近似解法を開発する。

最小脆弱性問題の特殊ケースである最小共有辺問題は、最小費用流問題の厳密解法があれば、それを用いて厳密解の高々$k-1$倍の近似解が得られることが知られている[2]。これに着想を得て、最小脆弱性問題を最小費用流問題に還元して、その近似解を求めることを考える。
提案手法では、粘菌アルゴリズムの基本的な枠組みは維持しつつ、リンクの長さの更新式を追加することで、リンクの流量に伴うリンクの長さの変化とリンクの容量制約を考慮する。

以下では、Teroら[4]が提案した数理モデルを説明する。

粘菌によるネットワークをグラフ$G(N,M)$で表すと、管はリンクに、管の分岐点はノードに対応する。始点ノードと終点ノードをそれぞれ$N_1$と$N_2$とし、$N_i$と$N_j$の間のリンクを$M_{ij}$と表す。

管内の流れをおおよそハーゲン・ポアズイユ流れとみなすと、$M_{ij}$の流量$Q_{ij}$は次のように表される。ここで、$D_{ij}$と$L_{ij}$はそれぞれ$M_{ij}$のコンダクティビティと長さ、$p_i$は$N_i$における圧力である。

各ノードでは、流入量と流出量がつりあい、始点ノードと終点ノードでは一定の流量$I_0$が流入出するため、次の式が得られる。このネットワークポアソン方程式を解くことで$p$が求められる。

$Q_{ij}$に対する$D_{ij}$の適応的変化を考えると、更新されたコンダクティビティは次のように表される。ここで、$f$は$f(0)=0$を満たす単調増加連続関数、$h$は時間の刻み幅である。

リンクの流量は対応する辺が使用されるパスの数に対応する。よって、$I_0=k$となる。

リンクの長さの更新式は式(3)と同様に次のようにする。ここで、$g(Q_{ij})$はリンクの流量に対応するリンクの長さであり、次のように定義される。ここで、$Cost_{ij}$、$Vul_{ij}$、$Cap_{ij}$はそれぞれ$M_{ij}$のコスト、脆弱性、容量であり、$c$は$0<c<1/(|M|-1)$を満たす実数である。

なお、式(5)は離散的であり、しばしば計算の収束を妨げるため、代わりに滑らかに近似した関数を用いる。

提案手法が最小脆弱性問題の近似解法として有効であることを示すために、図1(a)に示すグラフを用いて実験を行った。グラフ中の四角は始点と終点を表し、細線が1回使用された辺、太線が２回以上使用された辺を表す。

実験には次の関数を用いた。ここで、aは正の実数である。

また、実験では各パラメータに、$Cost_{ij}=1$、$Vul_{ij}=1$、$Cap_{ij}=k$、$c=1/|M|$、$a=100$、$h=1/120$を用いた。

$k$を1から6まで変化させてアルゴリズムを実行したところ、図1(b-f)に示すパスの集合が得られた。表1はその際の反復回数とペナルティを示しており、$k$が大きくなると反復回数が増加する傾向があるが、$k=4$以降は解が変化せず、反復回数が大きく変化しないことが読み取れる。

実験の結果、提案手法は最小脆弱性問題の解を得ることができることがわかった。図1(b-f)に示す通り、可能な限り辺を共有しないようなパスの集合が得られており、これは負荷を分散するようなネットワークの設計に応用可能性がある。

しかしながら、提案手法には課題も存在しており、現状ではパラメータに関する分析が不十分であり、それぞれが解の収束に与える影響が不明瞭である。

提案手法は粘菌アルゴリズムに基づくため、実装の容易さや性能の向上の可能性が従来の手法より高い。今後は、パラメータや初期状態の最適化に取り組むことで、提案手法の発展を目指す。

本研究では、粘菌アルゴリズムを用いて、最小脆弱性問題の近似解を求める方法を提案した。提案手法は、粘菌アルゴリズムをベースに変更を加えたものであり、リンクの長さを反復計算のたびに適応的に変化させるようにした。

また、迷路を模したグラフで提案手法を実行する実験を行い、評価を行った。実験の結果、提案した粘菌アルゴリズムを用いて、最小脆弱性問題の解を得ることができることが明らかになった。しかし、パラメータの設定によっては解に収束しないことがあることもわかった。パラメータが結果に及ぼす影響を更なる実験によって分析することが課題である。