トップページ⇒tech
42コメント13KB

遺伝的アルゴリズムを教えて下さい

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
Ｃ言語＆Ｃ＋＋で作りたいと思ってます
0002デフォルトの名無しさんNGNG
www1.neweb.ne.jp/wa/kamekame/ga/index.htm
0003しょーがないわねーNGNG
http://www.geneticprogramming.com/
0004お父さんでーすNGNG
int main( void )
{
　　int a,b;
　　a = 1 ;
　　b = 776 ;
　　printf("%d たす %d は %d です\n",a,b,a+b) ;
return 0 ;
}
0005中国語の的は日本語の「の」だとならった。NGNG
卵子は母親の遺伝子の内の半分、Ｘ染色体を提供し、精子は父親の遺伝子の半分のＸ染色体もしくはＹ染色体を提供する。
卵子が精子を受け入れることにより母親からの遺伝情報と父親からの遺伝情報が混じり合い、新しい生命体として子供が出来る。

一般的に遺伝情報には優性、劣性があって、優性遺伝情報は劣性遺伝情報をキャンセルして子供に現れる。が、劣性の遺伝情報も消えるわけではないので隔世で劣性の遺伝情報が現れることがある。

いじょ。
0006アダルトハンタNGNG
>>5
幽々白書に実例が紹介されていますね
0007デフォルトの名無しさんNGNG
ﾏｿｺの中にｱｰﾒｿを流し込めばOK.
0008デフォルトの名無しさんNGNG
ぼくはC++でつくりました。
GAの原理さえ知ってりゃわりとかんたんです。
0009デフォルトの名無しさんNGNG
＞１
卵との同期処理を忘れると動きません！
0010９NGNG
１じゃなくて >>7 の間違い
0011デフォルトの名無しさんNGNG
>>9
こっそりと同期させられてしまった経験あり
あのときはあせったね
0012デフォルトの名無しさんNGNG
>>11
プロ技板にようこそ＞キムタク

しっかしこの手のスレはなんでこうなるんだろ
興味あんのに・・・・・AIスレといいさ
0013デフォルトの名無しさんNGNG
1に自分で調べようと言う気がないから。
0014デフォルトの名無しさんNGNG
どうもAIスレと同じ奴が立てているような気がするのは俺だけか？
スレを立て逃げスンナ！
0015デフォルトの名無しさんNGNG
もしかして、黒衣じゃないか？
0016デフォルトの名無しさんNGNG
>>15
中西?
0017デフォルトの名無しさんNGNG
遺伝的アルゴリズムは、本質的には幅優先探索の一種です。
0018デフォルトの名無しさんNGNG
>>17
ちゃうよ。オペレータの設計によってどうとでもなる。
コツは連続空間をbit operationでジャンプするっちゅう
あたり。だから離散空間への適応はほぼないっす。
結局オペレータの設計いかん。
場合によってはモンテカルロよかまし程度に考えると
いいでしょう。
以前設計したやつは煮詰まると発散するようにした。
けど、それでも問題しだいやね。
ミューテーションに++とか--とかしてもいいんだよ。
遺伝アルゴリズムとか本読まないでチャレンジ
した方がいいと思われる。作ってから読もう。
0019SEANGNG
http://www.personal-media.co.jp/book/other/gagp.html
入門用
0020デフォルトの名無しさんNGNG
優良馬を輩出するための学問ですか？
0021五郎NGNG
>18

むずいなーわけわからん。
ライフゲームみたいなイメージなんだけど？

もっと実用的なってゆうか、よりアプリに近いレベルの話を聞きたい。
0022デフォルトの名無しさんNGNG
>ライフゲームみたいなイメージなんだけど？
それは、セルオートマトンと勘違いしてやしないかい?
0023五郎NGNG
>22
ごめん。セルオートマトンもよくわからない。

18さんの空間とかビットとかジャンプとか離散ってのをみて、なんだかライフゲームが頭に浮かんだだけっす。
なにもしらないしらないしらない。
AIの講義は１回出ただけなんですよ…。先生がつまんなそうだったから。講義する教授が別の人だったら講義出てただろうな。
0024デフォルトの名無しさんNGNG
>>17
戦略のある総当り探索といえる。
0025デフォルトの名無しさんNGNG
幅優先っつーか、ビームサーチそのもの。
002618NGNG
>>24,25
だってコストすらもってないじゃん。A*なんかの
一般公式にどうあてはめるの？探索空間をツリーでは
なくてどこでもいけるものとしてとらえるのがGAの違いだよ。
だから、GAは解のない所へもとんでいくっしょ。
もともとモンテカルロと大差ないんだから、いつかは
正解にたどり着く確率が100%に限りなく近くなるような
アルゴリズムだよ（収束速度あげたりするとそうでもないけど）
コードはだいたいこんなもん。３分もあれば書ける。
系列１=乱数の初期値
系列２=乱数の初期値
for(;;){
値１＝系列１の評価
　値２＝系列２の評価
　if( 値１＞値２ ){
　　値２＝遺伝子操作（値１，値２）
}else{
　　値１＝遺伝子操作（値１，値２）
　}
}
遺伝子操作はmutationとかcrossoverとか
好きなことすればいいよ。これはモデルが
単純過ぎてあんまり収束しないけどね。
0027デフォルトの名無しさんNGNG
GAはTSP(Traveling Salesman Problem)とかよく例に出されるよね。
002824NGNG
>>26
>だから、GAは解のない所へもとんでいくっしょ。
だから、総当りっていってるんだけど。

