遺伝的アルゴリズムの評価式に関する質問です。
膨大な数の組み合わせから正解の組み合わせを求めるという大規模組み合わせ問題があったとします。
このような問題を遺伝的アルゴリズムを用いて解こうとしているのですが、今用いている評価式より良いアイデアが自分では考えつかなかったため質問します。
以下、問題や用いている遺伝的アルゴリズムに関する詳しい説明です。
例えば、仮に、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になる、つまり正解の組み合わせが見つかれば、遺伝的アルゴリズムは終了する。
この評価式で遺伝的アルゴリズムを回しているのですが、この簡単な評価式では近似解に陥ったとき、解を求めるのがどうしても遅くなってしまいます。
全体的に長く、わかりにくい説明で申し訳ないのですが、この評価式の改善案、またはこの遺伝的アルゴリズムの改善案などがあれば教えていただきたいです。
以上、よろしくお願いします。
![その他([技術者向] コンピューター) イメージ](https://gazo.okwave.jp/okwave/spn/images/related_qa/c205_4_thumbnail_img_sm.png)
お礼
回答ありがとうございます。 私もGoogleでかなり調べたのですがなかなかいいサイトが見つからず質問させていただきました。 Knotopologさんは参考になる書籍はご存じないですか？