Genetic Algorithm Library Overview

Contents

• Genetic Algorithm Library
• Structure of the Library
• Chromosomes
• Populations
• Algorithms
• Threading
• Catalogues
• Random Number Generators
• Chromosome Representations
• Built-in Fitness Comparators
• Built-in Crossover Operations
• Built-in Mutation Operations
• Built-in Coupling Operations
• Built-in Replacement Operations
• Built-in Scaling Operations
• Built-in Stop Criteria Operations
• Built-in Genetic Algorithms
• Links

Genetic Algorithm Library

This is brief introduction in the design and the structure of the Genetic Algorithm Library. The library is set of C++ classes that represent building blocks of genetic algorithms.

Structure of the Library

Next diagrams illustrate basic structure of Genetic Algorithm Library.

Diagram - Structure of Genetic Algorithm Library

The first layer mainly contains classes that are not directly related to genetic algorithms but are essential for their implementation. Genetic Algorithm Library implements random number generators, a set of classes for platform-independent threading and synchronization, smart pointers for easier management of memory [primarily for automatic management of memory used by chromosomes] and catalogues [catalogs are used to store and keep track of currently available genetic operations].

Except these general-purpose features, library provides some more GA specific stuff at the lowest layer such as classes for keeping track of statistical information of genetic algorithms and observing framework. Interfaces for genetic operations and parameters' objects are also defined at this layer.

Together these features provide common functionality that is used by other, higher layers of the library. Classes of this layer are split in several namespaces.

Mid-layer part is split in three namespaces, as shown at the diagram. Majority of the core features of the library are implemented at this layer.

First of all, Chromosome namespace contains set of interfaces and classes used to represent chromosomes in the library and to define their basic behavior in the system. This namespace contains declaration of interfaces for four types of genetic operations: crossover, mutation, fitness operation and fitness comparator.

The second namespace is Population namespace. Central class of this namespace is class that manages population of chromosomes, stores statistical information and tracks the best and the worst chromosomes. Interfaces for selection, coupling, replacement and scaling operations are defined in this namespace.

The last namespace, Algorithm, defines interfaces for genetic algorithms and implements some of their basic behaviors. This namespace also defines interface for operations that implements stop criteria of the algorithms.

These two layers represent the core of the library.

The top layer of the library implements earlier mentioned genetic operations, chromosomes representations and genetic algorithms. As mentioned all built-in genetic operations are sorted in appropriate catalogues.

Diagram - Namespaces

Chromosomes

Chromosomes are central objects in a genetic algorithm. Chromosomes are defined by GaChromosome class in this library.

Diagram - GaChromosome class

GaChromosome is interface for actual implementations of chromosomes. This class [interface] defines methods Crossover, Mutation, CalculateFitness and CompareFitness which represent previously described genetic operations [mutation, crossover, fitness operation and fitness comparator].

MakeCopy method represents virtual copy constructor. New classes should override this method and it should return new instance of chromosome's object. This method can copy entire chromosome [setup and coded solution] or it can copy just chromosome's setup [leaving empty encoding]. MakeFromPrototype method makes new chromosome's object with the same setup as the current object but it initializes encoding of the solutions randomly.

Each chromosome has defined parameters [such as crossover and mutation probability], these parameters are represented by GaChromosomeParams class.

Diagram - GaChromosomeParams class

GaChromosomeParams defines mutation and crossover probability, size of mutation and number of crossover points as well as "improving-only mutation" flag. Default chromosome's parameters initialized by default constructor are:

• mutation probability: 3%
• mutation size: 1 [only one value of coded solution is mutated]
• only improving mutations are accepted: yes
• crossover probability: 80%
• number of crossover points: 1

All parameter classes in the library inherit GaParameters class.

Diagram - GaParameters class

This class [interface] defines Clone method which represents virtual copy constructor and it should return pointer new parameters' object which is the copy of the current object.

GaChromosomes class is interface and it does not implements any behaviors. Still some basic features are common to all chromosome types [storing chromosome parameters and fitness value]; these features are implemented by GaDefaulChromosome class. Beside parameters chromosome can have other configuration data [Chromosome Configuration Block or CCB] and these data are usually same for all chromosomes in the population. Storing of chromosome's configuration data is defined by GaChromosomeParamBlock class.

Diagram - GaDefaultChromosome and GaChromosomeParamsBlock classes

Crossover and Mutation methods of GaDefaultChromosome class performs these genetic operations only with probability defined by chromosome's parameters. If the operations should be performed these methods call PerformCrossover and PerformMutation. New chromosomes that inherits GaDefaultChromosome class should override PerformCrossover and PerformMutation not the Crossover and Mutation methods.

This class also introduces framework for improving-only mutations. Before the mutation operation is executed, PrepareForMutation method is called, this method should backup old chromosome, and then mutation is performed. After that, old fitness of chromosome [before mutation] and new one are compared. If the mutation has improved fitness it is accepted and AcceptMutation method is called, otherwise RejectMutation method is called. If the "improving-only mutation" flag is not set, mutations are immediately accepted without calls to these methods.

Crossover, mutation and fitness operations can be implemented by inheriting the already defined class that implements specific type of chromosomes. Then user can override PerformCrossover [or Crossover], PerformMutation [or Mutation] and CalculateFitness methods and implement specific operations for the targeted problem.

