2018年5月
    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 31    

Amazonウィジェット

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

AdSense

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

« 遺伝的アルゴリズムで育てる「お掃除ロボット」 その8 ~ちょっと修正~ | トップページ | 遺伝的アルゴリズムで育てる「お掃除ロボット」 その10 ~交叉アルゴリズムの改良~ »

2018年4月18日 (水)

遺伝的アルゴリズムで育てる「お掃除ロボット」 その9 ~選定と交叉の実装~

第一世代の遺伝子群はINDIV_LEN個の遺伝子を乱数で生成する。
生成した各遺伝子(行動パターン)をロボットに書き込んで、シミュレーション環境を走行させ、
マップ中のゴミの数に対して、いくつのゴミを拾ったかをスコアとして記録する。
スコアはパーセンテージで出てくるようにした。スコアが1になればパーフェクト。

一世代分のシミュレーションが完了したら、
qsortを使って遺伝子をスコア順にソートする。毎世代につきベストな遺伝子だけをbestIndに記録する。

第一世代以降は、ソートの結果上位半分をbestIndと交叉させ、
下位半分は新たに乱数で生成することにした。

交叉のやり方はwikipediaにいろいろ載っているのだが、
二点交叉という手法を使うことにした。これをひとまとめに関数として実装した。
※遺伝子の中で適当な区間(開始~終了)を決め、その区間をペア間で入れ替えるやり方。

mainにべた書きでとりあえず試してみた。

void main(void) {
	assert(INDIV_LEN % 4 == 0);

	//ロボットの初期の向き
	point_t ini_d = { 1,0 };

	//乱数セット
	srand(time(NULL));
	
	indiv_t inds[INDIV_LEN];

	for (indNumber = 0; indNumber < INDIV_LEN; indNumber++) {
		makeIndiv(&inds[indNumber].gen_set);
	}

	//世代分だけループを回す。
	static indiv_t bestInd;
	for (generation = 0; generation < EXEC_LEN; generation++) {

		//robotの数だけ試行
		for (indNumber = 0; indNumber < INDIV_LEN; indNumber++) {
			indiv_t *ind = &inds[indNumber];
			initRobot(ind, &ini_d);
			
			//マップを書き込み
			readMap();

			//初期位置にRobotをセット
			setRobotOnMap(ind);

			draw(ind);

			do {
				execRobot(ind);
				draw(ind);
				Sleep(15);

			} while (ind->life > 0);
		}

		//選定
		//ランキング式で選定
		qsort(inds, INDIV_LEN, sizeof(inds[0]), sorter);
    	
    	//best record
	  	if (bestGen.score < inds[0].score) {
	   		bestGen = inds[0];
	  	}
	  	
		//2点交叉
		int KOUSA_NUM = 10;
		int kousa_lim = 2 * KOUSA_NUM;
		for (int i = 0; i < kousa_lim; i+=2) {
			kousa(&inds[i], &inds[i+1]);
		}
		
		//残り半分は新しく生成する。
		for (int i = kousa_lim; i < INDIV_LEN; i++) {
			makeIndiv(&inds[i].gen_set);
		}
	}

	draw_result(&bestInd);
}

ベストスコアを世代毎にプロットして、成長率の遷移を見た。

 91_

世代が上がる毎にスコアが上がると思いきや、世代間に関連性がなくすべて当てずっぽうにやっているのと変わらなかった。 遺伝子の中身を見てみると、どうやら遺伝子がbestIndの内容に収束していっているようだ。 似たもの同士でしか掛け合わせができなくなれば、遺伝的アルゴリズムのメリットはうすい。 一方、 ロボットの動きを見ていると、遺伝子一個当たりの移動距離が長くなると、 なんとなく良い行動パターンが出にくいような気がした。 そこで試しに、遺伝子一個に設定する最大移動距離MAX_MOVLENを5→3に短くしてみた。

92_

同じプロットを試してみると、やはり成績が良くなる傾向になり、 スコアが100%になる回数が多くなった。 ただしこの条件は、このマップにしか当てはまらないかもしれないので偶然かもしれない。 どちらにしても、もう少し交叉のやり方を工夫しなければならない。 突然変異の実装はまだなので、次回はそれを試すことにした。 続く。

« 遺伝的アルゴリズムで育てる「お掃除ロボット」 その8 ~ちょっと修正~ | トップページ | 遺伝的アルゴリズムで育てる「お掃除ロボット」 その10 ~交叉アルゴリズムの改良~ »

C言語」カテゴリの記事

コメント

コメントを書く

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

トラックバック

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

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

« 遺伝的アルゴリズムで育てる「お掃除ロボット」 その8 ~ちょっと修正~ | トップページ | 遺伝的アルゴリズムで育てる「お掃除ロボット」 その10 ~交叉アルゴリズムの改良~ »