- 飛行中
- 目標に到達
- 墜落
- 前の世代のベスト飛行
- 目標に到達
- 墜落
遺伝的アルゴリズム・プレイグラウンド
遺伝的アルゴリズムは、進化が生き物を形づくるのと同じやり方で問題を解きます。ランダムな答えをたくさん試し、良いものを残し、それらを混ぜ合わせ、いくつかの部分をランダムに変え、これを繰り返すのです。ここでは答えはロケットです。各ロケットはランダムな推力の並びに従うだけで、ほかには何もしないので、最初はあてもなく転げ回ります。「実行」を押すと、集団が世代を追うごとに上達し、やがてほとんどのロケットが壁を回り込んで目標に届くようになる様子が見られます。どこへ行けばよいかは誰も教えていません。 「実行」を押すと、ロケットの集団が緑の目標にたどり着こうとする様子が見られます。各ロケットは自分の遺伝子だけに従って飛びます。遺伝子とは小さな推力の並びで、飛行中の各瞬間に1つずつ対応しています。飛行が終わるたびに、目標に最も近づいたロケット、とりわけ到達したロケットほど、次の世代の親になりやすくなります。親の遺伝子は混ぜ合わされ、そのうちいくつかはランダムに変えられます。「次の世代」を押すと、飛行の残りを飛ばします。フィールド上をドラッグすると壁を描け、壁をクリックすると消せます。
使い方
- 障害物を選ぶか、フィールド上をドラッグして自分で壁を描き、個体数、突然変異率、寿命を設定します。
- 「実行」を押して各世代の飛行を見ます。「次の世代」を押すと飛行の残りを飛ばせます。
- 目標に到達した割合をタイルとグラフで追い、ほかの突然変異率や選択方式も試してみましょう。
ロケットはどのように進化するか
どのロケットも遺伝子を持っています。飛行中の各瞬間に対する小さな推力が1つずつです。第1世代の遺伝子はランダムです。飛行が終わると各ロケットに適応度スコアが付きます。早く到着するほど高く、次に、最後に目標に近いほど高くなり、墜落すると10で割られます。次の世代の親はランダムに選ばれますが、適応度の高いロケットほど選ばれやすくなります。子はそれぞれ遺伝子の前の部分を一方の親から、残りをもう一方の親から受け継ぎ、いくつかの遺伝子はランダムな推力に置き換えられます。これが突然変異です。世代を重ねるうちに、良い飛行計画が広まり、さらに改良されていきます。
設定で何が変わるか
個体数が多いほど一度に多くの飛行計画を探れ、行き詰まりにくくなりますが、1世代にかかる時間は長くなります。突然変異率は、探索することとうまくいくものを残すことのバランスを決めます。突然変異がなければ集団はすぐに新しいアイデアを使い果たし、多すぎると良い飛行を見つけるより速く忘れてしまいます。ルーレット選択は適応度に比例して親を選び、トーナメントはランダムに選んだ3機のうち最良の1機を選びます。トーナメントは適応度の尺度の取り方にあまり左右されません。エリート保存は最良のロケットをそのまま次の世代へコピーするので、最良の結果が悪くなることはありません。
よくある質問
なぜロケットは互い違いの壁の後ろで行き詰まるのですか?
適応度は目標までの直線距離を測っているため、目標の下の壁に突っ込むロケットのほうが、すき間を探して遠ざかるロケットよりも高いスコアを得てしまいます。そのため集団はその袋小路に集まります。これが局所最適解です。個体数を増やす、突然変異を増やす、トーナメント選択を使うと抜け出しやすくなります。また、壁を回り込む実際の経路を測る適応度なら、この罠を避けられます。良い適応度関数を選ぶことは、遺伝的アルゴリズムを使ううえで最も難しい部分です。
自然界の進化もこのように働くのですか?
大筋ではそうです。突然変異と組み換えによる変異、遺伝子の遺伝、最も適応したものの選択は、ダーウィンの理論の要素です。ただし違いも大きいのです。自然には目標も適応度の式もなく、あるのは生存と繁殖だけです。また、実際のゲノムは行動を列挙するのではなく、発生を通じて体を形づくります。
遺伝的アルゴリズムは何に使われていますか?
考えられる答えの空間が膨大で、候補の評価が簡単な問題に使われます。アンテナや翼、自動車部品の形状設計、時間割の作成、ほかのアルゴリズムの設定の調整、ニューラルネットワークの設計、アートやゲーム戦略の創作などです。2006年のST5衛星に搭載されたNASAの進化したアンテナは有名な例です。
なぜ最良のロケットが次の世代で下手に飛ぶことがあるのですか?
エリート保存がなければ、最良のロケットはコピーされません。その遺伝子はほかの遺伝子と混ざり、場合によっては突然変異した形でしか残らないため、次の世代ではまったく同じ飛行が失われることがあります。エリート保存をオンにすると、最良のロケットがそのまま残され、最良の結果が悪くなることはありません。
サーバーに何か送信されますか?
いいえ。ロケットはお使いのブラウザの中で飛び、進化します。描いた壁はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