Genetic Algorithm Library provides another way to accomplish this. These genetic operations can be defined and implemented in separated classes. Then references to object of these classes [called functors] can be stored in CCB. This allows user to change genetic operations at runtime [which is not possible with previously described method].

Diagram - GaDynamicOperationChromosome class and interfaces for genetic operations

GaDynamicOperationChromosome overrides PerformCrossover, PerformMutation, CalculateFitness and CompareFitnesses methods and routes calls to functors of genetic operations stored in CCB.

CCB represented by GaChromosomeOperationsBlock class stores these functors.

GaCrossoverOperation is interface for crossover operation. User defined classes should override operator():

virtual GaChromosomePtr operator ()(
    const GaChromosome* parent1,
    const GaChromosome* parent2) const;

The parameters are pointers to parents that are used by crossover operation. Operator should return smart pointer to produced offspring chromosome.

GaMutationOperation is interface for mutation operation. User defined classes should override operator():

virtual void operator ()(GaChromosome* chromosome) const;

This operator takes [as parameter] pointer to chromosome on which this operation should be performed.

GaFitnessOperation is interface for fitness operation. User defined classes should override operator():

virtual float operator ()(const GaChromosome* chromosome) const;

This operator takes [as parameter] pointer to chromosome on which this operation should be performed and returns calculated fitness value of the chromosome.

The last operation is fitness comparator. Interface for fitness comparators are defined by GaFitnessComparator class. User defined classes should override operator():

virtual int operator ()
    float fitness1,
    float fitness2) const;

This operator takes two fitness values as parameters and returns an integer:

1. -1 if the first fitness value is lower then the second
2. 0 if these two values are equal
3. 1 if the first value is higher then the second

All classes that implements genetic operations in the library inherit GaOperation class.

Diagram - GaOperation class

MakeParameters makes parameters' object that is needed by the operation, and returns pointer to the object. If operation does not require parameters, method can return NULL pointer. CheckParameters method checks validity of provided parameters and returns true it they are valid or false if they are invalid. All genetic operations must implement these two methods.

Genetic Algorithm Library is designed to use stateless objects of genetic operations [functors]. Following that design, all built-in operations are stateless, but the library can handle user defined operations whose objects are not stateless.

Populations

Diagram - GaPopulation class

Population stores chromosomes and statistical information. Chromosomes in the population are represented by objects of GaScaledChromosome class. Objects of this class bind chromosomes to population. Chromosomes generally stores data which do not depend on population in which chromosomes reside, but there is portion of information about chromosomes which are dependant [such as scaled fitness or index of chromosomes in population]. These data are members of GaScaledChromosome class. It makes sharing of chromosomes among populations easier and more [memory] efficient.

Chromosomes can be stored in population in sorted or unsorted order [by fitness value - scaled or raw]. Whether the population should be sorted or not depends on other parts of genetic algorithm [selection operation for instance] and it is controlled by the parameters of population. It is also easier to track the best and the worst chromosomes when population is sorted, but it is more time consuming. If it is not sorted, population use sorted groups [GaSortedGroup class] to track these chromosomes. Sorted groups store indices of chromosomes in population. Number of tracked chromosomes [in both groups, the best and the worst] is defined by the parameters of the population. It is important to notice that tracking large number of chromosomes is inefficient, in such case it is probably better to use sorted population.

When the population is created it does not contain any chromosomes [it is not initialized]. Initialize method fills population by making new chromosomes using MakeFromPrototype method of provided prototype chromosome.

Diagram - Chromosomes in the population

GaStatistics class is used for storing and tracking statistics of the population. Objects of this class stores information of the current and the previous generation of the population.

Diagram - GaStatistics and support classes

GaStatValue template class stores single statistical value. GaStatValueType enumeration defines tracked statistical data. These data can be used to measure progress of the algorithm, and they are usually employed by stop criteria.

Behavior of the population is controlled by parameters of the population. GaPopulationParameters class manages population's parameters.

Parameters are only one segment of population's configuration. Configuration also includes genetic operations [that are performed over population - selection, coupling, replacement and scaling] and their parameters. GaPopulationConfiguration class stores and manages configuration. Configuration can be shared among the populations. Method BindPopulation applies configuration and binds population to it. UnbindPopulation instructs population that it should not use the configuration any more and unbinds population. When some aspect of the configuration is changed, all bound populations are notified.

When an object of population's configuration is made and initialized using default constructor, the constructor copies default configuration. Reference to default configuration can be obtained using GetDefault method. User can change default configuration in run-time. At start the default configuration is initialized to:

• population parameters:
  • population size: 10
  • resizable: no
  • sorted: yes
  • scaled fitness value used for sorting: no
  • track the best chromosomes: 0 [sorted population]
  • track the worst chromosomes: 0 [sorted population]
• fitness comparator: GaMaxFitnessComparator
• selection: GaSelectRouletteWheel, size: 2
• coupling: GaInverseCoupling, size: 2
• replacement: GaReplaceWorst, size: 2
• scaling: none

Diagram - Management of population's configuration

