[Previous] [Top] [Next]

2 The Matlab GA Toolbox

Whilst there exist many good public-domain genetic algorithm packages, such as Genesys and Genitor [16], none of these provide an environment that is immediately compatible with existing tools in the control domain. The Matlab Genetic Algorithm Toolbox [4] aims to make GAs accessible to the control engineer within the framework of an existing CACSD package. This allows the retention of existing modelling and simulation tools for building objective functions and allows the user to make direct comparisons between genetic methods and traditional procedures.

2.1 Data structures

Matlab essentially supports only one data type, a rectangular matrix of real or complex numeric elements. The main data structures in the GA Toolbox are chromosomes, phenotypes, objective function values and fitness values. The chromosome structure stores an entire population in a single matrix of size Nind x Lind, where Nind is the number of individuals and Lind is the length of the chromosome structure. Phenotypes are stored in a matrix of dimension Nind x Nvar, where Nvar is the number of decision variables. A Nind x Nobj matrix stores the objective function values, where Nobj is the number of objectives. Finally, the fitness values are stored in a vector of length Nind. In all of these data structures, each row corresponds to a particular individual.

2.2 Toolbox structure

The GA Toolbox uses Matlab matrix functions to build a set of versatile routines for implementing a wide range of genetic algorithm methods. In this section we outline the major procedures of the GA Toolbox.

2.2.1 Population initialisation

The GA Toolbox supports floating-point, binary and integer chromosome representations. Real-valued populations may be initialised using crtrp. Binary and integer populations may be initialised using the Toolbox function to create binary populations, crtbp. An additional function, crtbase, is provided that builds a vector describing the integer representation used. Conversion between binary and real-values is provided by the routine bs2rv that also supports the use of Gray codes and logarithmic scaling.

2.2.2 Fitness assignment

The fitness function transforms the raw objective function values into non-negative figures of merit for each individual. The Toolbox supports the linear-ranking algorithm of Baker [2] and a new non-linear ranking method [15], both in the routine ranking. The use of non-linear ranking permits higher selective pressures than the conventional ranking methods. In addition, the offsetting and scaling method of Goldberg [6] is also supported in the routine scaling.

2.2.3 Selection functions

These functions select a given number of individuals from the current population, according to their fitness, and return a column vector to their indices. Currently available routines are roulette wheel selection [3], rws, stochastic universal sampling [3], sus, truncation selection [12], seltrunc, and local selection [15], sellocal. A high-level entry function, select, is also provided as a convenient interface to the selection routines, particularly where multiple populations are used. In cases where a generation gap is required, i.e. where the entire population is not reproduced in each generation, reins or reinsloc can be used to effect uniform random or fitness-based reinsertion.

2.2.4 Crossover operators

The crossover routines recombine pairs of individuals with given probability to produce offspring. To support real-valued chromosome representations, discrete, intermediate and line recombination [12] are supplied in the routines recdis, recint and reclin, respectively. The routine recmut performs line recombination with mutation features [14].

Single-point, double-point and shuffle crossover are implemented in the routines xovsp, xovdp and xovsh, respectively. Reduced surrogate crossover is supported with both single-, xovsprs, and double-point, xovdprs, crossover and with shuffle, xovshrs. A general multi-point crossover routine, xovmp, that supports uniform crossover is also provided. A high-level entry function to all the crossover operators supporting multiple subpopulations is provided by the function recombin.

2.2.5 Mutation operators

Real-value mutation is available using the breeder GA mutation function [12], mutbga. Binary and integer mutation are performed by the routine mut. Again, a high-level entry function, mutate, to the mutation operators is provided.

2.2.6 Multiple subpopulation support

The GA Toolbox provides support for multiple subpopulations through the use of high-level genetic operator functions and a function for exchanging individuals amongst subpopulations, migrate. A single population is divided into a number of subpopulations by modifying the data structures used by the Toolbox routines such that subpopulations are stored in contiguous blocks within each data element. The high-level routines, such as select and reins, operate independently on each subpopulation contained in a data structure allowing each subpopulation to evolve in isolation from the others. Based on the Island or Migration model, migrate allows individuals to be transferred between subpopulations. Uni- and bi-directional ring topologies as well as a fully interconnected network are available as well as fitness-based and uniform selection and reinsertion strategies.

[Previous] [Top] [Next]