top
 
FastGeneticSearch
Aspect-Oriented Genetic Search
DESCRIPTION:
In this demo, I use two techniques (mix-in classes and parameterized construction) to create an aspect-oriented implementation of a genetic search (or as aspect-oriented as C++ is capable of, at least). Source code as well as an executable are included.

This approach is a good compromise between fast iteration and code complexity: Finer grained functional decomposition makes it cheap to experiment, easy to test. Mix-ins make it easier to assemble various cross-cutting behaviors without deep (and exponentially many) inheritance chains. Particles is a good example of the sorts of systems that can benefit from this approach. The result is exponentially more behaviors for linearly more code. Examples of both techniques can
be found in MutationGeneticSearch.h

I'm using mix-ins and parameterized construction for AI in my framework, i.e., A* and Genetic Search. I want to mix and match stages of the algorithms and various definitions of my search space, roll in logging and testing services, etc, without defining exponentially many classes. With this scheme, each new policy requires only one new class. Another advantage is that inconsistencies between policies can usually be caught at compile time.

The drawbacks are the ugly syntax of templates and increased compile time. Also, the structure seen here relies on virtual functions, which can be avoided at a slight cost of flexibility (see "Improving Freelists with Policy Based Design" in GPG 5). Finally, this system could be enhanced with compile-time asserts to test whether base classes provide the required services.

An aspect-oriented approach could have been used for the genes and chromosomes in this example, but is an exercise for another day. Chromosomes in this example are arrays of random unsigned ints. Fitness is determined by how correctly the values are sorted. Though you'd never really sort numbers with a genetic search, this Chromosome makes a good test bed because it is easy to visualize and debug. But at the expense of some genuinely ugly template parameters, I was able to put together this experiment very quickly. As it is, this example is already overkill for the small number of behaviors presented, but would "pseudo-aspect" approach will be useful as the number of possible policies grew.

FILES:
AspectOrientedGeneticSearch.zip
 
 

Back to Main Page

COPYRIGHT 2008 JAMES STEWART. ALL RIGHTS RESERVED. bottom