Genetic operations and their parameters are stored as pair in the configuration. Configuration uses GaOperationParametersPair class to store these pairs. Pair object stores pointer to operation object and copy of provided object of operation's parameters.

Diagram - GaOperationParametersPair class

Interface for selection operations are defined by GaSelectionOperation class. User defined classes should override operator():

virtual void operator ()(
    const GaPopulation& population,
    const GaSelectionParams& parameters,
    GaSelectionResultSet& result) const;

Selection operation takes reference to population's object and reference to selection parameters. It also takes reference to result set which is used to store selected chromosomes. Result set stores indices [in population] of selected chromosomes in sorted order [by fitness value]. GaSelectionResultSet class wraps GaSortdeGroup class. GaSelectionOperation class has method MakeResultSet which makes new instance of result set and returns reference to it. User defined classes can override this method if selection operation requires different type of result set.

GaSelectionParams is base class for parameters of selection operations. This class defines only one parameter [which is common for all selection operations], selection size.

Diagram - Selection operation interface

Interface for coupling operations are defined by GaCouplingOperation class. User defined classes should override operator ():

virtual void GACALL operator ()(
    const GaPopulation& population,
    GaCouplingResultSet& output,
    const GaCouplingParams& parameters,
    int workerId,
    int numberOfWorkers) const=0;

Coupling operation takes reference to population's object and reference to coupling parameters. It also takes reference to result set [GaCouplingResultSet class] which is used to store produced offspring chromosomes and information about their parents.

Coupling operation can be executed concurrently by multiple working threads. Framework supplies number of threads that execute the operation and ID of thread that executes current call to the operation.

GaCouplingParams is base class for parameters of coupling operations. This class defines only one parameter [which is common for all coupling operations], number of offspring chromosomes which should be produced.

Diagram - Coupling operation interface

Interface for replacement operations are defined by GaReplacementOperation class. User defined classes should override operator():

virtual void GACALL operator ()(
    GaPopulation& population,
    const GaReplacementParams& parameters,
    const GaCouplingResultSet& newChromosomes) const;

Replacement operation takes reference to population's object, reference to replacement parameters and reference to result set of coupling operation which contains offspring chromosomes that should be inserted in the population.

GaReplacementParams is base class for parameters of replacement operations. This class defines only one parameter [which is common for all replacement operations], number of chromosomes which should be replaced.

Diagram - Replacement operation interface

Interface for scaling operations are defined by GaScalingOperation class. User defined classes should override operator(), IsRankingBase and NeedRescaling methods:

virtual float operator ()(
    const GaScaledChromosome& chromosome,
    const GaPopulation& population,
    const GaScalingParams& parameters) const;

virtual bool IsRankingBased() const;

virtual bool NeedRescaling(
    const GaPopulation& population,
    const GaScalingParams& parameters) const;

operator() takes reference to population's object and reference to scaling parameters.

IsRankingBased method should return true if the implementation of scaling operation is based on ranking of chromosomes. Otherwise it should return false.

GaScalingParams is base class for parameters of scaling operations.

Scaling can be based on values that can change from generation to generation, or it can use values that remain constant during longer time of evaluation process or values that are not changed at all. Scaled fitness value are calculated when new chromosome is inserted in population, but changing of population may require rescaling of fitness values of all chromosomes in the population. NeedRescaling method is called by the framework to check whether the rescaling is required at the end of each generation. If this method return true framework rescales fitness values of all chromosomes in the population.

Diagram - Scaling operation interface

Algorithms

Genetic algorithm object is glue for described building blocks. It defines and controls evolution process and determines its end. Interface for genetic algorithms are defined by GaAlgorithm class.

Diagram - GaAlgorithm class

StartSolving, StopSolving and PauseSolving methods allows user to controls evolution process and GetState methods can be used to obtain its current state. When user changes any part of the algorithm [genetic operation or its parameters] during runtime, BeginParameterChange method should be called before any change take place. When user finishes changes, user must call EndParameterChange method.

GaAlgorithmParams class represent base class for algorithm's parameters.

Genetic algorithm notifies rest of the system about changes in evolution process through observer pattern. User must call SubscribeObserver method to start receiving these notifications. When notification is no longer required user can call UnsubscribeObserver method. Objects that are passed to these two methods must be instances of classes inherited from GaObserver [or GaObserverAdapter] class implements methods.

Diagram - Algorithm observing

GaObserver is interface for observers of the genetic algorithm. Implementations of methods of this interface are actually event handlers. When an event occurs in genetic algorithm, the algorithm walks through the list of subscribed observers and calls appropriate observers' that handles the event.

virtual void StatisticUpdate(
    const GaStatistics& statistics,
    const GaAlgorithm& algorithm);

void NewBestChromosome(
    const GaChromosome& newChromosome,
    const GaAlgorithm& algorithm);

void EvolutionStateChanged(
    GaAlgorithmState newState,
    const GaAlgorithm& algorithm);

Lists of observers are managed by GaObserverList. This class also implements GaObserver interface, but instead of handling events it routes notifications to all subscribed observers. operator+= and operator-= are used to subscribe and unsubscribe observers.

// subscribe observer
observerList += observer; 

// ussubscribe observer
observerList -= observer;

