The Open Collections website will be unavailable July 27 from 2100-2200 PST ahead of planned usability and performance enhancements on July 28. More information here.

Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Automatic optimizer for use in optimal process controllers Whale, Kenneth George 1968

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1968_A7 W53.pdf [ 4.54MB ]
Metadata
JSON: 831-1.0103257.json
JSON-LD: 831-1.0103257-ld.json
RDF/XML (Pretty): 831-1.0103257-rdf.xml
RDF/JSON: 831-1.0103257-rdf.json
Turtle: 831-1.0103257-turtle.txt
N-Triples: 831-1.0103257-rdf-ntriples.txt
Original Record: 831-1.0103257-source.json
Full Text
831-1.0103257-fulltext.txt
Citation
831-1.0103257.ris

Full Text

AUTOMATIC OPTIMIZER- FOR OPTIMAL PROCESS CONTROLLERS by KENNETH GEORGE WHALE B.A.Sc, U n i v e r s i t y of B r i t i s h Columbia, 1966 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE i n the Department of E l e c t r i c a l Engineering We accept t h i s t h e s i s as conforming t o the required standard AN USE IN Members of the Department of E l e c t r i c a l Engineering THE UNIVERSITY OF BRITISH COLUMBIA September, 1968 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t of the requirements fo r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree that the L i b r a r y s h a l l make i t f r e e l y , a v a i l a b l e fo r re ference and Study. I f u r t h e r agree that permiss ion fo r e x t e n s i v e copying of t h i s t h e s i s fo r s c h o l a r l y purposes may be granted by, the Head of my Department or by hijs r e p r e s e n t a t i v e s . It i s understood that copying or p u b l i c a t i o n of t h i s t h e s i s fo r f i n a n c i a l gain s h a l l not be a l lowed wi thout my w r i t t e n p e r m i s s i o n . Department The U n i v e r s i t y of B r i t i s h Columbia Vancouver 8, Canada ABSTRACT The p r a c t i c a l implementation of optimal c o n t r o l systems i n l a r g e i n d u s t r i a l process a p p l i c a t i o n s has been l i m i t e d by the high costs of the required computing f a c i l i t i e s . With the recent advances i n component f a b r i c a t i o n and the r e s u l t a n t decrease i n hardware c o s t s , s p e c i a l purpose computers, u t i l i z i n g v i r t u a l l y no software at a l l , can be constructed as economical a l t e r n a t i v e s to p r e s e n t l y a v a i l a b l e g e n e r a l purpose computers f o r use i n optimal process c o n t r o l l e r s . A design f o r one such s p e c i a l purpose machine, an automatic o p t i m i z e r , i s presented i n t h i s t h e s i s . Tests conducted on a working o p t i m i z e r constructed on the b a s i s of the given design, demonstrate that i t i s s u i t a b l y f a s t and powerful f o r use i n process c o n t r o l l e r s . In a d d i t i o n , the o p t i m i z e r i s inexpensive enough to be used as part of an economical process c o n t r o l l e r . TABLE OF CONTENTS Page LIST OF ILLUSTRATIONS : i v ACKNOWLEDGEMENT v i 1 . INTRODUCTION . 1 1 . 1 The Opt imal C o n t r o l l e r Requirement 1 1 .2 The O p t i m i z a t i o n Problem 3 1.3 Survey o f A v a i l a b l e Search Techn iques 8 1 .4 P o w e l l ' s Method and a M o d i f i c a t i o n 17 2. AUTOMATIC OPTIMIZER--BASIC DESIGN 23 2 . 1 System C o n f i g u r a t i o n 23 2 . 2 The A d j u s t e r U n i t 24 2.3 The Optimum D e t e c t o r 27 3 . AUTOMATIC OPTIMIZER—COMPLETE DESIGN 30 3 . 1 The Optimum D e t e c t o r 30 3 . 2 The A d j u s t e r Un i t 37 3 . 3 The S e a r c h C o n t r o l l e r • 41 3 . 3 . 1 L i n e a r Searches 42 3 . 3 . 2 A X - C o u n t e r s and Data T r a n s f e r 45 3 . 3 - 3 Sequence C o n t r o l . 56 4. SYSTEM EVALUATION AND CONCLUSIONS 64 4 . 1 O p t i m i z e r C o n s t r u c t i o n 64 4 -2 T e s t s and R e s u l t s 67 4 .3 Summary and C o n c l u s i o n s 76 LIST OF REFERENCES 77 APPENDIX I 79 APPENDIX II 82 APPENDIX I I I 85 i i i LIST OF ILLUSTRATIONS Figure . Page 1 H i e r a r c h i c a l C o n t r o l S t r u c t u r e 2 2 Sub-optimal C o n t r o l l e r 3 3 F i n k e l ' s Method 15 4 Powell's Method—Two Dimensions 18 5 Powell's Method—Three Dimensions 18 6 P.M.A.—Two Dimensions 21 7 P.M.A.--Three Dimensions 21 8 Comparison of Powell's Method and P.M.A -. . 22 9 Automatic Optimizer 23 10 Stepping Motor Response 26 11 Analog Sampling Method 28 12 Analog Sampling C i r c u i t 28 13 A/D Tracking C i r c u i t 30 14 D/A Transfer R e l a t i o n 31 15 Tracking Waveform 32 16 Tracking C i r c u i t w i t h Detection Logic 33 17 Detector Counter Sequence 34 18 Up/Down Counter 35 19 Complete Optimum Detector 36 20 Adjuster Unit Channel 37 21 Voltage to Frequency Converter 38 22 Voltage-Frequency Transfer C h a r a c t e r i s t i c 39 23 Step Pulse L e v e l Converter 39 24 Adjuster Channel Logic 40 25 Search C o n t r o l l e r S t r u c t u r e 41 i v Figure ' Page 26 Two Dimensional Search Sequence 43 27 Three Dimensional Search Sequence 45 28 Five Dimensional A X-Counter Array . . . 46 29 Primary AX-Counter Operation 48 30 Complete A X-Counter C i r c u i t 49 31 Rate R e g i s t e r , Transfer Gates and A X-Counter ... 51 32 Sign Memory Transfer Logic . . 53 33 Transfer Control Logic 54 34 Transfer Timing Diagram • 55 35 Sequence Unit S t r u c t u r e 56 36 Ring Counter C i r c u i t 58 37 Mode Co n t r o l Logic 59 38 Five Dimensional Sequence Chart 62 39 Rate R e g i s t e r D/A Converter '. 66 40 Contours of F i r s t Test Function 68 41 Re s u l t s of F i r s t Test 69 42 Contours of Second Test Function 71 43 R e s u l t s of Second Test 72 44 Contours of Third Test Function 73 45 Re s u l t s of Third Test 75 v ACKNOWLEDGEMENT Many thanks are due to Dr. E.V. Bohn f o r h i s general guidance of the t h e s i s p r o j e c t , to Dr. E.L. Sigurdson f o r h i s numerous h e l p f u l suggestions, and to Mr. D. Holmes f o r many hours of valuable t e c h n i c a l a s s i s t a n c e i n c i r c u i t c o n s t r u c t i o n and t e s t i n g . I would a l s o l i k e to thank those f e l l o w graduate students who a s s i s t e d by proof-reading the f i n a l d r a f t of the t h e s i s . G r a t e f u l acknowledgement i s given to the N a t i o n a l Research C o u n c i l f o r a bursary' provided i n 1966, f o r a research a s s i s t a n t s h i p granted i n 1967, and f o r general p r o j e c t support under Research Grant number 67-3134. v i 1. INTRODUCTION 1.1 The Optimal C o n t r o l l e r Requirement The r a p i d mathematical development of optimal c o n t r o l theory i n recent decades has f a r outpaced i t s . p r a c t i c a l a p p l i c a t i o n to the r e a l i z a t i o n of optimal c o n t r o l systems f o r i n d u s t r i a l processes. This f a i l u r e i s due l a r g e l y to the requirement, i n r e a l i s t i c s i t u a t i o n s , of l a r g e - s c a l e general purpose computing f a c i l i t i e s f o r continuous numerical s o l u t i o n of the complex and mul t i - d i m e n s i o n a l systems of equations which are encountered. The c a p a b i l i t i e s of today's most s o p h i s t i c a t e d computers, and indeed of those proposed f o r the near f u t u r e , are se v e r e l y taxed by such a p p l i c a t i o n s . More s i g n i f i c a n t l y , the high cost of such f a c i l i t i e s , n otwithstanding the d r a s t i c r e d u c t i o n i n computer hardware costs brought about by micro-miniature i n t e g r a t e d c i r c u i t technology, has r e s t r i c t e d such i n s t a l l a t i o n s to a r e l a t i v e l y few l a r g e government or i n d u s t r i a l establishments. Recent i n v e s t i g a t i o n s ^ ^ have pointed the way toward the red u c t i o n of the obstacle posed by d i m e n s i o n a l i t y , through the decomposition of the complete o p t i m i z a t i o n problem i n t o a number of much smaller and n e a r l y independent sub-problems. A c o n t r o l h i e r a r c h y can then be constructed (Figure 1) i n which l o c a l l y independent, sub-optimal c o n t r o l l e r s are co-ordinated by one c e n t r a l computer at a sup e r v i s o r y l e v e l to achieve, as c l o s e l y as p o s s i b l e , o v e r a l l process o p t i m i z a t i o n . A h i e r a r c h i c a l s t r u c t u r e i s economically a t t r a c t i v e only i f c o s t l y general purpose computing f a c i l i t i e s can be confined to the supervisory l e v e l s , and r e l a t i v e l y inexpensive sub-optimal c o n t r o l l e r s can be provided l o c a l l y . Such c o n t r o l l e r s are not 2. p r e s e n t l y a v a i l a b l e . Optimal c o n t r o l l e r s have, however, been im-plemented (rather expensively) on general purpose h y b r i d analog and d i g i t a l computers and the nature of the computations which they must perform are w e l l e s t a b l i s h e d . SUPERVISORY COMPUTER SUB-OPTIMAL CONTROLLER SUB-OPTIMAL CONTROLLER Figure 1. H i e r a r c h i c a l C o n t r o l S t r u c t u r e S p e c i a l purpose machines are needed to replace these expensive computers at the l o c a l l e v e l , and i t was with t h i s requirement i n mind that the work of t h i s t h e s i s was i n i t i a t e d . The remaining chapters are devoted to the s p e c i f i c a t i o n , design, c o n s t r u c t i o n and ev a l u a t i o n of one of the c o n s t i t u e n t sub-assemblies, an automatic o p t i m i z e r , r e q u i r e d f o r the economical synthesis of l o c a l , sub-optimal process c o n t r o l l e r s . 3. 1. 2 The Opt i m i z a t i o n Problem A r e p r e s e n t a t i v e sub-optimal c o n t r o l l e r i s depicted i n the block diagram of Figure 2. The process model c o n s i s t s of a set of d i f f e r e n t i a l equations d e s c r i b i n g , approximately, the dynamics of the a c t u a l process. On the ba s i s of the in f o r m a t i o n contained i n the model and knowledge of the de s i r e d process output the optimal c o n t r o l problem can be formulated--normally as a two-point boundary value problem subject to the m i n i m i z a t i o n of some s c a l a r performance f u n c t i o n of the projec t e d t e r m i n a l s t a t e of the process. DISTURBANCES OUTPUT -SI-PROCESS STATE ESTIMATOR r MODEL OF PROCESS DYNAMICS PROCESS CONTROL COMPUTER -£3» AUTOMATIC OPTIMIZER FAST TIME SCALE J Figure 2. Sub-optimal C o n t r o l l e r I f the process was modelled e x a c t l y and no e x t e r n a l disturbances were present, then the boundary value problem could be solved, minimizing the performance f u n c t i o n , and the optimal 4. c o n t r o l could be c a l c u l a t e d once, and generated t h e r e a f t e r by the c o n t r o l computer; no a d d i t i o n a l blocks would be required i n the c o n t r o l l e r s t r u c t u r e . . However, because the model i s not exact and disturbances are u s u a l l y present, the optimal c o n t r o l must be c o n t i n u a l l y re-adjusted as the process proceeds. Each c o n t r o l up-dating i m p l i e s the m i n i m i z a t i o n of the performance f u n c t i o n by repeated, f a s t - t i m e s o l u t i o n of the process model equations. The time i n t e r v a l s between minimizations must ob v i o u s l y be much smaller than e i t h e r the process d u r a t i o n or the time constants a s s o c i a t e d with changes i n the process s t a t e (due to both c o n t r o l adjustments and e x t e r n a l d i s t u r b a n c e s ) . Process time constants vary widely but can f r e q u e n t l y be expressed i n terms of minutes, so that i n t e r v a l s i n the order of a few seconds between minimizations are r e a l i s t i c . The performance f u n c t i o n i s computed only at the t e r m i n a l p o i n t s of f a s t - t i m e s o l u t i o n s of d i f f e r e n t i a l equations. However, i t s d i s c r e t e nature can be concealed i f the s o l u t i o n r e p e t i t i o n r a t e i s s u f f i c i e n t l y high and the f u n c t i o n value i s held constant between computations. The f u n c t i o n may be assumed to be a c c e s s i b l e f o r measurement, but not a n a l y t i c a l l y a v a i l a b l e as a known f u n c t i o n of the parameters ( u s u a l l y i n i t i a l c o n d i t i o n s of the model equations) which can be adjusted to a c h i e v e ' i t s m i n i m i z a t i o n . The task of an automatic o p t i m i z e r between the c o n t r o l up-datings i s b a s i c a l l y one of s t a t i c o p t i m i z a t i o n , although over longer periods of time, under the i n f l u e n c e of disturbances, the optimum may d r i f t and the o v e r a l l performance of the c o n t r o l l e r 5. may thus be considered one of dynamic o p t i m i z a t i o n . Due to the wide d i f f e r e n c e i n time constants between the process and process model, however, the d e v i a t i o n from the optimum should never be l a r g e , so that i t can be assumed that the op t i m i z e r need not d i s t i n g u i s h between g l o b a l or absolute minima and r e l a t i v e minima. Although as many as f i f t y independent v a r i a b l e s are not uncommon i n p r a c t i c a l i n d u s t r i a l process c o n t r o l problems, c o n s i s t e n t with the concept of decomposition, each sub-problem can reasonably be considered to contain not more than f i v e or s i x v a r i a b l e s . I t can f u r t h e r be assumed that these v a r i a b l e s are unconstrained, since such c o n s t r a i n t s as may e x i s t can g e n e r a l l y be incorporated Into the performance f u n c t i o n i t s e l f . In summary, the automatic o p t i m i z e r i s faced w i t h the' l o c a l , unconstrained s t a t i c o p t i m i z a t i o n of a measurable, but a n a l y t i c a l l y unknown, continuous s c a l a r performance f u n c t i o n of up to f i v e or s i x independent v a r i a b l e s . H i l l - c l i m b i n g search s t r a t e g i e s f o r s t a t i c o p t i m i z a t i o n problems are w e l l developed and documented i n the l i t e r a t u r e . I t remains to choose from among them a s t r a t e g y t h a t , while being powerful enough to converge r a p i d l y and e f f e c t i v e l y f o r f i v e dimensional problems, i s s u f f i c i e n t l y simple that i t can be economically implemented i n a s p e c i a l purpose machine. Before presen t i n g i n the next s e c t i o n a n e c e s s a r i l y b r i e f survey of a v a i l a b l e techniques, the c o n d i t i o n s required f o r a f u n c t i o n to possess an optimum are given below along w i t h some appropriate n o t a t i o n s . The performance f u n c t i o n i s designated as P = P(x) where X — (X-^ , Xg > • « « x^ ) 6. and, w i t h i n a region R i n the space defined by the independent v a r i a b l e s , P i s assumed to be continuous. • A necessary c o n d i t i o n that P have an extreme at a point x* i n the region R i s that the .gradient VP, where \ dP , . . . bP V P b? 2 6 * n (1.1) evaluated at x = x*, must be zero. S u f f i c i e n t c o n d i t i o n s f o r the point x* to be a l o c a l minimum or maximum can be determined by approximating P with a Taylor s e r i e s expansion about x*. CO -P(x) 1 i=0 d 1 P(x*) \ (1.2) In the above equation d i s an operator .defined as f o l l o w s : n _ i r , n „ i . A , 1 A ( X . - X * ) b I j " ~ a. b 3 3-1 6 x 3 -I In the immediate neighbourhood of the optimum, only the f i r s t few terms of (1.2) are r e q u i r e d , reducing the approximation t o : n n n « 1 t i « i ,2„,~. P(x) = P(x*) + > bp(x*) + 1 a,a, b p( x») + ... k=l j = l J k In matrix n o t a t i o n —/-P(x') = P(x*) + a' V P + 1 a'cj a 7. where ? _ q i j = ?TP(x*) are the components of Q. Since the point x = x* was s p e c i f i e d to be an extreme, the gradient term must be zero so the equation becomes P(x) - P(x*) + 1 a' Q a (1.3) 2 The second term on the r i g h t hand side of Equation (1.3) i s a standard quadratic form and i t f o l l o w s that i f x* i s to be a minimum of P(x) then a 7Q a = P(x) - P(x*) > 0 (1.4) so that Q must be a p o s i t i v e d e f i n i t e m a t r i x . I f x* i s to be a maximum _ _ a Q a = P(x) - P(x*) < 0 (1.5 ) and Q must be a negative d e f i n i t e m a t r i x . I f Q i s s e m i - d e f i n i t e then higher order terms of the Taylor s e r i e s expansion must be examined. I t can be seen from e i t h e r (1.4) or (1.5) that a maximum can be transformed to a minimum simply by negating the performance f u n c t i o n and so no g e n e r a l i t y i s l o s t by h e r e a f t e r assuming that a l l extremes sought are minima. Consistent w i t h the previous statement (page 5) that d i s t i n c t i o n between r e l a t i v e and absolute minima need not be made, i t w i l l be assumed a l s o t h a t , w i t h i n the region of i n t e r e s t R i n the independent v a r i a b l e space, the performance f u n c t i o n i s unimodal. That i s , from any point i n the region R there should e x i s t only a s t r i c t l y f a l l i n g path on the response surface from that point to the minimum. 8. 1.3 Survey of A v a i l a b l e Search Techniques In general, a h i l l - c l i m b i n g or search technique i n a s t a t i c o p t i m i z a t i o n problem c o n s i s t s of a d j u s t i n g the values of the independent v a r i a b l e s of the f u n c t i o n under i n v e s t i g a t i o n according to some p r e - e s t a b l i s h e d s t r a t e g y and, on the b a s i s of the r e s u l t s , l o c a t i n g the point or points at which the f u n c t i o n value i s a maximum or minimum. The nature of any p a r t i c u l a r f u n c t i o n , the amount of i n f o r m a t i o n a v a i l a b l e about i t , the manner i n which the data accumulated by the search s t r a t e g y i s to be manipulated (by hand or by computer, f o r i n s t a n c e ) , and the number of dimensions or independent v a r i a b l e s i n v o l v e d , are a l l v i t a l c o n s i d e r a t i o n s i n the determination of the s u i t a b i l i t y of any p a r t i c u l a r search s t r a t e g y to the s o l u t i o n of any given o p t i m i z a t i o n problem. The more general problem of choosing a search s t r a t e g y that i s s u i t a b l e f o r a whole range of f u n c t i o n s i s n a t u r a l l y more d i f f i c u l t s t i l l . With the statement of the problem, as given i n s e c t i o n (1.2), i n mind, a survey of a v a i l a b l e methods was made, the r e s u l t s of which are summarized below. Consistent w i t h the problem of s e c t i o n (1.2), techniques are not d i s t i n g u i s h e d on the b a s i s of t h e i r a b i l i t y to d i f f e r e n t i a t e between absolute and r e l a t i v e extremes, nor on t h e i r a d a p t a b i l i t y to problems i n which c o n s t r a i n t s of various forms are imposed on the independent v a r i a b l e s . The search techniques to be considered can b e ; c o n v e n i e n t l y c l a s s i f i e d i n t o two general c a t e g o r i e s — d i r e c t methods and gradient methods. Although such a d i s t i n c t i o n appears somewhat a r t i f i c i a l 9. i n a few cases, and, indeed, a d d i t i o n a l or a l t e r n a t i v e c l a s s i f i c a t i o n s are c e r t a i n l y p o s s i b l e , t h i s one, wit h some f l e x i b i l i t y , serves as a simple but u s e f u l guide. D i r e c t search methods are c h a r a c t e r i z e d by r e q u i r i n g nothing more of a performance f u n c t i o n than i t s value at a number, f r e q u e n t l y l a r g e , of points i n the space of its-independent (2) v a r i a b l e s . Included are a v a r i e t y of "random search" techniques f o ) the s o - c a l l e d " f a c t o r i a l method"^' described by Box, Wilde's " l a t t i c e t e c h n i q u e " ^ ^ , and the "pattern search" developed by Hooke and Jeeves. There are, of course, many others and many v a r i a t i o n s of those mentioned, but most (with the notable exception of random searches) are subject to f a i l u r e when a p p l i e d to performance f u n c t i o n s whose response surfaces contain ridges or v a l l e y s . Thus, although i n general d i r e c t search methods do have the advantage of s i m p l i c i t y , they are a l s o f r e q u e n t l y extremely i n e f f i c i e n t , even on simple f u n c t i o n s . Gradient search techniques, as the name suggests, make use of in f o r m a t i o n about the slope of the performance f u n c t i o n response surface to determine the d i r e c t i o n i n which to conduct experiments on i t . This i n f o r m a t i o n i s contained i n the "gradient v e c t o r " , ^ P ( x ) , of the performance f u n c t i o n where ? p ( x ) =(AL_ , .... ftp ^ Use of the gradient i m p l i e s that the component p a r t i a l d e r i v a t i v e s be c a l c u l a t e d i f P i s a n a l y t i c a l l y known, or approximated on the ba s i s of l o c a l experimentation i f t h i s i s not the case. Although not, s t r i c t l y speaking, a gradient method, the " u n i v a r i a t e " s e a r c h ^ \ which c o n s i s t s simply of searching, along 10. each of the d i r e c t i o n s of the independent v a r i a b l e axes i n succession, i s g e n e r a l l y considered with gradient methods because (7 ) of i t s close r e l a t i o n to " r e l a x a t i o n " w methods. Such methods a l s o adjust only one independent v a r i a b l e at a time, but the order i n which they are v a r i e d depends upon which component of the gradient vector i s l a r g e s t . L i k e the d i r e c t search methods, both the u n i v a r i a t e and r e l a x a t i o n techniques are fundamentally simple but r e l a t i v e l y i n e f f i c i e n t and prone to f a i l u r e i n some s i t u a t i o n s . f 3 ) Steepest descent techniques , f i r s t described by Cauchy i n 1847, have been, i n one form or another, the most widely used of a l l search s t r a t e g i e s . They are a l l based on the approximation of the performance f u n c t i o n by an n-dimensional hypersphere. Mathematically P(x) = p + c'x + 1 X 'K x . . (1.6) 2 where _ _ K = k I (1.7) and I i s the i d e n t i t y m a t r i x . D i f f e r e n t i a t i n g Equation (1.6) gives v T = c + K x (1.8) and s o l v i n g Equation (1.8) f o r x y i e l d s x = K - 1 ( "VP - C ) (1.9) S u b s t i t u t i n g two s p e c i f i c p o i n t s , x_ and x-_+_, i n t o Equation (1.9) and forming the d i f f e r e n c e , Equation (1.10) i s obtained. x i + 1 - x. = K - l ( " ^ P i + 1 - W . ) (1.10) Now, i f i t i s assumed that the point x^+-^ i s the extreme x* of the 1 1 . f u n c t i o n as approximated by Equation ( 1 . 6 ) , then V P ^ j must vanish and Equation ( 1 . 1 0 ) becomes TF-1 ( l . U ) x* - = -K S u b s t i t u t i n g Equation ( 1 . 7 ) i n t o t h i s r e s u l t gives ( 1 . 1 2 ) x* - X . = - 1 VP. 1 T T 1 Equation (1.12) s a y s , e s s e n t i a l l y , t h a t i f the approximation of P(x) can be reached by one search along the d i r e c t i o n defined by the gradient \7P^, the s o - c a l l e d steepest descent d i r e c t i o n . In most cases, of course, the approximation i s crude and the extreme found i s not the true optimum. A great many steepest descent improve the approximation by s c a l i n g the f u n c t i o n or transforming the independent v a r i a b l e s , and to compensate f o r i t s crudeness by i t e r a t i v e l y up-dating the gradient (and hence the approximation). Such methods have been found to be considerably more e f f e c t i v e than the d i r e c t search methods p r e v i o u s l y mentioned, but at the expense of the increased computational e f f o r t r e q u i r e d to c a l c u l a t e or estimate the gradient ve c t o r . As suggested, the r a t e of convergence of steepest descent methods i s h i g h l y dependent upon the nature of the response surface and tends to be very slow i n the presence of r i d g e s , and i n the immediate v i c i n i t y of the optimum. In the former case a tendency to zig-zag along the ridge i s e x h i b i t e d , w h i l e near the extreme the gradient i s very s m a l l . by a hypersphere i s accurate at the point x^, then the extreme v a r i a t i o n s ( 9 ) , ( 1 0 ) have been developed which attempt both to 12. A group of search techniques, c l o s e l y r e l a t e d to gradient methods but based on a higher order approximation to the response s u r f a c e , has been developed which e x h i b i t s much improved performance on r i d g e s , p a r t i c u l a r l y i n the neighbourhood of the optimum. The approximation, s i m i l a r i n form to that expressed i n Equation (1.6), i s P(x) = P + c'x + 1 X ' Q x (1.13) ° 2 where Q i s r e q u i r e d to be a symmetric, p o s i t i v e d e f i n i t e , n by n ma t r i x . Equation (1.13) i s the g e n e r a l i z e d n-dimensional r e p r e s e n t a t i o n of a quadratic s u r f a c e . F o l l o w i n g the same steps used to d e r i v e the steepest descent d i r e c t i o n , the equation x* - x± = -Q"1 W i (1.14) can be obtained. This equation i n d i c a t e s that from any p o i n t , x^, on a quadratic s u r f a c e , the optimum, x*, can be reached by a s i n g l e search along the d i r e c t i o n defined by Equation (1.14). For fu t u r e reference such a d i r e c t i o n w i l l be c a l l e d an "optimum d i r e c t i o n " . By twice d i f f e r e n t i a t i n g Equation (1.13), i t can be seen that the m a t r i x Q must be the s o - c a l l e d Hessian matrix whose components P q - 0 P are j u s t the second p a r t i a l d e r i v a t i v e s of P ( x ) . Thus, i f P(x) i s known a n a l y t i c a l l y then Q~l and VP^ can be c a l c u l a t e d and the requ i r e d search d i r e c t i o n determined e x a c t l y from any p o i n t . I f P(x) i s unknown then and VP. must be estimated. 1 3 . Methods based on t h i s p r i n c i p l e , g e n e r a l l y r e f e r r e d to as "Newton's"^^ methods, are s a i d to possess "quadratic convergence" since they l o c a t e the optimum of a true quadratic f u n c t i o n i n a f i n i t e number of steps. Such methods i n i t e r a t i v e form have been shown to be extremely powerful, converging e f f i c i e n t l y from poor i n i t i a l s t a r t i n g points even f o r non-quadratic response su r f a c e s . Unlike steepest descent techniques, which can be seen to be a s p e c i a l case of Newton's methods, convergence i s a c c e l e r a t e d as the optimum i s approached since a quadratic approximation becomes i n c r e a s i n g l y accurate. Ridges or v a l l e y s are a l s o t r a v e r s e d e f f i c i e n t l y . In recent years a f l u r r y of research, prompted by the • s u i t a b i l i t y of d i g i t a l computers to o p t i m i z a t i o n problems, has produced s e v e r a l new and powerful v a r i a t i o n s of the search techniques discussed to t h i s p o i n t . Two ra t h e r ingenious d i r e c t search methods, r e f e r r e d to r e s p e c t i v e l y as the "'sequential (12) (13 ) simplex" method and "Rosenbrock's" method, n e i t h e r of which have any sound t h e o r e t i c a l b a s i s apart from being systematic procedures, have shown s u r p r i s i n g l y good r e s u l t s . As w e l l , four r e l a t e d methods, "conjugate g r a d i e n t s " ^ , " d e f l e c t e d g r a d i e n t s " \ " P a r t a n " ^ ^ , and a technique which w i l l be c a l l e d -"Powell's (17) method" ;, are notable among many new s t r a t e g i e s derived from the p r i n c i p l e of Newton's method. A l l possess quadratic convergence and a l l have been demonstrated to be competent on d i f f i c u l t response surfaces up to many dimensions. The d e f l e c t e d gradient method determines an -optimum d i r e c t i o n by a c t u a l l y estimating the matrix Q of Equation (1.14). The estimate i s obtained p r o g r e s s i v e l y from a sequence of l i n e a r 14. search steps whose d i r e c t i o n s are defined by the equation d. , = x - x. = - LL . H. V P . l + l i + l i ^ 1 1 l where PL i s a matrix computed at the end of each step according to the f o l l o w i n g equations H = I o H. = H. + A. + B. ; i = 1,2,.. . l i - l l I ' ' I f the matrices A. and B. are chosen at each step to be i i A. = * i * L l — d i ^ P i B. = - H i - 1 ^ P i H i i ~~ V?. H. , V?. - i i - l I then i t can be shown that f o r a quadratic f u n c t i o n H = Q"1 ' n-1 so that d = x - x , = x-:; - x -, n n n-1 n-1 and the optimum i s l o c a t e d a f t e r n steps. The method of conjugate gradients generates an optimum d i r e c t i o n f o r a quadratic f u n c t i o n by a succession of steps based on the f o l l o w i n g i t e r a t i o n : d. = - V P. + R . d". . i = 1,2, . . .n i I r i i - l The vectors d^, again, represent d i r e c t i o n s of l i n e a r one-dimensional searches, VP. i s the gradient vector and yf2 ^ i s an 15. o r d i n a r y steepest descent d i r e c t i o n with Thereafter the constant ^ i s given by VP. n i - l For t h i s value of y6? ^ i t can be s h o w n t h a t the d i r e c t i o n d R i s an optimum d i r e c t i o n , as defined, by Equation (1.14 ) , from the p o i n t x^ ^ l o c a t e d by minimizing P(x) along the previous d i r e c t i o n d^ ^. The point x n must then be the optimum of P ( x ) . Partan (an acronym f o r p a r a l l e l tangents) and Powell's method are two d i f f e r e n t n-dimensional g e n e r a l i z a t i o n s of a (18 ) method proposed f o r two-dimensional quadratics by F i n k e l Based on the s o - c a l l e d theorem of p a r a l l e l chords, h i s technique i s i l l u s t r a t e d i n Figure 3 below. i-s- x 1 Figure 3• F i n k e l ' s Method 16. The g e n e r a l i z a t i o n s t a t e s e s s e n t i a l l y that i f the gradients at x n and on a quadratic surface are p a r a l l e l , then the optimum l i e s on the l i n e j o i n i n g the two p o i n t s . This can be r e l a t e d to Newton's method by w r i t i n g Equation (1.14) f o r the two points x^ - x* = - Q - 1 "VP-L x2 - x* = - Q"1 "vT 2 and thus x 2 - x-, = - Q"1 ( V?2 - V T i ) I f , however, a n ^ ^^1 a r e P a r a ± l e x then ~V?2 = k V P and hence x 2 - x± = - Q"1 V P 1 (k-1) (1.15) so that the d i r e c t i o n from x-, to x2 i s indeed an optimum d i r e c t i o n and must t h e r e f o r e pass through x* as w e l l . Partan l o c a t e s two such p o i n t s at which the gradients are p a r a l l e l by a sequence of l i n e a r searches i n n-dimensional space whose d i r e c t i o n s are chosen p a r a l l e l to c e r t a i n tangent planes. The number of planes to which these d i r e c t i o n s are constrained to be p a r a l l e l increases p r o g r e s s i v e l y u n t i l only one p o s s i b l e d i r e c t i o n remains and that i s shown to pass through the optimum. Powell's method accomplishes the same t h i n g by p r o g r e s s i v e l y reducing the d i m e n s i o n a l i t y of the sub-spaces i n which successive l i n e a r searches are performed. These l a s t four methods appear from the l i t e r a t u r e published to be the most g e n e r a l l y powerful techniques p r e s e n t l y a v a i l a b l e ; hence, they are the most d e s i r a b l e methods f o r s p e c i a l 17. purpose implementation. Unfortunately, they are a l s o the most, complex methods computationally, i n v o l v i n g vector and matrix manipulations of various forms. Such computations imply both memory storage and a r i t h m e t i c a l f a c i l i t i e s i n any automatic machine r e a l i z a t i o n . A more d e t a i l e d a n a l y s i s of Powell's method revealed, however, that i t could be modified s l i g h t l y so as to avoid v i r t u a l l y a l l of the computational requirements mentioned. This modified method which was adopted f o r an automatic o p t i m i z e r i s given, along w i t h the o r i g i n a l method of Powell, i n the next s e c t i o n . 1•^ Powell's Method and a M o d i f i c a t i o n In h i s 1962 paper, M.J.D. Powell presented the f o l l o w i n g a l g o r i t h m f o r the m i n i m i z a t i o n of a f u n c t i o n P(x) of n independent v a r i a b l e s . (1) From any point x-^  conduct a l i n e a r search i n the n-dimensional g r a d i e n t _ d i r e c t i o n VP_. The extreme i s l o c a t e d at x g . (2) Cpnduct a search i n the n-1 dimensional hyperplane c o n t a i n i n g Xg and orthogonal to the d i r e c t i o n Xg-x^. The new extreme i s at x^. (3) Conduct a l i n e a r search along the d i r e c t i o n x^-x^ l o c a t i n g the extreme at x^. I f P(x) i s quadratic then x^ i s the minimum sought. I f not, the algorithm must be i t e r a t e d and some c r i t e r i o n s a t i s f i e d to stop the search when i t has converged s u f f i c i e n t l y close to the minimum. Examination of step two reveals that the method i s r e c u r s i v e i n that each n-dimensional search invokes steps one, two and three f o r i t s execution. Figures 4 and 5 i l l u s t r a t e the l i n e a r search sequences i n two and three dimensions r e s p e c t i v e l y . 18. Figure 5. Powell's Method—Three Dimensions 19-The n-1 dimensional hyperplane c o n t a i n i n g and x^ must be tangent to the n-dimensional contours of the response surface at point x^, since x^ i s the minimum of P(x) In the r e s t r i c t e d , n-1 dimensional space. Hence, the n-dimensional g r a d i e n t • V P at x^ i s orthogonal to t h i s tangent plane and must t h e r e f o r e be p a r a l l e l to the gradient V P ^ at x . Equation (1.15) of s e c t i o n (1.3) showed that the l i n e j o i n i n g two such p o i nts must pass through the optimum. Except f o r the computations i n v o l v e d i n determining the gradient d i r e c t i o n f o r step one of the..algorithm, Powell's method i s w e l l s u i t e d f o r machine implementation. A m o d i f i c a t i o n i n v o l v i n g the a d d i t i o n of another step i s suggested to e l i m i n a t e these computations. The new a l g o r i t h m , designated the P.M.A. algor i t h m ( f o r Powell's Modified Algorithm) f o l l o w s : f l ) Conduct an n-1 dimensional se_arch from any point x D , l o c a t i n g the extreme at x_. (2) Conduct a l i n e a r search from x n along the d i r e c t i o n orthogonal to the n-1 dimensional hyperplane i n ( l ) , l o c a t i n g the extreme at Xg. (3 ) Conduct a search i n the n-1 dimensional hyperplane c o n t a i n i n g Xg and orthogonal to__the. d i r e c t i o n Xg-x-,, l o c a t i n g the extreme at x^ . (A) Conduct a l i n e a r search along the d i r e c t i o n x-j-x n , l o c a t i n g the extreme at x^. A new step one has been introduced to e s t a b l i s h the i n i t i a l (n-dimensional) gradient d i r e c t i o n from x n by l o c a t i n g x_ as the extreme i n an n-1 dimensional hyperplane--the gradient \7 P_ must be orthogonal to t h i s hyperplane at x n s i n c e , again, as i n step two of the o r i g i n a l a l g o r i t h m , t h i s hyperplane must be tangent to the n-dimensional contour surfaces of P(x) at x . The remaining steps of the new algorithm are i d e n t i c a l to those of the o r i g i n a l . 20. A f u r t h e r computational r e d u c t i o n can be obtained by a r b i t r a r i l y choosing n-1 co-ordinate d i r e c t i o n s to define the n-1 dimensional hyperspace of- step one. The gradient vector ^7Pj i s then constrained to be p a r a l l e l to the remaining -co-ordinate d i r e c t i o n and, conveniently, the n-1 dimensional hyperplane searched by step three of P.M.A. must be p a r a l l e l to the f i r s t one. The l i n e a r search sequences f o r the modified algorithm are shown i n Figures 6 and 7, again f o r two and three dimensions. Since only the manner of o b t a i n i n g the gradient d i r e c t i o n at x n has been a l t e r e d , i t i s to be expected that the quadratic convergence property of Powell's o r i g i n a l method should be r e t a i n e d i n t h i s modified v e r s i o n . This was indeed demonstrated to be so, as the r e s u l t s obtained by P.M.A. from d i g i t a l computer t e s t s compared favourably i n a l l cases w i t h those published by Powell i n h i s o r i g i n a l paper. The d i g i t a l computer program and a summary of the r e s u l t s i s contained i n Appendix I . A more r e v e a l i n g comparison between the two algorithms can be made on the b a s i s of the number of l i n e a r searches required f o r one i t e r a t i o n , or e q u i v a l e n t l y , to optimize a quadratic f u n c t i o n . This i n f o r m a t i o n i s shown i n Figure 8 f o r two, three, four and f i v e dimensions. The e n t r i e s i n each column are the numbers of l i n e a r searches c o n s t i t u t i n g one i t e r a t i o n of each al g o r i t h m . Figure 7. P.M.A.—Three Dimensions 22. n 2 3 4 5 Powell's method 3 5 7 . 9 M o d i f i e d method 4 10 22 46 Figure 8. Comparison of Powell's Method and P.M.A. As the t a b l e of Figure 8 c l e a r l y i n d i c a t e s , the modified algorithm e l i m i n a t e s computations at the expense of a r a t h e r l a r g e increase i n the number of l i n e a r searches. Provided, however, that the average time consumed by a l i n e a r search i s s u f f i c i e n t l y s m a l l , t h i s defect w i l l not s i g n i f i c a n t l y d e t r a c t from the performance of.the method, at l e a s t up to the required f i v e dimensions. I t i s a l s o s i g n i f i c a n t , of course, that the algorithm executes i t s search i n such a f a s h i o n that the value of the performance f u n c t i o n i s ever d i m i n i s h i n g u n t i l the optimum i s a t t a i n e d . The remaining chapters of t h i s t h e s i s are devoted to the design and e v a l u a t i o n of an- economical automatic system to implement t h i s modified v e r s i o n of Powell's search s t r a t e g y . 2. AUTOMATIC OPTIMIZER—BASIC DESIGN 23-2•1 System C o n f i g u r a t i o n A s p e c i a l purpose automatic o p t i m i z e r , designed to execute the modified form of Powell's search a l g o r i t h m , i s shown g r e a t l y s i m p l i f i e d i n the block diagram of Figure 9 below. r INTERFACE E ADJUSTER UNIT PERFORMANCE FUNCTION COMPUTER SEARCH CONTROL-LER INTERFACE OPTIMUM DETECTOR Figure 9... Automatic Optimizer The blocks outside the dotted l i n e s are e x t e r n a l to the opt i m i z e r and represent, i n some form, the performance f u n c t i o n , P(x~), which i s to be optimized. I t s output i s assumed to be an analog s i g n a l which i s r e l a t e d i n a continuous and unimodal manner to the values of i t s input s i g n a l s , x"(t). I t i s f u r t h e r assumed that the output response to an input change i s so f a s t as to appear to be instantaneous. Any s i g n a l c o n d i t i o n i n g or s c a l i n g r e q u i r e d to interconnect between the performance f u n c t i o n block 24. and the op t i m i z e r proper i s performed by the " i n t e r f a c e " b l o c k s , shown here as d i s t i n c t u n i t s ; normally they, can be considered as part of the performance f u n c t i o n block. In any event, i t w i l l be assumed throughout, the t h e s i s that the analog input to the optimum d e t e c t o r i s c h a r a c t e r i z e d by a s i g n a l to noise r a t i o . of at l e a s t s i x t y d e c i b e l s . The "optimum d e t e c t o r " continuously monitors the performance f u n c t i o n , P, and i n d i c a t e s the presence of l o c a l extremes, both minima and maxima. These i n d i c a t i o n s are i n t e r p r e t e d by the search c o n t r o l l e r which a p p r o p r i a t e l y sequences c o n t r o l s i g n a l s to the a d j u s t e r u n i t , so as to execute the d e s i r e d search a l g o r i t h m . The i t e r a t i v e nature of the search s t r a t e g y d i c t a t e s a d i g i t a l form f o r the search c o n t r o l l e r . The s t r u c t u r e s of the remaining two blocks are not so obvious, although f u n c t i o n a l l y they can be thought of, simply, as types of analog to d i g i t a l (A/D) and d i g i t a l to analog (D/A) converters.. With reference to the requirements of s e c t i o n (1.4), the next two s e c t i o n s of t h i s chapter w i l l describe the ba s i c c o n s i d e r a t i o n s i n v o l v e d i n the design of the a d j u s t e r u n i t and the optimum d e t e c t o r . 2.2 The Adjuster Unit As mentioned b r i e f l y i n s e c t i o n (2.1), the purpose of the a d j u s t e r u n i t i s to generate c o n t r o l l a b l e s i g n a l s , more s p e c i f i c a l l y v o l t a g e s , which are to be i n t e r p r e t e d by the performance f u n c t i o n block as instantaneous values of i t s independent v a r i a b l e s , x ^ ( t ) . There must thus, of course, be e x a c t l y n a d j u s t e r u n i t output s i g n a l s f o r a performance f u n c t i o n i n v o l v i n g n independent v a r i a b l e s . The manner i n which these 2 5 . s i g n a l s are to be c o n t r o l l e d i s revealed by close examination of the P.M.A. search algorithm given i n s e c t i o n (1.4) along with a b r i e f d i s c u s s i o n . Two d i s t i n c t types of searches are evident: (1) Linear searches p a r a l l e l to co-ordinate axes. (2 ) Linear searches i n a r b i t r a r y d i r e c t i o n s i n r-dimensional space; where r-S n, the number of independent v a r i a b l e s . Both types of searches imply continuous adjustment of the independent v a r i a b l e s , r e l y i n g on the optimum det e c t o r to recognize that a minimum has been l o c a t e d along a given l i n e . In a d d i t i o n , i t i s i m p l i e d that the a d j u s t e r u n i t must be capable of h o l d i n g constant any combination of these independent v a r i a b l e s , p o s s i b l y over extended time i n t e r v a l s . Searches of type one, p a r a l l e l to co-ordinate d i r e c t i o n s , can be r e a l i z e d merely by a d j u s t i n g one output s i g n a l at a "time, h o l d i n g the remainder constant, The f a s t e r the r a t e of change of the adjusted v a r i a b l e , the f a s t e r w i l l be the convergence to a minimum, assuming no l i m i t a t i o n s on e i t h e r the performance f u n c t i o n computer or the optimum d e t e c t o r . Searches of the second type may be implemented by simultaneously v a r y i n g r of the a d j u s t e r u n i t outputs at r dx independent r a t e s , i . The r e s u l t a n t search d i r e c t i o n i n r d t dx ' dimensional space then depends only on the r a t i o s of the I , dt and at no time i s i t necessary that the absolute values of any of the independent v a r i a b l e s be known. This i s s i g n i f i c a n t i n that the a d j u s t e r u n i t need not be capable of p r e c i s e l y s e t t i n g i t s output voltage l e v e l s , but only of a d j u s t i n g them. Although s e v e r a l analog a d j u s t e r u n i t . s t r u c t u r e s were considered (various forms of ramp generators and o p e r a t i o n a l a m p l i f i e r i n t e g r a t o r s ) , i t was decided to use d i g i t a l stepping 2 6 . motors f o r reasons of r e l i a b i l i t y , s t a b i l i t y and ease of i n t e r c o n n e c t i o n with the d i g i t a l search c o n t r o l l e r . A v a i l a b l e i n s e v e r a l types and s i z e s , both u n i d i r e c t i o n a l and b i d i r e c t i o n a l , and complete with custom matched e l e c t r o n i c d r i v e r c i r c u i t s , a l l stepping motors are c h a r a c t e r i z e d by an incremental response e x h i b i t i n g one-to-one correspondence between d i g i t a l input pulses and r o t o r angular p o s i t i o n , as shown i n Figure 10. ROTOR STEP ^ PULSES. Figure 10. Stepping Motor Response t Although much f a s t e r motors can be obtained f o r s p e c i a l i z e d a p p l i c a t i o n s , stepping r a t e s are normally l i m i t e d to about 800 to 1000 steps per second. S p e c i f i e d angular step a c c u r a c i e s a l s o vary considerably; however, such p o s i t i o n a l e r r o r s as do occur are non-cumulative, by v i r t u e of the motor design, whereby s t a b l e r o t o r p o s i t i o n s are f i x e d r e l a t i v e to the s t a t o r . A system of such stepping motors, one f o r each independent v a r i a b l e , d r i v i n g potentiometers through s u i t a b l e gear r a t i o s was adopted f o r the a d j u s t e r u n i t . Step pulses are 27. obtained from v a r i a b l e frequency pulse generators, and, although adjustment of the outputs from the potentiometers i s n e c e s s a r i l y i n d i s c r e t e amounts because of the d i g i t a l nature of the motors, the choice of gear r a t i o s and frequency range are such that continuous l i n e a r searches can be c l o s e l y approximated. Search speed i s l e s s than that which could be achieved using completely e l e c t r o n i c c i r c u i t r y , but i t i s f e l t to be s u f f i c i e n t f o r the r e l a t i v e l y slow processes to be encountered i n most i n d u s t r i a l o p t i m i z a t i o n problems. 2.3 The Optimum Detector The f u n c t i o n of the optimum d e t e c t o r c o n s i s t s of monitoring the performance f u n c t i o n as the a d j u s t e r u n i t conducts a l i n e a r search i n the space of i t s independent v a r i a b l e s , and i n d i c a t i n g immediately that a minimum along that l i n e i s reached. The s e n s i t i v i t y and response time of t h i s u n i t d i r e c t l y i n f l u e n c e s both the p r e c i s i o n with which the steps of the search a l g o r i t h m can be executed and the f i n a l r e s o l u t i o n to which the minimum can be l o c a t e d . There are three c o n c e p t u a l l y simple methods of d e t e c t i n g the extreme of a continuously v a r y i n g analog s i g n a l , employing e i t h e r d i r e c t d i f f e r e n t i a t i o n , analog sampling, or analog to d i g i t a l conversion. The f i r s t method i s c l e a r l y u n s u i t a b l e f o r the slow l y changing s i g n a l s expected, due to the i n h e r e n t l y poor low frequency response of d i f f e r e n t i a t i n g c i r c u i t s . The second method i n v o l v e s the c o n t i n u a l comparison of the analog s i g n a l value, P, wi t h a time delayed sample of i t s e l f , 28. P . When the d i f f e r e n c e s i g n a l , D = P - P , changes s i g n , the s s presence of an extreme i s i n d i c a t e d . P ( t ) , P g ( t ) Figure 11. Analog Sampling Method The p r e c i s i o n to which the extreme i s l o c a t e d can be made independent of the sampling " r a t e " by using a system c o n f i g u r a t i o n as shown i n Figure 12 below. Figure 12. Analog Sampling C i r c u i t 29. Here, samples are taken only a f t e r the analog input has changed by some small f i x e d amount. The two comparators CI and C2 are connected, so that increments of e i t h e r p o l a r i t y i n P may be detected. The t h i r d method c o n s i s t s of converting the analog input to a d i g i t a l equivalent and performing some so r t of manipulations on the d i g i t a l s i g n a l to determing at what point an extreme i s reached. The number of b i n a r y " b i t s " used t o d i g i t a l l y approximate the analog s i g n a l i s the primary l i m i t a t i o n on the achievable d e t e c t o r p r e c i s i o n . Although such techniques are g e n e r a l l y comparatively c o s t l y , the A/D conversion method was chosen f o r implementation i n favour of analog sampling because of the higher inherent . s t a b i l i t y , r e l i a b i l i t y , and noise immunity of d i g i t a l c i r c u i t r y . A complete d i s c u s s i o n of the design used i s given i n the next chapter. 30o 3. AUTOMATIC OPTIMIZER—COMPLETE DESIGN 3.1 The Optimum Detector A d i g i t a l optimum dete c t o r was b u i l t around the p r i n c i p l e of A/D conversion, using the t r a c k i n g c i r c u i t shown below. P( t ) D/A CONVERTER U/D COUNTER (N BITS) Figure 13. A/D Tracking C i r c u i t An up/down r e v e r s i b l e b i n a r y counter s u p p l i e d by uni n t e r r u p t e d pulses from a f i x e d frequency ( f c ) clock i s d i r e c t e d by the comparator, CI, to count up or down according to the d i f f e r e n c e between the analog i n p u t s , P ( t ) and V ( t ) , to the comparator. P ( t ) represents the value of the performance f u n c t i o n P ( x ( t ) ) , and V ( t ) i s the continuous analog conversion of the binary number, C^, i n the counter. The comparator i s connected i n such a way that V ( t ) provides negative feedback, f o r c i n g the counter 31. always to count i n the d i r e c t i o n that tends to reduce the d i f f e r e n c e P ( t ) - V ( t ) . V ( t ) and the equivalent b i n a r y number, C^, thus continuously t r a c k the i n p u t , P ( t ) . The number, N, of b i t s i n the up/down counter, the clock frequency, f , the s e n s i t i v i t y and speed of the comparator, and the D/A converter t r a n s f e r r e l a t i o n , (Figure 1 4 ) , are a l l important f a c t o r s governing the permissable range of the input P ( t ) , both i n terms of frequency and voltage magnitude. Of these f a c t o r s , only the comparator c h a r a c t e r i s t i c s are f i x e d (by a choice of comparator), and the remainder can be adjusted to give any d e s i r e d , p r a c t i c a l performance. V(t) 2 N- 1 Figure 14. D/A Transfer R e l a t i o n to be By choosing the D/A converter output step s i z e , Vg x, V S T > 2V D where i s the comparator window, the t r a c k i n g s i g n a l , V ( t ) f o r a constant input P ( t ) = C, can be made to resemble the waveform of Figure 15. 32. P ( t ) , V ( t ) *VD C t .Figure 15, Tracking Waveform V can be r e l a t e d to the length of the counter by the ST f o l l o w i n g equations; and V V. ST R 2 -1 (3-D where V^ i s the maximum D/A output voltage (and hence a l s o the maximum input s i g n a l v o l t a g e ) . The p r e c i s i o n w i t h \vhich P ( t ) can be tracked i s thus d i r e c t l y p r o p o r t i o n a l to the len g t h , N, of the up/down counter. This counter length can a l s o be r e l a t e d to the maximum ra t e of change of P ( t ) , (the s o - c a l l e d "slewing r a t e " ) , which can be followed by V ( t ) . I f AT i s the t o t a l time r e q u i r e d to count from C N = 0 to = 2^  - 1, then ob v i o u s l y AT = ,N seconds f o r a clock frequency, f . The maximum slewing r a t e of V ( t ) must then be q _ Vp f Sy = R C 2 N - 1 v o l t s second (3.2) and S must a l s o correspond to the maximum input slewing r a t e that can be handled by the optimum d e t e c t o r . The t r a c k i n g system of Figure 13 does not i n i t s e l f c o n s t i t u t e an A/L converter. A d d i t i o n a l c i r c u i t r y i s g e n e r a l l y i n c l u d e d to make CL. a c c e s s i b l e and to r e l a t e i t i n s i g n and N magnitude to the input s i g n a l P ( t ) . Since the search algorithm of s e c t i o n ( 1 . 4 ) does not r e q u i r e e x p l i c i t l y the value of P(t)-, t h i s c i r c u i t r y was omitted, and l o g i c was developed, i n s t e a d , f o r l o c a t i n g the extremes of P ( t ) . A diagram of the system, showing the extreme d e t e c t i o n c i r c u i t r y , i s given i n Figure 16. Another up/down counter (the d e t e c t o r counter), d r i v e n i n p a r a l l e l with the o r i g i n a l ( t r a c k i n g ) counter and i d e n t i c a l to i t except i n l e n g t h , has been added. P ( t ) o D/A CONVERTER JL_L TRACKING U/D COUNTER (N BITS) DETECTOR U/D COUNTER DOWN UP O.S. Figure 16. Tracking C i r c u i t with Detection Logic 34 The l o g i c a l sequence t a b l e (Figure 17) f o r t h i s new counter i l l u s t r a t e s the p r i n c i p l e used, assuming i t s length t o be four b i t s (M = 4). The most s i g n i f i c a n t b i t s are shown on the r i g h t . i 0 1 1 0 1 0 1 0 Count 0 0 1 o| up 1 1 0 0 0 1 0 0 1 0 0 0 st a t e - 0 0 0 o 1 1 1 1 Count 0 1 1 1 down 1 0 1 1 0 0 1 1 1 o 1 1 0 1 0 1 Detect 10 f o r i n c r e a s i n g P Detect 01 f o r decreasing P. Figure 17. Detector Counter Sequence C l e a r l y , i f the dete c t o r counter i s i n i t i a l l y r e s et to zero, then monitoring the two right-most b i t combinations, 10 and 01, i s s u f f i c i e n t to determine whether P ( t ) i s l o c a l l y i n c r e a s i n g or decreasing. ( A c t u a l l y , i n order f o r d e t e c t i o n symmetry w i t h i n c r e a s i n g or decreasing P ( t ) , the combination 1A 10 must be detected on the up count and AX01 on the down count.) In Figure 16 t h i s i s done by gates Gl and G2 i n conju n c t i o n , r e s p e c t i v e l y , w i t h the up and down one-shots. The p r e c i s i o n w i t h which changes i n P ( t ) can be detected by t h i s method i s p r i m a r i l y dependent on the length of the d e t e c t o r counter. A s o r t of q u a l i t y f i g u r e f o r the optimum det e c t o r can a c c o r d i n g l y be defined as E(M,N), where E(M,N) = A C M X 100% 2 N - 1 (3.3) and A i s the number of counts i n the detec t o r counter (and hence a l s o i n the t r a c k i n g counter) r e q u i r e d to generate a d e t e c t i o n pulse. E(M,N) thus i n d i c a t e s the achievable d e t e c t i o n p r e c i s i o n as a percentage of the allow a b l e range of the i n p u t P ( t ) . A t h e o r e t i c a l lower l i m i t of three counts f o r AC^, corresponding to M = 3, i s imposed by the n a t u r a l t r a c k i n g o s c i l l a t i o n of V ( t ) , as i l l u s t r a t e d i n Figure 15. A complete optimum de t e c t o r designed and constructed on the b a s i s of the foregoing c o n s i d e r a t i o n s i s shown i n Figure 19. Some a d d i t i o n a l c o n t r o l c i r c u i t r y (U/D c o n t r o l f l i p - f l o p and strobe pulse) i s in c l u d e d to avoid p o s s i b l e l o g i c a l hazards both i n counting and i n generation of dete c t o r p u l s e s . A standard up/down counter c i r c u i t , given i n Figure 18, was used. RESET CLOCK PULSES ©. Figure 18. Up/Down Counter 4.7K AMPLIFIER /4A702 1.5K - v V v V - j . 10K D'/A CONVERTER 1 '"^v\AAA~^ V BUFFERS DOWN O [STROBE: o.s. 470JI L V W \ A -P(t )470il e-VVV\A-INPUT CLOCK < fc) UP TRACKING U/D COUNTER DETECTOR U/D COUNTER RESET (I) DOWN UP O.S. o.s. /XA710 COMPARATOR TO SEARCH CONTROLLER Figure 19. Complete Optimum Detector 37. 3•2 The Adjuster Unit The complete a d j u s t e r u n i t c o n s i s t s of n stepping motor-potentiometer combinations, as discussed i n s e c t i o n (2.2). Each potentiometer, motor, and the ass o c i a t e d d r i v i n g c i r c u i t r y i s designated as an a d j u s t e r u n i t "channel", and i s represented by the s i m p l i f i e d block diagram below. STEP PULSE SOURCE Figure 20. Adjuster Unit Channel A voltage to frequency (V/F) converter i s used to generate the step pulses r e q u i r e d to actuate the motors. I t s output pulse r e p e t i t i o n r a t e i s d i r e c t l y p r o p o r t i o n a l to the analog voltage a p p l i e d to i t s input t e r m i n a l f • = K V o p i The c i r c u i t u s e d ^ 9 ) , a v a r i a t i o n of the standard u n i j u n c t i o n t r a n s i s t o r r e l a x a t i o n o s c i l l a t o r , i s shown i n Figure 21. A voltage versus frequency t r a n s f e r c h a r a c t e r i s t i c , given i n Figure 22, was obtained f o r the c i r c u i t , r e v e a l i n g that i t i s e s s e n t i a l l y l i n e a r over the frequency range from zero to about one thousand h e r t z , which covers the e n t i r e working range of the stepping motors. The output pulses are s u i t a b l e f o r d i r e c t input to the m i c r o - l o g i c gates of the channel c o n t r o l l o g i c s e c t i o n . Figure 21. Voltage to Frequency Converter Analog input to the V/F converter i s obtained from the search c o n t r o l l e r from a D/A converter connected to the bu f f e r e d outputs of a d i g i t a l r a t e r e g i s t e r whose contents, C R, can be a l t e r e d by the search c o n t r o l l e r . The step pulse frequency can hence be expressed as f = K K , C . ( 3 . 4 ) o p d R where K, i s a gain constant a s s o c i a t e d with the D/A converter. 39. Figure 22. Voltage-Frequency Transfer C h a r a c t e r i s t i c A complete diagram of O n e a d j u s t e r u n i t channel i s given i n Figure 24. Channel c o n t r o l l o g i c i s enclosed by dotted l i n e s . Depending on the s t a t e of the si g n f l i p - f l o p , step pulses from the V/F converter are routed, through l e v e l conversion (L/C) c i r c u i t s , (Figure 23), to e i t h e r the clockwise or counterclockwise input, t e r m i n a l s of the motor c o n t r o l l e r s . Enable and i n h i b i t l i n e s are a l s o a v a i l a b l e , p e r m i t t i n g the step pulses to be passed to.the motors, or blocked, i n a v a r i e t y of ways. +20v -20v -20v ' Figure 23. Step Pulse Level Converter 40. STEP MOTOR ¥ CO OTOR NTROLLER STEP INHIBIT rO V/F CONVER-TER 1 1111111111 CHANNEL CONTROL LOGIC 1 D/A CONVERTER BUFFERS RATE REGISTER Figure 24. Adjuster Channel Logic 41. 3.3- The Search C o n t r o l l e r The search c o n t r o l l e r must, i n response to the pulses received from the optimum d e t e c t o r , co-ordinate stepping of the ad j u s t e r u n i t motors, so as to perform l i n e a r searches i n the sequence p r e s c r i b e d by the P.M.A. search s t r a t e g y of s e c t i o n ( 1 . 4 ) . A block diagram of the search c o n t r o l l e r i s given i n Figure 25 below. AX-COUNTERS TRANSFER GATES I I I I I RATE REGISTERS BUFFERS D/A CONVERTERS . U 4 4 ADJUSTER UNIT TRANSFER CONTROL LOGIC 1 SEQUENCE UNIT OPTIMUM DETECTOR 7 T V V 1 MODE. CONTROL LOGIC | SJ^ARfJiH CONTROLLER _ J Figure 25. Search C o n t r o l l e r S t r u c t u r e Before d i s c u s s i n g i n d e t a i l the s t r u c t u r e of the various u n i t s shown i n Figure 25, a few poi n t s regarding the execution of these l i n e a r searches must be elaborated. 42. 3.3.1. Li n e a r Searches Any s p e c i f i e d l i n e a r search may begin, from a given point i n space, i n e i t h e r of two opposing d i r e c t i o n s . Unless the point i s i n f a c t the l o c a l extreme being sought, proceeding i n one of these d i r e c t i o n s w i l l improve the performance f u n c t i o n , while proceeding i n the other d i r e c t i o n w i l l cause i t to d e t e r i o r a t e . Since no a p r i o r i i n f o r m a t i o n i s a v a i l a b l e to d i s t i n g u i s h between these d i r e c t i o n s , the one that i s fav o r a b l e can only be determined by an experimental search i n e i t h e r one or the other of the two d i r e c t i o n s . For t h i s purpose a p r e l i m i n a r y experimental search can be accommodated as the f i r s t mode (Sign Test mode) of a standardized, two mode form of l i n e a r search. The second mode (Step mode), the search proper, then continues i n the same d i r e c t i o n , or reverses, •: depending upon the success or f a i l u r e of the p r e l i m i n a r y search. In a d d i t i o n to l o g i c a l l y s u p e r v i s i n g these two modes, the search c o n t r o l l e r must a l s o s p e c i f y f o r the a d j u s t e r u n i t the o r i e n t a t i o n i n r-dimensional space of the l i n e along which the search i s to be executed. The o r i e n t a t i o n i s , of course, obvious f o r type one l i n e a r searches, f o r which only one motor i s Involved. For searches of type two, as was stated i n s e c t i o n (2.2) and as i s i l l u s t r a t e d below f o r r equal to two, the o r i e n t a t i o n i s defined by the incremental changes accrued during previous type one searches i n each of the r independent v a r i a b l e s . 43. x i F igure 26. Two Dimensional Search Sequence For i n s t a n c e , the l i n e from point x to point x i n 2 4 Figure 26 i s e s t a b l i s h e d by the previous increments A x l and Ax2 (stages I I I and I I , r e s p e c t i v e l y ) according to the r e l a t i o n tan 6 Ax2 A x l These increments are not known d i r e c t l y , but t h e i r r a t i o can be determined r e a d i l y by counting the numbers, n and n , of pulses s u p p l i e d to the r e s p e c t i v e stepping motors, since A x2 = n s2 A x l n s i By l o a d i n g these pulse counts ( A x - c o u n t s ) i n t o the appropriate channel r a t e r e g i s t e r s at stage IV of the search i n Figure 26, i t f o l l o w s from Equation (3 -.4), s e c t i o n (3.2), t h a t , f o r the ensuing stage V search f o2 "ol n n s2 s i ( 3 . 5 ) • 44 c o n s t r a i n i n g i t to proceed along the l i n e j o i n i n g x^ and x , from x^ to the minimum at x . s> 4 C l e a r l y , the angular r e s o l u t i o n between adjacent search d i r e c t i o n s i s d i r e c t l y r e l a t e d to the p r e c i s i o n w i t h which the r a t i o expressed by Equation ( 3 * 5 ) can be define d ; and t h i s , i n t u r n , depends upon the number of b i t s , R, chosen f o r the r a t e r e g i s t e r . The minimum angle, H . , must be 9 • = t a n - 1 1 (3 2 R - 1 Values of R i n the range of eight to ten b i t s are f e l t t o provide, i n general, adequate angular r e s o l u t i o n . With reference once more to Figure 26, i t i s e s s e n t i a l f o r r a p i d convergence of the search toward the optimum, that the stepping motors should run at or near maximum ra t e f o r a l l stages of the search. This requirement i s r e a d i l y met f o r search stages I , I I , and I I I , where only one motor i s running at a time, by s e t t i n g the appropriate r a t e r e g i s t e r s f o r maximum V/F converter output r a t e s . Although not as e a s i l y done f o r searches of type two, since the motor speeds are set by the various pulse counts loaded i n t o the rat e r e g i s t e r s at stage IV, search speed can s t i l l be maintained near maximum by simultaneously s h i f t i n g the contents of a l l r e g i s t e r s toward t h e i r most s i g n i f i c a n t ends. Such s h i f t i n g r e s u l t s i n a simple b i n a r y s c a l i n g of the t r a n s f e r r e d pulse counts, l e a v i n g t h e i r r a t i o s unchanged, yet f o r c i n g at l e a s t one motor channel to operate close to top speed. 3.3.2 AX--Counters and Data Transfer 45. To i l l u s t r a t e c l e a r l y the requirements of the Ax-counters i n v o l v e d i n e s t a b l i s h i n g the d i r e c t i o n s of type two l i n e a r searches, the three dimensional search sequence of Figure 7 i s repeated below, with a l l p o i n t s and a l l p e r t i n e n t Ax increments l a b e l l e d . 2 23 x-8 y § . — • • x12 10 Figure 27. Three Dimensional Search Sequence Three type two l i n e a r searches are shown. Two of these, from p o i n t s four to f i v e and nine to ten, i n v o l v e only two dimensions (or v a r i a b l e s ) , while the t h i r d , from p o i n t s ten to eleven, i n v o l v e s a l l three. A double s u b s c r i p t n o t a t i o n i s used f o r the r e l a t e d A x increments, the f i r s t s u b s c r i p t r e f e r r i n g to the v a r i a b l e i n v o l v e d , and the second to the d i m e n s i o n a l i t y of the type two search f o r which the increment a p p l i e s . For example, A x ^ designates an increment i n the v a r i a b l e x , while A x denotes an increment i n the same 1 13 v a r i a b l e but r e l a t e d to a type two search i n three dimensions. From Figure 27, i t i s c l e a r that there i s some overlapping of the increments r e q u i r e d f o r the two and three dimensional type two searches. This overlapping n e c e s s i t a t e s the use of two Ax-counters to de f i n e the two dimensional type two search d i r e c t i o n s , and an a d d i t i o n a l three Ax-counters to de f i n e the three dimensional search d i r e c t i o n . For higher dimensions the extension i s expressed by the r e c u r s i o n equations and K = N + K N N-1 K 2 " 2 where K i s the t o t a l number of Ax-counters r e q u i r e d f o r a N • . search i n N dimensions. An array of fourteen counters as re q u i r e d f o r f i v e dimensions i s shown i n Figure 28. x l 2 x22 xl 3 x23 x33 x l 4 x24 x34 x44 x l 5 x25 x35 x45 x55 Transfer Gates Transfer Gates Transfer Gates Transfer Gates Transfer Gates Rate R e g i s t e r Rate R e g i s t e r Rate R e g i s t e r Rate R e g i s t e r Rate R e g i s t e r Figure 28. Five Dimensional AX-Counter Array The n o t a t i o n f o l l o w s that introduced f o r the three dimensions of Figure 21. The counters of each column are associated with the same v a r i a b l e . Those of each row correspond to a type two search of a given dimension, and only when Ax-counts have been obtained f o r a l l counters i n that row i s the type two search d e f i n e d . Then, i n order f o r i t to be executed, the e n t i r e row of Ax-counts must be t r a n s f e r r e d i n t o the appropriate r a t e r e g i s t e r s which are shown below each column. As can be seen f o r A x , A x and A x i n 12' 22 33 Figure 27, the shaded counters of Figure 28 are d i s t i n g u i s h e d from the r e s t i n that t h e i r pulse counts are always a t t a i n e d over only one l i n e a r search, while the others i n v o l v e s e v e r a l s e q u e n t i a l searches. The shaded counters are designated ( a r b i t r a r i l y ) as primary counters, and the others as secondary counters. Only the magnitude of any primary Ax-count i s r e q u i r e d , since the s t a t e of the corresponding a d j u s t e r channel s i g n f l i p - f l o p must, at the end of the type one search which produced the Ax-increment concerned, already represent the c o r r e c t i n i t i a l p o l a r i t y f o r that channel f o r the ensuing type two search. The secondary counters, however, must count through a number of l i n e a r searches, and hence a succession of Sign Test and Step modes, and must t h e r e f o r e record not only the c o r r e c t Ax-count, but i t s net p o l a r i t y as w e l l . Both primary and secondary counters use the same bas up/down counter complete with U/D c o n t r o l and strobe pulse c i r c u i t r y that was described f o r the optimum detector counters The primary counters r e q u i r e up/down c a p a b i l i t y i n order to c o r r e c t l y d.etermine the Ax-count i n s i t u a t i o n s f o r which the p r e l i m i n a r y Sign Test mode r e s u l t s i n a motor r e v e r s a l . Such a s i t u a t i o n i s depicted i n Figure 29. x c ( 0 ) : A X x ( t 3 ) A x COUNT Figure 29. Primary AX-Counter Operation Secondary counters r e q u i r e up/down c a p a b i l i t y to account f o r a p o s s i b l e succession of such motor r e v e r s a l s . The complete Ax-counter, c i r c u i t r y i s given i n Figure 30. C i r c u i t connections shown boldface are used by the primary counters, those shown dotted by the secondary counters FADJUSTER UNIT 3[-o SIGN INITIALIZE (1) STEP . PULSES J J PS S SIGN T F.F. PC R SIGN REVERSE COUNTER RESET AX-COUNTER SIGN H* INITIALIZE J ( 1 ) Figure 30. Complete AX-Counter C i r c u i t • 50. and the r e s t are common to both. A f u l l counter length AND gate i s provided to dete c t , i n con j u n c t i o n with the zero one-shot, the t r a n s i t i o n of the counter i n t o the reset (zero) s t a t e , and to a c c o r d i n g l y reverse the counting d i r e c t i o n ( r e f e r to Figure 29). A sig n memory (SM) f l i p - f l o p i s provided f o r each secondary counter to record the net p o l a r i t y of any Ax-increment. I t must f i r s t be " i n i t i a l i z e d " , along with the corresponding s i g n f l i p - f l o p . I t then r e c e i v e s the same s i g n r e v e r s a l pulses a p p l i e d to the s i g n f l i p - f l o p u n t i l the Ax-count begins, after, which i t i s reversed only by pulses from the zero one-shot. The SM f l i p - f l o p s t a t e at the co n c l u s i o n of the Ax-counts must thus represent the net sig n a s s o c i a t e d with the Ax-increment. Immediately f o l l o w i n g the accumulation of a l l the Ax-counts f o r any one l e v e l of the counter a r r a y of Figure 28, and before the a s s o c i a t e d type two l i n e a r search can be executed, t h i s - d a t a must be t r a n s f e r r e d i n t o the ra t e r e g i s t e r s which d r i v e , through D/A converters, the V/? converters of the corresponding a d j u s t e r channels. To avoid the much increased c i r c u i t complexity f o r the Ax-counters that would be r e q u i r e d to enable them to s h i f t i n a d d i t i o n to counting up and down, i t was decided to perform the t r a n s f e r i n p a r a l l e l r a t h e r than s e r i a l l y . One r a t e r e g i s t e r , the a s s o c i a t e d p a r a l l e l t r a n s f e r gates and one of the up to four p o s s i b l e Ax-counters from which the r a t e r e g i s t e r may be loaded, are depicted i n Figure 3 1 . Figure 31- Rate R e g i s t e r , Transfer Gates and AX-Counter 52. A complete t r a n s f e r i s executed i n two stages-~a p a r a l l e l t r a n s f e r from the .Ax-counters i n t o the r a t e r e g i s t e r s followed by a s e r i a l s h i f t i n the ra t e r e g i s t e r s . The s h i f t i s toward the most s i g n i f i c a n t ends of a l l r a t e r e g i s t e r s , and ensures that at l e a s t one a d j u s t e r channel w i l l operate close to maximum r a t e i n the subsequent type two l i n e a r search. In order f o r a p a r a l l e l t r a n s f e r to occur, i t i s necessary that a l l r a t e r e g i s t e r s i n v o l v e d have p r e v i o u s l y been r e s e t , and that l o g i c a l one l e v e l s are present on both the t r a n s f e r enable and s h i f t enable l i n e s . This being the case, a p o s i t i v e pulse a p p l i e d at the t r a n s f e r pulse input w i l l be t r a n s m i t t e d through the gates to the toggle i n p u t s of those r a t e r e g i s t e r f l i p - f l o p s f o r which the corresponding Ax-counter f l i p - f l o p s contain l o g i c a l zeros. The Ax-counts are thus t r a n s f e r r e d i n complement form to the r a t e r e g i s t e r s . I n v e r t i n g b u f f e r s on the r a t e r e g i s t e r f l i p - f l o p s , however, provide the t r a n s f e r r e d Ax-counts i n uncomplemented form to the D/A converters. Transfer of SM data to the s i g n f l i p - f l o p s i s complicated by the f a c t that other l e v e l s of Ax-counters may be monitoring the s t a t e of the si g n f l i p - f l o p s f o r which the SM data are de s t i n e d . This precludes the required i n i t i a l p r e - c l e a r i n g of the s i g n f l i p - f l o p s , s ince the counters, which monitor the f l i p - f l o p toggle inputs (Figure 30), would be d i s r u p t e d . To circumvent t h i s problem, the SM data p a r a l l e l t r a n s f e r i s executed i n two steps, from the SM f l i p - f l o p to an extra s c r a t c h pad (SP) f l i p - f l o p , and from there to the sign f l i p - f l o p . The req u i r e d c i r c u i t r y i s shown i n Figure 32. FROM SM F.F.»S Figure 32. Sign Memory Transfer Logic The SP f l i p - f l o p can be pre-cleared so that the f i r s t step can be executed using s i m i l a r t r a n s f e r gates and the same t r a n s f e r pulse as used f o r t r a n s f e r of the Ax-counts. The second step uses an a d d i t i o n a l pulse to toggle the sig n f l i p - f l o p whenever i t s s t a t e and that of the SP f l i p - f l o p d i f f e r . F o l l o w i n g the p a r a l l e l t.ransfer stage, a l o g i c a l zero appears on the s h i f t enable l i n e , and the r a t e r e g i s t e r s h i f t begins. I t continues u n t i l the most s i g n i f i c a n t b i t s of at l e a s t one of the t r a n s f e r r e d Ax-counts occupies the most s i g n i f i c a n t b i t p o s i t i o n of i t s rate r e g i s t e r . 54. Transfer c o n t r o l l o g i c which supervises a l l phases of the above p a r a l l e l and s h i f t stages i s shown i n Figure 33. A t r a n s f e r i s i n i t i a t e d by a l o g i c a l zero to one l e v e l s h i f t on the t r a n s f e r s t a r t l i n e . S everal delays are i n s e r t e d to ensure quiescent c o n d i t i o n s immediately before both the p a r a l l e l t r a n s f e r and s e r i a l s h i f t stages. f l t SHIFT PULSES n TC <£-J I— Q TRAN o . SHIFT COMPLETE (0) _ TRANSFER c M c PULSE LINE SHIFT TRANS-O.S. >— FER O.S. TRANSFER START LINE ( l ) CLOCK QSH PS SHIFT PC F.Fo DELAY O.S. Figure 33. Transfer C o n t r o l Logic F o l l o w i n g completion of the s h i f t stage, a t r a n s f e r complete s i g n a l i s generated to i n d i c a t e that the appropriate type two search may commence. 55. A t i m i n g diagram i s provided i n Figure 34, i n d i c a t i n g the waveforms at pe r t i n e n t points of both the t r a n s f e r c o n t r o l l o g i c and the Ax-counter, t r a n s f e r gate, r a t e r e g i s t e r c o n f i g u r a t i o n of Figure 31. TRANSFER START DELAY ONE-SHOT TRANSFER ONE-SHOT SHIFT ONE-SHOT SHIFT FLIP-FLOP 1 1 1 1 1 1 • SHIFT CLOCK jHJTJirijTrijTm SHIFT COMPLETE 'TRANSFER COMPLETE Figure 34. Transfer Timing Diagram 56. 3.3.3 Sequence Con t r o l The bulk of the c i r c u i t r y r e q u i r e d f o r the automatic o p t i m i z e r has now been presented. I t remains to c o r r e c t l y sequence the s e r i e s of l i n e a r searches, Ax-counts and data t r a n s f e r s so that the steps of the P.M.A. search are executed. For t h i s purpose, a sequence u n i t was designed as the heart of the search c o n t r o l l e r . I t provides c o - o r d i n a t i o n not only among the remaining blocks of the search c o n t r o l l e r i t s e l f , but al s o between i t and both the a d j u s t e r u n i t and the optimum d e t e c t o r . The sequence u n i t c o n s i s t s of a h i e r a r c h y of s i x - b i t r i n g counters, each w i t h i t s own input l o g i c network, as depicted i n Figure 35. Q. 'M TUPM o {gs» RESET 5 LOGIC TA5 4 LOGIC TAL LOGIC rTTTTT RING COUNTER NO. 5 RING COUNTER NO. 4 rTTTTT T T T T l RING COUNTER NO. 2 -g»5>—o SEQUENCE UNIT OUTPUTS Figure 35• Sequence Unit S t r u c t u r e . 57. Each i n d i v i d u a l r i n g counter c o n s i s t s of the c i r c u i t shown i n Figure 36. Both e x t e r n a l and automatic i n t e r n a l r e s e t s are a v a i l a b l e , and access i s provided to a l l s i x f l i p - f l o p outputs, only one of which at any time may be a l o g i c a l one. Each counter thus has s i x p o s s i b l e " s t a t e s " , each of which may be entered i n sequence by t r i g g e r i n g the advance one-shot through the input l o g i c network. According to the r e c u r s i v e nature of the P.M.A0 search s t r a t e g y , f o r which a two dimensional search c o n s i s t s of a set of l i n e a r searches, a three dimensional search a set of two dimensional searches, and so on, the r i n g counter l e v e l s shown i n Figure 35 correspond i n number to the dimension of the search over which each has d i r e c t c o n t r o l . No l e v e l i s i n d i c a t e d f o r l i n e a r or one dimensional searches. Instead, they are supervised by the mode c o n t r o l l o g i c given i n Figure 37. Pulses from the optimum det e c t o r are routed e i t h e r to the a d j u s t e r channel s i g n f l i p - f l o p s f o r motor r e v e r s a l , or to the sequence u n i t input l o g i c networks f o r r i n g counter advances, depending upon the s t a t e (Sign Test or Step) of the mode f l i p - f l o p . The de t e c t o r reset f l i p - f l o p , i n a d d i t i o n to r e s e t t i n g the d e t e c t o r counter of the optimum d e t e c t o r , a l s o i n h i b i t s a l l stepping motors f o r a short time f o l l o w i n g each de t e c t o r up pulse, thereby a v o i d i n g any p o s s i b l e l o g i c a l hazards a s s o c i a t e d w i t h motor r e v e r s a l or counter advances. RESET O.S. ADVANCE O.S. ADVANCE PULSE INPUT' j Figure 3 6 . . Ring Counter C i r c u i t 59. rrrrrT RESET DETECTOR U/n COUNTER L_ DOWN O.S. SIGN REVERSE O.S. . SIGN REVERSE PULSE I TSR O PS Q D R DETECTOR RESET F.F. O DETECTOR MODE RESET O.S/ O.S. OPTIMUM DETECTOR "1 MODE CONTROL LOGIC-MOTOR INHIBIT SYSTEM RESET MODE LINE T DETECTOR UP PULSE | M I Figure 37. Mode Cont r o l Logic 6 0 . The complete sequence of optimizer events r e q u i r e d f o r a f i v e dimensional P.M.A„ search i s presented i n the chart of Figure 38. Each step of the search algorithm implementation corresponds to one of the sequence u n i t " s t a t e s " (combination of r i n g counter s t a t e s ) l i s t e d i n the le f t - m o s t column of the ch a r t . The s t a t e s must progress i n the exact sequence shown i n order to execute the de s i r e d search. The second column l i s t s those step motors i n v o l v e d i n each of the search steps. The t r a n s f e r s r e q u i r e d at various stages of the sequence are i n d i c a t e d i n the t h i r d column, according to the number of dimensions or v a r i a b l e s i n v o l v e d , and hence, according to the vari o u s l e v e l s shown i n the Ax-counter array of Figure 28. The f o u r t h column of the chart i n d i c a t e s the p o i n t s i n the search sequence at which the secondary counters must be i n i t i a l i z e d , as mentioned i n connection w i t h the sig n and sig n memory f l i p - f l o p s . The various counters, both primary and secondary, which must count during each search step, are l i s t e d i n the f i n a l column. Although not included i n the chart, i t must be remembered that each of the search steps begins with a Sign Test mode and concludes with a Step mode. On the other hand, each of the t r a n s f e r s can, f o r convenience, be considered to occur e n t i r e l y during a Sign Test mode. I t may be h e l p f u l , f o r complete understanding of the char t , to study i t s f i r s t .fourteen steps along with the i l l u s t r a t i o n of the three dimensional search sequence shown p r e v i o u s l y i n Figure 27. From t h i s c h art, the i n t e r c o n n e c t i o n s required between the sequence u n i t and the remainder of the op t i m i z e r can r e a d i l y be d e r i v e d . 61. For example, i f Q. r e f e r s to the Q output of f l i p - f l o p i i n r i n g counter number j , then i t can be determined by-i n s p e c t i o n of the M2 column of the chart that the step enable input (which w i l l be abbreviated SE2) to a d j u s t e r u n i t channel two must be: SE2 = Q + Q + Q + Q + Q 22 5^2 53 54 55 S i m i l a r l y , the input l o g i c network re q u i r e d to produce the co r r e c t t r i g g e r pulses (TA2) f o r the advance one-shot of r i n g counter number two i s defined by the RC2 column of the chart to be: T A 2 = TUPM Q12 + Q22 + Q32 + Q52 + Q02 Q 2 3 + Q24 + Q25 + % T T C Q^2 where r e f e r s to the mode f l i p - f l o p output.and T^p^ t o t n e d e t e c t o r up pulses, both of which are produced by the mode c o n t r o l l o g i c of Figure 37. T i s a t r a n s f e r complete pulse from the t r a n s f e r c o n t r o l l o g i c . The remaining i n t e r c o n n e c t i o n f u n c t i o n s r e q u i r e d are tab u l a t e d i n Appendix I I I . STATE 'MOTORS TRANSFERS AX-COUNTERS RC5 RC4 RC3 RC2 Ml M2 M3 M4 M5| 2D 3D AD 5D i INITIATE 3D 4D 5D COUNT 0 0 0 ~ " 0 r ~ 1 1 1 1 T ~ 2 X AX22 • 3 x AX12 4 i X 5 X X 1 1 2 0 X X AX33 T 3 1 X AX13 ' 2 X AX22, AX23 3 X AX12, AX13 4 X 5 X " X AX13, AX23 1 1 4 0 X 1 1 5 0 X X X 1 2 0 0 X X AX44 i 3 1 1 X AX1A-2 X AX22, AX2A 3 X AX12, AX14 4 X 5 • X X AHA, AX24 1 3 2 0 X AX33 , AX34 i 3 3 1 X AX13, AX14 2 X AX22. AX23, AX2A 3 X A l l 2 , AXI3, ^ X14 4 X 5 X X AX13, AX23, AX14, AX24 , 1 3 4 0 X i 3 5 0 X X X AX14, AX24, AX34 1 0 0 X i 5 "o' 0 x X X X 2 0 0 o X X AX 53 .. _ Figure 3u. Five Dimensional Sequence Chart — - i ^ CO cr; w E H Oi 0;EH Xl!=:> O ° CO ft; w fH CO EH U A U A CVirH ' S ^ - S i - * jOjO U A ' C V I C V ioo:<3 U A EH < o; I H - 4 [H H H OA. Q - 4 UAUA !CV|rH •x x •OiO !UA UAUA OA OA JCV OA i—I C V : M r S r S >r^ i r S ! O O . O O . O -!uA'oA!OA:CV CV ;rH'OA:H;CV r - l • X X W 0 ; 0 0 0 , 0 UA CV X j« 'uA' H: X| <>j oA! CV. Xi o! OAl I I '. .X' o I UA; OA' x; O; UA UA CV rH: X X !0<J. UA CV X o UA UA CV Hi XX; O.O i U A ; U A ' U A - 4 - 4 ' ; !cv;-4-;rH>cv H i V V I M v ' S-- 1 • • n ir^S rS t^ S i O.O O.O O X! X X cv rH! U A ! - 4 - ! - 4 - C V rH ; - 4 :r - i ; c v k ,J kJ kJ kJ kJ O O O O O x UAUA' rH OA i—I CV r - l o o . o . o o J _i ; i CVloAWCN? H I rS .rS PS rS . oo ooo ! I i . 1 i •> r\ t\ ri - 4 : O A ; O A : C V cv' rH :OA|rH CV CV. XXIX X'Xi 0 0 0 0 , 0 X! UA C V x Oj UA rH! X| o -4' C V !< • rH! iXj o ; OA; ; CVi X1 o : OA" :H! :x; 0 ; U A OA 1 X' 0 : I UA< CV| X! o; UA| U A r - l --4; Xl X1 O! O.. OA' XI O ! - 4lev IX jO 1-4 !x O X UA OA' X 0 UA CV ' X; 0; U A 7 |X' iO; x - 4 CO OA °! o cv CV o w cr; EH! •<jOA EH;O CO - 4 o cr; U A o cr; ! I I I !X ! j X: j X ; ik^ OA CV'OA i ^ t , U A ' ;x o CV r H JCV |OA r4lUA' O i O ' O r H 'CV OA OA ! I x i x: X j i 'xl :X X X X X-X X X I ! X I ! X O A OA H I i OA -4(UA!0 r H i I ) CV OA - 4 : U A Q r H i H . r H ;cv : O A ! OA I I j OA OA .OA i CV OA OA OA OA OA - 4 X X X X: .X; |X I I X i • 'x :X -!X X X X X o o - 4 ' U A O O o p o I I o o OA OA -4 OAjOA OA I U A O O A - 4 ° ; i o i •A I I 64. 4. SYSTEM EVALUATION AND CONCLUSIONS An automatic o p t i m i z e r based on the design presented i n the previous chapter was b u i l t and tes t e d f o r two of the proposed f i v e dimensions. Before d e s c r i b i n g the t e s t s performed and the r e s u l t s obtained, a few points regarding the a c t u a l system c o n s t r u c t i o n w i l l be elaborated. 4• 1 Optimizer Construction Motorola MRTL d i g i t a l i n t e g r a t e d c i r c u i t s were used f o r a l l l o g i c f u n c t i o n s , minimizing both system bulk and component cos t . The optimum dete c t o r was constructed with a ten b i t (N) t r a c k i n g counter and a four b i t (M) dete c t o r counter. A p r e c i s i o n ten b i t P a s t o r i z a RSN269$ D/A converter module was used i n conjunction with a F a i r c h i l d fX A702 i n t e g r a t e d o p e r a t i o n a l a m p l i f i e r f o r the required D/A conversion of the t r a c k i n g counter contents. The comparator was a F a i r c h i l d jU A710 i n t e g r a t e d c i r c u i t . The D/A a m p l i f i e r gain was adjusted f o r a t o t a l input s i g n a l c a p a b i l i t y of ten v o l t s , f i x i n g the t r a c k i n g step s i z e , Vg T, at Vqrp = 10 = 10 m i l l i v o l t s , b i 10 2 - 1 and p r o v i d i n g optimum de t e c t o r s e n s i t i v i t y to f i f t y m i l l i v o l t changes i n the performance f u n c t i o n , P ( t ) . The q u a l i t y f a c t o r , E(M,N), defined i n s e c t i o n (3.1), i s E(4,10) = 5 X 100 =0.5% 65. A cl o c k frequency of s i x t y k i l o h e r t z was s e l e c t e d , p e r m i t t i n g an input slewing r a t e , Sy, of S y = 10 X' 60 X 10 3 = 600 v o l t s ^ second This was found to be adequate f o r a l l performance f u n c t i o n s t e s t e d . Turning now to the ad j u s t e r u n i t , IMC stepping motors s i z e .008-008 were used. A gear r a t i o was chosen f o r each channel to give a step motor to potentiometer r e l a t i o n of 1805 steps per potentiometer r e v o l u t i o n . This imposed a l i m i t of about 0.05 per cent on the r e s o l u t i o n , p a r a l l e l to each co-ordinate, with which the performance f u n c t i o n space could be searched f o r the optimum. An a d d i t i o n a l r e s u l t of t h i s choice was to r e q u i r e that a l l Ax-counters contain at l e a s t eleven b i t s i n order to permit the maximum p o s s i b l e count of 1805 steps to be recorded. In f a c t , twelve b i t counters were used, g i v i n g a maximum count of 4095 steps and a l l o w i n g f o r some fu t u r e v a r i a t i o n i n the search r e s o l u t i o n . The length of the rat e r e g i s t e r s was then n e c e s s a r i l y a l s o twelve b i t s , so that a l l p o s s i b l e Ax-counts could be t r a n s f e r r e d and accepted without d i s c a r d i n g any b i t s . This i s , of course, e s s e n t i a l , since low order b i t s , a s s o c i a t e d with small Ax-counts, may w e l l become s i g n i f i c a n t a f t e r s h i f t i n g i n the ra t e r e g i s t e r . Although the d e s i r e d achievable search r e s o l u t i o n along any given l i n e i n the space of the independent v a r i a b l e s f i x e d the rate r e g i s t e r length at twelve b i t s , i t was pointed out i n s e c t i o n (3.3-1) that only seven or eight rate r e g i s t e r b i t s were 66. needed to provide adequate angular r e s o l u t i o n between adjacent search l i n e s . For in s t a n c e , assuming eight b i t s and s u b s t i t u t i n g i n t o Equation (3.6) gives 6 m m = tan ^  1 - 0.23 degrees. 255 For seven b i t s , 0 = tan mm -1 1 = 0.45 degrees. 12? Since f u r t h e r p r e c i s i o n would have been wasted, only the eight most s i g n i f i c a n t r a t e r e g i s t e r b i t s were used hy the D/A converters to o b t a i n the analog -input voltages f o r each V/F converter. D i s c r e t e component D/A converters, as shown i n Figure 39, w i t h (20) p r e c i s i o n to plus or minus one b i t i n eight b i t s , were used. R/2R LADDER R R R 2R 2R AA/Wv-2R 2R 0 2R +12v © +12v TIS34 —&» 47K 10K '-MA/VVi BUFFERS 2 RATE REGISTER OUTPUTS TO V/F CONVERTER INPUT Figure 39- Rate R e g i s t e r D/A Converter 67. Based on the cost of the two dimensional system constructed, and using the most recent component p r i c e schedules (un i t q u a n t i t y ) , a t o t a l cost of j u s t under $1000 was estimated f o r the complete f i v e dimensional automatic o p t i m i z e r . This i s roughly one tenth of the cost of any s m a l l , p r e s e n t l y a v a i l a b l e , general purpose computer capable of performing the equivalent o p t i m i z a t i o n f u n c t i o n . The cost of the f i v e stepping motors ($750) was not i n c l u d e d i n the above estimate, since they e s s e n t i a l l y perform D/A conversion between the o p t i m i z e r and the performance f u n c t i o n computer, and such conversion would not normally be i n c l u d e d i n the cost of a general purpose computer. A f u r t h e r s u b s t a n t i a l r e d u c t i o n i n the estimated cost may be p o s s i b l e i n the near f u t u r e i f the f u l l p o t e n t i a l of l a r g e - s c a l e i n t e g r a t e d c i r c u i t technology (LSI), p r e s e n t l y under i n t e n s i v e i n v e s t i g a t i o n , can be r e a l i z e d . The l a r g e number of i d e n t i c a l c i r c u i t c o n f i g u r a t i o n s used i n the o p t i m i z e r design' are p a r t i c u l a r l y s u i t a b l e f o r adaptation to LSI. Comparable reductions i n the cost of general purpose machines cannot be expected, unless the present high cost of t h e i r software systems can a l s o be d r a m a t i c a l l y reduced. 4•2 Tests and Results The two dimensional o p t i m i z e r was t e s t e d i n the c o n f i g u r a t i o n of Figure 9 with a PACE 231-R analog computer se r v i n g as the performance f u n c t i o n computer. In a l l t e s t s , the o p t i m i z e r was operated i n a " r e p e t i t i v e " mode. 68. p p The f i r s t t e s t f u n c t i o n used, P = x i + 2X2", i s a simple quadratic f u n c t i o n with a minimum value of zero at the o r i g i n , and having symmetrical e l l i p t i c a l contours, as shown i n Figure 40 below. Figure 40. Contours of F i r s t Test Function Searches were s t a r t e d at a v a r i e t y of p o i n t s d i s t r i b u t e d i n a l l four quadrants, and, i n each case, comparable r e s u l t s were obtained. The two photographs shown i n Figure 41, r e p r e s e n t a t i v e of a t y p i c a l t e s t run, c l e a r l y i n d i c a t e that quadratic convergence i s i n f a c t approximated by the o p t i m i z e r , since the performance f u n c t i o n i s minimized i n one i t e r a t i o n . Any d e v i a t i o n from the path which the P.M.A. steps should t h e o r e t i c a l l y f o l l o w can be a t t r i b u t e d to the l i m i t e d s e n s i t i v i t y of the optimum dete c t o r to changes i n the performance f u n c t i o n . In a l l t e s t s made with t h i s f u n c t i o n , as these p a r t i c u l a r photographs r e v e a l , those i t e r a t i o n s f o l l o w i n g the i n i t i a l one were confined to a small region about the optimum w i t h i n which the f u n c t i o n d e v i a t i o n s d i d not exceed about two per cent of the s t a r t i n g values. 69 4 0 -4 -5 ft .x. 0 x 1 ^ TIME 2 SECONDS/DIVISION Figure 41. Results of F i r s t Test 70. A second t e s t f u n c t i o n was obtained from a simple optimal c o n t r o l problem whose s o l u t i o n can be obtained by the mi n i m i z a t i o n of the f u n c t i o n 2 2 P = 1 + x l + x l x 2 + x2 2 6 subject to the c o n s t r a i n t t h a t g = 9xn + 4x2 + 14 = 0 . The constrained minimum i s at the point (x n , x 2 ) = (-2, l ) (as can r e a d i l y be v e r i f i e d using a Lagrange m u l t i p l i e r ) at which point the minimum value of P i s •P . - 13 = 2.17 min — , — 6 The problem i n t h i s form was not s u i t a b l e f o r d i r e c t s o l u t i o n by the automatic o p t i m i z e r , which cannot handle c o n s t r a i n t s , and so an equivalent unconstrained problem was obtained by app l y i n g the c o n s t r a i n t g as a penalty f u n c t i o n to P. The augmented performance f u n c t i o n P A = P + k g 2 which a l s o has a minimum of 2.17 at (x-,, x^) = (-2, 1), was then presented to the automatic o p t i m i z e r f o r s o l u t i o n . With a value of k = 1, the f u n c t i o n P^ i s 2 2 P A = 1 + X l + x l x 2 + x2 + 2 6 / \ 2 9x1 + 4x2 + 14 This i s a l s o a quadratic f u n c t i o n , since only second powers and l i n e a r terms i n the independent v a r i a b l e s are present; however, the contours of P^, sketched i n Figure 42, represent a long, narrow, s l o p i n g v a l l e y , the type of response surface found p a r t i c u l a r l y troublesome by many of the d i r e c t search and steepest descent techniques mentioned i n s e c t i o n ( 1 . 3 ) . Figure L2, Contours of Second Test Function Photographs of the op t i m i z e r ' s performance with t h i s f u n c t i o n are given i n Figure 43 f o r s t a r t i n g p o i n t s i n the f i r s t quadrant and the f o u r t h quadrant. In both cases, the bottom of the v a l l e y was reached a f t e r only o n e . i t e r a t i o n and t h e r e a f t e r the search i t e r a t e d about the minimum. No d i f f i c u l t y f o l l o w i n g the v a l l e y was encountered. The convergence time was roughly f i v e seconds. 4 0 -5 I X 2 0 P A ( t )-2.0) 100% -is* TIME 2 SECONDS/DIVISION Figure 43. Res u l t s of Second Test 73. The f i n a l performance f u n c t i o n chosen to t e s t the op t i m i z e r was the f u n c t i o n P = 100(x2 - X i 2 ) 2 + (1 - x±)2 (]3 ) proposed by Rosenbrock i n I960 and used by Powell i n 1962 to t e s t h i s al g o r i t h m . I t represents a h i g h l y asymmetric curved v a l l e y , as shown i n Figure 44, and i s g e n e r a l l y regarded as a " d i f f i c u l t " f u n c t i o n to optimize. I t s minimum value i s zero at the point (1, 1). {2> x j Figure 44. Contours of Third Test Function The f i r s t time the o p t i m i z e r was t e s t e d with t h i s f u n c t i o n , the search followed the bottom of the v a l l e y r i g h t up to the upper r i g h t corner of the f i r s t quadrant, since the optimum detec t o r could not detect the s l i g h t increase i n P. To a l l e v i a t e t h i s d i f f i c u l t y , a simple penalty f u n c t i o n of the form J = x 2 2 ; i f x 2 ^ k J = 0 ; i f x'2 <c k 74. was instrumented on the analog computer. The modified f u n c t i o n optimized was then p A - p + J The e f f e c t of t h i s penalty was to c o n s t r a i n the search to the area below the h o r i z o n t a l l i n e x = k; the value of k was chosen to be 1 . 5 , as shown i n Figure 44 . With t h i s c o n s t r a i n t , the o p t i m i z e r produced the r e s u l t s shown by the photographs of Figure 4 5 , s u c c e s s f u l l y l o c a t i n g the optimum a f t e r about four or f i v e i t e r a t i o n s . The time r e q u i r e d to minimize P was not much more than that taken with the previous two f u n c t i o n s . The e x c e l l e n t r e s u l t s obtained f o r the s p e c i a l purpose o p t i m i z e r from these t e s t s i n two dimensions demonstrate th a t i t i s s u i t a b l e f o r the type of o p t i m i z a t i o n problems l i k e l y to be encountered i n optimal c o n t r o l l e r a p p l i c a t i o n s . No d i f f i c u l t i e s are a n t i c i p a t e d i n the expansion of the machine from two to the proposed f i v e dimensions, since the a l g o r i t h m i t s e l f has been t e s t e d up to f i v e dimensions and found s a t i s f a c t o r y , and the a d d i t i o n a l c i r c u i t r y r e q u i r e d f o r the f i v e dimensional implementation simply d u p l i c a t e s that used f o r the two dimensional machine. Since, as mentioned i n s e c t i o n ( 1 . 2 ) , a wide range of process time constants may be encountered, the o p t i m i z a t i o n speed achieved i n the t e s t r e s u l t s , (roughly one second per l i n e a r search), may or may not be adequate f o r any p a r t i c u l a r c o n t r o l l e r a p p l i c a t i o n . However, i f necessary, considerable speed improvement could be made by s e v e r a l methods without s i g n i f i c a n t l y a l t e r i n g the b a s i c s t r u c t u r e of the o p t i m i z e r . 0 •4 -5 4X; \ f • 0 100%" 1 — T -G> TIME 2 SECONDS/DIVISION Figure 4 5 . R e s u l t s of Th i r d Test 76. For i n s t a n c e , f a s t e r stepping motors could be employed, or, at some s a c r i f i c e to search r e s o l u t i o n , s maller gear r a t i o s could be used between the motors and potentiometers. A l t e r n a t i v e l y , the motoi^s and potentiometers could be replaced e n t i r e l y by some form of purely e l e c t r o n i c D/A conversion. However, i t must be remembered that i n a p r a c t i c a l optimal c o n t r o l l e r such as i s i l l u s t r a t e d i n Figure 2, the maximum search speed i s "ultimately l i m i t e d by the s o l u t i o n speed achievable f o r the process model equations. 4.3 Summary and Conclusions A s p e c i a l purpose automatic o p t i m i z e r has been designed f o r use i n p r a c t i c a l optimal process c o n t r o l l e r s . The design was based on the implementation of a modified v e r s i o n of a q u a d r a t i c a l l y convergent search algorithm developed i n 1962 by M.J.D. Powell, and i s s u i t a b l e f o r a p p l i c a t i o n to the l o c a l , unconstrained m i n i m i z a t i o n of a n a l y t i c a l l y unknown but otherwise a c c e s s i b l e performance f u n c t i o n s of up to f i v e independent v a r i a b l e s . The o p t i m i z e r was constructed f o r two of the f i v e dimensions and was t e s t e d on s e v e r a l known f u n c t i o n s of varying d i f f i c u l t y . , The r e s u l t s obtained c l e a r l y demonstrated that the s p e c i a l purpose machine was both powerful and f a s t . In a d d i t i o n , i t was found to be s u f f i c i e n t l y inexpensive to j u s t i f y i t s use i n h i e r a r c h i c a l c o n t r o l s t r u c t u r e s at a l o c a l , sub-optimal l e v e l . F u l l b e n e f i t of the economic advantages of the automatic o p t i m i z e r over a general purpose d i g i t a l computer can only be r e a l i z e d i f i t i s used i n conjunction with other inexpensive s p e c i a l purpose machines f o r the s y n t h e s i s of complete sub-optimal c o n t r o l l e r s , and i t i s both hoped and expected that such machines w i l l soon be forthcoming. REFERENCES 77. 1. Masak, M., "Decomposition and Optimal Control Theory", Ph. D. Thesis, Department of E l e c t r i c a l Engineering, F a c u l t y of Applied Science, U n i v e r s i t y of B r i t i s h Columbia, 1968. 2. Brooks, S.H., "A Dis c u s s i o n of Random Methods f o r Seeking Maxima", Operations Research, V o l . 6, pp. 244-251, 1958. 3. Box, G.E.P., and J.S. Hunter,."Multi-Factor Experimental Designs", Annals of Mathematical S t a t i s t i c s , V o l . 28, pp. 195-241, 1957. 4. Wilde, D.J., Optimum Seeking Methods, P r e n t i c e - H a l l , 1964. 5. Hooke, R., and T.A. Jeeves, " D i r e c t Search S o l u t i o n of Numerical and S t a t i s t i c a l Problems", Journal of the A s s o c i a t i o n  of Computing Machinery, pp. 212-229, 1961. 6. Friedman, M., a n d . L . J S a v a g e , "Planning Experiments Seeking . Maxima",•Techniques of S t a t i s t i c a l A n a l y s i s , McGraw-Hill, New York, 1947. 7. Booth, A.D., "An A p p l i c a t i o n of the Method of Steepest Descent to the S o l u t i o n of Systems of Non-Linear Simultaneous Equations", Q u a r t e r l y J o u r n a l of Mechanics and Applied  Mathematics,"Vol. 2, pp. 460-468", 1949. " 8. Curry, H.B., "The Method of Steepest Descent f o r Non-Linear M i n i m i z a t i o n Problems", Qu a r t e r l y Journal of Appli e d Mathematics, V o l . 2, pp. 258-260', 1944. " 9. Box, G.E.P., and K.B. Wilson, "The Experimental Attainment of Optimum Conditions", Journal of the Royal S t a t i s t i c s S o c i e t y , S e r i e s B, V o l . 13, pp. 1-37, 1951. 10. Leitman, G.(ed.), Optimization Techniques, Academic Press, New York, 1962. 11. Crocket, J.B., and H. Chernoff, "Gradient Methods of Maximization, P a c i f i c Journal of Mathematics, V o l . 5, pp. 33-50, 1955. 12. Nelder, J.A., and R. Mead, "A Simplex Method f o r Function M i n i m i z a t i o n " , Computer J o u r n a l , V o l . 7, p. 308, 1965. 13. Rosenbrock, H.H., "An Automatic Method f o r F i n d i n g the Greatest or Least Value of a Function", Computer J o u r n a l , ".. ; V o l . 3, pp. 175-184, I960. 14. F l e t c h e r , R., and CM. Reeves, "Function M i n i m i z a t i o n by Conjugate Gradients, Computer J o u r n a l , V o l . 7, pp. 149-154, 1964. 78. 15. F l e t c h e r , R. and M.J.D. Powell, "A Rapi d l y Convergent Descent. Method f o r M i n i m i z a t i o n " , Computer J o u r n a l , V o l . 6, pp.' ] 63-168, 196.3. 16. Shaw. B.V., R.J.Buehler, and 0. Kempthorne, "The Method of P a r a l l e l Tangents (Partan) f o r F i nding an Optimum", O f f i c e of  Naval Research Report, NR -042-207, (No. 2 ) , 1 9 6 l . 17. Powell, M.J.D., "An I t e r a t i v e Method f o r Fi n d i n g S t a t i o n a r y Values of Functions of Several V a r i a b l e s " , Computer J o u r n a l , V o l . 5, pp. 147-151, 1962. 18. F i n k e l , R.W., "The Method of Resultant•Descents f o r the M i n i m i z a t i o n of an A r b i t r a r y Function", Paper 71, P r e p r i n t s of  Papers Presented at the 14th N a t i o n a l Meeting of the  A s s o c i a t i o n of Computing Machinery, 1959. 19. Voelker, W.H., " T r a n s i s t o r C i r c u i t Converts Voltage to Regulated Frequency", E l e c t r o n i c s , p. 73, November 16, 1964. 20. Donaldson, R.W., and D. Chan, " C a l c u l a t i o n of Steady State E r r o r s i n D i g i t a l - t o - A n a l o g Ladder Converters", E l e c t r o n i c s  L e t t e r s , V o l . 3 , No. 5, May, 1967. APPENDIX I 79. P.M.A. Search (Fortran) Program The main subroutine of the program f o l l o w s . $IBFTC PMA • • • • DIMENSION FMU(5,5),DELTA(5,5),X(5),DIRTN(5),K(5) N=5 L=n FK-o< C STATEMENT(S) TO INITIALIZE X ( I ) 2 CALL SRCH (N,X,DIRTN,P,PNEW,FK,FMU,DELTA,L,K) WRITE(6,5)P 5 FORMAT(F15.8) IF(P.GT. [3 )G0 TO 2 RETURN END In the above subroutine, o < 5 ^ , and n must be set according to the problem. n i s the number of dimensions i n v o l v e d , and o < and j3> are parameters d e f i n i n g the step s i z e and the stopping c r i t e r i o n , r e s p e c t i v e l y . The performance f u n c t i o n e v a l u a t i o n subroutine i s given below. $IBFTC POLY SUBROUTINE POLY(P,X,N) DIMENSION X(N) C P-DESIRED FUNCTION OF X ( I ) — M U S T BE INSERTED RETURN END The above subroutine i s c a l l e d before and a f t e r each l i n e a r search step by the SRCH1 subroutine which f o l l o w s . $IBFTC SRCH1 . . . SUBROUTINE SRCH1(N,X,DIRTN,P PNEW,FK,FMU,DELTA,L,K) DIMENSION FMU(N,N),DELTA(N,N), X (N ), DIRTN(N ),K(N) CALL POLY (P,X,N) DO" 1 1=1 N X(I)=X(I)+FK*DIRTN(I) CALL POLY(PNEW,X,N) IF (PNEW.GT.P)FK=-FK DO 2 J=l,5000 P=PNEW DO 3 1=1,N 3 X(I)=X(I)+FK*DIRTN(I ) CALL POLY(PNEW,X,N) IF(PNEW.GT.P)GO TO 20 2 CONTINUE 20- RETURN END 80. The r e s t of the program, c o n s i s t s of i d e n t i c a l subroutines SRCH2, SRCH3,SRCH4 and SRCH5 which c o n t r o l the sequencing of l i n e a r searches to execute P.M.A. A r e p r e s e n t a t i v e subroutine i s given below where the parameter rj" must be 2, 3, 4, or 5. $IBFTC SRCH^ , SUBROUTINE SRCH 0 (N ,X, DIRTN , P, PNEW, FK ,"FMU, DELTA, L,K ) ) DIMENSION FMU (N , N ),DELTA(N,N),DIRTN(N),K(N ) K(L)=1 • 3 DO 2 1=1,N 2 DIRTN(I)=0.0 DIRTN(1)=1.0 LM1=L-1 • • CALL SRCH( 15 -1) (N, X, DIRTN, P, PNEW, FK , FMU, DELTA, LM1, K ) 7 IF(K(1).EQ.1)G0 TO 10 IF(K(1).EQ-.2)G0 TO 20 IF(K(1).EQ.3)G0 TO 30 IF(K(1).EQ . 4)G0 TO 40 10 DO 1 1=1,N FMU(L,I)=X(I) 1 DIRTN(I)=0.0 DIRTN(L)=1.0 K(L)=K(L)+1 • • CALL SRCH1(N,X,DIRTN,P,PNEW,FK,FMU,DELTA,1,K) GO TO 7 20 K(L)=K(L)+1 GO TO 3 • 30 DO 4 1=1,N DELTA(LI)=X(I ) 4 DIRTN(I)=DELTA(L,I)-FMU (L,I) K(L)=K(L)+1 GO TO 6 40 RETURN END The P.M.A. program was executed on an IBM 7040 d i g i t a l computer f o r the f u n c t i o n s t e s t e d o r i g i n a l l y by Powell with h i s 1962 a l g o r i t h m . The f i r s t f u n c t i o n used was P = 100(x 2 - x x 2 ) 2 + (1 - x_) which has a minimum of zero at (1, l ) A s t a r t i n g point of (-1.2, 1.0) was chosen as was used by Powell. The second f u n c t i o n chosen v/as P = (x-j + 1 0 x 2 ) 2 + 5 ( x 3 - x / + ) 2 + ( x 2 - 2 x 3 ) 4 + ( X l - x ) 4 which has a minimum of zero at the o r i g i n . The s t a r t i n g point was (3, -1, 0, 1). A comparison of the computer r e s u l t s w i t h those obtained by Powell i s presented i n the f o l l o w i n g chart. The P.M.A. method c l e a r l y i s e q u a l l y as powerful as the o r i g i n a l method. Function One Function Two I t e r a t i o n Powell P.M.A. Powell P.M.A. 0 1 2 3 4 5 6 7 24.200 3.643 2.898 2.195 1.412 0.831 0.432 0.182 24.200 1.645 0.988 0.532 0.402 0.354 0.343 0.336 215.00 0.009r 9 X 10-5 2 X IO" 6 215.00 0.056, 1.3 X 10-4 9.5 X IO" 5 APPENDIX I I 82. C i r c u i t Components Used Motorola s e r i e s MC700P d i g i t a l i n t e g r a t e d c i r c u i t s were used f o r a l l l o g i c c i r c u i t s . Logic l e v e l s of +3.6 v o l t s ( l o g i c a l one) and zero v o l t s ( l o g i c a l zero) apply; l o a d i n g r u l e s , p i n arrangements, c i r c u i t d e t a i l s , and operating s p e c i f i c a t i o n s are supp l i e d f o r a l l u n i t s i n the MC700P s e r i e s t e c h n i c a l data sheet. The l o g i c symbols used i n the t h e s i s are defined below. I n v e r t e r 0 a One-shot (Monostable ) M u l t i v i b r a t o r I n v e r t i n g B u f f e r NOR gate ( j »a+T5 b o-X—^ Clock Pulse Source CLOCK -© po S Q T R 0 PC - >\ i 1 J. p-1 X t n n +1 G S R Qn+1 'Q~n+1 — - a 0 0 1 1 0 1 0 1 Qr  ±n 1 Qn Qn 0 0 Qn The chart shows the f l i p - f l o p output s t a t e s i n response to a clock pulse on the toggle (T) input at time, t n . Response i s to the f a l l i n g edge of the clock pulse. D i r e c t preset (PS) and p r e c l e a r (PC) inputs o v e r - r i d e the toggle i n p u t . 83. Of the elements shown, a l l but the clock and one-shot are d i r e c t l y a v a i l a b l e i n the MC700P s e r i e s , and these two were constructed using the MC789P hex i n v e r t e r c i r c u i t and a few e x t e r n a l d i s c r e t e components as shown below. 84. The one-shot durations and clock frequencies used i n the system constructed are l i s t e d below. 1. Optimum Detector Clock f = 60 k i l o h e r t z c One-shots Tg - 5 microseconds T-rjp = 2 microseconds ^DN = 2 microseconds 2. Search C o n t r o l l e r Mode Co n t r o l Logic Tjyr = 500 microseconds Tp^ = 10 microseconds Transfer Control Logic Clock f = 10 k i l o h e r t z Sn One-shots T^y = Trp = Tg^j = 100 microseconds X-Counters Tr7 - 200 microseconds Tg = 100 microseconds Sequence Unit TA = 100 microseconds Tr, = 100 microseconds 0 APPENDIX I I I 85. System Interconnections Below are l i s t e d a l l of the i n t e r c o n n e c t i o n s required between the o p t i m i z e r c i r c u i t blocks described i n the t e x t of the t h e s i s . The r i n g counter s t a t e s are designated by the n o t a t i o n defined on page 61; other symbols used correspond to those used i n the referenced f i g u r e s . 1. Adjuster Unit (Refer to Figure 24) Step Enable Inputs + Q55 SE1 - Q 1 2 + Q 3 2 + Q 5 2 + Q 5 3 + Q54 SE2 = Q22 Q52 + Q53 + Q54 + Q55 SE3 = Q23 + Q53 + Q54 + SE4 - Q24 + Q54 + Q 5 5 SE5 = Q 2 5 + Q 5 5 Step I n h i b i t Inputs SI1 = SI2 = SI3 = SI4 = SI5 = Q D R Sign Reverse Inputs (Refer to Figures 24, 32, and 37) SRi = T S R (SEi) + (TEGi) ( T g H ) (S/SMi) f o r i = 1, 2, 3, 4 ' S R 5 = TSR ( S E 5 ) where S/SM i s the Sign/SM s i g n a l shown i n Figure 27 and TEGi are the enable s i g n a l s to the t r a n s f e r gates l i s t e d on page 87. 2. Search C o n t r o l l e r (Refer to Figure 30) A X-Counters Counter Enable Inputs (Refer to Figure 30) CE12 = Q 3 2, CE22 = Q 2 2 CE13 = Q33 ( Q 1 2 + Q32 + °-52)> C E 2 3 = Q33 ( Q22 + Q52^ CE33 • Q 3 3 , CE14 = ' Q34 ( Q22 + C J32 + Q52 4 Q 5 3 ) CE24 = Q34 <Q22 + Q 5 2 + Q 5 3 ) , CE34 = Q34 ( Q 2 3 + Q 5 3 ) CE44 = Q 2 4 ' CE15 = °'3 2 + Q 5 2 + Q 5 3 + V CE25 - Q 3 5 ^22 + Q^2 ^53 Q 5 4 } CE35 = Q 3 5 ( Q 2 3 + Q53 + Q54)' CE45 (Q24 + CE55 - Q 2 5 Counter I n i t i a l i z e Inputs (Refer to Figure 30) CI13 = CI23 = Q 2 3 CI14 = CI24 = CI34 = Q 2 4 CI15 = CI25 = CI35 = CI45 = Q 2 5 -Counter Reset Inputs CR12 = CR22 = 2 P R E S E T CR13 = CR23 = CR33 = Q'53 + Q R E S E T CR14 = CR24 = CR34 = CR44 = Q 5 4 + P R E S E T CR15 = CR25 =' CR35 = CR45 = CR55 = Q 5 5 + Q R E S E T where P R E S E T " Q02 Q03 Q04 Q05 Data Transfers Transfer S t a r t S i g n a l (Refer to Figure 33) TST = Q 4 2 + Q^. + Q U + Q / F 5 Transfer Enable S i g n a l s (Refer to Figure 31) AX-Counters TEC12 = TEC22 = ^42 TEC13 = TEC23 = TEC33 TEC14 - TEC24 = TEC34 = TEC44 - V TEC15 = TEC25 = TEC35 = TEC45 = TEC55 Q45 87. Transfer Gates TEGI = TEG2 = TST . TEG3 = Q43 + Q44 + Q45 TEG4 = Q 4 4 + Q45 TEG5 \5 S h i f t Enable S i g n a l s (Refer to F i gures 31 and 33) SHE i = ( Q S H) (TEG i ) ; f o r i = 1, 2, 3, 4, 5 S h i f t Complete S i g n a l s (Refer to Figures 31 and 33) SC = Q S H (A + B + C + D) (TEG5), B = Q R 4 (TEG4) (TEG3), D = ( Q R 2 + Q R 1) (TST) . where A Q R 5 c = Qj^3 Rate P r e c l e a r Inputs PCI = Q12 + Q PC2 = Q 2 2 + S PC3 = Q2^ + 0 PC4 = Q 2 4 + S . PC5 = Q25 + S where S = TM 32 + s The l o g i c f u n c t i o n S p r e c l e a r s a l l the r a t e r e g i s t e r s j u s t p r i o r to e a c h , t r a n s f e r a s s t i p u l a t e d on page 52. Sequence Unit Ring Counter Advance Pulses (Refer to Figures 33 and 36) ' T A 2 = TUPM (Q12 + Q 22. + Q32 + Q52 + Q23 + Q24 + Q25 } + T T C Q M Q 4 2 + START TA 3 = T U p M (Q, 2 + Q 2 3 + Q 5 3 + Q 2 4 + ) + T T Q Q M + START TAA = TTT™ff (Q„ + Q_. + Q_. + Q ) + Tr "UPM 4 g53 24 54 25 •TC 4^4 + START TA5 = T (Q„ + Q + Q ) + T O Q + START UPM 54 25 55 TC M 45 where START = Q R E S E T \ TSTART and l'5'j'ART ^ s a o n e ~ s h o t pulse o r i g i n a t i n g i n the c i r c u i t shown below. Ring Counter Reset Inputs (Refer to Figure 36) - RCR2 = RCR3 = RCR4 = RCR5 = SYSTEM RESET and SYSTEM RESET a l s o o r i g i n a t e s i n the c i r c u i t belowi 3 .6v © — MANUAL RESET 3.6v -1-Q o e — MANUAL START PS Q .Q PC SYSTEM RESET START ^ RECYCLE — — — © TRIGGER The above l o g i c i s used to manually reset and s t a r t the opt i m i z e r ( i n that sequence). I f switch SI i s grounded, the opt i m i z e r stops a f t e r one i t e r a t i o n - and must be reset and s t a r t e d again manually. I f switch SI i s connected to the r e c y c l e t r i g g e r , the system operates r e p e t i t i v e l y . The system reset s i g n a l must be connected to the po i n t s shown i n Figure 37 as w e l l as to the r i n g counter r e s e t t e r m i n a l s . The r e c y c l e t r i g g e r s i g n a l can be conveniently obtained as RCT = T UPM This being the case, T START should be at l e a s t twice as long as T M (Figure 37). 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0103257/manifest

Comment

Related Items