[ Home Page ] [ Eiffel Archive ] [ Eiffel Classes and Clusters ]

Genetic Algorithm classes

Written by I. M. Ikram

• 20 May 1996.
• Free for non-commercial use.
• Targets SmallEiffel -0.98.

ga.tar.gz (9803 bytes)

Introduction

Some simple genetic algorithm (GA) classes in Eiffel, aimed at solving optimization problems (both minimization and maximization). For a very quick and easy introduction to genetic algorithms, see http://www.cs.und.ac.za/~ikram/Projects/gaintro.html

You may modify and redistribute this code non-commercially. Please contact me if you wish to offer any comments, error reports, corrections, new classes, etc. Any updates made in future to these classes may be accessed through the URL: http://cs.und.ac.za/~ikram/Projects/GAEiffel/

These classes were developed with the aid of the excellent SmallEiffel freeware compiler, version -0.98, made available by Dominique Colnet and Suzanne Collin (ftp://ftp.loria.fr/pub/loria/genielog/SmallEiffel). Significant omissions from this version of the compiler are the BIT type, a standard random number class, and most of all, garbage collection (so I've been careful to avoid `memory leaks' here).

Files

ran.e	interface to `C' standard random number generation functions. Necessary external code is included in the file.
individual.e	individual_copyable.e: deferred classes relating to bit-string individuals
population.e, ss_population.e, gen_population.e	deferred classes relating to populations of bit strings
one_max.e, two_max.e, many_max.e, dejong_f1.e	some actual implementations of individuals corresponding to simple fitness functions
ss_pop_1.e, ss_pop_2.e, ss_pop_3.e, gen_pop_1.e	some actual implementations of populations capable of running simple genetic algorithms to solve optimization problems
ga_demo.e	allows any combination of the above fitness functions and genetic algorithms to be run

Class Hierarchy

RAN -- random numbers

INDIVIDUAL -- bit-string individuals         INDIVIDUAL_COPYABLE         -- reproducible individuals                 ONE_MAX, TWO_MAX, MANY_MAX, DEJONG_F1                 -- individuals meant to encode solutions to some simple optimization problems

POPULATION -- populations of bit-string individuals         SS_POPULATION         -- populations running steady-state algorithms                 SS_POP_1, SS_POP_2, SS_POP_3                 -- various steady-state strategies         GEN_POPULATION         -- populations running generational algorithms                 GEN_POP_1                 -- simple generational strategies

GA_DEMO -- demo/testing

Usage

See implementation of GA_DEMO class and header comments to the remaining classes.

Some quick notes

• To define a new optimization problem, write a subclass of INDIVIDUAL_COPYABLE with a routine called `evaluate,' which should set the value of the individual to some problem-dependent function of the individual's bit-string. See example classes at the bottom of the INDIVIDUAL hierarchy.
• To define a new genetic algorithm, subclass either SS_POPULATION or GEN_POPULATION, depending on whether it is to be a steady-state or a generational algorithm. The new class should have an `evolve' routine that implements one evolutionary step or generation. This routine should select parents from the current population for mating, and then evaluate the resulting children and place them (if needed) in the population. See example classes at the bottom of the POPULATION hierarchy.
• New subclasses may be tested by adding relevant clauses to the `inspect' instructions in GA_DEMO's `make_population' routine.

Suggested Improvements

• Currently, crossover is implemented by the `mate' routine in INDIVIDUAL. This is a one-point crossover operator between two individuals, creating two new ones. It should be simple to implement two-point and uniform crossover too.
• Make the INDIVIDUAL class generic so that it can implement genetic representations other than bit-strings. The representation type may then parameterize INDIVIDUAL.

[ Home Page ] [ Eiffel Archive ] [ Eiffel Classes and Clusters ]