When user-defined observer inherits GaObserver class it must implement all defined methods. Sometimes user does not want to receive all events. In this case user can use GaObserverAdapter class as base class for the observer. GaObserverAdapter class implements all methods defined by GaObserver with default event handling, the user can override only those methods that handles desired events.

End of evolution process is determined by stop criteria. Genetic Algorithm Library defines GaStopCriteria class that represent interface for this genetic operation. User defined class that implements stop criteria should override Evaluate method:

virtual bool Evaluate(
    const GaAlgorithm& algorithm,
    const GaStopCriteriaParams& parameters) const;

This method takes reference to algorithm's object whose state is evaluated and reference to parameters of the stop criteria. If algorithm reached required state and is should stop evolution this method should return true. If criteria is not reached, the method should return false.

GaStopCriteriaParams is base class for parameters of stop criteria.

Some default behaviors of genetic algorithm are implemented in GaBaseAlgorithm class.

Diagram - GaBaseAlgorithm class

This class manages state and state transitions of evolution process. Following diagram illustrates possible states of evolution process, transitions, actions that trigger transitions and reactions to the changes of the state.

Diagram - Algorithm's states

GaBaseAlgorithm implements StartSolving, StopSolving and PauseSolving methods that control evolution process. These methods perform state checks and state transitions. When the state of evolution process is changed, one of following virtual method is called OnStart, OnResume, OnPause, OnStopt. New classes that implement specific genetic algorithms should override these methods to handle state changes.

This class also manages list of subscribed observers and handles runtime changes by implementing BeginParameterChange and EndParameterChange methods that protects concurrent changes from multiple threads.

Genetic algorithms are convenient for parallelization because they operate on set of independent solutions. This allows genetic algorithms to take advantage of modern multiprocessor architectures with low [implementation and runtime] overheads.

Genetic Algorithm Library provides framework for parallel execution of genetic algorithms. This framework is built around GaMultithreadingAlgorithm class.

Diagram - GaMultithreadingAlgorithm class

Each multithreaded algorithm has one control thread and at least one working thread [worker]. Control thread prepares work, and then it transfer control to the workers. After all workers finish their portion of work, control thread gains control again and merges results produced by the workers. This class manages all used threads, so user does not have to worry about resources involved in multithreading.

Next diagram shows control flow of a multithreaded algorithm.

Diagram - Multithreaded algorithm workflow

GaMultithreadingAlgorithm class overrides OnStart, OnResume, OnPause, OnStop methods to control working and control threads.

ControlFlow and WorkFlow method represents flow of control and working threads. These methods provide synchronization and communication between control thread, workers and the rest of the system. Before ControlFlow transfer control to workers it calls BeforeWorkers method, and after workers finish it calls AfterWorkers method. Genetic algorithms implementations can override these methods to do specific work preparations and work merging. When worker gains control WorkFlow method calls WorkStep method. This method should be used to performer all of the work that can be executed simultaneously.

GaMultithreadingAlgorithmParams is base class for parameters of multithreaded algorithms. It defines number of workers involved in execution of genetic algorithm.

Threading

Genetic Algorithm Library contains set of classes, data types and macros that isolates platform-dependent threading. GaThread class wraps and controls system threads.

Diagram - GaThread class

GaThreadStatus enumeration defines possible states of the thread and GaThreadParameter structure is used to store start parameters of the thread.

Threading data types defined by the library:

GaCriticalSection isolates system-specific protection of critical sections from concurrent access by multiple threads. GaSectionLock class is used for automatic locking and unlocking of critical section objects.

// ...

GaCriticalSection _criticalSection;

// ...

void SomeMethod()
{
    // automatically acquires lock on _criticalSection synchronization object
    GaSectionLock lock( &_criticalSection, true );
	
    // ...critical section code...

    // lock object is destroyed when execution leave this scope
    // destructor of the object releases lock on used critical section object
}

Diagram - GaCriticalSection and GaSectionLock classes

Genetic Algorithm Library defines macros that make synchronization whit critical section objects easier. These macros are described later.

Synchronization data types:

Synchronization functions:

bool MakeSemaphore(
    SysSemaphoreObject& semaphore,
    int maxCount,
    int initialCount);

bool DeleteSemaphore(
    SysSemaphoreObject& semaphore);

bool LockSemaphore(
    SysSemaphoreObject& semaphore);

bool UnlockSemaphore(
    SysSemaphoreObject& semaphore,
    int count);

bool MakeEvent(
    SysEventObject& event,
    bool intialState);

bool DeleteEvent(
    SysEventObject& event);

bool WaitForEvent(
    SysEventObject& event);

bool SignalEvent(
    SysEventObject& event);

Synchronization macros:

ATOMIC_INC(VALUE)

ATOMIC_DEC(VALUE)

SPINLOCK(LOCK)

DEFINE_SYNC_CLASS

LOCK(LOCK_NAME)

UNLOCK(LOCK_NAME)

LOCK_OBJECT(LOCK_NAME,OBJECT)

LOCK_THIS_OBJECT(LOCK_NAME)

To use LOCK_OBJECT and LOCK_THIS_OBJECT macros to synchronize access to an object, class of the object must use DEFINE_SYNC_CLASS macro that injects members used by these macros.

Injected members are:

