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

Ｃ言語＆Ｃ＋＋で作りたいと思ってます

www1.neweb.ne.jp/wa/kamekame/ga/index.htm

http://www.geneticprogramming.com/

int main( void )
{
　　int a,b;
　　a = 1 ;
　　b = 776 ;
　　printf("%d たす %d は %d です\n",a,b,a+b) ;
return 0 ;
}

卵子は母親の遺伝子の内の半分、Ｘ染色体を提供し、精子は父親の遺伝子の半分のＸ染色体もしくはＹ染色体を提供する。
卵子が精子を受け入れることにより母親からの遺伝情報と父親からの遺伝情報が混じり合い、新しい生命体として子供が出来る。

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

いじょ。

>>5
幽々白書に実例が紹介されていますね

ﾏｿｺの中にｱｰﾒｿを流し込めばOK.

ぼくはC++でつくりました。
GAの原理さえ知ってりゃわりとかんたんです。

＞１
卵との同期処理を忘れると動きません！

１じゃなくて >>7 の間違い

>>9
こっそりと同期させられてしまった経験あり
あのときはあせったね

>>11
プロ技板にようこそ＞キムタク

しっかしこの手のスレはなんでこうなるんだろ
興味あんのに・・・・・AIスレといいさ

1に自分で調べようと言う気がないから。

どうもAIスレと同じ奴が立てているような気がするのは俺だけか？
スレを立て逃げスンナ！

もしかして、黒衣じゃないか？

>>15
中西?

遺伝的アルゴリズムは、本質的には幅優先探索の一種です。

>>17
ちゃうよ。オペレータの設計によってどうとでもなる。
コツは連続空間をbit operationでジャンプするっちゅう
あたり。だから離散空間への適応はほぼないっす。
結局オペレータの設計いかん。
場合によってはモンテカルロよかまし程度に考えると
いいでしょう。
以前設計したやつは煮詰まると発散するようにした。
けど、それでも問題しだいやね。
ミューテーションに++とか--とかしてもいいんだよ。
遺伝アルゴリズムとか本読まないでチャレンジ
した方がいいと思われる。作ってから読もう。

http://www.personal-media.co.jp/book/other/gagp.html
入門用

優良馬を輩出するための学問ですか？

>18

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

もっと実用的なってゆうか、よりアプリに近いレベルの話を聞きたい。

>ライフゲームみたいなイメージなんだけど？
それは、セルオートマトンと勘違いしてやしないかい?

>22
ごめん。セルオートマトンもよくわからない。

18さんの空間とかビットとかジャンプとか離散ってのをみて、なんだかライフゲームが頭に浮かんだだけっす。
なにもしらないしらないしらない。
AIの講義は１回出ただけなんですよ…。先生がつまんなそうだったから。講義する教授が別の人だったら講義出てただろうな。

>>17
戦略のある総当り探索といえる。

幅優先っつーか、ビームサーチそのもの。

>>24,25
だってコストすらもってないじゃん。A*なんかの
一般公式にどうあてはめるの？探索空間をツリーでは
なくてどこでもいけるものとしてとらえるのがGAの違いだよ。
だから、GAは解のない所へもとんでいくっしょ。
もともとモンテカルロと大差ないんだから、いつかは
正解にたどり着く確率が100%に限りなく近くなるような
アルゴリズムだよ（収束速度あげたりするとそうでもないけど）
コードはだいたいこんなもん。３分もあれば書ける。
系列１=乱数の初期値
系列２=乱数の初期値
for(;;){
値１＝系列１の評価
　値２＝系列２の評価
　if( 値１＞値２ ){
　　値２＝遺伝子操作（値１，値２）
}else{
　　値１＝遺伝子操作（値１，値２）
　}
}
遺伝子操作はmutationとかcrossoverとか
好きなことすればいいよ。これはモデルが
単純過ぎてあんまり収束しないけどね。

GAはTSP(Traveling Salesman Problem)とかよく例に出されるよね。

>>26
>だから、GAは解のない所へもとんでいくっしょ。
だから、総当りっていってるんだけど。

コードにPopulationの概念が入ってないぞ。
系列がPopulationのつもりかもしれんが、それなら世代が進まないので
なにを目的としてるのかわからん。系列が更新されないんだから
収束しないのはあたりまえ。

↑「デバッグ音頭」で検索できるぞなもし。

総当りかぁ。うーん。
24さんにはごめん。

あ、ごめんコード間違えてた。
系列１=乱数の初期値
系列２=乱数の初期値
for(;;){
　値１＝系列１の評価
　値２＝系列２の評価
　if( 値１＞値２ ){
　　系列２＝遺伝子操作（系列１，系列２，値１，値２）
　}else{
　　系列１＝遺伝子操作（系列１，系列２，値１，値２）
　}
}
だね。スマソ。
遺伝子操作は、評価の比率で適当に２つの系列から
新しい系列を生成する関数のつもり。

次の手が生成できるという事は枝が存在しているという事を意味しています。
ビームの幅がポピュレーションです。
次の世代へのパスが枝です。
ビームサーチそのものです。

>18
有限個の染色体をバラ撒いて、解がありそうな部分を並列的に
探索してるんだから幅優先の一種だとおもうが…

>>31
あのさあ、解の展開できるすべてのノードに対するコストと
すでに展開したノードのコストからなる関数をどう扱うかで
いろんな探索はできるのだよね。
枝はあるけど、可能性は全部じゃん。その理屈では全部を
対象とするんだから、１手で求まらないと変じゃない？
んじゃ、もっと聞くけどモンテカルロ法は何サーチなの？(藁

GAは
・確率的探索である
・与えられたコスト関数の最大化問題である
・変数空間の位相構造が比較的自由に決められる
　(離散最適化問題に適用しやすい)

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

うんちくsage

>>32
その幅優先の一種をビームサーチって言うんだって。

>>33
要するにあんたはビームサーチって聞いた事もないわけね。
それならそれでいいです。さよなら。

GAをこのまえ卒研でつかいました。せんでもいいGUIまで用意して，そのせいで結構時間がかかりました。肝心のGA本体部分はそこまでむずくないっす。なんだか18さんのかきこみるとむずかしくきこえるみたいですけど、そんなことないっす。

32>35
べつに、ビームサーチじゃないとは言ってないよ。18さんが
幅優先じゃないよって言ってるから、それに反応しただけ。
あと、ビームサーチは幅優先というか、
最良(のn個)優先探索の一種だと。(山登り法の一種じゃ?)

シミュレーション板にもあった。
まー、あっちは閑古鳥が鳴いてて役に立つかどうかは･･･

http://mentai.2ch.net/test/read.cgi?bbs=sim&key=960616675

ここのスレ見て、ナップザック問題解くやつを作ってみた。

結構感動ものだね。n がいくら大きくても関係ねーよーって
感じが良い。

>39
>ナップザック問題解く
近似解を見つけるだけで「解く」と言われると、ちょっと違和感が…
(数理科学出身)

まあ確かに近似解だし、それがどの程度近似しているのかも
わからん。

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

工学系の発想（なのか？）ですまん。

GAはね、設計につかうとかなり面白いよ。
パラメトリックデザインな問題にしておいて、
そのパラメータを最適化すんの。自作の画像圧縮ルーチンは
適当なオペレータをたくさんいれておいて、あとどれ使うか
というパラメータを作成して、それでぶんまわして３日くらい
機械に考えさせて作った。現在数万人くらい使ってるかな。
知らずに。