7

A、B1、B2、C1、C2 の 5 つの変数がある最適化問題があります。これらの 5 つの変数を最適化して、できる限り最小の二乗和平方根値を取得しようとしています。うまく機能している最適化手法がいくつかありますが、特にこれは問題を引き起こしています。

変数を変更する 32 のオプションすべてを調査し、最小の RSS 値を選択したいと考えています。これが意味することは、各変数が +/- 増分のいずれかであるということです。そして、それぞれの選択肢からさらに 2 つの選択肢が生まれ、5 つの変数で 32 の選択肢があります。( 2^5 )

明確にするために、私は自分の変数を追加しているのではなく、A、B1、B2 などを互いに追加していません。それらを任意の量だけインクリメント/デクリメントしています。A +/- X、B1+/- X2 など。そして、5 つの変数の増分/減分のどの組み合わせが最小の 2 乗和平方根値を返すかを把握しようとしています。

                                   A
                                 +/ \-
                                B1   B1
                               +/\- +/\-
                              B2 B2 B2 B2

5つのレベルすべてが完了するまで、これを繰り返します。これを解決するためにどこから始めればよいかさえわかりません。これを格納するには、どのようなデータ構造が最適でしょうか? それは反復的な解決策ですか、それとも再帰的な解決策ですか。問題に対する答えは必要ありません。むしろ、どこかを調べたり、どこかから始めたりする必要があります。この度はご覧いただきありがとうございます。

さらなる混乱を明確にするために、これが私の最適化方法です。5 つの変数と 5 つのインクリメントがあり、各インクリメントは変数に一致します。(a,b,c,d,e,f) ---> (incA, incB, incC, indD, incE, incF)

+/- incX から X ( x は 5 つの変数の 1 つ) の最適な組み合わせを見つけたいと思います。つまり、解決策は次のようになります: a+incA 、 B-incB 、 c+incC 、 d+incD 、 e+ incE、f-incF。組み合わせには 32 の可能性があります。以下のすべての回答を読んだ後、この可能なアルゴリズムに落ち着きました。（以下の私の回答を参照してください）必要に応じて編集や質問をしてください。これは完璧なアルゴリズムではありません。明確化と理解を容易にするためのものです。要約できることはわかっています。

//Settign all possible solutions to be iterated through later.
double[] levelA = new double[2];
double[] levelB = new double[2];
double[] levelC = new double[2];
double[] levelD = new double[2];
double[] levelE = new double[2];

levelA[0] = a + incA;
levelA[1] = a - incA;
levelB[0] = b + incB;
levelB[1] = b - incB;
levelC[0] = c + incC;
levelC[1] = c - incC;
levelD[0] = d + incD;
levelD[1] = d - incD;
levelE[0] = e + incE;
levelE[1] = e - incE;

double[] rootSumAnswers = new double[32];
int count = 0;

for(int i = 0; i < 2; i ++)
{
    for(int k = 0; k < 2; k++)
    {
        for(int j = 0; j < 2; j ++)
        {
            for(int n = 0; n < 2; n++)
            {
                for(int m = 0; m < 2; m++)
                {
                    rootSumAnswers[count++] = calcRootSum(levelA[i], levelB[k], levelC[j], levelD[n], levelE[m]);

                }
            }
        }
    }
}

//Finally, i find the minimum of my root sum squares and make that change permanent, and do this again.
4

4 に答える 4

3

次の関数を使用して、すべての可能な操作のセット ({-,-,-,-}、{-、-、-、+}、{-、-、+、-} など) を含むセットを生成できます。 true と false が + と - を表す bool 配列のリストを出力します。varsパラメータは、結合される変数の数を示します。5つの変数の場合、5つの変数を組み合わせるときに4つの演算子しかないため（最初の変数を否定できないと仮定して）、16の組み合わせしかないことに注意してください（あなたが述べたように32ではありません）：

public List<bool[]> GetOperators(int vars)
{
    var result = new List<bool[]>();

    for (var i = 0; i < 1 << vars-1; i++)
    {
        var item = new bool[vars - 1];
        for (var j = 0; j < vars-1; j++)
        {
            item[j] = ((i >> j) & 1) != 0;
        }
        result.Add(item);
    }
    return result;
}

このリストを取得したら、それを使用して、可能なすべての方法で変数を組み合わせることができます。最初に、一連の変数と単一のbool[]組み合わせを取得して適用するヘルパー関数を定義します (渡された変数の数の組み合わせに正しい数の要素があると想定しています)。

private double Combine(double[] vars, bool[] combination)
{
    var sum = vars[0];
    for (var i = 1; i< vars.Length; i++)
    {
        sum = combination[i - 1] ? sum + vars[i] : sum - vars[i];
    }
    return sum;
}

