- 締切済み
ＧＡ(遺伝的アルゴリズム)を教えてください！
republikyの回答
- republiky
- ベストアンサー率50% (7/14)
質問が2/10の書き込みなので、もう遅いかもしれませ んが、回答受付中だったのでとりあえず書いておきま す。シンプルなGAのプログラムを組む程度であれば、 MATLABでもCでも、手間はほとんど変わらないと思い ます。少々長いですがご容赦ください。 簡単な問題で考えましょう。解が整数のみとして、 0<=x<256の範囲において、関数(x-10)*(x-10)が最小値 となるような整数xをGAで求めてみましょう。 当然、答えはx=10となりますが、これがどのように して求められるのか説明していきます。 まず、解の候補をいくつか（たとえば5個）ランダムに 作成します。0<=x<256の範囲内にある任意の整数が適 当に5個選ばれます。それを x_i(i=1,2,3,4,5)として おきましょう。 ----------------------- （ステップ１） 目的は、関数f(x)=(x-10)*(x-10)の値が最も小さく なるようなxを求めるので、(x_i-10)*(x_i-10)の値 が大きいものは、求めたい解とは違うので削除しま す。 たとえば、解の候補が以下のように5つあったとき、 x_1 = 3 x_2 = 134 x_3 = 203 -> 削除 x_4 = 45 x_5 = 98 x_3はf(x_i)の値が最も大きいので、削除します。 一方で、x_1はf(x_i)の値が最も小さいので増殖 させます。つまり、 x_1 = 3 x_2 = 134 x_3 = 3 <- x_1と同じ値のものが増える x_4 = 45 x_5 = 98 プログラムでは、x_3 = x_1と書くだけで済む話です。 これが、GAでいう「選択」とか「淘汰」と呼ばれる ものです。 ----------------------- （ステップ２） 次は、x_iを「交叉」させます。つまり、親2人から 子供2人を生み出すことです。これは確率的に行う ので、すべてのx_iが交叉するわけではありません。 たとえば、x_2とx_3が両親となって、子供が2人生ま れるとしましょう。x_2とx_3を二進数で表現して、 x_2 = (10000110), x_3 = (00000011) とし、適当な場所で値を入れ替えます。例えば、下位 3ビットのみ入れ替えるのであれば、 x_2 = (10000011), x_3 = (00000110) となります。このようなビット列の入れ替えを確率 0.25くらいで行います。 ----------------------- （ステップ３） 最後に突然変異させますが、これはx_iのビット列 のうち、あるビットの値が0から1、もしくは1から0 に変化させるもので、確率0.01くらいの稀なケース として行わせます。 ----------------------- ステップ１～３までの1回の操作を「1世代」と呼び ます。これを何10世代、何100世代と繰り返していく と、「f(x)の値を最小にする」という目的にあった x_iのみが何世代にも渡って生き残って増殖していき 逆にf(x)の値が大きいx_iは数世代で死滅していきま す。 大雑把ですが、これがGAの流れです。もちろん、ここ で述べたことはあくまでイメージとして捉えるための ものなので、詳細は専門書を読まれることをお勧め します。私が講義で使ってるのは、萩原将文著「遺伝的アルゴリズム（朝倉書店）」です。最初の１，２章 を理解しておけば、概要を掴むには十分かと思います。
関連するQ&A
- 遺伝的アルゴリズムのプログラム
はじめての投稿になります．これからよろしくお願いします． 先日、大学でＧＡを使って あるxの関数(例えば，f(x)=x^2-2=0のxにあてはまる解を導き出す)を解いてくるようにと課題がありました。 しかし、ＧＡに関しては交叉や突然変異など基本的な用語を 教わったのみでプログラムが全然分かりません。 自分でも色々調べてみたのですが、全く参考になりそうなものが 見つかりませんでした。 そこで、もしご存知の方がいらっしゃるなら教えていただけないでしょうか？ プログラムを組む場合にはＣ言語を使うことになるのですが、どなたかＣ言語でよろしくお願いいたします！
- 締切済み
- C・C++・C#
- 遺伝的アルゴリズムのプログラミングについてですが・・・
遺伝的アルゴリズムのプログラムの基本的な流れが↓のページ http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/GA/GA.htm に 【1.初期化 2.生物集団の評価 3.交叉 4.突然変異 5.各個体の評価 6.淘汰】と書かれてあるのですが、 f(x) = sin(3x) + 0.5sin(9x) + sin(15x + 50) [0.1]区間の最大値を求める↓のプログラム http://www.sist.ac.jp/~suganuma/cpp/3-bu/18-sho/genetic/C++/gene_f.txt に当てはめるとどの部分がどこに当たるのでしょうか…(また、このプログラムはどこからどのように読んでいけばいいのでしょうか…)。一応コメントが書かれていますがよく分かりません＞＜； わかる方がいらっしゃいましたらよろしくお願いしますm( _ _ )m また、遺伝的アルゴリズムのプログラミングをする際の注意点があれば教えてください。
- ベストアンサー
- C・C++・C#
- 遺伝的アルゴリズムのシュミレーション
私は、遺伝的アルゴリズムについて勉強中です。 MATLABでGAをシュミレーションしたいのですが、英語で扱いにくい現状です。 MATLABやそのGAを扱う方法を解り易く説明したサイトを教えていただけませんか？ また、MATLAB以外のGAのソフト（出来れば日本語版）を知っていましたら教えていただけませんでしょうか？
- 締切済み
- その他([技術者向] コンピューター)
- 遺伝的アルゴリズム（ＧＡ）について
今（独学）Ｃ言語でＧＡの手法を勉強しています。まずはじめに、y=3x^3+2x^2+5x という関数で最小値探索を行うプログラムを作成しようとしているのですが、一点交叉など難しくて書けません。いろいろ図書館などへ行って調べているのですが、参考になるサンプルプログラムが無く、どうしたらよいのか解らないので教えてください。よろしくお願いします。
- 締切済み
- C・C++・C#
- 実践的な遺伝子的アルゴリズムの作成法
素人ですが、遺伝子的アルゴリズムを考える上で、大きな問題に直面しています。 １）最適化の対象を如何にコーディングするか？ ２）交叉点を如何に設けるか？ これらは組合せの対象の要素間に何らかの曖昧な複数の相関関係がある場合に難しくなります。 そこで、 １）「遺伝子的アルゴリズム」をタイトルにした一般の技術系の和書に書かれている以外に、実例を調べる手段？ ２）社会人が遺伝子的アルゴリズムの開発の実際を学ぶための公共の機関、例えば聴講生として学べる場所？ ３）遺伝子的アルゴリズムを組み込んだソフトを作る上で、普段使用しているＣ＋＋などの汎用プログラム言語と、ＳｃｈｅｍａやＬＩＳＰなどの知能プログラミング言語とでは、どちらが便利なのでしょうか？ これらの人工知能プログラム言語には、コーディングや交叉のための専用のコマンドが提供されているのでしょうか？ 自分は、情報工学の出身ではないため、Ｃ＋＋言語と「遺伝子的アルゴリズム」の技術書籍以外には、バックグラウンドがありません。よろしくお願いいたします。
- ベストアンサー
- その他（プログラミング・開発）
- 遺伝的アルゴリズムによる繰り返し囚人のジレンマ
初めて質問をさせていただきます。ヨロシクお願いします。 遺伝的アルゴリズムによる繰り返し囚人のジレンマゲームに関するプログラミングについて分からないことがあります。 当方はC++初心者のためクラスの使い方がイマイチ分かりません。 クラスの概念は文献により理解できるのですが便利さが実感できません。 具体的にいうと、遺伝的アルゴリズムのどの部分にクラスが適用できるのでしょうか？クラスを用いないで強引にプログラムすることは出来そうなのですが…。 囚人のジレンマゲームに関わらず、遺伝的操作(選択、交叉、突然変異)をクラスの概念を用いてプログラムする際のヒントとコツなどを教えて下さい！また遺伝子情報は配列を用いて表現するのでしょうか？なにぶん遺伝的アルゴリズムは初めてなので分からないことだらけです。ヨロシクお願いいたしますm(__)m
- ベストアンサー
- C・C++・C#
- Javaでの遺伝的アルゴリズムの実装について
別のWebサイトでも質問させていただいているのですが、 double[][] a={ {1,1,1,1,1,1,1,1,1,1}, {1,2,1,4,1,1,1,8,1,1}, {2,2,2,2,2,2,2,2,2,2}, {2,2,2,3,2,2,2,3,2,2}, {2,2,2,2,2,4,2,2,3,2}, }; のように予め決められている２次元配列（a[0],a[1],a[2],a[3],a[4]それぞれが遺伝子）と、 double[] fitness={50,100,60,90,120}; のように遺伝子それぞれに対応している適応度があるとして、（適応度は別プログラムで計算済み） 遺伝的アルゴリズムで予め設定された遺伝子と適応度をエリート及びルーレット選択、交叉、突然変異を行う（一世代のみ）プログラムをJavaを用いて作りたいのですが、 Web上にある例となるClassは初期集団をランダムで生成した上で、ランダムに生成された遺伝子に対し適応度計算を行い、それを選択、交叉、突然変異を行うClassに投げるものがほとんんどです。 なので、適応度計算を行わずに既にある遺伝子と適応度をどのようにして結びつけるのか、もともとランダムに生成された遺伝子に適応度計算を行うこと、複数世代行うことを前提に設計されている選択・交叉・突然変異等のClassをどう変更すればよいのかわからず、手詰まりになってしまいました。 周りの知り合いに聞いても、Javaは少しならわかるが専門外、遺伝的アルゴリズムは勉強したことがない人ばかりなので、聞きたくても聞けない状況となっております・・・。 遺伝的アルゴリズム及びJavaに詳しい方、どなたか実装例を教えていただけないでしょうか？ 参考にさせていただいたURL：http://www.ics.kagoshima-u.ac.jp/edu/ProgramingJava/samples/SimpleGA/step1/index.html#GA%20%E3%82%AF%E3%83%A9%E3%82%B9
- 締切済み
- Java
- 遺伝的アルゴリズムのクラスライブラリ
遺伝的アルゴリズムについて、できるだけわかりやすく使いやすいクラスライブラリはないでしょうか？ C++、できれば Java が良いのですが。 自分で１から作成しようかとも思ったのですが、遺伝的アルゴリズムは有名なので、みんなが使えるようなライブラリがすでに公開されているかも、と思いました。 もしあったら、自分はGA以外の部分のプログラムに集中することができますし。 できれば、使用感など教えていただけるとありがたいです。
- 締切済み
- その他（プログラミング・開発）
- 遺伝的アルゴリズム
遺伝的アルゴリズムをCで組み、Cygwinのgccコマンドでコンパイルしたのですが、実行するとエラーが出てしまいます。 gsb内で実行しwhereコマンドで異常箇所を探した場合のメッセージは以下の通りです。 #0 0x61016525 in stack_info::walk () from /usr/bin/cygwin1.dll #1 0x7c859dcc in OutputDebugStringsA () from /cygdrive/c/WINDOWS/system32/kernel32.dll #2 0x40010006 in ?? () #3 0x00000000 in ?? () プログラムは長いので載せられませんが、アルゴリズム中の染色体は二次元配列の遺伝子を含む構造体です。 遺伝子の配列に関わるノード数（chromo[timeslot][NODE]←このNODEです。プログラム冒頭で値をdefineで宣言しています）が30位なら世代数が比較的多くても動くのですが、これが50あたりになると世代数が低くてもエラーが出てしまいます。 printf関数で交叉や突然変異の結果を表示しているのですがちゃんと動作しているようです。 二台のパソコンどちらでやってもこのようなメッセージが出るので困っています。何が起こっているか見当がつく方、いらっしゃいましたら助言願います。 よろしくお願いいたします。
- ベストアンサー
- C・C++・C#
- ２次関数の最小値をＣ言語とGAを用いて求めたいです
私は機会系の大学生のものです。 今回は ２次関数の最小値をプログラムのＣ言語と遺伝的アルゴリズム（ＧＡ）を用いて求めたいのですが 私がＣ言語が素人のためプログラムを作れません...。例として教えていただけると幸いです。 よろしくお願い致します。
- 締切済み
- C・C++・C#