Genetic Algorithm Library

• Download library source code - 279 KB
• Download demo applications source code - 85.81 KB
• Download demo applications - 138.83 KB
• Download library documentation - 1.03 MB
• Latest library releases

Genetic Algorithm Library Overview

• Genetic Algorithm Library Overview
  • Genetic Algorithms
  • 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
  • Examples
    • Example 1: Finding minimum of f(x, y) = 5*x*sin(x) + 1.1*y*sin(y); x, y in interval (0, 10)
    • Example 2: Pattern Matching
    • Example 3: Traveling Salesperson Problem
    • Example 4: Class Schedule
  • Portability, Compiling and Linking the Genetic Algorithm Library
    • Windows Platform
    • Linux, Mac OS X, Solaris, and *BSD Platforms
    • Portability
    • Changes
      • Version 1.4

Genetic Algorithms

Genetic algorithms operate on a set of possible solutions. Because of the random nature of genetic algorithms, solutions found by an algorithm can be good, poor, or infeasible [defective, erroneous], so there should be a way to specify how good that solution is. This is done by assigning a fitness value [or just fitness] to the solution. Chromosomes represent solutions within the genetic algorithm. The two basic components of chromosomes are the coded solution and its fitness value.

Chromosomes are grouped into population [set of solutions] on which the genetic algorithm operates. In each step [generation], the genetic algorithm selects chromosomes from a population [selection is usually based on the fitness value of the chromosome] and combines them to produce new chromosomes [offsprings]. These offspring chromosomes form a new population [or replace some of the chromosomes in the existing population] in the hope that the new population will be better than the previous ones. Populations keep track of the worst and the best chromosomes, and stores additional statistical information which can be used by the genetic algorithm to determine the stop criteria.

A chromosome, in some way, stores the solution which it represents. This is called the representation [encoding] of the solution. There are a number of probable ways to represent a solution in such a way that it is suitable for the genetic algorithm [binary, real number, vector of real number, permutations, and so on] and they mostly depend on the nature of the problem.

Genetic algorithms produce new chromosomes [solutions] by combining existing chromosomes. This operation is called crossover. A crossover operation takes parts of solution encodings from two existing chromosomes [parents] and combines them into a single solution [new chromosome]. This operation depends on the chromosome representation, and can be very complicated. Although general crossover operations are easy to implement, building specialized crossover operations for specific problems can greatly improve the performance of the genetic algorithm.

Before a genetic algorithm finishes the production of a new chromosome, after it performs a crossover operation, it performs a mutation operation. A mutation operation makes random, but small, changes to an encoded solution. This prevents the falling of all solutions into a local optimum and extends the search space of the algorithm. Mutations as well as crossover operations depend on the chosen representation.

Crossover and mutation operations are not always performed when producing a new chromosome. If crossover is not performed, the genetic algorithm produces a new chromosome by copying one of the parents. The rates of crossover and mutation operations are called crossover probability and mutation probability, respectively. The crossover probability is usually high [about 80%], and the mutation probability should be relatively low [about 3%, but for some problems, a higher probability gives better results]. A higher mutation probability can turn the genetic algorithm in to a random search algorithm.

The last operations defined by genetic algorithms used to manipulate chromosomes are fitness operations and fitness comparators. A fitness operation measures the quality of the produced solution [chromosome]. This operation is specific to the problem, and it actually tells the genetic algorithm what to optimize. Fitness comparators [as their name suggests] are used to compare chromosomes based on their fitness. Basically, a fitness comparator tells the genetic algorithm whether it should minimize or maximize the fitness values of chromosomes.

Choosing parents for the production of new chromosomes from a population is called selection. Selection can be based on many different criteria, but it is usually based on the fitness value. The idea behind this is to select the best chromosomes from the parents in the hope that combining them will produce better offspring chromosomes. But, selecting only the best chromosomes has one major disadvantage, all chromosomes in a population will start to look the same very quickly. This narrows the exploration space, pushes the genetic algorithm into the local optimum, and prevents the genetic algorithm from finding possibly better solutions that reside in inaccessible areas of the exploration space. To preserve the diversity of chromosomes [and a wider exploration space] within the population, selection operations usually introduce a factor of randomness in the selection process. Some implementations of selection operations are entirely random.

One problem may occur with selection operations that are based on fitness values. When there is a chromosome with a dominant fitness value, it will be selected most of the times, thus it will cause problems similar to the existing ones. To prevent this, fitness values can be scaled [transformed] to lower the difference between dominant chromosome(s) and the rest of the population [this allows other chromosomes to be selected]. There are many ways to transform a fitness value. Usually, they are implemented by applying a mathematical transformation to the fitness value, but there are other methods like ranking based scaling that use the rank [based on the raw fitness values of chromosomes] of a chromosome as the scaled fitness value.

A coupling operation defines how the selected chromosomes [parents] are paired for mating [mating is done by performing a crossover operation over the paired parents and applying a mutation operation to the newly produced chromosome]. This operation gives better control over the production of new chromosomes, but it can be skipped and new chromosomes can be produced as the selection operation selects parents from the population.

The next step performed by a genetic algorithm is the introduction of new chromosomes into a population. Offspring chromosomes can form a new population and replace the entire [previous] population [non-overlapping population], or they can replace only a few chromosomes in the current population [overlapping population]. For overlapping populations, the replacement operation defines which chromosomes are removed [usually the worst chromosomes] from the current population and which offspring chromosomes are inserted. By replacing chromosomes, there is a chance that the genetic algorithm will lose the best chromosome[s] [found so far]. To prevent this, the concept of elitism is introduced into genetic algorithms. Elitism guarantees that the best chromosome[s] from the current generation are going to survive to the next generation.

