International Journal of Electrical Engineering Education: Teaching genetic algorithm using MATLAB

ABSTRACT In this paper, an attractive approach for teaching genetic algorithm (GA) is presented. This approach is based primarily on using MATLAB in implementing the genetic operators: crossover, mutation and selection. A detailed illustrative example is presented to demonstrate that GA is capable of finding global or near-global optimum solutions of multi-modal functions. An application of GA in designing a robust controller for uncertain control systems is also given to show its potential in designing engineering intelligent systems.

KEYWORDS control systems; genetic algorithm; MATLAB

1 INTRODUCTION

Genetic Algorithm (GA) is a major topic in a neural and evolutionary computing under-graduate (advanced level)/postgraduate course. The course plays an important role in designing intelligent control systems, which is now very attractive and stimulating to students in Electrical Engineering Departments. The usual way to teach genetic algorithm is by the use of PASCAL, C and C++ languages. In this paper, we present an attractive and easy way for teaching such a topic using MATLAB1. It has been found that this approach is quite acceptable to the students. Not only can they access the software package conveniently, but also MATLAB provides many toolboxes to support an interactive environment for modelling and simulating a wide variety of dynamic systems including linear, nonlinear discrete-time, continuous-time and hybrid systems. Together with SIMULINK, it also provides a graphical user interface (GUI) for building models as block diagrams, using click-and-drag mouse operations.

The rest of the paper is organised as follows. Section 2 introduces a simple version of genetic algorithm, canonical genetic algorithm (CGA), which was originally developed by Holland2. Section 3 describes the implementation details of the genetic operators: crossover, mutation and selection. Section 4 demonstrates the performance of the CGA with a multi-modal function. Section 5 provides an application of the developed genetic operators in designing a robust controller for uncertain plants, and section 6 gives a conclusion.

2 CANONICAL GENETIC ALGORITHM

Genetic algorithms are adaptive algorithms for finding the global optimum solution for an optimization problem. The canonical genetic algorithm developed by Holland is characterised by binary representation of individual solutions, simple problem-independent crossover and mutation operators, and a proportional selection rule. To understand these concepts, consider the standard procedure of the CGA outlined in Fig. 1. The population members are strings or chromosomes, which as originally conceived are binary representations of solution vectors. CGA undertakes to select subsets (usually pairs) of solutions from a population, called parents, to combine them to produce new solutions called children (or offspring). Rules of combination to yield children are based on the genetic notion of crossover, which consists of interchanging solution values of particular variables, together with occasional operations such as random value changes (called mutations). Children produced by the mating of parents, and that pass a survivability test, are then available to be chosen as parents of the next generation. The choice of parents to be matched in each generation is based on a biased random sampling scheme, which in some (nonstandard) cases is carried out in parallel over separate subpopulations whose best members are periodically exchanged or shared. The key parts in Fig. are described in detail as follows.

2.1 Initialisation

In the initialisation, the first thing to do is to decide the coding structure. Coding for a solution, termed a chromosome in GA literature, is usually described as a string of symbols from 0,1. These components of the chromosome are then labeled as genes. The number of bits that must be used to describe the parameters is problem dependent. Let each solution in the population of m such solutions xi, i = 1, 2, ..., m, be a string of symbols 0, 1 of length 1. Typically, the initial population of m solutions is selected completely at random, with each bit of each solution having a 50% chance of taking the value 0.

2.2 Selection

This process is also called roulette wheel parent selection and may be viewed as a roulette wheel where each member of the population is represented by a slice that is directly proportional to the member's fitness. A selection step is then a spin of the wheel, which in the long run tends to eliminate the least fit population members.

2.3 Crossover

Crossover is an important random operator in CGA and the function of the crossover operator is to generate new or 'child' chromosomes from two 'parent' chromosomes by combining the information extracted from the parents. The method of crossover used in CGA is the one-point crossover as shown in Fig. 2(a). By this method, for a chromosome of a length 1, a random number c between 1 and I is first generated. The first child chromosome is formed by appending the last I- c elements of the first parent chromosome to the first c elements of the second parent chromosome. The second child chromosome is formed by appending the last I - c elements of the second parent chromosome to the first c elements of the first parent chromosome. Typically, the probability for crossover ranges from 0.6 to 0.95.

2.4 Mutation

Mutation is another important component in CGA, though it is usually conceived as a background operator. It operates independently on each individual by probabilistically perturbing each bit string. A usual way to mutate used in CGA is to generate a random number v between 1 and I and then make a random change in the vth element of the string with probability P^sub m^ Epsilon (0, 1), which is shown in Fig. 2(b). Typically, the probability for bit mutation ranges from 0.001 to 0.01.

