進化型計算

遺伝的アルゴリズム（GA）など、進化型計算に関するスレッド

GA/ES/EP/GP/IA/ACOやEHWなどなど
GECCOやCECにセッションがあるような話題ならなんでもどうぞ

GAって離散空間に対するランダム探索とどう違うの？

ランダム探索は新しい個体を作るとき交差や突然変異しないんじゃん？

ってか、突然変異だけじゃね？

どうかな？

「評価が高い部分を残す」
って考え方（これを交差としようか？間違ってたらゴメン）は誰でも思いつくよ
自然自体がそうでしょ？

それを突然変異でいきなり変えるわけだから
それってランダム探索とどう違うの？
なんで交差だけで上手くいかないの？

問題と可能解に対する評価関数は決定してるよね？
とすると、初期解に対する交差が生成する解も決定しないかな？
じゃぁ突然変異は何をやっているの？

>>5さんのいうランダム探索の定義を教えてください。

解と言ったら、暗黙に解空間をR^nとしたものを考えるわけだけど、
GAなので都合よく離散化するために解空間をZ^nにしましょうか？

定義 （ランダム探索）
可能解s_i \in Z^nを乱数を用いて有限個生成（s_iの各要素を乱数で生成）する。
生成したもののうち、最も評価値の高いものを最適解とする探索。

age乙

まぁここは問題の解法を問うスレッドではなさそうなので、スレ違いかもね。

おっとしまった、暗黙にR^nじゃないや、大多数はZ^nが一般的だ、間違えた。

仮に探索序盤でひとつだけ飛びぬけて良い解がたまたま発見されたとする
すると検索途中であるにも関わらず、その解に向かって急激に収束を開始する。
これが初期収束と呼ばれる探索初期の段階で局所的最適解に収束する現象である。
この解が大域的最適解であるならば特に問題にはならないのだが、多くの場合
これは局所解のひとつであり、最適解は別のところにある場合が多い。

交差だけでGAを行おうとすると、このような現象が必ずと言っていいほど起こってしまう。
原因としては、解探索を行う候補の分散がなくなってしまうため。
この問題を解消するために突然変異を行ったりして、分散を一定探索数保とうとする作業を行う必要がある。

また、ランダム探索で行うと今度は収束する先がブレてしまい収束しなくなってしまう。
このためランダム探索と形質遺伝を考慮した探索をブレンドして探索するのが一般的。

シミュレーテッドアニーリングって最近聞かなくなったけど、どう違うの？

>>10
ランダムというか、誤差の最大値が徐々に小さくなってく感じだったっけ。

俺、昔使ったんだけど、
最初は大きめにジャンプさせて、荒っぽく最適解がありそうな所を探して
割と言い結果が出てる所を残して、そこから徐々にジャンプ量を小さくしていって
最適解に収束させるって方法だったような・・・(遠い目)

突然変異は極所解対策じゃなかったっけ？

>>7
あのさ、ぜんぜん違うでしょ？
どこが同じなのか説明してください。

SAはもう業界標準化したから。
数物系では理論として基本になってるから、
情報系の人にはもう手を出せなくなってるところはある。
論文読もうねw

ヒント：離散空間
ヒント：どう違うのかと聞いているのであって同じとは一言も言っていないし説明できる知識も無い

>>14
乱数を使っているからです

もちろんこれは突然変異で乱数を用いていると思っているからなので
乱数を使わずランダムでもない別の方法があるなら完全に違うと言えますね

>>9
丁寧にありがとうございます

関連wiki
http://wiki.ninki.org/wiki.cgi?p=%bf%ca%b2%bd%b7%bf%b7%d7%bb%bb

>>11
乱数を内部で使っていると、ランニングタイム無限で最適解を出力する確率が1に収束すると見なしていいかな？

これはランダム探索とGAの両方で成り立つと思うのだがどうか？

成り立つなら、両者に違いが無い理由の一つに挙げることができそうだが。

ＧＡとかニューラルネットって、嫌がられるキーワードになってしまったからなぁ。
まー言葉を変えてやってるだけだけどね。最近のパーティクルフィルタとかね。

