- 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
- Online documentation
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
- Portability, Compiling and Linking the Genetic Algorithm Library
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
if the first fitness value is lower than the second -
0
if these two values are equal -
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 returntrue
if the implementation of the scaling operation is based on the ranking of chromosomes. Otherwise, it should returnfalse
. -
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); |
Notifies the observer when the statistics of the algorithm has been changed. This event occurs at the end of each generation. |
void NewBestChromosome( const GaChromosome& newChromosome, const GaAlgorithm& algorithm); |
This event occurs when the algorithm finds new chromosomes that are better than the best chromosomes previously found. |
void EvolutionStateChanged( GaAlgorithmState newState, const GaAlgorithm& algorithm); |
The event notifies the observer when the user starts, stops, or pauses the evolution process or when the algorithm reaches the stop criteria. |
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:
SystemThread |
This type defines the system specific type for storing thread objects. |
ThreadID |
Variables/objects of this type are used for storing IDs of system threads. This type hides system specific types which are used for the purpose. |
ThreadFunctionPointer |
This type defines a pointer to a function that is used as a thread‘s entry point. |
ThreadFunctionReturn |
This type is used as a return value type for a function which is used as a thread‘s entry point. |
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:
SysSyncObject |
This type defines system-specific synchronization objects that is used
by the GaCriticalSection class. |
SysSemaphoreObject |
This type defines system-specific semaphore objects. |
SysEventObject |
This type defines system-specific event objects. |
Synchronization functions:
bool MakeSemaphore( SysSemaphoreObject& semaphore, int maxCount, int initialCount); |
This function is used to create an operating system object for a semaphore and to initialize it. |
bool DeleteSemaphore(
SysSemaphoreObject& semaphore);
|
This function is used to free the operating system semaphore object. |
bool LockSemaphore(
SysSemaphoreObject& semaphore);
|
This function is used to acquire access to a critical section protected by a semaphore. |
bool UnlockSemaphore( SysSemaphoreObject& semaphore, int count); |
This function is used to release access to a critical section protected by a semaphore. |
bool MakeEvent( SysEventObject& event, bool intialState); |
This function is used to create an operating system object for an event and to initialize it. |
bool DeleteEvent( SysEventObject& event); |
This function is used to free an operating system event object. |
bool WaitForEvent( SysEventObject& event); |
This function is used to block a calling thread until an event reaches the signaled state. When the calling thread is released, an event is restarted to the non-signaled state. |
bool SignalEvent( SysEventObject& event); |
This function is used to set an event to the signaled state. |
Synchronization macros:
ATOMIC_INC(VALUE) |
Atomically increments VALUE by one, and returns the new
value. |
ATOMIC_DEC(VALUE) |
Atomically decrements VALUE by one, and returns the new
value. |
SPINLOCK(LOCK) |
Protects a critical section with spinlock. LOCK must be a
variable of int type. To release a spinlock, the
LOCK variable should be set to 0. |
DEFINE_SYNC_CLASS |
This macro inserts members to a class which are needed to synchronize
access to an instance of the class. The LOCK_OBJECT and
LOCK_THIS_OBJECT macros are used to synchronize access to an
object. |
LOCK(LOCK_NAME) |
This macro is used to acquire access to a critical section protected
by the synchronization object (GaSectionLock or
GaCriticalSection ). |
UNLOCK(LOCK_NAME) |
This macro is used when a thread exits a critical section and releases
access to the synchronization object (GaSectionLock or
GaCriticalSection ). |
LOCK_OBJECT(LOCK_NAME,OBJECT) |
This macro acquires access to an object with a built-in synchronizer
and prevents concurrent access. It instantiates a
GaSectionLock object with the name LOCK_NAME ,
and acquires access to the object. When execution leaves the scope in
which LOCK_OBJECT is specified, the
GaSectionLock object is destroyed and access to the locked
object is released. Unlocking access to the object before leaving the
scope can be done by calling the UNLOCK(LOCK_NAME) macro. |
LOCK_THIS_OBJECT(LOCK_NAME) |
This macro acquires access to this and prevents concurrent access. It
declares and instantiates a GaSectionLock object with the
name LOCK_NAME and acquires access to this object. When
execution leaves the scope in which LOCK_OBJECT is specified,
the GaSectionLock object is destroyed and access to this
object is released. Unlocking access to the object before leaving the
scope can be done by calling the UNLOCK(LOCK_NAME) macro. |
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.
Data type | Interval | Class name | Global object |
int |
0-2147483647 | GaRandomInteger |
GaGlobalRandomIntegerGenerator |
float |
(0, 1) | GaRandomFloat |
GaGlobalRandomFloatGenerator |
double |
(0, 1) | GaRandomDouble |
GaGlobalRandomDoubleGenerator |
bool |
true or false
|
GaRandomBool |
GaGlobalRandomBoolGenerator |
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:
- create copy of supplied population object
- initialize provided population object
- select parents and produce offspring chromosomes
- copy the best chromosome from the current population [elitism]
- insert offspring chromosomes into new population
- check stop criteria [exit if reached]
- 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:
- initialize provided population object
- select parents and produce offspring chromosomes
- replace old chromosomes with offspring
- check stop criteria [exit if reached]
- switch population object and return to step 2.
Examples
The user must perform these steps to build a genetic algorithm with this library:
- Choose representation of the chromosomes
- Define fitness operation
- Choose crossover and mutation operations and fitness comparator
- Choose selection, coupling, replacement, and scaling operations
- 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:
- pointer to parameters of chromosomes
- pointer to genetic operation functors [crossover, mutation, fitness operation, and fitness comparator]
- pointer to value set which defines the domain of
x
andy
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:
- population size: 30
- resizable population: no [incremental algorithm is used, which does not require resizable population]
- population is sorted: yes
- scaled fitness is used for sorting: no
- tracking of the best chromosomes: 0 [population is already sorted]
- 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:
- selection operations:
GaSelectRouletteWheel
- number of selected chromosomes: 2
- coupling operation:
GaInverseCoupling
- offspring produced: 2
- replacement operation:
GaReplaceWorst
- chromosomes replaced: 2
- scaling operation: none
- sort comparator:
GaMaxFitnessComparator
[default] changed toGaMinFitnessComparator
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<char>*> (chromosome)->GetCode(); int score=0; for(int i=0;i<patternSize;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 );
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:
- mutation probability: 3%
- mutation size: 2
- improving only mutations: no
- crossover probability: 80%
- number of crossover points: 1 [ignored]
CCB:
TspCrossover
TspSwapMutation
TspFitnessOperation
TspMinFitnessComparator
- Value set is not defined
Population parameters:
- population size: 100
- resizable population: no [an incremental algorithm is used which does not require a resizable population]
- population is sorted: yes
- scaled fitness is used for sorting: no
- tracking of the best chromosomes: 0 [population is already sorted]
- tracking of the worst chromosomes: 0 [population is already sorted]
Configuration of the population:
-
GaSelectRandomBest
selection which selects 8 chromosomes -
GaSimpleCoupling
which produces 8 offspring chromosomes -
GaRandomReplaces
which replaces 8 chromosomes in each generation, with an elitism size of 10 chromosomes - 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:
Microsoft C++ | Intel C++ | GCC G++ | Borland C++ | Sun Studio C++ | |||||||||||||||||||
Windows |
12 |
12 |
6 |
||||||||||||||||||||
Linux |
34 |
34 |
|||||||||||||||||||||
Mac OS X |
34 |
34 |
|||||||||||||||||||||
*BSD |
345 |
||||||||||||||||||||||
Solaris |
5 |
8 |
|||||||||||||||||||||
|
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
- Adding GeneticAlgorithm.lib to Project Properties->Linker->Additional Dependencies.
- Setting the proper directories so that Visual Studio can find the
library and its headers. This can be done locally or globally.
- 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
- Adding GeneticLibrary.lib to:
- Globally by adding directories into the appropriate places (Include
files and Library files)
Tools->Options->Projects and Solutions->VC++ Directories
- Locally
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==
inGaChromosome
interface is nowbool
.operator !=
is also added toGaChromosome
interface. This change also affects:GaMultiValueChromosome
,GaSingleValueChromosome
andGaBinaryChromosome
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 toint GaRandomGenerator::Generate()
. - Declaration of method
void GaRandomGenerator::Initalization(unsigned int seed)
has been changed tovoid 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 ofGaRandomGenerator
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
andGaRandomDouble
.
- Declaration of method
-
GaChromosomeDomainBlock
now can stores multiple value sets.const GaValueSet* GACALL GetValueSet(int pos) const
,void GACALL SetValueSet(GaValueSet* domain, int pos)
andint GACALL GetValueSetCount() const
method are added to the class. Declaration of methodconst T& GetClosestValue(const T& value) const
has been changed toconst 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 affectsGaMVArithmeticChromosome
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
andSetCheckForDuplicates
methods have been added toGaCouplingParams
class andSetClearDuplicates
andGetClearDuplicates
methods toGaCouplingResultSet
class. This change also affectsGaMulitpleCrossoverCouplingParams
. Checking is implemented byCheckForDuplicates
function. Production of offspring chromosomes for all built-in operations is now implemented in a single function:ProduceOffspring
.