駆け足で読む『Swarm Intelligence』

駆け足で読む『Swarm Intelligence; From Natural to Artificial Systems』

Swarm Intelligence: From Natural to Artificial Systems (Santa Fe Institute Studies on the Sciences of Complexity)

• Chapter 1 イントロダクション Introduction
• Chapter 2 アリの食糧探索行動、組み合わせ最適化、意思伝達ネットワークによる経路決定 Ant Foraging Behavior, Combinatorial Optimizaton, and Routing in Communications Network
• Chapter 3 仕事の分割と個々の作業の割り当て Division of Labor and Task Allocation
• Chapter 4 墓地の組織化、たくさんの子の仕分け、データ解析、グラフの分割 Cemetery Organization, Brood Sorting, Data Analysis, and Graph Patitioning
• Chapter 5 自己組織化と鋳型をデータ解析とグラフの分割に適用する Self-Organization and Templates: Application to Data Analysis and Graph Partitioning
• Chapter 6 巣の建築と自立して組み立てること Nest Building and Self-Assembling
• Chapter 7 昆虫とロボットが協力して輸送する Cooperative Transport by Insects and Robots
• Chapter 8 エピローグ Epilogue

駆け足で読む『Swarm Intelligence; From Natural to Artificial Systems』Chapter 1 イントロダクション

• 1.1 社会性のある昆虫(社会性昆虫)
• 1.2 社会性昆虫の集合体としての行動をモデル化する
  • 1.2.1 モデル化、設計すること
  • 1.2.2 社会性昆虫に見られる自己組織化現象
    • 正と負のフィードバック、ランダム性、相互作用
  • 1.2.3 Stigmergy
    • "Stigmergy is a mechanism of indirect coordination between agents or actions."(Wiki)
      • アリが食物探査のときに道にフェロモンを残して、アリ個体群と道上の物質とが「残す」「感知する」という相互作用のもと、探索行動が組織化するような現象のこと

駆け足で読む『Swarm Intelligence; From Natural to Artificial Systems』Chapter 2 アリの食糧探索行動、組み合わせ最適化、意思伝達ネットワークによる経路決定

• ２経路の選択
  • ２つの要素
  • ２択の場合
  • 、ここでは選択肢A,Bのそれぞれに、「実績として起きた事象の数(アリで言えば、アリが落としたフェロモン量)」
  • は非線形の程度を決める。はフェロモンがないときの「得点」→ランダム性のための下駄
• 複数の選択肢でどれかが選ばれていく様子

library(MCMCpack)
Niter<-1000

n<-4
k<-20

A<-4

M<-matrix(0,Niter,A)

for(i in 2:Niter){
	M[i,]<-M[i-1,]
	prob<-(M[i-1,]+k)^n
	prob<-prob/sum(prob)
	s<-sample(1:A,1,prob=prob)
	M[i,s]<-M[i,s]+1
}

matplot(M/((1:Niter)-1),type="l")

