THE DESIGN AND DEVELOPMENT OF A GENERIC GENETIC ALGORITHM IN C++

The basic premise:

How this can be applied to every day problems:

1. It can be assigned a scalar fitness directly related to how close it is to the optimal solution for the search space and
   
   
2. Its �gene string� is in a form that can be crossed with another string of the same type while maintaining the integrity of both strings produced can be �evolved� using a genetic algorithm in this way:
   


1. A population of random �gene strings� is created.



2. Each string�s measure of fitness is determined.



3. Part of the population is selected probabilistically based on fitness and copied into the new generation.



4. Part of the population is selected probabilistically based on fitness and then is cross-bred.



5. The new generation is returned in place of the old one.



6. steps 2-5 are repeated until a �gene string� that meets the termination criterion is found.

The purpose of this project:

The design parameters

1. The program had to run in Borland C++ 4.5



2. The program had to be capable of handling user-defined types so long as they conformed to this template (Tree.h is a good example):
   
   class userClass{
   public:
   userClass( );
   ~userClass( ); //when necessary to free the memory taken by the object
   void go( int pos );
   userClass *cut( );
   void paste( userClass &auserClass );
   ..........
   ..........
   int numnodes( );
   const userClass &operator=( const userClass &auserClass );
   
   private:
   .........
   .........
   };
   
   userClass::userClass( )
   The class must have a default constructor which creates an empty instance of the object.
   
   userClass::~userClass( )
   When the default destructor is not sufficient to free all the memory allocated for the object, the class must include a destructor which does.
   
   userClass::void go(int pos)
   Moves the internal pointer of the class to the position pos between 0 and numnodes().
   
   userClass *userClass::cut( )
   Cuts the current instance of userClass at the position of the movable pointer and returns an instance of userClass containing the resultant piece. The movable pointer must stay in the same position.
   
   void userClass::paste(userClass &auserClass)
   Takes an instance of userClass, auserClass, created by the cut function and appends it to the current instance of userClass, having just undergone the cut function, at the point indicated by the movable pointer while maintaining the integrity of the current instance.
   
   int userClass::numnodes( )
   Returns the number of nodes or potential cut/paste points in this instance of userClass.
   
   const userClass &userClass::operator =(const userClass &auserClass)
   Makes the current instance of userClass an exact, entirely separate copy of auserClass.
   
   
3. The program had to handle populations of any size within the memory limitations of the computer on which it was run.



4. The program had to include functions that supported crossbreeding within the population.



5. The program had to, when given all appropriate functions and an input population that has been evaluated in a static environment and that has individuals with different fitness values, produce an output population that had an average fitness that was higher than the average fitness of the input population when tested in the same environment.

Methodology

1. Design both a simple static environment and a population type.



2. Program the simple static environment for the genetic algorithm population as well as any functions required for an individual in the population to interact with the environment.



3. Debug the environment.



4. Program the population and those functions required to initialize and monitor the population.



5. Test the population in the environment and debug both as necessary.



6. Design the genetic algorithm engine and the program required to coordinate the environment, population, and genetic algorithm engine.



7. program the genetic algorithm engine.



8. Program the coordination program.



9. Debug the genetic algorithm engine with test data.



10. Combine all elements and debug as necessary.



11. Repeat steps 1 - 5 and 10 for each new type of AI population and environment.



12. Program and debug statistics package to interpret the data collected from test runs.

CONCLUSION

1. The program had to run in Borland C++ 4.5. The genetic algorithm does not, technically, conform to this parameter. Because of the poor pointer debugging incorporated in the Borland compiler the researcher changed platforms to Microsoft Visual C++ 5.0. Programs will no longer run in Borland C++ 4.5 because that version of C++ does not include bool as a system data type. This is easily fixable, however, should another programmer wish to take the time and include the bool.h header file before all the include statements in their main file.



2. The program had to support the use of independently programmed gene types and environments. The program does support user defined gene types that conform to the layout listed in the design parameters.



3. The program had to handle populations of any size within the memory limitations of the computer on which it was run. Due to unavoidable logistical considerations, the generic genetic algorithm can only handle populations of up to half the available computer memory. This is because the genetic algorithm must store the old generation while creating the new one.



4. The program had to include functions that supported crossbreeding within the population. The genetic algorithm does support crossbreeding.



5. The program had to, when given all appropriate functions and an input population that has been evaluated in a static environment and that has individuals with different fitness values, produce an output population that has an average fitness that is higher than the average fitness of the input population when tested in the same environment. The integer test clearly showed that this parameter is satisfied.

1. The genetic algorithm has an overselection function.



2. The genetic algorithm automatically detects if the strings are of fixed or variable length and acts accordingly.



3. The Tree class is a generic, templated data tree type that can be used as a gene type with the genetic algorithm. All of the appropriate member functions to perform straight and cross reproduction have already been written. This in conjunction with the genetic algorithm cuts up to 80% of the time involved in setting up any genetic algorithm run that uses data trees as the gene type.



4. The Gstring class is a generic, templated variable or fixed length gene string type that has all appropriate funtions included for use with the generic genetic algorithm. This type is not quite as useful as the Tree class, but it still saves a fair amount of programming time.

Future research

1. Decimation, in which the program creates a very large starting population and then uses that population to create a smaller starting population based on fitness.



2. Support for the random mutation of genes. The researcher is also currently developing additional generic gene types that can be used in conjunction with the genetic algorithm to solve many diverse problems. These types include:



1. A generic multi-state automaton type. This type would be capable of evolving survival or game-playing strategies.



2. A generic neural network type. A genetic algorithm could be used instead of a traditional learning algorithm to determine the weights of a neural network. Such a type could be used for such things as predicting stocks, evolving survival behavior, and basic image recognition and compression.



3. A generic "creature" type to serve as a base type for organisms in artificial life simulations.

1. Potential solutions can be represented in such a way as to conform to the gene type layout shown by the genetic algorithm para meters.



2. Potential solutions can be assigned a scalar fitness that increases as the p otential solution approaches the correct answer.