A quick tour of GA

This is my note for learning A quick tour of GA.

Genetic algorithms(GAs) are stochastic search algorithms inspired by the basic principles of biological evolution and natural selection. GAs simulate the evolution of living organisms, where the fittest individuals dominate over the weaker ones, by mimicking the biological mechanisms of evolution, such as selection, crossover and mutation.

The R Package GA provides a collection of general purpose functions for optimization using genetic algorithms. The package includes a flexible set of tools for implementing genetic algorithms search in both continuous and discrete case, whether constrained or not. Users can easily define their own objective function depending on the problem at hand. Several genetic operators are available and can be combined to explore the best setting for the current task. Furthermore, users can define new genetic operators and easily evaluate their performances. Local search using general-purpose optimisation algorithms can be applied stochastically to exploit interesting regions. GAs can be run sequentially or in parallel. using an explicit master-slave parallelisation (主从并行化) or a coarse-grain isolands approach（粗粒度孤岛方法）.

Function optimisation in two dimensions

The GA search process can be visualised by defining a monitoring function as follows:

Setting some members of the initial population

The suggestions argument to ga() function call can be used to provide a matrix of solutions to be inclued in the initial population.

As it can be seen, the first two solution considered are those provided, whereas the rest is filled randomly as usual. A full search can be obtained as follows:

Constrained optimisation

A GA solution can be obtained by defining a penalised fitness function:

A graph showing the the solution found is obtained as:

Hybrid GAs

Hybrid Genetic Algothrms (HGAs) incorporate efficient local search algorithms into GAs. In case of real-valued optimisation problems, the GA package provides a simple way to start local searchs from GA solutions after a certain number of iterations, so that, once a promising region is identified, the convergence to the local optimum can be speed up.

The use of HGAs is controlled by the optional argument optim = TRUE (by default is set to FALSE). Local searches are executed using the base R function optim(), which makes avaiable general-purpose optimisation methods, such as Nelder-Mead, quasi-Newton with and without box constraints, and conjugate-gradient algorithms. The local search method to be used and other parameters are controlled with the optional argument optimArgs, which must be a list with the following structure and defaults.

Parallel computing

Consider the following simple example where a pause statement is introduced to simulate an expensive fitness function.

Island evolution

GAs can be designed to evolve using an Island evolution approach. Here the population is partitioned in a set of sub-populations (islands) in which isolated GAs are executed on separated processor runs. Occasionally, some individuals from an island migrate to another island, thus allowing sub-populations to share genetic material.

This approach is implemented in the gaisl() function, which has the same input arguments as the ga() function, with the addition of the following argument:

1. numIslands: an integer value specifying the number of islands to use (by default is set to 4).
2. migrationRate: a value in the range (0, 1) which gives the proportion of individuals that undergo migration between islands in every exchange (by default equal to 0.10).
3. migrationInterval: an integer value specifying the number of interations at which exchange of individuals takes place (by default set at 10).

Parallel computing is used by default in the Island evolution approach. Hybridistion by local search is also availabel as discussed previously.

# R