5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

進化型計算

1 :名無しさん@お腹いっぱい。:2006/09/03(日) 18:00:58 ID:E0Mbsued0
遺伝的アルゴリズム(GA)など、進化型計算に関するスレッド

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

2 :名無しさん@お腹いっぱい。:2006/09/04(月) 01:04:13 ID:Lu4Tluho0
GAって離散空間に対するランダム探索とどう違うの?

3 :名無しさん@お腹いっぱい。:2006/09/27(水) 09:40:53 ID:INlbQsez0
ランダム探索は新しい個体を作るとき交差や突然変異しないんじゃん?

4 :名無しさん@お腹いっぱい。:2006/09/27(水) 12:25:20 ID:mN2AMeW40
ってか、突然変異だけじゃね?

5 :名無しさん@お腹いっぱい。:2006/10/02(月) 14:38:40 ID:7maW6lGv0
どうかな?

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

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

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


6 :名無しさん@お腹いっぱい。:2006/10/04(水) 03:13:10 ID:uW4pcXRD0
>>5さんのいうランダム探索の定義を教えてください。

7 :名無しさん@お腹いっぱい。:2006/10/04(水) 19:52:43 ID:FV/8z84V0
解と言ったら、暗黙に解空間をR^nとしたものを考えるわけだけど、
GAなので都合よく離散化するために解空間をZ^nにしましょうか?

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

age乙

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

8 :名無しさん@お腹いっぱい。:2006/10/04(水) 19:54:52 ID:FV/8z84V0
おっとしまった、暗黙にR^nじゃないや、大多数はZ^nが一般的だ、間違えた。

9 :名無しさん@お腹いっぱい。:2006/10/09(月) 07:43:25 ID:bObezdsD0
仮に探索序盤でひとつだけ飛びぬけて良い解がたまたま発見されたとする
すると検索途中であるにも関わらず、その解に向かって急激に収束を開始する。
これが初期収束と呼ばれる探索初期の段階で局所的最適解に収束する現象である。
この解が大域的最適解であるならば特に問題にはならないのだが、多くの場合
これは局所解のひとつであり、最適解は別のところにある場合が多い。

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

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

10 :名無しさん@お腹いっぱい。:2006/10/09(月) 09:20:26 ID:47VJLyW90
シミュレーテッドアニーリングって最近聞かなくなったけど、どう違うの?

11 :名無しさん@お腹いっぱい。:2006/10/09(月) 10:20:19 ID:szfx6FXX0
>>10
ランダムというか、誤差の最大値が徐々に小さくなってく感じだったっけ。


12 :名無しさん@お腹いっぱい。:2006/10/09(月) 10:29:59 ID:47VJLyW90
俺、昔使ったんだけど、
最初は大きめにジャンプさせて、荒っぽく最適解がありそうな所を探して
割と言い結果が出てる所を残して、そこから徐々にジャンプ量を小さくしていって
最適解に収束させるって方法だったような・・・(遠い目)

13 :名無しさん@お腹いっぱい。:2006/10/09(月) 16:41:55 ID:72eFW7kU0
突然変異は極所解対策じゃなかったっけ?

14 :名無しさん@お腹いっぱい。:2006/10/13(金) 00:43:51 ID:Fmqeqvmr0
>>7
あのさ、ぜんぜん違うでしょ?
どこが同じなのか説明してください。

15 :名無しさん@お腹いっぱい。:2006/10/15(日) 04:36:49 ID:AGehj/Px0
SAはもう業界標準化したから。
数物系では理論として基本になってるから、
情報系の人にはもう手を出せなくなってるところはある。
論文読もうねw

16 :名無しさん@お腹いっぱい。:2006/11/11(土) 00:35:26 ID:TN+Bp7Pk0
ヒント:離散空間
ヒント:どう違うのかと聞いているのであって同じとは一言も言っていないし説明できる知識も無い

17 :名無しさん@お腹いっぱい。:2006/11/11(土) 01:27:35 ID:TN+Bp7Pk0
>>14
乱数を使っているからです

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

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

18 :名無しさん@お腹いっぱい。:2006/11/27(月) 15:02:02 ID:MLbXiGPu0
関連wiki
http://wiki.ninki.org/wiki.cgi?p=%bf%ca%b2%bd%b7%bf%b7%d7%bb%bb


19 :名無しさん@お腹いっぱい。:2006/12/17(日) 07:17:17 ID:GfVjIjnN0
>>11
乱数を内部で使っていると、ランニングタイム無限で最適解を出力する確率が1に収束すると見なしていいかな?

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

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

6 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)