次を使用して、組み合わせを適切にフォーマットすることもできます。

private string FormatCombination(double[] vars, bool[] combination)
{
    var result = vars[0].ToString("0.00##");
    for (var i = 1; i < vars.Length; i++)
    {
        result = string.Format("{0} {1} {2:0.00##}", result, combination[i - 1] ? "+" : "-", vars[i]);
    }
    return result;
}

すべてをまとめて、考えられるすべての組み合わせをテストします。

var vars = new []
{
    1.23, // A
    0.02, // B1
    0.11, // B2
    0.05, // C1
    1.26  // C2
};

foreach (var combination in GetOperators(vars.Length))
{
    var combined = Combine(vars, combination);

    // Perform your operations on "combined" here...

    Console.WriteLine("{0} = {1}", FormatCombination(vars, combination), combined);
}

これは出力されます：

1.23 - 0.02 - 0.11 - 0.05 - 1.26 = -0.21
1.23 + 0.02 - 0.11 - 0.05 - 1.26 = -0.17
1.23 - 0.02 + 0.11 - 0.05 - 1.26 = 0.01
1.23 + 0.02 + 0.11 - 0.05 - 1.26 = 0.05
1.23 - 0.02 - 0.11 + 0.05 - 1.26 = -0.11
1.23 + 0.02 - 0.11 + 0.05 - 1.26 = -0.07
1.23 - 0.02 + 0.11 + 0.05 - 1.26 = 0.11
1.23 + 0.02 + 0.11 + 0.05 - 1.26 = 0.15
1.23 - 0.02 - 0.11 - 0.05 + 1.26 = 2.31
1.23 + 0.02 - 0.11 - 0.05 + 1.26 = 2.35
1.23 - 0.02 + 0.11 - 0.05 + 1.26 = 2.53
1.23 + 0.02 + 0.11 - 0.05 + 1.26 = 2.57
1.23 - 0.02 - 0.11 + 0.05 + 1.26 = 2.41
1.23 + 0.02 - 0.11 + 0.05 + 1.26 = 2.45
1.23 - 0.02 + 0.11 + 0.05 + 1.26 = 2.63
1.23 + 0.02 + 0.11 + 0.05 + 1.26 = 2.67

編集：

あなたの質問への変更により、回答を更新しました。他の人が述べたように、このような完全な検索を使用する必要はないかもしれませんが、とにかくこの方法が役立つ場合があります。

GetOperators()(以前のように2 n-1ではなく) 2 nの組み合わせを返すようにわずかに変更します。

public List<bool[]> GetOperators(int vars)
{
    var result = new List<bool[]>();

    for (var i = 0; i < 1 << vars; i++)
    {
        var item = new bool[vars];
        for (var j = 0; j < vars; j++)
        {
            item[j] = ((i >> j) & 1) != 0;
        }
        result.Add(item);
    }
    return result;
}

メソッドは、Combine()使用される変数と組み合わせに加えて一連のインクリメントを取るように変更されます。組み合わせの各要素について、 の場合trueは増分が変数に追加され、 false の場合は減算されます。

private double[] Combine(double[] vars, double[] increments, bool[] combination)
{
    // Assuming here that vars, increments and combination all have the same number of elements
    var result = new double[vars.Length];
    for (var i = 0; i < vars.Length; i++)
    {
        result[i] = combination[i] ? vars[i] + increments[i] : vars[i] - increments[i];
    }

    // Returns an array of the vars and increments combined per the given combination
    // E.g. if there are 5 vars and the combination is: {true, false, true, true, false}
    // The result will be {var1 + inc1, var2 - inc2, var3 + inc3, var4 + inc4, var 5 - inc5}
    return result;
}

またFormatCombination()、新しい組み合わせスタイルを表示するように更新されます。

private string FormatCombination(double[] vars, double[] increments, bool[] combination)
{
    var result = new List<string>(vars.Length);

    var combined = Combine(vars, increments, combination);

    for (var i = 0; i < vars.Length; i++)
    {
        result.Add(string.Format("{0:0.00##} {1} {2:0.00##} = {3:0.00##}", vars[i], combination[i] ? "+" : "-", increments[i], combined[i]));
    }
    return string.Join(", ", result.ToArray());
}

すべてを一緒に入れて：

var vars = new[]
{
    1.23, // A
    0.02, // B
    0.11, // C
    0.05, // D
    1.26, // E
};

var increments = new[]
{
    0.04, // incA
    0.11, // incB
    0.01, // incC
    0.37, // incD
    0.85, // incD
};

foreach (var combination in GetOperators(vars.Length))
{
    var combined = Combine(vars, increments, combination);

    // Perform operation on combined here...

    Console.WriteLine(FormatCombination(vars, increments, combination));
}

