Genetic Algorithm:
A C++ Implemetation
Greg Sawyer
ECE 539
Final Project
12-19-03
For my final project I made an implementation of genetic algorithm in C++. Matlab has many uses, but if fuzzy logic is to find more practical application it is going to have to be ported to languages that are in wide use.
My implementation of genetic algorithm can use either multipoint or single point crossover. The user can specify which to use at startup, it defaults to using multipoint, or the user can change which he/she is using at just about any time in the program. Through the use of global variables most of the options can be changed on the fly; however, one must be vary careful when changing these values. The goal of this project was to make the code portable and user friendly, allowing the user a lot of freedom.
The algorithm maintains a list of vectors and their corresponding weights. The vectors from the first breeding generation are called critical vectors. Each critical vector is crossed with every other critical vector. From the second generation on, all the vectors are examined and the ones with highest weights become the second generation’s critical vectors. The amount of critical vectors remains the same between generations unless the user adds another critical vector. In addition a check is done every generation to make sure that with the resulting critical vectors that the ‘gene pool’ is not dead (i.e. its potential to produce vectors other than those in the critical set is 0).
An overview of my code follows:
void print(element &e0); void print_all();
Functions primarily for debugging.
void prompt_config(); void init_config(config myconfig);
Functions to allow the user to manipulate the way ga reacts
void clear_all();
Useful function to reset ga to the default settings.
void add_critical(element &list);
Used in the construction of a ga solution, some starting vectors must be given.
void single_point(element &base, element &cross, element &final);
void multi_point(element &base, element &cross, element &final);
Implementations of single point and multipoint crossover
void addinorder(element *nhead, element *n);
List manipulation function that adds element *n to the list pointed to by *nhead in
Descending order by weight.
int deadgene();
Called by nextgen(), used to decide if the gene pool is dead
void killgen();
Function sorts by weight and removes all but ga_critical vectors from the list.
int nextgen();
nextgen handles the new vectors resulting from all the crosses.
element *getgen();
returns a pointer to the first element in the list produced by nextgen
Actual code is attached to the electronic submission.