7
votes

Comment puis-je itération entre 32 options binaires?

J'ai un problème d'optimisation où j'ai 5 variables: A, B1, B2, C1, C2. J'essaie d'optimiser ces 5 variables pour obtenir la plus petite valeur carrée de la somme de racine que je peux. J'ai quelques techniques d'optimisation qui fonctionnent bien, mais celle-ci en particulier me donne des problèmes.

Je veux explorer toutes les 32 options de changement de variables et choisir la plus petite valeur RSS. Ce que je veux dire par ceci est chaque variable peut soit être +/- un incrément. Et chaque choix conduit à 2 autres choix, avec 5 variables qui sont 32 choix. (2 ^ 5) P>

Pour clarifier, je n'aijoute pas mes variables: A, B1, B2, etc., je suis incrémenté / les décrémentant par un montant arbitraire. A +/- x, b1 +/- x2, etc. Et j'essaie de déterminer quelle combinaison d'incrémentation / décrémentation de mes 5 variables de 5 variables reviendront la valeur carrée de la somme de racine la plus basse. P>

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


5 commentaires

Je ne suis pas sûr de l'application de la "somme de racine streilleur". Votre arbre a l'air que vous regardez la somme A +/- B1 +/- B2 +/- C1 +/- C2 et tente de déterminer où mettre un + < / code> et où mettre un - pour minimiser cette somme. Ou êtes-vous en train de regarder la somme sqrt (A * A +/- B1 * B1 ... +/- C2 * C2) ?


Est-ce que je manque quelque chose ou ne serait-il pas plus petit que les variables individuelles s'approchent zéro? Donc, il n'y aurait pas besoin de tester les 32 possibilités, vous pouvez vous éloigner des tests 10.


Vérifiez Ceci out. Il s'agit d'arbres de recherche binaire (BST).


Le carré de la racine est utilisé pour évaluer lequel des 32 options renvoie le meilleur résultat. Quelle valeur de RSS est le plus bas du 32 est le choix actuel que je vais utiliser pour itération de mes variables. Et je vais examiner la possibilité de tester seulement 10, merci


@Kenetik Désolé, mais votre explication est toujours assez déroutante. Est-ce que «montant arbitraire» fixe ou variable? Veuillez indiquer la formule réelle pour la valeur que vous souhaitez minimiser dans votre question et indiquez clairement quelles variables sont fixes et qui doivent être optimisées.


4 Réponses :


1
votes

Réponse à la version actuelle de la question

Vous n'avez pas besoin de faire une recherche du tout ici. Pour chaque variable, choisissez le signe (+ ou -) pour lequel A +/- inca code> a la plus petite valeur absolue (autrement dit le signe qui produit le plus petit carré em> de a +/- inc A code>). Cela minimise toutes les termes dans la somme des carrés, et donc minimisé toute la somme. P>

réponse précédente h2>

supposant que vous souhaitez minimiser sqrt (A * A + / - B1 * B1 +/- B2 * B2 +/- C1 * C1 +/- C2 * C2) Code> En choisissant des panneaux appropriés + code> ou - code>, Itérale simplement sur les 32 combinaisons possibles et choisissez celle qui donne le résultat le plus petit. Pour itérer toutes les combinaisons, observez que si vous ithétiez sur les entiers 0 à 31 et regardez leurs représentations binaires, vous trouverez tous les combinaisons em> de 5 zéros et ceux. Observez en outre que vous pouvez déterminer si un entier particulier con contient 1 au chiffre binaire K, il vous suffit de vérifier si le bit et la puissance de N et K-TH de 2 ne sont pas nuls. Dans pseudo-code, vous faites donc P>

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


7 commentaires

Merci pour votre réponse rapide, votre solution fonctionne parfaitement, quant à ma mauvaise explication, ce n'était pas ce que je cherchais. J'Aplrie pour la manquement interprétation de la question, j'ai ré-édité ma question. J'ajoute un incrément arbitraire à chacune de mes 5 variables, pas les 5 variables les unes aux autres. Merci cependant pour cet algorithme