出力 (要約):

1.23 - 0.04 = 1.19、0.02 - 0.11 = -0.09、0.11 - 0.01 = 0.10、0.05 - 0.37 = -0.32、1.26 - 0.85 = 0.41
1.23 + 0.04 = 1.27、0.02 - 0.11 = -0.09、0.11 - 0.01 = 0.10、0.05 - 0.37 = -0.32、1.26 - 0.85 = 0.41
1.23 - 0.04 = 1.19、0.02 + 0.11 = 0.13、0.11 - 0.01 = 0.10、0.05 - 0.37 = -0.32、1.26 - 0.85 = 0.41
1.23 + 0.04 = 1.27、0.02 + 0.11 = 0.13、0.11 - 0.01 = 0.10、0.05 - 0.37 = -0.32、1.26 - 0.85 = 0.41
...
于 2012-10-05T16:51:44.710 に答える
1

最初の回答がc＃ではなく擬似コードであるため削除されたため...抽象セットをスタックに変更しました...

優れた再帰的アプローチが機能すると思います。

int FindBest(int increment, Stack<int> decided_vars, Stack<int> free_vars)
{
  if free_vars.size() == 0
  {
     return PerformCalculation(decided_vars);
  }

  int new_element = free_vars.Pop()
  new_element += increment;

  //check one case
  decided_vars.Push(new_element)
  int result1 = FindBest(increment, decided_vars, free_vars)

  //reset sets for second case
  decided_vars.Pop();
  new_element -= 2 * increment;
  decicded_vars.Push(new_element);
  int result2 = FindBest(increment, decided_vars, free_vars);

  //reset sets as they were to give back to parent
  decided_vars.Pop()
  free_vars.Push( new_element + increment )

  return max(result1, result2);
}

PerformCalculationは、最大化/最小化する関数として定義できます。

于 2012-10-05T17:36:13.063 に答える
1

現在のバージョンの質問への回答

ここでは、検索を行う必要はまったくありません。各変数について、A +/- incA絶対値が最小になる符号 (+ または -) を選択します (つまり、 の最小二乗を生成する符号A +/- inc A)。これにより、平方和のすべての項が最小化されるため、合計が最小化されます。

前の回答

sqrt(A*A +/- B1*B1 +/- B2*B2 +/- C1*C1 +/- C2*C2)適切な記号+またはを選択して最小化したい場合-、32 の可能な組み合わせを単純に反復し、最小の結果が得られるものを選択します。すべての組み合わせを反復するには、整数 0 から 31 を反復し、それらのバイナリ表現を調べると、5 つのゼロと 1 のすべての組み合わせが見つかることに注意してください。さらに、特定の整数 n が 2 進数 k で 1 を含むかどうかを調べることができることに注意してください。ビット単位の n と 2 の k 乗がゼロでないかどうかを確認するだけです。したがって、疑似コードでは、

min_sign_a = 1
min_sign_b1 = 1
min_sign_b2 = 1
min_sign_c1 = 1
min_sign_c2 = 1
min_sum = a*a + b1*b1 + b2*b2 + c1*c1 + c2*c2
for(i in 1,...,31)
  sign_a = (i & 1) ? -1 : 1
  sign_b1 = (i & 2) ? -1 : 1
  sign_b2 = (i & 4) ? -1 : 1
  sign_c1 = (i & 8) ? -1 : 1
  sign_c2 = (i & 16) ? -1 : 1
  sum = sign_a*a*a + sign_b1*b1*b1 + sign_b2*b2*b2 + sign_c1*c1*c1 + sign_c2*c2*c2
  if (sum < min_sum)
    min_sign_a = sign_a
    min_sign_b1 = sign_b1
    min_sign_b2 = sign_b2
    min_sign_c1 = sign_c1
    min_sign_c2 = sign_c2
  end
end

ここで、"&" は bitwise-and を表します。i の k 番目のビットの 1 は、k 番目の変数に負の符号を与え、0 はそれに正の符号を与えます。min_sum「i = 0」の場合、つまり、ループの最初の実行で初期化されないことに対処する必要がないように、ループの開始前に処理されるようにすべての符号が正です。

于 2012-10-05T16:51:13.320 に答える
1

いくつかのパラメータを最適化する良い方法は、Nelder–Mead 法または Downhill Simplex 法です。すべての順列をテストすることなく、非常に自然な方法でパラメーター空間を「ウォーク」します。ダウンヒルシンプレックス法も参照してください（原理を示す優れたグラフィックス付き）。

C#のコードも見つけました。しかし、私はそれをテストしませんでした。

于 2012-10-05T17:55:42.333 に答える