package jsat.math.optimization;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import jsat.linear.DenseVector;
import jsat.linear.Vec;
import jsat.math.Function;
import jsat.math.FunctionVec;
import jsat.utils.ProbailityMatch;
/**
* The Nelder-Mean algorithm is a simple directed search method. As such, it does not need any information about
* the target functions derivative, or any data points. To perform best, the Nelder-Mean method needs N+1
* reasonable initial guesses for an N dimensional problem.
* The Nelder-Mean method has the advantage that the only information it needs about the function it is going to minimize, is the function itself.
*
* @author Edward Raff
*/
public class NelderMead implements Optimizer
{
private static final long serialVersionUID = -2930235371787386607L;
/**
* Reflection constant
*/
private double reflection = 1.0;
/**
* Expansion constant
*/
private double expansion = 2.0;
/**
* Contraction constant
*/
private double contraction = -0.5;
/**
* Shrink constant
*/
private double shrink = 0.5;
private int maxIterations = 1000;
public NelderMead() {
}
public NelderMead(NelderMead toCopy)
{
this.reflection = toCopy.reflection;
this.expansion = toCopy.expansion;
this.contraction = toCopy.contraction;
this.shrink = toCopy.shrink;
this.maxIterations = toCopy.maxIterations;
}
/**
* Sets the reflection constant, which must be greater than 0
* @param reflection the reflection constant
*/
public void setReflection(double reflection)
{
if(reflection <=0 || Double.isNaN(reflection) || Double.isInfinite(reflection) )
throw new ArithmeticException("Reflection constant must be > 0, not " + reflection);
this.reflection = reflection;
}
/**
* Sets the expansion constant, which must be greater than 1 and the reflection constant
* @param expansion
*/
public void setExpansion(double expansion)
{
if(expansion <= 1 || Double.isNaN(expansion) || Double.isInfinite(expansion) )
throw new ArithmeticException("Expansion constant must be > 1, not " + expansion);
else if(expansion <= reflection)
throw new ArithmeticException("Expansion constant must be less than the reflection constant");
this.expansion = expansion;
}
/**
* Sets the contraction constant, which must be in the range (0, 1)
* @param contraction the contraction constant
*/
public void setContraction(double contraction)
{
if(contraction >= 1 || contraction <= 0 || Double.isNaN(contraction) || Double.isInfinite(contraction) )
throw new ArithmeticException("Contraction constant must be > 0 and < 1, not " + contraction);
this.contraction = contraction;
}
/**
* Sets the shrinkage constant, which must be in the range (0, 1)
* @param shrink
*/
public void setShrink(double shrink)
{
if(shrink >= 1 || shrink <= 0 || Double.isNaN(shrink) || Double.isInfinite(shrink) )
throw new ArithmeticException("Shrinkage constant must be > 0 and < 1, not " + shrink);
this.shrink = shrink;
}
@Override
public void optimize(double tolerance, Vec w, Vec x0, Function f, FunctionVec fp, boolean parallel)
{
List initialPoints = new ArrayList<>();
initialPoints.add(x0.clone());
optimize(tolerance, maxIterations, f, initialPoints, parallel).copyTo(w);
}
/**
* Attempts to find the minimal value of the given function.
*
* @param eps the desired accuracy of the result.
* @param iterationLimit the maximum number of iteration steps to allow. This value must be positive
* @param f the function to optimize. This value can not be null
* @param initalPoints the list of initial guess points. If too small, new ones will be generated. if too large,
* the extra ones will be ignored. This list may not be empty
* @param parallel {@code true} if multiple threads should be used for
* optimization, or {@code false} if a single thread should be used.
* @return the computed value for the optimization.
*/
public Vec optimize(double eps, int iterationLimit, Function f, List initalPoints, boolean parallel)
{
if(initalPoints.isEmpty())
throw new ArithmeticException("Empty Initial list. Can not determin dimension of problem");
Vec init = initalPoints.get(0);
int N = initalPoints.get(0).length();
//The simplex verticies paired with their value from the objective function
List> simplex = new ArrayList<>(N);
for(Vec vars : initalPoints)
simplex.add(new ProbailityMatch<>(f.f(vars, parallel), vars.clone()));
Random rand = new Random(initalPoints.hashCode());
while(simplex.size() < N+1)
{
//Better simplex geneartion?
DenseVector newSimplex = new DenseVector(N);
for(int i = 0; i < newSimplex.length(); i++)
if(init.get(i) != 0)
newSimplex.set(i, init.get(i)*rand.nextGaussian());
else
newSimplex.set(i, rand.nextGaussian());
simplex.add(new ProbailityMatch<>(f.f(newSimplex, parallel), newSimplex));
}
Collections.sort(simplex);
//Remove superfolusly given points
while(simplex.size() > N+1)
simplex.remove(simplex.size()-1);
//Center of gravity point
Vec x0 = new DenseVector(N);
//reflection point
Vec xr = new DenseVector(N);
//Extension point, also used for contraction
Vec xec = new DenseVector(N);
//Temp space for compuations
Vec tmp = new DenseVector(N);
final int lastIndex = simplex.size()-1;
for(int iterationCount = 0; iterationCount < iterationLimit; iterationCount++)
{
//Convergence check
if(Math.abs(simplex.get(lastIndex).getProbability() - simplex.get(0).getProbability()) < eps)
break;
//Step 2: valculate x0
x0.zeroOut();
for(ProbailityMatch pm : simplex)
x0.mutableAdd(pm.getMatch());
x0.mutableDivide(simplex.size());
//Step 3: Reflection
x0.copyTo(xr);
x0.copyTo(tmp);
tmp.mutableSubtract(simplex.get(lastIndex).getMatch());
xr.mutableAdd(reflection, tmp);
double fxr = f.f(xr);
if(simplex.get(0).getProbability() <= fxr && fxr < simplex.get(lastIndex-1).getProbability())
{
insertIntoSimplex(simplex, xr, fxr);
continue;
}
//Step 4: Expansion
if(fxr < simplex.get(0).getProbability())//Best so far
{
x0.copyTo(xec);
xec.mutableAdd(expansion, tmp);//tmp still contains (x0-xWorst)
double fxec = f.f(xec);
if(fxec < fxr)
insertIntoSimplex(simplex, xec, fxec);//Even better! Use this one
else
insertIntoSimplex(simplex, xr, fxr);//Ehh, wasnt as good as we thought
continue;
}
//Step 5: Contraction
x0.copyTo(xec);
xec.mutableAdd(contraction, tmp);
double fxec = f.f(xec);
if(fxec < simplex.get(lastIndex).getProbability())
{
insertIntoSimplex(simplex, xec, fxec);
continue;
}
//Step 6: Reduction
Vec xBest = simplex.get(0).getMatch();
for(int i = 1; i < simplex.size(); i++)
{
ProbailityMatch pm = simplex.get(i);
Vec xi = pm.getMatch();
xi.mutableSubtract(xBest);
xi.mutableMultiply(shrink);
xi.mutableAdd(xBest);
pm.setProbability(f.f(xi));
}
Collections.sort(simplex);
}
return simplex.get(0).getMatch();
}
private static void insertIntoSimplex(List> simplex, Vec x, double fx)
{
//We are removing the last element and inserting a new one that is better
ProbailityMatch pm = simplex.remove(simplex.size() - 1);
pm.setProbability(fx);
x.copyTo(pm.getMatch());
//Now put it in the correct place
int sortInto = Collections.binarySearch(simplex, pm);
if (sortInto >= 0)
simplex.add(sortInto, pm);
else
{
sortInto = -(sortInto)-1;
if(sortInto == simplex.size())//Then it was just better thne the last
simplex.add(pm);
else//It was a bit better then that
simplex.add(sortInto, pm);
}
}
@Override
public void setMaximumIterations(int iterations)
{
if(iterations <= 0)
throw new IllegalArgumentException("Number of iterations must be positive, not " + iterations);
this.maxIterations = iterations;
}
@Override
public int getMaximumIterations()
{
return maxIterations;
}
@Override
public NelderMead clone() {
return new NelderMead(this);
}
}
Ads help maintain this website.