TALS: Divide to Coordinate: Coevolutionary Problem Solving

Revised Version.

Summarized in Japanese by Y. Kanada.

Created: 9/17/94, Modified: 6/22/95.

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

まえおき

  1. この論文をとりあげた理由 : ALife の論文ではないが，複雑系における創発的な問題解決をめざしている -- 金田の計算モデル CCM と共通の目的をもち， かつ類似の手法をつかっている． しかもこの研究はこれまでの CCM の研究方向とはちがって物理的な背景をもっているので，CCM の今後の研究方向をきめるうえで示唆的である．
  2. 本文中の [...] は金田の補足ないし注釈． CCM に関する注釈はこの論文とは関係がないので無視してよい．

1. Introduction
  1. サブタスクやエージェントを調整してふるまい (performance) を最適化するには，どの 変更もつねに全体の性能を利することを保証するように [大域最適化として] おこなわれることがしばしば 仮定される : ビジネス，軍事，政治組織から自動的な問題解決まで．
  2. この論文の目的は，それとはちがう可能性を追究すること -- 矛盾する制約をふくむ非常に困難な問題を最適化する subtasks のあいだの 調整は，全体の問題をサブタスク, エージェントのサブグループ, "patches" などにわけることによって，よりよくできるかもしれない．
  3. 各 patch は自分のふるまいを最適化するように利己的にはたらく [局所最適化をする] -- それが他のサブタスクや patch が対している問題をかえてしまう ことにはおかまいなしに．
  4. 全体のふるまいはそれらのシステムの創発的て集団的 (collective) なふるまいとして生じる．

  5. とりあげる問題 : NK モデル -- spin-glass の一種 [じつは spin-glass とは非常にちがう (?!)].
  6. 最適化の目的 : エネルギーがひくくなるシステム変数の configuration をもとめる．
  7. 主要な問題
    1. 問題を分割して各部分か利己的な最適化をすることによって，全体を 最適化するよりよい解がえられるような NK の問題が存在するか．
    2. もしそれがあるなら，最適な分割はあるか (-- ある)．
    3. なにが最適性を特徴づけるか (-- システムを秩序と無秩序の境界付近におくこと [edge of chaos?] でしばしば特徴づけられる)．
      …

2. The model
  1. N 個のスピン [結晶中の原子あるいは染色体中の遺伝子のようなもの]．
  2. 各スピンは 2 状態 : 0, 1．
  3. スピンの状態によってエネルギーがかわる．
  4. あるスピンのエネルギーはそれ自身と他の K 個のスピン (任意の方法でえらべる, 0 <= K < N) の状態に依存する [K が増加 -- coupling が強化]．
  5. [K 個のスピンの状態と，それによってきまるスピンのエネルギー との関係は，下記の実験ではランダムにあたえられる -- ランダムな landscape.]
  6. 具体的な問題設定 : 120 x 120 の 2 次元格子状のスピンをかんがえる． K = 4, 8, 12, 24 (Figure. 1).
  7. 全スピンによってきまるエネルギーないし適応度は 0 〜 1 の値をとるとする (式 (1)) -- 各スピンのエネルギーの平均値としてあらわされる [CCM も同様]．
  8. Figure 2: N = 3, K = 2 の例．

2.1 Patches: partitioning the system into domains

  1. 120 x 120 の格子からスピンをランダムにえらんで反転させる (Glauber dynamics)．
  2. スピンの初期値はランダム．
分割によってよりよい解がえられることはあるか?
  1. 全体のエネルギーが低下するときだけ (温度 0 で) 反転させるようにすると，わるい (poor) local minimum にとらわれる．
  2. 格子を 60 x 60 ずつに 4 分割しておなじことをすると，全体に対して のときより local minimum にとらわれにくくなる : もとの local minimum が分割後は local minimum でなくなることがある [その可能性がたかい]．
  3. Patch にわけることでシステムはわるい local minimum からのがれることができる [CCM においてもたしかめられている -- CCM では patch size は反応規則の規模に相当]．
エネルギーを最小化するために最適な分割はなにか? その特徴は?
  1. 120 x 120 の格子を p x q (p, q は 120 の約数) に分割する．
  2. ランダムに選択したスピンをふくむ分割のエネルギーが低下する ときだけ反転させる (modified Glauber dynamics)．
  3. 3 つの更新法:
  4. エネルギーが収束するまで実行する． だいたい 50 世代以下で収束する (N ステップを "1 世代" とする)．
  5. 以下の結果は 50 回のことなるランダムな landscape についての試行の平均．

3. Results

3.1 Squares vs. other partitionings

  1. 正方形がもっとも性能がよく，それからはずれるにつれて 性能が低下する．
  2. 120 x 120 の格子を p x p という正方形の patch に分割する (p = 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120)．

