Hatena::ブログ(Diary)

( ゜Д゜)..タイトル考え中 このページをアンテナに追加 RSSフィード

2008-06-11

PHPで人工知能

今日、会社で「マッチ箱の脳」という本を借りて読みました。

で、この人工知能の話がめちゃくちゃ面白いんですよ。もはや人工知能に夢中です。

WEBでも内容が読めるぽいですね。

マッチ箱の脳 web

http://www.1101.com/morikawa/index_AI.html

そこで

PHPでこの本の中に書いてある、人工知能を実装してみました。

まずは、

http://www.1101.com/morikawa/2001-04-22.html

http://www.1101.com/morikawa/Match/GaMatch.html

このページの内容です。マッチ箱で作るGAってのに挑戦してみました。

ga.php

<?php
main();


function main() {
  $geneticGroup = new GeneticGroup();
  $evaluator    = new Evaluator();
  $judgement    = new Judgement();

  // 初期化
  foreach (range(1, 10) as $val) {
    $genetic = new Genetic(Toolkit::make_rand_arr());
    $evaluator->evaluate($genetic);
    $geneticGroup->add($genetic);
  }
  while (! $judgement->judge($geneticGroup)) {
    // 淘汰
    $geneticGroup->remove();
    
    // 親の選択
    $childs = GAManager::cross($geneticGroup->genetics[0],
			       $geneticGroup->genetics[1]);
    // 交叉 
    foreach ($childs as $child) {
      // 突然変異
      GAManager::mutate($child);
      $evaluator->evaluate($child);
      $geneticGroup->add($child);
    }
  }
  echo "{$judgement->judgeCount}回の世代交代がなされました。\n";
}

  // 遺伝子グループクラス
class GeneticGroup
{
  public $genetics = array();

  // ポイントの高い順に並び替える
  public function sort() {
    for ($i=0; $i < count($this->genetics); $i++) {
      for ($j=$i+1; $j < count($this->genetics); $j++) {
	if ($this->genetics[$i]->point < $this->genetics[$j]->point) {
	  $tmp = $this->genetics[$j];
	  $this->genetics[$j] = $this->genetics[$i];
	  $this->genetics[$i] = $tmp;
	}
      }
    }
  }

  // 点数の低い二つを消去する
  public function remove() {
    $this->sort();
    array_pop($this->genetics);
    array_pop($this->genetics);
  }

  // グループに加える
  public function add($genetic) {
    $this->genetics[] = $genetic;
  }
  
  // maxのポイントを得る
  public function getMax() {
    $this->sort();
    return $this->genetics[0]->point;
  }
}

// 遺伝子クラス
class Genetic
{
  public $point;
  public $answer = array();

  public function __construct($answer) {
    $this->answer = $answer;
  }
  public function setPoint($point) {
    $this->point = $point;
  }
}

class GAManager
{
  // 交配する
  public static function cross($genetic1, $genetic2) {
    $answer1 = array();
    $answer2 = array();
    $dice = self::dice();
    for($i=0; $i < count($genetic1->answer); $i++) {
      if ($i >= $dice-1) {
	$answer1[] = $genetic2->answer[$i];
	$answer2[] = $genetic1->answer[$i];
      } else {
	$answer1[] = $genetic1->answer[$i];
	$answer2[] = $genetic2->answer[$i];
      }
    }
    return array(new Genetic($answer1), new Genetic($answer2));
  }

  // 突然変異
  public static function mutate($genetic) {
    $dice = self::dice();
    if ($dice == 12) {
      return;
    }
    $key = $dice%11 + floor($dice/11) - 1;
    $genetic->answer[$key] = $genetic->answer[$key]%3 + 1;
  }

  // サイコロを二つふって足した目を返す
  private static function dice() {
    return rand(1, 6) + rand(1, 6);
  }
}

// 評価者クラス
class Evaluator
{
  private $answer = array();

  public function __construct() {
    $this->answer = array(3, 1, 2, 2, 2, 3, 1, 3, 3, 1);
  }

  // genetic にポイントを付ける
  public function evaluate($genetic) {
    $point = 0;
    foreach ($this->answer as $k => $v) {
      if ($genetic->answer[$k] == $v) {
	$point += 10;
      }
    }

    $genetic->setPoint($point);
  }
}

// 遺伝終了判断クラス
class Judgement
{
  public $judgeCount;
  public $maxPoint;
  public function __construct() {
    $this->maxPoint = 100;
  }

  public function judge($geneticGroups) {
    ++$this->judgeCount;
    if ($geneticGroups->getMax() == $this->maxPoint) {
      return true;
    } else {
      return false;
    }
  }
}

class Toolkit
{
  // ランダムな答えを作成する
  public static function make_rand_arr() {
    $rand = array();
    for ($i = 0; $i < 10; $i++) {
      $rand[$i] = rand(1, 3);
    }
    return $rand;
  }
}

こんな感じになりました。しかし5回に1回くらいプログラムが止りません。

でも終わる時は、大体十何回とか三十何回とかの世代交代で終了します。


以下考察なのですが、プログラムが止まらない時ってのは、

親になる遺伝子の答えが全く同じで、得点が90点の時なんですよね。


で、遺伝子の同じ親からは、親と同じ子供しか生まれない。

さらに、突然変異は答えに単純に1を足してるだけなので、

もし本当の答えとの差が2あったら、一生世代交代が終わらない。

とか、そんなことが原因かなーって思っています。


遺伝子が同じだったら親になっちゃだめ、っていうルールを付ければ解決できるのかな。

というか、文章上手くまとまんないなー。。。自分の以外な才能に驚きです。

まとめ

人工知能、かなりきてますね。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/HaSUmi/20080611/1213142678