Similarity-based Grouping Genetic Algorithm Chromosome. More...

#include <sgga.h>

Inheritance diagram for RChromoSG< cInst, cChromo, cThreadData, cGroup, cObj >:
[legend]
Collaboration diagram for RChromoSG< cInst, cChromo, cThreadData, cGroup, cObj >:
[legend]

Public Member Functions

 RChromoSG (cInst *inst, size_t id)
 
virtual void Init (cThreadData *thData)
 
virtual void Evaluate (void)
 
double ReAllocate (void)
 
size_t CalcNewProtosNb (void)
 
void DoKMeans (void)
 
void DivideWorstObjects (void)
 
void MergeBestGroups (void)
 
void TreatSocialObjects (void)
 
void kMeansOptimisation (void)
 
virtual void Optimisation (void)
 
virtual void LocalOptimisation (void)
 
bool SameGroup (size_t obj1, size_t obj2) const
 
virtual void Copy (const cChromo &chromo)
 
double GetSimJ (void)
 
double GetAgreementCriterion (void) const
 
double GetDisagreementCriterion (void) const
 
double GetFi (void) const
 
double GetFiPlus (void) const
 
double GetFiMinus (void) const
 
virtual ~RChromoSG (void)
 
- Public Member Functions inherited from RChromoG< cInst, cChromo, RFitnessSG, cThreadData, cGroup, cObj >
 RChromoG (cInst *inst, size_t id)
 
virtual void Clear (void)
 
virtual void RandomConstruct (void)
 
virtual void Crossover (cChromo *parent1, cChromo *parent2)
 
virtual void Mutation (void)
 
virtual void Inversion (void)
 
virtual void Modify (void)
 
virtual void Verify (void)
 
virtual ~RChromoG (void)
 
- Public Member Functions inherited from RChromo< cInst, cChromo, cFit, cThreadData >
 RChromo (cInst *inst, size_t id)
 
virtual void StrongMutation (void)
 
virtual void Print (void)
 
virtual ~RChromo (void)
 
- Public Member Functions inherited from RGroups< cGroup, cObj, cChromo >
 RGroups (RCursor< cObj > objs, const size_t max)
 
void Init (void)
 
void ClearGroups (void)
 
cGroup * ReserveGroup (size_t id=cNoRef)
 
void ReleaseGroup (cGroup *group)
 
void InsertObj (cGroup *to, cObj *obj)
 
void InsertObjs (const cGroup *from, cGroup *to)
 
void DeleteObj (cGroup *from, cObj *obj)
 
void DeleteObjs (cGroup *grp)
 
cGroup * GetGroup (size_t id) const
 
cGroup * GetGroup (const cObj *obj) const
 
cObj * GetObj (size_t idx) const
 
RCursor< cObj > GetObjs (const RGroup< cGroup, cObj, cChromo > &grp) const
 
void CopyGrouping (const RGroups &grps)
 
void ComputeOrd (void)
 
bool SameGroupment (const RGroups *grps) const
 
RCursor< cObj > GetObjsCursor (void) const
 
RCursor< cGroup > GetUsedGroups (void) const
 
double ComputeAdjustedRandIndex (const cChromo &groups) const
 
virtual ~RGroups (void)
 
- Public Member Functions inherited from RContainer< cGroup, true, false >
 RContainer (size_t m, size_t i=0)
 
 RContainer (const RContainer< cGroup, true, false > &src)
 
 RContainer (const RContainer< cGroup, false, false > &src)
 
int Compare (const RContainer< cGroup, true, false > &) const
 
size_t GetNb (void) const
 
size_t GetMaxPos (void) const
 
size_t GetMaxNb (void) const
 
size_t GetIncNb (void) const
 
bool VerifyIndex (size_t idx) const
 
void VerifyTab (size_t max=0)
 
void Clear (size_t m=0, size_t i=0, bool force=false)
 
void ReOrder (int sortOrder(const void *, const void *), size_t min, size_t max)
 
void ReOrder (int sortOrder(const void *, const void *))
 
void ReOrder (void)
 
void Exchange (size_t pos1, size_t pos2)
 
void Shift (size_t idx, bool reverse)
 
void Transfer (RContainer< cGroup, a, o > &src)
 