An algorithm performs the previously described steps one by one in sequence, and when they have been performed, it is said that a generation has passed. At the end of each generation, the genetic algorithm checks the stop criteria. Because of the nature of genetic algorithms, most of the time, it is not clear when the algorithm should stop, so a criteria is usually based on statistical information such as the number of the generation, the fitness value of the best chromosome, or the average fitness value of the chromosomes in the population, the duration of the evolution process...

Genetic Algorithm Library

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

Note: For more details about changes in recent versions of the library see this section of the article.

Structure of the Library

The following diagram illustrate the basic structure of the Genetic Algorithm Library:

The first layer mainly contains classes that are not directly related to genetic algorithms but are essential for their implementation. The 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 [catalogues are used to store and keep track of currently available genetic operations].

Except these general-purpose features, the 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 the 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.

The mid-layer part is split into three namespaces, as shown in the diagram. The majority of the core features of the library are implemented at this layer.

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

The second namespace is the Population namespace. The central class of this namespace is a class that manages the 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 an interface for operations that implement the stop criteria of the algorithms.

These two layers represent the core of the library.

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

Chromosomes

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

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

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

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

GaChromosomeParams defines the mutation and crossover probability, the size of the mutation, and the number of crossover points, as well as the "improving-only mutation" flag. The default chromosome parameters initialized by the 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 the GaParameters class.

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

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

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

This class also introduces a framework for improving-only mutations. Before the mutation operation is executed, the PrepareForMutation method is called. This method should backup the old chromosome, and then the mutation is performed. After that, the old fitness of the chromosome [before mutation] and the new one are compared. If the mutation has improved fitness, it is accepted, and the AcceptMutation method is called; otherwise, the 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 types of chromosomes. Then, the user can override the PerformCrossover [or Crossover], PerformMutation [or Mutation], and CalculateFitness methods and implement specific operations for the targeted problem.

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

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

The CCB, represented by the GaChromosomeOperationsBlock class, stores these functors.

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

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

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

GaMutationOperation is the interface for the mutation operation. The user defined classes should override operator():

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

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

GaFitnessOperation is the interface for the fitness operation. The user defined classes should override operator():

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

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

The last operation is the fitness comparator. The interface for fitness comparators are defined by the GaFitnessComparator class. The 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 than the second
2. 0 if these two values are equal
3. 1 if the first value is higher than the second

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

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

The 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

Population objects of genetic algorithms are represented in this library by the GaPopulation class.

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

Chromosomes can be stored in a 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 the genetic algorithm [the selection operation, for instance], and it is controlled by the parameters of the population. It is also easier to track the best and the worst chromosomes when the population is sorted, but it is more time consuming. If it is not sorted, the population uses sorted groups [the GaSortedGroup class] to track these chromosomes. Sorted groups store the indices of the chromosomes in the population. The 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 numbers of chromosomes is inefficient; in such cases, it is probably better to use a sorted population.

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

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

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

The behavior of the population is controlled by the parameters of the population. The GaPopulationParameters class manages a population's parameters.

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

When an object of a population's configuration is made and initialized using the default constructor, the constructor copies the default configuration. A reference to the default configuration can be obtained using the GetDefault method. A user can change the default configuration at 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

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

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

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

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

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

An interface for coupling operations is defined by the 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;

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

A coupling operation can be executed concurrently by multiple working threads. The framework supplies a number of threads that execute the operation and an ID of the thread that executes the current call to the operation.

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

An interface for replacement operations is defined by the GaReplacementOperation class. User defined classes should override operator():

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

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

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

An interface for scaling operations is defined by the GaScalingOperation class. User defined classes should override the 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 a reference to the population's object and a reference to the scaling parameters.
• IsRankingBased should return true if the implementation of the scaling operation is based on the ranking of chromosomes. Otherwise, it should return false.
• GaScalingParams is the base class for the parameters of the scaling operations.

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

Algorithms

A genetic algorithm object is a glue for the described building blocks. It defines and controls the evolution process, and determines its end. An interface for genetic algorithms is defined by the GaAlgorithm class.

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

The GaAlgorithmParams class represents the base class for the algorithm's parameters.

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

GaObserver is the interface for the observers of the genetic algorithm. Implementations of methods of this interface are actually event handlers. When an event occurs in the genetic algorithm, the algorithm walks through the list of subscribed observers and calls the appropriate observers that handle 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 the GaObserver interface, but instead of handling events, it routes notifications to all the subscribed observers. operator+= and operator-= are used to subscribe and unsubscribe observers.

// subscribe observer
observerList += observer;

// ussubscribe observer
observerList -= observer;

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

The end of the evolution process is determined by the stop criteria. The Genetic Algorithm Library defines the GaStopCriteria class that represents an interface for this genetic operation. The user defined class that implements the stop criteria should override the Evaluate method:

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

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

GaStopCriteriaParams is the base class for the parameters of the stop criteria.

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

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

GaBaseAlgorithm implements the StartSolving, StopSolving, and PauseSolving methods that control the evolution process. These methods perform state checks and state transitions. When the state of the evolution process is changed, one of the following virtual methods 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 a list of subscribed observers, and handles runtime changes by implementing BeginParameterChange and EndParameterChange methods that protect 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.

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

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

The following diagram shows the control flow of a multithreaded algorithm:

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

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

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

Threading

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

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

The threading data types defined by the library:

GaCriticalSection isolates system-specific protection of critical sections from concurrent access by multiple threads. The 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
}

The Genetic Algorithm Library defines macros that make synchronization with 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 the LOCK_OBJECT and LOCK_THIS_OBJECT macros to synchronize access to an object, the class of the object must use the 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
};

