Как я могу преодолеть дискретную природу численного алгоритма, который в настоящее время пропускает определенное действительное число внутри цикла?
У меня довольно сложный алгоритм, который выполняет поиск, где я использую $search переменная в некотором диапазоне [от 0,25 до 1,75].
На основе алгоритма происходит «интересная» вещь, когда $search ровно 1, потому что он попадает в конфигурацию переменных, которая иногда (но не всегда) наиболее благоприятный. Часть кода зависит от $search быть ровно 1, чтобы получить этот самый благоприятный результат.
Точнее говоря, в диапазоне поиска обычно есть какое-то конкретное значение, которое дает наиболее благоприятный результат, но, как показывает мой алгоритм, это конкретное значение чаще всего пропускается. Здесь я выкладываю пример, когда это конкретное значение (на основе других входов и конфигурации) оказывается ровно 1 ..
Эта проблема
Математически говоря, если $search был непрерывным, а не сдержанным, у меня не было бы этой проблемы. Моя проблема состоит в том, чтобы попытаться найти наиболее подходящую переменную конфигурацию с использованием дискретной математики. Проблема здесь в алгоритме. Вторичная проблема, на которую также следует обратить внимание — это арифметика с плавающей запятой, но я не верю, что это проблема здесь только сейчас.
Основной цикл:
$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";
Естественно, $search почти никогда 1 точно. Это выглядит так:
- +0,99569478115682
- +0,99866447159913
- +1,0016341620414
- +1,0046038524837
- +1,0075735429261
- …
Обратите внимание, как 1 пропускается в вышеуказанном цикле. Ради аргумента, скажем, наиболее выгодная позиция происходит на 1.003000. Это значение (1.003000) также будет пропущено.
Вопрос
Как я могу улучшить, реструктурировать, переосмыслить, реорганизовать, переписать мой цикл, чтобы избежать проблем такого типа?
Решение
Простым улучшением может быть использование итеративного подхода:
В вашем текущем цикле вы ищите, скажем, 500 значений в интервале [0,25, 1,75]. Допустим, вы можете таким образом сузить оптимум до гораздо меньшего интервала [0,995, 1,007]. Затем снова разделите этот интервал на, скажем, 500 значений и повторите цикл. Повторяйте, пока не достигнете желаемой точности.
Математически вы хотите найти максимум в заданном интервале функции f: search -> power это вычисляет некоторые power значение для данного search параметр. Обратите внимание, что это, как правило, легче, чем плавнее ваша функция f является. Чтобы почувствовать что f может показаться, что вы можете построить функцию на основе значений, которые вы вычислили в цикле.
Если ваша функция хорошо себя ведет и, скажем, унимодальна (имеет только один «горб»), то, например, простой поиск золотого сечения будет эффективным.
Другие решения
Вот быстрый фрагмент кода JavaScript / псевдокода, чтобы помочь решить вашу проблему. По сути, ваша функция должна вызывать себя рекурсивно, если вы обнаружите, что дельта / наклон изменились с положительного на отрицательное.
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
Вот JSFiddle http://jsfiddle.net/hw5f2o1s/
Приведенный выше подход не сработает, если максимум лежит между вашим начальным минимумом и шагом + низкий уровень, потому что рекурсия запускается достижением пика, а затем снижением от него. Если это произойдет, вам, возможно, придется сделать шаг переменная меньше, увеличивая силу двух деления (высокий низкий).
Числа с плавающей точкой имеют ограниченную точность (они осторожны), ожидайте отклонения.
Увидеть: http://php.net/manual/en/language.types.float.php
Вы можете попробовать произвольное расширение точности
Текущее направление
Число 1.0 кажется важным, возможно, представляющим default, Переработать код для включения 1.0 как часть $searchлибо вставляя его как часть того же цикла, либо как отдельную итерацию.