遺伝的アルゴリズムの評価式に関する質問です。

質問

膨大な数の組み合わせから正解の組み合わせを求めるという大規模組み合わせ問題があったとします。
このような問題を遺伝的アルゴリズムを用いて解こうとしているのですが、今用いている評価式より良いアイデアが自分では考えつかなかったため質問します。

以下、問題や用いている遺伝的アルゴリズムに関する詳しい説明です。

例えば、仮に、23, 21, 65, 78, 43, 78, 83, 56, 78 ,89　の10個の数の組み合わせがあるとき、
合計して109になる組み合わせ（23,21,65）を見つけたいという問題です。（正解の組み合わせは複数個あっても、一個見つかれば良い。また正解の組み合わせは必ずあるものとする。）

この問題を遺伝的アルゴリズム（GA）を使って解くとします。

以下、簡単なGAの説明です。
表現型に2進数ビット列を用いる。
個体数は200とし、初期個体はランダムで生成する。
評価式はf(x) = b/(b+|b-t|)(bは正解の組み合わせの合計値で、tは2進数ビット列で1を立てた場所の数の合計値である。)。終了条件はこの評価値がf(x)=1になることである。
交叉は一様交叉で突然変異も行う。

表現型について詳しく説明すると、
コード化に 0と 1の並びである2進数ビット列を用いて、 その場所に対応する数を加算する場合は1を, 逆に加算しない場合は0を遺伝子の表現型に立てビット列を生成しました。

例えば今回の正解の組み合わせ(109)を2進数ビットで表すと下のようになる。

23, 21, 65, 78, 43, 78, 83, 56, 78 ,89
1 1 1 0 0 0 0 0 0 0 ←2進数ビットを用いた表現型。

（1が立っている場所の数が加算されて合計で109となり、これが正解の組み合わせであることがわかる。）

そして、この遺伝的アルゴリズムの評価式を
f(x) = b/(b+|b-t|)
とします。(bは正解の組み合わせの合計値で、tはビット列で1を立てた場所に対応する数の合計値である。)
評価式f(x)=1になる、つまり正解の組み合わせが見つかれば、遺伝的アルゴリズムは終了する。

この評価式で遺伝的アルゴリズムを回しているのですが、この簡単な評価式では近似解に陥ったとき、解を求めるのがどうしても遅くなってしまいます。

全体的に長く、わかりにくい説明で申し訳ないのですが、この評価式の改善案、またはこの遺伝的アルゴリズムの改善案などがあれば教えていただきたいです。

以上、よろしくお願いします。

回答No.2

mpro-gram · ベストアンサー

どんなプログラムになってるのか解りにくいのですが、終了判定時に、floatデータと 1 とを == で比較してて、float 側の誤差のせいで、無限ループに陥ってるのかな？と思ったのだけれど、
評価式結果が0.0 から 1.0 までのfloatである必要があるなら、終了判定方法側を問題とすべきかと思います。

http://ipr20.cs.ehime-u.ac.jp/column/ga/chapter4.html
このサイトを参考に、ナップサック問題でプログラムしてみたけど、かなり近似までいってるものに、交叉や突然変異をかけると、おおむね遠ざかってしまうので、もっとも近い物は除外して交叉するとか、10世代いっても解が得られないなら、初期の組み合わせからやり直すなど、f(x)以外の部分のアルゴリズムもよく練らないと、常に素早くとはいかないようですね。
途中経過データを出力するなどして、ループ原因を探るのがよいでしょう。

回答No.1

mpro-gram

現象として「整数しか扱わないはずなのに、評価式にわり算が入ってるせいで、循環小数やら、無限小数が割り込んできて計算精度を下げている」だろうことは予想が付く。
わり算を使わないで、どう解くかを考えればよいのでは？
割って１かどうかならわり算しないで、分母と分子を直接等号比較しちゃえば、分母に0 が紛れ込んでも問題ない。そのわり算後の結果データを使ってさらなる計算しているわけでもなさそうだし
というか比較部分の問題だけなら、その式なら b==t なら真 true 値を返し、それ以外は偽 false を返す関数とすればよいような？
f(t) = b / (b+ |b-t|) →　f(t) = (b==t)?true:false

補足

mpro-gramさん

回答有難うございます。

すみません。説明するのを忘れていたのですが、
評価式で出た値をルーレット選択に利用しています。
つまり評価式f(x) = b/(b+|b-t|)の値が1（正解の組み合の値）に近いほどルーレット選択によって次世代の個体に残りやすくしています。

そして次世代の個体は、前の世代で評価値の高い個体を確率的に多く選択したものに、交叉や突然変異をして出来た個体になります。この処理を繰り返すことで答え（求める正解の組み合わせ）に近づきます。