The 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 a critical section ends before the end of the scope, the UNLOCK macro can be used to unlock the 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 a critical section is possible without using GaSectionLock objects. The LOCK and UNLOCK macros can be used directly on critical section 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 a catalogue as a pair [operation name and pointer to the operation object]. The name of the operation must be unique in the catalogue. The user can obtain a pointer to the operation object (functors) by specifying the operation name. The GaCatalogue template class manages the catalogues.

The GaCatalogueEntry class is used to store pointers to genetic operation objects and the name under which it is registered in the catalogue.

The Register and Unregister methods add or remove genetic operations from a catalogue. The GetEntryData method finds genetic operations by their names.

The Genetic Algorithm Library defines eight built-in catalogues:

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

Before a catalogue for specific types of operations can be used, the 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 the initialization and the finalization of the library. For user-defined catalogues, the user must manually call these methods.

// using built-in catalogue
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 manage the memory used by objects that are registered.

Random Number Generators

The GaRandomGenerator class implements the RANROT algorithm for generating random numbers. It generates a 64-bit wide integer [two 32-bit integers] at a time. All other built-in random number generators in the library are built on top of this class.

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

Chromosome Representations

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

The 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. The Invert method should choose a defined number of chromosome's code values and invert them. The Flip method should change a randomly defined number of chromosome's code values.

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

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

The 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 the chromosome's code into buffers and the initialization of chromosomes from buffers of values. The MakeBuffer method should make a buffer object that can store a specified number of values and return a pointer to the object. FillBuffer should copy a block of values at a specified position to a buffer. The FromBuffer method should initialize a chromosome's code with values stored in a provided buffer.

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

The 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 a method for finding the midpoint.

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

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

The GaValuSet is a base class for value sets in the library.

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

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

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

The GaMultiValueSet template class represents a value set with multiple values. Each value in a 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.

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

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

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

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

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

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

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

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

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

These classes are located in the Chromosome::Representation namespaces.

Built-in Fitness Comparators

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

There are two fitness comparators:

• GaMaxFitnessComparator - used for genetic algorithms which maximize the fitness value,
• GaMinFitnessComparator - used for genetic algorithms which minimize the fitness value.

Built-in Crossover Operations

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

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

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

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

Built-in Mutation Operations

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

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

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

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

Built-in Selection Operations

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

The GaSelectBest class implements a selection operation that selects N [defined by the selection size in the 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.

The GaSelectRouletteWheel class implements a 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 a sorted population. If the population has defined a scaling operation, the selection uses the scaled fitness values; otherwise, it uses the raw fitness values. This selection operation can select a single parent more the once, which can cause problems for some replacement operations. To avoid this, GaSelectRouletteWheel uses the GaSelectDuplicatesParams class for its parameters to control duplicates in the selection result set.

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

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

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

Built-in Coupling Operations

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

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

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

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

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

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 have been used, but more children should be produced, the operation restarts from the beginning until enough children is produced.

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

Built-in Replacement Operations

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

The GaReplaceWorst operation replaces the worst chromosomes in the population with offspring chromosomes form the 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 the GaReplacementParams class for its parameters.

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

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

The 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 an elitism mechanism. The GaReplaceElitismParams class is used by the operations and defines the 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 the Population::ScalingOperations namespace.

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

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

These operations do not require parameters.

The GaLinearScaling operation scales the fitness values using linear transformation: scaled_fitness = a * fitness + b [a and b are scaling coefficients]. a and b are calculated in the following 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 the average fitness which determines the scaled fitness value of the best chromosome in the population]

This operation cannot work with negative fitness values.

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

Both operations use the GaScaleFactorParams class for their parameters.

Built-in Stop Criteria Operations

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

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

GaFitnessCriteria decides when the algorithm should stop based on the 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]. The GaFitnessCriteriaComparison enumeration defines the types of comparisons that can be used to compare the desired fitness value with a specified limit. GaFitnessCriteria uses the GaFitnessCriteriaParams class as its parameters.

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

Built-in Genetic Algorithms

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

The GaSimplemAlgorithm class implements a genetic algorithm with non-overlapping populations. The user needs to supply a population object [does not have to be initialized] when creating the genetic algorithm. The algorithm implements elitism, and a number of saved chromosomes are defined by the parameters of the algorithm [the GaSimpleAlgorithmParams class]. The algorithm works in the 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 and return to step 3.

The GaIncrementalAlgorithm class implements a genetic algorithm that uses an overlapping population and replaces only a few chromosomes per generation [using a replacement operation]. The user needs to supply a population object [does not have to be initialized] when creating the genetic algorithm. The algorithm works in the 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 and return to step 2.

Examples

The user must perform these steps to build a genetic algorithm with this library:

1. Choose representation of the chromosomes
2. Define fitness operation
3. Choose crossover and mutation operations and fitness comparator
4. Choose selection, coupling, replacement, and scaling operations
5. Choose type of algorithm and stop criteria

Example 1: Finding Minimum of f(x, y) = 5*x*sin(x) + 1.1*y*sin(y); x, y in interval (0, 10)

Important: before using the GAL, GaInitialize must be called. Also, before quitting the application, GaFinalize must be called.

The easiest way is to choose a multi-value chromosome's representation which supports arithmetic operations [the Chromosome::Representation::GaMVArithmeticChromosome<double> class].

After choosing a chromosome's representation, the user must define the fitness operation.

class fFitness : public GaFitnessOperation
{
public:

    virtual float GACALL operator() (const GaChromosome*
        chromosome) const
    {
        const vector<double>& vals=
            dynamic_cast<const GaMVArithmeticChromosome<double>*>
            (chromosome)->GetCode();

        return 5*vals[0]*sin(vals[0])+1.1*vals[1]*sin(vals[1]);
    }

    virtual GaParameters* GACALL MakeParameters() const { return NULL; }

    virtual bool GACALL CheckParameters(const GaParameters&
        parameters) const { return true; }
};

