Jump to content
  • Advertisement
Sign in to follow this  
Narf the Mouse

Critique my recursive stochastic hill-climbing algorithm

This topic is 2991 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a recursive stochastic hill-climbing algorithm for solving equations. The things I would like to work on are performance, efficiency and my own understanding of the algorithm, as I worked it out through a combination of intuition, mathematical instinct and late-night braining. *Snip* Latest two code sections at the bottom. [Edited by - Narf the Mouse on April 12, 2010 10:02:56 PM]

Share this post


Link to post
Share on other sites
Advertisement
Just from a quick scan, there's some variables named such that their purpose is unclear, like
(Func<Double[], Double, Double> f
... f? Really? Give things names that make it clear what they are doing without scanning all the code to infer it from usage.

EquationSolveWithin takes a lot of arguments and has a shedload of data, can it be broken up into smaller methods with their own concern. Don't speculate on the performance implications of this just yet; this looks like c#, the JIT may observe the heat (high call frequency) of one of your smaller methods and optimise it further than it can with such a large method. Either way, strive for clarity over speculative performance gains.

Ditch the commented out code, it's a distraction. Don't leave in "debug hook" code, use conditional breakpoints.

Break conditions like the following out into sensibly named methods i.e instead of
   } while (Math.Round(output, 11) != Math.Round(target, 11) && high != low && tempHigh != current && tempLow != current && (foundCloser || iterationsWithoutBetter < 50));

prefer
 } while (SomeSensibleName());
, same with;
  
if ((closest.HasValue && high < closest && oldHigh > target) ||(closest.HasValue && high > closest && oldHigh < target))
and
if ((closest.HasValue && low > closest && oldHigh > target) ||(closest.HasValue && low < closest && oldHigh < target))

These are stylistic but the will help reason about the algorithm. This is what I'd do before any actual tweaking, your mileage may vary.

Share this post


Link to post
Share on other sites
Ok, I've put all the complicated checks into their own functions; in doing so, I found one legacy check that was unnecessary, as it was doing the same thing wether it returned true or false, so that's been optimized out.

And thanks.

public static List<Double> EquationSolver(Func<Double[], Double, Double> equationToSolve, Double[] inputs, Double target = 0, Filter filter = null)
{
List<Double> list = new List<double>();
EquationSolveWithin(equationToSolve, inputs, target, 0, Double.MaxValue, ref list, filter);
EquationSolveWithin(equationToSolve, inputs, target, 0, (-Double.MaxValue), ref list, filter);
return list;
}


public static void EquationSolveWithin(
Func<Double[], Double, Double> equationToSolve, Double[] inputs, Double target,
Double low, Double high, ref List<Double> list, Filter filter
)
{
Double current = ((high - low) / 2.0) + low;
Double output = 0;
Double? firstOutput = null;
bool reverse = false;
Double distance = high * high * high;
Double lastDistance = high * high * high;
Double oldLow = low;
Double oldHigh = high;
Double tempLow = low;
Double tempHigh = high;
Double? closest = null;
Double closestDistance = 0;
int iterationsWithoutBetter = 0;
bool foundCloser = false;

do
{
current = ((high - low) / 2.0) + low;
/* if (!firstOutput.HasValue)
current = ((high - low) / 2.0) + low;
else
current = ((high - low) * GeneralData.Random.NextDouble()) + low; */


tempLow = low;
tempHigh = high;


lastDistance = distance;
output = equationToSolve(inputs, current);
if (!firstOutput.HasValue)
{
firstOutput = output;
distance = output - target;
lastDistance = output - target;
closestDistance = output - target;
closest = current;
foundCloser = true;
iterationsWithoutBetter = 0;
}
distance = output - target;
/* if (high <= 20000)
{
int j = 0;
++j;
} */



if (ShouldReverse(distance, lastDistance))
reverse = !reverse;

if (!reverse)
{
high = current;
// high = ((high - current) / 2.0) + current;
}
else
{
low = current;
// low = ((current - low) / 2) + low;
}

foundCloser = false;
++iterationsWithoutBetter;
if (Math.Abs(distance) <= Math.Abs(closestDistance))
{
closestDistance = output - target;
closest = current;
foundCloser = true;
iterationsWithoutBetter = 0;
}

if (GoneToFarA(target, high, oldHigh, closest))
{
if (!reverse)
high = closest.Value * 2;
else
low = closest.Value / 2;
}
if (GoneToFarB(target, low, oldHigh, closest))
{
if (!reverse)
low = closest.Value / 2;
else
high = closest.Value * 2;
}

} while (
NotDone(target, low, high, current, output, tempLow, tempHigh, iterationsWithoutBetter, foundCloser)
);

Boolean passedFilter = PassedFilter(filter, current);
if (NewAndValid(target, list, current, output, passedFilter))
{
list.Add(Math.Round(current, 11));
EquationSolveWithin(equationToSolve, inputs, target, oldLow, current, ref list, filter);
EquationSolveWithin(equationToSolve, inputs, target, current, oldHigh, ref list, filter);
}


// -19x^5 + 18x^4 + 125x^3 + -56x^2 + -150x + 29 =
// x1 = 2.6220971863491
// x2 = 1.3224569490446
// x3 = 0.1859002930856
// x4 = -1.9980761764108
// x5 = -1.1850098310158
}