Holland's early designs for CGA were simple, but were reported to be effective in solving a number of problems considered to be difficult at the time. The field of genetic algorithms has since evolved, chiefly as a result of innovations in the 1980s, to incorporate more elaborate designs aimed at solving problems in a wide range of practical settings. Characteristically, GAs are distinguished in the following features: (1) they work with a coding of the parameter sets instead of the parameters themselves; (2) they search with a population of points, not a single point; (3) they use the objective function information directly, rather than the derivatives or other auxiliary knowledge, to find maxima; (4) they process information using probabilistic transition rules, rather than deterministic rules. These features make GAs robust to computation, readily implemented with parallel processing and powerful for global optimisation.

3 IMPLEMENTATION OF CGA USING MATLAB

This section describes the procedure of implementing the canonical genetic algorithm using MATLAB. For simplicity, we assume that the task is to achieve the maximum of a one-variable multi-modal function, f(x) > 0, for x belonging to the domain [a, b]. The implementation steps are as follows.

3.1 Initialisation

For CGA, a binary representation is needed to describe each individual in the population of interest. Each individual is made up of a sequence of binary bits (0 and 1). Let stringlength and popsize denote the length of the binary sequence and the number of individuals involved in the population. Each individual uses a string codification of the form shown in Fig. 3. Using MATLAB, the whole data structure of the population is implemented by a matrix of size popsize x (stringlength + 2):

In the above routine, we first generate the binary bits randomly, and then replace the (stringlength + 1)-th and (stringlength + 2)-th columns with real x values and objective function values, where fun is the objective function, usually denoted by a .m file.

3.2 Crossover

At the top of the crossover routine, we determine whether we are gong to perform crossover on the current pair of parent chromosomes. Specifically, we generate a random number and compare it with the probability parameter pc. If the random number is less than pc, a crossover operation is performed; otherwise, no crossover is performed and the parent individuals are returned. If a crossover operation is called for, a crossing point cpoint is selected between 1 and stringlength. The crossing point cpoint is selected in the function round,

which returns a pseudorandom integer between specified lower and upper limits (between 1 and stringlength -1). Finally, the partial exchange of crossover is carried out and the real values and fitness of the new individuals child 1, child 2, are computed.

3.3 Mutation

3.4 Selection

3.5 Accessing on-line information

Continued from page 1.

We have shown how the three main pieces of CGA may be easily coded and easily understood. After implementing the key genetic operators, implementation of the main program is straightforward. At the moment, the World Wide Web and the Internet provide some quality MATLAB source codes for different kinds of genetic algorithms. Chris Houck, Jeff Joines, and Mike Kay at North Carolina State University have developed two versions of the genetic algorithm for function optimization using both MATLAB 4 and MATLAB 5. The WWW site is: http://www.ie.ncsu.edu/mirage. Andrew F. Potvin has also implemented a simple version of genetic algorithm which is available on the WWW site: http://unix.hensa.ac.uk/ftp/mirrors/matlab/contrib/v4/optim/genetic/.

It should be pointed out that although the above Toolboxes are very useful in solving many engineering problems, they are sometimes too comprehensive for the students. In many situations, the students need to modify the genetic operators to meet their own problem-dependent requirements. However, they found it very difficult to change some parts of the above GA Toolboxes, because the whole package is heavily interconnected. With the source codes provided in this section, the students found it quite easy to modify the genetic operators and invent some new genetic operators. This is helpful in promoting the students' creativity, which is necessary and important in the new teaching process.

4 AN ILLUSTRATIVE EXAMPLE

for x belonging to the domain [0,1]. The characteristic of the function is plotted in Fig. 4(a). As shown in the figure, the function has three maxima, with a global maximum achieved at x = 0.1527.

Several trials have been performed changing the fundamental parameter values. Below, a relevant example, with popsize = 30, stringlength = 20, pc = 0.95 and pm = 0.05 is reported. Fig. 4(a) shows the initial population for the optimisation of a one-variable optimisation: the * represent the individuals of the population, randomly generated in the function domain. Fig. 4(b) shows the population after 50 generations of the CGA, and Fig. 4(c) gives the population after 100 generations of the CGA.

As can be observed from Fig. 4(a), at the first step, the population (represented by * in the figures) is randomly distributed in the whole function domain. During the evolution of the algorithm, Fig. 4(b), the individuals of the population tend to concentrate at the peaks of the function and at convergence, Fig. 4(c), most of the individuals are clustered near the desired maximum value of the function.

5 AN APPLICATION EXAMPLE