• mutable GaCriticalSection _synchronizator attribute and
• GaCriticalSection* GACALL GetSynchronizator() const method

class SomeClass
{

    DEFINE_SYNC_CLASS

    // rest of the class declaration

};

Then user can use macros to synchronize access to an object of the class.

void SomeMethod()
{
    SomeClass obj;

    // Declares GaSectionLock object obj_lock that
    // use critical section object embedded into obj object
    LOCK_OBJECT( obj_lock, obj );

    // ...critical section code...

    // lock is released automatically
    // by destroying obj_lock object
}

void SomeClass::SomeMethod()
{
    // Declares GaSectionLock object obj_lock that
    // use critical section object embedded into this object
    LOCK_THIS_OBJECT( obj_lock );

    // ...critical section code...

    // lock is released automatically
    // by destroying obj_lock object
}

If critical section ends before end of scope UNLOCK macro can be used to unlock critical section object.

void SomeClass::SomeMethod()
{
    // Declares GaSectionLock object obj_lock that
    // use critical section object embedded into this object
    LOCK_THIS_OBJECT( obj_lock );

    // ...critical section code...

    // release lock on critical section object
    UNLOCK( obj_lock );

    // ...non-critical code...

    // section can be locked again using same lock object
    LOCK( obj_lock );

    // ...critical section...
}

Locking is of critical section in possible without using objects of GaSectionLock objects. LOCK and UNLOCK macros can be used directly on critical sections objects.

// ...

GaCriticalSection _criticalSection;

// ...

void SomeMethod()
{
    // lock critical section object
    LOCK( _criticalSection );

    // ...critical section code...

    // release lock
    UNLOCK( _criticalSection );
}

Catalogues

Catalogues are used to store available genetic operations. Each type of genetic operation has its own catalogue. Genetic operations are stored in catalogue as a pair [operation name and pointer to operation object]. Name of the operation must be unique in the catalogue. User can obtain pointer to operation object (functors) by specifying operation name. GaCatalogue template class manages catalogues.

Diagram - GaCatalogue class

GaCatalogueEntry class is used to store pointer to genetic operation object and its name under which it is registered in catalogue.

Register and Unregister methods adds or removes genetic operation from catalogue. GetEntryData methods finds genetic operation by its name.

Genetic Algorithm Library defines eight built-in catalogues:

• GaCrossoverCatalogue
• GaMutationCatalogue
• GaFitnessComparatorCatalogue
• GaSelectionCatalogue
• GaCouplingCatalogue
• GaReplacementCatalogue
• GaScalingCatalogue
• GaStopCriteriaCatalogue

Before catalogue for specific type of operations can be used MakeInstance method must be called. FreeInstance should be called after the catalogue is no loner needed. For built-in catalogues these methods are called during initialization and finalization of the library. For user-defined catalogues user must manually call these methods.

// using built-in catalgue
GaSelectionOperation* select =
    GaSelectionCatalgoue::Instance().GetEntryData(
    "GaRandomSelect" );

// user-defined catalogue
GaCatalgoue<UserOperationType>::MakeInstance();

// register
GaCatalgoue<UserOperationType>::Instance().Register( 
    "UserOperation1", new UserOperation1() );
GaCatalgoue<UserOperationType>::Instance().Register( 
    "UserOperation2", new UserOperation2() );

// retrieve data 
UserOperationType* operation = 
    GaCatalgoue<UserOperationType>::Instance().GetEntryData(
    "UserOperation1" );

// unregister
GaCatalgoue<UserOperationType>::Instance().Unregister(
    "UserOperation1");

// free resources used by catalogue
GaCatalgoue<UserOperationType>::FreeIntance();

Catalogues manages memory used by the object of operations object that are registered.

Random Number Generators

Diagram - Random number generators

These random number generator classes have methods that generate numbers in predefined interval, between predefined minimum and user-defined maximum and between user-defined minimum and maximum. GaRandomBool has two additional methods that specify probability of true value being generated.

Chromosome Representations

Genetic Algorithm Library defines few interfaces that enable chromosomes to be used with built-in crossover and mutation operations.

GaMutableCode interface should be implemented by chromosomes that support random flipping or inverting of values in its code. This interface defines two methods Invert and Flip. Invert method should choose defined number of chromosome's code values and invert them. Flip method should change randomly defined number of chromosome's code values.

Diagram - GaMutableCode interface

GaSwapableCode interface should be implemented by chromosomes that can swap block of chromosome's code values. This interface defines Swap method.

Diagram - GaSwapableCode interface

GaSizableCode interface should be implemented by chromosomes that can change number of values in its code. Insert method should insert defined number of random values at specified position in chromosome's code. Remove method should remove block of values at specified position from chromosome's code.

Diagram - GaSizableCode interface

GaMultiValueCode interface should be implemented by chromosomes that can have more then one value in its code. This interface defines methods for extracting values from chromosome's code into buffers and initialization of chromosomes from buffers of values. MakeBuffer method should make buffer object that can store specified number of values and return pointer to the object. FillBuffer should copy block of values at specified position to buffer. FromBuffer method should initialize chromosome's code with values stored in provided buffer.

Diagram - GaMultiValueCode interface