3.2 Optimal patch size

  1. 最適な patch size は K に依存する．
  2. K がちいさいと landscape はなめらかで，120 x 120 が最適．
  3. K が増加するにつれて landscape に起伏ができる．
  4. Figure 3-5 (それぞれ random, fitter, greedy updating) が K = 4 の結果．
    Random, fitter では local minimum なし．
    Greedy では local minimum がある (ただし，ばらつきがおおきい)．
  5. Figure 6-8 が K = 8, Figure 9-11 が K = 12, Figure 12-14 が K = 24 の結果．
    Patch size が 120 x 120 よりはるかにちいさいときにエネルギーは 最小になる -- この結果は t 検定により有意．
    ただし，K = 4, greedy のときは p = 120 のときが最低．
  6. K を一定 (12) にして N をかえたときの patch size とエネルギーとの関係をみた (Figure 15)． 最適な patch size は N がおおきくなると一定値にちかづく (?)

3.3 A phase transition in patched lattices

  1. Patch size p = 120 のときには秩序的なふるまいをする (もよりの local minimum に収束する)．
  2. p = 1 のときは K 入力の Boolean network になる -- カオティックなふるまいをする．
  3. 1 <= p < 120 のどこかで相転移するはず : p < 6 のときはほとんどのスピンが反転するが，p = 6 になると突然大半のスピンが凍結する (random, greedy のとき)．
  4. Figure 16 は p = 5 (fitter dynamics) のときにどのスピンがよりおおく反転したかをしめしたもの (黒いのがよりおおく反転した部分) -- patch size がはっきりみてとれる [patch を固定するからスピンの凍結がおこる (?) -- CCM では可動]．
  5. Figure 17 は p = 6 のとき．ほとんどのスピンは凍結している -- するどい相転移．

3.4 The correlation of the energy minima with the phase transition

  1. Figure 18 はエネルギーが最小値をとる patch size と相転移がおこる patch size との関係をしめす (50 landscapes についての実験結果) : K = 4 のときは相関がないが，K = 24 のときに相関は最強．
  2. Table 2 は両方の patch size が一致するわりあい (%)．
  3. 相関は greedy, random, fitter の順でたかくなる．
  4. 相関は K がおおきくなるほどたかくなる．
  5. 最適な patch size は通常秩序と無秩序 (chaos) の相転移点のちかくにある．

4. Discussion

結果のまとめ
  1. 上記の結果は，ある種のくみあわせ最適化問題において， 問題を利己的なふるまいをする patch に分割したほうが，しばしば よりよい解がもとまることをしめしている．
  2. 分割された patch が共進化的な問題解決をしている．
  3. 他の patch にかかわる制約を無視したほうが，わるい local minima をぬけだすのにやくだつ．
  4. 共進化的な問題解決は単純な問題解決にはやくだたないが，起伏のある landscape をもった (矛盾する制約をもった) 問題になるほどやくにたつ．
  5. ある程度矛盾する制約をもつ問題でも大域最適化でうまくいく (K = 4 のとき) が，その度合がおおきくなるとはるかにちいさな patch size が最適になる (K = 8 で 36 スピン，K = 24 で 400 スピン)．
  6. Patch size がちいさいときはカオティック，おおきなると秩序的にふるまう．
  7. 最適な patch size は通常秩序と無秩序 (chaos) の相転移点のちかくにある．
今後の課題など
  1. 格子以外の NK システムのときにどうなるかをしらべる．
  2. Patch がその要素や境界を利己的に変化させることによって， 全体のエネルギーが自発的に非常にひくい値をとる単純なアルゴリズムを みつける．
  3. 矛盾する制約をもった NK 以外のクラスの複雑な問題をしらべる [金田はすでにこれをやっている]．
  4. この理論は会社や政府などの社会的組織の分散化 (decentralization) の理論的基礎になる．

疑問点など

  1. 最適解との比較をしていない．
  2. Random, fitter, greedy dynamics のあいだの最小値の比較すらしていない． これらの最小値を比較すると fitter がもっともよい (最適値にちかい) -- それは fitter がもっとも locality がたかいことと関係がある ?
  3. 収束するまでの時間を問題にしていない -- 問題解決においては非常に重要． Locality がたかいほど時間はかかるはず (CCM での経験からすると)．
  4. 全体のエネルギーが部分のエネルギーの平均値 (または和) としてあらわされる状況をかんがえているが，くみあわせ最適化問題において これは十分一般的 (あるいは広範囲に応用可能) か ? [CCM にも共通する問題点]
  5. そもそもエネルギーの大域的最小化をするという問題設定は適切か ? 結局は大域最適化をめざしている -- 従来のわくぐみにとらわれている．
Y. Kanada (Send comments to kanada@trc.rwcp.or.jp)