RContaineroperator= (const RContainer< cGroup, true, false > &src)
 
RContaineroperator= (const RContainer< cGroup, false, false > &src)
 
void Copy (const RContainer< cGroup, a, false > &src)
 
RContaineroperator+= (const RContainer< cGroup, a, o > &src)
 
size_t GetIndex (const TUse &tag, bool &find, size_t min=0, size_t max=0) const
 
bool IsIn (const TUse &tag, bool sortkey, size_t min=0, size_t max=0) const
 
bool IsIn (const TUse &tag, size_t min=0, size_t max=0) const
 
const cGroup * operator[] (size_t idx) const
 
cGroup * operator[] (size_t idx)
 
const cGroup * GetPtrAt (size_t idx) const
 
cGroup * GetPtrAt (size_t idx)
 
cGroup * GetPtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0) const
 
cGroup * GetPtr (const TUse &tag, size_t min=0, size_t max=0) const
 
cGroup * GetInsertPtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0)
 
cGroup * GetInsertPtr (const TUse &tag, size_t min=0, size_t max=0)
 
cGroup * GetInsertPtrAt (const TUse &tag, size_t pos)
 
RContainer< cGroup, false,
false > * 
GetPtrs (const TUse &tag, size_t min=0, size_t max=0) const
 
size_t GetTab (const void **tab, size_t min=0, size_t max=0) const
 
size_t GetTab (void **tab, size_t min=0, size_t max=0)
 
size_t GetTab (const cGroup **tab, size_t min=0, size_t max=0) const
 
size_t GetTab (cGroup **tab, size_t min=0, size_t max=0)
 
void InsertPtrAt (cGroup *ins, size_t pos, bool del)
 
void InsertPtrAt (cGroup *ins, size_t pos)
 
void InsertPtr (cGroup *ins, bool del=false, size_t min=0, size_t max=0)
 
void DeletePtrAt (size_t pos, bool shift, bool del)
 
void DeletePtrAt (size_t pos, bool shift)
 
void DeletePtrAt (size_t pos)
 
void DeletePtr (const TUse &tag, bool sortkey, bool del, size_t min=0, size_t max=0)
 
void DeletePtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0)
 
void DeletePtr (const TUse &tag, size_t min=0, size_t max=0)
 
void Inter (const iRContainer< cGroup > &src1, const iRContainer< cGroup > &src2)
 
void Union (const iRContainer< cGroup > &src1, const iRContainer< cGroup > &src2)
 
virtual ~RContainer (void)
 
- Public Member Functions inherited from iRContainer< C >
size_t GetNb (void) const
 
size_t GetMaxPos (void) const
 
size_t GetMaxNb (void) const
 
size_t GetIncNb (void) const
 
bool VerifyIndex (size_t idx) const
 
void VerifyTab (size_t max=0)
 
void Clear (size_t m=0, size_t i=0, bool force=false)
 
void ReOrder (int sortOrder(const void *, const void *), size_t min, size_t max)
 
void ReOrder (int sortOrder(const void *, const void *))
 
void ReOrder (void)
 
void Exchange (size_t pos1, size_t pos2)
 
void Shift (size_t idx, bool reverse)
 
void Transfer (iRContainer< C > &src)
 
iRContaineroperator= (const iRContainer< C > &src)
 
void Copy (const iRContainer< C > &src)
 
iRContaineroperator+= (const iRContainer< C > &src)
 
size_t GetIndex (bool order, const TUse &tag, bool &find, size_t min=0, size_t max=0) const
 
size_t GetIndex (const TUse &tag, bool &find, size_t min=0, size_t max=0) const
 
bool IsIn (const TUse &tag, bool sortkey, size_t min=0, size_t max=0) const
 
bool IsIn (const TUse &tag, size_t min=0, size_t max=0) const
 
const C * operator[] (size_t idx) const
 
C * operator[] (size_t idx)
 
const C * GetPtrAt (size_t idx) const
 
C * GetPtrAt (size_t idx)
 
C * GetPtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0) const
 
C * GetPtr (const TUse &tag, size_t min=0, size_t max=0) const
 
C * GetInsertPtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0)
 
C * GetInsertPtr (const TUse &tag, size_t min=0, size_t max=0)
 
