SiGraph: sulcal graphs


sigraph::Anneal Class Reference

Recuit simulé. More...

#include <si/graph/anneal.h>

Collaboration diagram for sigraph::Anneal:

Public Types

enum  Mode {
  METROPOLIS , GIBBS , ICM , MPM ,
  SPECIAL
}
 
enum  IterType { VERTEX , CLIQUE , CUSTOM }
 
enum  VoidMode { VOIDMODE_NONE , VOIDMODE_REGULAR , VOIDMODE_STOCHASTIC }
 
enum  InitLabelsType { INITLABELS_NONE , INITLABELS_VOID , INITLABELS_RANDOM }
 

Public Member Functions

 Anneal (CGraph &cg, MGraph &rg)
 
virtual ~Anneal ()
 
void init (Mode mode, double temp, double tmult, double tICM, double stopProp, unsigned gibbsMaxTrans, bool verbose=true, IterType itType=VERTEX, InitLabelsType voidInitialLabels=INITLABELS_RANDOM, const std::string &voidLabel="", std::ostream *plotStream=0, unsigned niterBelowStopProp=1)
 Fixe l'état initial.
 
void setVoidMode (VoidMode mode, unsigned occurency=0)
 Mode "void": essais de configs où tous les labels sont remplacés par void.
 
void deleteExtensions ()
 
void addExtension (AnnealExtension *ae, unsigned occurency=20)
 
void clear ()
 Libère les structures allouées dans les graphes.
 
void reset ()
 Revient aux conditions initiales.
 
void checkStop ()
 Teste le critère d'arrêt et fixe l'état correspondant.
 
void fitStep ()
 Effectue une passe de recuit.
 
void fit ()
 Effectue tout le recuit.
 
void stepMetropolis ()
 Effectue une passe en mode Métropolis.
 
void stepGibbs ()
 Effectue une passe en mode Gibbs Sampler.
 
void stepICM ()
 Effectue une passe en mode ICM déterministe.
 
void stepVoid ()
 Effectue une passe en mode Void (essais de configs ou tout un label est enlevé)
 
void processPotentials (const std::set< Vertex * > &vertices, std::vector< EnergyField > &en)
 Calcule les différentes énergies des transitions possibles d'un groupe de noeuds, en Gibbs Sampler ou en ICM.
 
double processAllPotentials ()
 Calcule les potentiels de toutes les cliques.
 

Interrogation de l'état du système

CGraph_cgraph
 Graphe à étiqueter.
 
MGraph_mgraph
 Graphe modèle.
 
Mode _modeI
 Mode initial.
 
Mode _mode
 Mode courant.
 
double _tempI
 Température initiale.
 
double _temp
 Température courante.
 
bool _finished
 
double _tmult
 
double _tICM
 
double _stopProp
 
unsigned _ntrans
 
unsigned _maxtrans
 
unsigned _gibbsMaxTrans
 
double _stepDeltaE
 
double _deltaE
 
double _initEnergy
 
bool _verbose
 
IterType _iterType
 
SGProvider_sgProvider
 
unsigned _niter
 
std::ostream * _plotStream
 
InitLabelsType _initialLabelsType
 
std::string _voidLabel
 
VoidMode _voidmode
 
unsigned _voidoccurency
 
std::vector< AnnealExtension * > _annealExtensions
 
unsigned _extensionPassOccurency
 
bool _doubleDrawingLots
 
unsigned _niterBelowStopProp
 
unsigned _currentNiterBelowStopProp
 
const CGraphcGraph () const
 Graphe à étiqueter.
 
CGraphcGraph ()
 
const MGraphrGraph () const
 Graphe modèle.
 
MGraphrGraph ()
 
Mode modeI () const
 Mode de recuit initial.
 
Mode mode () const
 Mode courant.
 
double tempI () const
 Température initiale.
 
double temp () const
 Température courante.
 
bool isFinished () const
 Retourne true si le recuit est fini.
 
double tMult () const
 Multiplicxateur de température.
 
double tICM () const
 Température de passage en ICM.
 
double stopProp () const
 Proportion de transformations acceptées en dessous de laquelle on arrête le recuit.
 
