2018年9月
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30            

Amazonウィジェット

  • お気に入り
  • 欲しいもの
  • 面白かった本
  • Raspberry Pi
  • ドローン
  • 書籍ランキング

AdSense

  • 広告
無料ブログはココログ

« 遺伝的アルゴリズムで育てる「お掃除ロボット」 その9 ~選定と交叉の実装~ | トップページ | コラム:連載の落穂拾い。 pdcursesはprintfと両立できない。 »

2018年4月25日 (水)

遺伝的アルゴリズムで育てる「お掃除ロボット」 その10 ~交叉アルゴリズムの改良~

前回までmainべた書きで書いていたところを、
下記のように書き換えた。
以降kousaの中身だけを書き換えることで、アルゴリズムを変更できるようにした。

  //選定
  //ランキング式で選定
  qsort(inds, INDIV_LEN, sizeof(inds[0]), sorter);

  //best record
  if (bestInd.score < inds[0].score) {
   bestInd = inds[0];
  }

  //交叉
  //上位半分をベストと掛け合わせ、バッファ下半分に書き込む。
  //バッファ上半分はペアを作って掛け合わせる。
  //int KOUSA_NUM = 1;
  int kousa_lim = INDIV_LEN / 2; //境界を計算
  for (int i = 0; i < kousa_lim; i++) {
   indiv_t work0 = inds[i];
   indiv_t work1 = bestInd;
   kousa(&work0, &work1);
   inds[i + kousa_lim] = work0;
  }
  
  for (int i = 0; i < kousa_lim; i+=2) {
   kousa(&inds[i], &inds[i+1]);
  }

前回のkousa関数は2点交叉だけを実装したものだったが、 今回は突然変異のコードを入れてみた。 遺伝子を交叉させたあとに、1/2の確率で遺伝子のいずれか一個に変異を起こすようになる。


getStartEnd(int *start, int *end) {
	int a = rand() % GEN_LEN; //0<= a < GEN_LENをとり得る。
	int b = rand() % GEN_LEN + 1; //+1はfor文の終了値のため。
	if (a > b) {
		*end = a;
		*start = b;
	}
	else if (a == b) {
		*end = GEN_LEN - 1;
		*start = GEN_LEN / 2;
	}
	else {
		*end = b;
		*start = a;
	}
}

void kousa(indiv_t *ind_a, indiv_t *ind_b) {

	//二点交叉を使う
	int start, end;
	getStartEnd(&start, &end);
	//printf("start,end = %2d,%2d\n", start, end);

	gen_t temp_a;
	gen_t temp_b;

	for (int i = start; i < end; i++) {
		temp_a = ind_a->gen_set.gen[i];
		temp_b = ind_b->gen_set.gen[i];

		ind_b->gen_set.gen[i] = temp_a;
		ind_a->gen_set.gen[i] = temp_b;
	}

	//突然変異を入れる。
	totsuzen(ind_a);
	totsuzen(ind_b);
}

void totsuzen(indiv_t *ind) {
	int sw = rand() % 2;//変異を起こすかどうかを決めるスイッチ
	int idx = rand() % GEN_LEN; //どのgenを変異させるか

	if (sw) {
		saikoro(&ind->gen_set.gen[idx]);
	}
}

成長をプロットしてみた。 前回とは少しプロットの仕方を変えてみた。

101_

今までの分はベスト遺伝子のスコアのみを世代毎にプロットしていたが、 今回は1世代分のソート済みの各遺伝子のスコアを全部載せてある。 塊1個分が1世代分に当たる。 赤い枠で囲った部分の左端の点がその世代の中でのベストスコアで、 右に行くほど順位が下がっていく。 これによってスコアのばらつき具合が見える。スコアのばらつきが小さいということは、 遺伝子ごとの個性が揃っていて、行動パターンが似通っているということ。 早く成長させるには、個性ができるだけばらついた状態で試行を繰り返すのが効果的であると推測した。

前回よりは劇的によくなったのだが、まだまだ世代毎のばらつきが小さく、 前世代のベストの個体によく似た個体が繰り返し生成されているような印象だった。 もう少しばらつかせる方法を追加しなければならない。 そこで、変異関数で起こす変異の種類を増やしてみた。 適当に区間を選んで、その区間は全く新しい要素を入れ込むだけ。 変異は、何もしない・一個だけ変異・区間で変異。の3種類とした。


void totsuzen(indiv_t *ind) {
	int sw = rand() % 3;//どの変異を起こすかを決めるスイッチ
	int idx;
	int start, end;

	switch (sw) {
	case 0:
		break; //何もしない。
	case 1:
		idx = rand() % GEN_LEN; //どのgenを変異させるか
		saikoro(&ind->gen_set.gen[idx]);
		break;
	case 2:
		getStartEnd(&start, &end);
		for (int i = start; i < end; i++) {
			saikoro(&ind->gen_set.gen[i]);
		}
		break;
	default:
		break;
	}
}

再度プロットを実行。 グラフを見ると、世代毎のスコアのばらつき具合が広くなった。 12世代目までスコア80%を超えることがなかったのだが、今回は5世代目には90%を超えるようになり成長は早くなった。

102_

同じ遺伝子を掛け合わせに使っても、突然変異を導入したことですぐに飽和しないようになった。 ※突然変異の確率が高すぎて、もはや突然でもなんでもなくなってしまったが。。。 そして、時たま100%掃除できる遺伝子が出てくるようになった。 試しに走らせてみた時の動画を公開。 公開用として、試行中の個体のスコアをメーターで表示するようにした。 あとは文字の色をcursesを使っていろいろ触ってみた。 <<注意>>試しに音楽も入れてみたので、ボリュームに気をつけてください。

ようやく

« 遺伝的アルゴリズムで育てる「お掃除ロボット」 その9 ~選定と交叉の実装~ | トップページ | コラム:連載の落穂拾い。 pdcursesはprintfと両立できない。 »

C言語」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/518723/66485330

この記事へのトラックバック一覧です: 遺伝的アルゴリズムで育てる「お掃除ロボット」 その10 ~交叉アルゴリズムの改良~:

« 遺伝的アルゴリズムで育てる「お掃除ロボット」 その9 ~選定と交叉の実装~ | トップページ | コラム:連載の落穂拾い。 pdcursesはprintfと両立できない。 »