In this post, I develop the base classes and helper classes that will be used by future classes that implement various region elimination methods.
The objective of a region elimination optimization problem is to find the minimum value of a function within a given starting region. For example, the function can be (x-2)2 and the starting region can be 1 to 3. For that example, the solution is 2, since that is the minimum value of the function in that region.
The first class shown in the code below is called Region Elimination Results. It is basically a data structure that stores the results of the region elimination routine and includes a boolean to indicate whether or not the region elimination method succeeded or failed. It also stores the X and Y values of the minimum found by the region elimination routine.
The next class, Search Point, is used for calculations by the region elimination routines. It stores the X and Y values of a point used by the region elimination routine.
Another class, Search Point Collection, stores a collection of search points and inherits from the generic Collection class. It has a field and property that sets the maximum size of the collection. This field is used when an item is inserted into the collection. If the collection has fewer items than the max size, the item is added to the collection. If the collection has the same number of items as the max size, then the item with the greatest Y value is removed from the collection before the new item is added. This class also contains other fairly straight forward helper functions used by the region elimination methods.
The last class in this post is Region Elimination Base and it is the base class of the classes used for the region elimination methods. It contains a public virtual function called Region Eliminate which is overridden in the classes that inherit from Region Elimination Base and performs the region elimination routine.
The source code for these classes is given below.
public class RegionEliminationResults
{
private bool _succeeded =
false;
private double _xResult =
double.NaN;
private double _yResult =
double.NaN;
public RegionEliminationResults()
{
}
public RegionEliminationResults(double result, double yResult)
{
_succeeded = true;
_xResult = result;
_yResult = yResult;
}
public RegionEliminationResults(bool succeeded)
{
_succeeded = succeeded;
}
public RegionEliminationResults(double xResult, double yResult, bool succeeded)
{
_succeeded = succeeded;
_xResult = xResult;
_yResult = yResult;
}
public bool Succeeded
{
get { return _succeeded; }
set { _succeeded = value; }
}
public double XResult
{
get { return _xResult; }
set { _xResult = value; }
}
public double YResult
{
get { return _yResult; }
set { _yResult = value; }
}
}
public class SearchPoint
{
private double _x = double.NaN;
private double _y = double.NaN;
public SearchPoint()
{
}
public SearchPoint(double x)
{
_x = x;
}
public SearchPoint(double x, double y)
{
_x = x;
_y = y;
}
public double X
{
get { return _x; }
set { _x = value; }
}
public double Y
{
get { return _y; }
set { _y = value; }
}
public override string ToString()
{
return "SearchPoint X:" + _x.ToString() + " Y:" + _y.ToString();
}
}
public class SearchPointCollection : Collection<SearchPoint>
{
private int _maxSize = 3;
public SearchPointCollection()
: base()
{
}
protected override void InsertItem(int index, SearchPoint item)
{
while (index >= _maxSize)
{
SearchPoint worstPoint = (from pt in this orderby pt.Y descending select pt).ToArray()[0];
base.Remove(worstPoint);
index--;
}
base.InsertItem(index, item);
SearchPoint[] points = (from pt in this orderby pt.X select pt).ToArray();
for (int i = 0; i < points.Length; i++)
{
this[i] = points[i];
}
}
public bool CanAdd(SearchPoint newPoint)
{
bool canAdd = (from pt in this where pt.X == newPoint.X select pt).Count() == 0;
if (canAdd)
{
double currentMin = (from pt in this select pt.Y).Max();
canAdd = newPoint.Y < currentMin;
}
return canAdd;
}
public bool CanAdd(double newX)
{
return (from pt in this where pt.X == newX select pt).Count() == 0;
}
public bool IsBracketed()
{
double min = (from pt in this select pt.Y).Min();
bool result = min < this[0].Y && min < this[Count - 1].Y;
if (!result)
{
double max = (from pt in this select pt.Y).Max();
result = min == max;
}
return result;
}
public double ParabolicMinYEstimate()
{
double result = double.NaN;
if (Count == 3)
{
double[] x = (from pt in this select pt.X).ToArray();
double[] y = (from pt in this select pt.Y).ToArray();
result = Polynomial.ParabolicMin(x, y);
}
return result;
}
public double CubicMinYEstimate()
{
double result = double.NaN;
if (Count == 4)
{
double[] x = (from pt in this select pt.X).ToArray();
double[] y = (from pt in this select pt.Y).ToArray();
CubicMinResults res = Polynomial.CubicMin(x, y);
if (res.ResultType == CubicResultType.StandardSecondOrder || res.ResultType == CubicResultType.StandardThirdOrder)
{
result = res.LocalMinX;
}
}
return result;
}
public int MaxSize
{
get { return _maxSize; }
set { _maxSize = value; }
}
public SearchPointCollection Clone(int nMaxSize)
{
SearchPointCollection cloneCollection = new SearchPointCollection();
cloneCollection.MaxSize = nMaxSize;
for (int i = 0; i < Count; i++)
{
cloneCollection.Add(new SearchPoint(this[i].X, this[i].Y));
}
return cloneCollection;
}
public SearchPoint FindMinY()
{
return (from pt in this orderby pt.Y select pt).ToArray()[0];
}
}
public class RegionEliminationBase
{
protected bool _cancel = false;
protected int _numStartingPoints = 2;
public RegionEliminationBase()
{
}
public virtual RegionEliminationResults RegionEliminate(Func<double, double> function, SearchPointCollection startPoint, double eliminationFraction)
{
return new RegionEliminationResults();
}
public bool Cancel
{
get
{
bool result = false;
lock (this)
{
result = _cancel;
}
return result;
}
set
{
lock (this)
{
_cancel = value;
}
}
}
protected void CalculateMissingValues(SearchPointCollection points, Func<double, double> function)
{
for (int i = 0; i < points.Count; i++)
{
if (double.IsNaN(points[i].Y))
{
points[i].Y = function(points[i].X);
}
}
}
public int NumStartingPoints
{
get { return _numStartingPoints; }
}
}
Subscribe