How to iterate between 32 binary options?

Question

I have an optimization problem, where I have 5 variables: A, B1, B2, C1, C2. I am trying to optimize these 5 variables in order to get the smallest root squared I can. I have several optimization methods that work fine, but this in particular gives me some problems.

I want to study all 32 options for changing variables and select the lowest RSS value. I mean that every variable can be a +/- increment. And each choice leads to two more options, with 5 variables, which is 32 options. (2 ^ 5)

To clarify, I do not add my variables: A, B1, B2, etc. to each other, I increase / decrease them by an arbitrary amount. A +/- X, B1 +/- X2, etc. And I'm trying to figure out which increment / decrement combination of my 5 variables will return the smallest square root sum value.

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

So, and so on, until all 5 levels are completed. I don’t even know where to start trying to solve this problem. What data structure would be best for storing it? Is it an iterative or recursive solution. I do not need an answer to the problem, rather look somewhere or start somewhere. Thanks again for taking the time to look at this.

To clarify further confusion, this is my optimization method. I ahve 5 variables and 5 increments, each increment corresponds to a variable. (a, b, c, d, e, f) ---> (incA, incB, incC, indD, incE, incF)

I want to find the best combination of +/- incX for X (x is one of 5 variables), that is: the solution could be something like: a + incA, B-incB, c + incC, d + incD, e + incE f-incF. There are 32 possible combinations, after reading all the answers below, I settled on this possible algorithm. (see my answer below) make the necessary changes and questions. This is not an ideal algorithm, it is for clarification and ease of understanding, I know that it can be compressed.

 //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. 

Answer 1

You can create a set containing all possible sets of operations (for example, {-, -, -, -}, {-, -, -, +}, {-, -, +, -}, etc.) using the following function, which will list bool arrays, where true and false represent + and -. The vars parameter indicates the number of variables to combine. Please note that for 5 variables there are only 16 combinations (not 32, as you state), since there are 4 operators when combining 5 variables (if the first variable cannot be undone):

 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; } 

Once you have this list, you can use it to combine variables in all possible ways. First, we define a helper function that takes a set of variables and one combination of bool[] and applies it (it assumes that the number of combinations for the number of variables passed has the correct number of elements):

 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; } 

You can also format the combination beautifully using:

 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; } 

Putting it all together to check all possible combinations:

 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); } 

This will output:

  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 

---

Edit:

For changes to your question, I updated my answer. As already mentioned, it is not necessary to use a full search such as this, but you can still find a useful method.

GetOperators() changes slightly to return 2 ^n- combinations (and not 2 ^n-1 as before):

 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; } 

The Combine() method is modified to accept a set of increments in addition to the variables and combinations to be used. For each element of the combination, if it is true , the increment is added to the variable; if it is false, it is subtracted:

 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 // Eg 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; } 

And FormatCombination() also updated to display the new combination style:

 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()); } 

Putting it all together:

 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)); } 

Output (abbreviated):

  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
 ...

Answer 2

Answer to the current version of the question

You do not need to search for any search at all. For each variable, select the sign (+ or -) for which A +/- incA has the smallest absolute value (in other words, the sign that produces the smallest square A +/- inc A ). This minimizes all terms in squares and therefore minimizes the entire amount.

Previous answer

Assuming you want to minimize sqrt(A*A +/- B1*B1 +/- B2*B2 +/- C1*C1 +/- C2*C2) , choosing the appropriate + or - signs, just iterate over 32 possible combinations and select the one that gives the least result. To iterate over all combinations, note that if you iterate over integers from 0 to 31 and look at their binary representations, you will find all combinations of 5 zeros and ones. Next, note that you can find out if a particular integer n 1 has the binary digit k, you just need to check if the bitwise and n and kth value of 2 is equal to zero. In pseudo code, you therefore execute

 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 

Here is the "&" stand for bitwise and. One of the kth bit, I gives the kth variable a negative sign, zero gives it a positive sign. The case "i = 0", i.e. All signs are positive, as they are processed before the start of the cycle, in order to avoid the need to deal with min_sum not initialized in the first run of the cycle.

Answer 3

Since my first answer was deleted, as it was pseudocode instead of C # ... I changed my abstract set to stack ...

I think a good recursive approach works:

 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); } 

You can define PerformCalculation as the function you want to maximize / minimize.

Answer 4

A good method for optimizing multiple parameters is the Nelder-Mead method or the Downhill Simplex method . It "passes" through the parameter space in a completely natural way, without testing each permutation. See Also Descent Method to the Side (with good graphics showing the principle).

I also found code in C # ; however, I have not tested it.