TALS: Emergent Colonization and Graph partitioning

Summarized in Japanese by Y. Kanada.

Created: 6/21/94, Modified: 6/24/95.

参照 : [金田のホームページ], [親ページ].

まえおき

  1. この論文をとりあげた理由 : ALife 的な手法でグラフ分割の問題をといている -- 金田の計算モデル CCM に似たかんがえかたで，いままで CCM でといてきたのと類似する問題を といているからである．ただし，グラフ分割は仕様が明確で静的な問題なので， ALife 的な手法が適した問題であるかどうかは疑問である．
  2. 本文中の [...] は金田の補足ないし注釈．

Abstract

古典的な最適化の問題であるグラフ分割を種の動的な共適応 (co-adaptation) の 問題に変換した．さまざまな種の自律的な animats の人工的な社会をつくり， 共適応によって，最適化問題の解に一致する territorial colonization にいた る．われわれのモデルはこのグラフ分割問題のための社会をコントロールする 規則の集合として最小限のものであることが実験的にわかった．また，シミュレー ションの結果はこの，あたらしい分散アルゴリズムが適切でロバストであることを しめしている．

1. Introduction

  1. 自然のシステムが複雑なのはその要素や内的なダイナミクスが複雑だから ではなくて，自己組織・創発によってもたらされる．

  2. Territorial colonization は創発的な属性のひとつ．有限な資源が空間的 分布に分布しているために個体が競争して，コロニーが創発する．
  3. コロニーとは，``有機体の集合であって，部分的に群をなして いて，サイズや時間のうえで比較的安定であり，そのメンバー間で高水準の相互 作用がみられるもの'' のことをいう [1]．

  4. Territorial colonization は，かならずしもエージェント間の高水準の組織に 依存しているのではない... [創発している]．``Swarm intelligence'' で ある．

  5. この論文では ``swarm intelligence'' パラダイムをつかってグラフ分割問題 のあたらしいアルゴリズムを開発する．
  6. グラフ分割問題とその応用の説明 [ここでは省略]．

  7. [この方法でグラフ分割問題をとくと] 大域的な目的をまったくしらない animats によって大域的な分割が創発する．

2. Swarm Intelligence and Combinatorial Optimization

  1. ``Swarm intelligence'' によるくみあわせ最適化 : これまでに最短経路問題，巡回セールスマン問題，クラスタリングなどの あたらしいアルゴリズムがみつかっている．

  2. 自然のシステムの「複雑さ」は，アルゴリズム論でいう「複雑さ」とは ちがう : アルゴリズム論ではあらかじめ明確に定義された問題を自動的な 手続きでとくときの困難さをいうが，自然のシステムではあらかじめわかる 「結末」によってきめられるものではない．
  3. 自然のシステムにおいては，「結末」[目的] はあらかじめきめられていない． おおくのばあい「結末」をもとめることが目的である．...

  4. Swarm 機能論理のひとつの特異性は，animat の社会とその環境との相互の 共決定性にある．
  5. システムの自己組織性は Grasse [9] によって導入された stigmergy の概念にもとづくことができる．
  6. Grasse は，しろありの巣において，大域的な仕事をするのに，はたらきありの 間でコミュニケーションがどのように必要ないかをしめした．
  7. はたらきありは，あらたな刺激をつくりだすことによって環境をかえる． その刺激があらたな反応をおこすということをくりかえして，ある種の 構造が創発する -- 自己触媒的．

3. The Co-adaptation Model

3.1 The Clique Partitioning Problem (問題の定義と基本機構)

  1. G = (V, E, w): n 個の頂点集合 V と関数 w : E → R [実数] によっておもみづけられた辺の集合 E とからなる完全グラフ．
  2. P = (V1, ..., Vp): 集合 V の p 個のクラス ("cliques") への分割をもとめる (p はあたえられない)．
  3. f を最小化する :
    f(P) =
    Σ(k = 1, p) Σ((u, v) ∈ E, u ∈ Vk,v ∈ Vk w(u, v)) w(u, v)

  4. グラフの頂点を animats とみなし，それらがコロニーをつくる．
  5. Majority rule: コロニーは過半数がおなじ種の頂点の集合．
  6. f は明示的には計算しない．

  7. この機構は，すべての animats に共通な移動戦略，強化手続き，aging 機構 によってうごかされる．
  8. 移動戦略: animats が自種のコロニーにとどまるか，他種の コロニーを脱出するようなうごきを好む．
  9. 強化手続き: あたらしい世代では territorial colonization が大域的に向上するように，局所的に好ましい移動が強化される．
  10. Aging 機構: ふるい世代は aging 機構によってしだいに きえていく．(時間は不連続)

3.2 Animats and Environment Characteristics

  1. 社会の環境は 4 つぐみ (V, E, w, e) によってきまる．
  2. V: 頂点の集合，E: 辺の集合， w: 辺のおもみ，e(x): 個体 x の種．
  3. vt(x): 時刻 t における個体の位置． G の頂点によって定義される，
  4. at(x): 時刻 t における個体の年齢．
  5. st(x): 満足度 (2 値)．
  6. この機構は全 animats に共通な関数 rt と，複数の種の個体が同数 のときにつかうヒューリスティック h にも依存する．

3.2.1 Initialization

  1. q >= p とする (q は最適分割における種の数，p は分割数)
  2. 種は絶滅することがあるが，あたらしくできることはない．
  3. 初期状態では，animats は種に関して一様に分布し，ランダム・グラフの頂点に わりあてられる．

  4. wv(u, v): ... Sigmoid 関数．

