/*SHHSearch.h *declarations of Spendley, Hext and Himsworth Simplex Search *Adam Gurson College of William & Mary 1999 */ #ifndef _SHHSearch_ #define _SHHSearch_ #include #include #include #include #include "objective.h" #include "vec.h" #include "cmat.h" #include "subscrpt.h" #define stoppingStepLength 10e-8 /*sqrt(fabs(3.0 * (4.0/3.0 - 1.0) - 1.0))*/ #ifndef DEBUG #define DEBUG 0 #endif //#ifndef maxCalls //#define maxCalls 200 //#endif class SHHSearch { public: // constructors and destructors SHHSearch(int dim); // default constructor SHHSearch(int dim, double Sigma); // constructor which allows shrinking coefficient initialization SHHSearch(const SHHSearch& Original); // deep copy constructor ~SHHSearch(); // destructor // algorithmic routines void ExploratoryMoves(); // use Spendley, Hext and Himsworth to find function minimum void ReplaceSimplexPoint(int index, const Vector& newPoint); // replaces simplex point indexed at index with newPoint void CalculateFunctionValue(int index); // finds the f(x) value for the simplex point indexed at index and // replaces the proper value in simplexValues void SetSigma(double newSigma); // allows the user to set a new value for // the shrinking coefficient bool Stop(); // returns true if the stopping criteria have been satisfied void fcnCall(int n, double *x, double& f, int& flag); // indirection of function call for purposes of keeping an accurate // tally of the number of function calls // Simplex-altering functions void InitRegularTriangularSimplex(const Vector *basePoint, const double edgeLength); // deletes any existing simplex and replaces it with a regular // triangular simplex in the following manner: // // basePoint points to a point that will be the "origin" of the // simplex points (it will be a part of the simplex) // edgeLength is the length of each edge of the "triangle" // // functionCalls is reset to 0 and ALL FUNCTION VALUES ARE CALCULATED. // // NOTE: basePoint is assumed to be of proper dimension void InitFixedLengthRightSimplex(const Vector *basePoint, const double edgeLength); // deletes any existing simplex and replaces it with a right-angle // simplex in the following manner: // // basePoint points to a point that will be the "origin" of the // simplex points (it will be a part of the simplex) // edgeLength is to be the length of each simplex side extending // from the basePoint along each positive coordinate direction. // // functionCalls is reset to 0 and ALL FUNCTION VALUES ARE CALCULATED. // // NOTE: basePoint is assumed to be of proper dimension void InitVariableLengthRightSimplex(const Vector *basePoint, const double* edgeLengths); // deletes any existing simplex and replaces it with a right-angle // simplex in the following manner: // // basePoint points to a point that will be the "origin" of the // simplex points (it will be a part of the simplex) // edgeLengths points to an array of n doubles, where n is the // dimension of the given search. x_1 will then be located // a distance of edgeLengths[0] away from the basepoint along the // the x_1 axis, x_2 is edgeLengths[1] away on the x_2 axis, etc. // // functionCalls is reset to 0 and ALL FUNCTION VALUES ARE CALCULATED. // // NOTE: basePoint and edgeLengths are assumed to be of proper dimension void InitGeneralSimplex(const Matrix *plex); // deletes any existing simplex and replaces it with the one // pointed to by plex // // functionCalls is reset to 0 and ALL FUNCTION VALUES ARE CALCULATED. // // NOTE: THIS ASSUMES THAT plex IS OF PROPER DIMENSION void ReadSimplexFile(istream& fp); // may also pass cin as input stream if desired // input the values of each trial point // NOTE: THIS FUNCTION WILL ONLY ACCEPT n+1 POINTS // // functionCalls is reset to 0 and ALL FUNCTION VALUES ARE CALCULATED. // Query functions int GetFunctionCalls() const; // number of objective function evaluations void GetMinPoint(Vector* &minimum) const; // simplex point which generates the best objective function // value found thus far // USER SHOULD PASS JUST A NULL POINTER, WITHOUT PREALLOCATED MEMORY double GetMinVal() const; // best objective function value found thus far void GetCurrentSimplex(Matrix* &plex) const; // performs a deep copy of the simplex to a Matrix pointer // points to a newly allocated chunk of memory upon return // USER SHOULD PASS JUST A NULL POINTER, WITHOUT PREALLOCATED MEMORY void GetCurrentSimplexValues(double* &simValues) const; // performs a deep copy of the simplexValues array to a double pointer // points to a newly allocated chunk of memory upon return // USER SHOULD PASS JUST A NULL POINTER, WITHOUT PREALLOCATED MEMORY void GetCurrentSimplexAges(double* &simAges) const; // performs a deep copy of the simplexAges array to a double pointer // points to a newly allocated chunk of memory upon return // USER SHOULD PASS JUST A NULL POINTER, WITHOUT PREALLOCATED MEMORY int GetVarNo() const; // returns the number of dimensions int GetTolHit() const; // returns toleranceHit void printSimplex() const; // prints out the simplex points by row, their corresponding f(x) // values, and the number of function calls thus far private: void FindMinReplacementIndices(int replacementSkipIndex); // sets minIndex to the simplex index of the point which generates // the lowest value of f(x) // sets replacementIndex to the simplex index of the point which // generates the highest value of f(x) excluding the point at // maxSkipIndex // if maxSkipIndex is set to a valid simplex index, the // replacement search will skip over that index during its search // this is used to prevent the simplex from getting stuck // in a "back and forth" infinite loop void FindCentroid(); // finds the centroid void FindReflectionPt(); // finds the reflection point and sets its f(x) value void ShrinkSimplex(); // this function goes through the simplex and reduces the // lengths of the edges adjacent to the best vertex int AgesTooOld(); // determines when to shrink the simplex based on // how old the individual simplex points are // returns 1 if true and a shrink should occur, 0 otherwise void UpdateAges(int newIndex); // increments the ages of all simplex points EXCEPT the point // with index newIndex, which gets an age of 1 void ResetAges(); // resets all simplex point ages to 1 int dimensions; // the number of dimensions // (the dimension of the problem) Matrix *simplex; // the current simplex double *simplexValues; // their corresponding f(x) values double *simplexAges; // their corresponding ages double sigma; // shrinking coefficient int minIndex; // index of point generating min f(x) int replacementIndex; // index of point to be replaced Vector *centroid; // the current centroid Vector *reflectionPt; // the reflection point double reflectionPtValue; // the value of f(reflectionPt) long functionCalls; // tally of number of function calls int toleranceHit; // 1 if stop due to tolerance, 0 if funcCalls // the following vectors are simply extra storage space // that are used by functions that require a vector of // size = dimensions Vector *scratch, *scratch2; }; #endif