At the forefront of Artificial Intelligence

Designing an AI Library

Last Updated: 4th December, 2001

After writing 3 applications as part of the Explorer-series, I was interested in creating a library of C++ classes that would encapsulate modern AI paradigms such as genetic algorithms, neural networks and the A* pathing algorithm as well additional algorithms such as hill-climbing, simulated annealing, minimax/alpha-beta pruning etc.

This TechFile will be updated as I add new things and learn lessons. The first installment will deal with initial lessons learning - think of more as a lesson of software engineering than artificial intelligence.

Part I: Initial Design

Before starting the project, I'd read up a lot on the STL and its intricacies: iterators, functors, and using templates - therefore, I started off using all these things very enthusiastically. I first started with genetic algorithms - so I created a templated genetic algorithm class (genetic_algorithm) that took two template parameters: the genotype and a GA functor to handle fitness calculation, mating and mutating. The genotype had to be derived from a base class genotype. This was also templated - 3 parameters that dictated the data type of the genotype and the range.

I soon realized that most genetic algorithms were actually arrays of values (for example, a genotype would be an array of integers to solve a diophantine equation), so I created an additional template class genotype_array that took the type and size of the vector.

To aid development, I created additional classes to handle various commonly used types of genotypes - such as integers, floats, chars and strings. I did this by deriving from genotype and implementing the necessary virtual functions, then creating aliases. Code is probably necessary at this point:

// **** In genotype.h ****
// stdgenotype: a standard genotype for ints, floats and chars.

template<class T, T l, T u> class stdgenotype : public genotype
{
    public:
        stdgenotype() { m_tGenoData = l + rand() % (u - l + 1); }
};

// **** In ga_aliases.h ****

template<int lwr, int top> class genotype_int : public stdgenotype<int, lwr, top> {};
template<char lwr, char top> class genotype_char : public stdgenotype <char, lwr, top> {};

While this seemed a great idea to begin with, the more and more I developed the system the more I found myself tripping over the templates. On retrospect, I also found it pointless to use templates to specify the ranges. Since vectors are dynamically created, they don't benefit from having a size. In fact, they would hinder operation at times since you couldn't assign two genotypes with the same data type but differing ranges, since the compiler sees them as two inherently different types.

Another problem which seems harder to overcome is the ridiculously long names that are associated with the class due to the iterators used:

typedef std::vector< geno_subtype >::iterator gaDataIterator;
typedef std::vector< geno_subtype >::const_iterator gaDataConstIterator;
typedef std::vector< geno_diophantine >::const_iterator gaConstIterator;

Nevertheless, someone versed in the STL shouldn't have a problem dealing with the necessary typedefs.

Results So Far

These architectural problems aside, the genetic algorithm code seems to work very well. Here is an example of a GA with a population of 100 (and elitism) running on the diophantine equation a + 2b + 3c + 4d + 5e + 6f + 7g + 8h = 320:

The best is:  24  13  24  12  -7  21   0   8  with a fitness of 5!
The best is:   4  22  -9   4   6   2  12  20  with a fitness of 3!
The best is:   4  22  -9   4   6   2  12  20  with a fitness of 3!
The best is: -22 -20 -25  22  24  21  -3  18  with a fitness of 0!

As you can see, the GA very quickly found a result (in 53.544 milliseconds actually).

Submitted: 04/12/2001

Article Toolbar

BibTeX entry