粘菌アルゴリズムによる最短経路問題の解法
2010SE277 横山 優希
指導教員：小藤 俊幸

1

はじめに

本研究で扱う粘菌とは真性粘菌というもので, さらに具体的に名前を述べるとすればモジホコリという名前の粘菌である. 粘菌の持つ基本的な特性として, 粘菌自身の体を流動的に運動させて餌を捕食する性質を持っており, 餌を配置するとそこに向かって管状に移動する. このことか
ら変形菌とも言われている. さらに, この粘菌という生物はおもしろい性質がある. その性質というのは, 迷路状の地形の入り口と出口に餌を配置すると最短経路を通って迷路上を進むと言うものである. 本研究では, その性質について述べられた論文 [1] の数学モデルを参考にし,C 言語により最短経路問題を解くプログラムを組んで, そのプログラムを使って例題を実際に解き, 実験結果を記している.

2

粘菌と最短経路問題

2.1

粘菌のもつ性質と有用性

粘菌の持つ性質とは何か, それは複数箇所に餌を配置されるとすべての餌を得るために餌から餌へと体を伸縮させるということである. この性質は最短経路問題の解決法の一つとしてあげることができる. 最短経路問題を解くときにもっとも有名とされているものはダイクストラ法である. しかし, この方法では正確な最短経路を識別することは可能であるものの, 複数箇所の目的地つまりノード数が多ければ多いほど必要な計算時間が過剰になってしまう. ここで, 最短経路を見つけるときの条件を三つ述べる.

- 確実に最短経路を見つけるということ.
- 経路検索の迅速性.
- 情報の更新からの最短経路の再設定に対する適応性粘菌はこの三つの条件を満たして経路を見つけることができる.
2.2

粘菌を用いた実験方法

ここからは, 具体的に実験方法について述べていく. 粘菌により最短経路を見つける実験方法の一つとして次のものがある. 初めに迷路の中に餌を二ヶ所配置し, そしてそこに粘菌をおく. すると粘菌は様々な経路を通って餌まで辿り着こうとする. しかし, 時間が経つと最短経路を通る粘菌の管以外はなくなり, 一本の道となる. そのことで最短経路を見つけることができると言うわけだ. また,粘菌はある光や危険な化学物質を嫌うためそれを粘菌の通り道に配置するとその箇所を避けて最短経路を見つけようとするのである. しかし, この実験には欠点があり餌の量が均一に配置されていなければ多く餌のあるところに粘菌が行ってしまうこと, さらに迷路内での実験だと粘菌が壁を乗り越えてしまう可能性があるというものだ.

数学的モデル3

ノードの数 (餌の数) を Ni から Nj まで設置さらに, 流れは N1 から N2 へと流れていくものとしてポアズイユ流れの法則を用いて仮定すると (1) 式が導かれる.

Qij =Dij(pi − pj )
Lij

(1)

この時,pi は Ni の圧力,pj は Nj の圧力を示し,Lij は Ni ,Nj間の長さ (Mij ),Dij は伝導率を示す. また Qij は流量を示している. また, 各ノードに対してキルヒホッフの法則を考慮すると, 以下のような式を得られる.

 X
Qij = 0 (j ≠ 1, 2 のとき)i X
Qi1 + I0 = 0iXQi2 − I0 = 0


(2)


 −I0 (j = 1)
X Dij
(pi − pj ) =I0 (j = 2)
Lij
 0(j ≠ 1, 2)i(3)dDij = f (|Qij |) − γDij
dt(4)

i

I0 は最初のノードから流れる量である. つまり, 始点と終点は一方的に流れ続け, 流れ込みつづけるため I0 を式に入れることで和を 0 としており, 途中のノードでは流れ込んでくる量, 流れていく量が同じなため総和が 0 になっている. さらに (1) 式 (2) 式を組み合わせると,(3) 式のようにまとめられる.

各ノードにおいて (3) 式をそれぞれ立てて連立方程式を解くことで pi の値が得られる. また,Qij によって Dij が変動したとすると.という式が得られ,f (Q) は増加関数であるため,f (0) =0 である. この式から伝導性 Dij が減少する傾向にある.
f (Q) = α|Q| として (3) 式に代入すると.

dDij = α|Qij | − γDijdt(5)

この式は Qij によって変動される Dij を求めるための式となっていて, α,γ は正の定数である.

4粘菌アルゴリズムの実装

4.1

粘菌アルゴリズムの概要

最短経路問題を解く際の手順は以下の通りである.
0(a) 初期時刻の伝導率 Dijを (適当に) 与え,Ni の圧力を基準にする. つまり pi = 0 とする.