En outre, si il décide de passer à des variables plus ou moins?


Lol, qu'est-ce qu'il veut un nombre arbitraire de variables? Je pense qu'il est probablement préférable d'avoir la structure du code agnostique du nombre de variables.


@sshannin pourquoi? La complexité de la complexité vous achète rien. Si votre problème est d'optimiser 5 variables, CODE pour 5. Sauf si vous avez déjà savoir que ce sera 6 demain, 4 dans une semaine et éventuellement 20. Ceci est particulièrement vrai ici, où quelque chose De plus de 20 variables ne fonctionnera de toute façon pas, car le temps d'exécution augmente de manière exponentielle. Donc, vraiment, ce qui doit indiquer un algorithme générique qui se décompose pour N> = 20 quand même?


Je suis d'accord avec votre point principal. Mais je ne pense pas vraiment que l'affaire générique est plus difficile à coder ou à comprendre ... En fait, je pense que c'est beaucoup plus clair que votre bit-piratage.


@sshannin je suis respectueusement en désaccord. Conceptuellement , la boucle plus de 32 cas est beaucoup plus simple qu'une méthode récursive qui utilise deux piles pour suivre l'état de son état. De plus, le piratage binaire peut être facilement nettoyé un peu en utilisant un tableau au lieu de ces variables de signe distinctes. Il appuierait même un nombre arbitraire de variables (bien, pour de petites valeurs de "arbitraire", au moins ...). La solution la plus lisible, BTW, n'est probablement que 5 boucles imbriquées ;-).


Hah, assez juste. La façon dont je l'ai fait est beaucoup plus naturelle pour moi (évidemment). Tout ce qui fonctionne le mieux pour vous, je suppose: p



3
votes

Vous pouvez produire un ensemble contenant tous les ensembles d'opérations possibles (par exemple {-, -, -, -}, {-, -, -, +}, {-, -, +,}, etc.) en utilisant le Fonction suivante qui produira une liste des matrices de bool où vrais et faux représentent + et -. Le paramètre vars code> indique que le nombre de variables est combiné. Notez que pour 5 variables, il n'y a que 16 combinaisons (non 32 dans votre état) car il n'y a que 4 opérateurs lors de la combinaison de 5 variables (en supposant que la première variable ne peut pas être annulée):

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


2 commentaires

Merci pour votre réponse rapide, votre solution fonctionne parfaitement, quant à ma mauvaise explication, ce n'était pas ce que je cherchais. J'Aplrie pour la manquement interprétation de la question, j'ai ré-édité ma question. J'ajoute un incrément arbitraire à chacune de mes 5 variables, pas les 5 variables les unes aux autres. Merci cependant pour cet algorithme.


@Kenetik j'ai mis à jour ma réponse en fonction des modifications apportées à votre question.



1
votes

Étant donné que ma première réponse a été supprimée puisque c'était pseudocode au lieu de c # ... J'ai changé mon ensemble abstrait en une pile ...

Je pense qu'une belle approche récursive fonctionne: xxx < / Pre>

Vous pouvez définir une performanceCalculation comme fonction que vous souhaitez optimiser / minimiser.


2 commentaires

Je suis désolé, je n'ai pas connu que votre première réponse a été supprimée, je n'ai même pas eu la chance de le voir. Je vais regarder par-dessus celui-ci soigneusement, merci pour votre contribution


J'ai ajusté ma réponse pour faire les ajustements +/- par un incrément spécifié tel que vous avez ajouté à votre question.



1
votes

Une bonne méthode pour optimiser plusieurs paramètres est le méthode Nelder-Mead ou Simplex Downhill Simplex Méthode . Il "marche" à travers l'espace de paramètre de manière assez naturelle, sans tester toutes les permutations. Voir aussi Méthode de Downhill Simplex (avec bons graphiques montrant le principe).

J'ai aussi trouvé un code en C # ; Cependant, je ne l'ai pas testé.


0 commentaires