The fFitness class inherits the GaFitnessOperation class and overrides operator() which calculates the fitness value of the chromosome by evaluating the actual mathematical function.

The next step is to build a chromosome configuration block (CCB) which contains:

1. pointer to parameters of chromosomes
2. pointer to genetic operation functors [crossover, mutation, fitness operation, and fitness comparator]
3. pointer to value set which defines the domain of x and y variables

The class Chromosome::Representation::GaValueInterval<T> is used as the chromosome's value set because the domain of x and y variables is a continuous interval (0, 10). GaIntervalValueSet requires four bounds [low and high bounds to specify the interval of the original values, and low and high bounds to specify the interval of the inverted values] and a generator of random values.

GaValueIntervalBound<double /> valueInt(0,10);
GaValueIntervalBound<double /> invValueInt(0,10);
GaValueInterval<double /> valueSet(valueInt,invValueInt,
    GaGlobalRandomDoubleGenerator,false);

The CCB should be:

fFitness fitnessOperation;
GaChromosomeDomainBlock<double> configBlock(&valueSet,
    GaCrossoverCatalogue::Instance().GetEntryData(
    "GaMultiValueCrossover"),
    GaMutationCatalogue::Instance().GetEntryData("GaFlipMutation"),
    &fitnessOperation,
    GaFitnessComparatorCatalogue::Instance().GetEntryData(
    "GaMinFitnessComparator"),
    &chromosomeParams);

The CCB is defined to use the GaMultiValuesCrossover and GaFlipMutation operations. GaMinFitnessComparator is specified because the purpose of the algorithm is to find the minimum of the function.

When the CCB is defined, the user can build the prototype chromosome:

GaMVArithmeticChromosome<double> prototype(2,&configBlock);

Besides the prototype chromosome, the user must define the population's parameters before the population object can be created:

1. population size: 30
2. resizable population: no [incremental algorithm is used, which does not require resizable population]
3. population is sorted: yes
4. scaled fitness is used for sorting: no
5. tracking of the best chromosomes: 0 [population is already sorted]
6. tracking of the worst chromosomes: 0 [population is already sorted]

GaPopulationParameters populationParams(30,false,true,false,0,0);

This population object uses the default configuration, except it changes the sort comparator:

1. selection operations: GaSelectRouletteWheel
2. number of selected chromosomes: 2
3. coupling operation: GaInverseCoupling
4. offspring produced: 2
5. replacement operation: GaReplaceWorst
6. chromosomes replaced: 2
7. scaling operation: none
8. sort comparator: GaMaxFitnessComparator [default] changed to GaMinFitnessComparator

Everything is now ready to create the population object:

GaPopulationConfiguration populationConfig;
populationConfig.SetParameters(populationParams);
populationConfig.SetSortComparator(
    &configBlock.GetFitnessComparator());

GaPopulation population( &prototype, &populationConfig );

This example uses an incremental genetic algorithm [the GaIncrementalAlgorithm class]. To create the algorithm's object:

GaMultithreadingAlgorithmParams algorithmParams(1);
GaIncrementalAlgorithm algorithm(&population,algorithmParams);

where the user specifies the population on which the genetic algorithm will operate and the parameters of the algorithm. The constructor of the algorithm's parameters takes the number of working threads.

When the user builds a genetic algorithm for these kind of problems, it is not possible to know the exact termination criteria of the algorithm. In these situations, it is convenient to use a stop criteria based on the duration of the evolution process or its progress. One such stop criteria is a criteria based on the number of generations. The example uses only one thread because the algorithm produces only a few new chromosomes per generation.

GaGenerationCriteriaParams criteriaParams(100000);

algorithm.SetStopCriteria(
    GaStopCriteriaCatalogue::Instance().GetEntryData(
    "GaGenerationCriteria"),&criteriaParams);

The constructor of the criteria's parameters takes the number of generations after which the algorithm should stop.

To monitor the evolution process, the user must specify an observer object to the genetic algorithm.

class fObserver : public GaObserverAdapter
{
    virtual void GACALL NewBestChromosome(const GaChromosome&
        newChromosome,const GaAlgorithm& algorithm)
    {
        const vector<double>& vals=
            dynamic_cast<const GaMVArithmeticChromosome<double>&>
            (newChromosome).GetCode();
        cout << "New chromosome found:\n";
        cout << "Fitness: " << newChromosome.GetFitness() << endl;
        cout << "x: " << vals[0] << " y: " << vals[1] << endl;
    }

    virtual void GACALL EvolutionStateChanged(GaAlgorithmState
        newState,const GaAlgorithm& algorithm)
    {
        if(newState==GAS_RUNNING)
            cout << "start\n";
        else if(newState==GAS_CRITERIA_STOPPED)
            cout << "end";
    }
};

To register the observer:

fObserver observer;
algorithm.SubscribeObserver(&observer);

And to start the algorithm:

algorithm.StartSolving(false);

StartSolving's parameter defines whether the algorithm should continue a previously paused evolution process [true] or it should start an entirely new process [false].

Example 2: Pattern Matching

This example implements a genetic algorithm that tries to guess the sequence of characters. The example defines this sequence of characters:

