Genetic Programming in C#

On 07.31.10, In Code, Development, By The Villain
C# may not be the best language to use for Genetic Programming, but as these examples show, it can work. Our interest in C# Genetic Programming happened as a result of C# becoming our language of choice for the Project, almost by default. In our pursuit of C# GP sample code, we found a number of resources worth sharing:

This MSDN article by Brian Connolly is a great place to start. The code may be getting a little outdated, but I compiled and ran the “ant food-finding program” just fine. The article is detailed in its explanation of the code and how the GP functions. One cool thing to me is how the program also prints out the code of the evolved genetic programs, and labels each ant by its corresponding generation and individual number.

MSDN Ant Example GP
MSDN's Ant GP

There are several Genetic Programming libraries that are written in C# and fully available online:

GPE (Genetic Programming Engine) is a library inspired by the preceding MSDN article. It has plenty of documentation available online. I have downloaded the library but have not had any free time to play around with it yet.

Aforge.NET has become our primary GP library to play around with so far. Documentation and samples are good and up-to-date, although the bread and butter of Aforge deals more with Imaging, so the GP (and GA, and GEP) portion is not as expansive as some of the other libraries we’ve found.

Aforge GP
Time Series Progression with Aforge

SLNGP (Silverlight and .Net Genetic Programming) has a great looking library, but next to no documentation to support it.

Honorable mention goes to this blog about Lambda GP, and another potential for good GP source code in C#, “Gene Hackman.”

In future blogs we’ll extend the search for quality Genetic Programming sources in other languages, such as LISP and Python, and we’ll share our experiences along the way.

Stumbleupon Twitter Google Buzz Digg it del.icio.us Facebook Reddit Yahoo Buzz
Tagged with:
 
0 Comments
Leave A Response

Bitmap-Binary Basics

On 02.01.10, In Code, Development, Video Games, By The Villain
The Bitmap-Binary Converter will likely be the core engine for at least the early versions of Alphabet Soup. To create it, there are a few things we need to consider. The two most glaring questions are how will we read individual pixels, and how will the actual conversion between pixel color and binary code take place? An even more basic consideration is which programming language we will use. I am leaning heavily toward C#, as it seems fully capable of tackling both problems. There are a couple of ways we could do this. Let's start with the assumption we begin with the bitmap and define all the colors for a given letter ("A", for example). This website explains how to access each pixel individually--exactly what we are trying to do. This is the core of the code allowing the color definition for each pixel based on location within the bitmap: public void SetPixel(int x, int y, PixelData color)     {         PixelData* pixel = PixelAt(x, y);         *pixel = color;     } However this is using 'unsafe' code to access each individual pixel. To use 'safe' code the actual program execution would take forever. So there may be a third alternative worth looking into. And here are more thoughts about this. This is something we are going to have to experiment with to find the best method, or we might have to figure out our own. To save the bitmap code for future use, we will have to set the black pixels to 1 and white pixels to 0. This will produce 256 characters, ranging from charA[0] to charA[255]. We might have the program write this data to a separate file, or just store it within its own memory. For visual reference, here is the bitmap in actual size: A Here is the 'A' bitmap represented in binary: 0000000000000000 0000000100000000 0000001110000000 0000001010000000 0000011011000000 0000010001000000 0000110001100000 0000100000100000 0000100000100000 0001111111110000 0001111111110000 0001000000010000 0011000000011000 0010000000001000 0110000000001100 0000000000000000 Here is the above bitmap referenced in pixel notation (shortened to describe the four corners): (0,0) through (0,15) ... (15,0) through (15,15) And here is the character equivalent to the above pixels: charA[0] = (0,0) = value of '0' charA[15] = (0, 15) = value of '0' charA[240] = (15,0) = value of '0' charA[255] = (15,15) = value of '0' Or, we do it the other way: Start with 62 '.txt' files (52 letters and numbers 0-9, or whatever amount we end up with for the base set of characters), each with 256 "0" and "1" characters representing the 16x16 bitmap. Read the text from the file and use the code "if charA[0]='0'..." / "if charA[0]='1'..." and the earlier bitmap code to convert each corresponding pixel to black or white by referencing the corresponding pixel within the bitmap. Whenever crossover occurs in the program, it creates a new binary (or .txt) file to represent that organism. I think a thorough understanding of the C# StringBuilder Class is going to come in handy for this, in splicing strings of binary characters and performing other modifications. Again, this will be closely intertwined with the GP or GA code, which will be the determining factor for where the splicing will occur each time. Basically we're accomplishing the same thing but from two different directions: bitmap-to-binary or binary-to-bitmap. It will probably be valuable to know how to do this in both directions for purposes of the program anyway. Basic C# data type conversions (string-to-binary-to-decimal-to-chars-to-string and so on) will be instrumental in making this work properly. This should actually be pretty simple; it will just take some time to sort out the details. What I described above should accomplish the basic functionality of the BBC; once we get this working we can move onto the engine's more complex functions, such as attributing higher "sensitivity values" to certain pixels and recognizing "contact" with other letters.
Tagged with: •
 
