shhsearch.h

在linux下面实现的单纯性算法的源代码

/*SHHSearch.h
 *declarations of Spendley, Hext and Himsworth Simplex Search
 *Adam Gurson College of William & Mary 1999
 */

#ifndef _SHHSearch_
#define _SHHSearch_

#include <iostream.h>
#include <fstream.h>
#include <math.h>
#include <stdlib.h>
#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<double>& 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<double> *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<double> *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<double> *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<double> *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<double>* &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<double>* &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<double> *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<double> *centroid;      // the current centroid
   Vector<double> *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<double> *scratch, *scratch2;
};


#endif