ＧＡ(遺伝的アルゴリズム)を教えてください！

質問

はじめまして。
先日、大学でＧＡ（遺伝的アルゴリズム）を使って
簡単な掛け算の（例えば、３×○＝１２で○の中に当てはまる
数字を導き出す）問題を解いてくるようにと課題がありました。
しかし、ＧＡに関しては基本的な用語（交叉や突然変異など）を
教わったのみでプログラムが全然分かりません。
自分でも色々調べてみたのですが、全く参考になりそうなものが
見つかりませんでした。
そこで、もしご存知の方がいらっしゃるなら教えていただけないでしょうか？
プログラムを組む場合にはＣ言語（Ｃ自体も使ったことがありません・・・。）
を使うことになるのですが、できればＭＡＴＬＡＢを使いたいと思っています。
もちろんＣ言語でも構いませんので、よろしくお願いします！

回答No.3

republiky

質問が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の流れです。もちろん、ここ
で述べたことはあくまでイメージとして捉えるための
ものなので、詳細は専門書を読まれることをお勧め
します。私が講義で使ってるのは、萩原将文著「遺伝的アルゴリズム（朝倉書店）」です。最初の１，２章
を理解しておけば、概要を掴むには十分かと思います。

回答No.2

k-841

GAを初めて学んだころは、下の書籍を参考にしました。
というか、もろにプログラムが載ってます。

安居院猛,長尾智晴,
「ジェネティックアルゴリズム」
昭晃堂,1993

さて、GAを実際に使うためには、
あらかじめ考えなくてはならないことがあります。
一つは解(ご質問の例では「○」)をどう染色体にコーディングするか、
もう一つは、適応度関数をどのように設定するか、です。

まずコーディングですが、一般的に数値を解として求めたい場合は、
2進数や、グレイコード(興味があったら調べて下さい)を染色体で表現します。
染色体での表現は、染色体長の二進ビット列ですが、
何も考えず整数を表現するのではなく、
たとえば染色体で表現された整数を100で割ったりすれば、
100分の1の精度で小数を表現することができます。
精度と定義域から染色体長とコーディング方法を決めるとよいですね。

次に適応度関数ですが、これは求めたい解が最大適応度になるような関数にします。
例の問題であれば、たとえば
f = 1 ÷ ( | 12 - 3x○ | + α )
とかなんとかすると、○が4のときにfが最大になりますね。

このような決め事を経て、いよいよプログラミングをするわけですが、
これは#1の方のご回答が適当と思われますので、割愛します。
上で書いた適応度は最適解のとき最大になりますので、
ルーレット選択の方法が#1の方の説明と異なりますから、
一応アルゴリズムを簡単に説明しておくと、
全個体の適応度の総和Sを求め、0～Sの乱数Rを発生させ、
個体番号(たとえば配列の要素番号)順の累積和と比較し、
Rが初めて累積和を下回ったときの番号の個体を選択します。
この方法で2つの個体を選択すれば交叉や突然変異によって新しい個体を生成することができます。
そして、個体数だけの個体を生成したところで世代交代になります。

回答No.1

satoryu

はじめまして。
私は以前に遺伝的アルゴリズムを
若干やっていたものです。
私も似たような課題プログラムをＣ言語で作成しました。
そのときはＸ^２の（０＜ｘ＜１０）での最大値を求める課題でした。
基本的には、アルゴリズムは変わらないはずです。

#define G_SIZE 8 //遺伝子配列のサイズ

struct Gene { //遺伝子の構造体
int binary[G_SIZE]; //遺伝子(０、１の値)
int x; //遺伝子から生成される変数x
int result; //実際の計算結果（３×Ｘ）
int value; //評価値
}

と以上の様に宣言してみます。
ここでは、遺伝子＝３×○の○の値としています。
binaryは遺伝子を２進数の配列と仮定しています。
これを十進数に直したのがメンバ変数のＸです。
resultは実際に３×Ｘの計算結果です。
上での構造体（遺伝子）を乱数など用いて幾つも生成していき
そこから遺伝的アルゴリズムの流れを適用します。
必要とされる関数としては、
実際に掛け算をする関数(１)、
掛け算の結果からその遺伝子が解に近いかを評価する関数(２)、
遺伝子を淘汰させる関数(３)、
遺伝子を交叉さえる関数(４)、
突然変異をさせる関数(５)、
以上が必要です。（主な流れはmain()内で作成）
(１)は簡単です。（関数化する必要も無い様に思われますが流れを見易くするため)
(２)は、理想とする解を
#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;
}
以上の様なのはどうでしょうか？
ＧＡが最適解を取りえるかを左右する部分でもありますが、
簡単な問題なのでこの程度がちょうど良いかと思います。
(３）はルーレット法を用いてはどうでしょうか。
（私はそれしか知らないんです。すいません）
ルーレット法はご存知かと思いますが、
この方法は全体の評価値の中で、その遺伝子がどれだけの割合を占めているかで
次の世代への生存確率を決定するものです。
大学の課題ということなので、ここはヒントを書き加えるのみにさせて頂きます。
そのほうが質問者のこらからのプログラミング技術向上のためかと思います。
○流れ
　(1)全体の評価値の総和をとる（ルーレットの作成）
　(2)遺伝子毎の範囲を記録（ルーレット盤上で占める範囲）
　(3)乱数をとる（ルーレットに当てる矢）（ダーツをイメージして下さい）
　(4)何回か(1)～(3)を繰り返す。（繰り返しの回数は定数か乱数で決定）
　(5)矢の当たった遺伝子を削除（淘汰）
以上のでプログラムが書けるのではないでしょうか？
(４)の交叉の関数も然程難しくはありません。
乱数を用いて交叉する遺伝子の組を決定し、
配列binaryのどの部分を入れ替えるかを乱数で決定します。
（一点交叉の場合。多点交叉の場合は乱数で範囲を決定すれば出来ます。）
(５)でも同様に、
乱数を用いて突然変異をするかを決定し、
配列binaryのどの部分の値を変えるかを乱数で決めます。
そして、（１）から（５）までの行程を複数回行い終了決定条件に至ったら
終了させます。
終了決定条件は自分で考えてみてください。
例えば、
　遺伝子全部が同じ値になったらそれを解みなして終了、とか
この終了決定条件も遺伝子数などに左右され、最適解を出すかという部分にも
色々と影響してきます。
ここを変えることで解への収束速度が変わる訳です。
（実際には突然変異、交叉をさせる確立と評価関数の方が影響は大きい）

以上で参考になれば幸いです。
課題頑張ってください。