単語記事: 遺伝的アルゴリズム

編集

遺伝的アルゴリズムとは、生物群が環境へ適応するときの遺伝学的変化の諸概念(染色体の交叉・突然変異・自然淘汰)を問題解決方法に見立ててその解を探る手法である。英語ではGenetic Algorithm略語GA)。

概要

問題の解の補を生物の各個体の遺伝子に見立て、ランダムに生成した各個体の遺伝子を交換や突然変異により解にふさわしい遺伝子を持つ個体を生み出すように処理を進めていく。各個体が環境にどの程度適応しているかを算出し、遺伝子の適応度が高い個体は子孫を残しやすく、適応度が低い個体は子孫を残しにくくすることから遺伝的アルゴリズムと呼ばれる。

厳密解よりも適度に厳密解に近いものを最適解として探索するアルゴリズムの1つである。問題の解をめるのに通常の全検索手法では非現実的に長時間を要する問題、あるいは極度に煩雑な手続きを必要とする問題に対して用いられる。

分かりやすい例

  1. 少年少女100人ずつ用意します。
  2. 一生懸命歌っていただきます。
  3. 歌の上手い上位5人ずつを残して残りは殺します。
  4. 互いに交配して彼らの子供を男女100人ずつ用意します。
  5. 2〜4を何回も繰り返します。
  6. どっかで停止し、その時一番うまかった一組を残して殺します。
  7. 残った2人が鏡音リン・レンです。
  8. なんだってー!?

- 本掲示板>>3より

具体的にやってみよう

遺伝的アルゴリズムでは、冒頭にもあるように生命の進化の概念によって問題の最適化を行っている。
以下では、問題が与えられてからこれを遺伝的アルゴリズムによって解くまでのごく単純な流れを解説する。

問題設定

ここでは、単純な例として

「a*(10-a)*b*(10-b)*c*(10-c)を最大にするa,b,cの組(a,b,cは0以上10未満の整数)をめる」

というものを考えてみる。この程度の問題であれば総当たりでもコンピュータを使えば一で解けるが、変数の種類や値の範囲が増えていくとかかる時間が爆発的に増えていくため、遺伝的アルゴリズムほかいろいろな手法が必要となってくるのである。

「遺伝子」による記述

遺伝的アルゴリズムでは、変数を遺伝子として記述する。その方法は問題によってさまざまなものがあり、記述の仕方を変えることで問題が解きやすくも解きにくくもなったりする。

今回の問題では変数が3つなので、3つのハコからなる遺伝子を考えるのが簡単だろう。例えばa=1, b=2, c=5なら

1 2 5

といったように、数字の入ったハコの列を考えることにする。

初期状態としては、ランダムに数字の入ったハコ列がたくさん用意されている。生物っぽく言えば多様な「個体」がたくさんいるような状態になっている。とりあえず例として、上の1体と下の9体の計10体がいるとする。

0 3 8
1 9 6
5 2 5
4 0 7
7 0 5
1 3 3
6 4 4
7 5 8
6 5 8

遺伝的操作

これ以降の操作は、やり方によって順番が違ったり細かい設定があったりするが、とりあえずそれぞれを簡単に説明をしていく。

自然淘汰

それぞれの個体について、「適応度」を計算する。適応度とは、与えられた問題に対してどの程度有能な個体であるかという標であり、今回の例で言えば、実際に「a*(10-a)*b*(10-b)*c*(10-c)」をそれぞれ計算してみた結果が「適応度」ということになる。

適応度が高い個体の遺伝子は、次の世代で生き残る可性が高い。そんなわけで、上記10個体の中から次の世代で生き残る個体を計算すると、以下の人たちが残る(とりあえずここでは5個体を残すということにした)。他の人たちは自然殺されました。

5 2 5
1 3 3
6 4 4
7 5 8
6 5 8

ここで、生き残る個体を決定するための手法について、代表的なものに絞って解説する。

エリート選択