C * GetInsertPtrAt (const TUse &tag, size_t pos)
 
size_t GetTab (const void **tab, size_t min=0, size_t max=0) const
 
size_t GetTab (void **tab, size_t min=0, size_t max=0)
 
size_t GetTab (const C **tab, size_t min=0, size_t max=0) const
 
size_t GetTab (C **tab, size_t min=0, size_t max=0)
 
void InsertPtrAt (C *ins, size_t pos, bool del)
 
void InsertPtrAt (C *ins, size_t pos)
 
void InsertPtr (C *ins, bool del=false, size_t min=0, size_t max=0)
 
void DeletePtrAt (size_t pos, bool shift, bool del)
 
void DeletePtrAt (size_t pos, bool shift)
 
void DeletePtrAt (size_t pos)
 
void DeletePtr (const TUse &tag, bool sortkey, bool del, size_t min=0, size_t max=0)
 
void DeletePtr (const TUse &tag, bool sortkey, size_t min=0, size_t max=0)
 
void DeletePtr (const TUse &tag, size_t min=0, size_t max=0)
 
void Inter (const iRContainer< C > &src1, const iRContainer< C > &src2)
 
void Union (const iRContainer< C > &src1, const iRContainer< C > &src2)
 
virtual ~iRContainer (void)
 

Protected Attributes

R::RContainer< cGroup, false,
false > * 
ToDel
 
double CritSimJ
 
double CritAgreement
 
double CritDisagreement
 
double FiMinus
 
double FiPlus
 
double Fi
 
cObj ** thObjs1
 
size_t NbObjs1
 
cObj ** thObjs2
 
size_t NbObjs2
 
R::RContainer< cObj, false, false > Protos
 
R::RContainer< cObj, false, false > OldProtos
 
cChromo ** thTests
 
RPromKernelSC< cChromo > * thProm
 
RPromSol ** thSols
 
size_t MostSimilarGroup1
 
size_t MostSimilarGroup2
 
bool VerifyCentroids
 
- Protected Attributes inherited from RChromoG< cInst, cChromo, RFitnessSG, cThreadData, cGroup, cObj >
RGroupingHeuristic< cGroup,
cObj, cChromo > * 
Heuristic
 
- Protected Attributes inherited from RGroups< cGroup, cObj, cChromo >
RCursor< cObj > Objs
 
size_t MaxObjId
 
size_t * ObjectsAss
 
RContainer< cObj, false, false > ObjsAss
 
RContainer< cObj, false, false > ObjsNoAss
 
size_t * OrdObjectsAss
 
size_t * NewUsedId
 
- Protected Attributes inherited from iRContainer< C >
C ** Tab
 
size_t NbPtr
 
size_t MaxPtr
 
size_t LastPtr
 
size_t IncPtr
 

Additional Inherited Members

- Static Public Member Functions inherited from RContainer< cGroup, true, false >
static int SortOrder (const void *a, const void *b)
 
- Static Public Member Functions inherited from iRContainer< C >
static int SortOrder (const void *a, const void *b)
 
- Public Attributes inherited from RChromo< cInst, cChromo, cFit, cThreadData >
cInst * Instance
 
size_t Id
 
cFit * Fitness
 
bool ToEval
 
- Public Attributes inherited from RGroups< cGroup, cObj, cChromo >
RContainer< cGroup, false, false > Used
 
- Protected Member Functions inherited from iRContainer< C >
void Create (const iRContainer< C > &src)
 
iRContainerNormalCopy (const iRContainer< C > &src)
 
void DeepCopy (const iRContainer< C > &src)
 
iRContainerAdd (const iRContainer< C > &src)
 

Detailed Description

template<class cInst, class cChromo, class cThreadData, class cGroup, class cObj>
singleton R::RChromoSG< cInst, cChromo, cThreadData, cGroup, cObj >

Similarity-based Grouping Genetic Algorithm Chromosome.

The RChromoSG class provides a representation for a chromosome for the similarity-based grouping genetic algorithm.

Constructor & Destructor Documentation

RChromoSG ( cInst *  inst,
size_t  id 
)

Construct the chromosome.

Parameters
instThe instance of the problem.
idThe identifier of the chromosome.
virtual ~RChromoSG ( void  )
virtual