private static bool ShouldReverse(Double distance, Double lastDistance)
{
return (distance > 0 && lastDistance < 0)
|| (distance < 0 && lastDistance > 0)
|| (Math.Abs(distance) > Math.Abs(lastDistance));
}


private static bool GoneToFarA(Double target, Double high, Double oldHigh, Double? closest)
{
return (closest.HasValue && high < closest.Value && oldHigh > target)
|| (closest.HasValue && high > closest.Value && oldHigh < target);
}


private static bool GoneToFarB(Double target, Double low, Double oldHigh, Double? closest)
{
return (closest.HasValue && low > closest.Value && oldHigh > target)
|| (closest.HasValue && low < closest.Value && oldHigh < target);
}


private static bool NotDone(Double target, Double low, Double high, Double current, Double output, Double tempLow, Double tempHigh, int iterationsWithoutBetter, bool foundCloser)
{
return Math.Round(output, 11) != Math.Round(target, 11)
&& high != low && tempHigh != current && tempLow != current
&& (foundCloser || iterationsWithoutBetter < 15);
}


private static Boolean PassedFilter(Filter filter, Double current)
{
Boolean passedFilter = false;
if (filter != null)
{
double? first = filter.value;
double? second = filter.Process(current);
passedFilter = (first != second);
}
else
passedFilter = true;
return passedFilter;
}


private static bool NewAndValid(Double target, List<Double> list, Double current, Double output, Boolean passedFilter)
{
return passedFilter && !list.Contains(Math.Round(current, 11)) && Math.Round(output, 11) == Math.Round(target, 11);
}



Share this post


Link to post
Share on other sites
It wasn't correctly filtering; I've fixed that. Also, I've added an optional "searchRange" potential optimization.


public static List<Double> EquationSolver(
Func<Double[], Double, Double> equationToSolve,
Double[] inputs,
double target = 0,
Filter filter = null,
double searchRange = Double.MaxValue)
{
List<Double> list = new List<double>();
EquationSolveWithin(equationToSolve, inputs, target, 0, searchRange, ref list, filter);
EquationSolveWithin(equationToSolve, inputs, target, 0, (-searchRange), ref list, filter);
return list;
}