コードにPopulationの概念が入ってないぞ。
系列がPopulationのつもりかもしれんが、それなら世代が進まないので
なにを目的としてるのかわからん。系列が更新されないんだから
収束しないのはあたりまえ。
0029デフォルトの名無しさんNGNG
↑「デバッグ音頭」で検索できるぞなもし。
003026NGNG
総当りかぁ。うーん。
24さんにはごめん。

あ、ごめんコード間違えてた。
系列１=乱数の初期値
系列２=乱数の初期値
for(;;){
　値１＝系列１の評価
　値２＝系列２の評価
　if( 値１＞値２ ){
　　系列２＝遺伝子操作（系列１，系列２，値１，値２）
　}else{
　　系列１＝遺伝子操作（系列１，系列２，値１，値２）
　}
}
だね。スマソ。
遺伝子操作は、評価の比率で適当に２つの系列から
新しい系列を生成する関数のつもり。
003125NGNG
次の手が生成できるという事は枝が存在しているという事を意味しています。
ビームの幅がポピュレーションです。
次の世代へのパスが枝です。
ビームサーチそのものです。

003217NGNG
>18
有限個の染色体をバラ撒いて、解がありそうな部分を並列的に
探索してるんだから幅優先の一種だとおもうが…
003326NGNG
>>31
あのさあ、解の展開できるすべてのノードに対するコストと
すでに展開したノードのコストからなる関数をどう扱うかで
いろんな探索はできるのだよね。
枝はあるけど、可能性は全部じゃん。その理屈では全部を
対象とするんだから、１手で求まらないと変じゃない？
んじゃ、もっと聞くけどモンテカルロ法は何サーチなの？(藁
0034デフォルトの名無しさんNGNG
GAは
・確率的探索である
・与えられたコスト関数の最大化問題である
・変数空間の位相構造が比較的自由に決められる
　(離散最適化問題に適用しやすい)

という点から、simulated annealing法(SA)と類比されることが多いです。
多点同時SAという言い方をしている人もいます。

うんちくsage
0035デフォルトの名無しさんNGNG
>>32
その幅優先の一種をビームサーチって言うんだって。

>>33
要するにあんたはビームサーチって聞いた事もないわけね。
それならそれでいいです。さよなら。
0036デフォルトの名無しさんNGNG
GAをこのまえ卒研でつかいました。せんでもいいGUIまで用意して，そのせいで結構時間がかかりました。肝心のGA本体部分はそこまでむずくないっす。なんだか18さんのかきこみるとむずかしくきこえるみたいですけど、そんなことないっす。
0037デフォルトの名無しさんNGNG
32>35
べつに、ビームサーチじゃないとは言ってないよ。18さんが
幅優先じゃないよって言ってるから、それに反応しただけ。
あと、ビームサーチは幅優先というか、
最良(のn個)優先探索の一種だと。(山登り法の一種じゃ?)
0038デフォルトの名無しさんNGNG
シミュレーション板にもあった。
まー、あっちは閑古鳥が鳴いてて役に立つかどうかは･･･

http://mentai.2ch.net/test/read.cgi?bbs=sim&key=960616675
0039ななしさんNGNG
ここのスレ見て、ナップザック問題解くやつを作ってみた。

結構感動ものだね。n がいくら大きくても関係ねーよーって
感じが良い。
0040デフォルトの名無しさんNGNG
>39
>ナップザック問題解く
近似解を見つけるだけで「解く」と言われると、ちょっと違和感が…
(数理科学出身)
0041ななしさんNGNG
まあ確かに近似解だし、それがどの程度近似しているのかも
わからん。

ただ、今実用で似た問題を解く必要に迫られていて、
これなら十分だと感じた。つうか、試した例は全部
ぴったりの解が見つかった。

工学系の発想（なのか？）ですまん。
0042デフォルトの名無しさんNGNG
GAはね、設計につかうとかなり面白いよ。
パラメトリックデザインな問題にしておいて、
そのパラメータを最適化すんの。自作の画像圧縮ルーチンは
適当なオペレータをたくさんいれておいて、あとどれ使うか
というパラメータを作成して、それでぶんまわして３日くらい
機械に考えさせて作った。現在数万人くらい使ってるかな。
知らずに。
■ このスレッドは過去ログ倉庫に格納されています