かっこいい名前がついているが、やっていることは単純に「適応度が高い順にn個生き残らせる」というもの。実装が簡単な上、結果の収束がいのが利点。その代わり、遺伝子の多様性が失われやすいため、後述のローカルミニマム・ローカルマキシマムに陥りやすくなってしまう。遺伝的アルゴリズムの成功のためには、ダメな子の存在が不可欠なのである。

これ単品ではあまり役に立たないが、後述の手法と上手く組み合わせて使うことで、解をめる速度を上げることができる。

ルーレット選択

割とよく使われる選択手法。東京フレンドパークルーレットのようなものを用意し、適応度の高い個体には広い面積、適応度の低い個体には狭い面積を割り当てる。そしてこのルーレットダーツをn本投げて、当たった個体が生き残る(選択済みの個体が選ばれたらやり直し)という手法。

収束の速度エリート選択にべて落ちる。しかし適応度の低い個体にも生き残りのがあるため、ローカルミニマムなどには陥りにくい。

この選択手法では必然的に乱数を多く用いるため、個体数が多い場合や世代数を重ねる場合には、乱数生成方法にも気を配るとよい。言標準のライブラリではなく、メルセンヌツイスターやXORShiftなど、ある程度きちんとした手法を利用しよう。

トーナメント選択

名前の通り、各個体同士でトーナメント戦を行い、上位n個が生き残るという手法。トーナメント表によっては適応度が低めの個体でも生き残るため、これもエリート選択よりはいい結果を出しやすい。また、本当にどうしようもなくダメな子は生き残らないため、収束率もそれほど悪くない。

交叉

個体同士が遺伝子の交わりによって新しい個体を生み出す操作。とりあえずオスとかメスとかはあまり気にしないことになっている。アッー!

例えば上の5体の中で、左から1番と2番が交わることを考える。3か所のハコについて、どちらの数字を使うかというのは、ランダムだったりちょっとしたテクニックを使ったりとやり方によってさまざまである。例えばこの交叉によって、下のように新たな個体が生まれる。

5 2 5
×
1 3 3
5 3 5

また、競走などでの高い優秀な個体は交配の人気が高かったりするように、適応度の高い遺伝子が交叉に使われやすくするというようなテクニックもあったりする。

突然変異

ある個体の遺伝子の一部がいきなり変わること。交叉だけでは親となる個体の性質しか伝わらないために、場合によってはあまり適応度が高くないのに同じような個体ばかりが生き残って、それ以降の適応度の向上が見られなくなってしまったりするので、突然変異によるランダムな変化が重要となることがある。

ただしその確率があまり高くなると、交叉によって優秀な遺伝子を残していくという遺伝的アルゴリズム本質から外れたただのランダムサーチになってしまうため、突然変異の確率については工夫が必要である。

例えば、上で生き残っていた5個体の一番右の個体の遺伝子が以下のように突然変異してみたりする。

6 5 8
1 5 8

繰り返し、そして終焉

上記の遺伝的操作をぐるぐると繰り返していくにつれて、適応度の高い人たちが多く残っていくようになる。

そして、ある程度進めていくと「a=5, b=5, c=5」という個体が最も適応度の高いものとして現れ、それがずっと生き残っていくこととなる(はずである)。突然変異により多少ぶれることがあっても、個体群が全体的にこの最適解に近い遺伝子を持っている(はずな)ので、もう少し世代を進めていけばまた同じ遺伝子が現れてくる。そうやって、今回の問題の答えがこの個体の表す数値である、と結論付けることになる。


総じて遺伝的アルゴリズムは「いいものといいものを掛け合わせればいいものが出来る」という信念に基づく手法であり、決定論的なものではないので「絶対に最適なものがめられる」という確が得られたものではない。しかし冒頭にもあるように、「最適に近い解をめる」ための手法としては、やり方が簡単であり較的それっぽい結果も得られるということから、較的有用なものだということは出来るだろう。

利点と欠点

利点

  • 複雑な問題でもそれなりの時間でそれっぽい結果を得ることができる。

