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