3.2.2 The age function at

  1. 時刻がすすんだぶんだけ年齢が加算される．
  2. ことなる頂点に移動したときには年齢が加算される．
  3. 年齢が Amax をこえると死ぬ．
  4. 時刻 t における年齢 : at(x) = t + m(vt(x))
    ここで m(vt(x)) = 0， x が vt(x) にとどまるとき
    m(vt(x)) = K.wvt(x) (vt(x), vt+1(x))， vt(x) から vt+1(x) に移動するとき (定数 K > 0)
  5. この戦略によって，極値にとらわれる危険をへらしている．

3.2.3 Satisfaction Function st

  1. 個体は自種の頂点にいるときには満足する．
  2. 満足関数の定義 :
    st(x) = 1，e(x) = e^v(t),
    st(x) = 0，その他のとき．
    [満足関数を 2 値にしているのはまずい ?!]

3.2.4 The Reproduction Function rt

  1. Animats が満足しているときには R 個の同種の 0 歳の animats を生む [無性生殖]．[満足すべき状態を強化する.]
  2. 再生産関数の定義 :
    rt(x, vt(x)) = R，e(x) = ev(t) のとき
    rt(x, vt(x)) = 0，それ以外のとき
  3. ◆◆◆

3.2.5 Equality Case Heuristic h

  1. m 種の個体が頂点 v 上で同数のとき，h によって動作が きめられる．
  2. ... 同数の種について大域的な貢献を評価して，評価のたかいものの個体数を増加させる．
    [ランダム・ノイズをいれるのではだめか?]

  3. 頂点 v の個体数が 0 になったときには，m = q として， おなじ手続きであたらしい animats が生成される．
  4. これは絶滅した種が再生される唯一の方法である．
  5. これは 1 頂点からなる clique において非常に重要である．

3.2.6 The Motion Strategy of an Animat

Animat の選択
  1. 逐次マシンで分散環境をシミュレートするために，モンテカルロ法をつかっている．
  2. Animat x はランダムに選択枝，移動の確率はつぎの式できめる :
    Prob(x, move) = at(x) / Amax　[???]
行き先の頂点の選択
  1. st(x) = 1 のとき (同種のものの頂点にいるとき) :
    移動しない確率がたかいが，移動元と移動先のあいだの辺のおもみに反比例する確率で 移動する．
  2. st(x) = 0 のとき (異種のものの頂点にいるとき) :
    移動元と移動先のあいだの辺のおもみに比例する確率で移動する．[???]

4. Model Parameters and Validation

4.1 The Model Sensibility to Parameters (パラメタに関するモデルの感度)

  1. 現実の問題からとった例 (G1, ..., G6) で 2000 回の animats の移動を 50 回 くりかえして平均値をもとめた．
  2. 5 つのパラメタ : N (Animats の初期個体数)，Amax (寿命)， R (再生産率)，q (初期状態での種の数)， K (移動が年齢にあたえる影響)．
  3. G1 について最適なパラメタ値をやまのぼり法でもとめて，G2, ..., G4 にはそのまま， G5, G6 には補正をかけてつかった．
  4. ある種のなだれ現象が寿命と関係していることが指摘されている (図 1)．...
  5. パラメタが解の最適性にあたえる影響を図 (2, 4, 5, 6) にしめしている．

4.2 Model Experimental Validation

  1. h, rt, at などの相対的な重要性をしらべる．
  2. これらの関数の一部を無効化した 7 つのモデルを評価する (表 2)． (移動戦略の無効化 : 移動先をランダムに選択)
  3. Aging によって個体数を制御しないと最適解にちかづくのに必要のない環境変化が たえまなくおこるようになる．
  4. Aging がないと種がきえさることがなくなり，種の数と最適な clique 数が一致 しなくなる．
  5. ヒューリスティック h がないと局所最適点にとどまりやすい．(最適なグラフに 少数の点からなる clique があるとき)

  6. この実験から，これらすべての関数が重要であることがしめされた．
  7. とくに，h によって微妙な G1 の分割が可能にされている (最適解は唯一 (?))．

5. Simulation Results

  1. 表 3: 小規模の問題では 92 % 以上，大規模の問題でも 80 % 以上で最適解が もとめられた．標準偏差もちいさい．
  2. 計算時間 (反復回数) も，逐次計算でもじゅうぶんみじかい．

  3. 最適状態のちかくで非周期的な環境変動がみられる (図 7)．
  4. 最適状態はもっとも頻繁におとずれる状態 -- 最頻状態を解とみなせる．
  5. 大域的な基準にもとづく計算なしに最適にちかい解がもとめられる．

  6. 種の適応という点からこのシステムのダイナミクスを解析すると，「いきのこる」 ことが種のおもな非明示的な目的になっていることがわかる．
  7. ◆◆◆

6. Conclusion

  1. Territorial colonization をみちびくモデルを提案した．
  2. この colonization のふるまいはあらかじめきめられた適応関数によらずに， 自己組織化によって創発する; Packerd [17] によって導入された intrinsic adaptation の例をしめしている．
  3. ここで使用したグラフ分割の問題においては既知の解法と競争できるようにみえる -- 現在，タブー探索，Simulated annealing，GA などと系統的に比較しつつある．
  4. アルゴリズムの複雑さについていうと，この方法には 2 つの利点がある : 大域的な規準なしに解が創発する，本質的に分散的な手続きである．
  5. 並列マシンにインプリメント中．
Y. Kanada (Send comments to kanada@trc.rwcp.or.jp)