欠点

  • 偶然見つけられた場合を除いて、厳密な解が得られない。
  • 単純な総当りよりもアルゴリズムが複雑になる。
  • 「どのくらい個体を生き残らせるか」「どのくらい突然変異を起こすか」「初期個体の遺伝子をどのように設定するか」等、問題とは直接関係ないパラメータの調節が必要になる。
  • ローカルミニマム、ローカルマキシマムに個体が偏ってしまい、本当の最小値や最大値とはかけ離れた値を解としてしまうことがある。
    • 遺伝的アルゴリズムは言うなれば見えない人に複数の山頂がある山々を登れ、と言っているようなものである。一度ある山頂に到達してしまえば、もっと高い地点があるのにそこにたどり着けなくなってしまうという状態になってしまう。
      そこでさらに良質の解を得るために行うことといえば、その人を山頂から蹴落とすこと…つまり、1回時間を巻き戻して再演算を行うとか、適応度の評価方法や個体の選抜方法を一時的に変更する(環境を変えて今まで進化の頂点にいたらを殺する)、突然変異率を一時的に変更したりなどして退化させることである。

遺伝的アルゴリズムは特徴をきちんと理解した上で、用量・用法を守って正しくご利用ください。

遺伝的アルゴリズムが深く関わる諸作品

関連動画

関連商品

関連項目


【スポンサーリンク】

携帯版URL:
http://dic.nicomoba.jp/k/a/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
ページ番号: 1533024 リビジョン番号: 1699634
読み:イデンテキアルゴリズム
初版作成日: 09/02/22 22:21 ◆ 最終更新日: 12/12/13 21:39
編集内容についての説明/コメント: N700系新幹線電車
記事編集 / 編集履歴を閲覧

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

遺伝的アルゴリズムについて語るスレ

58 : ななしのよっしん :2013/08/09(金) 16:33:47 ID: luLzTOzNDB
D-Wave量子コンピュータ最適化問題の解法の一つ「焼きなまし法」を加速する装置だ。素因数分解が高速で解けるわけではないので暗号屋はまだ安心していい。

http://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3%95

59 : ななしのよっしん :2014/01/26(日) 04:33:24 ID: 8BSpTI+ZgV
>>54
そうだね、君みたいに人を見下してるようなコメントが多いのも特徴だね
原理は簡単だろうがそれをややこしくしか説明できないバカがそれらしくってるのが多いんだ、って話だよ言わせんな恥ずかしい

ちょっとROMってくるわ
60 : ななしのよっしん :2014/07/22(火) 18:51:27 ID: kSp42j8rdr
むにむに教授の木を作るやつとハイハイを学習させるやつが
分かりやすく出来てていいと思った
61 : ななしのよっしん :2015/03/24(火) 23:45:23 ID: KD4IXNY1gF
なんでカット&スライス法が載ってないんだぜ?
62 : ななしのよっしん :2016/02/25(木) 14:16:35 ID: a8Q3YMPcMl
新作動画で「墓があるからジャンプ」とか言ってる人があまりに多くてまだまだ認知度低いなあと思った
63 : ななしのよっしん :2016/03/02(水) 18:53:16 ID: CfVU2/Ossb
この動画の事なら、ニューラネットワークと画像認識がセットだから間違ってないよ
>>sm28277973
64 : ななしのよっしん :2016/03/08(火) 07:42:19 ID: iaclYnKp4r
むしろ、画像認識をしていないってしている人の多さが認知度の低さを物語ってるような
65 : ななしのよっしん :2016/03/18(金) 08:27:51 ID: 6TlJPoYXIe
目隠しプレイしか出来ないならそれが通用するゲームを選ぶのが先や
66 : ななしのよっしん :2016/05/14(土) 19:56:03 ID: UmM67rdOlX
>>63動画に関して言えばNEATGAのどっちかの認識を持ってない人が
>>62のような間違ったことを高に言ってる感じ
67 : ななしのよっしん :2016/11/20(日) 17:14:14 ID: Yu2FX+bMq7
あれを見て山本弘とこの人が頭に浮かんだ
  JASRAC許諾番号: 9011622001Y31015