GaCodeValuesBuffer class is used to manage buffers for storing values from chromosomes' codes. Buffer can be used to store values from multiple chromosomes so it is suitable combining chromosomes in crossover operations.

Diagram - GaCodeValuesBuffer class

GaArithmeticalCode interface should be implemented by chromosomes that support arithmetic operations over values in its code. This interface defines operators for basic arithmetic operations [+, -, *, /] and method for finding midpoint.

Diagram - GaArithmeticalCode interface

GaCodeValue interface should be implemented by classes that wrap data types of values in chromosome's code. This interface define FormBuffer method that should extract single value [at specified position] form provided buffer. Initialize method when implemented should randomly initialize wrapped value.

Diagram - GaCodeValue interface

In the most of the situations values in chromosome's code have constraints [domain]. These constraints in the library are realized via value sets. GaDomainChromosome class uses CCB that stores pointer to value set that defines constraints of values in chromosome's code.

Diagram - GaDomainChromosome and GaChromosomeDomainBlock classes

GaValuSet is base class for value sets in the library.

Diagram - GaValueSet class

GenerateRandom method randomly chooses one value from value set and returns it. Inverse method returns corresponding value from group of inverted values. Belongs method returns true if specified value belongs to value set. ClosestValue returns closest value to specified value which belongs to value set.

Each value set has group of values [called originals] and corresponding group of opposite values [called inverted values]. _viceVersa member define treatment of inverted values. If it is set to true inverted values are treated as valid members of value set, which means inverted values can be used with all defined operations of value set in a same way as original values.

GaSingleValueSet template class represents value set with only one original value and one inverted value. This value set is useful for values of chromosome's code that can have two possible states.

Diagram - GaSingleValueSet class

GaMultiValueSet template class represents value set with multiple values. Each value in group of originals has exactly one corresponding inverted value. Duplicates of original values are not allowed. Inverted values can be duplicated only if _viceVersa is set to false.

Diagram - GaMultiValueSet class

GaIntervalValueSet template class represents value set that contains continues values in specified interval. Bounds of interval are defined by GaValueIntervalBounds template class. Type of values in the set must have +, -, > , >= , < and <= operators defined. User must provide generator of random values that implements GaRandom interface.

Diagram - GaIntervalValueSet class

GaUnboundValueSet template class should be used when values of chromosome's code has no additional constraints. Type of stored values must have unary - operator defined. User must provide generator of random values that implements GaRandom interface. Range of values generated by this value set is determined only by provided random generator.

Diagram - GaUnboundValueSet class

GaCombinedValueSet can be used to merge two or more value sets into one set.

Diagram - GaCombinedValueSet class

GaSingleValueChromosome template class can be used for chromosomes represent solution with a single value. It can be single real or integer number or value of any other type. This class implements only GaMutableCode interface. Because SingleValueChromosome inherits GaDomainChromosome class, domain of value can be controlled by value set.

GaSVAChromosome template class is suitable for chromosomes that support arithmetic operations because it implements GaArithmeticalCode. Data type of chromosome's values must have +, -, *, / operators and operator / with right-hand side operand of integer type defined. This allows chromosomes to be used with built-in arithmetic crossover operations.

Diagram - GaSingleValueChromosome class

GaMultiValueValueChromosome template class can be used for chromosomes which requires multiple values to represent solution. This class implements GaMutableCode, GaSwapableCode, GaSizableCode and GaMultiValueCode interfaces. GaChromosomeValue class is used for injecting values into chromosome's code and extracting value.

GaMVAChromosome template class extends GaMultiValueValueChromosome in the same way that GaSVAChromosome extends GaSingleValueValueChromosome.

Diagram - GaMultiValueChromosome class

GaBinaryChromosome template class implements chromosomes that use binary encoding to presentation solution. This class has set of methods that encode built-in types to binary stream and that decode the stream into original values. GaBinaryChromosome uses GaBinaryChromosomeParams class for parameters of chromosomes. This class defines probability set state when chromosome is created.

GaBit class is used for injecting bits into chromosome's code or extracting them.

Diagram - GaBinaryChromosome class

These classes are located in Chromosome::Representation namespaces.

Built-in Fitness Comparators

Built-in fitness comparators are located in Chromosome::FitnessComparators namespace.

Diagram - Built-in fitness comparators

There are two fitness comparators:

• GaMaxFitnessComparator - are used for genetic algorithm which maximize fitness value,
• GaMinFitnessComparator - are used for genetic algorithm which minimize fitness value.

Built-in Crossover Operations

Built-in crossover operations are located in Chromosome::Crossover namespace.

Diagram - Built-in crossover operations

GaMutiValueCrossover class implements crossover operation which creates child by choosing N cross points and then it copies values from parents in turns, changing source parent each time it reaches chosen cross point. This operation requires chromosomes that implement GaMultiValueCode interface.

Diagram - Results of GaMutiValueCrossover operation

GaMidpointCrossover class implements crossover operation which creates child by invoking Midpoint method of chosen parents. This operation requires chromosomes that implement GaArithmeticalCode interface.

Diagram - Results of GaMidpointCrossover operation
[multi-value chromosome, type of values is int]

GaAddCrossover invokes operator+ of parent chromosome and GaSubCrossover invokes operator-.

