遺伝的プログラム 制約

質問

遺伝的プログラミングで教えてください。
下記のような課題を考えています。

三個の正の整数　A,B,Cが有ります。A+B+C の合計は　5000

下記のF1 + F2 + F3 の合計を最小となる様な　A,B,C を導きたい。
F1=(1/25000 x (A-500)^2+100) x A
F2=(1/25000 x (B-1500)^2+75) x B
F3=(1/25000 x (C-3000)^2+50) x C

AとBとCは16bitの2進数にして、48bitの固まりにして、1 点交叉法　で48bitの途中で入れ替え様と思っています。

A,B,Cの合計が常に5000となるようにした場合、1点交叉法　だと5000とならなくなるので、AとBの合計から5000を引いてCを導こうと思っていますが、その場合でも 交差後に5000を超える場合は、交叉やり直せば良いのでしょうか。

また1点交叉法以外にお勧めが有りましたら、教えていただけないでしょうか。

回答No.3

rabbit_cat

>変数が20、関数が20の場合でも～
質問の問題は#2さんも指摘されてますが、最適値がほぼ自明という、ものすごく簡単な問題なので、正直、どんなにアホな遺伝子の取り方ヲしても「うまく行ってしまう」でしょう。

もし、変数が増えたり、関数が複雑になったりすれば、全くそうは行きません。おそらく一点交叉ではうまく行かないでしょう。
個人的には（オリジナルの）遺伝的アルゴリズムは、あんまり性能の良い最適化アルゴリズムとは思わないので（特に連続変数の最適化では）、もし、遺伝的アルゴリズムを使うこと自体が目的ではなくて、最適化することが目的であるなら別のアルゴリズムを試してみることをおすすめします。
個人的には、連続変数の最適化（とくに制約が緩いor簡単に無制約に帰着できる場合）では、
Differentilal Evolution
というアルゴリズム（広い意味では遺伝的アルゴリズムの一種です）が良いと思います。単純なアルゴリズムですが、各種のベンチマークなんかでは相当に優秀な結果がでています。

回答No.2

stomachman

式を一目見れば、コタエはA=4998, B=C=1、って分かっちゃうでしょ。

　たとえ、わざと探索で解いてみせるデモンストレーションなのだとしても、評価関数F=F1+F2+F3はA, B, Cで簡単に偏微分できるのだし、整数だという事以外の制約条件 (A≧1, B≧1, C≧1, A+B+C = 5000) はラグランジュの未定乗数法に素直に乗る。だから、最低の手抜きでも最急降下法を使わない理由がない。しかも、この問題には局所最適解なんかないので、どこからスタートしても確実に最適解に行き着く。

　という訳で、この問題を解くのに遺伝的アルゴリズムを使おうというセンスがおかしい。あるいは、これが遺伝的アルゴリズムの演習だとするなら、出題のセンスがおかしい。いずれにしても、やればやるほどセンスやイロイロが鈍くなっちゃいそうな、とても悪趣味な話です。

　悪趣味を承知で遺伝的アルゴリズムを使うにしたって、局所最適解がないんだから、多数の個体を維持する必要はなく、優勝者だけから次世代を生成すれば宜しい。つまり交叉には意味がなくて、単に優勝者のゲノムに点突然変異をひとつ加えたものを全種類作って（種類がbit数のぶんだけしかないから、全部作らない理由がない）、次の優勝者を選ぶ、ということを繰り返すだけで良い。
　こんな問題に使っても、遺伝的アルゴリズムならではの特長というものが全く現れない。やっぱり悪趣味。

　なお、制約条件については、A+B+Cが5000になるように規格化すればよろしい。A, B, Cの大きさを指定する遺伝子をそれぞれa, b, cとして、
　　A = 5000 a / (a+b+c)の四捨五入
　　B = 5000 b / (a+b+c)の四捨五入
　　C = 5000 - A - B
として競争させるんでもいいが、これだとa, b, cが際限なく大きくなってオーバーフローすることもありうる。そこでもう一工夫するなら、（ま、要するに効率よくいろいろぐちゃぐちゃいじる、ということさえやればいいんだから、多少手を加えたって構わない）新しいゲノムを作る作業の最後の仕上げとしてこの式を使って、a, b, cを規格化された値A, B, Cに書き換えてしまえばいいでしょ。そうすれば、全てのゲノムは常にA+B+Cが5000になっているから。また、A, B, Cのどれかが0になった奴は即座に殺しとけ。

　ともあれ酷い話だな。

回答No.1

rabbit_cat

制約付きの最適化で、制約をどのように入れるのがよいかを考えることは、それ自体がものすごく困難な問題です。
また、遺伝的アルゴリズムは、交叉のさせ方に性能の良し悪しが決まって今います。
どんな、方法がよいかは問題毎に異なっていて、汎用的に有効な方法はないです。

ただ、質問の問題について言えば、目的関数や制約がかなり簡単なので、おそらく、どんな方法でやってもそれなりにうまくいく（うまくいってしまう）と思います。

補足

変数が20、関数が20の場合でも1 点交叉法で大丈夫でしょうか。
変数は正の整数で24bit程度に拡張する可能性があります。