In this section, we provide an application example of the developed GA in designing robust controller for uncertain control systems. Robust control under parametric uncertainty is an important research area with many practical applications. When the system has a general nonlinear uncertainty structure, the usual approach is to overbound it by an interval dynamical system. The robust controller design can be transformed into solving an eigenvalue optimisation problem, which involves optimising the maximum real part of eigenvalues of the characteristic polynomial for the uncertain plant. This kind of problem is a typical non-smooth and nonconvex optimisation problem, and may have several local optima. We demonstrate that GA is capable of solving this kind of problem. A practical flywheel-shaft-flywheel system, including uncertainty in the length of the shaft and shaft damping, is employed to carry out the numerical simulation.

5.1 Uncertain control systems

The robust controller design can be considered as determining the parameter value p Epsilon P so that the feedback control system is stable for all q Epsilon Q. However, the presence of the k-dimensional uncertainty vector, q, complicates the analysis of the uncertain transfer functions such as (4) and equations such as (6). Thorough robust analysis requires that the behaviour of every point in the uncertainty space, i.e. all qEpsilon Q, must be checked. As this is impossible, a common technique involves creating a grid of points for each qi Epsilon [q^sub i^^sup -^, q^sub i^^sup +^ ], i = 1, ..., k, and analysing behaviour over this k-dimensional grid. This approach is computationally intensive and inexact - one can never be certain that a finer grid might not change a robust stability prediction. In the next subsection, we discuss solving this problem using GA optimisation approach.

5.2 Robust controller design via GA

6 CONCLUSION

In this paper, an attractive approach for teaching genetic algorithm has been presented. This approach is based primarily on using MATLAB in implementing the genetic operators: crossover, mutation, and selection. An advantage of using such an approach is that the student becomes familiar with some advanced features of MATLAB, and furthermore, with the availability of other MATLAB Toolboxes such as The Control Systems Toolbox, Neural Network Toolbox and Fuzzy Logic Toolbox, it is possible for the student to develop genetic algorithm-based approaches to designing intelligent systems, which could lead to his/her final year or MSc project.

REFERENCES

[1] MATLAB 5, The Math Works Inc., Natick, MA (1997)

[2] Holland, J., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann

Arbor (1975)

[3] Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, AddisonWesley (1989)

[4] Borie, J. A., Modern Control Systems, Prentice-Hall International (1986) [5] Sebald, A. V. and Schlenzig, J., `Minimax design of neural net controller for highly uncertain plants', IEEE Trans. Neural Networks, 5, pp. 73-82 (1994)

ABSTRACTS - FRENCH, GERMAN, SPANISH

Enseignement d'algorithme gen*tique par MATLAB

Dans cet article une approche attractive pour enseigner I'algorithme genetique (GA) est pr6sent6e. Cette approche est basee sur l'utilisation de MATLAB pour implementer les operateurs genetiques: mutation, selection et croisement. Un exemple illustratif detaille est presente pour demontrer que GA est capable de trouver un optimum global ou quasi-global pour des fonctions multi-modales. Une application de GA dans la conception d'un controleur robuste pour des systemes a controle incertain est egalement donnee pour montrer son potentiel dans la conception de systemes intelligents en ingenierie.

Genetische Algorithmen mit MATLAB lehren

In diesem Bericht wird ein attraktives Vorgehen zum Lehren genetischer Algorithmen (GA) vorgestellt. Dieses Vorgehen beruht in erster Linie auf der Verwendung von MATLAB in der Durchfuhrung der genetischen Operatoren: Uberkreuzung, Mutation und Selektion. Ein ausfuhrliches illustratives Beispiel wird vorgestellt, um zu beweisen, daB GA fahig ist, globale oder fast globale optimale Losungen multimodaler Funktionen zu finden. Eine Anwendung von GA bei der Auslegung eines robusten Reglers fur ungewisse Steuersysteme wird ebenfalls angegeben, um dessen Potential in der Entwicklungstechnik intelligenter Systeme zu zeigen.

Ensenanza de algoritmos geneticos empleando MATLAB

En este articulo se presenta una aproximacion atractiva para la ensenanza de algoritmos gen6ticos (AG). Esta aproximacion se basa, en primer lugar, en emplear MATLAB para la implementacion de los operadores geneticos: cruzamiento, mutacion y seleccion. Se presenta un ejemplo ilustrativo detallado para demostrar que el AG es capaz de buscar soluciones globales o casi globales optimas de funciones multimodales. Se muestra asi mismo una aplicacion de AG en el diseno de controladores robustos para sistemas de control con incertidumbres que muestra su potencial en el diseno de sistemas de ingenieria inteligentes.

Y J. C AO1 and Q, H. WU2

1Intelligent Computer Systems Centre, University of the West of England, Bristol, UK

2 Department of Electrical Engineering and Electronics, University of Liverpool, Liverpool, UK