next up previous
Next: A new framework for Up: GAGSa flexible Previous: Introduction

Object-oriented programming and Genetic Algorithms

 

In order to implement a problem in an object oriented program, it is divided in objects whose interactions are well defined [Booch, 1994]. Those objects are grouped in classes with the same behavior, i.e., the same interface. That interface and sometimes the behavior can be inherited: new objects can be defined in terms of other object properties. Usually related classes are collected into what is called a class library, which is the C.4ex ++ equivalent of a C library; class libraries are usually referred to as toolboxes

Evolutinary computation is a paradigm in which, instead of dealing with only one solution to a problem, several solutions are pursued at the same time; these solutions are compared with each other, in such a way that only the best are kept; then they are changed (mutated) and combined with each other, to generate new solutions, that are in turn compared, and so on, until a predetermined number of generations are reached. Evolutionary computation paradigms, like genetic algorithms [Goldberg, 1989], evolutionary programming, genetic programming and evolution strategies, vary in the operators used to generate new solutions, but they all fall within the same framework.

Object oriented programming has been applied to EC as to any other algorithm from early on. The examples in Davis Genetic Algorithm handbook [Davis, 1987] use an object oriented version of LISP, which makes it have a flexibility other implementations lack. However, many more times a more mainstream language, like C.4ex++, has been used. Especially, two programs, TOLKIEN [Tang, 1994] and GAlib [Wall, 1995], stand out. Commercial packages have been left out, since only press releases are available to judge them; a more complete review can be found in [Filho et al., 1994].

In evolutionary computation, two main structures, or classes, come to mind: a chromosome structure, which is a representation the solution, and a population or genetic algorithm class, which includes all the chromosomes and operates on them in evolutionary fashion. Different object oriented EC toolkits implement these classes in a different way; and what is more important, provide for different procedures to change those structures in order to adapt them to a particular scientist's needs.

TOLKIEN includes a complete framewok for OO programming, a complete class library, and whatever is needed to program a GA. It is divided in different parts: crossover, selection, scaling scheme and population. It is somewhat extensible, but in order to program a GA, a whole set of operations (as many as 14) must be made to extend existing classes; besides, this can only be done at compile time. The operators provided are the only ones available, and they cannot be extended; population operators and size are also fixed. It has been implemented mainly for UNIX machines using GNU compilers, since it uses the GNU library for some of its functions, like bitstring manipulation; therefore, it is not portable to MS-DOS or Windows machines. Its support has been discontinued, and its author does not work on it any more.

Matthew's GAlib has been the latest addition to the list of OO GA implementations. It's based mainly around two classes: a chromosome class and a Genetic Algorithm class. Its main feature is the implementation of different kinds of chromosome representation: list, tree, array, and binary string, using templates, a C.4ex++ feature that allows to program type-independent classes. However, there is only provision for two operators in each chromosome: crossover and mutation, which must be defined for each kind of class that inherits from the Genome classes. The GA class concept is similar to that of the TOLKIEN package, with three predefined types of population selection and reproduction. It also relies on some builtin classes, so that it is more difficult to port.

Thus, in both libraries, chromosome-altering operators and population-changing operators are part of the public interface of the chromosome and population class; adding an operator means usually a major redesign of the class library, and can be done only at compile time. That is probably the reason why many people with special EC needs do not use them. Besides, restricting them to an UNIX using environment means banning them from the many people that uses Macs and Windows-based PCs.


next up previous
Next: A new framework for Up: GAGSa flexible Previous: Introduction

[JJ J. J. Merelo * jmerelo@kal-el.ugr.es[E-MAIL]
Equipo GeNeura -- GeNeura Team
Departamento de Electrónica y Tecnología de los Computadores
Universidad de Granada Granada (Espaņa)
Phone: +34-58-243162; Fax: +34-58-243230