public static void EquationSolveWithin(
Func<Double[], Double, Double> equationToSolve, Double[] inputs, Double target,
Double low, Double high, ref List<Double> list, Filter filter
)
{
Double current = ((high - low) / 2.0) + low;
Double output = 0;
Double? firstOutput = null;
bool reverse = false;
Double distance = high * high * high;
Double lastDistance = high * high * high;
Double oldLow = low;
Double oldHigh = high;
Double tempLow = low;
Double tempHigh = high;
Double? closest = null;
Double closestDistance = 0;
int iterationsWithoutBetter = 0;
bool foundCloser = false;

do
{
current = ((high - low) / 2.0) + low;
/* if (!firstOutput.HasValue)
current = ((high - low) / 2.0) + low;
else
current = ((high - low) * GeneralData.Random.NextDouble()) + low; */


tempLow = low;
tempHigh = high;


lastDistance = distance;
output = equationToSolve(inputs, current);
if (!firstOutput.HasValue)
{
firstOutput = output;
distance = output - target;
lastDistance = output - target;
closestDistance = output - target;
closest = current;
foundCloser = true;
iterationsWithoutBetter = 0;
}
distance = output - target;
/* if (high <= 20000)
{
int j = 0;
++j;
} */



if (ShouldReverse(distance, lastDistance))
reverse = !reverse;

if (!reverse)
{
high = current;
// high = ((high - current) / 2.0) + current;
}
else
{
low = current;
// low = ((current - low) / 2) + low;
}

foundCloser = false;
++iterationsWithoutBetter;
if (Math.Abs(distance) <= Math.Abs(closestDistance))
{
closestDistance = output - target;
closest = current;
foundCloser = true;
iterationsWithoutBetter = 0;
}

if (GoneToFarA(target, high, oldHigh, closest))
{
if (!reverse)
high = closest.Value * 2;
else
low = closest.Value / 2;
}
if (GoneToFarB(target, low, oldHigh, closest))
{
if (!reverse)
low = closest.Value / 2;
else
high = closest.Value * 2;
}

} while (
NotDone(target, low, high, current, output, tempLow, tempHigh, iterationsWithoutBetter, foundCloser)
);

if (NewAndValid(target, list, current, output))
{
if (PassedFilter(filter, current))
{
list.Add(Math.Round(current, 11));
EquationSolveWithin(equationToSolve, inputs, target, oldLow, current, ref list, filter);
EquationSolveWithin(equationToSolve, inputs, target, current, oldHigh, ref list, filter);
}
}


// -19x^5 + 18x^4 + 125x^3 + -56x^2 + -150x + 29 =
// x1 = 2.6220971863491
// x2 = 1.3224569490446
// x3 = 0.1859002930856
// x4 = -1.9980761764108
// x5 = -1.1850098310158
}

private static bool ShouldReverse(Double distance, Double lastDistance)
{
return (distance > 0 && lastDistance < 0)
|| (distance < 0 && lastDistance > 0)
|| (Math.Abs(distance) > Math.Abs(lastDistance));
}


private static bool GoneToFarA(Double target, Double high, Double oldHigh, Double? closest)
{
return (closest.HasValue && high < closest.Value && oldHigh > target)
|| (closest.HasValue && high > closest.Value && oldHigh < target);
}


private static bool GoneToFarB(Double target, Double low, Double oldHigh, Double? closest)
{
return (closest.HasValue && low > closest.Value && oldHigh > target)
|| (closest.HasValue && low < closest.Value && oldHigh < target);
}


private static bool NotDone(Double target, Double low, Double high, Double current, Double output, Double tempLow, Double tempHigh, int iterationsWithoutBetter, bool foundCloser)
{
return Math.Round(output, 11) != Math.Round(target, 11)
&& high != low && tempHigh != current && tempLow != current
&& (foundCloser || iterationsWithoutBetter < 15);
}


private static Boolean PassedFilter(Filter filter, Double current)
{
Boolean passedFilter = false;
if (filter != null)
{
double? first = filter.value;
double? second = filter.Process(current);
passedFilter = (first != second);
}
else
passedFilter = true;
return passedFilter;
}


private static bool NewAndValid(Double target, List<Double> list, Double current, Double output)
{
return !list.Contains(Math.Round(current, 11)) && Math.Round(output, 11) == Math.Round(target, 11);
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!