High-Level Class Design

Date: 2015-10-07; view: 633.

A high-level view of the class design is shown in Figure 4. Several of the classes I use, such as the Cell, AntTrailGrid, TerminationReport, IComparable, mFoodGathered, and Ant, are problem specific. If you wanted to use the kernel of this implementation for another problem space, you would need to develop different versions of these classes. However, the Generator, Function, and ExpressionTree classes that together form the core of the GP algorithm can remain essentially unchanged.

The Cell class represents a grid cell. The AntTrailGrid class is used to perform graphics operations on the display grid panel. I won't describe these classes in detail as they pertain more to the user interface than to GP.

The Ant class and its associated TerminatingReport class represent the problem I'm trying to solve. An Ant is Figure 4 Class Design

initialized by passing a grid, a food goal, and a limit on the number of steps it will take. In my implementation I limit every ant to 400 steps. The Ant has public methods to turn and move, and private member variables to record the steps taken and food gathered as it moves through its grid. The Ant also maintains a history of where it's been on the grid in the private mTrail ArrayList. It also has a single, Boolean function: FacingFood.

Whenever an ant takes a step, it checks to see if it has reached its food goal or if it has taken the maximum number of steps allowed. If one of these is true, it saves its history in the member variable mConcludingReport, a TerminationReport. The TerminationReport records the food and step counts, and also saves the trail of the ant. The Fitness method of TerminationReport implements the fitness measure of an ant by returning an integer score that accounts for the food gathered and the steps taken. Ants that gather more food in fewer steps are more fit than other Ants that perform worse. TerminationReport also implements the CompareTo method of the IComparable interface. The CompareTo method compares TerminationReports according to fitness. When a generation completes, the Generator class will have hundreds or even thousands of TerminationReport instances in an ArrayList, and the IComparable implementation allows the ArrayList to be sorted by fitness.

Generator is the kernel of the GP implementation. It performs selection, breeding, code generation, execution, and result sorting. A generator is constructed by passing a BaseClass type (the Ant class, in this case), and a maximum expression tree depth limit. It uses reflection on the BaseClass type to find all of its public methods that have no parameters with the exception of the special NotFinished method. All of the void methods will be the primitive operations available for the GP algorithm to employ. Any Boolean methods with no parameters are used to control the execution of the primitive operators. This information is stored in Function objects. When NewGeneration is called requesting an initial population of N ants, it builds N random ExpressionTree objects. Generator uses these ExpressionTrees and CodeDOM classes to construct N subclasses of Ant, each of which has a single method called Execute. The Execute method has a loop of the expression tree statements that are executed as long as the NotFinished method returns true.

Generator places all of these classes in a single namespace, compiles them, and loads this new assembly. It then creates a single instance of each generated class, invokes its Execute method, and saves the TerminationReport. In a more robust implementation, each assembly would be isolated in its own AppDomain so that it could be unloaded when no longer needed. For demo purposes, I've chosen to keep things simple and to load all assemblies into the main AppDomain.

TerminationReport has a single, static method called GoalException. Generator uses this to create a special instance of the TerminationReport. This instance will have the same fitness as a perfect ant—one that gathered all available food in the minimum number of steps. Generator will continue with successive generations, performing selection and crossover breeding until it reaches the generation limit or it evolves a perfect ant.

Generator is a general-purpose implementation of GP. I stated earlier that you could define a different problem as a different "ant." Perhaps this ant would expose a set of primitive mathematical functions such as addition, multiplication, and exponentiation. Its grid would be a set of (x,y) input and output values from a function for which you would need to develop a mathematical expression. You could then essentially use Generator without change to solve this problem as well.

To be truly generic, the design needs to be changed, but only slightly. Generator uses TerminationReport directly to construct the goal exception of the perfect ant, and it also has some knowledge of the Init method that is used to pass the Grid to the ants that it instantiates. In the detailed discussion of Generator that follows, I'll describe what is needed to make it truly generic instead.