Comment puis-je surmonter la nature discrète d'un algorithme numérique qui saute actuellement un certain nombre réel dans une boucle?

Question

J'ai un algorithme assez complexe qui effectue une recherche où j'utilise une variable $search dans une certaine plage [0,25 à 1,75].

Sur la base de l'algorithme, il est une chose « intéressante » se produit lorsque le $search est exactement 1, parce qu'elle touche une configuration de variables qui est parfois (mais pas toujours) le plus favorable. Une partie du code dépend de $search étant exactement 1 pour produire le résultat le plus favorable. Plus spécifiquement, il y a généralement une certaine valeur spécifique dans la plage de recherche, qui produit le résultat le plus favorable, mais la façon dont mon algorithme est présenté, cette valeur spécifique est le plus souvent ignorée. Ici, je présente par exemple lorsque cette valeur spécifique (en fonction d'autres entrées et la configuration), se trouve être exactement 1 ..

Le problème

Mathématiquement si $search était continue plutôt que discrète, je n » J'ai ce problème. Mon problème est d'essayer de converger sur la configuration variable la plus favorable en utilisant des mathématiques discrètes. Le problème ici est l'algorithme. Le problème secondaire à surveiller est aussi l'arithmétique en virgule flottante, mais je ne crois pas que ce soit le problème ici.

Basic Loop:

$maxPowerOut = 0 ; 
for ($increment = 0; $increment <= 500; $increment ++) 
{ 
    //vars computed elsewhere, i.e: 
    //MIN = 0.24651533; 
    //STEP = 0.00196969 
    $search = MIN + STEP * $increment; 

    //compute several coefficients (returns an array) 
    $coeff = $this->coefficient($search); 

    //design is a complex library function 
    list($a, $b) = $this->design($coeff); 

    $powerOut = $a * $b; 

    //keep track of max power (and other params, not shown) 
    if ($powerOut > $maxPowerOut) 
     $maxPowerOut = $PowerOut; 
} 

//currently prints 899.993 instead of 900 as should be expected 
print "Max Power is $maxPowerOut"; 

Naturellement, $search est presque jamais 1 exactement. Il va comme ceci:

• 0,99569478115682
• 0,99866447159913
• 1,0016341620414
• 1,0046038524837
• 1,0075735429261
• ...

Notez comment 1 est sautée sur en boucle au-dessus. Pour le bien de l'argument disons que la position la plus favorable se produit à 1.003000. Cette valeur (1.003000) serait également ignorée.

Question

Comment puis-je améliorer, restructurer, repenser, réorganiser, réécrire ma boucle pour éviter ce type de problème?

Answer 1

Une simple amélioration pourrait consister à utiliser une approche itérative:

Dans votre boucle de courant vous recherchez dire 500 valeurs dans l'intervalle [0,25, 1,75]. Disons que vous pouvez réduire l'optimum à l'intervalle beaucoup plus petit [0.995, 1.007] de cette manière. Ensuite, divisez cet intervalle en valeurs de 500 et répétez votre boucle. Répétez jusqu'à ce que vous atteigniez la précision désirée. Mathématiquement, vous voulez trouver le maximum dans un intervalle donné d'une fonction f: search -> power qui calcule une valeur power pour un paramètre donné search. Notez que cela est généralement plus facile, plus votre fonction est lisse f. Pour avoir une idée de ce à quoi peut ressembler f, vous pouvez tracer la fonction en fonction des valeurs que vous avez calculées dans votre boucle.

Si votre fonction est bien conduite et est dit unimodal (a seulement un "bosse"), alors par exemple un simple golden section search serait efficace.

Answer 2

Les nombres à virgule flottante ont une précision limitée (ils sont discrets), attendez-vous à des écarts.

Voir: http://php.net/manual/en/language.types.float.php

Vous pouvez essayer le arbitrary precision extension

Answer 3

direction actuelle

Nombre 1.0 semble être d'une importance, ce qui représente peut-être default.Retravailler le code pour inclure 1.0 dans le cadre du $search, en l'injectant dans le cadre de la même boucle ou en tant qu'élément séparé.

Answer 4

Voici un court extrait de code/pseudo code JavaScript pour vous aider à résoudre votre problème. Fondamentalement, votre fonction devrait s'appeler récursivement si vous trouvez que les deltas/pente ont basculé de positif à négatif.

function findMax(low, high) { 
    var maxOut = Number.MIN_VALUE; 
    // Calculate a step based on the low and high 
    // Using a power of 2 since the floating point numbers are represented by binary 
    var step = Math.abs((high - low)/128); 
    // we'll be tracking the deltas of two test values 
    var prevDelta; 
    var delta; 
    // loop and check two values at a time 
    for(var i=low; i<=(high - step); i+=step) { 
     // coef ... 
     // design ... 
     // for testing 
     var out1 = Math.cos(i); 
     var out2 = Math.cos(i + step); 
     // update the max 
     if(out1 > maxOut) maxOut = out1; 
     if(out2 > maxOut) maxOut = out2; 
     // calc delta 
     delta = out2 - out1; 
     if(prevDelta !== undefined) { 
      // If one delta is going up and 
      // another is going down... 
      // Recursively call the function 
      if(prevDelta > 0 && delta < 0) { 
       var out3 = findMax(i - step, i + step); 
       // update the max 
       if(out3 > maxOut) maxOut = out3; 
      } 
     } 
     prevDelta = delta; 
    } 
    return maxOut; 
} 
alert(findMax(-0.5, 0.5)); // returns 1 

Voici le jsFiddle http://jsfiddle.net/hw5f2o1s/

L'approche ci-dessus ne fonctionnera pas si les maximum se situe entre votre étape initiale faible et faible +, car la récursion est déclenchée en atteignant un pic puis en descendant de celui-ci. Si cela se produit, il se peut que vous deviez rendre la variable étape plus petite en augmentant la puissance de deux divisant (haut - bas).