遺伝的アルゴリズムを活用した自動車の進化過程を観察
(rednuht.org)- ランダムに生成された二輪形状が世代を重ねるごとに、より遠くまで走る自動車として選択・変異されていく過程をブラウザで見られるHTML5シミュレーション
- BoxCar2Dのアイデアを緩やかに踏襲しているが、コードは新たに書き直されており、物理計算にはbox2dを使用
- 突然変異率、突然変異の大きさ、地面の条件、重力、エリートクローン数を調整して進化条件を変えられる
- 同じseedで同じトラックを作れるため結果を比較しやすいが、シミュレーション自体は完全に決定的ではない
- ゲノムには車体と車輪の形状・位置・密度が含まれ、遠くへ進むほど地形が複雑になるため、単純な最高記録だけでは安定性を保証しにくい
自動車が進化する仕組み
- プログラムはランダムな二輪形状を世代ごとに進化させ、自動車のように走る個体を生み出すシンプルな遺伝的アルゴリズムシミュレーション
- BoxCar2Dから緩やかに着想を得ているが、コードは一から書かれている
- 物理エンジンにはbox2dを使用
- seedrandom.jsはDavid Bauが作成
操作と進化設定
- 保存と復元機能により、実験状態を引き継げる
- Save Populationは現在の個体群をローカルに保存
- Restore Saved Populationは以前に保存した個体群を復元
- シミュレーションの進め方も直接変更できる
- Supriseは描画を切り替えてシミュレーションを高速化
- New Populationは生成されたトラックを維持したまま、自動車の個体群全体を再開始
- View top replayは現在のシミュレーションを一時停止して最高性能の自動車を表示し、もう一度クリックするとシミュレーションを再開
- Create new world with seedは、同じseedなら常に同じトラックを作るため、他の人と同じseedで競える
- 進化パラメータは新しい世代がどれほど大きく変化するかを左右する
- Mutation rateは新世代が生まれる際、各個体の各遺伝子がランダムな値に変異する確率
- Mutation sizeは各遺伝子が変異できる範囲で、低い値ほど元の値に近い値になる
- Elite clonesは次世代へそのままコピーされる上位n台の自動車数を決める
グラフで見る性能変化
- グラフの色は世代ごとの性能を異なる基準で示す
- 赤色は各世代の最高スコアを示す
- 緑色は各世代の上位10台の自動車の平均を示す
- 青色は全世代の平均を示す
ゲノムが表す自動車の構造
- 自動車のゲノムは車体と車輪を構成する複数の遺伝子に分かれる
- Shape: 頂点ごとに1個、合計8個の遺伝子
- Wheel size: 車輪ごとに1個、合計2個の遺伝子
- Wheel position: 車輪ごとに1個、合計2個の遺伝子
- Wheel density: 車輪ごとに1個、合計2個の遺伝子で、より暗い車輪はより高い密度を意味する
- Chassis density: 1個の遺伝子で、より暗い車体はより高い密度を意味する
制限事項とコード公開
- シミュレーションは期待するほど決定的ではなく、最良の自動車が以前と同じ性能を出せないことがある
- 地形は距離が伸びるほど複雑になる
- スクリプトの読み込み確認を別途処理していないため、動作がおかしければページを再読み込みする必要がある
- コードはGitHub repositoryで公開されており、コントリビューションを受け付けている
- 元はrednuht.orgで作成され、その後GitHubのコントリビューターたちが参加した
1件のコメント
Hacker Newsのコメント
これを最初に作ったのはもうほぼ20年前ですが、今でもたまにここに上がってくるのを見るとうれしいですね
Ruffleのおかげで、まだブラウザ上で動きます:
https://peteshadbolt.co.uk/posts/ga/
サイトは本当にすばらしいです。上がってくるたびに、つい長い時間見入ってしまいます
友人と昼休みの間に実行したままにして、戻ってきてどちらが勝ったかを見る、ということをしていました
いつも、ある設計が運よく成功したあと世代ごとに支配的になり、その後の突然変異はちゃんと機能するレベルに近づくことすらできない行き止まりにはまるように見えます
数百世代経っても上位10個が変わらない、という感じです。遺伝的アルゴリズムの性質なのかもしれません。かなり良い解を素早く見つけたあと局所最大値に捕まる、ということかもしれないし、突然変異率や突然変異の大きさの設定をもっと調整する必要があるのかもしれません
高い突然変異率は局所最適解に早く到達しますが抜け出しにくく、低い突然変異率ははるかに多くの世代を必要とするものの、たいていはより良い適応につながります
遺伝的ヒューリスティックでは、まさにそういう現象が起きるため、非常に悪い方法です
ただ現状では動力と速度は変わらず、数世代経つと形だけがごく少し変わるように見えます。下のほうを見るとゲノムの説明がありますね: 形状8遺伝子、車輪サイズ2、車輪位置2、車輪密度2、車体密度1です。結局、2つの車輪と中程度の車体形状に収束し、その後は大きな進展がないように見えます。動力と速度も変異要素に入れると面白そうです
面白いです。ただ、速度調整はあまり直感的ではありませんね。「Surprise」を押すと速くなり、複数の反復をすばやく進められます
突然変異率、つまりgが変わる可能性と、突然変異の大きさΔgは、個体群が時間とともに進化するのを見ながらいじるのに向いたハイパーパラメータです。車に一種のサスペンションが生まれるような「compliance」遺伝子があると面白そうです。私が試したほとんどの実行では、ほぼすべてがTronのバイクのような形に進化しました
大きな車輪に小さな車輪が付いた形で、ぴょんぴょん跳ねながらすべての障害物を越えていきます
過去の議論です:
https://news.ycombinator.com/item?id=5942757 (664 points | Jun 2013 | 169 comments)
https://news.ycombinator.com/item?id=10600486 (162 points | Nov 2015 | 57 comments)
Flashなしのboxcar2dですね
https://news.ycombinator.com/item?id=2196747
物理シミュレーションは明らかに非弾性衝突を使っているようで、これはかなり非現実的です。そのため、見た目には十分よさそうな多くの車がコースを通過できません。摩擦係数も非常に低く見えます。私が作った車のほとんどは、2区間の坂道すら登れませんでした
https://web.archive.org/web/20240428203838/http://boxcar2d.c...
小さなバグがあります。約280m以降は道路がなく、すべての車が果てしない穴に落ちていきます
「ランダムな二輪の形態を何世代にもわたって車へ進化させる」とありますが、私の住んでいるところでは二輪自動車をオートバイと呼びます
それでもシミュレーションはとてもクールです！
そのため、従来の四輪車のように、速度が0でも倒れません。その性質だけでも、オートバイより四輪車に近い挙動だと言えると思います
とても視覚的で楽しい可視化なので気に入っています
これを見て、「Self-parking car evolution」で遺伝的アルゴリズムを試してみるようになりました:
https://trekhleb.dev/self-parking-car-evolution/
Cell LabというすばらしいAndroidアプリを思い出します。ペトリ皿の中で生きる多細胞または単細胞生物を作れました
望むなら放射線レベルを上げて、突然変異と進化が起きるようにもできました
こういうものが好きなら、https://old.reddit.com/r/WatchMachinesLearn/に来てみてください