はじめまして。
先日、大学でGA(遺伝的アルゴリズム)を使って
簡単な掛け算の(例えば、3×○=12で○の中に当てはまる
数字を導き出す)問題を解いてくるようにと課題がありました。
しかし、GAに関しては基本的な用語(交叉や突然変異など)を
教わったのみでプログラムが全然分かりません。
自分でも色々調べてみたのですが、全く参考になりそうなものが
見つかりませんでした。
そこで、もしご存知の方がいらっしゃるなら教えていただけないでしょうか?
プログラムを組む場合にはC言語(C自体も使ったことがありません・・・。)
を使うことになるのですが、できればMATLABを使いたいと思っています。
もちろんC言語でも構いませんので、よろしくお願いします!
A 回答 (3件)
- 最新から表示
- 回答順に表示
No.3
- 回答日時:
質問が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)として
おきましょう。
-----------------------
(ステップ1)
目的は、関数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でいう「選択」とか「淘汰」と呼ばれる
ものです。
-----------------------
(ステップ2)
次は、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くらいで行います。
-----------------------
(ステップ3)
最後に突然変異させますが、これはx_iのビット列
のうち、あるビットの値が0から1、もしくは1から0
に変化させるもので、確率0.01くらいの稀なケース
として行わせます。
-----------------------
ステップ1~3までの1回の操作を「1世代」と呼び
ます。これを何10世代、何100世代と繰り返していく
と、「f(x)の値を最小にする」という目的にあった
x_iのみが何世代にも渡って生き残って増殖していき
逆にf(x)の値が大きいx_iは数世代で死滅していきま
す。
大雑把ですが、これがGAの流れです。もちろん、ここ
で述べたことはあくまでイメージとして捉えるための
ものなので、詳細は専門書を読まれることをお勧め
します。私が講義で使ってるのは、萩原将文著「遺伝的アルゴリズム(朝倉書店)」です。最初の1,2章
を理解しておけば、概要を掴むには十分かと思います。
No.2
- 回答日時:
GAを初めて学んだころは、下の書籍を参考にしました。
というか、もろにプログラムが載ってます。
安居院猛,長尾智晴,
「ジェネティックアルゴリズム」
昭晃堂,1993
さて、GAを実際に使うためには、
あらかじめ考えなくてはならないことがあります。
一つは解(ご質問の例では「○」)をどう染色体にコーディングするか、
もう一つは、適応度関数をどのように設定するか、です。
まずコーディングですが、一般的に数値を解として求めたい場合は、
2進数や、グレイコード(興味があったら調べて下さい)を染色体で表現します。
染色体での表現は、染色体長の二進ビット列ですが、
何も考えず整数を表現するのではなく、
たとえば染色体で表現された整数を100で割ったりすれば、
100分の1の精度で小数を表現することができます。
精度と定義域から染色体長とコーディング方法を決めるとよいですね。
次に適応度関数ですが、これは求めたい解が最大適応度になるような関数にします。
例の問題であれば、たとえば
f = 1 ÷ ( | 12 - 3x○ | + α )
とかなんとかすると、○が4のときにfが最大になりますね。
このような決め事を経て、いよいよプログラミングをするわけですが、
これは#1の方のご回答が適当と思われますので、割愛します。
上で書いた適応度は最適解のとき最大になりますので、
ルーレット選択の方法が#1の方の説明と異なりますから、
一応アルゴリズムを簡単に説明しておくと、
全個体の適応度の総和Sを求め、0~Sの乱数Rを発生させ、
個体番号(たとえば配列の要素番号)順の累積和と比較し、
Rが初めて累積和を下回ったときの番号の個体を選択します。
この方法で2つの個体を選択すれば交叉や突然変異によって新しい個体を生成することができます。
そして、個体数だけの個体を生成したところで世代交代になります。
No.1
- 回答日時:
はじめまして。
私は以前に遺伝的アルゴリズムを
若干やっていたものです。
私も似たような課題プログラムをC言語で作成しました。
そのときはX^2の(0<x<10)での最大値を求める課題でした。
基本的には、アルゴリズムは変わらないはずです。
#define G_SIZE 8 //遺伝子配列のサイズ
struct Gene { //遺伝子の構造体
int binary[G_SIZE]; //遺伝子(0、1の値)
int x; //遺伝子から生成される変数x
int result; //実際の計算結果(3×X)
int value; //評価値
}
と以上の様に宣言してみます。
ここでは、遺伝子=3×○の○の値としています。
binaryは遺伝子を2進数の配列と仮定しています。
これを十進数に直したのがメンバ変数のXです。
resultは実際に3×Xの計算結果です。
上での構造体(遺伝子)を乱数など用いて幾つも生成していき
そこから遺伝的アルゴリズムの流れを適用します。
必要とされる関数としては、
実際に掛け算をする関数(1)、
掛け算の結果からその遺伝子が解に近いかを評価する関数(2)、
遺伝子を淘汰させる関数(3)、
遺伝子を交叉さえる関数(4)、
突然変異をさせる関数(5)、
以上が必要です。(主な流れはmain()内で作成)
(1)は簡単です。(関数化する必要も無い様に思われますが流れを見易くするため)
(2)は、理想とする解を
#define ID_VALUE 12 //Ideal Value(理想的な値)
として、12にどれだけ近いかを評価値とすれば良いと思います。
例えば
int value_as( int a ) { //評価関数
int res; //返り値
res = ID_VALUE - a; //理想的な値との差を取る
if ( res < 0 ) res = (-1)*res; //値を正の値にする
return res;
}
以上の様なのはどうでしょうか?
GAが最適解を取りえるかを左右する部分でもありますが、
簡単な問題なのでこの程度がちょうど良いかと思います。
(3)はルーレット法を用いてはどうでしょうか。
(私はそれしか知らないんです。すいません)
ルーレット法はご存知かと思いますが、
この方法は全体の評価値の中で、その遺伝子がどれだけの割合を占めているかで
次の世代への生存確率を決定するものです。
大学の課題ということなので、ここはヒントを書き加えるのみにさせて頂きます。
そのほうが質問者のこらからのプログラミング技術向上のためかと思います。
○流れ
(1)全体の評価値の総和をとる(ルーレットの作成)
(2)遺伝子毎の範囲を記録(ルーレット盤上で占める範囲)
(3)乱数をとる(ルーレットに当てる矢)(ダーツをイメージして下さい)
(4)何回か(1)~(3)を繰り返す。(繰り返しの回数は定数か乱数で決定)
(5)矢の当たった遺伝子を削除(淘汰)
以上のでプログラムが書けるのではないでしょうか?
(4)の交叉の関数も然程難しくはありません。
乱数を用いて交叉する遺伝子の組を決定し、
配列binaryのどの部分を入れ替えるかを乱数で決定します。
(一点交叉の場合。多点交叉の場合は乱数で範囲を決定すれば出来ます。)
(5)でも同様に、
乱数を用いて突然変異をするかを決定し、
配列binaryのどの部分の値を変えるかを乱数で決めます。
そして、(1)から(5)までの行程を複数回行い終了決定条件に至ったら
終了させます。
終了決定条件は自分で考えてみてください。
例えば、
遺伝子全部が同じ値になったらそれを解みなして終了、とか
この終了決定条件も遺伝子数などに左右され、最適解を出すかという部分にも
色々と影響してきます。
ここを変えることで解への収束速度が変わる訳です。
(実際には突然変異、交叉をさせる確立と評価関数の方が影響は大きい)
以上で参考になれば幸いです。
課題頑張ってください。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・14歳の自分に衝撃の事実を告げてください
- ・架空の映画のネタバレレビュー
- ・「お昼の放送」の思い出
- ・昨日見た夢を教えて下さい
- ・【お題】絵本のタイトル
- ・【大喜利】世界最古のコンビニについて知ってる事を教えてください【投稿~10/10(木)】
- ・メモのコツを教えてください!
- ・CDの保有枚数を教えてください
- ・ホテルを選ぶとき、これだけは譲れない条件TOP3は?
- ・家・車以外で、人生で一番奮発した買い物
- ・人生最悪の忘れ物
- ・【コナン30周年】嘘でしょ!?と思った○○周年を教えて【ハルヒ20周年】
- ・ハマっている「お菓子」を教えて!
- ・最近、いつ泣きましたか?
- ・夏が終わったと感じる瞬間って、どんな時?
- ・10秒目をつむったら…
- ・人生のプチ美学を教えてください!!
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・都道府県穴埋めゲーム
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
匂いに相性があるって本当です...
-
『細胞の中に奇妙な構造の現れ...
-
ヨウ素って臭いありますか? フ...
-
合板から発する臭いについて
-
一重の目の旦那さんと二重の目...
-
夜の顕微鏡の短歌の表現技法を...
-
中国って遺伝子改良された人間...
-
匂いをかぐではなく、「匂う」?
-
蟻はどうやって食べ物を探知し...
-
皆さんが尊敬する「科学者(物...
-
側抑制の仕組みがよくわかりま...
-
唾液って乾くとなぜ皆くさいん...
-
^^v 血液型O型の人はニオイを...
-
いちじくの匂いって、人によっ...
-
なぜ、おなかの中の赤ちゃんは...
-
【医学・細胞分裂後の細胞の移...
-
クローン技術を使って臓器だけ...
-
「様」と「さん」の使い分けの...
-
ボカシ肥料の匂い
-
遊離アミノ酸とアミノ酸の違い
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
合板から発する臭いについて
-
中国って遺伝子改良された人間...
-
『細胞の中に奇妙な構造の現れ...
-
いちじくの匂いって、人によっ...
-
一重の目の旦那さんと二重の目...
-
匂いに相性があるって本当です...
-
ヨウ素って臭いありますか? フ...
-
ボカシ肥料の匂い
-
√242は、簡単にできますか? (...
-
劣性の遺伝子(悪いところ・欠...
-
不衛生な食べ物は、加熱すれば...
-
葉緑体って全部の植物にありま...
-
夜の顕微鏡の短歌の表現技法を...
-
サウナ好きはガンになりにくい...
-
テレゴニーについて
-
側抑制の仕組みがよくわかりま...
-
匂いをかぐではなく、「匂う」?
-
日本人で耳たぶがない人や朝鮮...
-
「マッチの匂いについて」
-
中2理科生物の植物の細胞につい...
おすすめ情報