PUBLIC

SAOptC::SAOptC(int,int,double,double,double,int,int,TraceC,BooleanT) SAOptC::~SAOptC(void) SAOptC::ResetSeed(void) SAOptC::Optimize(SACostC &) SAOptC::Optimize(SACostC &,SArray1dC,HardAssignC &) SAOptC::MultiOptimize(SACostC &,int) SAOptC::MultiOptimize(SACostC &,int,SArray1dC,HardAssignC &) SAOptC::DoOptimize(SACostC &,HardAssignC &) SAOptC::SimOnceAssignment(SACostC &,HardAssignC,double) SAOptC::SimOnce(SACostC &,HardAssignC,double) SAOptC::SetClamped(SArray1dC) SAOptC::ResetClamped(void) SAOptC::GetRandomUnClamped(BooleanT) SAOptC::RandomiseUnclamped(HardAssignC &) BaseOptC::Optimize(BaseCostC &) BaseOptC::Optimize(BaseCostC &,SArray1dC,HardAssignC &) BaseOptC::ResetSeed(void) BaseOptC::NObjs(void) const BaseOptC::NLabs(void) const BaseOptC::RanHardLabel(int &,BooleanT) BaseOptC::RanSoftLabel(int &) BaseOptC::AddNoise(SoftAssignC &,double,int &,double) BaseOptC::NormaliseSoft(SoftAssignC &) BaseOptC::NormaliseSoftLabels(SoftAssignC &) BaseOptC::NormaliseSoftObjects(SoftAssignC &) BaseOptC::Difference(SoftAssignC &,SoftAssignC &) BaseOptC::SoftToHard(const SoftAssignC &) BaseOptC::PrintSoftLabel(SoftAssignC &) BaseOptC::PrintHardLabel(HardAssignC &) BaseOptC::CheckPermute(HardAssignC &) BaseOptC::ForcePermute(HardAssignC &) TraceC::TraceC(int,ostream &) TraceC::~TraceC(void) TraceC::TraceC(const TraceC &)

SAOptC
include	"amma/SAOpt.hh"
User Level:	Default
Library:	CombOpt
Example:	doNumClassComb.cc
Section:	Optimisation.Implementation Numerical Methods.Optimisation.Implementation
In Scope:	std

Comments:
------------------------------------------------------------------------- *********** Simulated Annealing ***************************************** ------------------------------------------------------------------------- This is a minimizer. Major choices: Apart from the usual parameters you must choose - assignment or not. The assignment flag selects that the solution must be a permutation matrix. - some variables may be clamped (fixed) and the optimisation proceeds only over other variables All the stuff for clamping probably adds an overhead HOW DOES IT WORK? ----------------- The non-assignment method in one pass - looks at each object and computes the energy of all possible labels - the label is reassigned with a thermal probability The assignment method in one pass - loops over all objects - then chooses another object at random - computes the energy of a swap - performs the swap with thermal probability The execution times are NOT comparable as the permutation algorithm has a much smaller search space. Parameters ---------- nobjs nlabs thi tlo f passes idum ------------------------------------------------------------------------- -------------------------------------------------------------------------

public BaseOptC

double thi;

start and end temperature

double tlo;

start and end temperature

double f;

temperature reduction factor

int passes;

number of passes at each temperature

int idum0;

seed for random number generator

int idum;

seed for random number generator

BooleanT assignment;

Set to labelling or assignment problem

SArray1dC clamped;

int no_unclamped;

SAOptC(int _nobjs,int _nlabs,double _thi,double _tlo,double _f,int _passes,int _idum = -1,TraceC tr = TraceC(NoTrace,cout),BooleanT _assignment = FALSE)

~SAOptC()

Destructor

void ResetSeed()

set the seed to its first given value if negative this restarts the random seqeunce

HardAssignC Optimize(SACostC & func)

HardAssignC Optimize(SACostC & func,SArray1dC<BooleanT> _clamped,HardAssignC & start)

Optimize the specified function according to previously specified parameters. An initial guess may be supplied and is important for clamped problems! For assignment problems start must be a valid permutation solution!

HardAssignC MultiOptimize(SACostC & func,int n)

HardAssignC MultiOptimize(SACostC & func,int n,SArray1dC<BooleanT> _clamped,HardAssignC & start)

multiple starts of the previous function.

HardAssignC DoOptimize(SACostC & cost,HardAssignC & work)

does the real work! Starts at given labelling takes account of clamp array

int SimOnceAssignment(SACostC & cost,HardAssignC work,double temp)

One pass at fixed temperature, solution is always an assignment

int SimOnce(SACostC & cost,HardAssignC work,double temp)

One pass at fixed temperature

void SetClamped(SArray1dC<BooleanT> _clamped)

Set the clamped array using the input, the clamped array remains unchanged until another call of this function

void ResetClamped(void)

Set all objects to NOT clamped

int GetRandomUnClamped(BooleanT reset)

get an unclamped object at random, returns -1 if there is 0 or 1 unclamped objects

void RandomiseUnclamped(HardAssignC & work)

HardAssignC Optimize(BaseCostC & func)

HardAssignC Optimize(BaseCostC & func,SArray1dC<BooleanT> _clamped,HardAssignC & start)

void ResetSeed()

int NObjs() const

int NLabs() const

HardAssignC RanHardLabel(int & idum,BooleanT ass = FALSE)

Random initial assignment of labels

SoftAssignC RanSoftLabel(int & idum)

Random initial assignment of labels

void AddNoise(SoftAssignC & work,double x,int & idum,double minp = 1e-10)

add uniform noise scaled by x to work set negatives to positive and set minimum to minp does NOT normalize

void NormaliseSoft(SoftAssignC & w)

normalise the label set

SoftAssignC NormaliseSoftLabels(SoftAssignC & wold)

normalise the label set

SoftAssignC NormaliseSoftObjects(SoftAssignC & wold)

normalise the object set

double Difference(SoftAssignC & w1,SoftAssignC & w2)

sum of absolute differences

HardAssignC SoftToHard(const SoftAssignC & ass)

Random initial assignment of labels

void PrintSoftLabel(SoftAssignC & r)

print out

void PrintHardLabel(HardAssignC & r)

print out

BooleanT CheckPermute(HardAssignC & r)

checks to see that the labelling is a permutation

void ForcePermute(HardAssignC & r)

forces the solution to be a permutation by a crude and possibly slow algorithm

Inline TraceC(int tl = NoTrace,ostream & os = cout)

Constructor

Inline ~TraceC()

Destructor

Inline TraceC(const TraceC & t)

Copy Constructor