遺伝的アルゴリズムGenetic Algorithm
複数の候補を混ぜ少し変えて選んでいく方法
- 遺伝的アルゴリズムは候補を一度にたくさん作っておいて、うまくいったものを選んで混ぜ、少し変える作業を繰り返す方法です。
- 候補一つは設定値を並べた一覧です。その一覧を点数で順に並べ、上位だけを次の回に進めます。
- 混ぜるとは、うまくいった二つの候補の項目を分けて受け取り新しい候補を作ることで、一か所をわざとずらして変える作業も一緒に行います。
- 勾配が求められなかったり設定が飛び飛びの値だったりするときに役立ちます。代わりに候補の数だけ試験しなければならず遅いです。
- 多様性が消えるとそこで止まります。だからわざと出遅れた候補も少し残し、変える幅を調節します。
目次
1たとえで理解する
キャンプ場に着いて日よけを張るのに、正解は一つではありません。ポールをどれだけ高くするか、ロープを何度に広げるか、ペグを何本打つか、どちら側を風上に向けるか。組み合わせは数十通りです。一組ずつ順番に試す代わりに、六か所で六通りのやり方を一度に張ってみると、夕方の風一回で六つの答えが出ます。そのうちよく持ちこたえた二つを選び、一方のポールの高さと他方のロープの角度を取ってきて新しく張ります。そこにペグの本数一つだけをわざと変えてみます。翌日の夕方には、最初よりずっと頑丈なやり方が手元に残ります。遺伝的アルゴリズムはこのやり方をそのまま移したものです。
2くわしく
一つではなく一群を扱います
普通の学習は答え一つを持って少しずつ直していきます。遺伝的アルゴリズムは最初から候補を数十から数百作っておいて一緒に動かします。この群れを集団と呼びます。
候補一つは設定値をずらりと並べた一覧です。日よけなら、ポールの高さ、ロープの角度、ペグの本数のような項目が順番に書かれた行です。項目をどう決めるかが問題を解く半分を占めます。項目が細かすぎると組み合わせが手に負えないほど増え、粗すぎると良い答えが一覧の中に入らなくなります。
点数で順に並べ上位だけ残します
候補ごとに実際に試験して点数を付けます。この点数を適応度と呼びます。日よけなら風にどれだけ耐えたか、駐車の問題なら目標の場所にどれだけ近づいたかです。ここで大事なのは点数を付ける規則さえあればよいという点です。どう直せば良くなるか知る必要はありません。
点数順に並べたあと、上位いくつかを次の回の親に選びます。ただし常に一位だけを選ぶわけではありません。いくつか抜き出してその中から良いものを選ぶ形で少し緩く選んでこそ、序盤にたまたま良かった候補が集団全体を独占しません。いちばん良い候補一つか二つはそのまま次の回に進めることもあります。
混ぜることと一か所を変えること
新しい候補は二つの親の一覧を分けて受け取って作ります。前半分は片方から、後半分はもう片方から取ってくる形です。項目ごとにコインを投げてどちらから受け取るか決めることもあります。違う強みを持つ二つをつなげてより良い一つを狙う仕掛けです。
ここにもう一つ加えます。作った一覧から項目を一つ選び、値を少しずらして変えるのです。これがないと、最初に作った候補の中になかった値は永遠に現れません。変える幅が小さすぎると同じ場所を回り続け、大きすぎるとせっかく見つけた良い組み合わせが毎回崩れます。混ぜることは持っているものを組み合わせる作業で、変えることはなかったものを持ち込む作業です。
世代が重なると
一回を世代と呼びます。世代が進むほど点数の平均が上がり、集団の中の候補どうしが似てきます。あるところからいくら回しても点数が上がらなくなると、そこで止まります。
問題はあまりに早く似すぎてしまう場合です。序盤に目立って良い候補が一つ出ると、その子孫が集団を埋め尽くし、より良い答えが別のところにあっても、そこへ向かう候補が残りません。だから選び方を緩くしたり、変える割合を少し上げたり、集団をいくつかに分けて別々に動かしながらときどき混ぜたりする方法を使います。
どこに使うか
勾配が求められる問題なら、たいてい勾配降下法系のほうがずっと速いです。遺伝的アルゴリズムの出番はその反対側です。点数は付けられるがどちらに直せば良くなるかわからない問題、設定が個数や順序のように飛び飛びの値である問題、良い答えがあちこちに散らばっている問題で役に立ちます。
かかる値は試験の回数です。世代ごとに候補の数だけ試験しなければならないので、一回の試験に時間がかかると手に負えません。だから試験が速い問題や複数台を同時に動かせる問題でよく使い、神経網の設定値を選ぶ作業や形を設計する作業にときどき使われます。
3もう少し正確に
遺伝的アルゴリズム(Genetic Algorithm)は、進化の選択・交叉・突然変異をまねて作った探索方法です。候補一つを個体、設定の一覧を遺伝子、候補の群れを集団、点数を適応度と呼びます。親を選ぶ方式はトーナメント選択や順位に基づく選択がよく使われ、上位の候補をそのまま進めることをエリート保存と呼びます。目的関数の勾配を使わないので微分できない問題にも当てはめられますが、最適な答えを見つける保証はありません。
たとえがずれる点もあります。日よけは人が目で見てどちらがなぜ持ちこたえたか見当がつきますが、遺伝的アルゴリズムは理由を問わず点数だけを見ます。だから人が見て不自然な組み合わせが生き残ることもあります。またキャンプは夕方一回で六通り試せば終わりですが、実際の問題では同じ候補でも条件によって点数が変わるので、何度も試して平均を取らなければならない場合が多いです。
4やってみる
5よくある誤解
遺伝的アルゴリズムは学習の一種だと思われがちですが、実際にはデータから規則を学ぶのではなく、良い設定を探し出す探索方法です。
世代を長く回せば必ず最良の答えに届くと考えられがちですが、実際には集団が早く似すぎてしまうとそこで止まります。
変える割合は高いほどよいと信じられがちですが、実際には高すぎるとせっかく見つけた良い組み合わせが毎回崩れて点数が上がりません。
7ひとこと要約
つまり遺伝的アルゴリズムは、候補を何組も作って点数で順に並べたあと、うまくいったものを混ぜて一か所ずつ変えながら答えを仕上げる方法です。
誤りや、もっと良いたとえがありますか？ 修正を提案する · 最終更新2026-09-02