(b) 後に示す連立 1 次方程式を解いて, 圧力 p0i を求め, 流量 Q0ij を計算する.
1(c) オイラー近似により, 時刻 t1 での伝導率 Dijを求め
nnる. 以下, 同様に時刻 tn での圧力 pi , 流量 Qij を求め,n+1オイラー近似により, 時刻 tn+1 での伝導率 Dijを求める.

(b) で記した連立 1 次方程式というのは,Qnij =nDij(pn − pnj )n
Lij i(6)図 1 最短経路問題

を以下の式に代入して,
 X nQij = 0 (j ≠ 1, 2 のとき)


i

X

Qni1 + I0 = 0iXQni2 − I0 = 0(7)i

それで得られた式nX Dijnn(p−p)=jLnij i
i−I0 (j = 1)
I0 (j = 2)0(j ≠ 1, 2)(8)

これを各ノードにおいて p0i の連立 1 次方程式を立てる.
その方程式をガウス消去法で解き p0i を求める. 流量 Q0ijが求められたら, 次の時刻の伝導率を更新するために, 以下のオイラー近似を用いる.
n+1nnDij= Dij+ δt(α|Qnij | − γDij)(9)

ここでは α = 1.0,γ = 1.0,δ = 0.1 としている. 次に (9)n+1式で得られた Dijを用いて, 同様に計算をしていく.

4.2

プログラムの実装

今回作成したプログラムは, まずあらかじめ決められたノード間の距離, 伝導率を打ち込み, 読み込ませる. a[i][j]という変数を用いるのだが, この時の a[i][j] というものは,
ノード Ni での (8) における圧力 pj の係数を代入する配列として扱っている. 各ノードにおいて,p[i] の係数の値を代入していくのだが, ノード i と pj が一致する場合 (i = j).
X Dijそつまり, 対角成分においては a[i][i] を a[i][i] =Lijj

Dijのように代入れ以外の非対角成分の時は a[i][j] = −Lijする. その後 p[i] の初期値をノード 0 を 1.0, それ以外を0.0 とし a[i][j] と p[i] との連立方程式をガウス消去法で解き,(6) 式を用いて Q を求める. その後, 伝導率 D の更新を (9) 式を用いて求める. この手順を 100 回ループさせたものがこのプログラムとなる.

5

実験結果

図 1 のような最短経路問題があったとする. この問題0においては Dijを適当にあたえて, 先ほど説明したプログ
ラムで解くと次のような値が得られる


99
99
Q99

01 = 0.003378, Q04 = 0.719808, Q05 = 0.276814



99
99

Q12 = 0.003140, Q14 = 0.000238



99
99

Q99

23 = 0.120676, Q24 = −0.237229, Q29 = 0.119693



99

 Q39 = 0.120676
99
Q99
45 = 0.001184, Q46 = 0.481633
99

Q56 = 0.004722, Q99

57 = 0.273276

99
99

Q67 = −0.000010, Q99

68 = 0.455848, Q69 = 0.030517



99

Q78 = 0.273266
 99
Q89 = 0.729114
この時の Q99
ij が相対的に大きければ大きいほど粘菌がNi ,Nj 間を最短経路とみなして移動するということである. つまりこの最短経路問題は 0 → 4 → 6 → 8 → 9 が最短経路であると言える.

6

おわりに我々が目にするであろうカーナビ. 最短経路のルートを見つけれるだけでなく,「事故による情報の更新といった条件」も粘菌を使った最短経路問題の解法はクリアできる. さらに, 光や, 化学物質を避けるといった性質を利用す
れば鉄道の線路を効率よく敷くための最短経路を導き出せる. 日本地図上の山や川など線路を敷けない地形に光や化学物質を配置し, 駅をおきたい場所に餌を並べておけば粘菌が効率の良い線路の敷き方を示してくれるといった具合である. また, この数学モデルからプログラムを組み実験を行うことで, プログラムの正確であることが分かり粘菌アルゴリズムに対して理解が深まった. 今後の課題としては, 実際に粘菌を捕獲し実験しさらに理解を深めたい.

参考文献[1] Atushi Tero,Ryo Kobayashi,Toshiyuki Nakagaki:”Physarum solver: A biologically inspired
method of road-network navigation”,2006[2] 中垣俊之.『粘菌 その驚くべき知性』, 株式会社 PHP研究所,2010.

[3] 築 地 克 弥, 松 田 千 夏, 高 橋 和 成.『 忌 避 化 学 物質を利用した粘菌変形体のネットワーク形成』.
http://www.ous.ac.jp/garden/kenkyuhoukoku/16/Naturalistae
39-45.pdf