Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

/magnus/back_end/Genetic/include/GACPforORGSolver.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: GACPforORGSolver.h,v 1.2 2000/10/07 18:36:59 bormotov Exp $
00003  */
00004  
00005 // Contents: Declaration of classes GAConjProblemForORGroupSolver, GAConjProblemForORGroupConjecture
00006 //
00007 // Principal Author: Alexander Ushakov
00008 //
00009 // Status: in progress
00010 //
00011 // Revision History:
00012 //
00013 
00014 #ifndef _GACPFORORGSOLVER_H_
00015 #define _GACPFORORGSOLVER_H_
00016 
00017 #include "Word.h"
00018 #include "OneRelatorGroup.h"
00019 #include "Associations.h"
00020 #include "RandomNumbers.h"
00021 
00022 
00023 //---------------------------------------------------------------------------//
00024 //----------------------- GACPforORGSolverChromosome ------------------------//
00025 //---------------------------------------------------------------------------//
00026 
00027 
00028 class GACPforORGSolverChromosome
00029 {
00030  public:
00031   GACPforORGSolverChromosome( const Word& c, bool d ) : deg(d) , con(c) { }
00032   
00033   bool getDeg( ) const { return deg; }
00034   
00035  protected:
00036   Word con;
00037   // conjugator
00038   bool deg;
00039   // degree of the relator 
00040   // false: -1
00041   // true :  1
00042   
00043   friend class GACPforORGSolverGene;
00044 };
00045 
00046 
00047 
00048 //---------------------------------------------------------------------------//
00049 //------------------------ GACPforORGSolverGene -----------------------------//
00050 //---------------------------------------------------------------------------//
00051 
00052 
00053 
00054 class GACPforORGSolverGene
00055 {
00056  public:
00057 
00058   /////////////////////////////////////////////////////////
00059   //                                                     //
00060   //  Constructors                                       //
00061   //                                                     //
00062   /////////////////////////////////////////////////////////
00063 
00064   GACPforORGSolverGene( OneRelatorGroup& group , const Word& w1 , const Word& w2 );
00065   GACPforORGSolverGene( const GACPforORGSolverGene& g );
00066   GACPforORGSolverGene& operator = ( const class GACPforORGSolverGene& g );
00067   ~GACPforORGSolverGene( );
00068 
00069   
00070   /////////////////////////////////////////////////////////
00071   //                                                     //
00072   //  Accessors                                          //
00073   //                                                     //
00074   /////////////////////////////////////////////////////////
00075 
00076   double fitness( );
00077   bool noConj( ) const { return exp==NOONE; }
00078 
00079   Word getWord1( ) const { return theWord1; }
00080   Word getWord2( ) const { return theWord2; }
00081 
00082 
00083   bool getHasShorterWords( ) { bool res = hasShorterWords; hasShorterWords = false; return res; }
00084   bool getHasConjecture( )   const { return hasConjecture; }
00085   Word getConjectureWord( )  const { return conjectureWord; } 
00086 
00087   static Word randomWord( int gens , int wLen );
00088   static double proximity( const Word& W1 , const Word& W2 , int* c1=0 , int* c2=0 );
00089   // proximity of two words. This function invoked by fitness function only.
00090   // Currently the results type is integer. Return a value that show 
00091   // how one (cyclically) word likes to another.
00092 
00093   GACPforORGSolverChromosome* randomChromosome( bool deg ) const;
00094 
00095 
00096 public:
00097 
00098   /////////////////////////////////////////////////////////
00099   //                                                     //
00100   //  Reproduction functions                             //
00101   //                                                     //
00102   /////////////////////////////////////////////////////////
00103 
00104 
00105   void check( );
00106   // check exp. sum of generators in two given words 
00107   // and make some mutation to set it equal (by the relator)
00108 
00109   // next functions invoke by Solver::reproduction( )
00110 
00111   bool mutation( );
00112 
00113   bool permutation( );
00114   // permutation of any two chromosomes in chromosomes table
00115   // doesn't use currently
00116 
00117   friend bool crossover( GACPforORGSolverGene& g1 , GACPforORGSolverGene& g2 );
00118   // this function changes places of two chromosomes in g1 and in g2
00119   // if curExp!=ANY => the degree of chromosomes must be equal
00120 
00121 
00122 private:
00123 
00124   /////////////////////////////////////////////////////////
00125   //                                                     //
00126   //  Data members                                       //
00127   //                                                     //
00128   /////////////////////////////////////////////////////////
00129 
00130   Word theWord1;             
00131   // first word
00132   Word theWord2;             
00133   // second word (algorithm deals with this word), this word isn't shorter than previous one
00134   OneRelatorGroup& theGroup; 
00135   // group
00136 
00137   static UniformRandom r;
00138 
00139   double fit;                //current fitness of gene, or -1 if it doesn't exist jet
00140   int nChr;                  //number of chromosomes  (not using field currently)
00141 
00142 
00143   /////////////////////////////////////////////////////////
00144   //                                                     //
00145   //  Chromosome table and functions deals with it       //
00146   //                                                     //
00147   /////////////////////////////////////////////////////////
00148 
00149   //Chromosome table has got theWord2.length() columns
00150 
00151   void resize( unsigned pos , unsigned newsize );
00152   GACPforORGSolverChromosome*** chromosomes; // pointer to chromosomes table
00153   unsigned* lengthes;        // lengthes of each column in chromosomes table
00154   unsigned* sizes;           // sizes of column 
00155   static unsigned jumpSize;  // number of increasing columns in table
00156 
00157   void clear( );             
00158   // clear the chromosome table
00159 
00160 
00161   void delChr( unsigned p1, unsigned p2 );
00162   void addChr( GACPforORGSolverChromosome* chr , unsigned p1, unsigned p2 );
00163   // add and delete chromosome from the table
00164 
00165   enum _FindPos{ ALL=0, POSITIVE=1, NEGATIVE=2};
00166   void findPos( _FindPos tp, unsigned num , unsigned& p1 , unsigned& p2 ) const;
00167 
00168  private:
00169 
00170   /////////////////////////////////////////////////////////
00171   //                                                     //
00172   //  Type of gene                                       //
00173   //                                                     //
00174   /////////////////////////////////////////////////////////
00175 
00176   bool hasConjecture;
00177   // this variable sets if algoritm obtained words with a big reduce
00178   Word conjectureWord;
00179   // result of the big reduce, it means just if variable "hasConjecture" sets
00180   // two word W1 and W2 with a big reduce - it means (in this version of algorithm) 
00181   // length(W1*W2) < ( length(W1)+length(W2) ) / 2
00182 
00183   bool hasShorterWords;
00184   // if algorithm obtained shorter words, it sets to true
00185 
00186   /////////////////////////////////////////////////////////
00187   //                                                     //
00188   //  Exponential sum of degree of chromosomes in table  //
00189   //                                                     //
00190   /////////////////////////////////////////////////////////
00191 
00192   int exp;
00193   int curExp;
00194   // exponetial sum of the RELATOR
00195   // these members must be equal
00196   
00197   int getExp( );
00198   // compute a number (exp), exponetial sum of RELATOR must be equal with
00199   
00200   static const int ANY;
00201   static const int NOONE;
00202   //const values for curExp
00203   //ANY => it means any number (exp may be equal to any integer value)
00204   //NOONE => it impossible to set exp to curExp and words are not conjugates
00205 
00206   //friend class GAConjProblemForORGroupSolver;
00207 };
00208 
00209 
00210 
00211 //---------------------------------------------------------------------------//
00212 //------------------- GAConjProblemForORGroupSolver -------------------------//
00213 //---------------------------------------------------------------------------//
00214 
00215 
00216 
00217 class GAConjProblemForORGroupSolver
00218 {
00219  public:
00220 
00221   /////////////////////////////////////////////////////////////////
00222   //                                                             //
00223   // Constructors:                                               //
00224   //                                                             //
00225   /////////////////////////////////////////////////////////////////
00226 
00227   GAConjProblemForORGroupSolver( const OneRelatorGroup& group , const Word& W1 , const Word& W2 , bool createFile = true , bool cp = true );
00228 
00229   ~GAConjProblemForORGroupSolver( );
00230 
00231   GAConjProblemForORGroupSolver operator = ( const GAConjProblemForORGroupSolver& solver ) ;
00232   // hidden
00233 
00234  protected:
00235 
00236   GAConjProblemForORGroupSolver( const OneRelatorGroup& group , const Word& W1 , const Word& W2 , File* f );
00237   // this constructor used for conjectures only
00238 
00239  public:
00240 
00241   
00242 
00243   //////////////////////////////////////////////////////////////////
00244   //                                                              //
00245   // Accessors:                                                   //
00246   //                                                              //
00247   //////////////////////////////////////////////////////////////////
00248 
00249   bool isConj( );
00250 
00251   int getNumberOfIterations( ) const { return theIter1; }
00252   // get total number of iterations done by Solver::isConj and internal conjectures
00253 
00254   Chars getFileName( ) const { 
00255     if( !file )
00256       error( "GAConjProblemForORGroupSolver::getFileName" );
00257     return file->getFileName(); 
00258   }
00259 
00260 
00261   //////////////////////////////////////////////////////////////////
00262   //                                                              //
00263   //  Internal functions                                          //
00264   //                                                              //
00265   //////////////////////////////////////////////////////////////////
00266 
00267  public:
00268 
00269   static int rnd1( int max );  
00270   static int roulette( double d1 , double d2 );
00271   static int roulette( int num , double* d);
00272   
00273   static Word greedyReduce( const OneRelatorGroup& group , const Word& word );
00274   static bool oneGreedyReduce( const OneRelatorGroup& group , Word& w );
00275   static void insert( Word& dst , const Word& src , int pos);
00276 
00277  protected:
00278 
00279 
00280   void checkImprovementTime( );
00281 
00282   int reproduction( );
00283   bool tournament( GACPforORGSolverGene& gene );
00284   int selectGene( ) const;
00285 
00286 
00287   // I invoke this function when get more shorter words, in the constructor 
00288   // and if there is so long time since last improvement
00289   // It resets pair of words
00290   void toStart( const Word& W1 , const Word& W2 );
00291 
00292  protected:
00293 
00294   //////////////////////////////////////////////////////////////////
00295   //                                                              //
00296   //  Data members                                                //
00297   //                                                              //
00298   //////////////////////////////////////////////////////////////////
00299 
00300   static double prob[2][3];
00301   //two sets of probability of mutation, permutation and crossover
00302 
00303   bool conjProblem;
00304   // it it sets then it solves conjugacy problem
00305   // else solves word problem
00306 
00307   int lastImprovement;
00308   //
00309  
00310   int fitnessRate;
00311 
00312   int theIter1, theIter2;
00313   // number of iterations
00314 
00315   double bestFit;
00316   // best fitness value have ever obtained 
00317 
00318   File* file;
00319   bool deleteFile;
00320   // session file
00321 
00322   //////////////////////////////////////////////////////////////////
00323   //                                                              //
00324   //  Checked words                                               //
00325   //                                                              //
00326   //////////////////////////////////////////////////////////////////
00327 
00328   AssociationsOf< Word , int > checkedWords;
00329 
00330 
00331   //////////////////////////////////////////////////////////////////
00332   //                                                              //
00333   //  Genes                                                       //
00334   //                                                              //
00335   //////////////////////////////////////////////////////////////////
00336 
00337   int numGenes;
00338   GACPforORGSolverGene** genes;
00339   GACPforORGSolverGene *newGene[2];
00340 
00341 
00342   //////////////////////////////////////////////////////////////////
00343   //                                                              //
00344   //  Algebraic objects                                           //
00345   //                                                              //
00346   //////////////////////////////////////////////////////////////////
00347 
00348   OneRelatorGroup theGroup;
00349   Word theWord1;
00350   Word theWord2;
00351   
00352   static const int NOCONJ;
00353 };
00354 
00355 
00356 //---------------------------------------------------------------------------//
00357 //----------------- GAConjProblemForORGroupConjecture -----------------------//
00358 //---------------------------------------------------------------------------//
00359 
00360 
00361 class GAConjProblemForORGroupConjecture : private GAConjProblemForORGroupSolver
00362 {
00363  private:
00364   GAConjProblemForORGroupConjecture( const OneRelatorGroup& group , const Word& W , File* f ) : 
00365     GAConjProblemForORGroupSolver( group , Word( ) , W , f ) { }
00366 
00367   bool isConj( int maxIter , int& doneIter );
00368 
00369   friend class GAConjProblemForORGroupSolver;
00370 };
00371 
00372 
00373 #endif

Generated at Tue Jun 19 09:49:35 2001 for Magnus Classes by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001