Diagram - Results of GaAddCrossover operation
[multi-value chromosome, type of values is int]

Diagram - Results of GaSubCrossover operation
[multi-value chromosome, type of values is int]

Built-in Mutation Operations

Built-in crossover operations are located in Chromosome::Mutation namespace.

Diagram - Built-in mutation operations

GaSwapMutation class implements mutation operation which chooses two blocks of values in chromosome's code and swaps their positions in the code [maximal number of values that are swapped is defined by mutation size specified in parameters of chromosome].

Diagram - Results of GaSwapMutation operation

GaInvertMutation class implements mutation operation which chooses N values [maximal number of values is defined by mutation size specified in parameters of chromosome] and invert their values using Invert method of value set defined by the chromosome. This operation requires chromosomes that implement GaMutableCode interface.

Diagram - Results of GaInvertMutation operation

GaFlipMutation class implements mutation operation which chooses N values [maximal number of values is defined by mutation size specified in parameters of chromosome] and sets their values randomly using GenerateRandom method of value set defined by the chromosome. This operation requires chromosomes that implement GaMutableCode interface.

Diagram - Results of GaFlipMutation operation

Built-in Selection Operations

Built-in selection operations are located in Population::SelectionOperations namespace.

Diagram - GaSelectBest and GaSelectWorst selection operations

GaSelectBest class implements selection operation that selects N [defined by selection size in parameters of the operation] chromosomes which are the best in the population. If the population is not sorted, the operation can only select those chromosomes that are in the best chromosomes sorted group of the population.

GaSelectRouletteWheel and GaSelectTournament operations

GaSelectRouletteWheel class implements selection operation that selects chromosomes based on their fitness value. Fitness values of the chromosomes are used to calculate their probability of selection. When the genetic algorithm maximizes fitness, greater fitness means greater selection probability. If the genetic algorithm minimizes fitness, lower fitness means greater selection probability. The operation requires sorted population. If the population has defined scaling operation the selection uses scaled fitness values; otherwise it uses raw fitness values. This selection operation can select single parent more the once which can cause problems for some replacement operation. To avoid this, GaSelectRouletteWheel uses GaSelectDuplicatesParams class for its parameters to controls duplicates in selection result set.

GaSelectTournament uses similar method as GaSelectRouletteWheel. It performs N [defined by the parameters of the operation] "roulette wheel" selections for a single place in selection result set. The best chromosome among the chosen is placed in result set. This process is repeated to select all parents. The operation uses GaSelectTournamentParam class for its parameters.

Diagram - GaSelectRandom and GaSelectRandomBest operations

GaSelectRandom class implements selection operation which chooses parents randomly. The operation can select single parent more the once which can cause problems for some replacement operation. To avoid this, GaSelectRandom uses GaSelectDuplicatesParams class for its parameters to controls duplicates in selection result set.

GaSelectRandomBest works the same way as GaSelectRandom but it selects more parents then it is defined by the parameters, then it truncates result set so it can fit to desired selection size, leaving only the best parents in the set. GaRandomBestParams class is used by this operation and it defines number of parents to select before truncation.

Built-in Coupling Operations

Built-in coupling operations are located in Population::CouplingOperations namespace.

Diagram - Built-in coupling operations [1]

GaSimpleCoupling operation takes first two parents from the selection result set and then produces two offspring chromosomes using crossover operations, and each parent is bound to a one child, then it takes next two parents, and so on... If all parents are used, but more children should be produced, the operation restarts from the beginning of selection result set until enough children are produced. This coupling use GaCouplingParams class for its parameters.

Diagram - GaSimpleCoupling operation

Diagram - Built-in coupling operations [2]

GaCrossCoupling operation takes parents sequentially from the selection result set. If all parents are used, but more children should be produced, the operation restarts from beginning until enough children are produced.

Diagram - GaCrossCoupling operation

GaInverseCoupling operation takes the first parents sequentially from the selection results, and the second parents are the ones who are at the distance from the last chromosome in the selection results which is equal to distance of the first parent form the first chromosome in the result set. If all parents are used, but more children should be produced, the operation restarts from the beginning until enough children is produced.

Diagram - GaInverseCoupling operation

GaRandomCoupling operation takes the first parents sequentially from the selection result set, and the second parents are chosen randomly. If all parents are used as the first parents, but more children should be produced, the operation restarts from the beginning until enough children is produced.

Diagram - GaRandomCoupling operation

GaBestAlwaysCoupling operation always takes chromosome with the best fitness value in the selection result set for the first parent and the second parents are sequentially taken. If all parents are used, but more children should be produced, the operation restarts from the beginning until enough children is produced.

Diagram - GaBestAlwaysCoupling operation

When two parents are chosen, these operations produce specified number of children using crossover operation. Then they choose child with the best fitness value among produced children, store the child in the coupling result set and bounds one parent to the child. These couplings use GaMultipleCrossoverCouplingParams class for parameters to control number of produced children per parent's pair.

Built-in Replacement Operations

Built-in replacement operations are located in Population::ReplacementOperations namespace.

Diagram - GaReplaceWorst and GaReplacBest operations