Destruct the chromosome.

Member Function Documentation

virtual void Init ( cThreadData *  thData)
virtual

Initialization of the chromosome.

Parameters
thDataPointer to the "thread-dependent" data.

Reimplemented from RChromoG< cInst, cChromo, RFitnessSG, cThreadData, cGroup, cObj >.

virtual void Evaluate ( void  )
virtual

Evaluation of the chromosome.

Reimplemented from RChromo< cInst, cChromo, cFit, cThreadData >.

double ReAllocate ( void  )

Reallocate the objects to the groups based on the different prototypes.

Returns
the average similarity between the objects and their prototype.
size_t CalcNewProtosNb ( void  )

Compute the number of new prototypes until the last K-Means iteration.

void DoKMeans ( void  )

Perform a K-Means on the chromosome.

void DivideWorstObjects ( void  )

Divide the group containing the two most dissimilar objects.

void MergeBestGroups ( void  )

Merge the two groups containing the two most similar centroids.

void TreatSocialObjects ( void  )

Treat the social objects, i.e. if these objects are alone in a group, put them in another group.

void kMeansOptimisation ( void  )

kMeans-based Optimization.

virtual void Optimisation ( void  )
virtual

Perform an optimization.

Reimplemented from RChromoG< cInst, cChromo, RFitnessSG, cThreadData, cGroup, cObj >.

virtual void LocalOptimisation ( void  )
virtual

Perform a local optimization.

Reimplemented from RChromoG< cInst, cChromo, RFitnessSG, cThreadData, cGroup, cObj >.

bool SameGroup ( size_t  obj1,
size_t  obj2 
) const

Do a mutation of the chromosome. Since the GCA seems to over-group, the mutation merge the two groups containing the most similar centroids. Look if two objects are in the same group or not.

Parameters
obj1Identifier of the first object.
obj2Identifier of the second object.
Returns
true if they are in the same group, else false.
virtual void Copy ( const cChromo &  chromo)
virtual

The assignment operator.

Parameters
chromoChromosome used as source.

Reimplemented from RChromoG< cInst, cChromo, RFitnessSG, cThreadData, cGroup, cObj >.

double GetSimJ ( void  )

Get the value of the 'J' measure.

Returns
double.
double GetAgreementCriterion ( void  ) const

Get the value of the agreement criterion for the chromosome.

Returns
double.
double GetDisagreementCriterion ( void  ) const

Get the value of the disagreement criterion for the chromosome.

Returns
double.
double GetFi ( void  ) const
Returns
Fi of the solution.
double GetFiPlus ( void  ) const
Returns
Fi+ of the solution.
double GetFiMinus ( void  ) const
Returns
Fi- of the solution.

Member Data Documentation

R::RContainer<cGroup,false,false>* ToDel
protected

Pointer to a container used to store the objects to delete.

double CritSimJ
protected

Value of the Similarity criterion "J" : (Average Similarity inside each group)/(Maximal similarity between centroids+2) .

double CritAgreement
protected

Value of the "Agreement" criterion.

double CritDisagreement
protected

Value of the "Disagreement" criterion.

double FiMinus
protected

Fi minus value.

double FiPlus
protected

Fi minus value.

double Fi
protected

Fi minus value.

cObj** thObjs1
protected

Temporary array of Objects (Thread dependent data).

size_t NbObjs1
protected

Number of objects in thObjs1.

cObj** thObjs2
protected

Temporary array of Objects (Thread dependent data).

size_t NbObjs2
protected

Number of objects in thObjs2.

R::RContainer<cObj,false,false> Protos
protected

Prototypes used for the KMeans.

R::RContainer<cObj,false,false> OldProtos
protected

Old prototypes used for the KMeans.

cChromo** thTests
protected

Test Chromosome (Thread dependent data).

RPromKernelSC<cChromo>* thProm
protected

PROMETHE Kernel used by the chromosome.

RPromSol** thSols
protected

Array of solutions to create in PROMETHEE Kernel.

size_t MostSimilarGroup1
protected

Identifier of the first of the two most similar centroid.

size_t MostSimilarGroup2
protected

Identifier of the second of the two most similar centroid.

bool VerifyCentroids
protected

Verify that the centroids are updated.