const char pattern[] =
"        GGGGGGGGGGGGG               AAA               LLLLLLLLLLL             "
"     GGG::::::::::::G              A:::A              L:::::::::L             "
"   GG:::::::::::::::G             A:::::A             L:::::::::L             "
"  G:::::GGGGGGGG::::G            A:::::::A            LL:::::::LL             "
" G:::::G       GGGGGG           A:::::::::A             L:::::L               "
"G:::::G                        A:::::A:::::A            L:::::L               "
"G:::::G                       A:::::A A:::::A           L:::::L               "
"G:::::G    GGGGGGGGGG        A:::::A   A:::::A          L:::::L               "
"G:::::G    G::::::::G       A:::::A     A:::::A         L:::::L               "
"G:::::G    GGGGG::::G      A:::::AAAAAAAAA:::::A        L:::::L               "
"G:::::G        G::::G     A:::::::::::::::::::::A       L:::::L               "
" G:::::G       G::::G    A:::::AAAAAAAAAAAAA:::::A      L:::::L         LLLLLL"
"  G:::::GGGGGGGG::::G   A:::::A             A:::::A   LL:::::::LLLLLLLLL:::::L"
"   GG:::::::::::::::G  A:::::A               A:::::A  L::::::::::::::::::::::L"
"     GGG::::::GGG:::G A:::::A                 A:::::A L::::::::::::::::::::::L"
"        GGGGGG   GGGGAAAAAAA                   AAAAAAALLLLLLLLLLLLLLLLLLLLLLLL";
const int patternSize=sizeof(pattern)-1;

UThe ued symbols are: G,A,L,: and a white space.

The genetic algorithm uses a Chromosome::Representation::GaMVArithmeticChromosome<double> chromosome representation with a defined domain of values by the Chromosome::Representation::GaMultiValueSet<char> class.

GaMultiValueSet<char> valueSet(false);
valueSet.Add("GAL: ","     ",5);

The fitness operation calculates the percent of matched characters and returns that number as the fitness value of the chromosomes:

class pFitness : public GaFitnessOperation
{
public:

    virtual float GACALL operator()(const GaChromosome*
        chromosome) const
    {
        const vector<char>& v=
            dynamic_cast<const GaMultiValueChromosome&ltchar>*>
            (chromosome)->GetCode();

        int score=0;
        for(int i=0;i&ltpatternSize;i++)
        {
            if(v[i]==pattern[i])
            score++;
        }

        return (float)score/patternSize*100;
    }

    virtual GaParameters* GACALL MakeParameters() const
        { return NULL; }

    virtual bool GACALL CheckParameters(const GaParameters&
        parameters) const { return true; }
};

The CCB looks like the CCB in the previous example, except it uses a new fitness operation and another fitness comparator, because its objective now is to maximize the fitness:

pFitness fitnessOperation;
GaChromosomeDomainBlock<char /> configBlock(&valueSet,
    GaCrossoverCatalogue::Instance().GetEntryData(
    "GaMultiValueCrossover"),
    GaMutationCatalogue::Instance().GetEntryData("GaFlipMutation"),
    &fitnessOperation,
    GaFitnessComparatorCatalogue::Instance().GetEntryData(
    "GaMaxFitnessComparator"),
    &chromosomeParams);

Prototype chromosome:

GaMultiValueChromosome<char> prototype( patternSize, &configBlock );</char>

This example uses a genetic algorithm with non-overlapping populations, and it produces the entire population. To increase the diversity of the produced chromosomes, the number of selected chromosomes is increased. Note that this type of an algorithm requires a resizable population. The population object and its configuration:

GaPopulationParameters populationParams(30,true,true,false,0,0);

GaPopulationConfiguration populationConfig;
populationConfig.SetParameters(populationParams);
populationConfig.SetSortComparator(
    &configBlock.GetFitnessComparator());
populationConfig.Selection().GetParameters().SetSelectionSize(6);

GaPopulation population(&prototype, &populationConfig);

As mentioned, this example uses the Algorithm::SimpleAlgorithms::GaSimpleAlgorithm class for the genetic algorithm.

GaSimpleAlgorithmParams algorithmParams(10,2);
GaSimpleAlgorithm algorithm(&population,algorithmParams);

The first argument of the parameters' constructor is the elitism depth and the second is the number of working threads. This algorithm produces much more chromosomes per generation than the previous one, so it is suitable for parallelization.

In this example, the exact termination condition is known: when the algorithm finds the chromosome with a fitness value of 100 [100% match]. The right stop criteria is Algorithm::StopCriterias::GaFitnessCriteria:

GaFitnessCriteriaParams criteriaParams(100,GFC_EQUALS_TO,
    GSV_BEST_FITNESS);
algorithm.SetStopCriteria(
    GaStopCriteriaCatalogue::Instance().GetEntryData(
    "GaFitnessCriteria"),
    &criteriaParams);

The observer of the algorithm displays the best chromosomes as they are found:

class pObserver : public GaObserverAdapter
{
public:
    virtual void GACALL NewBestChromosome(const GaChromosome&
        newChromosome,const GaAlgorithm& algorithm)
    {
        const vector<char>& v=
        dynamic_cast<const GaMultiValueChromosome<char>&>
            (newChromosome).GetCode();

        cout<<"Generatiron: "<<
            algorithm.GetAlgorithmStatistics().GetCurrentGeneration()
            <<endl;
        cout<<"Fitness: "<<newChromosome.GetFitness();
        cout<<"\n-------------------------\n";

        for(int i=0;i<v.size();i++)
        {
            if(!(i%78))
                cout<<endl;

            cout<<v[i];
        }
        cout<<"\n-------------------------\n";
    }

    virtual void GACALL EvolutionStateChanged(GaAlgorithmState
        newState,const GaAlgorithm& algorithm)
    {
        if(newState==GAS_CRITERIA_STOPPED)
            cout<<"end.";
    }
};

The subscription of the observer is the same as in the previous example:

pObserver observer;
algorithm.SubscribeObserver( &observer );

The starting of the evolution:

algorithm.StartSolving(false);

Example 3: Traveling Salesperson Problem

The chromosome is an array of cities [pointers to objects of the TspCity class] in the order in which they are visited. It is implemented by the TspChromosome class. The class inherits GaMultiValueChromosome to implement a custom initialization of the chromosome by overriding the MakeFromPrototype method. This method copies cities into the chromosomes' code and then it shuffles their positions. This class also overrides the MakeCopy method and defines a copy constructor.

