3

私は次のような関数を持っています:f(x) = min(f_1(x_1), ..., f_n(x_n))ここでnは約 10 で、すべてf_iが正の単調で滑らかであり、それらの値はほとんどの場合 (すべてx_iの場合f_i) は 10 倍未満の差です。そのため、分析にはかなり適しているようです。
そのような制約を持ってそれを最大化するための最良の（高速な？）方法は何ですか：
-すべてx_i整数であり、〜100未満です-すべて
の積はx_i指定された値の近くにある必要があります（それから10％以内であると仮定します）

任意の言語でのアルゴリズムの説明は歓迎されますが、Python である場合は 10 倍優れています :)

PS:以前、私は遺伝的アルゴリズムを扱ったことがあり、最初にこのタスクに適用しました。しかし、それは最良の選択ではないようです。GA は非常に遅く、また、この問題に対する効率的なクロスオーバー操作を思いつきませんでした。

4

1 に答える 1

1

開始点をランダムに選択し、各関数 f_i を各入力 x_i で評価し、最小入力を決定し、最低の結果を与えた関数の入力をインクリメントするよりも優れた解決策はすぐにはわかりません。エレガントではなく、複雑でもありませんが、ベースラインのブルート フォース アプローチとしては優れています。

int (**f_is)(int n);

//...

int xs[10];

//...

while(true) {
    int i = 0;

    int cmin = f_is[0](i);
    int cminIndex = 0;

    for(i = 1; i < 10; ++i) {
        int cfunc = (f_is[i])(i);

        if(cmin < cfunc) {
            cmin = cfunc;
            cminIndex = i;
        }
    }

    ++xs[cminIndex];
}

編集:さらにいくつか: f_i(n_i) を並列に計算し、結合して最小値を取ると、はるかに高速になりますが、最小値を生成した関数のインデックスを通信する方法が必要です呼び出し元に。Haskellは Python よりもはるかに高速であり、場合によっては多大な労力を費やすことなく優れた同時実行サポートを取得できるため、これを記述する優れた言語として Haskell をお勧めします。

于 2012-08-11T22:38:10.213 に答える