8 External Layers

Our system is prepared for the implementation of different approaches to the problem of the genetic algorithm parallelization (parallelization methods). All kernel processes consist of certain layers that provide various services. Each layer is responsible for some part of process functionality. Our aim was to prepare process class hierarchy to provide basic functions and services that we expect to be useful for the implementation of different parallelisation methods. We suggest not to change these layers. We expect that the implementation of some new method will be realised as an implementation some top-level layer. We refer this layer as the external layer.

Layers from the process architecture up to the generic GA layers are able to initialize all kernel processes, to compute local genetic algorithms, to stop the computation after the termination condition has been fulfiled and to collect the results of computation. These layers also implement the universal data and control interfaces of the kernel.

The only technique that is not implemented in these layers is the parallelisation method i.e method of cooperation between the local genetic algorithms, running parallely in child processes. We assume the external layer implements such a method. It can either use services of the lower-level layers or implement its own mechanisms (in an overridden virtual method). It is also possible to override any supportive object in this level.

For list of steps necessary for implementation of an external layer see section How To Implement External Layer.

8.1 Diffusion External Layer

The diffusion external layer (classes TDiffusionGGA and TDiffusionLGA) is an example of implementation of the parallelisation method in an external layer. For the description of this method see section Parallelisation in System Overview .


The new feature, that adds diffusion external layer to the process hierarchy, is the internal structure of subpopulation. We refer this structure as the grid of places. All genetic operators are performed locally according to this structure i.e. a part of the grid is chosen before the operator is performed and it can affect only genes from the chosen part. This layer also maintains a structure among the child processes. The cooperation between two child processes, that are direct neighbours in this structure, is performed this way: each process maintains a certain number of shadow copies of genes that are members of subpopulation of the neighbour process. Only copies of genes that are near the subpopulation (according to the grid structure) are maintained. Whenever the original gene is changed by a genetic operator, a short message containing the description of this change is sent to the processes that maintain a copy of this gene. In this way the shadow copies are refreshed. This is the mechanism of the process cooperation: results achieved by a child process can affect the computation of another child process.

8.1.2Grid Structure

The grid structure of subpopulation is implemented in the class that represents a gene i.e. each gene object contains information about its direct neighbours in the grid. In fact, each gene object knows positions of all its neighbours in the grid. This information is implemented in class TGenEx. It is a successor of the class TGen that represents a standard gene. These extended genes are maintained by a special population implemented in the class TSubPop. This class is a successor of the standard population class TPopulation. Class TSubPop is an abstract class that defines the basic functionality of a structured population. E.g it defines abstract method SetTopology() that should establish connections between genes. The abstract methods of this class are then overriden in successor classes, that implement a certain type of the grid structure e.g. class TSubPop4 implements a grid of four neighbours, class TSubPop2 implements a grid of two neighbours. The key method of these classes is method Neighbourhood() that returns a neighbourhood of the given point in the grid up to the specified distance.

8.1.3 Initialization

The diffusion external layer implements a special initialisation procedure: the structure is established among the child processes and sets of genes are exchanged between the child processes to create the shadow copies. See section Kernel Initialisation. The first mechanism is provided by a special message (tag MT_INIT, special tag MS_NEIGHBOURS) sent by the parent process to each child process. These messages contain the PIDs of the direct neighbours of the given process. The second mechanism is provided by the message (tag MT_INIT, special tag MS_BORDERLAND), which contains the serialized borderland genes. These genes are connected as shadow copies to the subpopulation grid structure.

8.1.4 Computation

The standard genetic algorithm cannot be performed in the case of diffusion method, because it does nor respect the subpopulation grid structure. The diffusion layer overrides method TGACover::GABody(), where the main loop of genetic algorithm is implemented. Actually the used mechanism is:

  1. A part of the grid is selected as a neighbourhood of randomly chosen point in the grid (referred as the finger). This is provided by special GAtool selector (class TFinger). The radius of the neighbourhood is specified by the kernel parameter Dmax.
  2. The standard genetic algorithm loop is performed (method TGACover::GABody() is called) with the genes selected in the first step.
  3. The result of the main loop is put back to the grid structure instead of some old genes, that must be put away. This is performed by special GAtool selector TLocalWghtRndmGrid. This selector selects genes from the neighbourhood selected in the first step. The selected genes are put away and the new genes are inserted at their position. This selector selects the genes, to be put away, by an inversive roulette wheel i.e. a low fitness value means high probability of the selection. There are implemented also other special operators (TWghtRndmGrid,TRndmGrid,TLocalRndmGrid) that does not fully fit the diffusion method philosophy, but are also provided for usage (kernel parameters LocalGridOp and RuletteGridOp).


The diffusion external layer sends messages on the priority PRIORITY_OTHER (see Messages ), reserved for external layers. The only message it sends during the computation has tag MT_DIFFUSION and special tag MS_BCHANGE. This message contains the serialized gene that was changed during the computation of another child process (a direct neighbour). This message is sent only to processes which maintain the shadow copy of the changed gene. Whenever the message is received, the proper shadow copy is refreshed. These messages can be buffered to reduce the network load.

Programmer's Guide Project Antares