一番の気に入らない理由が、

・進化型
・遺伝的

っていうあくまで比喩の表現を使い続けていることだな
おまけに中身の話ができる人を見たことも聞いたこともない

ニューラルネットワークで、教師信号を与えて任意のステートマシンになるように学習させることができるモデルってありますか？

ニューラルネット使わなくても、入力と教師信号で配列つくれば、任意の関数つくれるしな。
過学習するのは配列もニューラルネットももはや似たようなもんだしなぁ。

入力にあわせてうまいモデルを考えるってのをみんなでやってるところに、
なんでもかんでも遺伝的アルゴリズムとかニューラルネットもってこられても微妙なんじゃね？
メタヒューリスティクスが嫌われるのはその辺に原因があるような気が・・・。

説明になってないなこれ>>9

>>2に関連して、
http://ja.wikipedia.org/wiki/%E3%83%8E%E3%83%BC%E3%83%95%E3%83%AA%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%81%E5%AE%9A%E7%90%86

> 工学者や最適化の専門家にとっては、この定理は問題領域の知識
> を可能な限り使用して最適化すべきだということを示しており、
> 領域を限定して特殊な最適化ルーチンを作成すべきであることを示している。

だってさ。

メタヒューリスティック（対象に依存しない汎用的解法）は
そのまま使わずにヒューリスティックに落とせ
（知識を使って最適化しなさい）ということか。

ランダム探索とGAの違いは最適化できるか、できないかの違い

>>2だけじゃなくて
それ以降の「違い」に関する話とかに関連して
が正確かな

>>24

性能
|
| 　　　　　　　　　　　　　|
| ﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆﾆAﾆﾆﾆﾆﾆﾆﾆﾆ <- ノーフリーランチの概念図
|
〜(なかなか越えられない壁)〜
|
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ <- 世の中のほとんどの探索アルゴリズム
+----------------------------

だからこそ、流行ってたんじゃないの？
そりゃ上界の話はわかるし、ドメインを設定した方がうまくいくのもわかるよ。
当たり前。でも、いままではその当たり前すら実現できていなかったというか。

>>26
> ドメインを設定した方がうまくいくのもわかるよ
> 当たり前すら実現できていなかったというか

厳しい意見ですね。

「当たり前だが、それを行うのは非常に難しい」

と付け加えないと、>>9みたいに語られていることを鵜呑みにして、
何も考えずストレートに実装→真っ青になっちゃう人が出るのを予防できない。

>>16
> ヒント：離散空間

離散空間だと、評価関数は滑らかとは限らないしなー

いや、そもそも滑らかという考えをするのが間違いか

>>24

> ランダム探索とGAの違いは最適化できるか、できないかの違い
じゃー、GAとパーティクルフィルタの違いは？

>>29
自分でしらべたら？

借ります

今の進化計算手法で一番おもしろいトピックはなんですか

age

まだこの分野っておもしろいの？

最近はGAじゃなくてEDAらしいよ。

GAはプログラムで作るときが面白いな。
できると急につまらなくなるけどな。

抽象的アルゴリズム概念の因数分解はできますか？ｗ

進化する計算が存在できたとして、それが暴走しない条件を説明してくれ。
進化が劣化にならない条件を説明してくれ。

そもそも未知な物へ進化するとは良し悪し両方を含むということではないのか？
都合の良い考えだけで進化すると考えるのは愚かじゃないのか？
計算そのものが進化するとは裏返せば劣化という意味になる、
それは特徴が変わっただけにすぎないだろう。

進化ではなく、環境に常に存在する可変型。それは仕組みで情報処理を
するのではなく、ネットワークの繋がりを元に情報処理をする。
作られたものが動くのではなく、環境そのものに合わせて形を変える
計算と思ったほうが良いのではないか？

>>37
無数の組み合わせの可能性を試す、無数の組み合わせから出来た概念を
取り扱う情報処理装置なら可能だろう。

エリート戦略ってのがあってな・・・