unsigned nTrans () const
 Nombre de transformations acceptées au cours de la dernière passe.
 
unsigned maxTrans () const
 Nombre de transformations proposées au cours de la dernière passe.
 
unsigned gibbsMaxTrans () const
 Nombre max.
 
double deltaE () const
 Variation d'énergie du graphe depuis le début du recuit.
 
double stepDeltaE () const
 Variation d'énergie du graphe à la dernière passe.
 
double initialEnergy () const
 
double energy () const
 
bool verbosity () const
 dit si les affichages sont autorisés ou interdits
 
IterType iterType () const
 
unsigned nIter () const
 Nb d'itérations de recuit effectuées.
 
bool doubleDrawingLots () const
 Dit si on est en mode DoubleTirage, technologie © JeffProd'00, pour les passes void et extensions.
 
void setDoubleDrawingLots (bool t)
 
const std::string & voidLabel () const
 
void setAllowThreads (bool)
 enables or disables the use of multiple threads during annealing.
 
bool threadsAllowed () const
 
void setMaxIterations (unsigned n)
 
unsigned maxIterations () const
 Maximum number of iterations before switching to next mode.
 
unsigned MPMUnrecordedIterations () const
 Number of MPM steps before labels stats are recorded.
 
void setMPMUnrecordedIterations (unsigned n)
 

Detailed Description

Recuit simulé.

Fait le recuit simulé à partir d'un graphe à cliques (CGraph) à étiqueter et d'un graphe modèle (MGraph).

Avant de faire un recuit, il faut avoir initialisé les cliques du graphe à étiqueter (fonction ModelFinder::initCliques()).

Il faut aussi initialiser les paramètres du recuit en appelant la fonction init().

Puis l'utilisation se fait par la fonction fit() (recuit complet), ou pas à pas en initialisant d'abord le recuit (fonction reset()) puis en appelant la fonction fitStep() en boucle jusqu'à ce que isFinished() retourne true (recuit terminé).

