![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?8acaa2e)
遺伝的プログラミングで教えてください。
下記のような課題を考えています。
三個の正の整数 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点交叉法以外にお勧めが有りましたら、教えていただけないでしょうか。
A 回答 (3件)
- 最新から表示
- 回答順に表示
No.3
- 回答日時:
>変数が20、関数が20の場合でも~
質問の問題は#2さんも指摘されてますが、最適値がほぼ自明という、ものすごく簡単な問題なので、正直、どんなにアホな遺伝子の取り方ヲしても「うまく行ってしまう」でしょう。
もし、変数が増えたり、関数が複雑になったりすれば、全くそうは行きません。おそらく一点交叉ではうまく行かないでしょう。
個人的には(オリジナルの)遺伝的アルゴリズムは、あんまり性能の良い最適化アルゴリズムとは思わないので(特に連続変数の最適化では)、もし、遺伝的アルゴリズムを使うこと自体が目的ではなくて、最適化することが目的であるなら別のアルゴリズムを試してみることをおすすめします。
個人的には、連続変数の最適化(とくに制約が緩いor簡単に無制約に帰着できる場合)では、
Differentilal Evolution
というアルゴリズム(広い意味では遺伝的アルゴリズムの一種です)が良いと思います。単純なアルゴリズムですが、各種のベンチマークなんかでは相当に優秀な結果がでています。
No.2
- 回答日時:
式を一目見れば、コタエは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
- 回答日時:
制約付きの最適化で、制約をどのように入れるのがよいかを考えることは、それ自体がものすごく困難な問題です。
また、遺伝的アルゴリズムは、交叉のさせ方に性能の良し悪しが決まって今います。
どんな、方法がよいかは問題毎に異なっていて、汎用的に有効な方法はないです。
ただ、質問の問題について言えば、目的関数や制約がかなり簡単なので、おそらく、どんな方法でやってもそれなりにうまくいく(うまくいってしまう)と思います。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 「FFTの基本は、DFTはサンプル数Nが偶数なら 2つのDFTに分解できるということ。 分解するとD 3 2022/03/31 21:01
- Java Java モンスターブリーダー 1 2023/02/05 09:44
- Excel(エクセル) Excel2007での条件付き書式について 6 2023/05/02 10:56
- 生物学 エンドウを材料として、 種子の形と葉の色の形質について、遺伝の実験を行った。これらの形質に関する遺伝 1 2023/06/14 21:55
- 物理学 共鳴箱の代わりの言葉 3 2023/05/30 07:58
- C言語・C++・C# C言語 3 2022/10/04 15:07
- Visual Basic(VBA) 列と行の名前(重複あり)が交差するセルに、データを入力したい 2 2022/06/25 22:42
- Excel(エクセル) SUMIFのIF分岐について 4 2023/04/15 12:57
- 数学 場合の数、確率 43 図形 三角形の個数 2 2023/07/26 07:27
- Excel(エクセル) 隣り合っていないセルを まとめて税込表示したい 8 2022/09/25 14:32
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
プラスとマイナスが入った比率...
-
私は大学一年なのですが、大学...
-
三角関数の最大値・最小値につ...
-
数学の記号
-
ラグランジュの未定乗数法について
-
非線形偏微分方程式についてです。
-
遺伝的プログラム 制約
-
積分のくくりだし
-
ミクロ経済学
-
3000円が3割なら10割はいくらで...
-
「日常生活における数列」とは...
-
10の-9乗ってどういう意味ですか?
-
確率の問題で、「5人の中から3...
-
【 数A 場合の数 】 問題 10円...
-
x1=(1,1,1),x2=(1,1,-1),x3=(1,...
-
ナッシュ交渉解の求め方を教え...
-
シグマなど文字を含んだままで...
-
国の予算原則について質問です...
-
ばらつきの掛け算
-
日本の風俗嬢人口って10万人超...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報