13,045,564 members (69,102 online)
Add your own
alternative version

#### Stats

328.7K views
31.1K downloads
542 bookmarked
Posted 19 May 2008

# Genetic Algorithm Library

, 7 Apr 2012
 Rate this:
Please Sign up or sign in to vote.
A framework for genetic algorithms

## 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.

Diagram - Chromosome representations [for maximization of a single-parameter function]

Diagram - Chromosome representations [Traveling Salesman 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.

Diagram - Crossover operation examples

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.

Diagram - Mutation operation examples [swap mutation is performed over the first, and over the second, an invert mutation is performed]

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.

Diagram - Scaling fitness value [shows the selection probability of chromosomes]

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.

Diagram - Coupling operation flowchart

Diagram - Selection operation without coupling operation flowchart

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...

Diagram - Flowchart of a genetic algorithm [overlapping population coupling operation]

Diagram - Flowchart of a genetic algorithm [overlapping population without coupling operation]

Diagram - Flowchart of a genetic algorithm [non-overlapping population with coupling operation]

## 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:

Diagram - 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.

Diagram - Namespaces

### Chromosomes

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

Diagram - `GaChromosome` class

`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.

Diagram - `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.

Diagram - `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.

Diagram - `GaDefaultChromosome` and `GaChromosomeParamsBlock` classes

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].

Diagram - `GaDynamicOperationChromosome` class and interfaces for genetic operations

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

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

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

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

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

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

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

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

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

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

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

The last operation is the fitness comparator. The interface for fitness comparators are defined by the `GaFitnessComparator` class. The user defined classes should override `operator()`:

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

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

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

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

Diagram - `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.

Diagram - `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.

Diagram - Chromosomes in the population

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.

Diagram - `GaStatistics` and support classes

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

Diagram - Management of a population's configuration

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.

Diagram - `GaOperationParametersPair` class

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.

Diagram - Selection operation interface

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.

Diagram - Coupling operation interface

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.

Diagram - Replacement operation interface

An interface for scaling operations is defined by the `GaScalingOperation` class. User defined classes should override the `operator()`, `IsRankingBase`, and `NeedRescaling` methods:

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

virtual bool IsRankingBased() const;

virtual bool NeedRescaling(
const GaPopulation& population,
const GaScalingParams& parameters) const;```
• `operator()` takes a reference to the population's object and a reference to the scaling parameters.
• `IsRankingBased` should return `true` if the implementation of the scaling operation is based on the ranking of chromosomes. Otherwise, it should return `false`.
• `GaScalingParams` is the base class for the parameters of the scaling operations.

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

Diagram - Scaling operation interface

### 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.

Diagram - `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.

Diagram - Algorithm observing

`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.

Diagram - `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.

Diagram - Algorithm's states

`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.

Diagram - `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:

Diagram - Multithreaded algorithm workflow

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.

Diagram - `GaThread` class

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
}```

Diagram - `GaCriticalSection` and `GaSectionLock` classes

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.

Diagram - `GaCatalogue` class

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`

Diagram - Random number generators

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.

Diagram - `GaMutableCode` interface

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

Diagram - `GaSwapableCode` interface

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.

Diagram - `GaSizableCode` interface

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.

Diagram - `GaMultiValueCode` interface

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.

Diagram - `GaCodeValuesBuffer` class

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.

Diagram - `GaArithmeticalCode` interface

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.

Diagram - `GaCodeValue` interface

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.

Diagram - `GaDomainChromosome` and `GaChromosomeDomainBlock` classes

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

Diagram - `GaValueSet` class

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.

Diagram - `GaSingleValueSet` class

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`.

Diagram - `GaMultiValueSet` class

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.

Diagram - `GaIntervalValueSet` class

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.

Diagram - `GaUnboundValueSet` class

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

Diagram - `GaCombinedValueSet` class

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.

Diagram - `GaSingleValueChromosome` class

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`.

Diagram - `GaMultiValueChromosome` class

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.

Diagram - `GaBinaryChromosome` class

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

### Built-in Fitness Comparators

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

Diagram - Built-in fitness comparators

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.

Diagram - Built-in crossover operations

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.

Diagram - Results of `GaMutiValueCrossover` operation

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.

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

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

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

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

### Built-in Mutation Operations

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

Diagram - Built-in mutation operations

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].

Diagram - Results of `GaSwapMutation` operation

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.

Diagram - Results of `GaInvertMutation` operation

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.

Diagram - Results of `GaFlipMutation` operation

### Built-in Selection Operations

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

Diagram - `GaSelectBest` and `GaSelectWorst` selection operations

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.

`GaSelectRouletteWheel` and `GaSelectTournament` operations

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.

Diagram - `GaSelectRandom` and `GaSelectRandomBest` operations

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.

Diagram - Built-in coupling operations [1]

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.

Diagram - `GaSimpleCoupling` operation

Diagram - Built-in coupling operations [2]

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.

Diagram - `GaCrossCoupling` operation

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.

Diagram - `GaInverseCoupling` operation

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.

Diagram - `GaRandomCoupling` operation

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

Diagram - `GaBestAlwaysCoupling` operation

When two parents are chosen, these operations produce 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.

Diagram - `GaReplaceWorst` and `GaReplacBest` operations

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.

Diagram - `GaReplaceParents` and `GaReplaceRandom` operations

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.

Diagram - `GaWindowScaling` and `GaNormalizationScaling` operations

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.

Diagram - `GaLinearScaling` and `GaExponentialScaling` operations

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.

Diagram - `GaGenerationCriteria` and `GaGenerationCriteriaParams` classes

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

Diagram - `GaFitnessCriteria` and `GaFitnessCriteriaParams` classes

`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.

Diagram - `GaFitnessProgressCriteria` and `GaFitnessProgressCriteriaParams` classes

`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.

Diagram - Built-in genetic algorithms

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

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

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

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

## Examples

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

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

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

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

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

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

```class fFitness : public GaFitnessOperation
{
public:

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

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

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

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

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

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

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

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

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

The CCB should be:

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

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

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

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

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

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

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

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

Everything is now ready to create the population object:

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

GaPopulation population( &prototype, &populationConfig );```

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

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

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

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

```GaGenerationCriteriaParams criteriaParams(100000);

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

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

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

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

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

To register the observer:

```fObserver observer;
algorithm.SubscribeObserver(&observer);```

And to start the algorithm:

`algorithm.StartSolving(false);`

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

### Example 2: Pattern Matching

Screenshot - Pattern Test application

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

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

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

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

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

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

```class pFitness : public GaFitnessOperation
{
public:

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

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

return (float)score/patternSize*100;
}

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

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

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

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

Prototype chromosome:

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

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

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

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

GaPopulation population(&prototype, &populationConfig);```

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

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

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

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

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

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

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

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

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

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

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

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

```pObserver observer;
algorithm.SubscribeObserver( &observer );```

The starting of the evolution:

`algorithm.StartSolving(false);`

### Example 3: Traveling Salesperson Problem

Screenshot - TSP application

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

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

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

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

virtual GaChromosomePtr GACALL MakeNewFromPrototype() const;

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

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

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

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

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

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

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

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

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

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

Parameters of chromosomes:

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

CCB:

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

Population parameters:

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

Configuration of the population:

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

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

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

### Example 4: Class Schedule

Screenshot - Class Schedule application

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

 - Compiler is supported. - Compiler is not supported. 1 - Available as Visual Studio project. 2 - Can be compiled as static or dynamic library (DLL). 3 - Makefile available. 4 - Can only be compiled as static library. 5 - `gmake` command is used for building the library. 6 - compiler must be configured to use the STLport library. 7 - `dmake` command is used for building the library.

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

### Windows Platform

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

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

• Method 1

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

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

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

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

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

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

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

The procedures are same for both versions of the project.

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

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

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

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

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

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

where %compiler% is:

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

%platform%s are the following:

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

and the configuration is one of these:

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

Makefiles are available in the /makefiles directory.

`make -f icc_linux_debug all`

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

`gmake -f gcc_bsd_release all`

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

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

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

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

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

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

### Portability

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

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

## Changes

### Version 1.4

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

## License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)

## About the Author

 Software Developer Serbia
No Biography provided

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 First PrevNext
 GitHub project moved? roscler10-Nov-15 4:43 roscler 10-Nov-15 4:43
 .NET port for GA ssttvv00217-Dec-14 6:30 ssttvv002 17-Dec-14 6:30
 my vote of 5 ghiltong13-Nov-14 9:48 ghiltong 13-Nov-14 9:48
 Cant compile the sample Seyyed Hossein Hasan Pour19-Oct-14 5:42 Seyyed Hossein Hasan Pour 19-Oct-14 5:42
 SALE ERROR Lourdes Aurora NiñoHuertas9-Oct-13 20:52 Lourdes Aurora NiñoHuertas 9-Oct-13 20:52
 SimpleGA fails on "GaScaledChromosome::CompareFitnesses" IAmBruce23-May-13 13:26 IAmBruce 23-May-13 13:26
 Re: SimpleGA fails on "GaScaledChromosome::CompareFitnesses" Mladen Janković24-May-13 12:28 Mladen Janković 24-May-13 12:28
 Re: SimpleGA fails on "GaScaledChromosome::CompareFitnesses" IAmBruce24-May-13 12:55 IAmBruce 24-May-13 12:55
 Re: SimpleGA fails on "GaScaledChromosome::CompareFitnesses" Mladen Janković24-May-13 13:26 Mladen Janković 24-May-13 13:26
 Re: SimpleGA fails on "GaScaledChromosome::CompareFitnesses" IAmBruce24-May-13 15:43 IAmBruce 24-May-13 15:43
 Re: SimpleGA fails on "GaScaledChromosome::CompareFitnesses" Mladen Janković24-May-13 18:18 Mladen Janković 24-May-13 18:18
 Re: SimpleGA fails on "GaScaledChromosome::CompareFitnesses" IAmBruce25-May-13 0:58 IAmBruce 25-May-13 0:58
 Re: SimpleGA fails on "GaScaledChromosome::CompareFitnesses" Mladen Janković25-May-13 12:09 Mladen Janković 25-May-13 12:09
 Re: SimpleGA fails on "GaScaledChromosome::CompareFitnesses" IAmBruce25-May-13 12:18 IAmBruce 25-May-13 12:18
 Re: SimpleGA fails on "GaScaledChromosome::CompareFitnesses" Mladen Janković26-May-13 1:50 Mladen Janković 26-May-13 1:50
 Re: SimpleGA fails on "GaScaledChromosome::CompareFitnesses" IAmBruce26-May-13 15:56 IAmBruce 26-May-13 15:56
 How can I test ?? i SoRa29-Apr-13 8:57 i SoRa 29-Apr-13 8:57
 My vote of 5 Xiaoming Tu22-Mar-13 6:34 Xiaoming Tu 22-Mar-13 6:34
 My vote of 5 Carlos Renato4-Feb-13 1:48 Carlos Renato 4-Feb-13 1:48
 My vote of 5 Peter Hawke2-Feb-13 18:31 Peter Hawke 2-Feb-13 18:31
 Approach to implement a GA library Member 977826224-Jan-13 7:55 Member 9778262 24-Jan-13 7:55
 My vote of 5 Phat (Phillip) H. VU3-Jan-13 23:51 Phat (Phillip) H. VU 3-Jan-13 23:51
 My vote of 5 punittiwan16-Nov-12 20:05 punittiwan 16-Nov-12 20:05
 How to use Multiple variable?(with different range) Member 856970026-Sep-12 14:41 Member 8569700 26-Sep-12 14:41
 Re: How to use Multiple variable?(with different range) Mladen Janković28-Sep-12 8:07 Mladen Janković 28-Sep-12 8:07
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Jul-17 13:43 Refresh 1234 Next »

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.170713.1 | Last Updated 7 Apr 2012
Article Copyright 2008 by Mladen Janković
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid