遺伝的アルゴリズムの解説
進化は、うまくいくものを残してそれに変化を加えるだけで、設計者なしに目や翼や脳を生み出してきました。遺伝的アルゴリズムはこの考え方を借りて、コンピュータで問題を解きます。問題そのものを理解する必要はなく、良い答えと悪い答えを見分けられさえすればよいのです。そのため、考えられる答えの空間が大きすぎ、また複雑すぎてほかの方法では探索できないときに、強力な道具になります。
基本的な考え方
1960年代から1970年代にかけて、ミシガン大学のジョン・ホランド(John Holland)はダーウィンの理論をアルゴリズムに変え、1975年の著書『自然・人工システムにおける適応』(Adaptation in Natural and Artificial Systems)で説明しました。同じころドイツでは、インゴ・レッヒェンベルク(Ingo Rechenberg)とハンス=パウル・シュヴェフェル(Hans-Paul Schwefel)が工学設計のための進化戦略を開発しました。共通する手順は、解の候補の集団を保ち、それらを評価し、良いものに変化を伴って子を残させ、これを何世代も繰り返すというものです。
遺伝子と集団
各候補は染色体、つまり遺伝子の並びで表されます。プレイグラウンドでは、ロケットの遺伝子はその推力で、飛行中の各瞬間に1つずつ対応します。ほかの問題では、遺伝子は数のビットであったり、経路上の都市の順番であったり、設計における部品の寸法であったりします。第1世代はランダムなので、答えの空間を広く探索しますが、良い答えはほとんど含まれていません。
適応度関数
適応度は、候補がどれだけ良いかを表すただ1つの数値であり、アルゴリズムが問題について知っている唯一のものです。ロケットの場合、早く到着することを最も高く評価し、次に目標の近くで終わることを評価し、墜落には罰を与えます。よく選ばれた適応度関数は探索を滑らかに良い答えへと導きますが、不注意に作られた適応度関数は誤ったものに報酬を与え、アルゴリズムはそこに残された抜け穴をどれでも突いてきます。
選択
親は、適応度の高い候補ほど多くの子を残せるように選ばれますが、弱い候補にもチャンスは残されます。その遺伝子に役立つ部分が含まれているかもしれないからです。ルーレット選択は、各候補に適応度に比例した大きさのルーレットの区画を割り当てます。トーナメント選択はいくつかの候補をランダムに選び、その中で最良のものを取ります。選択を強くすると進歩は速まりますが、集団が似通ってしまい、探索が早すぎる段階で終わることがあります。
交叉と突然変異
交叉は2つの親を組み合わせます。ここでは、子は遺伝子の前の部分を一方の親から、残りをもう一方の親から受け継ぐので、あるロケットの序盤の動きと別のロケットの終盤の動きが組み合わさることがあります。突然変異はいくつかの遺伝子をランダムに置き換えます。交叉は集団がすでに持っているものを組み換え、突然変異は集団がこれまで持っていなかったものをもたらします。ホランドのスキーマ定理は、選択と組み換えのこの組み合わせのもとで、良い遺伝子からなる短い構成要素が集団の中にどのように広がるかを説明しています。
エリート保存、探索と活用
最良の候補をいくつか、そのまま次の世代へコピーすること、つまりエリート保存によって、最良の答えが失われないことが保証されます。どの遺伝的アルゴリズムも、探索空間の新しい領域を試す「探索」と、すでに良いものを磨く「活用」のバランスを取らなければなりません。変化が少なすぎると集団は1つの平凡な答えに収束し、多すぎるといつまでも落ち着きません。個体数、突然変異率、選択圧が、このバランスを決めるつまみです。
局所最適解
遺伝的アルゴリズムは適応度に従うだけなので、だまされることがあります。最良の答えへの道筋がまずより悪い答えを通る場合、集団は最も近い丘に登ってそこにとどまってしまいます。これが局所最適解です。プレイグラウンドの互い違いの壁の後ろでは、目標の下で墜落するロケットのほうが、向きを変えてすき間を探すロケットよりもスコアが高くなるため、集団は壁に押し寄せます。対策としては、個体数を増やす、突然変異率を上げる、集団の多様性を保つ、そして何よりも、より良い適応度関数を使うことが挙げられます。
試してみましょう
遺伝的アルゴリズム・プレイグラウンドを開いて、壁1枚、すき間、柱、互い違いの壁、あるいは自分で描いた壁を回り込むようにロケットを進化させてみましょう。個体数、突然変異率、寿命、選択方式を変え、エリート保存をオン・オフし、目標に到達するロケットの割合がどれだけ速く増えるか、あるいはなぜ増えないのかをグラフで追ってみてください。
よくある質問
遺伝的アルゴリズムは人工知能の一種ですか?
探索と最適化の手法として、AIと機械学習という広い分野に属します。ニューラルネットワークのように例から学ぶのではなく、試行と選択によって解の候補を改良します。両者はよく組み合わされます。たとえば、ニューラルネットワークの構造や重みを進化させる手法があり、これはニューロエボリューションと呼ばれます。
遺伝的アルゴリズムは必ず最良の答えを見つけますか?
いいえ。遺伝的アルゴリズムはヒューリスティックです。難しい問題に対してたいてい良い答えを見つけますが、最良の答えであるという保証はなく、それがどれだけ最良に近いかの証明もありません。厳密な方法が十分に速い問題では、その方法のほうが優れています。
遺伝的アルゴリズムと進化戦略の違いは何ですか?
どちらも進化的アルゴリズムです。古典的な遺伝的アルゴリズムは、文字列のような染色体に対する交叉を重視します。進化戦略は主に実数に対する突然変異を用い、多くの場合、進行に合わせて突然変異の大きさを自ら調整します。現代の手法は両方の考え方を取り入れています。
なぜ最初のロケットはあんなに不器用なのですか?
最初の遺伝子は完全にランダムな推力なので、平均すると打ち消し合い、ロケットはただ漂います。たまたまおおよそ正しい方向へ推したまれなロケットを選択が残し、交叉がそれらの良い区間を組み合わせて初めて、まとまりのある飛行が現れます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
遺伝的アルゴリズム・プレイグラウンドを開く