class TspChromosome : public GaMultiValueChromosome<const TspCity*>
{
public:
    TspChromosome(GaChromosomeDomainBlock<const TspCity*>* configBlock) :
        GaMultiValueChromosome(configBlock) { }

    TspChromosome(const TspChromosome& chromosome,
        bool setupOnly) :
        GaMultiValueChromosome<const TspCity*>(chromosome, setupOnly) { }

    virtual GaChromosomePtr GACALL MakeCopy(bool setupOnly) const
        { return new TspChromosome( *this, setupOnly ); }

    virtual GaChromosomePtr GACALL MakeNewFromPrototype() const;

    int GACALL GetCityPosition(const TspCity* city) const;
};

Using a simple single-point or multi-point crossover operation will generate a large amount of invalid solutions which degrades the algorithm's performance and results. To prevent the generation of invalid solutions, the algorithm uses a custom crossover operation. The operation takes a random city from one parent and copies it to the child chromosome. Then, it searches for the cities which are connected to the chosen city [in both parents] and takes the nearest one [and copies it to the child chromosome] if it is not already taken. It is taken if the operation chooses another connected city. If all the connected cities are taken, the operation randomly chooses a city that has not been taken. Then, the crossover uses that city to extend the path in the same way. The process is repeated to select all the cities. The TspCrossover class implements this crossover operation:

class TspCrossover : public GaCrossoverOperation
{
public:
    virtual GaChromosomePtr GACALL operator ()(
        const GaChromosome* parent1,
        const GaChromosome* parent2) const;

    virtual GaParameters* GACALL MakeParameters() const { return NULL; }

    virtual bool GACALL CheckParameters(
        const GaParameters& parameters) const { return true; }

private:
    inline void SelectNextCity(const TspCity* previousCity,
        const TspCity** currentBestNextCity,
        const TspCity* nextCity) const;
};

The algorithm uses the built-in GaSwapMutation operation. The fitness value is equal to the length of the path. The TspFitnessOperation class implements the fitness operation:

class TspFitness : public GaFitnessOperation
{
public:
    virtual float GACALL operator ()(
        const GaChromosome* chromosome) const;

    virtual GaParameters* GACALL MakeParameters() const { return NULL; }

    virtual bool GACALL CheckParameters(
        const GaParameters& parameters) const { return true; }
};

Parameters of chromosomes:

1. mutation probability: 3%
2. mutation size: 2
3. improving only mutations: no
4. crossover probability: 80%
5. number of crossover points: 1 [ignored]

CCB:

1. TspCrossover
2. TspSwapMutation
3. TspFitnessOperation
4. TspMinFitnessComparator
5. Value set is not defined

Population parameters:

1. population size: 100
2. resizable population: no [an incremental algorithm is used which does not require a resizable population]
3. population is sorted: yes
4. scaled fitness is used for sorting: no
5. tracking of the best chromosomes: 0 [population is already sorted]
6. tracking of the worst chromosomes: 0 [population is already sorted]

Configuration of the population:

1. GaSelectRandomBest selection which selects 8 chromosomes
2. GaSimpleCoupling which produces 8 offspring chromosomes
3. GaRandomReplaces which replaces 8 chromosomes in each generation, with an elitism size of 10 chromosomes
4. No scaling operation

The algorithm uses GaFitnessProgressCriteria because the exact termination condition is not known. The criteria will stop the algorithm if it is unable to improve the fitness value for more than 1 in 50000 generations. The genetic algorithm is incremental.

The TSP class is the container for the object of the algorithm. The TspCity class represents and stores information about a city [such as its coordinates and name]. It has the GetDistance method which calculates the distances between the cities. TspCities manages the collection of cities entered by the user.

Example 4: Class Schedule

The genetic algorithm for making the class schedule is already described here. In this article, the demo application demonstrates the solution of the same problem using the Genetic Algorithm Library.

The Schedule class defines a chromosome's representation. It inherits GaMultiValueChromosome.

class Schedule : public GaMultiValueChromosome<list<CourseClass*> >
{
    friend class ScheduleCrossover;
    friend class ScheduleMutation;
    friend class ScheduleFitness;
    friend class ScheduleObserver;

private:
    CourseClassHashMap _classes;

    CourseClassHashMap _backupClasses;

    // Flags of class requirements satisfaction
    mutable vector<bool> _criteria;

public:
    Schedule(GaChromosomeDomainBlock<list<CourseClass*> >* configBlock);

    Schedule(const Schedule& c, bool setupOnly);

    virtual ~Schedule() { }

    virtual GaChromosomePtr GACALL MakeCopy(bool setupOnly) const
        { return new Schedule( *this, setupOnly ); }

    virtual GaChromosomePtr GACALL MakeNewFromPrototype() const;

    virtual void GACALL PreapareForMutation();

    virtual void GACALL AcceptMutation();

    virtual void GACALL RejectMutation();

    // Returns reference to table of classes
    inline const hash_map<courseclass*, />& GetClasses() const
        { return _classes; }

    // Returns array of flags of class requirements satisfaction
    inline const vector<bool>& GetCriteria() const
        { return _criteria; }

    // Return reference to array of time-space slots
    inline const vector<list<CourseClass*>>& GetSlots() const
        { return _values; }
};

Then the crossover, mutation, and fitness operations are defined:

class ScheduleCrossover : public GaCrossoverOperation
{
public:
    virtual GaChromosomePtr GACALL operator ()(
        const GaChromosome* parent1,
        const GaChromosome* parent2) const;

    virtual GaParameters* GACALL MakeParameters() const
        { return NULL; }