Plusieurs modes de recuit sont disponibles:

  • METROPOLIS: Algorithme de Metropolis simplifié. Pour chaque passe de recuit simulé, on essaie, pour chaque noeud du graphe à étiqueter, un changement aléatoire d'étiquette. L'ordre de passage des noeuds est aléatoire et change d'une fois sur l'autre. La température est abaissée après chaque passage de tous les noeuds (sans attendre stabilisation comme dans l'algorithme original de Metropolis).
  • GIBBS: Algorithme du Gibbs Sampler. A chaque passe, chaque clique est traitée dans un ordre aléatoire. (on travaille sur les cliques, et pas sur les noeuds comme dans l'algorithme de Metropolis). Pour chaque clique, toutes les transformations possibles impliquant un nombre de noeuds maximal donné sont évaluées, puis le choix se fait aléatoirement parmi ces transformations en fonction de la probabilité de chacune.
  • ICM: Mode déterministe. L'ICM fonctionne comme le Gibbs sampler (évaluations par cliques, configurations à plusieurs changements) sauf que le choix final n'est pas aléatoire, mais on prend systématiquement le choix le plus probable.
  • MPM: Maximum Posterior Marginal. Annealing is done at a constant temperature (ideally the critical temperature), using the Gibbs Sampler algorithm. When the process ends (after a determined number of iterations), each node is assigned the label which has been most taken during the annealing (most probable label). Then the process generally switches to ICM mode to end up in a coherent state in a satisfactory minimum.

Les modes Metropolis, Gibbs et MPM basculent vers le mode ICM en dessous d'un certain seuil de température, pour finir le recuit au plus vite dans le minimum local le plus proche.

Le recuit s'arrête lorsque la proportion du nombre de transformations acceptées par rapport au nombre proposé passe en dessous d'un seuil donné lui aussi.

On peut interroger l'état du système: température, nombres de changements proposés et acceptés, énergie actuelle, différence d'énergie entre le début du recuit et l'état actuel, différence d'énergie au cours de la dernière passe, etc. en utilisant les fonctions qui vont bien.

Definition at line 122 of file anneal.h.

Member Enumeration Documentation

◆ InitLabelsType

Enumerator
INITLABELS_NONE 

Pas d'initialisation des labels: prendre ceux qui y sont déjà

INITLABELS_VOID 
INITLABELS_RANDOM 

Definition at line 159 of file anneal.h.

◆ IterType

Enumerator
VERTEX 

Itération noeud par noeud, ordre aléatoire.

CLIQUE 

Itération clique par clique, ordre aléatoire.

CUSTOM 

Itération sur d'autres groupes de noeuds (je verrai + tard)

Definition at line 139 of file anneal.h.

◆ Mode

Enumerator
METROPOLIS 

Algorithme original de Métropolis.

GIBBS 

Gibbs Sampler.

ICM 

ICM (déterministe)

MPM 

MPM (Maximum Posterior Marginal)

SPECIAL 

Internal mode.

Definition at line 125 of file anneal.h.

◆ VoidMode

Enumerator
VOIDMODE_NONE 

Pas de mode void.

VOIDMODE_REGULAR 

Mode régulier.

VOIDMODE_STOCHASTIC 

Mode stochastique.

Definition at line 149 of file anneal.h.

Constructor & Destructor Documentation

◆ Anneal()

sigraph::Anneal::Anneal ( CGraph & cg,
MGraph & rg )

◆ ~Anneal()

virtual sigraph::Anneal::~Anneal ( )
virtual

Member Function Documentation

◆ addExtension()

void sigraph::Anneal::addExtension ( AnnealExtension * ae,
unsigned occurency = 20 )

◆ cGraph() [1/2]

CGraph & sigraph::Anneal::cGraph ( )
inline

Definition at line 249 of file anneal.h.

References _cgraph.

◆ cGraph() [2/2]

const CGraph & sigraph::Anneal::cGraph ( ) const
inline

Graphe à étiqueter.

Definition at line 248 of file anneal.h.

References _cgraph.

◆ checkStop()

void sigraph::Anneal::checkStop ( )

Teste le critère d'arrêt et fixe l'état correspondant.

◆ clear()

void sigraph::Anneal::clear ( )

Libère les structures allouées dans les graphes.

◆ deleteExtensions()

void sigraph::Anneal::deleteExtensions ( )

◆ deltaE()

double sigraph::Anneal::deltaE ( ) const
inline

Variation d'énergie du graphe depuis le début du recuit.

Definition at line 278 of file anneal.h.

References _deltaE.

◆ doubleDrawingLots()

bool sigraph::Anneal::doubleDrawingLots ( ) const
inline

Dit si on est en mode DoubleTirage, technologie © JeffProd'00, pour les passes void et extensions.

Definition at line 290 of file anneal.h.

References _doubleDrawingLots.

◆ energy()

double sigraph::Anneal::energy ( ) const
inline

Definition at line 282 of file anneal.h.

References _deltaE, and _initEnergy.

◆ fit()

void sigraph::Anneal::fit ( )

Effectue tout le recuit.

◆ fitStep()

void sigraph::Anneal::fitStep ( )

Effectue une passe de recuit.

◆ gibbsMaxTrans()

unsigned sigraph::Anneal::gibbsMaxTrans ( ) const
inline

Nombre max.

de transformations par groupe de noeuds dans le Gibbs Sampler (et l'ICM)

Definition at line 276 of file anneal.h.

References _gibbsMaxTrans.

Referenced by init().

◆ init()

void sigraph::Anneal::init ( Mode mode,
double temp,
double tmult,
double tICM,
double stopProp,
unsigned gibbsMaxTrans,
bool verbose = true,
IterType itType = VERTEX,
InitLabelsType voidInitialLabels = INITLABELS_RANDOM,
const std::string & voidLabel = "",
std::ostream * plotStream = 0,
unsigned niterBelowStopProp = 1 )

Fixe l'état initial.

Parameters
modeType de recuit (Anneal::METROPOLIS, Anneal::GIBBS ou Anneal::ICM)
tempTempérature initiale
tmultMultiplicateur de décroissance de température (entre 0 et 1)
tICMUn recuit METROPOLIS ou GIBBS passe en mode ICM quand la température atteint la température tICM
stopPropProportion de changements acceptés en dessous duquel le recuit s'arrête
gibbsMaxTransNombre max. de transformations à la fois dans une clique par l'algorithme du Gibbs Sampler et l'ICM
verbositySi {\tt true} (par défaut), affiche à chaque pas la température, le mode de recuit, la variation d'énergie du pas, les nombres de changements acceptés et proposés. Si {\tt false}, n'affiche rien.
itTypeType d'itération sur le graphe: types de groupes de noeuds et ordre de passage. Pour l'instant ça n'est utilisé qu'en modes ICM et Gibbs. Pour Metropolis on verra plus tard.
plotStreamstream dans lequel les énergies sont écrites à chaque pas de recuit, pour traçage de courbes. Si ce paramètre est laissé à 0, rien n'est écrit.

References gibbsMaxTrans(), INITLABELS_RANDOM, mode(), stopProp(), temp(), tICM(), VERTEX, and voidLabel().

◆ initialEnergy()

double sigraph::Anneal::initialEnergy ( ) const
inline

Definition at line 281 of file anneal.h.

References _initEnergy.

◆ isFinished()

bool sigraph::Anneal::isFinished ( ) const
inline

Retourne true si le recuit est fini.

Definition at line 262 of file anneal.h.

References _finished.

◆ iterType()

IterType sigraph::Anneal::iterType ( ) const
inline

Definition at line 285 of file anneal.h.

References _iterType.

◆ maxIterations()

unsigned sigraph::Anneal::maxIterations ( ) const

Maximum number of iterations before switching to next mode.

Especially useful in constant temperature modes such as MPM. The default is 0 and means no limit.

◆ maxTrans()

unsigned sigraph::Anneal::maxTrans ( ) const
inline

Nombre de transformations proposées au cours de la dernière passe.

Definition at line 273 of file anneal.h.

References _maxtrans.

◆ mode()

Mode sigraph::Anneal::mode ( ) const
inline

Mode courant.

Definition at line 256 of file anneal.h.

References _mode.

Referenced by init(), and setVoidMode().

◆ modeI()

Mode sigraph::Anneal::modeI ( ) const
inline

Mode de recuit initial.

Definition at line 254 of file anneal.h.

References _modeI.

◆ MPMUnrecordedIterations()

unsigned sigraph::Anneal::MPMUnrecordedIterations ( ) const

Number of MPM steps before labels stats are recorded.

Useful to wait a kind of stabilization before recording labels stats

◆ nIter()

unsigned sigraph::Anneal::nIter ( ) const
inline

Nb d'itérations de recuit effectuées.

Definition at line 287 of file anneal.h.

References _niter.

◆ nTrans()

unsigned sigraph::Anneal::nTrans ( ) const
inline

Nombre de transformations acceptées au cours de la dernière passe.

Definition at line 271 of file anneal.h.

References _ntrans.

◆ processAllPotentials()

double sigraph::Anneal::processAllPotentials ( )

Calcule les potentiels de toutes les cliques.

Cette fonction est utilisée à l'initialisation, ou pour calculer l'énergie totale du graphe

Returns
énergie totale du graphe

◆ processPotentials()

void sigraph::Anneal::processPotentials ( const std::set< Vertex * > & vertices,
std::vector< EnergyField > & en )

Calcule les différentes énergies des transitions possibles d'un groupe de noeuds, en Gibbs Sampler ou en ICM.

Cette fonction efface le vecteur et le re-remplit

◆ reset()

void sigraph::Anneal::reset ( )

Revient aux conditions initiales.

◆ rGraph() [1/2]

MGraph & sigraph::Anneal::rGraph ( )
inline

Definition at line 252 of file anneal.h.

References _mgraph.

◆ rGraph() [2/2]

const MGraph & sigraph::Anneal::rGraph ( ) const
inline

Graphe modèle.

Definition at line 251 of file anneal.h.

References _mgraph.

◆ setAllowThreads()

void sigraph::Anneal::setAllowThreads ( bool )

enables or disables the use of multiple threads during annealing.

When enabled, multiple threads will only be used on platforms that support such a feature (threads and thread-safe reference counters), and which have multiple CPUs. In such case, one thread by CPU will be used. Be warned that there will not necessarily be a large benefit for it since threads synchronization will use a significant overhead and bottlenecks. On a bi-Xeon Linux with hyperthreading enabled, I ususally don't get more than 40-50% speedup for 4 logical CPUs (but 2 physical CPUs are actually present). On a bi-G5 Mac, I get basically almost no speed improvement.

◆ setDoubleDrawingLots()

void sigraph::Anneal::setDoubleDrawingLots ( bool t)
inline

Definition at line 291 of file anneal.h.

References _doubleDrawingLots.

◆ setMaxIterations()

void sigraph::Anneal::setMaxIterations ( unsigned n)

◆ setMPMUnrecordedIterations()

void sigraph::Anneal::setMPMUnrecordedIterations ( unsigned n)

◆ setVoidMode()

void sigraph::Anneal::setVoidMode ( VoidMode mode,
unsigned occurency = 0 )

Mode "void": essais de configs où tous les labels sont remplacés par void.

Parameters
modeVOIDMODE_NONE: désactivé; VOIDMODE_REGULAR: essais réguliers, une fois sur occurency; VOIDMODE_STOCHASTIC: essais irréguliers, avec probabilité 1/occurency
occurencypériodicité de la passe en mode "void"

References mode().

◆ stepDeltaE()

double sigraph::Anneal::stepDeltaE ( ) const
inline

Variation d'énergie du graphe à la dernière passe.

Definition at line 280 of file anneal.h.

References _stepDeltaE.

◆ stepGibbs()

void sigraph::Anneal::stepGibbs ( )

Effectue une passe en mode Gibbs Sampler.

◆ stepICM()

void sigraph::Anneal::stepICM ( )

Effectue une passe en mode ICM déterministe.

◆ stepMetropolis()

void sigraph::Anneal::stepMetropolis ( )

Effectue une passe en mode Métropolis.

◆ stepVoid()

void sigraph::Anneal::stepVoid ( )

Effectue une passe en mode Void (essais de configs ou tout un label est enlevé)

◆ stopProp()

double sigraph::Anneal::stopProp ( ) const
inline

Proportion de transformations acceptées en dessous de laquelle on arrête le recuit.

Definition at line 269 of file anneal.h.

References _stopProp.

Referenced by init().

◆ temp()

double sigraph::Anneal::temp ( ) const
inline

Température courante.

Definition at line 260 of file anneal.h.

References _temp.

Referenced by init().

◆ tempI()

double sigraph::Anneal::tempI ( ) const
inline

Température initiale.

Definition at line 258 of file anneal.h.

References _tempI.

◆ threadsAllowed()

bool sigraph::Anneal::threadsAllowed ( ) const

◆ tICM()

double sigraph::Anneal::tICM ( ) const
inline

Température de passage en ICM.

Definition at line 266 of file anneal.h.

References _tICM.

Referenced by init().

◆ tMult()

double sigraph::Anneal::tMult ( ) const
inline

Multiplicxateur de température.

Definition at line 264 of file anneal.h.

References _tmult.

◆ verbosity()

bool sigraph::Anneal::verbosity ( ) const
inline

dit si les affichages sont autorisés ou interdits

Definition at line 284 of file anneal.h.

References _verbose.

◆ voidLabel()

const std::string & sigraph::Anneal::voidLabel ( ) const
inline

Definition at line 292 of file anneal.h.

References _voidLabel.

Referenced by init().

Member Data Documentation

◆ _annealExtensions

std::vector<AnnealExtension *> sigraph::Anneal::_annealExtensions
protected

Definition at line 352 of file anneal.h.

◆ _cgraph

CGraph& sigraph::Anneal::_cgraph
protected

Graphe à étiqueter.

Definition at line 322 of file anneal.h.

Referenced by cGraph(), and cGraph().

◆ _currentNiterBelowStopProp

unsigned sigraph::Anneal::_currentNiterBelowStopProp
protected

Definition at line 356 of file anneal.h.

◆ _deltaE

double sigraph::Anneal::_deltaE
protected

Definition at line 341 of file anneal.h.

Referenced by deltaE(), and energy().

◆ _doubleDrawingLots

bool sigraph::Anneal::_doubleDrawingLots
protected

Definition at line 354 of file anneal.h.

Referenced by doubleDrawingLots(), and setDoubleDrawingLots().

◆ _extensionPassOccurency

unsigned sigraph::Anneal::_extensionPassOccurency
protected

Definition at line 353 of file anneal.h.

◆ _finished

bool sigraph::Anneal::_finished
protected

Definition at line 333 of file anneal.h.

Referenced by isFinished().

◆ _gibbsMaxTrans

unsigned sigraph::Anneal::_gibbsMaxTrans
protected

Definition at line 339 of file anneal.h.

Referenced by gibbsMaxTrans().

◆ _initEnergy

double sigraph::Anneal::_initEnergy
protected

Definition at line 342 of file anneal.h.

Referenced by energy(), and initialEnergy().

◆ _initialLabelsType

InitLabelsType sigraph::Anneal::_initialLabelsType
protected

Definition at line 348 of file anneal.h.

◆ _iterType

IterType sigraph::Anneal::_iterType
protected

Definition at line 344 of file anneal.h.

Referenced by iterType().

◆ _maxtrans

unsigned sigraph::Anneal::_maxtrans
protected

Definition at line 338 of file anneal.h.

Referenced by maxTrans().

◆ _mgraph

MGraph& sigraph::Anneal::_mgraph
protected

Graphe modèle.

Definition at line 324 of file anneal.h.

Referenced by rGraph(), and rGraph().

◆ _mode

Mode sigraph::Anneal::_mode
protected

Mode courant.

Definition at line 328 of file anneal.h.

Referenced by mode().

◆ _modeI

Mode sigraph::Anneal::_modeI
protected

Mode initial.

Definition at line 326 of file anneal.h.

Referenced by modeI().

◆ _niter

unsigned sigraph::Anneal::_niter
protected

Definition at line 346 of file anneal.h.

Referenced by nIter().

◆ _niterBelowStopProp

unsigned sigraph::Anneal::_niterBelowStopProp
protected

Definition at line 355 of file anneal.h.

◆ _ntrans

unsigned sigraph::Anneal::_ntrans
protected

Definition at line 337 of file anneal.h.

Referenced by nTrans().

◆ _plotStream

std::ostream* sigraph::Anneal::_plotStream
protected

Definition at line 347 of file anneal.h.

◆ _sgProvider

SGProvider* sigraph::Anneal::_sgProvider
protected

Definition at line 345 of file anneal.h.

◆ _stepDeltaE

double sigraph::Anneal::_stepDeltaE
protected

Definition at line 340 of file anneal.h.

Referenced by stepDeltaE().

◆ _stopProp

double sigraph::Anneal::_stopProp
protected

Definition at line 336 of file anneal.h.

Referenced by stopProp().

◆ _temp

double sigraph::Anneal::_temp
protected

Température courante.

Definition at line 332 of file anneal.h.

Referenced by temp().

◆ _tempI

double sigraph::Anneal::_tempI
protected

Température initiale.

Definition at line 330 of file anneal.h.

Referenced by tempI().

◆ _tICM

double sigraph::Anneal::_tICM
protected

Definition at line 335 of file anneal.h.

Referenced by tICM().

◆ _tmult

double sigraph::Anneal::_tmult
protected

Definition at line 334 of file anneal.h.

Referenced by tMult().

◆ _verbose

bool sigraph::Anneal::_verbose
protected

Definition at line 343 of file anneal.h.

Referenced by verbosity().

◆ _voidLabel

std::string sigraph::Anneal::_voidLabel
protected

Definition at line 349 of file anneal.h.

Referenced by voidLabel().

◆ _voidmode

VoidMode sigraph::Anneal::_voidmode
protected

Definition at line 350 of file anneal.h.

◆ _voidoccurency

unsigned sigraph::Anneal::_voidoccurency
protected

Definition at line 351 of file anneal.h.


The documentation for this class was generated from the following file: