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

質問

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

回答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のどの部分の値を変えるかを乱数で決めます。
そして、（１）から（５）までの行程を複数回行い終了決定条件に至ったら
終了させます。
終了決定条件は自分で考えてみてください。
例えば、
　遺伝子全部が同じ値になったらそれを解みなして終了、とか
この終了決定条件も遺伝子数などに左右され、最適解を出すかという部分にも
色々と影響してきます。
ここを変えることで解への収束速度が変わる訳です。
（実際には突然変異、交叉をさせる確立と評価関数の方が影響は大きい）

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