最短経路問題に対する粘菌アルゴリズムの収束性
2010SE202 白田勉
指導教員：小藤俊幸

1

はじめにf (Q) = α|Q| より

本研究では, 粘菌を用いて輸送ネットワークの最短経路を導き出す数学モデルについて述べる. このモデルは生物学上の観察に基づいており, 迷路や地図のような複雑なネットワークの経路探索に使うことができる.

2

最短経路問題をとくアルゴリズム

最短経路問題を解く一番有名な技術にダイクストラ法がある. この方法は正しい最短ルートを発見することができる. しかしノード数が増えるとコンピュータ計算が極端に時間が必要になるというデメリットがある.

3

粘菌による最短経路問題の数学モデル

粘菌に食料源を与えたとき粘菌の一部が食料源の上に集まり二つ, 三つの管が結ばれる. 粘菌の一部で結ばれた道は迷路の中であっても最短の道である.[2]
過去の実験から下記のことが示されている.
・開口管は消滅する可能性が高い.
・二つ以上の管が二つの食料源を結ぶとき, 長い方の管は徐々に消滅する.

dDij = α|Qij | − rDijdt(6)f (Q) は増加関数で f (0) = 0. この方程式から伝導性が急激に減少する傾向にあることが示される.
(1)-(3) の式より,
 −I0 j = 1
∑ Dij
(7)
(pi − pj ) =I0 j = 2Lij 0 その他
iDij
P2 =0 とおくと,(5) 式よりすべての Pi と Qij = Lij(pi −pj ) をそれぞれ確定することができる.
ここで注意することがる.Dij は (4) 式によって変化する
一方で, 例えばさまざまな pi や Qij はそれぞれの瞬間のDij ,Lij により (5) 式を解き, 明確にすることによって確定される.
伝導性は管の厚さ, 管の消滅に密接に関わっている.

4

経路探索の実演

二つの特別なノード, 食料原は N1 , N2 .N1 と N2 の間は Mij と示される. 変数 Qij は Mij を通して Ni から Njまで変動する. ポアズイユ流れと仮定すれば変動 Qij は

Qij =Dij(pi − pj )Lij(1)と与えられる. Pi はノード N1 の圧力, Li j は Mi j の長さ, Dij は Mij の伝導性である. それぞれのノードにキルヒホフの法則を考察すれば∑
Qij = 0(j ≠ 1, 2)(2)iが与えられる. もとのノード N1 と受信側のノード N2 から二つの方程式∑
Qi1 + I0 = 0(3)

I0 :流入する流量 I1 :流出する流量 L:辺の長さ Q:流量
Pi :頂点 i の圧力
節点 1 を圧力の基準点とし,P1 = 0 とおく. 流入する流量と流出する流量は一致している.
(1) 式より
Q1 =D1D1(p0 − p1 ) =p0L1L1(8)

Q2 =

D2
D2(p0 − p1 ) =p0L2L2(9)i∑Qi2 − I0 = 0(4)iが得られる. I0 はもとのノードから流れてくる. このモデルで I0 は定数であると注意しなければならない. 伝導性
Dij は時間で変化する. 変数 Qij によれば次のように表される

dDij = f (|Qij |) − rDijdt(5)と示される. これより, 節点 0 の圧力 p0 を求めることができる.

Q1 + Q2 = I0 → (D2D1+)p0 = I0
L1L2I0D2
L1 + L2→ p0 = D1(10)伝導性 D1 ,D2 は

dD1I0
D1 = α|| − rD1
D21dt
L1 DL + L(11)dI0
D2
D2 = α|| − rD2
D21dt
L2 DL + L(12)1122となる. それぞれを f (D1 , D2 ), g(D1 , D2 ) として,f (D1 , D2 ) = 0, g(D1 , D2 ) = 0 をみたす平衡点 (D1 , D2 )を探す.

D1 ≧ 0,D2 ≧ 0,(D1 , D2 ) ≠ 0 の場合を考えると (11),(12)の式がそれぞれD1 (αI0 L2− r) = 0
L2 D1 + L1 D2(13)D2 (αI0 L1− r) = 0
L2 D1 + L1 D2(14)と変形することができる. そしてここから解を求めると,(D1 , D2 ) = (0,αI0 )rα= ( I0 , 0)r

具体的にパラメータを α = r = 1, L1 =1, L2 =2,I0 =1 とおいて考えると, 平衡点 (1,0),(0,1) で下の図のようになる.

srand48(50)d[0][1]=0.710943, d[0][2]=0.979425, d[0][3]=0.018650,
d[0][4]=0.146505, d[0][5]=0.986598, d[0][6]=0.584182,
d[0][7]=0.461962.
d[1][2]=0.452157, d[1][3]=0.703557, d[1][4]=0.804022,
d[1][5]=0.704205, d[1][6]=0.334573, d[1][7]=0.734250.
d[2][3]=0.457446, d[2][4]=0.222292, d[2][5]=0.615298,
d[2][6]=0.825747, d[2][7]=0.615784.
d[3][4]=0.263695, d[3][5]=0.956441, d[3][6]=0.767507,
d[3][7]=0.157245.
d[4][5]=0.612721, d[4][6]=0.521288, d[4][7]=0.772524.
d[5][6]=0.022071, d[5][7]=0.035796.
d[6][7]=0.697342.
実行結果
q[0][1]=0.094303 q[0][2]=0.903521 q[0][3]=0.002176
q[1][4]=0.029543 q[1][5]=0.064760
q[2][4]=0.776673 q[2][6]=0.126848
q[3][6]=0.002176
q[4][5]=0.806148 q[4][6]=0.000069
q[5][7]=0.870907
q[6][7]=0.129093
各節点からあるいくつの道の中から数値が１に近い道をたどるルートが答えである.
0-2-4-5-7 のルートをたどっているので伝導性をランダムで与えても最短のルートを選ぶことがわかる.

5

上記の図は三つの範囲に分かれている.∆t 秒後に,D1軸,D2 軸,(13) 式で囲まれた範囲は++方向,(13) 式と (14)式の間の範囲は+-方向, それ以外の範囲は–方向に動く.
つまりどの点においても最終的には (1,0) に収まる. よって (1,0) が距離が短いルートだと分かる.
次にノード数を増やした複雑な経路の問題を考える. 下
記の図の各ノードに対してランダムに伝導性を与える.
図の最短経路は,0-2-4-5-7 であるが, 伝導性をランダムで与えてものこの様になるかをプログラムを用いて調べる.

おわりに

本研究では, 粘菌を使った最短経路探索問題を数学モデル化した. 簡単な経路を使った問題では, モデル化した式をしていきに具体的にパラメータを与えることでグラフとして表すことができ, 短い方の道へと収束することがわかった. ノード数を増やした問題ではまず伝導性の値をランダムに与え, どのような値であっても最短の道を選ぶのかを調べ, いかなる数値が与えられた場合でも最短の道に収束した.

参考文献[1] 中垣俊之 著: 『粘菌 その驚くべき知性』,PHP サ
イエンス・ワールド新書 (2010).
[2] Atsushi Tero,Ryo Kobayashi,Toshiyuki Nakagaki:Physarum solver,A biologically inspired
method of road-network navigation(2006)