爆走行動設計問題!!

爆走する車の行動を設計せよ!!
進化計算班：
津波古正輝＆當間啓介
要求仕様
• あるコースをスタートからゴールに最短で
到着するような車の動きを考えるよ.
GA設計
• コーディング
車の行動を木構造で表し、最下位のノードには終
端記号、それ以外は非終端記号を割り当てた。
• 適応度計算
データを与えると点数を返すシミュレータを用意した。
• 選択/交叉/突然変異
選択：ランク選択
交叉：一点交叉
突然変異：ある部分を消して部分木を作って置き換え
※単にノードが1つだけの場合もありうる
コーディング
木構造の繋がりのイメージ
非終端記号(11~16)
終端記号(1~10)
選択(ランク選択)
淘汰の確率
T1
個体
増殖の確率
Z1
点数高い
T2
個体
T3
個体
Z2
T4
個体
Z3
個体
Z4
・個体が点数の高い順番に配列に格納されている。
・その配列の中で、4つのランクに別れている。
低い
交叉、突然変異
交叉：
ランダムに選んだ二つの個体を一点交叉させる。
突然変異：
ランダムに選んだ個体中のある部分木を新しく作った
部分木に変える
シミュレータ
GA側
• GP側で作成した
プログラム(木)を
受け取り、点数を
返す関数
t e s t n u m b e r .c
を作成した。
t e s t n u m b e r .c
木
点数
シミュレータ側
0：GOの示す方向に前進する
1：GO=0に変更し、GOの示す方向に前進する
2：GO=1に変更し、GOの示す方向に前進する
3：GO=2に変更し、GOの示す方向に前進する
4：GO=3に変更し、GOの示す方向に前進する
5：GO=4に変更し、GOの示す方向に前進する
6：GO=5に変更し、GOの示す方向に前進する
7：GO=6に変更し、GOの示す方向に前進する
8：GO=7に変更し、GOの示す方向に前進する
9：GOを反転させ、前進する。その後、GO=-1にする
終端記号
10：とまる。GO=-1、V、Acceleを0にする
11：Vの値で分岐。Vが40より大きいか(Yes=0,No=1)
非終端記号
12：Vが最高スピードに近い(Yes=0,No=1)
13：どれくらい道が続いてるのか。GOの先の数字の計算。(0,1,2,3,4)
14:障害物はあるか。GOの示す先に0があるか調べる(Yes=0,No=1,わからない=2)
15：コース上に車は存在するか。 (Yes=0,No=1)
16：Hit(衝突回数)で分岐。(0,1,2,3,4,5,6,7)
設定可能
説明
・コース(二次元配列と数字)サイズ、タイプ
・車のスタート位置とゴール位置
・各パラメータの設定(スピード、時間、距離等の計算式)
GO
０１２
３車４
５ 6 7
コース
点数(評価)の付け方
・DataEdit.cのHyouka関数に記述
Hyouka=1000/Time-Hit*30+1000/S;
・変数の操作はAdvance.c内に記述
V=Vo+Accele*Time;
S=Vo+1/(2*Accele*Time*Time)+S;
Accele=(V*V-Vo*Vo)/(2*S);
※他多数のソースにあり
実行
• 実行方法
%make
%./GP
%plot.sh
%open gp.png
※./GPで作成されたデータを
画像として出力するのがplot.sh
以下のパラメータで実験
• DEPTH
• KOTAI
• KOUSA_K
木の深さ
作られる個体数
交叉確率
適応度高い
淘汰の確率
増殖の確率
• TOTSUZEN_K
• LOOP
4
50
50%
低い
T1(=10) T2 (=25) T3 (=50) T4 (=75)
Z1(=80) Z2 (=60) Z3 (=30) Z4 (=10)
突然変異確率
世代数
5%
500
適応度推移図
作成したプログラムを
テストデータで実施すると、
右図のようなグラフが
得られた.
シミュレータを用いた
データで実行すると…
NEXT PAGE
適応度推移図(実際のデータ)
• エリート選択にすると、結果が変わったか
もしれない。
• 淘汰、増殖などに使用した確率が妥当で
ないので、その確率を考える。
• シミュレータ側の改善

Download Report