GaReplaceWorst operation replaces the worst chromosomes in the population with offspring chromosomes form provided coupling result set. If the population is not sorted, the operation can replace only those chromosomes which are stored in the worst sorted group of the population. This operation uses GaReplacementParams class for its parameters.

GaReplaceBest operation works the same way as GaReplaceWorst, but it replaces the best chromosomes in the population.

Diagram - GaReplaceParents and GaReplaceRandom operations

GaReplaceParents operation replaces parents of the offspring chromosomes in provided coupling result set. As mentioned coupling operation stores information about chromosome's parent in the coupling result set. If this operation is used, selection operation should not select same chromosome more then once and coupling operation should not bound one parent to more the one child.

GaReplaceRandom operation randomly chooses chromosomes which are going to be replaced.

These two operations can remove the best chromosomes from the population, to prevent this, they implement elitism mechanism. GaReplaceElitismParams class is used by the operations and defines number of the best chromosomes in the population that are safe from the replacement operation.

Built-in Scaling Operations

Built-in scaling operations are located in Population::ScalingOperations namespace.

Diagram - GaWindowScaling and GaNormalizationScaling operations

GaWindowScaling operation calculates scaled fitness by subtracting fitness of the worst chromosome form fitness of the chromosome which is scaled [scaled_fitness = chromosome_fitness - worst_chromosome_fitness].

GaNoramlizationScaling operation calculates scaled fitness based on the ranking of the chromosome [scaled_fitness = population_size - chromosome_rank]. It requires sorted population.

These operations do not require parameters.

Diagram - GaLinearScaling and GaExponentialScaling operations

GaLinearScaling operation scales fitness values using linear transformation saled_fitness = a * fitness + b [a and b are scaling coefficients]. a and b are calculated in fallowing manner:

if( min_f > ( factor * avg_f - max_f ) / factor - 1 )
{
    a = avg_f / ( avg_f - min_f  );
    b = -1 * min_f * avg_f / ( avg_f - min_f );
}
else
{
    a = ( factor - 1 ) * avg_f / ( max_f - avg_f );
    b = avg_f * ( max_f - factor * avg_f ) / ( max_f - avg_f );
}

• min_f - fitness value of the worst chromosome in the population
• max_f - fitness value of the best chromosome in the population
• avg_f - average fitness value of all chromosomes in the population
• factor - scaling factor [used to multiply average fitness which determines scaled fitness value of the best chromosome in the population]

This operation cannot work with negative fitness values.

GaExponentialScaling operation calculates scaled fitness by raising chromosome's fitness value to specified power [specified by the parameters of the population].

Both operations use GaScaleFactorParams class for their parameters.

Built-in Stop Criteria Operations

Built-in stop criteria operations are located in Population::StopCriterias namespace.

Diagram - GaGenerationCriteria and GaGenerationCriteriaParams classes

GaGenerationCriteria is used to stop the genetic algorithm when it reaches desired number of generations. It uses GaGenerationCriteriaParams class as parameters.

Diagram - GaFitnessCriteria and GaFitnessCriteriaParams classes

GaFitnessCriteria decides when the algorithm should stop based on algorithm's statistical information of fitness values [raw or scaled, such as fitness of the best chromosome, average fitness or the fitness of the worst chromosome]. GaFitnessCriteriaComparison enumeration defines types of comparisons that can be used to compare desired fitness value with specified limit. GaFitnessCriteria uses GaFitnessCriteriaParams class as its parameters.

Diagram - GaFitnessProgressCriteria and GaFitnessProgressCriteriaParams classes

GaFitnessProgressCriteria decides when the algorithm should stop based on progress of algorithm's statistical information of fitness values. This criteria measure and track progress of desired value during the generations of the algorithm. It the algorithm fails to make desired progress in a single generation after defined number of generation, the criteria instructs algorithm to stop. GaFitnessProgressCriteriaParams class represents parameters for this criteria. Parameters' class also stores history of the algorithm's progress.

Built-in Genetic Algorithms

Built-in genetic algorithms are located in Population::SimpleAlgorithms namespace.

Diagram - Built-in genetic algorithms

GaSimplemAlgorithm class implements genetic algorithm with non-overlapping populations. User needs to supply population object [does not have to be initialized] when creating the genetic algorithm. The algorithm implements elitism and number of saved chromosomes are defined by the parameters of the algorithm [GaSimpleAlgorithmParams class]. The algorithm works in following manner:

1. create copy of supplied population object
2. initialize provided population object
3. select parents and produce offspring chromosomes
4. copy the best chromosome from the current population [elitism]
5. insert offspring chromosomes into new population
6. check stop criteria [exit if reached]
7. switch population objects an return to step 3.

GaIncrementalAlgorithm class implements genetic algorithm that uses overlapping population and replaces only few chromosomes per generation [using replacement operation]. User needs to supply population object [does not have to be initialized] when creating the genetic algorithm. The algorithm works in following manner:

1. initialize provided population object
2. select parents and produce offspring chromosomes
3. replace old chromosomes with offspring
4. check stop criteria [exit if reached]
5. switch population object an return to step 2.

Links

• Genetic Algorithm Library
• Genetic Algorithms Overview
• Using Genetic Algorithm Library
• Demo Applications
• Genetic Algorithm Library Documentation