Genetic Algorithms
A genetic algorithm can be really easy to implement. I made it a little harder for myself by creating a generic library in stead of a domain specific algorithm for some specific problem. My aim is to build tools to be used again. What was implemented:
What was not implemented:
Actually, this implementation is generic, but very limited. The possibilities of extending and modifying a genetic algorithm are large. I made a consideration between studying long on this subject to gain deeper insight in its intricacies, and moving on to other subjects and I chose the latter, because its more important to me now to gain a wide understanding of available AI techniques. I do believe that my architecture may be extended without to much hardship. Remarks
Sample use
This sample solves the n-Queens problem. As you can see, the domain specific class takes up most of the space. class CQueenGenome: public CGeneticGenome { protected: int n; int *y; public: CQueenGenome(int new_n) { n = new_n; y = new int[n]; } ~CQueenGenome(){ delete[] y; } /// create a new genome, no randomization is required virtual CGeneticGenome *NewGenome(){ return new CQueenGenome(n); } /// create default (random) values for the genes virtual void Initialize() { for (int i=0; i<n; i++) MutateGene(i); } /// set the length (i.e. the number of genes) virtual void SetLength(int NewLength){} /// return the length virtual int GetLength(void){ return n; } /// copy gene at position Pos to Child at pos ChildPos virtual void CopyGene(int Pos, CGeneticGenome *Child, int ChildPos) { ((CQueenGenome *)Child)->y[ChildPos] = y[Pos]; } /// is this genome equal to Genome virtual bool Equals(CGeneticGenome *Genome) { for (int i=0; i<n; i++) { if (y[i] != ((CQueenGenome *)Genome)->y[i]) return false; } return true; } /// store a random value in the gene virtual void MutateGene(int GeneIndex) { int old_y, new_y; old_y = y[GeneIndex]; do { new_y = CMath::GetRandomInt(0, n-1); } while (new_y == old_y); y[GeneIndex] = new_y; } /// calculate and return the fitness of this genome virtual void CalculateFitness(void) { int piece, piece_x, piece_y, pos_x, pos_y; Fitness = 0.0f; for(piece=0; piece<n; piece++) { piece_x = piece; piece_y = y[piece]; // horizontal right for(pos_x = piece_x+1, pos_y = piece_y; pos_x < n; pos_x++) { if (y[pos_x] == pos_y){ Fitness--; } } // horizontal left for(pos_x = piece_x-1, pos_y = piece_y; pos_x >= 0; pos_x--) { if (y[pos_x] == pos_y){ Fitness--; } } // right up for(pos_x = piece_x+1, pos_y = piece_y+1; (pos_y < n) && (pos_x < n); pos_y++, pos_x++) { if (y[pos_x] == pos_y){ Fitness--; } } // right down for(pos_x = piece_x+1, pos_y = piece_y-1; (pos_y >= 0) && (pos_x < n); pos_y--, pos_x++) { if (y[pos_x] == pos_y){ Fitness--; } } // left up for(pos_x = piece_x-1, pos_y = piece_y+1; (pos_y < n) && (pos_x >= 0); pos_y++, pos_x--) { if (y[pos_x] == pos_y){ Fitness--; } } // left down for(pos_x = piece_x-1, pos_y = piece_y-1; (pos_y >= 0) && (pos_x >= 0); pos_y--, pos_x--) { if (y[pos_x] == pos_y){ Fitness--; } } } Fitness = 1.0f + (Fitness / (2 * n)); if (Fitness < 0.0) Fitness = 0.0f; } /// is the genome fit enough to stop evolving? virtual bool IsFitEnough(void) { return (Fitness == 1.0f); } virtual const CString ToString(void) const { CString String; for (int i=0; i<n; i++) { String += y[i]; String += ' '; } return String; } }; int main(int argc, char* argv[]) { // genetic algorithms CQueenGenome QueenGenome(100); CGeneticModel GeneticModel(&QueenGenome); // this part is optional, it changes some settings of the algorithm // for educational purposes, the default values are set here, just to // show how it can be done GeneticModel.ClearParentSelectionTypes(); GeneticModel.AddParentSelectionType(PARENTSELECTIONTYPE_RANK); GeneticModel.AddParentSelectionType(PARENTSELECTIONTYPE_RANK); GeneticModel.AddParentSelectionType(PARENTSELECTIONTYPE_RANK); GeneticModel.AddParentSelectionType(PARENTSELECTIONTYPE_RANK); GeneticModel.AddParentSelectionType(PARENTSELECTIONTYPE_TOURNAMENT); GeneticModel.ClearCrossoverTypes(); GeneticModel.AddCrossoverType(CROSSOVERTYPE_FIXEDLENGTH_ONEPOINT); GeneticModel.ClearMutationTypes(); GeneticModel.AddMutationType(MUTATIONTYPE_CHANGEGENE); GeneticModel.SetPopulationSize(100, 10, 10, -1); GeneticModel.SetMutationRate(1.0f); GeneticModel.Initialize(); // evolve the model until it found a fit enough genome GeneticModel.Evolve(); // print out the genome's value CGeneticGenome *FittestGenome = GeneticModel.GetFittestGenome(); printf("Genome %s\n", FittestGenome->ToString().GetBuffer()); } Links
|