0 Comments
Leave A Response

Starting with Subclasses for Alphabet Soup, 0.01

On 01.24.10, In Code, Development, Ideas, Video Games, By The Villain
(Originally published January 10, 2010) Time to get some thoughts down on digital paper concerning the actual code for Alphabet Soup. For simplicity's sake, here are some more specific ideas: To stay close to the code in MSDN's ant program, we can start with a similar "ant" grid, allowing only up/down and left/right movements. This is not our "floating letters" environment yet, just think of it as a first step toward that. We also have to redefine what the classes are and where they belong. The "ant" class becomes our "alphabet" class. "Food" in our case should be redefined to individual letter "species." Let's start with Alpha, Beta and Charlie to keep it simple. So, while an ant in MSDN's program will encounter food along its path, any alphabet character will be encountering alphabet subclasses (formerly food) along its path. What the code decides to do results in whether the encountered character is devoured (or eaten, as in the original program), morphed, defended against or something else. So, the individual letters must obey the general rules of the alphabet class, but what they do individually depends on the evolutionary code that is run every time a collision occurs--and what happens should depend upon which letters are involved. I call this the ContactReaction() function. Here is a general framework: Alphabet class, stay with MSDN example, with adjustments: public Void Init(Cell[,] grid, int StepLimit, int SurvivalGoal) Move() function includes basic movements and the results of contact between letters, to call on evolution code: public void Move() {     if(NotFinished())     {         GetFacingCellCoord(outxLocation, outyLocation);         mTrail.Add(newTrailSpace(xLocation, yLocation));         mTotalSteps++;             if(mGrid[xLocation, yLocation].HasAlpha())             {             ContactReaction(Alpha) // calls function for what happens            when character encounters Alpha             // This will be where the evolutionary choice takes place,             well, part of it (see below)             }             if(mGrid[xLocation, yLocation].HasBeta())             {             ContactReaction(Beta)             }             if(mGrid[xLocation, yLocation].HasCharlie())             {             ContactReaction(Charlie)             }     } } Here we will place the evolution stuff--to include within ContactReaction() function: {     // (Define basic function here with evolutionary aspect,     including specifics for each letter (see below))     if(result=Devour)     {         mGrid[xLocation,yLocation].SetEmpty(); // this is as if the         letter eats the other character     }     else     {         (OTHER OPTIONS/TRANSFORMATIONS/EVOLUTION) // Run Generator code        } } The ContactReaction() function will involve a lot of tweaking in combination with MSDN's Generator class. It will call on the Generator class and expression tree constructors to perform the genetic crossover algorithms after every collision. The code for these can be found at http://msdn.microsoft.com/en-us/magazine/cc163934.aspx#S5 An important question... Generator and Expression Tree from MSDN look great for our purposes, but should we include separate generator/expression tree specs for each of the different letters? More specifically, how will the letter's shape have an effect on what happens in a collision? Should we define this aspect of it within the generator/expression tree? I think the best solution is to define those specs in our ContactReaction() function, meaning that function would have to be tailored to each individual character--but that way the generator/expression tree class can remain one and just be referenced by the ContactReaction() function--as I have shown above. So the evolutionary choice will still take place in the MSDN-defined classes, but each of the collisions will involve a "lean" toward reaction based on letter shape, as we define in ContactReaction(). This may or may not be the best solution, but it is a start.
Tagged with: • • •
 
0 Comments
Leave A Response

Alphabet Soup, 0.01

On 01.24.10, In Code, Development, Ideas, Video Games, By The Villain
(Originally published December 29, 2009) The Project still requires an immense amount of reading and research before it can produce much fruit, but there is nothing to keep us from starting with the basics (except of course the risk of extinction like everyone who has ventured before us). We obviously cannot do this completely from scratch, so to find out where to begin, we look to simple GP and GA examples. Pariahpism discovered MSDN's example program using ants to find the most efficient way to follow a trail of food in a 32x32 square matrix. The program uses C# in the .NET framework, along with Microsoft's System.CodeDom Namespace. Full source code for the example program is available here. Now, to apply the principles of the Ant/Food program to Alphabet soup, we begin by breaking the program into the comparable classes. I consider the User Interface a separate aspect of the program to be built later, but additionally there are two necessary sets of high level classes. The first set is the problem set, which includes the customized goals and limitations. Basically, these are the details specific to our program (letter class, number class, case class, goals, movements, starting population, and so on). While the article's program describes an ant following a path of food, Alphabet Soup will involve alphabet characters reacting to collisions with one another. A secondary but important aspect of this set of classes is a private method (or methods) included to record what happens within the program--the generational "history" which is saved to an array so the array instances can be compared for fitness level. This allows the program to use natural selection for determining "who" survives to the next generation--and, in the case of Alphabet Soup--what the future holds for those letters which collide, based in part on the fitness of past results. For the early versions of our program, the problem set and UI will take up the bulk of our customized coding. The GP framework, on the other hand, already exists more or less. It does still have to be customized as far as the variable names are concerned, but the basic set of code instructions will be very similar to what the article defines--especially if we create our first program in C#. In other words, the GP framework is a standardized code including the necessary algorithms for mutations and inheritance. At the core of the GP framework, the Ant/Food program uses the Generator class, which the article refers to as the "kernel" of the GP implementation. It does, after all, perform: "selection, breeding, code generation, execution, and result sorting." Something I've been seeing over and over again in GP is Koza's "tree" full of terminals and functions. For the ant program, functions include "FacingFood" and terminals include "Left" and "Right." For Alphabet Soup, let's use the examples of function: "CollidingLetter" with terminals "Avoid" and "Attack." Random expressions are created by the algorithm by combining available functions and terminals from the tree. For instance, "if CollidingLetter, then Attack else Avoid." These random combinations are weighed against a fitness measure (defined elsewhere in the program), which helps determine the outcome of the future generations. In following traditional GP, the selected alphabet characters (a certain percentage) are copied for crossover and reproduction while the rest are discarded--depending on how exactly we choose to do it. Again, this code should be easily modified from MSDN's version to what we need for Alphabet Soup. The article also addresses the role of mutation in the ant program. Mutation will be crucial to how Alphabet Soup plays out: "[Mutation] involves making a random change in a small number of offspring in order to maintain diversity in the population. Mutation is essential because otherwise the population becomes completely dominated by a few good bloodlines, which makes it difficult to continue progress beyond a certain point. [The Ant/Food program] performs a simple mutation step during the crossover operation to introduce randomness. When a terminal node is copied, a random terminal is substituted two percent of the time." So these are the basics of the basics to get us started. Another note to keep in mind is the usefulness of XML. The Ant program copies the ant path to an XML file which can later be reloaded. This may not have much use for the application itself, but it can be interesting for reviewing past generations and possible patterns/flaws/suggestions in the code. Also, check out another simple example in C.
Tagged with: • • • • • • • •
 
0 Comments
Leave A Response
Go To Top »