G E N E T I C A L G O R I T H M S IN S Y S T E M IDENTIFICATION A N D CONTROL By Kristinn Kristinsson B. Sc. Electrical Engineering University of Iceland, 1986 A THESIS SUBMITTED INPARTIAL THE REQUIREMENTS MASTER FULFILLMENT OF FOR THE DEGREE O F O F APPLIED SCIENCE in THE FACULTY O FGRADUATE ELECTRICAL STUDIES ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY O F BRITISH COLUMBIA August 1989 © Kristinn Kristinsson, 1989 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Electrical Engineering The University of British Columbia 2075 Wesbrook Place Vancouver, Canada V6T. 1W5 Date: Abstract Current online identification techniques are recursive and involve local search techniques. In this thesis, we show how genetic algorithms, a parallel, global search technique emulating natural genetic operators can be used to estimate the poles and zeros of a dynamical system. We also design an adaptive controller based on the estimates. The algorithms are shown to be useful for continuous time parameter identifications and to be able to identify directly physical parameters of a system. Simulations and an experiment show the technique to be satisfactory and to provide unbiased estimates in presence of colored noise. ii Table of Contents Abstract ii List of Tables vi List of Figures vii Acknowledgement 1 2 xi Introduction 1 1.1 General introduction 1 1.2 "Standard" identification methods 1 1.3 Motivation for this work 2 1.4 Outline of this thesis 3 Genetic Algorithms 4 2.1 History of Genetic Algorithms 4 2.2 The algorithm 4 2.3 Coding 2.4 Reproduction 7 2.4.1 9 '. Ranking 7 2.5 Crossover 10 2.6 Mutation 11 2.7 Mathematical Foundations 11 2.8 Example 13 iii 2.9 3 14 System Identification 19 3.1 Background 19 3.2 Discrete time identification 21 3.2.1 Parameter identification 25 3.2.2 Pole-zero identification 25 3.2.3 Results 27 3.3 3.4 3.5 3.6 4 Summary Recursive Least Squares estimation 31 3.3.1 32 Results Continuous time identification 38 3.4.1 Results 39 Friction compensation 41 3.5.1 43 Results Summary 44 Controller design 46 4.1 Controller 46 4.2 Parameter based design 48 4.3 Pole-zero based design 50 4.3.1 Multiple poles and zeros 53 4.3.2 Complex poles and zeros 53 4.3.3 Implementation 54 4.4 Results 54 4.4.1 Minimum phase plant 56 4.4.2 Nonminimum phase plant 64 4.4.3 Unrnodeled dynamics 65 iv 4.5 5 6 4.4.4 Persistently exciting signal 73 4.4.5 Recursive Least Squares 76 Summary 79 Experiment 82 5.1 Water level in a tank 82 5.2 Simulation results 83 Conclusions 87 Bibliography 89 A Genetic algorithms procedures 92 v List of Tables 2.1 Fitness dependent reproduction 8 2.2 Reproduction 15 2.3 Crossover and mutation 15 3.4 Search space for a stable minimum phase system 28 3.5 Search space for continuous time parameters 39 4.6 Search space for nonminimum phase 65 4.7 Search space for unmodeled dynamics 68 vi List of Figures 2.1 Genetic Algorithm 6 2.2 Ranking 10 2.3 Function with 11 local maxima 14 2.4 G A generations 16 2.4 G A generations (continued) 17 3.5 Window size = 5 22 3.6 Window size = 10 22 3.7 Window size = 20 23 3.8 Window size = 30 23 3.9 Number of trials = 1 24 3.10 Number of trials = 2 24 3.11 Number of trials = 3 24 3.12 Number of trials = 30 24 3.13 Parameters 26 3.14 Poles and zeros in the complex plane 26 3.15 Reparameterized complex plane 26 3.16 P R B S input and output of a system without noise 29 3.17 Pole-Zero estimate of a system without noise 29 3.18 Estimation of gain and delay of a system without noise 30 3.19 Pole zero locations 30 3.20 P R B S input and output with noise 33 vii 3.21 Parameter identification using R L S 33 3.22 Parameters locations 34 3.23 G A , pole zero identification 34 3.24 G A , parameters identification calculated from the pole zero identification 35 3.25 G A , parameters locations calculated from the pole zero identification . . 35 3.26 G A , parameters identification 36 3.27 G A , parameters locations 36 3.28 Continuous-time-system input and output 39 3.29 Continuous-time parameter estimates 40 3.30 Actual output and the output using the final estimates 40 3.31 Friction model 42 3.32 Motor input (/) and output (w) 43 3.33 Friction parameters identification 44 4.34 Two-degree of freedom controller 48 4.35 G A adaptive controller 49 4.36 Parameter Controller 50 4.37 Factorized Controller 55 4.38 Ladder 55 4.39 Reference input and output of a minimum phase system without noise . 56 4.40 Pole-Zero estimates for a minimum phase system without noise 57 4.41 Estimates of gain and delay for a minimum phase system without noise 57 4.42 Pole zero locations 58 4.43 Reference input and output of a minimum phase system with noise using pole-zeros estimates 59 4.44 Pole-zero estimates for a minimum phase system with noise vin 60 4.45 Estimates of gain and delay for a minimum phase system with noise . . 4.46 Pole zero locations 60 61 4.47 Reference input and output of a minimum phase system with noise using parameter estimates 62 4.48 Parameter estimates for a minimum phase system with noise 4.49 Estimates of gain and delay for a minimum phase system with noise 62 . . 63 4.50 Parameters locations 63 4.51 Reference input and output for a nonminimum phase system 66 4.52 Parameter estimate for a nonminimum phase system 66 4.53 Gain and delay estimate for a nonminimum phase system 67 4.54 Pole zero locations for a nonminimum phase system 67 4.55 Input-Output for 3 parameters estimate with unmodeled dynamics . . . 68 4.56 Parameter estimate for unmodeled dynamics 69 4.57 Gain and delay estimate for unmodeled dynamics 69 4.58 Input-Output with dead beat control 70 4.59 Parameter estimate for unmodeled dynamics with dead beat control . . 70 4.60 Gain and delay estimate for unmodeled dynamics with dead beat control 71 4.61 Input-Output with desired pole = 0.7 4.62 Parameter estimates for unmodeled dynamics with desired pole = 0.7 71 . 72 4.63 Gain and delay estimate for unmodeled dynamics with desired pole = 0.7 72 4.64 Reference input and output of a system with window size = 30 73 4.65 Parameters for a window size = 30 74 4.66 Gain and delay for a window size = 30 74 4.67 Reference input and output of a system with window size = 60 75 4.68 Parameters for a window size = 60 75 4.69 Gain and delay for a window size = 60 76 ix 4.70 Reference input and output of a system using R L S 77 4.71 Parameter estimates for RLS 77 4.72 Parameter locations for R L S 78 4.73 Reference input and output of a system using G A to compare to R L S 79 4.74 Parameter estimates for G A to compare with R L S 80 4.75 Parameter locations for G A 80 5.76 Tank Input-Output 83 5.77 Parameter estimate for a tank 84 5.78 Estimated gain for a tank 84 5.79 Pole zero locations for a tank 85 x Acknowledgement I would like to use this opportunity for thanking all those that have made the completion of this thesis possible. I would especially like to thank Prof. Guy A . Dumont, my thesis advisor, for introducing the Genetic Algorithms to me and for his advice and guidance in my research. I would also like to thank Ye Fu for providing the R L S routines and Rob Ross for his assistance in operation the Pulp & Paper Centre's fxVAX computer. At last special thanks go to Dr. K . Natarajan who read the final draft of this thesis. xi Chapter 1 Introduction 1.1 General introduction The area of system identification has been given a lot of attention over the years. Many methods have been used and many extended versions exist, but all of them are based upon eighteenth century mathematics which assumes smooth search space with ever present derivatives. In the last few years Artificial Intelligence and learning have been gaining lot of popularity and have been entering many fields, but little has been done to apply them in the field of system identification and control. 1.2 "Standard" identification methods On-line system identification methods used to date are based on recursive implementation of off-line methods such as least-squares, maximum-likelihood or instrumental variable. A l l those methods are based on the same principle and a unified description exists [23]. Those recursive schemes are in essence local search techniques that search for zero gradient by going in a direction suggested by the local gradient. They go to the nearest point that gives zero gradient and stay there. Nothing will get the methods to search further as long as the gradient stays zero. It is therefore very difficult for those methods to find a global maximum and they often fail in the search for global maximum if the search space is not differentiable or linear in the parameters. Because of 1 Chapter 1. Introduction 2 the linearity condition they have difficulty locating directly poles and zeros or physical parameters of a system. Another aspect is that these methods are all serial. They go from one point in the search space to another at every sampling instant, as a new input-output pair becomes available. They are not capable of iterating more than once on each data they receive, they need new data to direct the search. 1.3 Motivation for this work Genetic algorithms are a parallel, global search technique that emulates natural genetic operators. They search many points simultaneously and thus have the potential to converge more rapidly. In every generation new artificial chromosomes are created by taking parts of the fittest chromosomes of the previous generation and combining them to make a highly fit chromosome. They do not need to assume that the search space is differentiable or continuous because they go from one generation to another with transition rules that are probabilistic. This means the algorithms do not have to wait for new data, but can iterate a few times on each data they receive. They work with a population of binary coded strings so they can explore the search space in each generation and then direct the search to regions where there is a high probability of finding improved performance. Genetic algorithms have also been shown to excel in multimodal optimization [10], and thus have the potential to give unbiased estimates in presence of coloured noise. In this thesis, a Genetic Algorithm (GA) is implemented as an estimator for discrete time systems. The results obtained employing this new identification method are particularly favourable and they are considered to be well suited to the adaptive Chapter 1. Introduction 3 control problem. Although the use of G A has been gaining popularity, its use in adaptive control has not been investigated. The algorithm is used on few discrete time systems, both minimum and nonminimum phase and with or without colored noise. It is used to identify either parameters or poles-and-zeros. The encouraging results are then compared with Recursive Least Squares. 1.4 Outline of this thesis This thesis is organised as follows: Chapter 2. Genetic Algorithms are described and some of the simple genetic operators are explained. The algorithm is then used to find the maximum for a function with eleven local maxima. Chapter 3. A G A for system identification is implemented both in discrete and continuous time and simulations results are shown. The algorithm is also compared to Recursive Least Squares algorithm. Chapter 4. The pole placement controller design is outlined and simulations results are shown using the G A to identify plants with either minimum phase or nonminimum phase characteristic and unmodeled dynamics. One simulation is then done using Recursive Least Squares for the identification for comparison. Chapter 5. A n experiment with a water tank is explained and identification results are shown. Chapter 6. Conclusions and suggestions for further work are given. Chapter 2 Genetic Algorithms 2.1 History of Genetic Algorithms The algorithms come out of work done by John H . Holland and his students at the University of Michigan. The underlying principles of genetic algorithms were first published by Holland in 1962 [18]. The mathematical framework was developed in the late 1960's and in 1975, Holland's pioneering book, Adaptation in Natural and Artificial Systems was published [19]. The same year it was shown by one of his student that Genetic Algorithms (GAs) are very useful in function optimization even on "difficult" domains that are multimodal, noisy and high-dimensional [10]. In 1983, Goldberg used G A to minimize power consumption in gas-pipelines and then combined a learning classifier system with a G A to detect leakage in the system [13]. In the last four years a lot of research has been devoted to G A , two conferences have been held [16,17] and two books have been written on the subject [15,9]. Genetic Algorithms have proven to be useful in many different applications [15], like function optimization, computer network design, travelling salesman problem, pattern recognition and many more. 2.2 The algorithm Genetic algorithms differ from other search techniques by the use of concepts taken from natural genetics and evolution theory. They are different in four ways: 1. G A s work with coding of the parameters, not the parameters themselves. 4 Chapter 2. Genetic Algorithms 5 2. G A s search from a population of points, not a single point. 3. G A s only need fitness values. There is no requirement for derivatives or other auxiliary knowledge. 4. G A s use probabilistic transition rules, not deterministic rules. The parameters to be found by the G A , need to be coded as a finite length string over a finite search space. As an example, consider a stable real pole, (magnitude less than one) the search space would be on the interval [0,1] or if we want a resolution of 1/1000 the search space would be in the integer interval [0,1000] and with a binary coding this would be coded as a 10 bit string. The algorithm works with a population of strings, searching many peaks in parallel, hence reducing the possibility of ending at a local minimum and missing the global minimum. The only available feedback from the system is the value of the performance measure (fitness). Although transition rules are probabilistic, the algorithm is not simply a random search. It is a randomized search that is guided by the fitness values of each string. The algorithm uses information, already in the population, about things that have worked well in the past. By use of operators taken from population genetics the algorithm efficiently explores part of the search space where the probability of finding improved performance is high. A genetic algorithm in its simplest form consists of 3 steps: (see Figure 2.1) 1. Reproduction 2. Crossover 3. Mutation In the next three sections these will be described in details. Chapter 2. Genetic Algorithms 6 Randomly generated initial population r "One ~| generation - Reproduction Crossover Mutation L I Figure 2.1: Genetic Algorithm J Chapter 2. Genetic Algorithms 2.3 7 Coding It has been shown that binary coding is in a certain sense the optimal coding [19]. Suppose we have the binary strings 1010010111 and 1110100110, by comparing them we can see some similarity, 1 * 10* *011*, where * is a don't care. We call 1 * 10* *011*, a schema (plural, schemata). A string can be an instance of 2 1 0 = 1024 schemata which can be found by replacing any of the bits in the string by a don't care. The number of possible schemata on the alphabet {*,0,1} for the binary coding is 3 10 = 59094 so by carefully selecting the string all schemata could be represented by 58 strings. If the coding is decimal we would need 3 decimal number to represent the same search space as a 10 bit binary string would. A three bit decimal string would be an instance of 2 = 8 schemata but the number of possible schemata on the alphabet { * , 0 , 1 , . . . , 9} 3 would be l l 3 = 1331 so all schemata would have to be represented by 166 strings. So binary coding would need 3 times fewer strings to explore the search space. Therefore binary coding is chosen with each parameter corresponding to a fixed length binary substring of j bits [ 0 , . . . , 2 — 1]. The value, (x), of the binary substring is mapped to d an interval of the real numbers [/6,u6] to give y = -^—( b U - lb) + lb (2.1) W i t h n parameters, the final string consists of n concatenated substrings. I ai | • • • | a n | (2.2) | 2.4 10--01 | ••• | 01---11 I Reproduction In the reproduction part of the algorithm it is decided which strings are going to survive and which ones are going to disappear, based on what in biological terms, is known as Chapter 2. Genetic Algorithms 8 number of offsprings 1 0 1 2 1 1 1 2 1 0 F(i) 100 10 200 300 210 0.50 0.05 1.00 1.50 1.05 290 310 280 120 180 1.45 1.55 1.40 0.60 0.90 Table 2.1: Fitness dependent reproduction. the survival of the fittest principle. It is done by assigning a positive number, fitness F(i), to each individual in the population. It must be positive because high fitness individuals should receive more offsprings than low fitness individuals. Based on the normalized fitness F (i), n the number of offsprings for each individual is calculated. The fitness function tells us how well the system, to optimize or control, is behaving under a certain string. The fitness function can be any nonlinear, nondifferentiable, discontinuous function, because the algorithm only needs a fitness value assigned to each string. The number of offsprings is chosen according to the string normalized fitness. The fitness is normalized with the average value of the fitness, F £.(0 = • }' ] (2-3) 1=1 so the strings with above average fitness will have more than 1 offspring and those with below average fitness will have less than 1 offspring on the average (see Table 2.1). The strings are selected according to the expected value of the normalized fitness or what has become known as Stochastic Remainder Selection without Replacement, Chapter 2. Genetic Algorithms 9 [15]. That means the strings will receive number of offsprings equal to the integer value of their normalized fitnesses and then the population is filled up by choosing another offspring for each of the strings with probability equal to their fractional part until the total number of offsprings are equal to the population size TV. The algorithm keeps track of the best string in the population and if it is not in the new population (because some other G A operators destroyed it) it randomly replaces another string in the new population. 2.4.1 Ranking It is important to regulate the number of offsprings an individual can get, to maintain a diversity in the population. Especially for the first few generations, when a few "super" individuals can potentially take over a large part of the population, thereby reducing the diversity of the population. The presence of super individuals can be sensed by monitoring the number of individuals that are going to receive 0 offsprings. It is somewhat a better way than limiting the number of offsprings an individual can get, because it could be desirable to give a good individual many offsprings as long as the diversity is maintained. To control the reproduction, ranking can be introduced [3]. Whenever a certain ratio of the normalized fitness is going to receive 0 offsprings, the strings are sorted according to their fitness values. Then, instead of calculating the normalized fitness as in Equation 2.3, the normalized fitness is given to each string according to „ ... F ^ 2(max-l) = /y_i w ., , + 1 - ( * ma x iV + l ~ VjfZi , <-) 2 4 where max as shown in Figure 2.2 is a user defined value, 1 < max < 2, and N is the population size. The range of the normalized fitness will then be [2-max,max]. This means that no matter how big the fitness is for the best string its normalized fitness Chapter 2. Genetic Algorithms 10 max 1 2-max - - 1 N rank(i) Figure 2.2: Ranking will never be more than max when ranking is in effect. The lowest ranking string will similarly always be guaranteed 2 — max as its normalized fitness. 2.5 Crossover Reproduction directs the search towards the best but does not create any new individuals. The offsprings are identical to their parent. In nature, the offsprings are not exact copy of the parents, they usually have two parents and then inherit their characteristic from both parents to make up a new individual. The main operator to work on the parents is crossover, the main searching operator. This operator takes valuable information from both parents and combines it to find a highly fit individual. To apply this operator, two strings from the reproduced population are mated at random and they are cut once randomly between two bits. The new strings are then created by interchanging the tails. It means that parent A will get the tail cut from parent B as it tail and vice versa. This can best be explained by an example. Suppose there are Chapter 2. Genetic Algorithms 11 two strings 00000000 and 11111111 and assume a random number generator comes up with a 3 as the cutting place or crossover site. Then the new strings will be 11100000 and 00011111 Reproduction and crossover give genetic algorithms much of their power. The search is emphasized towards the best and new regions are explored by using information about things that have worked well in the past. 2.6 Mutation Even though reproduction and crossover come up with many new strings they do not introduce any new information into the population at the bit level. They work with the bits that are already in the population and do not get any new bits into the population. The bits can only reproduce or die, so if at certain position all the bits have the same value, there is no way that crossover and reproduction can get the lost bit back. To insure against such a loss and as a source of new bits, mutation is introduced. In the case of binary coding, the mutation operator simply flips the state of a bit from 0 to 1 or vice versa. But it should be used sparingly because it is a random search operator that searches the space randomly and the algorithm is intended to be a randomized searching algorithm, not a random search. 2.7 Mathematical Foundations The theoretical properties of genetic algorithms can be studied using the theory of schemata 1 proposed by Holland [19]. The defining length of a schema, 6(h), is the see definition of schemata in Section 2.3 1 Chapter 2. Genetic Algorithms 12 length between its outermost denning positions, for example 6(0 *0) = 3 — 1 = 2 and S(* — 3 — 3 = 0. The defining length is a measure of how often crossover may be destructive for a particular schema. For the schema 0*0 there are two ways to destruct it by cutting it, but the schema * * 0 can not be destructed by crossover, providing both offsprings created by crossover are kept. The order of a schema, o(h), on the other hand, is a measure of how often mutation will be destructive for a schema. The order of a schema is the number of defining positions for a string, for example o(0 * 0) = 2 and o(* * 0) = 1, or in other words, mutation can possibly destruct schema 0 * 0 in two places but schema * * 0 in one place. In other words, schemata with short defining length and low order, stands the biggest chance of surviving into the next generation. This can be written as the Schemata Theorem [19] T h e o r e m 1 Consider a GA using both crossover and mutation. The expected pro- portion of each schema represented in the population changes in one generation from m(h,t) to m(h,t + 1) > m ( M ) 7 ^ ( l : - ro (M)) ( - *")° X <fc) Where p is the probability of a particular mating to undergo a crossover and p c the probability of a single bit to mutate during a generation. m is The average fitness of the strings at time t representing the schema h is denoted by F(h,t) and F(t) is the average fitness of the population. What it means is that the number of schemata at time t + 1 is greater or equal to the number at time t multiplied by the expected number of offsprings less those schemata that are destructed by crossover or mutation. In other words the schemata theorem states that the algorithm is going to converge towards the best, but there is no guarantee that it is converging to the optimum. As Goldberg [15] puts it (pp.74): Chapter 2. Genetic Algorithms 13 "Convergent behavior without guarantee of optimality bothers many people who approach genetic algorithms from other, more traditional, optimization backgrounds. . . .the fact of the matter is that genetic algorithms have no convergence guarantees in arbitrary problems. They do sort out interesting areas of a space quickly, but they are a weak method, without the guarantees of more convergent procedures. This does not reduce their utility. Quite the contrary, more convergent methods sacrifice globality and flexibility for their convergence." G A have been shown to behave well on multimodal functions, although there is no known necessary and sufficient condition under which a function is genetically optimizable. However, numerous studies have shown that functions on which G A fail are pathological, and generally fail to be optimized by any other known technique except exhaustive search [4]. In a recent study by Goldberg [14] it has been shown that even though the algorithm is misled, it will converge for a wide range of starting conditions (initial population) and under unfavorable conditions. 2.8 Example Suppose we have the function (1 - cos2nt) sin lint 2 (2.5) and wish to find the maximum on the time interval [0,1]. The function has 11 local maxima, the global one being in the middle as shown in Figure 2.3. By not knowing the underlying function itself, but only the values of it, it is very difficult to locate the maximum. If the direction of steepest gradient is followed the maximum will be the one closest to the starting point. The G A on the other hand should be able to find the maximum by climbing more than one peak at a time. Chapter 2. Genetic Algorithms 14 rt rt 1.6 - o. o.e 0.4 o.e O.B 1.0 Figure 2.3: Function with 11 local maxima Assume the interval [0,1] is coded as 10 bit binary string and the population size is 10. The initial population is chosen randomly and the binary string then mapped onto the time interval. The fitness is read from Figure 2.3. The average fitness is calculated and the number of offsprings for each individual found (see Table 2.2). Crossover and mutation are done by choosing mates and crossover site, both at random. Mutation is applied by mutating every bit of the new population with probability equal to p m (approx. 1/1000), see Table 2.3. After three generations the algorithm is able to find a solution within 3.5% of the maximum, as can be seen in Figure 2.4. It is not until after 12 generations it finds The Maximum, but that is one of the underlying principles of the algorithm that it does its best while learning to do better. 2.9 Summary Because the algorithm works with a population of strings, it is given more chance to locate the global maximum in a multimodal search space. It is in fact searching many points (peaks) in parallel and exchanging information between the peaks. The initial Chapter 2. Genetic Algorithms 1000001101 0011110101 0000001110 1100010111 1000110111 0101011011 1111010111 1001100101 0111010011 0101001011 parameters 0.513 0.239 0.014 0.773 0.554 0.339 0.961 0.599 0.457 0.324 15 fitness 1.61 0.78 0.00 0.85 0.17 0.80 0.03 1.67 0.01 1.40 av. 0.74 normalized fitness 2.18 1.05 0.00 1.16 0.24 1.16 0.04 2.26 0.01 1.89 offsprings 2 2 0 1 0 1 0 2 0 2 Table 2.2: Reproduction reproduction mate x-site 10-00001101 100-0001101 00-11110101 00111101-01 110001-0111 01010110-11 100110-0101 100-1100101 01010010-11 01010010-11 3 8 1 10 7 9 5 2 6 4 2 3 2 8 6 8 6 3 8 8 new generation 1011110101 1001100101 0000001101 0011110111 1100110101 0101011011 1001100111 1000001101 0101001011 0101001001 Table 2.3: Crossover and mutation Generation 3 Generation 1 CTl Generation 14 Generation 12 Generation 11 Generation 9 Chapter 2. Genetic Algorithms 18 population is generated randomly and the population size is kept constant throughout the process. The algorithm only requires payoff information (fitness) for each of the string, without the need for assumptions such as differentiability, thus making it very useful for discontinuous surfaces. Genetic algorithms are inherently parallel. Indeed, all strings or individuals in a population evolve simultaneously without central coordination. To realize their full potential, they must be implemented on parallel computer architectures. Chapter 3 System Identification 3.1 Background Although a variety of techniques have been developed for system identification, none has proven to be effective in all domains. It would be nice to have a method that is sufficiently robust, that is, could be used on a broad class of problems. G A s have been used on a variety of problems as have been reported in [16,17,15,14]. In this chapter the algorithms are going to be applied to both discrete and continuous time systems. But first we look at some previous work in this area. Etter et. al. [11] studied the system below and modelled it as having only two poles. (t) = 1 + 1 0 g 1 y u (t) (3.6) They identified o,\ and a with the input as a white noise and used population size of 2 11. They showed that the G A did better in locating the true values than a random search did. Das and Goldberg [8] worked with system of the form = ^ MO 1 + £ a^q 1 ^ £ + aq ( « ( < ) + <(«)) (3.7) 2 with 6 = —0.2, bi — 0.1, b — 0.4, a = —1.6 and a — 0.95. The system they used 0 2 t 2 was non-minimum phase and very oscillating (£ = 0.04). They successfully identified the five parameters with the input as a P R B S signal and e(t) as Gaussian noise with variance equal to 10% of the input. 19 Chapter 3. System Identification 20 Smith and DeJong [22] used G A to calibrate a nonlinear model of US. migration patterns. There has been one application of G A for continuous time systems. Goldberg [12] identified mass-spring system with small damping (£ = 0.05) mx(t) + cx{t) + kx{t) = f(t) (3.8) where m — 1.0, c = 0.1 and k = 1.0. The force function, /(<), was a two step staircase function and he identified directly the parameters of the continuous time system, m,c and k. A l l the applications so far have been on open loop systems and for the discrete time systems have identified the parameters of the models which R L S can easily do. Nobody has seen the ability of the G A to identify directly the poles and zeros. When estimating poles and zeros with conventional estimation methods the problem is that the system is no longer linear in the parameters. Standard algorithms do not identify directly the poles and zeros. They change the system into a concatenation of second order systems and then calculate the poles and zeros for each 2 nd order block [24]. G A s on the other hand can directly identify the poles and zeros. There is really no difference from G A ' s point of view whether it is identifying the poles and zeros or the parameters. A l l it needs is a fitness value to assign to each string. The advantage of knowing the poles and zeros is simpler controller design as can be seen in Chapter 4. G A s could also be used to identify physical parameters, like Goldberg did in [12] for a mass-spring system. For instance, using this method the friction coefficient in a motor drive could be identified directly. Traditionally discrete time estimation is used which results in coefficients that are nonlinearly dependent upon the sampling time. Because of G A s ability to deal with nonlinearity they can be used to identify continuous time systems. Chapter 3. System Identification 21 The simulations were performed on Pulp and Paper Centre /nVAX. Programs were written in P A S C A L for the Genetic Algorithm and in F O R T R A N for the R L S part. 3.2 Discrete time identification Consider the system A{q-')y{t) = 2?(<f > ( « - d) + C{q- )e{i) (3-9) X Where A,B and C are polynomials in the backward shift operator, q' , i . e. y(t — 1) = 1 q~ y(t) and y,u and e are the output, input and noise respectively. The noise e(t) is a 1 normally distributed random sequence with zero mean and a unit variance (cr^). The polynomials A and C are assumed to be monic. The objective is to estimate A(q~ ), 1 B(q~ ) and the delay d, when given the input u(t) and the output y(t). The estimates 1 are denoted by Two sequences e(t) and n(t), can be defined, for calculating how well the estimates fit the system, as: Mq-'M*) = Biq-'Ht - d) + e(t) (3.10) or v(t) = y(t)-m (3.ii) with Aiq-^yit) = Biq-'Ht Then we try to minimize i?[e (f.)] or E[n (t)}. 2 2 - d) The first case corresponds to the least- squares case and has a search space which is quadratic, the second is akin to the Instrumental Variable (IV) case and has a highly nonlinear search space. Depending on the method used, the fitness function is chosen as = X > "(*(«-*))' i=0 (3-12) Chapter 3. System Identification 22 G e n e r a t i o n s Figure 3.5: Window size = 5 Figure 3.6: Window size = 10 or as F(t) = Y,M-( (t-i)Y v (3.13) t=0 where M is a bias term needed to ensure a positive fitness as explained in Chapter 2 and w is the window size or the number of time steps the fitness is accumulated over, with a effect akin to that of the forgetting factor in R L S . The effect of different window sizes can be seen in Figures 3.5 to 3.8 where the algorithm is run on a system with P R B S input and colored noise. For the moment just assume that the figures show some parameters of a second order system. From these figures it can be seen that the variance of the parameter estimates reduces as the window size increases. But there is a price to pay for increasing the window size. Implementing these fitness functions is expensive in terms of C P U time. Because of the nature of the algorithm, (i. e. coding, probabilistic transfer rules, etc.) no recursive version of the fitness function exists. So at every generation the algorithm has to calculate the estimated output for the whole window which makes the execution time proportional to the window size. There is also an advantage of not having a recursive fitness function. That means that Chapter 3. System Identification '<) fir. ;"i ! i n . j ; , . : •-. : <\ : rt\ r' i r :.!!!;! •, : ; ;; ii 'I '' i '• \i 1 B *|; i: i i ;i '* •i ( :| t(- :IL : : •; ' : J. •'. i; *• • : Xi 0.7170 : ' I'i'ii*-| i !?? ^ ? • ':: i ;i j ' ^ * -' : : : ; • •i *• "•: 3 "' i ' W^il 1 rljUlUir-Kl •0.7010 Estimated value <~ 23 ' 'o i' 1 ! ij Figure 3.7: Window size = 20 J f M i i i Irtj 1 h L ; •.0OOOEO3 i liit ji | Li J | f _ | j 1B0. G e n e r a t i o n s ! ij'i' , i'i" ! ; : "i SOO. G e n e r a t i o n s Figure 3.8: Window size = 30 the algorithm does not have to wait for new input-output data before coining up with new estimates. It can actually iterate as often as one likes for each sample but there is some upper limit because of time constraints and i n the window the input has to be persistently excited (see Chapter 4, Section 4.4.4) for the algorithm to converge to a certain value. Figures 3.9 to 3.11 show parameter estimates for different number of trials (generations per sample) for a system with P R B S input and no noise. It is seen that the algorithm actually needs fewer generations (200,175,150) to converge as the number of trials increases from 1 to 3 and hence number of data points (200,87,50). But there should be some limit on number of trials as can be seen from Figure 3.12 where the algorithm uses 30 trials for each data it needs about 2250 generations to converge or 75 samples. Chapter 3. System Identification 24 G e n e r a t i o n s Figure 3.9: Number of trials = 1 - Figure 3.10: Number of trials = 2 -7.1IMOC-03 G e n e r a t i o n s Figure 3.11: Number of trials = 3 G e n e r a t i o n s Figure 3.12: Number of trials = 30 Chapter 3. System Identification 3.2.1 25 Parameter identification The system of Equation 3.9 can be described by the following polynomials A{q~ ) = B( -') = 6 (l + 6 - 1 + --- + M - ) C{q- ) = 1 + c q- + • • • + c q~ l q 1 1+ a - +--- + a q- 1 n l 9 0 n ( - ) n i g 1 1 3 14 n n The G A can be used to identify the parameters in A and B and the delay, using either Equation 3.12 or 3.13 as a fitness function. For a second order stable system it gives a search space for ai and a of the form seen in Figure 3.13. If the system is also inversely 2 stable the search space for f>i and b is of the same form too. 2 3.2.2 Pole-zero identification Because they do not require linearity in the parameters, genetic algorithms can directly identify the poles and zeros of the system. In pole-zero form, the plant can be written as: (3.15) Biq- ) 1 = b {l-z - ){l-z q- )-..{l-z q- ){l-z q- ) 1 0 iq 1 l 1 m 1 m Where m = n/2 if n is even and m = (n + l ) / 2 if n is odd. The parameters, p z m m and will be zero if n is odd. It can also be reparameterized so that a complex conjugate poles or two real poles will be represented by two parameters. A{q-i) = (l-(a ±/3 )g- )-..(l-(a ±/? )g- ) B{q~') = Ml-(7l±tfl)g- )-"(l-(7m±*nx)?- ) 1 1 1 1 m m (3.16) 1 1 The parameters Pi and Si can be either imaginary (complex conjugate poles) or real (two real poles). Because the signs on (3 and 8 are of no importance we can use the signs to decide if the numbers are imaginary or real, negative will mean complex number and Chapter 3. System Identification a 26 2 •2 -2 2 \ i?e -2 _ ,_ _ , rigure 3.13: Parameters Figure 3.14: Poles and ze- Figure 3.15: Reparameter. ., , , . , , , ros in the complex plane lzed complex plane positive will mean real numbers. As an example l + 2 - -f0g1 2 9 l+2 - +2g1 g 2 = (l-(_l + l)g- )(l-(-l-l) - ) 1 1 9 = {l-{-l+jl) -i){l-(-l-ji) -i) q q = [-1,+1] = [-1,-1] (3.17) That gives search space for a stable system of the form seen in Figure 3.15. Where the lower half plane excluding the real axes, represents the complex conjugate poles and the upper half plane represents the real axes. If the parameters for a second order system are given by [23] (see Figure 3.13) : Aiq- ) = B(q- ) = C(q- ) = 1 X X The l.O-l.bq' + 0.7q~ 1 2 (3.18) 1.0(1.0+ 0.5g- + 0.0g- ) 1 2 1 . 0 - 1.0?" + 0.2g1 2 poles and zeros are (see Figure 3.14) : A\q~ ) x = Biq- ) = 1 1.0 - (0.75 i j O . 3 7 ) ? - 1 (3.19) 1.0(1.0- (-0.25 i-0.25)?- ) 1 or (see Figure 3.15 ) : pi = [0.75,-0.37] t2 = p x ,2 = ' 0.75 + j'0.37 0.75 - j'0.37 (3.20) Chapter 3. System Identification 27 and the zeros z l i 2 = [-0.25,+0.25] f -0.5 zi,2 = < = ( (3.21) 0.0 For a stable minimum phase plant, the poles and zeros are inside the unit circle (Figure 3.14), therefore the search space can be limited to be the unit circle or a box enclosing the unit circle. For a nonminimum phase plant some of its zeros will be outside the unit circle, so one has to decide how big the search space is going to be depending on a priori knowledge of the system. 3.2.3 Results Parameter settings The crossover rate is chosen so as to give some of the population the opportunity to survive into the next generation without any changes. The mutation rate is chosen such that on the average one string in the population is mutated. Unless stated otherwise the genetic parameters have therefore been chosen as follows [8] : Pc = p 0.8 = m population 0.01 (3.22) — 100 Second order systems were used so six parameters needed to be identified, that is d and 6 and then either parameters, bi,&2> i and a or poles-zeros, a i , / ? i , 7 i and h\. The a 0 2 delay is coded as two bit string to give 4 choices for the delay and the other parameters are coded as 7 bit strings, making totally a 37 bit string, which leaves the search space with 2 3 7 = 1.37 1 0 n alternatives. The parameters have been concatenated as follows M|o |o |6 |6 |6 | a 2 1 2 0 (3-23) Chapter 3. System Identification 28 or M|ai|/?i|7il*ilM (3.24) depending on whether poles-zeros or parameters were identified. Upper and lower bound on the parameters are defined (see Figures 3.13 and 3.14) and the resolution of the coding is calculated using Equation 2.1. lower bound 1 0.0 -2.0 -1.0 -1.0 d b CLi,bi 0 0-2, b 2 ai,/?i»7i»*i upper bound 4 2.0 2.0 1.0 1.0 # of bits 2 7 7 7 7 resolution 1 0.016 0.032 0.016 0.016 Table 3.4: Search space for a stable minimum phase system Identification with PRBS A P R B S signal is used as an input for the system of Equation 3.18. The P R B S input has a period of 127 with the bit interval equal to four times the sampling interval. The G A is run for 600 generations and 3 trials are used for each input-output data so 200 samples will be used. The window (forgetting factor) has been set as 30, i . e. the fitness function is calculated for the current input-output and the 30 previous samples. Figure 3.16 shows the output for the P R B S signal when there is no noise in the system (cr = 0). 2 Figures 3.17 and 3.18 show the estimated parameters for each 1 generation using instrumental variable criterion as given in Equation 3.13. The values of the estimates of the last generation are written at the right hand side of the graphs. After about 150 generations or 50 samples the algorithm comes up with unbiased estimates for all parameters except the zeros. Parameters —ji and 8i should both be 0.250 so a bias of 0.321 for 6\ seems rather big. But if bi and 6 are calculated we 2 Estimation of — Q i , / ? i , — 71,6 X Chapter 3. System Identification 29 3 3 O C3 O.OO 60. lOO. Number of 160. samples Figure 3.16: P R B S input and output of a system without n o i s e in - • 0.2130 T3 •7.I000E-02 ISO. 300. 460. Generations Figure 3.17: Pole-Zero estimate of a system without noise Chapter 3. System Identification 30 Chapter 3. System Identification 31 get 0.426 and 0.050 respectively (true values 0.50, 0.0). The steady state gain of the system is 7.5 so Equation 3.13 is less sensitive to changes in the zeros than the poles and it should also be emphasized that the algorithm does not necessarily converge to T H E optimum. "It does its best while learning to do better." Figure 3.19 show how the poles and zeros move around in the complex plane for each generation where the initial generation is at the back and the final generation is in front. The unit circle is also plotted every 100 generations together with the estimates at that point. 3.3 R e c u r s i v e Least Squares e s t i m a t i o n The actual process, or the system, is assumed to be described by an equation of the form A(q->)y(t) = B(q-*)u(t) + Ciq-'Mt) (3.25) where e(t) is a white noise with zero mean and a variance o~\ and the polynomials A(q~ ), B(q~ ) and C(q~ ) are given as 1 1 1 Aiq- ) = Biq- ) = Ciqr ) = 1 1 1 1.0 + a j g - + • • • + a q- « 1 q~ ( l n na (3.26) 1.0 + b - + -.- + b q- >) l n iq nb i.o Now introduce the parameter vectors 9 and 6 and a vector, <p(t), with the previous inputs and outputs 9 = [a-^, - • • ,a ,l,bx, 0 = [a ,...,a .,l,&i,-",&n„] tp{t) = na 1 - • • ,b ] nb n The output of the model (A(q (3- ) 27 T [-y{t-l),---,-y{t-n ),u{t-l),---,u(t-n -l)] T a x b ) and B(q )) can then be written as J (3.28) Chapter 3. System Identification 32 so the system output can be written as (3.29) y(t) = y{t) + *(t) Least squares is a prescription that one should take the value of 6 which makes the sum of the squares of the e(t), J^^ e (tf) as small as possible. It can be shown [23] that 2 =1 the LS estimate of 0 is £=($ $) r $ y - 1 (3.30) T where 2/(1) Y (3.31) = <P(N) y(N) T The estimate of 0 can be made recursive by Ki = P = £t+i = yt+i - pf+iOt t+ t+1 (3.32) ( l - J W f + 1 ) f where A is the forgetting factor. For numerical stability, the P matrix is factorized as Pt = s s? t (3.33) where 5" is an upper-triangular matrix and S is then updated at each iteration [6]. t 3.3.1 Results The Recursive Least Square (RLS) algorithm is run for the system of Equation 3.25 with the polynomials A, B and C described by Equation 3.18 with the noise variance, o\ = 1.0. The forgetting factor is set to 0.9 to resemble a window for the GA of 30 33 Chapter 3. System Identification 3 a o "3 fl O.O BO. -40. 60. 60. Number lOO. of 120. 140. 160. ISO. samples Figure 3.20: P R B S input and output with noise a) -O <L> 50. 100. Number of s a m p l e s 100. Figure 3.21: Parameter identification using R L S ZOO. Chapter 3. System Identification -2 J Figure 3.22: Parameters locations > 7.1000E-02 -o CO s Figure 3.23: G A , pole zero identification Chapter 3. System Identification 35 Figure 3.25: GA, parameters locations calculated from the pole zero identification Chapter 3. System Identification Figure 3.27: GA, parameters locations 36 Chapter 3. System Identification steps (0.9 30 = 0.04) and a 1 ; 37 a , &i and b are then identified. 2 2 2 Figure 3.21 shows the result using the input shown in Figure 3.20. It can be seen that the estimates have rather large variance especially b\ and b (the long dashed and dotted line respectively). 2 Their value after 200 samples is 1.3957 and 0.6088 respectively but 10 samples before their values were 0.4214 and 1.2141 respectively so it is difficult to say what value they are converging to. The estimates for ai and a have also a variance but much smaller 2 and they converge to biased estimates with the final estimates as -1.1543 and 0.4974 respectively. Figure 3.22 shows plot of a as a function of 2 and b as a function of 2 bx with the time axis running out of the page and the triangle for a stable estimates plotted every 50 samples. To compare those results with the G A , the G A is run identifying the same parameters as those identified by the R L S . That means that the gain, b and the delay, d, are 0 assumed to be known so there are only four parameters to be identified. Using same parameter settings as in Table 3.4 it gives a total string length of 28 bits, so the population size has been set to 50. The G A is run twice, first identifying the poles and zeros and secondly identifying the parameters. The results of the pole-zeros identification is shown in Figure 3.23, it is then converted into the parameters, Figure 3.24 and a 3-D figure is plotted, Figure 3.25. The parameters estimation is shown in Figure 3.26 and the corresponding 3-D figure is shown in Figure 3.27. It can be seen that in both cases the poles have almost zero bias, they are only limited by the resolution of the search space. They converge in about 50 generations for the pole-zero identification but in about 100 generations for the parameters identification or about twice as fast for the pole-zero identification than for the parameters. The zeros converge slowly for both cases but the final estimates are close to the true values (0.5 and 0.0) in both cases. If G A is then compared to the R L S it can be seen that the R L S needs more than 50 True values from Equation 3.18 are -1.5, 0.7, 0.5 and 0.0 respectively. 2 Chapter 3. System Identification 38 samples for the poles to converge but the zeros do not converge, whereas the G A needs between 50 and 100 generations for the poles to converge which means that with 3 trials per sample it needs between 17 and 33 samples and the zeros are slowly converging. So in terms of number of samples the G A converges faster. But as mentioned earlier the fitness function for the G A can not be calculated recursively so the algorithm has to calculate the outputs for all the window and to calculate every output it involves (?i + rif, + 1) multiplications and ( n + rif,) additions. The difference in bias of the a a estimates are mostly caused by different objective (cost) function, the R L S uses a simple least square whereas the G A uses IV alike objective function. 3.4 Continuous time identification Consider n-th order system with a differential operator s = ^ and unknown coefficients a; and bi y(t) = V" + <t) 6 n (3-34) The goal is to estimate directly the unknown coefficients a^'s and 6j's using the knowledge of the continuous time input and output. Current techniques would find a model of the process with filtered input and output and then use any suitable method like R L S for identification of the parameters of the model and consequently the parameters of the continuous time system [20]. One way to do the estimation using the G A would be to find the parameters 0 (0 — [d , • • •, d , 6 • • •, b ] ) such that the area of the difT a n 1? n ference between the actual output y and the output of the model y over a time window W is the smallest. min / (y(t) - y(tj)) e Jw 2 (3.35) At every sampling time T„ the area is calculated for previous W seconds, putting the initial conditions of y equal to the initial conditions of y at time kT, — W. As in the Chapter 3. System Identification fr' M i , 39 • f«< I. "i * J J">' ii»i»»!! I'! J ' .1'I « " ' I I 1 Ii ii i' 'i'' II H ' ! i l .' , 11' '11' 1 !i i'",'' ii 'i . '' ' ' ' ' 'i i ' i' i 'i i'i 11,!•i n;;II ii i'i IIi'i .iiI, n II " i" 'i i' i' ' i " j , i , ii', i ' ' " *i. . .Hi ' I' II 11' ' • " i i i i i i i 1 1 1 1 i r «i"iii »'•.'! i "I'II n mi I'll !! II Mil 1 1 1 1 ll 'I " I • ,I'II'I^,, III 'I ' pi I. i i i' s ii i ' i n ii ', " i' ' i i i h ii 1 I'l". 1'i ^'!::i;'!!'.'i!':>•'!'.' " ' ' ! ' ' 111 " i " i' I' ii 'j i'!!i"'i:i'!i'i »'!!!!-':'!!!!!..!!!!.!!!!! ' ! ' IIji 1"in : ;;«: V H .1 i r 1 i n i! i i " ii >: ii'i' i I * •'« I f :i' ;iI n 'l I.i V 51" i "n 1 If!'"!: 1 / O.O 1 1 » i ' i ! ! : •' 'I 1 |I 10. SO. 1 30. 40. 60. 60. II" *!! l! \i)'ti .'•!!! "> *)V< 1 1 1 1 1 /1 TO. 80 90. 100. Time Figure 3.28: Continuous-time-system input and output discrete time case, the algorithm can be run several times for each sampling time. 3.4.1 Results This has been implemented in ACSL using the PASCAL subroutines from previous implementations of the algorithm. A second order system has been used with the transfer function: y(t) 0.0/1+ 1.0 u{t) s +0.5s+ 1.0 2 [ ' The GA is used to find all four parameters of the plant. The search space has been defined as in Table 3.5. The total string length is 36 bits so the GA parameters have oi, a ,h,b 2 2 lower bound 0.0 upper bound 12.775 # of bits 9 precision 0.025 Table 3.5: Search space for continuous time parameters Chapter 3. System Identification 40 12. O. ' ' • ' ' ' ' 0.0 60. lOO. ISO. 200. BBO. 300. 360. 400. 460. BOO. B60. 600. 1 1 1 1 1 Generations Figure 3.29: Continuous-time parameter estimates 0.4 0.3 0.2 0.1 O.O —.2 -.3 - I 1 1 o.o to. eo. 1 30. 1 1 1 40. BO. eo. 1 70. 1 eo. . 90. 1 100. Time Figure 3.30: Actual output and the output using the final estimates Chapter 3. System Identification 41 been set the same as in Equation 3.23. The input u(t) has been chosen as (see the dashed line in Figure 3.28) : u(t) = 0.08 sin 0.5* + sin 3.0* (3.37)' The input is chosen so as to excite the system both above and below the natural frequency and they should have about the same amplitude in the output for the parameters to converge to the true value. The sampling time T, is 0.5 seconds and the window is chosen as 8 seconds. The parameter estimates are shown in Figure 3.29. The convergence is slow but they approach the actual values and the estimate after 450 generations, i. e. 150 sampling intervals is 0.000. + 1.050 s + 0.6005 + 1.025 ' 2 j which has a natural frequency, a; = 1.01 and a damping ratio, £ = 0.30 instead of n 1.0 and 0.25 respectively. If both the actual output and the output using the final estimates are plotted (Figure 3.30) one can see that the response is almost identical excluding the transient. 3.5 Friction compensation Now look at the estimation of physical parameters, namely the friction of a motor. A motor with friction torque T / and a load disturbance torque TJ can be described by the following model, J^ = KI{t)-T (i) f + T (t) l (3.39) where J is the total moment of inertia, K is the current constant and / is the motor current. Neglecting the load disturbance and introducing m = «(0 + ^ (3-40) Chapter 3. System Identification 42 Figure 3.31: Friction model the motor model can be written as J^ = Ku(t) + {f (u>)-T (u,)} f f (3.41) If the estimates are good the term inside the bracket is going to vanish and the model looks like a frictionless motor. Many models for the friction have been suggested but a model used in [5] has been adopted. The model is: z>(o,) = { aiu> + / ? i iv > 0 a iv + j3 iv < 0 2 2 Therefore the estimation of Tf(iv) requires estimation of four parameters, on, (3.42) a 2 and f3 . Only two of them can be estimated at a given time depending on whether 2 the angular velocity iv is greater than zero or less than zero. G A can be applied to this problem ones the objective function has been defined. Assuming it is required to minimize the error between the actual angular velocity and the estimated one, the fitness function becomes minj (u>(t) -<v{t)) dt 2 where W is a time window over which the objective function is calculated. (3.43) Chapter 3. System Identification O. B. 10. 43 16. 20. 26. 30. 36. *0. 46. 60. Time Figure 3.32: Motor input (I) and output (w) 3.5.1 Results The parameters of the friction model have been chosen as : Q l = 0.1 B x = 0.4 a = 0.2 3 2 = -0.2 2 (3.44) and the motor is assumed to have K = 1.0 and J = 0.1. The parameters that are identified are a l 5 /?!, a , — f3 and they are assumed to lie between 0 and 1.2775 which 2 2 with a string length of 9 gives precision of 0.0025 for each one of them. When the output is greater then zero a i and f3i are identified and when the output is less than zero the other two, a and j3 are identified. Therefore two populations are maintained, 2 2 one for cti and /?i and the other for a and (3 . The string length in each population is 2 2 18 so the population size is chosen as 50 for each one of them. The time window W for the integral of Equation 3.43 is chosen as 2 seconds and there are 3 trials for each Chapter 3. System Identification 44 > co -»-> ea s Figure 3.33: Friction parameters identification sample which is sampled at the rate of 5 per second. The input is a square wave with period equal to 12 seconds, which can be seen together with the output in Figure 3.32. Figure 3.33 shows the estimated parameters using G A and the final value that the G A comes up with is: dj = 0.100 0 X = 0.400 (3.45) d 2 = 0.205 -3 2 = 0.180 which have almost zero bias. The algorithm takes less than 100 generations to find approximate estimates for each one of the populations and further refinements are then found along the way. 3.6 Summary In this chapter it has been demonstrated how GAs can be used to estimate both continuous and discrete time systems and for identifying parameters, poles and zeros or Chapter 3. System Identification 45 physical parameters of a system. The G A has proven to be a. robust algorithm, whereas in all the applications the basic algorithm (procedures) stays the same. The only difference between these different applications is a different routine to calculate the fitness function. In all the applications shown in this chapter, the G A has been able to converge towards the actual values of the parameters. In most cases it gives unbiased estimates but in some cases it takes time, like the identification of the zeros, primarily because the objective function is not as sensitive to changes in the zeros as changes in the poles and the G A is only looking for a good solution not necessarily the best. In comparison to some widely known identification technique, R L S , the G A perform as well or even better in terms of number of samples required to converge. But G A can also easily be used on problem where R L S is difficult or even not possible to use because of the requirement of linearity in the parameters of the system. Chapter 4 C o n t r o l l e r design 4.1 Controller There are a large variety of adaptive design techniques. In this thesis I have chosen to use an indirect scheme and I am not identifying the stochastic part, so an adaptive pole placement design has been chosen. It is a simple design method that makes use of the knowledge about the poles and zeros to obtain a desired transfer function or desired response. A SISO plant is described by an A R M A X model: 1 *>=S- 3£ (<)+ - (<) (4 46) The control law for a two-degree of freedom pole-placement controller (Figure 4.34) can be written as R(q)u(t) = -S(q)y(t) + T(q)y (t) (4.47) T where y is the reference signal and R is assumed to be monic. To simplify the writing T in the analysis that follows, the arguments of polynomials are suppressed. If Equation (4.47) is written in terms of the system input u(t) and then put into Equation (4.46) the closed loop system becomes TB x . . q RC d Auto Regressive A(q), Moving Average C(q), eXternal signal B(q) 46 , . / Chapter 4. Controller design 47 The desired closed loop transfer function is given by H = (q) f=g (4,9) or TB Bm q*AR + BS A ( 4 - 5 0 ) m By choosing the desired closed loop transfer function and estimating the plant, the controller design has been reduced to finding the polynomials R, S and T that satisfy Equation 4.50. Some of the process zeros can be cancelled in the design. If B is factorized as B = B B~, where B + B~ is uncancelled process zeros, B m that are not factors of B m must be written as, B m d m The parts of B must be a factor of + Generally the degree of q AR + BS is + m = B~B' must be factors of q AR + BS so B R. Therefore R must be written as R = B R. higher than A is cancelled stable process zeros and + d so there must be some cancellation on the transfer function. So the Diophantine equations becomes q AR + B~S = A A (4.51) d 0 m and T can be found from T = B' A t m (4.52) o 0 where tf is to ensure proper gain and A is the observer polynomial that is cancelled 0 0 in the transfer function [1]. In order to design the controller we need to solve the Diophantine Equation 4.51 for R and S. In order to find a unique solution the degree of S has to be less than the sum of d and degree of A. We choose degS = deg A + d — 1. Using the causality conditions (degR > degS) the degree of A 0 can be found from Equation 4.51 to be degA 0 > 2(degA + d) - degA m - degB + - 1 (4.53) Chapter 4. Controller design Vr 48 + o T U 1_ B A R Figure 4.34: Two-degree of freedom controller The degree of R can be found from Equation 4.51 as degR = degA + degA 0 — deg A — d m (4.54) This procedure assumes that the true plant A, B is known. When the true plant is not known, one can use the G A to do the estimation of the plant A, B and then design an indirect adaptive control scheme as shown in Figure 4.35. 4.2 Parameter based design By assuming that we have knowledge of A and B~ and that A is chosen we can solve 0 Equation 4.51 for R and S. Define n = deg A, m = degB~, fc = degA and j = 0 degA , m then A(q) = q + aq~ B~{q) = b (q +b q - o{q) = g m(q) = q + aiwq " H S(q) = sq*- 1 R(q) = A A n n + • ••+ o 1 1 m m 0 fc 3 d 1 + ••• + «fc 0 3 n q m f c _ 1 0 0 + --- + b ) 1 1 + ai g n 1 h a •\-s q - ><+J-»-<t n+d + y d 1 jw • • • + r q +3-»- - + k + 2 (4.55) J n + r f -i --. + r _ _ k+j n d Chapter 4. Controller design 49 r "TSSTfivTATO" Parameters Control design Figure 4.35: G A adaptive controller In matrix form 4.51 can be written as 1 0 a x '•• 0 0 0 : ... o 1 a a n x 1 0 0 0 '•• : h ••• 0 0 0 a : '•• 1 0 ••• 0 b ! 0 0 0 ': 0 ••• n 1 ... o • • ' . 1 0 0 0 \ r ' •. 1 1 (4.56) k+j-n-d 0\ Ofco boSo 0 h m 0 0 0 '• a JW 0 boS +d-i n 0 b m where the upper right hand zero matrix has degA — (degA + d — degA a m + degB~ — 1) number of rows and the lower left hand zero matrix has d number of rows. If A and B~ have no common factors, Equation 4.56 can be solved for r< and S;, to design the Chapter 4. Controller design 50 1 1 B +* H* ) U Figure 4.36: Parameter Controller controller. Equation 4.50 in the backward shift operator (<j~ ) becomes a f j-{j-degB -(n+d-degB))'jr" j-(n+d-degB) g* m ( A*R* + q~(n+d-degB)fi* -(k-(2(n+d)-j-degB+ - 1 ) ) g* (4.57) q where * denotes that the polynomial is in the backward shift operator. If degA degB m m — = deg A -f- d — degB and the equality in Equation 4.53 is true, the transfer function becomes f*-{n+d-degB) ft* n A*R* -+ q-{^+d-degB)ff*S* (4.58) The controller can then be implemented as shown in Figure 4.36. 4.3 Pole-zero based design Wittenmark and Evans [24] have come up with a pole-zero placement algorithm based on pole-zero parameterization. What they have done is to model a high order system as a concatenation of second order systems, identify the parameters of the second order subsystems and then calculate the poles and zeros. The solution of the Diophantine equation corresponds then to a solution of a. linear triangular system of equations where the controller parameters can be calculated recursively. Chapter 4. Controller design 51 Assume that the poles and zeros of A and B respectively, are known and the poles of A and A are chosen. m 0 (q) = (<7 - Pi) •••(?- B~(q) = buiq - z ) • • • (q - A {q) = {q ~ Pi ) Mq) = A Pn) z) x m (4.59) m • • • (q ~ w p) jw {q ~ Pio) • • • (q ~ Pko) As before Equation 4.51 needs to be solved for R and S. The solution can be split up into three parts: One for finding coefficients of the terms with degree less than d, the second for finding coefficients of the terms with degree rn + n + d and higher and the third one for finding the rest of the coefficients. The polynomial R can be split up into two parts, one with terms of degree lower than m and the other with terms of degree m and higher. R{q) = q R" + R' m = + ^y+i-m-n-rf-l . . . + + ^ ( 4 . 6 0 ) where R" can be calculated recursively by long division of Equation 4.51. Similarly for the S polynomial. S = q S'+S" d = q (3 q -' d n 0 + • • • + !„_!) + s'^q - + --- + 3^, d 1 (4.61) where 5" can be found by long division. By using the fact that A(pi) — 0 and B~(zi) — 0 the coefficients in R' and S' can be calculated separately by evaluating Equation 4.51 for q — pi and q = z it B-{ )p S\ ) d Vi Pl zfA{zi)R'(zi) = A^pAA^pA-B-ipAS'Xpt) = A {z )A {z )-zfA{z )zrR"{z ) 0 i m i i (4.62) i (4.63) Chapter 4. Controller design 52 where 2, are uncancelled process zero (zi € B~). B y reparameterizing R and S' into Newton coefficients, solution to Equations 4.62 and 4.63 can be found by solving a set of triangular system of equations. m—l S'{q) (4.64) (4.65) = E-S/i(9) i=0 where i =0 1 9i(q) = fi(q) = (4.66) I n;=i(g-^) i < t < m - i t= 0 1 nj=i(?-Pi) l<i<n-l 0 1< k <i (4.67) and 9i{*k) Yl) (z =1 fi(Pk) = ' k (4.68) - Zj) i + 1 < k < m 1< k <i ' 0 (4.69) Now, the parameters of R' and S' can be found by solving the following set of triangular equations A o t P i M m t P i ) _ S"(PI) __ fB-( ) P HP? Pl _ / 0 (4.70) ^ f f 1 - ^ = * 0 +'i/l(Pn) + - " + <. /„- ( „) 1 1 P Chapter 4. Controller design 53 and for R' A (zi)A (zi) 0 m Ao(z )A„ (z ) 2 l 2 \iMz ) ! 2 " " l i f e ) " 4.3.1 0 -mjjii/ \ _m D»/ \ _ -^R(^) ~ _ - = I / , -I „ („ \ r + r {z ) 0 l9l 2 < + r[ {z ) gi + •••+ m r' _ _ {z ) m igm x m Multiple poles and zeros Assume that the algorithm estimates that there is a pole p; with multiplicity m^. It implies that is has to find m ; coefficients from the pole. That can be done by replacing m; equations in Equation 4.62 by the following B-( )p S'( ) = d Pi Pi A [B-( ) S'(q)} = d q ^ q q=pi [B-( )q S'( )} = d q q I g= A ( )A ( ) 0 Pi m A ( )A ( ) [Ao q m - Pi q B-( )S"( ) Pi - Pi B-( )S"( )) q q q=pi (4.72) i^[A ( )A ( )-B-( )S''( )] 0 q m q q q q=pi Pi from the first equation we can get and the last one we get s[_ 1+ . In the case of multiple zeros we differentiate Equation 4.63 instead of Equation 4.62. 4.3.2 Complex poles and zeros Complex poles and zeros do not cause any problem because Equations 4.70 and 4.71 can be assumed to be defined on the complex plane. That means that some of the coefficients r,- and will be complex so a filtering of complex signals has to be included (see Figure 4.38 Section 4.3.3). The total signal will however always be real as can be seen if Z\ and z from Equation 4.71 are assumed to be complex conjugate zeros 2 (zj = z = a — jb) and further more assume that r' — a + j/3. Then the first two 2 0 Chapter 4. Controller design 54 equations in Equation 4.71 become a + j/3 = r' a-jB - 0 (4.73) r' + r[{z 0 x Zl ) so r j is r, = I~ b (4.74) 1 Because r' is used in combination with — r' z the total signal is always a real signal. u 1 r' - r\z = a - j 3 0 4.3.3 1 {{a + jb) = a - -J x (4.75) Implementation The polynomials in the backward shift operator are m-1 k + j-m-n-d i=0 = s- i=0 R"" + -( +J-"- - + ) R'* fc d m g j = E*sM9 )9~ _1 B+1+i +9" i:*r9 n »=0 = (4.76) 1 _i t=0 5'* + g-"5"* (4.77) If the equality in Equation 4.53 holds (k = 2(n + d) — j — degB becomes R* = R"* + -(n+d-d B) u q eg R & n d t h e c o n t r o u + — 1) Equation 4.77 e r can be implemented as shown in Figure 4.37, where R" and S" are implemented using a ladder network as shown in Figure 4.38. 4.4 Results In the simulation runs that follow, the input has been chosen to be a square wave with period of 60 steps, the desired closed loop system is supposed to have a deadbeat response and the observer is deadbeat as well. A n impulse is used to initialize the G A , i . e. fill up the window. Chapter 4. Controller design Vr 55 + T* + o—o , 1 I 1 H"* / = deg A + d - degB R" + y S" J q -n S'" Figure 4.37: Factorized Controller l - Viq -n + l „' 1 - p -iq 1 1 n q-'<-2 'n-l -oFigure 4.38: Ladder Chapter 4. Controller design 56 P. _2. I —SO. 1 1 O.OO 60. ! Number 1 ! 1 100. of 160 1 1 200. samples Figure 4.39: Reference input and output of a minimum phase system without noise 4.4.1 M i n i m u m phase plant The plant to be controlled is the same one as used in Chapter 3. Aiq-'Ml) = B{q- )u{i l - 1) + C{q- )e{i) l (4.78) with A{q~ ) = Biq- ) = C{q- ) = l 1 X 1 . 0 - 1.5?- + 0 . 7 1 2 9 1.0(1.0 + 0.5c; + 0.0q~ ) -1 2 l.O-l.Og^+O^g- (4.79) 2 The poles and zeros of A and B are identified using the IV criterion from Equation 3.13 using the same parameters settings as in Table 3.4. W i t h o u t noise Chapter 4. Controller design "to > 0} Figure 4.40: Pole-Zero estimates for a minimum phase system without noise •a 900. Generations Figure 4.41: Estimates of gain and delay for a minimum phase system without noi Chapter 4. Controller design 58 2-1 -2-J Figure 4.42: Pole zero locations Chapter 4. Controller design 59 fx o ex -2. ' — BO. ' 0.00 1 BO. N u m b e r 1 of 100. samples " 160. ' 200. Figure 4.43: Reference input and output of a minimum phase system with noise using pole-zeros estimates Figure 4.39 shows the reference input and output of the plant when there is no added noise in the system (<r = 0.0). The output follows the reference input within the 2 first 30 steps and there is a bit of oscillations in the control signal because of zeros cancellations. The estimates of the poles and zeros are plotted in Figure 4.40 and it can be seen that unbiased estimates are obtained after about 300 generations or 100 time steps. Prior to that there is a small bias in the estimates, particularly in the zeros, that contributes to the small ripples in the output whenever the reference input is changed. The gain converges to the true value after about 81 generations or 27 steps as can be seen in Figure 4.41. Figure 4.42 shows then the locations of the poles and zeros estimates in the complex plane. W i t h noise Chapter 4. Controller design 0.2280 B.0000E-03 s to Figure 4.44: Pole-zero estimates for a minimum phase system with noise T8 soo. Generations Figure 4.45: Estimates of gain and delay for a minimum phase system with noi Chapter 4. Controller design 2-1 Figure 4.46: Pole zero locations 61 Chapter 4. Controller design 62 2. 1. 3 OH D o. -1. -2. -60. O.OO 100. 60. N u m b e r of 160. 200. samples Figure 4.47: Reference input and output of a minimum phase system with noise using parameter estimates 2. 11 I*. 1. ,*. i\ Es timated values 1 -' ; 1" h ZL. -L--. - f "I 1 : P: ,1. ,? O. _ Ji. 1 i -z. O.O 1 1B0. 300. Generations 1 460. 600. Figure 4.48: Parameter estimates for a minimum phase system with noise Chapter 4. Controller design 63 goo. Generations Figure 4.49: Estimates of gain and delay for a minimum phase system with noise Chapter 4. Controller design 64 Figure 4.43 shows the reference input and the output of the plant when a colored noise is added to the output. The white noise, e(*), has standard deviation <J\ — 0.1. By looking at Figures 4.44 and 4.45 it can be seen that good estimates are found after 50 generations or 17 steps, but there is still a small bias in the estimates especially the zeros. It should though be remembered that even though the zeros have a, big bias, if the parameters are calculated they do not have a big bias. For example the final estimates for the zeros of 0.228 and 0.008 (true value 0.25 and 0.25) gives the parameters 0.456 and 0.052 which is not far from the true values of 0.5 and 0.0. The estimates i n the complex plane for every generation are then shown in Figure 4.46. To see how the controller based on its parameters behaved compared to the controller based on the poles and zeros, the G A was run again but now estimating the parameters not the poles and zeros. It was shown (Figure 4.47) that the parameters controller does as good job as the pole-zero controller. The estimates take a little bit longer time to converge to acceptable level (Figures 4.48 and 4.50) than they did in Figures 4.44 and 4.45 and the zeros take long time to find refined values because the objective function is more sensitive to changes in the poles than zeros because of steady state gain of 7.5. Figure 4.50 shows then the a — a and b — b plane for each generation x 2 x 2 and how the estimates evolve. 4.4.2 Nonminimum phase plant The plant to be controlled is taken from Clarke [7]. O.lg-iQ. + 2 g ~ ) ( l + 0q- ) 1 1 (1 - O . ^ X l - O.Sq- ) 1 (4.80) Chapter 4. Controller design 65 Using the parameterization given in Chapter 3 the plant parameters are as follows: b = 0.1 d= 1 0 = 0.85 7 p\ = 0.05 l = 1.0 (4.81) ^ = 1.0 The search space for the poles and the gain is the same as previously but the search space for the zeros has been doubled in size (see Table 4.6) to account for the nonmininium phase behaviour. The observer is chosen to be deadbeat and the desired closed lower bound upper bound # of bits precision -2.0 2.0 7 0.032 7ii*i Table 4.6: Search space for nonminimum phase loop plant is assumed to have poles at 0.2 and 0.0 and because unstable process zeros B~ are not cancelled the desired transfer function becomes: q-*B0.2?- (4.82) 1 It is not until after 300 generation or 100 time steps that estimates (Figures 4.52 and 4.53) are found that give a good control and the output is following the reference input quite nicely as can be seen i n Figure 4.51. The estimates have a small bias but that does not seem to affect the output. 4.4.3 Unmodeled dynamics We use the same N M P plant as in the previous section (Section 4.4.2) but now the G A uses a first order model ^ , 4 . 8 3 ) Similar test sequence as used by Clarke [7], i . e. the system is initially run in open loop and then there are setpoint changes every 25 step. The window is chosen as 50 th Chapter 4. Controller design Z3 P. & -4-> o p. N u m b e r of samples Figure 4.51: Reference input and output for a nonminimum phase syst CO -B.0000E-03 O.O ISO. 300. 4B0. eoo. Generations Figure 4.52: Parameter estimate for a nonminimum phase system em Chapter 4. Controller design Figure 4.54: Pole zero locations for a nonminimum phase system 67 Chapter 4. Controller design 68 3 -60. 0.00 60. 100. 160. Number of 800. 260. 3O0. samples 360. 400. Figure 4.55: Input-Output for 3 parameters estimate with unmodeled dynamics samples and the search space is defined as in Table 4.7. d bo ai The desired pole was set lower bound upper bound # of bits precision 1 0.0 -1.0 -2.0 4 2.0 1.0 20.0 2 1 0.016 0.016 0.043 7 7 9 Table 4.7: Search space for unmodeled dynamics at 0 (dead-beat). For the first simulation the delay d is assumed to be known so only the gain, the pole and the zero (b , a and b ) are identified. That gives a response 0 x x that has about 70% overshoot and has a low damping as shown in Figure 4.55 and the parameter estimates are as shown in Figures 4.56 and 4.57 with the estimates for the zero not converging to a certain value. But when all the four parameters (b , 6 0 1} d and aj) are identified (population size = 50, total string length = 23) the overshoot is reduced to about 30% and the damping is higher, Figure 4.58, and the system is Chapter 4. Controller design 69 BO. > 'V' to B * >' SUV"!! !l Generations Figure 4.56: Parameter estimate for unmodeled dynamics 8.4000E02 Figure 4.57: Gain and delay estimate for unmodeled dynamics Chapter 4. Controller design =3 1=5 o -»-> CL, 0.00 60. lOO. 160. Number of 200. 260. 300. 360. samples Figure 4.58: Input-Output with dead beat control 13 ro 6 Generations Figure 4.59: Parameter estimate for unmodeled dynamics with dead beat control Chapter 4. Controller design 71 1 1 1 11 82. M —» to Generations Figure 4.60: Gain and delay estimate for unmodeled dynamics with dead beat control 3 ex o QL, a -eo. o oo eo. 100. iso Number eoo. of eso. aoo. 3GO. samples Figure 4.61: Input-Output with desired pole = 0.7 400. Chapter 4. Controller design CD "(0 t> -O CO -4-> s Generations Figure 4.62: Parameter estimates for unmodeled dynamics with desired pole •si •B5 eoo. Generations Figure 4.63: Gain and delay estimate for unmodeled dynamics with desired pole Chapter 4. Controller design 73 3 QH 3 H-» o "3 QH -60. 0.00 60. 100. 160. Number of ZOO. Z60. 30O samples 360. Figure 4.64: Reference input and output of a system with window size 30 estimated to be (see Figures 4.59 and 4.60) 0.599g- (l + 0.798g- ) 1 - 0.953?2 1 1 (4.84) Further improvement is obtained if a slower response is chosen (desired pole at 0.7), Figure 4.61. The estimated model becomes (see Figures 4.62 and 4.63) 0.662g- (l + 0.712g- ) 1 - 0.937?3 1 1 4.4.4 (4.85) Persistently exciting signal To show the effect of a persistent excitation, the minimum phase system of Equation 4.79 without noise (<T = 0.0) is run for a step change every 60 sample and a. window 2 size of 30 and 60. For the smaller window the algorithm comes up with good estimates after about 150 generations (see Figures 4.65 and 4.66), but is not able to keep them because the input and the output does not change over the window. The estimates 74 Chapter 4. Controller design n co > ca s co Ed 800. Generations Figure 4.65: Parameters for a window size = 30 -a -65 CM Generations Figure 4.66: Gain and delay for a window size = 30 Chapter 4. Controller design 3 OH -l-> o 3 QH — lOO. —60. O.OO 60. lOO. Number 160. 200. 260. 300. 360. 400. of samples Figure 4.67: Reference input and output of a system with window size > Generations Figure 4.68: Parameters for a window size = 60 Chapter 4. Controller design 76 fz. eoo. Generations Figure 4.69: Gain and delay for a window size = 60 starts to deteriorate and the algorithm is not able to bring them back consequently the output does not follow the input very well (Figure 4.64). When the window is increased to 60, to be able to include a step change in the window at all time, the estimates are shown to converge to the true value (Figures 4.68 and 4.69). Because of a small bias in the estimates the output has a small overshoot at every setpoint change (Figure 4.67). 4.4.5 Recursive Least Squares To compare the G A to some method that is widely known, a standard R L S algorithm is used on the same system as before with noise variance o\ = 0.1. The same pole placement controller design is used. A deadbeat observer is chosen and the closed loop poles and zeros are set at zero (deadbeat). The forgetting factor is set to 0.9 to resemble a window for the G A of 30 steps (0.9 30 = 0.04) and a ,a ,fe and 6 are then identified. 1 2 1 2 Figure 4.70 shows the reference input and the output of the system. It can be seen that Chapter 4. Controller design 77 3 ex ao a -4-» OH Timesteps Figure 4.70: Reference input and output of a system using R L S CD J3 !> T3 2.8200E-02 CD CO s eo. ioo. Number of 160. samples Figure 4.71: Parameter estimates for R L S Chapter 4. Controller design Figure 4.72: Parameter locations for R L S Chapter 4. Controller design 79 3 -BO. 0.00 60. Number of lOO. 160. samples 200. Figure 4.73: Reference input and output of a system using G A to compare to R L S the overshoots becomes larger as the parameter estimates deteriorates (Figure 4.71). Figure 4.72 shows plot of a as a function of a and b as a function of b\. 2 x 2 To compare those results with G A , the G A has been run for same parameter estimates (only pole and zeros, not gain and delay) using IV criterion and the results are shown in Figures 4.73, 4.74 and 4.75. Comparing Figure 4.70 and Figure 4.73 one can see that there is not much of a difference in their response. Both have transients while searching for good parameters and after few steps output follows the input. The R L S is quicker to converge to a value whereas the G A is satisfied with suboptimal estimates. 4.5 Summary It has been shown how knowledge of the plant (.4 and B), either its parameters or poles-and-zeros, can be used to design a pole-placement controller. Simulations results Chapter 4. Controller design 80 3 cu .*-> eo 0 m 1BO. 300. Generations 400. Figure 4.74: Parameter estimates for G A to compare with R L S Chapter 4. Controller design 81 show that the G A is as well fit for doing the identification as the R L S . The G A has proven to be able to handle both minimum and nonminimum phase systems and has also shown its ability to control when there is unmodeled dynamics. Chapter 5 Experiment 5.1 Water level in a tank A n experiment was carried out on a tank system at the Pulp and Paper Centre. The tank has a sensor to measure the height h of the water and a pump to pump the water, given a drive voltage u, into the tank. The outflow of the tank is a function of the tank level so the dynamics will be nonlinear. Therefore the tank can be described by a nonlinear differential equation of the form [2]: ^ = -AVh at + Bf(u(t)) (5.86) Where A depends on gravity and the ratio between the effective outlet area and the cross section of the tank and B depends on the cross section of the tank and also relates the pump flow to the drive voltage u of the pump motor electronics. A linear model of the tank is given i n A s t r o m and Ostberg [2] as: KT His) = ' Ts + l (5.87) K K 1 where T depends on A and the initial height and K depends on the sensor and the constant B. A Z O H is used together with the A/D converter to read the water height so the Z-transform would be: „, , H KT(1 - e-%)z~ ( ) = — r z (1 — e where T, is the sampling time. 82 IT-T— T 1 (- ) 5 z~ ) 1 88 Chapter 5. Experiment 83 10. 80. 30. Number 40. of 60. 60. 70. samples Figure 5.76: Tank Input-Output 5.2 Simulation results To collect the data the sampling time is chosen as 0.55 sec. and 80 samples are obtained using P R B S as the input (see figure 5.76). Because of the prohibitive time it takes to run the G A on an I B M A T we were not able to do any online control on the tank. The G A is therefore run offline using the I V fitness function (see equation 3.13) to identify directly the poles and zeros. The algorithm assumes that there are two poles, one zero and it also identifies the gain b . 0 il+Piq-W+Piq- ) 1 [ j The poles are decoded as in chapter 3. Both the poles and the zero are assumed to be stable so they are assumed to lie between -1 and +1. The gain is assumed to be in the range [0,10] The length of each string is chosen as 11 which give resolution of about 1/1000 for the poles and the zero and about 5/1000 for the gain. W i t h four Chapter 5. 84 Experiment cu > cu -•-> 0 co Generations Figure 5.77: Parameter estimate for a tank .s 0.8000E-02 Generations Figure 5.78: Estimated gain for a tank Chapter 5. Experiment -2-" Figure 5.79: Pole zero locations for a tank Chapter 5. Experiment 86 parameters to identify, the total string length is 44 bits so the population size is set to 100. The probability of crossover and mutation is chosen as before to be 0.80 and 0.01 respectively and 6 generations were generated each sampling interval. Figure 5.77 and 5.78 show the estimated parameters for each generation using the input output data of figure 5.76. The estimated system after 300 generations is: o.oesg-Mi-o.eeig- ) (1 - 0.637g- )(l - 0.965-r ) 1 1 1 o.oesg(1 - 0.965-?- ) 1 1 [ ' ' So the zero cancels one of the poles and the system is a first order system with a delay and a pole close to the unit circle. The time it takes to fill up the tank is about 10 seconds so with a sampling time close to half a second the pole should be according to equation 5.88 about -0.95 so the estimates seems good. In figure 5.76 the output of the tank is shown if the final estimated parameters were used (dashed line). It can be seen that the estimated output is not far from the actual one and it should be pointed out that the estimated output is put equal to the actual output at the beginning of every window, which means that the two output are much closer than suggested in figure 5.76. In figure 5.79 the locations of the poles and the zero are shown in the complex plane for every generation where the cancellation of one of the poles with the zero can be clearly seen. Chapter 6 Conclusions In this thesis a new approach was taken to the identification problem. The usual hill climbing algorithms that follow the steepest gradient were abandoned for a method that uses concepts from evolutionary theory called Genetic Algorithms. They proved to be able to identify both discrete time and continuous time systems and could give unbiased estimates in the presence of colored noise. They showed some advantage over R L S and could be used in cases were the system is not linear in the parameters were R L S can not be used, for example identify physical parameters, delays and pole-zeros. They were used to design an adaptive pole-placement controller and gave good control for a variety of problems as demonstrated by simulations. A n experiment was presented. The algorithm was tested on a real data from a tank system. The algorithm behaved well but because of the prohibitive time it takes for the algorithm to run on an I B M - A T , no real time online control was attempted. Genetic Algorithms have proven to be useful on wide range of applications without any changes in the basic algorithm. The only interface with the system the algorithm is working on is through the objective or fitness function. That function is the only thing that needs to be changed from one application to another. Because the G A s search within a population not from a single value they are insensitive to noise. As with the R L S , there must be some priori knowledge about the system to identify, the search space that the parameters are likely to lie within must be specified and also the resolution. For a proper choice of the resolution the algorithm will prevent the 87 Chapter 6. Conclusions 88 estimates from jumping around and hence could be used to filter some noise. It should also be remembered that the algorithm is a randomized search technique, so there is no guarantee of optimality, the algorithm does its best while learning to do better. A n area for further research is the exploitation of more than the best string in the population for the design of a robust controller. For example the average of the ten best strings in the population could be used for preventing abrupt changes in the estimates. Also dominance could be used for a changing plant and for a multimodal search space, like the example from chapter 2, some sort of distribution among the peaks could be maintained by introducing sharing, that is the individuals are prevented from crowding around one particular peak by punishing them for being too close together. That could be particularly useful in changing environment where by maintaining diversity in the population the algorithm does not put all of its effort into searching around a particular peak. Finally, G A s are parallel algorithm, so every attempt to run the algorithm on nonparallel computer is bound to be slow. For our case the algorithm uses little bit less than 1 second of C P U time for each generation, on a /A-VAX (1 MIPS) for population size of 100, string length of 37 and window size of 30 steps. Once parallel computer architectures become readily available, G A will become more attractive. Bibliography strom, K . J . and B . Wittenmark, (1984). Computer controlled systems, Prentice Hall Inc., Englewood Cliffs N . J . [2] Ast r6m, K . J . and A . B . Ostberg, (1985). " A teaching laboratory for process control," Proceedings of the American Control Conference, pp. 1380-1385, vol. 3. [3] Baker, J . E . , (1985). "Adaptive Selection Methods for Genetic Algorithms," Proceedings of an International conference on Genetic Algorithms and Their Applications, pp. 101-111. [4] Bethke, A . D . , (1980). Genetic algorithms as function optimizers. Doctoral dissertation (CCS), University of Michigan, A n n Arbor, M I . [5] Canudas, C , K . J . Astrom and K . Braun, (1987). "Adaptive compensation in D C motor drives," IEEE Journal of robotics and automation, pp. 680-685, vol. R A - 3 , No. 6, December. [6] Clarke, D . W . , (1981). "Implementation of self tuning controllers," Self-tuning and adaptive control: Theory and applications, (eds. C . J . Harris and S.A. Billings), pp. 144-165. [7] Clarke, D . W . , (1984). "Self-tuning control of nonminimum-phase systems," Automatica, vol. 20, pp. 501-517. [8] Das, R. and D . E . Goldberg, (1988). "Discrete-Time parameter estimation with 89 Bibliography Genetic algorithms," Proceedings of the 19 90 l annual Pittsburgh conference on mod- elling and simulation. [9] Davis, L . (Ed.) (1987). Genetic Algorithms and Simulated Annealing, London: Pitman. [10] DeJong, K . A . , (1975). An analysis of the behavior of a class of genetic adaptive systems. Doctoral dissertation (CCS), University of Michigan, A n n Arbor. [11] Etter, D . M . , M . J . Hicks, and K . II. Cho, (1982). "Recursive adaptive filter design using an adaptive genetic algorithm." Proceedings of the IEEE International conference on Acoustics, Speech and Signal Processing, pp. 635-638, vol. 2. [12] Goldberg, D . E . , (1981). System identification via genetic algorithm, Unpublished manuscript, University of Michigan, A n n Arbor, M I . [13] Goldberg, D . E . , (1983). Computer-aided gas pipeline operation using genetic algorithms and rule learning. Doctoral dissertation (civil engineering), University of Michigan, A n n Arbor. [14] Goldberg, D . E . , (1987). "Simple genetic algorithms and the minimal deceptive problem," Genetic algorithms and simulated annealing, Lawrence, D . (Ed.), Pitman Publishing, pp. 74-88. [15] Goldberg, D . E . , (1989). Genetic algorithms in Search, optimization and Machine Learning, Addison-Wesley. [16] Grefenstette, J . J . (Ed.), (1985). Proceedings of an International conference on genetic algorithms and their applications, Hillsdale, N J : Lawrence Erlbaum Associates. Bibliography 91 [17] Grefenstette, J . J . (Ed.), (1987). Genetic algorithms and their applications: Proceedings of the second international conference on genetic algorithms, Hillsdale, N J : Lawrence Erlbaurn Associates. [18] Holland, J . H . , (1970). "Outline for a logical theory of adaptive systems," A. W. Burks (Ed.), Essays on cellular automata, pp. 297-319, University of Illinois Press. [19] Holland, J . H . , (1975). Adaptation in Natural and Artificial Systems, University of Michigan Press, A n n Arbor. [20] Johansson, R., (1986). Identification of continuous time dynamic systems, Tech- nical Report, Department of Automatic Control, Lund Institute of Technology, Lund, Sweden. [21] Kristinsson K . and G . A . Dumont (1988). "Genetic algorithms in system identification", Third I E E E international symposium on intelligent control, Arlington, VA, USA. [22] Smith, T. and K . A . DeJong, (1981). "Genetic Algorithms applied to the calibration of information driven models of US migration patterns," Proceedings of the 12 th Annual Pittsburgh conference on Modelling and Simulation, pp. 955-959. [23] Soderstrom, T., L . Ljung, and I. Gustavsson, (1974). A comparative study of recursive identification methods, Report 7427, Lund Institute of Technology, Lund, Sweden. [24] Wittenmark, B . and B . J . Evans, (1988). " A n adaptive pole placement controller based on pole-zero parameterization," Preprint from the 8 th IFAC/IFORS sympo- sium on identification and system parameter estimation, pp.98-103, Beijing, China. Appendix A Genetic algorithms procedures Program P P C G A P R O C E D U R E Select a population ; BEGIN F O R all the population size D O F O R all the bits D O IF random > 0.5 T H E N bit := 1 E L S E bit := 0 ; END ; P R O C E D U R E Schemata ; BEGIN { Count how many 1 there are in each bit position using one counter for each bit position. Then count lost bits by counting number of counters that have value equal to 0 or population size. Then count converged bits by counting number of counters that have value less than converged % or those with value greater than (1 - converged) %. } END ; P R O C E D U R E System ; 92 Appendix A. Genetic algorithms procedures BEGIN { Choose either P R B S input (no control) or setpoint changes } IF setpoint changes T H E N Every bitinterval multiply the input y f(t) re with -1.0 ; IF P R B S input T H E N Every bitinterval make the P R B S sequence using shift register as given Eykhoff [1974] ; Find e(t), the normally distributed random sequence ; Call the controller design with the best estimate to find the next controller output, u(t) ; END ; P R O C E D U R E Convert the strings into the parameters ; BEGIN F O R all the population D O F O R all the substrings D O BEGIN x := decimal value of the binary substring ; resolution := maximum value - minimum value 2length oi substring _ j ' y := x * resolution + minimum value ; END ; END ; P R O C E D U R E Fitness evaluation ; Appendix A. Genetic algorithms procedures BEGIN F O R all the population D O BEGIN F O R t-window size T O t-0 D O BEGIN IF R L S T H E N BEGIN e:=y-ju; fitness := bias - e + fitness ; 2 END ELSE BEGIN y := f u • v-=y-y ; fitness := bias - r/ + fitness ; 2 END END ; END ; END ; P R O C E D U R E Quicksort; Use algorithm given in the book D A T A S T R U C T U R E by Thomas A . Stan dish page 25-27 or any other sorting algorithm TECHNIQUES Appendix A. Genetic algorithms procedures PROCEDURE Rank; BEGIN max — 1 a := 2 popsize — 1 ' max — 1 b := 1 : -(popsize + 1) ; popsize — 1 FOR all the popsize DO fitness := a * rank + b ; END ; PROCEDURE Offspring ; BEGIN FOR all the population DO BEGIN Normalized fitness := fitness / meanfit ; Int fit := integer value of normalized fitness ; Offspring count := Intfit ; Throw a dice to decide if the string gets one offspring for the fractionalpart or not ; END ; IF there are too few or too many in the population THEN choose the one that were most likely to get additional offspring and did not or the one that were most unlikely to get additional offspring and did, depending on whether the population size is too small or too large respectively. ; END ; Appendix A. Genetic algorithms procedures P R O C E D U R E Copies ; BEGIN W H I L E population size is not full D O BEGIN Next string ; W H I L E offspring count < 0 D O BEGIN Copy string ; Offspring count := offspring count - 1 END ; END ; END ; P R O C E D U R E Crossover ; BEGIN F O R half the population size D O BEGIN Find the first string that has not been used Choose another string randomly ; Apply crossover with p probability ; c IF crossover T H E N BEGIN Choose crossover point randomly ; Appendix A. Genetic algorithms procedures Copy first half of first string up to crossover point and second half of second string from crossover point to the end into the first offspring ; Copy first half of second string up to crossover point and second half of first string from crossover point to the end into the second offspring ; END ELSE BEGIN Copy first string into first offspring ; Copy second string into second offspring ; END ; END ; END ; P R O C E D U R E Mutation ; BEGIN F O R all the population size D O F O R all the bits in each string D O Mutate each bit with p m END ; BEGIN Get all parameters ; Initialize random generators ; probability ; 97 Appendix A. Genetic algorithms procedures Initialize system input and output ; Print initial values ; Select a population ; Start with the initial estimate as 1, 0, ..., 0 ; F O R kids := 1 T O number of kids D O BEGIN Schemata ; IF (kids-1) / trial = integer T H E N system ; Convert the strings into the parameters ; Fitness evaluation ; Calculate the average fitness ; Offspring ; Count how many receive 0 offsprings ; IF (receive 0 offsprings) > (fitOpct * popsize) T H E N BEGIN Quicksort ; Rank ; Offspring ; END ; Copies ; Crossover ; Mutation ; Find the best string ; IF it is not in the new population T H E N Replace a string randomly chosen with the best one Appendix A. Genetic algorithms procedures Print report ; Make the new generation the current one ; END ; END ; 99
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Genetic algorithms in system identification and control
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Genetic algorithms in system identification and control Kristinsson, Kristinn 1990
pdf
Page Metadata
Item Metadata
Title | Genetic algorithms in system identification and control |
Creator |
Kristinsson, Kristinn |
Publisher | University of British Columbia |
Date Issued | 1990 |
Description | Current online identification techniques are recursive and involve local search techniques. In this thesis, we show how genetic algorithms, a parallel, global search technique emulating natural genetic operators can be used to estimate the poles and zeros of a dynamical system. We also design an adaptive controller based on the estimates. The algorithms are shown to be useful for continuous time parameter identifications and to be able to identify directly physical parameters of a system. Simulations and an experiment show the technique to be satisfactory and to provide unbiased estimates in presence of colored noise. |
Subject |
Algorithms System identification |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-10-28 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065632 |
URI | http://hdl.handle.net/2429/29628 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1990_A7 K74.pdf [ 4.33MB ]
- Metadata
- JSON: 831-1.0065632.json
- JSON-LD: 831-1.0065632-ld.json
- RDF/XML (Pretty): 831-1.0065632-rdf.xml
- RDF/JSON: 831-1.0065632-rdf.json
- Turtle: 831-1.0065632-turtle.txt
- N-Triples: 831-1.0065632-rdf-ntriples.txt
- Original Record: 831-1.0065632-source.json
- Full Text
- 831-1.0065632-fulltext.txt
- Citation
- 831-1.0065632.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065632/manifest