Data processing: generic control systems or specific application – Generic control system – apparatus or process – Optimization or adaptive control
Reexamination Certificate
1998-08-03
2002-01-01
Grant, William (Department: 2121)
Data processing: generic control systems or specific application
Generic control system, apparatus or process
Optimization or adaptive control
C700S019000, C700S029000, C700S030000, C700S046000, C700S052000, C700S053000, C318S561000, C318S560000, C705S007380, C705S002000
Reexamination Certificate
active
06336050
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a processor system arranged to optimise one or more signals.
2. Related Art
In many industrial applications, one or more input quantities (for example raw materials or signal values) are combined according to some predetermined process to produce an output quantity (e.g. a chemical composition, or a processed signal).
In general, the output is therefore a function of the input. In some cases, the function will be known, whereas in others it will not be known. In some cases, the function will linear, whereas in others it will be non linear. In some cases, the function will be well behaved, whereas in others it will include discontinuities.
For many types of function, an optimum output value (e.g. chemical yield, chemical composition, bit error rate of a process signal, or throughput capacity over a telecommunications network) is possible, corresponding to a predetermined optimum input value or, where there is more than one input, to a set of such input values, which may be considered to define an input vector.
In many types of function, there may be more than one such optimum value (which may either be a maximum or a minimum). Generally, one of these is the true optimum value (the global optimum value) and the others are local optima. It is generally desired to find the global optimum value, rather than local optima.
For simple analytical functions, such as a cubic function, it is possible to find the optima (in this case, for example, minima) by differentiating the function, to locate points of inflection; double differentiating the function, to determine which are minima; determining the value of the function at each such minimum; and selecting the lowest. However, this approach fails where the function is either unknown or ill-behaved, or both.
Two general numerical approaches which can deal with functions of these types are known. and will be referred to as “global” approaches and “local” approaches.
Global approaches include “brute force” search techniques; in such techniques, the function is evaluated at a large number of possible function values distributed over the range of possible input values, and the minimum is found directly.
Such an approach is possible for functions which depend on a small number of input variables, over a small range of those variables. However, for a large number of variables and/or a large variable range, the number of occasions on which the function must be solved (which is computationally intensive and time consuming) becomes very large, rendering such approaches slow and unsuitable for, for example, real time signal processing or network control applications.
On the other hand, “local” techniques start with one input vector position and “move” to a new vector position in a direction which optimises the function. Such techniques include Genetic Algorithms and Simulated Annealing processes. For example, where the optimum sought is a minimum, the search process may consist of determining the function value at input values spaced at either side of the starting point, determining whether either generates a function value lower than the starting function value, and selecting that which does so; and then repeating the process.
It will be seen that a process of this kind will continue to move the currently selected input value until a local minimum of the function value is found. However, with local search techniques of this kind, there is no guarantee that the global optimum will be found.
One known technique which attempts to reduce this problem within a local search scheme is known as “Dynamic Hill Climbing”, as described in “Dynamic Hill Climbing”, de la Maza and Yurate, AI Expert, March 1994 at pages 26-31.
In this scheme, each optimisation run is provided in two loops; an inner loop and an outer loop. The inner loop comprises a local search, arranged to find a local minimum. Once the local minimum has been found, the technique reverts to the outer loop, which determines another starting position (i.e. input value vector) and re-executes the inner loop. This process is repeated until most of the range of input values have been reviewed.
This technique was found useful for performing a co-ordinate change transformation for matching two sets of image data derived from computer topography or magnetic resonance imaging.
The present inventors have concluded that the Dynamic Hill Climbing technique, together with others, does not perform well on certain types of function, in which it does not find the global optimum within a reasonable number of iterations.
SUMMARY OF THE INVENTION
An aim of the present invention is to improve on the performance of such algorithms, at least for certain types of function. Accordingly, the invention finds application in many industrial fields; for example, in real time signal processing, or industrial process control. Particular embodiments of the invention comprise a multi-pulse linear predictive coder, an adaptive filter useful, for example, as an echo cancellor; an image transform generator (e.g. for matching two images or for performing a motion vector search); a chemical plant controller; a crystal structure modeller; and a telecommunications network management unit.
Accordingly, the present invention provides, in one aspect a processor system for optimising comprising: means for inputting data relating to a function of a plurality of input signals for which it is desired to find output values which give an optimum value of said function; means for finding said output values by performing a plurality of cycles to reach a convergence, each of which cycles comprises: providing an old current value of the or each input signal; selecting a test value of one or more said input signals; generating said function from said selected test value or values; selecting a new said current value in dependence upon the relationship between the value of the function for the test value and the value of the function for the old current value, said test values including values close to said old current values so as to move said input signal towards a local convergence; and means for outputting said output values; characterised in that said finding means is adapted to perform said cycles such that in some but not all of said cycles, said test value of one or more said input signals is selected to lie remotely within the range of said input signal to said old current value, so as to move said input signal towards a global convergence prior to completion of said local convergence.
REFERENCES:
patent: 4208712 (1980-06-01), Deutsch
patent: 4744027 (1988-05-01), Bayer et al.
patent: 4894773 (1990-01-01), Lagarias
patent: 5136538 (1992-08-01), Karmarkar et al.
patent: 5572420 (1996-11-01), Lu
patent: 5587897 (1996-12-01), Iida
De La Maza M et al., “dynamic hill climbing (optimization algorithm)”, Al Expert, Mar. 1994, USA, vol. 9, pp. 26-31.*
Atkinson A. C., “A segmented algorithm for simulated annealing”, Statistics and Computing, Dec. 1992, UK, vol. 2, pp. 221-230.*
Brooks S. P. et al., “automatic starting point selection for function optimization”, Statistics and Computing, Dec. 1994, UK, vol. 3, pp. 173-177.
Amin Shara J
Fernandez-Villacanas Martin Jose-Luis
British Telecommunications public limited company
Grant William
Patel Ramesh
LandOfFree
Method and apparatus for iteratively optimizing functional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for iteratively optimizing functional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for iteratively optimizing functional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2858497