    virtual bool GACALL CheckParameters(
        const GaParameters& parameters) const { return true; }

};

class ScheduleMutation : public GaMutationOperation
{
public:

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

    virtual GaParameters* GACALL MakeParameters() const
        { return NULL; }

    virtual bool GACALL CheckParameters(
        const GaParameters& parameters) const { return true; }

};

class ScheduleFitness : public GaFitnessOperation
{
public:

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

    virtual GaParameters* GACALL MakeParameters() const
        { return NULL; }

    virtual bool GACALL CheckParameters(
        const GaParameters& parameters) const { return true; }
};

For more information about the chromosome representation and these operations, see this article.

The ScheduleTest class is the container for the objects of the genetic algorithm.

ScheduleTest::ScheduleTest()
{
  // initialize GAL internal structures
  GaInitialize();

  // make chromosome parameters
  // crossover probability: 80%
  // crossover points: 2
  // no "improving only mutations"
  // mutation probability: 3%
  // number of moved classes per mutation: 2
  _chromosomeParams = new GaChromosomeParams(
    0.03F, 2, false, 0.8F, 2 );

  // make CCB with fallowing setup:
  // there are no value set
  // with ScheduleCrossover, ScheduleMutation and
  // ScheduleFitness genetic operations
  // set fitness comparator for maximizing fitness value
  // use previously defined chromosome's parameters
  _ccb = new GaChromosomeDomainBlock<list<courseclass* /> >(
    NULL, &_crossoverOperation, &_mutationOperation,
    &_fitnessOperation,
    GaFitnessComparatorCatalogue::Instance().GetEntryData(
    "GaMaxFitnessComparator" ),
    _chromosomeParams );

  // make prototype of chromosome
  _prototype = new Schedule( _ccb );

  // make population parameters
  // number of chromosomes in population: 100
  // population always has fixed number of chromosomes
  // population is not sorted
  // non-transformed(non-scaled) fitness values are used
  // for sorting and tracking chromosomes
  // population tracks 5 best and 5 worst chromosomes
  GaPopulationParameters populationParams(
    100, false, true, false, 2, 0 );

  // make parameters for selection operation
  // selection will choose 16 chromosomes
  // but only 8 best of them will be stored in selection result set
  // there will be no duplicates of chromosomes in result set
  GaSelectRandomBestParams selParam( 10, false, 16 );

  // make parameters for replacement operation
  // replace 8 chromosomes
  // but keep 5 best chromosomes in population
  GaReplaceElitismParams repParam( 10, 2 );

  // make parameters for coupling operation
  // coupling operation will produce 8 new chromosomes
  // from selected parents
  GaCouplingParams coupParam( 10 );

  // make population configuration
  // use defined population parameters
  // use same comparator for sorting as comparator used by chromosomes
  // use selection operation which randomly selects chromosomes
  // use replacement operation which randomly chooses
  // chromosomes from population
  // which are going to be replaced, but keeps best chromosomes
  // use simple coupling
  // disable scaling
  _populationConfig = new GaPopulationConfiguration( populationParams,
    &_ccb->GetFitnessComparator(),
    GaSelectionCatalogue::Instance().GetEntryData(
    "GaSelectRandom" ), &selParam,
    GaReplacementCatalogue::Instance().GetEntryData(
    "GaReplaceRandom" ), &repParam,
    GaCouplingCatalogue::Instance().GetEntryData(
    "GaSimpleCoupling" ), &coupParam,
    NULL, NULL );

  // make population
  // with previously defined prototype of chromosomes
  // and population configuration
  _population = new GaPopulation( _prototype, _populationConfig );

  // make parameters for genetic algorithms
  // algorithm will use two workers
  GaMultithreadingAlgorithmParams algorithmParams( 2 );
  // make incremental algorithm with previously defined population
  // and parameters
  _algorithm = new GaIncrementalAlgorithm(
    _population, algorithmParams );

  // make parameters for stop criteria based on fitness value
  // stop when best chromosome reaches fitness value of 1
  GaFitnessCriteriaParams criteriaParams(
    1, GFC_EQUALS_TO, GSV_BEST_FITNESS );

  // sets algorithm's stop criteria (base on fitness value)
  // and its parameters
  _algorithm->SetStopCriteria(
    GaStopCriteriaCatalogue::Instance().GetEntryData(
    "GaFitnessCriteria" ), &criteriaParams );

  // subscribe observer
  _algorithm->SubscribeObserver( &_observer );
}

Portability, Compiling, and Linking the Genetic Algorithm Library

The Genetic Algorithm Library supports the following compilers and platforms:

The library contains a set of preprocessor directives that control the compilation process according to the detected compiler and the targeted operating system.

Windows Platform

The Genetic Algorithm Library is available in two versions of Visual Studio 2005 projects. The first one is configured to use the Microsoft C/C++ compiler and the second one uses the Intel C++ compiler. Projects are located in /vs directory.

To add the Genetic Algorithm Library functionality to the application, the library must be linked with it. There are two methods to do this in Visual Studio 2005:

• Method 1

  Adding the Genetic Algorithm Library project to the application's solution, and then setting a reference to the Genetic Algorithm Library project.

• Method 2
  1. Adding GeneticAlgorithm.lib to Project Properties->Linker->Additional Dependencies.
  2. Setting the proper directories so that Visual Studio can find the library and its headers. This can be done locally or globally.
     1. Locally
        • Adding GeneticLibrary.lib to:

          Project Properties->Linker->General->Additional Library Directories

        • Adding the Genetic Algorithm Library source code directory (/source) to preprocessor searches:

          Project Properties->C/C++->General->Additional Include Directories

     2. Globally by adding directories into the appropriate places (Include files and Library files)

        Tools->Options->Projects and Solutions->VC++ Directories

