ITエンジニア勉強ブログ

自分が学んだことを共有していきます。

シェリングの分居モデルのJavaScript実装

シェリングの分居モデルをJavaScriptで実装しました。


ランダムに配置されたエージェント達が初めは移動を繰り返していますが、だんだんと同種のエージェント同士でカタマリを作って定住するようになっていきます。
だいたい数十秒で収束しますので、しばらく見守ってあげてください。


See the Pen
Untitled
by Imai (@imai1)
on CodePen.

このモデルの面白いところは、非常に簡単なルールのエージェントしか実装していないのに、上記のような挙動になることです。初めて知ったという方は以下の解説もご覧いただけたら嬉しいです。

モデルについて

モデルの定義

モデルの定義は非常にシンプルです。

  • 碁盤状のマップを用意して、各マスにランダムにエージェントを配置する。
  • 一定時間ごとに以下を繰り返す。
    • 各マスのエージェントごとに、隣接する8マスの[同種のエージェント数/全エージェント数]を計算し、閾値未満なら隣接する空きマスにランダムに移動させる。

たったこれだけで、冒頭のように分居するエージェント達のシミュレーションが作れてしまいます。

モデルの解説

このモデルは、日本人街や中華街など、異人種が集団で固まって居住する現象を説明する理論として、1970年代に経済学者シェリングが考えたものとのことです。

引越しの閾値は別種のエージェントの不許容度合いを表しています。

もし閾値が1.0だとしたら、どうなるでしょうか?すなわち、隣接する領域に別種のエージェントがいる場合に必ず引っ越す場合にはどうなるでしょうか。

直観的には高速に分拠が進むようにも思えますが、実際には各エージェントはバラバラに移動し続け収束しません。冒頭のCodePenでテキストボックスの閾値に1.0を入力して確かめてみてください。リセットボタンをつけていませんが途中から閾値を変えても結果は大差ありません。

一方、マップのサイズにもよりますが、閾値を下げていって0.3くらいでも十分に分居が生じます。

現実には短時間に連続して引越しできないとか、隣接領域に移動するのではなく良さそうな居住区に飛び地で移動するなどの違いはありますが、分拠は別種のエージェントに対する不許容の結果として生じるのではなく、むしろある程度の許容によって生じる(かもしれない)という可能性を示したのがこのモデルの面白いところです。

なお、シェリングは後にノーベル経済学賞を受賞する方ですが、まだコンピュータが一般に普及していない時代に、手計算でこのシミュレーションを行ったらしいです。

実装について

分居モデルのクラス

全コードはCodePenの方をご覧いただくとして、主要な部分を抜粋しました。

class SegregationModel {
  constructor(width, height) {
    this.width = width;
    this.height = height;
    this.map = new Array(this.height);
    for (let y = 0; y < this.height; ++y) {
      this.map[y] = new Array(this.width);
    }
  }
  initializeMap(probabilityDistribution) {
    // エージェントの分布を初期化する。
  }
  countFraction(x, y) {
    // (x, y)の隣接領域の同種エージェント割合を数える。
  }
  move(x, y) {
    // (x, y)のエージェントを隣接する空き領域にランダムに移動させる。
  }
  update(threshold) {
    // 1世代更新する

    // 充足していないエージェントの探索
    const movers = new Array();
    for (let y = 0; y < this.height; ++y) {
      for (let x = 0; x < this.width; ++x) {
        if (this.map[y][x] == undefined) {
          continue;
        }
        if (this.countFraction(x, y) < threshold) {
          movers.push([x, y]);
        }
      }
    }

    // 引越し
    // for文の順序の早い方に固まる傾向があるため、引っ越し順はシャッフルする
    for (const [x, y] of shuffle(movers)) {
      this.move(x, y);
    }
  }
}

SegregationModel.mapが各マスの状態です。エージェントの種類のIDか、空欄の場合はundefinedです。

update関数が、1世代分の引越しの更新処理です。for文の順に引越しをしていくと特定の方向に移動が固まる(例えばfor (y=0; y < height; y++) for (x=0; x < width; x++)だと、マップの左上にエージェントが集まっていく)傾向が確認できたので、1世代のmove関数の実行をランダムな順にする一手間が加えられていますが、本質的には前述の解説の擬似コードそのものかと思います。

canvasへの描画の関数

SegregationModelのある時点の状態の描画は、以下のdrawModelToCanvas関数にまとめました。

const imgs = new Array();
for (let i = 0; i < 2; i++) {
  imgs.push(new Image());
}

imgs[0].src = "省略";
imgs[1].src = "省略";

function drawModelToCanvas(model, canvasId, cellWidth, cellHeight) {
  const canvas = document.getElementById(canvasId);
  const context = canvas.getContext("2d");

  context.clearRect(0, 0, canvas.width, canvas.height);

  for (let y = 0; y < model.height; ++y) {
    for (let x = 0; x < model.width; ++x) {
      const person = model.map[y][x];
      if (person != undefined) {
        const img = imgs[person];
        const dx = x * cellWidth;
        const dy = y * cellHeight;
        const [width, height] = 
              (img.naturalHeight < img.naturalWidth) ?
              [cellWidth, img.height * cellWidth / img.width] :
              [img.width * cellHeight / img.height, cellHeight];
        context.drawImage(img, dx, dy, width, height);
      }
    }
  }
}

やっていることは簡単で、SegregationModel.mapの種類IDに従って、エージェントの画像を適切なサイズに縮小しながら碁盤状に貼り付けているだけです。

なお、本来はimgs.src[0] = "..."の部分でImageオブジェクトの初期化完了を待つための非同期処理が必要です。初期化完了前にdrawModelToCanvasを実行しても、何も描画されないこと以外の問題はなかったため、本コードでは気にしないことにしました。

エージェントの画像はいらすとやさんからお借りしました。言及しても危なくない対立が良いかなと思って、体育会系と理系の画像にしました。が、大きめのマップにするとコントラスト的に見難かったので反省です。

アニメーション

一定時間毎のアニメーションは次のように実装しました。

function update() {
  const inputThreshold = document.getElementById(thresholdInputId);
  const threshold = inputThreshold.value;
  model.update(threshold);
  drawModelToCanvas(model, canvasId, cellWidth, cellHeight);
}

setInterval(update, 500);

一定時間毎の処理を一つの関数にまとめて、setIntervalで呼び出すだけです。一定時間毎の処理は、閾値の取得、モデルの更新、再描画、の三つだけです。