遺伝的アルゴリズムとは、生物群が環境へ適応するときの遺伝学的変化の諸概念(染色体の交叉・突然変異・自然淘汰)を問題解決方法に見立ててその解を探る手法である。英語ではGenetic Algorithm(略語でGA)。
問題の解の候補を生物の各個体の遺伝子に見立て、ランダムに生成した各個体の遺伝子を交換や突然変異により解にふさわしい遺伝子を持つ個体を生み出すように処理を進めていく。各個体が環境にどの程度適応しているかを算出し、遺伝子の適応度が高い個体は子孫を残しやすく、適応度が低い個体は子孫を残しにくくすることから遺伝的アルゴリズムと呼ばれる。
厳密解よりも適度に厳密解に近いものを最適解として探索するアルゴリズムの1つである。問題の解を求めるのに通常の全検索手法では非現実的に長時間を要する問題、あるいは極度に煩雑な手続きを必要とする問題に対して用いられる。
遺伝的アルゴリズムでは、冒頭にもあるように生命の進化の概念によって問題の最適化を行っている。
以下では、問題が与えられてからこれを遺伝的アルゴリズムによって解くまでのごく単純な流れを解説する。
ここでは、単純な例として
「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個体の一番右の個体の遺伝子が以下のように突然変異してみたりする。
|
→ |
|
上記の遺伝的操作をぐるぐると繰り返していくにつれて、適応度の高い人たちが多く残っていくようになる。
そして、ある程度進めていくと「a=5, b=5, c=5」という個体が最も適応度の高いものとして現れ、それがずっと生き残っていくこととなる(はずである)。突然変異により多少ぶれることがあっても、個体群が全体的にこの最適解に近い遺伝子を持っている(はずな)ので、もう少し世代を進めていけばまた同じ遺伝子が現れてくる。そうやって、今回の問題の答えがこの個体の表す数値である、と結論付けることになる。
総じて遺伝的アルゴリズムは「いいものといいものを掛け合わせればいいものが出来る」という信念に基づく手法であり、決定論的なものではないので「絶対に最適なものが求められる」という確証が得られたものではない。しかし冒頭にもあるように、「最適に近い解を求める」ための手法としては、やり方が簡単であり比較的それっぽい結果も得られるということから、比較的有用なものだということは出来るだろう。
遺伝的アルゴリズムは特徴をきちんと理解した上で、用量・用法を守って正しくご利用ください。
掲示板
82 ななしのよっしん
2021/01/31(日) 00:30:13 ID: XsPSNC/ljZ
まあ単純に考えれば「巨乳とのギャップ萌え」が発生したかもしれんな
もっと単純に考えれば形ぽいものが収束して意味あるものにさせたかっただけかもしれない
でもちょっと前まで花ぽく見えた事もあるし
王冠ぽく見えたこともあるし黒いカチューシャや
サングラスに見えたこともある
でも今は「赤いリボン」(今後変わる可能性も当然ある)
なぜ?ぽく見えたものは進化してもっと見える形にならないで別の赤いリボンに収束したのか?
これが本当に大事
萎えるて「俺の思ってるのと違う」て意味に思えるが
なんて独りよがりな考え方なのだ
(省略しています。全て読むにはこのリンクをクリック!)
83 ななしのよっしん
2021/01/31(日) 00:38:46 ID: 6TlJPoYXIe
ある程度収束したら複数系統に分かれるようにできたほうがいいかもしれんな
84 ななしのよっしん
2021/02/01(月) 18:11:51 ID: J+XJEOKJBA
このまま手足を単純に伸ばしてもよくわからないポーズになるしどうなるのかなぁと思っていたら、手のポーズが軌道変更されてO脚まで作られてきたな
本格的にコントラポストなポーズが出来てきたことで手足を作るモチベも出てきた
急上昇ワード改
最終更新:2024/05/13(月) 19:00
最終更新:2024/05/13(月) 19:00
ウォッチリストに追加しました!
すでにウォッチリストに
入っています。
追加に失敗しました。
ほめた!
ほめるを取消しました。
ほめるに失敗しました。
ほめるの取消しに失敗しました。