The procedures are same for both versions of the project.

The library can be compiled as a static or dynamic [DLL] library. It is compiled as a DLL, by default; if it is compiled and used as a static library, GENETICLIBRARY_STATIC must be defined.

Output files are GeneticLibrary.dll and GeneticLibrary.lib when the library is compiled as a DLL, or only GeneticLibrary.lib if it is compiled as a static library. These files are located in the /build/%configuration%/%compiler% directory, where %configuration% is debug or release, and %compiler% is msvc for the Microsoft C/C++ compiler, or icc_win for the Intel C++ compiler. The GeneticLibrary.dll file must be copied to the same directory where the executable file of the application resides.

The Genetic Algorithm Library is linked against the dynamic version of the common run-time libraries [CRT], by default. When the library is linked against the dynamic version of the CRT, the application may fail to start on machines which do no have the Microsoft Visual C++ 2005 Redistributable Package installed. It is important to notice that the application which uses the Genetic Algorithm Library must be linked against the same version CRT as the library.

Linux, Mac OS X, Solaris, and *BSD Platforms

The compilation of the library can be done from the console by invoking make with an appropriate Makefile. On the Solaris operating system, gmake is used for compiling the library with GCC G++ and dmake for compiling with Sun Studio C++. For *BSD systems, use GNU make [gmake] instead of BSD make [make].

make -f %compiler%_%platform%_%configuration% all

where %compiler% is:

• gcc - for GCC G++ compiler.
• icc - for Intel C++ compiler.
• scc - for Sun Studio C++ compiler.

%platform%s are the following:

• linux - for the Linux family of operating systems.
• macos - for the Mac OS X operating system.
• solaris - for the Solaris operating system.
• bsd - for the BSD family of operating systems.

and the configuration is one of these:

• debug - compiles the library with debugging information and no optimization.
• release - compiles the library with optimized code generation, and it strips the debugging information.

Makefiles are available in the /makefiles directory.

make -f icc_linux_debug all

Example: Compilation as Debug on Linux using Intel C++

gmake -f gcc_bsd_release all

Example - Compilation as Release on FreeBSD using GCC G++

The output file is a static library named libGeneticLibrary.a and it is located in the /build/%configuration%/%compiler%_%platform% directory.

To link the Genetic Algorithm Library with an application, the user must specify a path to the library and the name of the library file:

g++ -Wl,-L"%path_to_library%/build/%configuration%/%compiler%_%platform%"
     -lGeneticLibrary -o "application_executable" [list of object files]

For the Intel C++ compiler, the user should use the icpc command instead of g++, and for the Sun Studio C++ compiler, the cc command.

%path_to_library% is the path to the directory where the library is located. On some platforms, there are additional requirements for linking the application with the Genetic Algorithm Library. On Linux, the -lrt switch must be specified to the linker. The Sun Studio linker requires the -library=stlport4 and -lrt switches, and the GNU linker on *BSD system requires the -march=i486 and -lpthread switches.

Portability

To port this library to other platforms with no major changes to the core of the library, the targeted platform must support:

• Multithreading - if the targeted platform has POSIX Threads support, porting can be easier because the Genetic Algorithm Library already employs Pthreads for multithreading on UNIX-like systems.
• Atomic increment, decrement operations as well as atomic compare and exchange instructions or atomic exchange operation.
• STL - The Genetic Algorithm Library relies, in some segments, on STL and some nonstandard STL extensions such as hash_map.
• IEEE754 standard for floating point numbers - some parts of the library, like the random number generator, assumes that the targeted processor architecture supports this standard.

Changes

Version 1.4

• Return value of operator== in GaChromosome interface is now bool. operator != is also added to GaChromosome interface. This change also affects: GaMultiValueChromosome, GaSingleValueChromosome and GaBinaryChromosome classes.
• Random number generator algorithm has been changed from RANROT to MWC.
  • Declaration of method void GaRandomGenerator::Generate(unsigned int& word1, unsigned int& word2) has been changed to int GaRandomGenerator::Generate().
  • Declaration of method void GaRandomGenerator::Initalization(unsigned int seed) has been changed to void GaRandomGenerator::Initalization(unsigned int seed1, unsigned int seed1).
  • enum GaRandomParams has been removed since it is no longer needed after algorithm change.
  • struct GaState has been added as a member of GaRandomGenerator class and it represents current state of random number generator. Its members _w and _z store 64-bit state.
  • The way of generating random numbers in specified interval has been changed to equalize probabilities for all numbers in the interval. The maximal value specified to the Generate method is now included in interval. This change affects: GaRandomInt, GaRandomBool, GaRandomFloat and GaRandomDouble.
• GaChromosomeDomainBlock now can stores multiple value sets. const GaValueSet<t>* GACALL GetValueSet(int pos) const</t>, void GACALL SetValueSet(GaValueSet<t>* domain, int pos)</t> and int GACALL GetValueSetCount() const method are added to the class. Declaration of method const T& GetClosestValue(const T& value) const has been changed to const T& GetClosestValue(const T& value, int pos) const.
• Multivalue chromosome represented by GaMultiValueChromosome class now uses separate value set for each value position. This change also affects GaMVArithmeticChromosome class.
• Coupling operations now can check whether the produced offspring chromosome already exists in the population and not insert it to result set if that is the case. The operation stores this setting to result set, so replacement operation can clear duplicates before they are inserted in population. To accomplish this, GetCheckForDuplicates and SetCheckForDuplicates methods have been added to GaCouplingParams class and SetClearDuplicates and GetClearDuplicates methods to GaCouplingResultSet class. This change also affects GaMulitpleCrossoverCouplingParams. Checking is implemented by CheckForDuplicates function. Production of offspring chromosomes for all built-in operations is now implemented in a single function: ProduceOffspring.