• StarLogoというソフト(こちら)
• 平面の探索
  • 平面を正方格子で考えると、それは、正方格子というグラフを空間とした行動であって、「グラフ」を空間にすることで一般化できるだろう
  • 以下のソースは次のように考えている
  • 有限平面を正方格子として、それを表すグラフについて、隣接ノードを列挙する
  • アリは、このグラフ上を確率的に移動する
  • アリは、複数の状態を持つ(エサを巣に持ち帰るときには、エサを持っている状態と持っていない状態の２状態)
  • アリは、自身の状態によって、進行エッジの選択に関して異なる確率ベクトルを持つ
  • アリは、複数の進行エッジの先のノードのフェロモン量に応じて、エッジを選ぶが、かなりの乱雑さを持たせることが、集団としての探索がうまく行くコツのようである(この乱雑さは、フェロモンの総量によらずに下駄をはかせる方がよさそうである(どんなにフェロモンが多くても、一定の確率で、フェロモンのない格子点へも進めるようにする)
  • アリは自身の状態により、異なるフェロモンを現在地に置く
  • アリの置くフェロモンは、特定の状態のアリのエッジ選択情報となる
  • フェロモンは時間とともに消失する
  • 巣とエサの位置は指定する(複数の格子点を一塊として指定するのがよい)
  • エサはアリに持ち帰らせる(結果としていつか消滅する)ようにしてもよいし無尽蔵にしもよい(以下のソースは無尽蔵)
  • 巣とエサとは、生物学的な意味であるが、これは、アリの状態を変更する場所であると定義すればよい
• 解く課題は
  • 経路の最適化・分布の最適化
  • セールスマン問題
  • ２次割り付け問題(Quadratic assignment problem(Wikiはこちら))は(こちらの用量反応曲線に関して用いる、Isotonic regression(こちら)の２次計画問題と同様に最適化の困難問題)

# 正方格子
# 格子の１辺の点の数
N<-100
# 全格子点の２次元座標
XY<-expand.grid(1:N,1:N)
# 格子点の数
Nloc<-length(XY[,1])
# すべての格子点について隣接点を全列挙する
Neighbors<-list()

difX<-outer(XY[,1],XY[,1],"-")
difY<-outer(XY[,2],XY[,2],"-")
for(i in 1:Nloc){
	Neighbors[[i]]<-which(difX[i,]^2+difY[i,]^2<=1)
	Neighbors[[i]]<-Neighbors[[i]][which(Neighbors[[i]]!=i)]
	
	#Neighbors[[i]]<-Neighbors[[i]][sample(1:length(Neighbors[[i]]),2)]
	
}
# アリの数
Nant<-300
# アリの状態数
Nstate<-2
# 初期状態で、すべてのアリは１か所(巣の中)にいることにする
half<-floor(N^2/2+N/2)
Ax<-sample(half:(half+1),Nant,replace=TRUE)
# アリの初期状態も１つ(エサを探しに行く状態)
Sx<-sample(1:1,Nant,replace=TRUE)
# 状態別のアリ分布ベクトル
V<-matrix(0,Nloc,Nstate)

for(i in 1:Nant){
	V[Ax[i],Sx[i]]<-V[Ax[i],Sx[i]]+1
}

# 状態変化指定行列
# ある場所は、ある状態をある状態に変える。それを表す行列
C<-matrix(rep(1:Nstate,Nloc),byrow=TRUE,ncol=Nstate)
# 巣の中心とその半径
Center.1to2<-c(N*2/9,N*2/9)
Radius.1to2<-N/20
# エサのある場所の中心とその半径
Center.2to1<-c(N/2,N/2)
Radius.2to1<-N/20
for(i in 1:Nloc){
	if(sum(XY[i,]-Center.1to2)^2<=Radius.1to2){
		C[i,1]<-2
	}
	if(sum(XY[i,]-Center.2to1)^2<=Radius.2to1){
		C[i,2]<-1
	}
}

# 状態別フェロモン分布ベクトル
P<-matrix(0,Nloc,Nstate)
# 状態別フェロモン下駄値
Pgeta<-rep(0.5,Nstate)
# 状態別フェロモン指数
Pexp<-rep(5,Nstate)
# 状態別フェロモン投下量
Pv<-c(1,1)
# 状態別フェロモン投下対象状態
Pt<-c(2,1)
# 単位時間当たりの減衰率
Pr<-c(0.95,0.95)
# 試行時間
Niter<-10000
par(mfcol=c(2,3))
for(i in 1:Niter){
	# 移動
	tmpV<-matrix(0,Nloc,Nstate)
	for(j in 1:Nstate){
		for(k in 1:Nloc){
			destination<-Neighbors[[k]]
			#prob<-(P[destination,j]+Pgeta[j])^Pexp[j]
			prob<-(P[destination,j])^Pexp[j]
			if(sum(prob)==0){
				prob<-rep(1,length(prob))
			}
			prob<-prob/sum(prob)
			prob<-prob+Pgeta[j]
			prob<-prob/sum(prob)
			s<-sample(destination,V[k,j],replace=TRUE,prob=prob)
			for(l in s){
				tmpV[l,j]<-tmpV[l,j]+1
			}
		}
	}
	# 状態変化
	tmpV2<-matrix(0,Nloc,Nstate)
	for(j in 1:Nstate){
		for(k in 1:Nstate){
			tmp<-which(C[,j]==k)
			tmpV2[tmp,k]<-tmpV2[tmp,k]+tmpV[tmp,j]
		}
		
	}
	V<-tmpV2
	#print(apply(V,2,sum))
	# フェロモン
	# フェロモン減衰
	for(j in 1:Nstate){
		P[,j]<-P[,j]*Pr[j]
	}

	for(j in 1:Nstate){
		P[,Pt[j]]<-P[,Pt[j]]+V[,j]*Pv[j]
	}
	
	#par(ask=FALSE)
	image(matrix(log(P[,1]+1),N,N),main="pheromone1")
	image(matrix(log(P[,2]+1),N,N),main="pheromone2")
	image(matrix(apply(log(P+1),1,sum),N,N),main="pheromone1+2")
	image(matrix(sign(V[,1]),N,N),main="ant1")
	image(matrix(sign(V[,2]),N,N),main="ant2")
	image(matrix(apply(sign(V),1,sum),N,N),main="ant1+2")
	#Sys.sleep(0.1)
	#par(ask=TRUE)
}

駆け足で読む『Swarm Intelligence; From Natural to Artificial Systems』Chapter 3 仕事の分割と個々の作業の割り当て

• 集団での仕事の分割と作業の割り当てについて
  • 個体の違い
    • 出生時期による分業制(temporal polyethism)
    • 分担作業による形態の違い
    • 同一年齢・同一形態の群の中で個体差
• どうやって違いを生じせしめるか
  • 反応閾値モデル
• 作業の種類数
  • 作業が１種類であるモデル
  • 作業が複数種類であるモデル
• 作業の成功・失敗というフィードバックがかかる
• 複数の作業を行うことができる「虫」がいるときに、「待たれている作業」が「虫」をその作業をするように導くこと、周囲で、関連する(前後関係に会ったりする)作業がどのように進められているかという情報が「虫」をその作業をするように仕向けること、等の「相互作用」がある
• 特化すること Specialization
• 仕事の割り当てを硬直化しないこと
• すべてを一つに集中しないこと(遊びを持たせておく)

駆け足で読む『Swarm Intelligence; From Natural to Artificial Systems』Chapter 4 墓地の組織化、たくさんの子の仕分け、データ解析、グラフの分割

• 近傍のみの情報を用いて、単純作業をする「虫」が集まることで、ソート・クラスタリングが進む仕組みに関する章
• 個別にピックアップして、「同様のもののたまっているところ」に置くことの繰り返し
• ソートのアルゴリズムの中にも、隣り合った値を比べて入れ替えるかどうかを決めるものもあって、そもそも、アルゴリズムそのものという側面があるが、「虫」は「必ず」何かをするのではなくて、「確率的に」何かをする、「必ず、こうする」のではなく「こうすることが、ああするよりも」多いというような作業をする
• 蜂の巣で幼虫や蛹のソートが行われて同心円状の形態ができることと、リンパ濾胞が同心円状の形態をなすことは同じだろうか？
• Multidimensional Scaling
• Graph Partitioning

駆け足で読む『Swarm Intelligence; From Natural to Artificial Systems』5 自己組織化と鋳型をデータ解析とグラフの分割に適用する

• ソート・クラスタリングは、並べたり分類されたりすればよいが、この章では、「鋳型」となる形を大きくするような場合の「虫」の仕事の進め方
• 反応拡散系(こちらやこちら)

駆け足で読む『Swarm Intelligence; From Natural to Artificial Systems』6 巣の建築と自立して組み立てること

• Stigmergy (環境との相互作用でなされる行動)
  • Quantitative stigmergy
  • Qualitative stigmergy
• Qualitative stigmergyの例
  • ハチの巣を大きくするときに、正６角形の継ぎ足しにあたって、１辺共有で作るか、２辺共有で作るか、３辺共有で作るかによって、巣の空間占拠具合が変わってくる。その都度、どれにするかを選ばなくては…
  • その継ぎ足し方の違いで、出来上がる巣の高次構造が異なってくる

駆け足で読む『Swarm Intelligence; From Natural to Artificial Systems』7 昆虫とロボットが協力して輸送する

• 一人では運びきれない荷物をどうやって、みんなで運ぶことにするのか
• 年に１度、神輿を担ぐことや、６年に一度、御柱を運ぶのは、「協力」の練習？