>>39
エリート戦略には選択したエリートが間違った解だった場合に
間違った解での進化を止めることは不可能なことぐらい知れ。

宮元武蔵の言葉に「観の目つよく、見の目よわく」（ｒｙ
目の前の最も優秀な解を選ぶ建前論では、危機管理そのものを放棄
したのに等しい。誤動作する例外判定の無いプログラムのようだ。

生物が進化の過程でエリートを選択しなかった理由ぐらい勉強してこなかったのか？

どうやら俺は
中二病の馬鹿にレスしちまったようだ

中卒君あらわる↑

変なのが住み着いたなあ・・・

日本語でおｋ

プログラムの作成に当たり
仕様だけ与えて
あとはGPつかってプログラムを自動生成･･･
ってのはいつになったら実現するの？

>>45
無理、自動生成された仕組みから秩序が生まれない限り
暴走するだけ。ガン細胞の様に。

進化には犠牲がつき物だろう、

生物の進化では絶滅に近い状態があった場合に急激な進化
があったことが分かっている。

進化した後の秩序が自動的に形成されるかがポイントで
秩序なき進化は46の言う暴走と等しいだろう。

プログラムを生成する場合
評価関数は何にするのが普通なんだろう
プログラムとしての正解は(関数とみたとき)一つしかないのに

定義域のいろんな値に対する関数値とか？

>>49
だよなぁ

でもできれば
int plus(int a, int b){
int result=a+b;
while(1);
return result;
}
見たいなのにも評価を与えたいところ

>>50
無限ループの行が致死性（lethal）だから評価できなくていんじゃね？
GA や GP では遺伝型が致死性になるのをできるだけ防ぐ工夫も重要だったりする。

ループ以外の部分は、この個体では評価されてないが、
集団全体で見ればちゃんと評価されてるのでおk

>>49ので考えてみて気づいた

教師となるプログラムがないと
値の正当性を評価できない
プログラムを作るのが目的なのに困った

引数と関数値の正しい組合せを学習データとして大量に与える

>>53
具体性の欠片も感じられない

>>54
実際に触ったことないなら
せめてググるくらいしてから来いよ、坊や

>>53ので問題なのは
有限個の学習データに対し
それを満たす異なったプログラムが無数にあることだと思うけれど
複雑さにペナルティを与えることで
上手くいくと思う

例えば
対象がプログラムでなく数式の場合は
数式y=xを作りたかったとして
学習データ(-1,-1),(0,0),(1,1)を与えたとき
y=-x^3+2xよりもy=xのほうが生成確率が上がる

有限個の学習データでも
そのデータがプログラムの特徴を上手くつかんでいて
かつ
コード化、評価関数が上手く定められていれば
何とかなりそうな気も･･･というより何とかするのが目的か

問題は
対象がプログラムのとき
どのようなコード化、評価関数がよいのか･･･

希望的観測だなｗ

>>57
思い込みたい奴は、普通そうなんでは？
脳内仮説が事実のように暴走したような

GAは問題に依存しない解法
だから「メタ」ヒューリスティックとか言われてんじゃねーの？

きちんと「進化」を問題として扱えってことなんだろ？
疑問視してるやつの批判ってのは

進化するとは、先天的情報を一切無視できることを言う。
先天的制限の範囲でしか問題解決できないアルゴリズムは進化とはいわない
想定の範囲。（ホリエモン

遅レスだが>>41ってかなり粘着キチガイだとわかった。

ほしゅ
でも粘着キチガイがこないことを祈る

62が基地害だからもう意味なしのスレだと確定

２０１０年には、１００発言に到達予定、そして２１００年には
何も無い誰の記憶からも消える。

そんな難しい考えはどうだっていいよ
暗算にしろｲﾝﾄﾞ式にしろ早く計算することが正しいんだと言われればそれまでで今まで俺が学んできた数学ってなんなんだって事
結局は人それぞれ考え方が違うんだよ
しゃあないな

>>65
数学の基本は美しさを求める学問だと悟ってない状況でそんなこと
いわれてもねぇ。