Introduction
The intention of this series of articles is to write an introduction into the world of genetic algorithms starting from the absolute beginnings and working towards more complex solutions as the series progresses. The code provided is intended to run on Windows XP with .NET version 1.1. This article will focus on the very basic elements of genetic algorithms focusing on what a genetic algorithm is and will provide the code for a demonstration application that despite having certain problems will be used to show how a genetic algorithm is intended to work with more advanced methods being the target of future articles. The secondary aim of the articles is to develop and provide a free genetic library that will allow any future development of genetic algorithms both for myself and others to be developed more easily by providing a set of generic tools that will allow future developers using the library to concentrate more on the application specific side of what they want their genetic algorithm to do rather than constantly trying to work out how to do it.
What is a genetic algorithm?
The theory of a genetic algorithm is based on the idea of reproduction and genetics in biology. This, to greatly simplify, is to take a pair of strings or lists of letters or chemical types and which are compatible and to mix and match them and see what the results are. Of course, there are limits in biology to what exactly can be mixed and matched and the same should go for our own genetic algorithms. To go right down to the genetic algorithms for dummies level for a moment if you have a cup of coffee and some sugar and some salt and try different combinations of two of the three then most people will agree that the coffee and sugar mix taste the best while the others pretty much suck in terms of providing a refreshing beverage.
The biological idea of a genetics algorithm is the DNA strand with each section of the DNA strand being equivalent to a certain function or characteristic of the body. Although it should probably be mentioned here that this bodily characteristic is rarely as simple as tall or short or big nose or little nose but rather these things are more a combination of the resulting influences of the separate strands of chemicals within the genetic strands, influences which I'm pretty sure are not fully understood by anyone yet, so don't go expecting genetic face lifts to start appearing in the supermarket any time soon. But let's just for a second suppose that such a thing is actually possible and that we can nip off down to the supermarket and get our very own genetic face lift in pill form. How would it be made up, well at a guess it would go something like this,
You start with a few basic types which you can choose from, starting with:
SIZE:
Fat
Skinny
Medium
Then you think about the length.
LENGTH:
Long
Short
Medium
Finally, you put a bit of characteristics on it.
CHARACTERISTIC:
Hooked
Stubby
Average
You take one pill from each section and wake up in the morning with the nose of your choice and if you don't like it then you can always try another combination the next night. Of course, though the only problem with this is when the decisions about your genetic make up are made you are just a chemical soup in your mothers womb, so your ability to affect the outcome is somewhat limited, along with the fact that you couldn't possibly have any idea about what type of noses are going to be "in" in twenty years time. So along with the rest of us you have to let nature do it's job and whine about it when you're a teenager.
The idea behind genetic algorithms is to simulate the job done by nature when making this kind of choice and use it to find answers to problems. Being programmers we want to find the correct answers but we won't worry about that a great deal for now and just concentrate on how we are going to get an answer at all. To use a genetic algorithm for the above problem what we do is present the solution as an array and then select the answers from that so we would have:
Array 0 :- SIZE
Array 1 :- LENGTH
Array 2 :- CHARACTERISTIC
Each item in the array would contain another array that holds the options so Array 0 would contain:
array 0 :- Fat
array 1 :- Skinny
array 2 :- Medium
Now if in the code we use zeros and ones to turn an option on or off with a 1 being on and a 0 being off then a print out of the Array 0 for a fat nose would read 100, a print out for a skinny nose would be 010 and a print out for a medium nose would read 001. We could of course have mixes and variations such as a medium fat nose which would be 101 but we won't go there for now. So extending this throughout a print out for a completely average nose would read:
Array 0 :- 001
Array 1 :- 001
Array 2 :- 001
which would give us a complete string ( probably should steer clear of the phrase nose string here ) of 001001001. Now if we say that this is how all noses are defined then all we need to do is manipulate this string and we can select any type of nose that is possible given our requirements by simply switching the values in the string between 1 and 0.
This is what a genetic algorithm does of course the string doesn't have to be zeros and ones and it can represent anything you want it to be but at its most basic form a genetic algorithm will manipulate a string in order for the program to get whatever meaning is represented by the string from it. The meaning and representations of the string are of course up to the programmer and the requirements of the project. So the next question is how do we do it.
The demonstration code
Before we get into the details of how to implement the genetic algorithm, we should probably take a quick look at the demonstration code provided with the article.
For this project all the code is provided in one project that builds slightly different executables designed to highlight the points in each article. The demonstration code for this project is the GeneticsDev project which can be built by left clicking on the project in Developer Studio and then right clicking and selecting "Set As StartUp Project" on the menu.
The idea behind the demonstration code is to provide what appears to be a binary type of calculator, that is you enter a sum to be calculated in the boxes provided and the code tries to find the answer to the sum in binary. The amount of binary numbers that can be calculated is configurable by the code and we will look at the reason for this and the repercussions later. For now though the GeneticsDev demonstration uses ten bit binary numbers so anything that returns a one will return a string of 0000000001 and a two would be 0000000010 and a three would be 0000000011 etc. Note that there is no real reason to use binary strings here I just felt that it would give a simple visual representation of what is occurring in the code.
The demonstration itself is a simple front end that uses three custom threads, one that is fired during start-up and is used to do the initialization for the genetic algorithm and two separate threads that are used to do the calculations. The reason for the separate threads is that the application is processor intensive and will become unresponsive if threads are not used.
Reproduction
Genetic algorithms are basically random data trying to find the answer or the solution to a problem through what is essentially guess work. The initial array is randomly initiated and then we hope to move it into the direction of the answer or solution. This of course requires that we have at least some idea of the solution we are looking for but it doesn't mean that the requirements for testing the fitness need to be as exact as I have shown them in the demonstration code to this project. Basically it is possible to write a fitness function that requires the code to achieve a goal say of finding a path through a map without requiring that the code finds a specific path through the map, as in the shortest or the longest. However, if we don't have any type of fitness function within the code at all we are just peeing into the wind and hoping to get it into a bucket that someone has randomly placed behind us. Without any attempt to guide the program to the solution we are looking for we may as well just make a lot of calls to the random function and see what the code does. This is what version one of the genetic algorithm does.
So we take our randomly initialized array and check to see if it has the correct answer in it while all the time kind of hoping that it doesn't start randomly guessing it every time that we run it and for those who have run the demonstration code already you may have seen that sometimes this is the case. Now we have the situation where we have an array of random data and a solution that we want the code to find, the way genetic algorithms do this is to select data from the array and use it to create new data. This is done by using the biological technique of combining the data in some way so that we create an entirely new attempt at a solution from the data that we have selected. This is called reproduction.
Reproduction is the cornerstone of any genetic algorithm and serves exactly the same function that it serves in biology. The idea being that you take two or more parents and derive offspring, in this case we are using binary string so say 0000000001 and 0000000010 are the parents there are only three noticeably different offspring that can be produced these being 0000000001, 0000000010 and 0000000011, which in decimal numbers would be 1, 2 and 3. The code that determines which offspring will be chosen is covered in the section on Crossover below for now we will concentrate on just how we are supposed to decide who the parents are supposed to be.
The common term for selecting the parents in a genetic algorithm is called Fitness. Fitness is meant to be the way of selecting the parents from which the offspring for the genetic algorithm are chosen and as such is the hardest part of the genetic algorithm to discuss as it is always completely application specific, so we will discuss it in terms of the demonstration code on the understanding that the method chosen is completely optional and that there are other ways of choosing the parents even within the demonstration code. The only limits really when it comes to choosing the fitness for a genetic algorithm are really the developer's imagination and understanding of the project requirements.
In the demonstration project we set up an array of hundred binary numbers which may or may not contain a binary string who's decimal value is equal to the answer. If there is no binary string who's decimal value is equal to the required answer then we create a new generation of binary strings from the current generation but before we can do this we need to select the items from the array of a hundred that we are going to use as parents to derive the offspring from. In the demonstration code for this project found in form one of the GeneticsDev project, I have written a function called Fitness that checks through the array of numbers to see if there are numbers on either side of the answer that we want. If there is, then the code will take the twenty five or however many there are values on either side of the correct answer. If none of the values within the array are greater than the answer required the code will take the twenty five values just under the required answer and if there are no values smaller than the required answer then the code will take the twenty five values that are just higher than the required answer. The Fitness function is called by version two of the genetic algorithm.
Selection
Before the genetic algorithm can make any decisions, it must choose who the parents are going to be and as with nature the kids may not always get the parents they deserve. There are a number of ways the parents for the next child in the algorithm can be generated which we will go into more detail later, in the first demonstration though a simple random algorithm known as Roulette Wheel Selection is used. Roulette Wheel Selection simply chooses two parents at random from those on offer in the array although the parents themselves have been through the fitness function first so it is not completely random in that sense.
Crossover
Crossover is the mechanism by which genetic algorithm chooses the parts of the parents that it wants, this can be application specific but is kept general throughout these projects. To go back to the biological analogy, crossover is the part of the code where one parent has brown eyes and the other parent has blue eyes and the color of the child's eyes is determined. There are a number of ways in which this can be achieved some of which are discussed in part two of this project. For now though crossover goes something like this. If you have two parents, 0101010101 and 1010101010. You want to create a child that is a mixture of the two parents. The simplest way to do this and the way that is used in the demonstration code for this project is to split the parents strings and simply cross them, so you get a child that looks like: 0101001010.
This gives you a unique offspring that is made up entirely from the parents genetic make-up.
Mutation
Mutation is the process by which random variations are introduced into the genetic string, to continue with the natural analogy say that you have a string for the eyes and that part of the string has a value to indicate if the child's eyes are squinty or not. If a random value is generated when the child is created and the value is less than a given value which is usually extremely low, it's set to 0.01 in the demonstration code then the value for squinty eyes will be changed from what ever its current value is to it's opposite. So if the child's value for squinty eyes is 0 for 'not squinty' when the value is fired, then it will be set to one and the child will have squinty eyes.
The code
The code for this demonstration is designed to give a simple view into the world of genetic algorithms, showing how the basic code works and concentrating on demonstrating the order of things rather than trying to create a fully functioning program from the start I figured it would be best to talk about the common pitfalls and problems that can run into it when using genetic algorithms for a couple of reasons, the first being that we aren't dealing with an exact science here, every project will be different and a solution that works for one project is likely to completely foul up another project, so understanding the reasons for this is paramount before starting any project.
The demonstration code
The demonstration project is a simple Windows application that uses a RichTextBox and a couple of threads to initialize the array and to maintain application usability while the application is running. The code itself is a sort of mock calculator in that it does small sums that the user can enter. The numbers are then converted to binary strings. which in this case are ten characters long, the reason for this being that in testing ten characters gives a good balance between the code being able to randomly find the results and being able to determine the results through the algorithm without the need for further complicating the code with additional checks and balances.
The code uses these genetic strings to get a number and then attempts to find the correct answer to the sum entered by checking the binary values in the array with the value given by the sum entered.
When the application starts a thread is started that initializes the array that contains the binary numbers and the user interface is disabled until this is complete. The user then enters a sum using the numeric check boxes on the forms. The two values on the forms are restricted as the total value of the answer cannot exceed the maximum value that can be held in a ten character binary array. Once the user has entered the sum they can run it through one of two genetic algorithm implementations, the first implementation being a very basic implementation that relies on the generation of random numbers or the second version that uses a fitness function to try and guide the algorithm to the correct answer.
Before we get down to the problems of these implementations as they stand, let's take a look at how they work. First of all the array is initialized when a variable named binGenetics is initialized as an object of the Binary Genetics class in the constructor. Once the initialization thread starts the binGenetics.Initialise() function is called and runs the following code:
for( int i=0; i<PopulationSize; i++ )
{
this.GeneticsArray.Add(new BinaryGeneticsString(ChromosomeLength));
}
This adds a new BinaryGeneticsString object of ChromosomeLength which is 10 and is set with the constant SIZEOFBITS in the class, to the GeneticsArray. The BinaryGeneticsString constructor calls its InitialiseString function to set up the binary string for the number with the code:
Random rand = new Random();
for( int i=0; i<ChromosomeLength; i++ )
{
System.Threading.Thread.Sleep( 2 );
GeneticsString.Add( rand.Next() % 2 );
}
which creates a random string of zeros and ones in an array of ChromosomeLength size. Once the array is initialized then the user interface for the code will activate allowing the user to choose the version of the genetic algorithm to run.
Starting with the GeneticsThreadOne function in form1.cs of the GeneticsDev project we can see how the code runs. It should be mentioned though that the variables labeled binTest and binAnswer are objects of the BinaryConversion class that is used to do conversions from decimal to binary strings and back, storing the numbers internally as they go.
When the code does nothing more than print information to the RichEditBox it is replaced with "/// print out".
bool bStop = false;
int nRunCount = 0;
while( bStop == false )
{
for( int i=0; i<binGenetics.PopulationSize; i++ )
{
binTest.BinaryString =
((BinaryGeneticsString)binGenetics.GeneticsArray[i]).ToString();
if( binAnswer.Number == binTest.Number )
{
bStop = true;
OnStopThreadOne( this, null );
break;
}
}
if( bStop == false )
{
binGenetics.Run();
nRunCount++;
}
}
The code cycles through the population stored in the GeneticsArray and checks to see if any of the values are equal to the answer that we are looking for, if the answer is found the code stops the thread and resets the user interface. If the answer is not found within the population the BinaryGenetics run function is called.
The BinaryGenetics run function is the entrance to the code from the genetics library and looks like this:
ArrayList holdingList = new ArrayList();
for( int i=0; i<PopulationSize; i++ )
{
BinaryGeneticsString bsTemp =
new BinaryGeneticsString( ChromosomeLength, false );
RouletteWheelSelection();
SinglePointCrossOver( bsTemp, nCrossOverPoint );
holdingList.Add( bsTemp );
}
GeneticsArray.Clear();
for( int i=0; i<PopulationSize; i++ )
{
GeneticsArray.Add( holdingList[ i ] );
}
Mutation();
The code shows the order in which the genetics algorithm functions are called. To begin with a temporary ArrayList is created to hold the new population for the algorithm, then the crossover point is initialized which is set here at the half way point along the array. We then create a new object of type BinaryGeneticsString which is the object that contains a single member of the GeneticsArray population and in this case will be a child to be entered into the next generation of the algorithm. This is created by passing in the ChromosomeLength which is the size of the genetics string, in this case an array of ten characters and an initialize boolean value of false which indicates to the constructor that it does not need to fill the array with random characters as we are intending to pass the object to the SinglePointCrossover function which will fill the array from the parents that are selected by the RouletteWheelSelection function which are discussed below. The child is then added to the holding array and the process is repeated until we have a new generation for the genetics algorithm. This new generation is then copied from the temporary array into the main GeneticsArray.
The library
As mentioned above the idea behind the library is to both provide a framework to use in building future genetic algorithm projects and as a template to hold some of the more generic functionality. Which in this case means holding some of the functionality for the selection and crossover so that when an algorithm is being tested it should be reasonably simple to be able to change the selection and crossover functions used within the project to find an implementation that will allow the best results. The main library classes are the Genetics Base class and Genetics String class and both are meant to be inherited by the current implementation to provide the basic functionality of the genetics algorithm so that the classes that inherit from them can concentrate on getting the implementation right.
The main class is the Genetics Base class which contains the main blueprint of the functionality for the genetic algorithm, as well as the variables necessary for the implementation of the algorithm such as the population size and the length of the chromosome array. Its main characteristics though lie in the three abstract functions and how they are implemented by child classes. These are:
public abstract void Initialise();
public abstract void Mutation();
public abstract void Run();
The Run function's implementation in the child BinaryGenetics class is listed above, while the Mutation function will be listed in the mutation section below. The Initialise function simply sets the Genetic Strings required for the program. In the case of BinaryGenetics program this is:
for( int i=0; i<PopulationSize; i++ )
{
this.GeneticsArray.Add(new BinaryGeneticsString(ChromosomeLength));
}
which adds a new BinaryGeneticString which is a child of the object to the GeneticsArray. The GeneticsString class at its most basic level is a simple object array holder that holds what will be used as the Genetic data for the program. It does not have to be a string and can be any sort of object that the project requires. The class has one function that needs to be implemented in a child class and that is the InitialiseString function which sets up each piece of the Genetic String and is of course highly application specific. The InitialiseString function in the BinaryGeneticsString looks like this:
Random rand = new Random();
for( int i=0; i<ChromosomeLength; i++ )
{
System.Threading.Thread.Sleep( 2 );
GeneticsString.Add( rand.Next() % 2 );
}
The important line here is the GeneticsString.Add function that adds, chromosome length 0 or 1's to the GeneticsArray.
Fitness
As mentioned the way Fitness is calculated for a genetic algorithm is highly application specific so I can only talk about it here in reference to the current project. The idea of the Fitness function is that we want to narrow down the range of values within the array so that they approach the value that we are seeking. In the demonstration project, if we have an answer 54 and have an array of randomly generated numbers from which we are trying to find the answer, we naturally want to remove the answers from the array that are farthest away from the value we require. This is done in the project, once we have ascertained that we do not have the correct answer, by getting the twenty five values that are closest to the correct answer. The code for the Fitness function is too long to list here and can be found in Form1.cs.
Selection
As mentioned above the selection method used for the first demonstration project is the Roulette Wheel Selection method and the code looks like this:
Random rand = new Random();
int nSelected = rand.Next( GeneticsArray.Count );
gsParentOne = ( GeneticsStrings )GeneticsArray[ nSelected ];
System.Threading.Thread.Sleep( 2 );
nSelected = rand.Next( GeneticsArray.Count );
while( gsParentOne ==
( GeneticsStrings )GeneticsArray[ nSelected ] )
{
nSelected = rand.Next( GeneticsArray.Count );
}
gsParentTwo = ( GeneticsStrings )GeneticsArray[ nSelected ];
The variables gsParentOne and gsParentTwo are private GeneticsString class members in the GeneticsBase class and these are used to store the parents of the new child that is to be created by the crossover function. As you can see from the above code this is done by randomly selecting a string from the array and then selecting another one whilst making sure that we are selecting two different parents.
Crossover
Once we have selected our parents that are going to form the child we need to get to the crossover function, whose function it is to take a part of one parent and a part of another parent and mix them together so that we get a new, in this case binary string:
child.GeneticsString.Clear();
for( int i=0; i<SingleCrossOverPoint; i++ )
{
child.GeneticsString.Add( gsParentOne.GeneticsString[ i ] );
}
for( int i=SingleCrossOverPoint; i<gsParentTwo.GeneticsString.Count; i++ )
{
child.GeneticsString.Add( gsParentTwo.GeneticsString[ i ] );
}
As with the Selection functions there are several crossover functions available for us to use, with the one used here being the Single Point Crossover. The SinglePointCrossOver function joins the parents at a single point within the GeneticsString, this point is set by the SingleCrossOverPoint value within the GeneticsBase class.
Mutation
The final part of the process is the mutation part, at least it is the way the library is organized as it works once the complete array of children has been built rather than applying it individually at the time each child is created. It is also not applied within the base classes as once again it is application specific, you can't write a mutation function for a genetic algorithm until you know what it is that you are mutating. So the function can be found in the BinaryGenetics class and it looks like this:
Random rand = new Random();
Random randLocation = new Random();
int nLocation = 0;
BinaryGeneticsString bsTemp = null;
for( int i=0; i<PopulationSize; i++ )
{
if( rand.NextDouble() < MutationRate )
{
nLocation = randLocation.Next( ChromosomeLength );
bsTemp = ( BinaryGeneticsString )GeneticsArray[ i ];
if( ( Int32 )bsTemp.GeneticsString[ nLocation ] == 0 )
{
bsTemp.GeneticsString[ nLocation ] = 1;
}
else
bsTemp.GeneticsString[ nLocation ] = 0;
}
}
The decision whether a child is to be mutated or not is entirely dependant on the MutationRate which is adjustable but is set to 0.01 in the GeneticsBase class which gives it a pretty small chance of ever being used. If however by some chance a mutation does take place we select a random place within the child string and simply flip whatever bit we find there.
Problems
Now in a perfect world we would be able to say fine that's a wrap, pack our stuff and go home to fire up World of Warcraft and put our feet up. Unfortunately, there remains one minor setback and that is the program we have has one tiny but noticeable little flaw. And that little flaw is that it simply isn't very good at doing what we want it to do. In fact, if you run the second algorithm for long enough you will get something that looks like this:
Fixing the problems
The problem here is that although the algorithm got quite close to the answer, it is only 12 off after all, the algorithm isn't sophisticated enough to
- detect that it is close but not close enough to answer and,
- it has no way of changing itself so that it can correct this problem.
One quick solution to this problem is the SingleCrossOverPoint variable in the GeneticsBase class, this variable sets the point at which the SinglePointCrossOver algorithm copies the parent strings to the newly created child string. When this is set to four, the numbers will tend to converge close to the value but when set to five this seems to be further apart.
This however, is a common problem with genetic algorithms and while changing the crossover points or algorithm completely is one solution there is no guaranteed solution. There are a few tools that we can use. Here are two of them.
In the Form1.cs file at line 49 there is a variable called bool bProblemSolving which is set to false by default, if you set this to true before compiling you will get changes to the program interface that looks like this:
Generations
Once the checkbox for generations is clicked the code will use the default settings or any changes made to the default settings. It works on the idea that there are fifty cycles of breeding to create a generation, if the answer to the sum ( in this case ) isn't found by the end of a generation then the genetics array is reinitialized and the process is started again until either the correct answer is found or the program runs through all its allotted generations. Adding the generations code to the program is fairly simple in that all we need to do is initialize the generation code and then interrupt the loop with the code to update it.
To initialize generations we add the following code:
if( bProblemSolving == true )
{
binGenetics.UseGenerations = generationsBox.Checked;
if( binGenetics.UseGenerations == true )
{
binGenetics.NumberOfGenerations =
( int )numberGenerationsBox.Value;
binGenetics.NumberOfCyclesPerGeneration =
( int )cyclesPerGenerationBox.Value;
}
}
which checks if the problem solving mode is on and then checks if the generations option is checked, if it is then the variables to control the generations code are set to the values in the numeric boxes. The following code is then added to the loop to control the flow of the program:
if( binGenetics.UseGenerations == true )
{
if( nGenerationCount == binGenetics.NumberOfGenerations )
{
bStop = true;
OnStopThreadOne( this, null );
}
if( nRunCount == binGenetics.NumberOfCyclesPerGeneration )
{
binGenetics.Initialise();
nGenerationCount++;
nRunCount = 0;
}
}
As with the initialization code we first check that the problem solving option is on and then check to see if we've used all our allowed generations if we haven't we then check to see if the end of a cycle has been reached and if it has we reset everything and reinitialize the GeneticsArray to start again.
Elitism
Elitism is the process by which items in the GeneticsArray are preserved into the next generation of the array so that a parent in one generation will be mixed with the children from the next generation. In the GeneticsDev example the code saves the five values closest to the answer that we are looking for. The code that does this is similar to the code that checks for the fitness values within the form1.cs file. In fact it started as a straight cut and paste and the AddEliteValues function in the BinaryGenetics.cs file was edited from there.
Adding Elitism to a child class of the GeneticsBase class is really quite simple in that you add code that looks something like this to the run function:
if( UseElitism == true )
{
AddEliteValues();
}
Simple check if elitism is being used and then call the function that you will have to write to get the elite values that you wish to save. Of course, you will have to set it up first which requires:
binGenetics.UseElitism = elitismBox.Checked;
if( binGenetics.UseElitism == true )
{
binGenetics.ElitismValue = binAnswer.Number;
}
or similar code being added to the function that calls the run function.
Additional code
Along with the development of any library goes the need for functionality so I've also included a number of selection and crossover methods that can be used in any application developed using the library. In order to develop and test these methods I decided that rather than trying to shoehorn them into the GeneticsDev application I would include a second application developed specifically for the purpose. This is the GeneticsDevAdditional application provided with the sample code. In order to compile and run this sample right click on the GeneticsDevAdditional title and select Set As Startup Project.
As you can see there have been a few cosmetic changes to accommodate the extra options on two tab pages one containing the options for Selection and one containing the options for CrossOver. The main changes made to the code are:
binGenetics.CrossOverMethod = CROSSOVERMETHODS.SINGLEPOINTCROSSOVER;
binGenetics.SelectionMethod = SELECTIONMETHODS.ROULETTEWHEEL;
binGenetics.SingleCrossOverPoint = 5;
binGenetics.DualPointCrossOverPointOne = 4;
binGenetics.DualPointCrossOverPointTwo = 7;
binGenetics.PositionBasedCrossOverPoints = 5;
In Form1.cs for the GeneticsDevAdditional project as you can see from the first two lines the Crossover and Selection methods are now set by an enum in the base classes which are then used by the Selection and CrossOver functions and are called from the modified run function in the BinaryGenetics class:
Selection();
CrossOver( bsTemp );
Selection methods
There are only two options available for selection. The first one being the Roulette wheel option that we have seen previously and the second being the Fixed Point selection option. The problem from the point of view of this code is that once you start getting into the specifics of what selection methods you are going to use then you are venturing into the realm of application specific code, so the idea behind this option is that the person using the library can write a selection algorithm and then simply tell the base class which two array items it would like to use as parents.
The code given here simply starts by taking the first two items in the array and passing the array values into the Selection method with the Crossover method being called as usual. There are a number of other ways you could implement this, for instance you could start at both ends of the array and work your way to the middle or alternatively you could extend the number of array items saved by the Elitism function and then use only those array places to generate the children for the next generation.
Crossover methods
There are four crossover methods available. The first being the SinglePointCrossOver which was used in the original application and then there's the RandomPointCrossOver, DualPointCrossOver and PositionBasedCrossOver. These are all variations of selecting values from the parent arrays and copying them into the child array.
The RandomPointCrossOver function randomly selects the crossover point and copies the values from parent one in the first part and the values from parent two into the second part.
The DualPointCrossOver function selects two points in the array. The ends are filled in with parent one and the middle is filled in by parent two.
The PositionBasedCrossOver is similar to the RandomPointCrossOver function except that the entire parent one array is copied into the child array and then a fixed number of points are randomly selected from parent two, which are then copied to the same locations in the child array.
The code for both the Selection and the CrossOver methods can be found in the GeneticsBase.cs file.
Conclusion
That concludes the beginners guide to genetic algorithms. In the next part, we'll take a look at using genetic algorithms in more of a hopefully realistic application, i.e. where it does something useful in a situation where the end we are looking for is known but not how to get there and I will be taking a look at adaptive programming.
Primary references
- Mat Buckland , ( 2002 ) AI Techniques For Game Programming, Premier Press Game Development Series.
- David E. Goldberg, ( 1989 ) Genetic Algorithms In Search Optimization And Machine Learning, Addison Wesley.
- Wolfgang Banzhaf et al, ( 1998 ) Genetic Programming An Introduction, Morgan Kaufmann.
References
- Tom Archer ( 2001 ) Inside C#, Microsoft Press
- Jeffrey Richter ( 2002 ) Applied Microsoft .NET Framework Programming, Microsoft Press
- Charles Peltzold ( 2002 ) Programming Microsoft Windows With C#, Microsoft Press
- Robinson et al ( 2001 ) Professional C#, Wrox
- William R. Staneck ( 1997 ) Web Publishing Unleashed Professional Reference Edition, Sams.net
- Robert Callan, ( 1999 ) The Essence Of Neural Networks, Prentice Hall
- Timothy Masters ( 1993 ) Practical Neural Network Recipes In C++, Morgan Kaufmann ( Academic Press )
- Melanie Mitchell ( 1999 ) An Introduction To Genetic Algorithms, MIT Press
- Joey Rogers ( 1997 ) Object-Orientated Neural Networks in C++, Academic Press
- Simon Haykin ( 1999 ) Neural Networks A Comprehensive Foundation, Prentice Hall
- Bernd Oestereich ( 2002 ) Developing Software With UML Object-Orientated Analysis And Design In Practice Addison Wesley
- R Beale & T Jackson ( 1990 ) Neural Computing An Introduction, Institute Of Physics Publishing
- Bart Kosko ( 1994 ) Fuzzy Thinking, Flamingo
- Buckley & Eslami ( 2002 ) An Introduction To Fuzzy Logic And Fuzzy Sets, Physica-Verlag
- Steven Johnson ( 2001 ) Emergence, The Penguin Press
- John H. Holland ( 1998 ) Emergence From Chaos To Order, Oxford University Press
- Earl Cox ( 1999 ) The Fuzzy Systems Handbook, AP Professional
- Mark Ward ( 1999 ) Virtual Organisms, Pan
- Bonabeau, Dorigo, Theraulaz ( 1999 ) Swarm Intelligence From Natural To Artificial Systems, Oxford University Press
- Masao Mukaidono, Fuzzy Logic For Beginners ( 2002 ) World Scientific Publishing
- Deborah Gordon, Ants At Work ( 1999 ), W W Norton
- Gigerenzer, Todd & ABC Research Group ( 1999 ) Simple Heuristics That Make Us Smart, Oxford University Press
- Rodney A. Brooks ( 1999 ) Cambrian Intelligence, MIT Press
- Winfred F. Hill, ( 1964 ) Learning A Survey Of Psychological Interpretations, University Paperbacks.
- M. Tim Jones, ( 2003 ) AI Application Programming, Charles River Media
