Optimizer

Details Optimizer Optimizer

2000-08-17

2003-06-03

Patel, Ramesh (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, C318S560000, C318S561000

Reexamination Certificate

active

06574516

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an apparatus for, and a method of optimising one or more signals.
2. Related Art
In many industrial applications, one or more input quantities (for example quantities of 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) as a function of the inputs. 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 continuous, whereas in others it will include discontinuities.
For many types of function, an optimum output value 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.
There will be a true optimum value (the global optimum value) but there are often local optima. It is generally desired to find the global optimum value, rather than local optima. Examples of functions which will have an optimum output value include functions for evaluating chemical yield, chemical composition, bit error rate of a process signal, or interference in a mobile telecommunications network.
For simple analytical functions, such as a cubic function, it is possible to find the optimum (in this case, for example, minimum) 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 discontinuous, 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. 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.
A well known technique for avoiding convergence on local optima is the technique of simulated annealing, described for example in “Optimisation by simulated annealing” by S. Kirkpatrick et al, Science 220 (1983) pp 671-680. International paptent application number WO98/34188 describes another a local search technique which attempts to avoid local optima. Such techniques are referred to in this specification as energy minimisation techniques and the function to be solved is referred to as an energy function.
A problem with known techniques is that the performance is dependent on user selected parameters. For example, the performance of the simulated annealing algorithm is dependent on a parameter representing the ‘initial temperature’ and on the strategy selected for changing this parameter.
BRIEF SUMMARY OF THE INVENTION
In accordance with a first aspect of the present invention there is provided a method of finding preferred values for at least one input signal corresponding to an optimum of a function of the at least one input signal, the method comprising performing a plurality of cycles to reach a convergence defined by an exit criterion, each of which cycles comprises steps of
(a) providing an old current value of the or each input signal;
(b) providing an old current value of the function;
(c) selecting a test value of one or more said input signals;
(d) generating said function from said selected test value or values and comparing the generated function value with the old current value of the function;
and either, when the outcome of step (d) is that the generated function value is more optimal than the old current value, the steps of
(e) providing a new current value of the or each input signal equal to the selected test value or values, and a new current value of the function equal to the generated function value;
(f) testing whether that generated function value is more optimal than the most optimal of generated function values stored by previously performed cycles, and, if so, storing that generated function value;
(g) testing for said exit criterion, and if the exit criterion is not met, returning to step (a);
or, when the outcome of step (d) is that the generated function value is not more optimal than the old current value, the steps of
(h) returning directly to step (a), provided that step (d) has not been followed by step (h) a predetermined number of times in succession; and otherwise
(i) providing a new current value of the function equal to a generated function value stored under substep (f) of a previously performed cycle, and then returning to step (a).
Preferably, the operation of step (i) provides the new current value of the function equal to the most optimal stored generated function value, provided that the last succeeding operation of step (f) of a previous performed cycle did not store the respective generated function value; and wherein, if the last succeeding operation of step (f) of a previous performed cycle did store the respective generated function value, the nth operation of step (i), without any intervening operation of substep (e) when n in greater than one, provides the new current value of the function equal to the n+1th most optimal stored generated function value.
In accordance with a second aspect of the present invention there is provided an apparatus for finding preferred values for at least one input signal corresponding to an optimum of a function of the at least one input signal, the method comprising performing a plurality of cycles to reach a convergence defined by an exit criterion, the apparatus comprising:
means for detecting said exit criterion;
means for selecting a test value for at least one input signal;
means connected to receive the selected test value or values, and responsive to data defining said function of the at least one input signal to generate a function value from the selected test value or values;
a store for storing a current value of the function, a current value of the or each input signal, and one or more generated function values;
modifying means arranged
to receive the generated function value,
to modify the stored current value of the function to be equal to one of the function values when the current value has not been modified for a predetermined number of cycles of operation; and
means for cyclically operating said selecting, generating and modifying means until the detecting means detects said exit criterion.
Preferably, the modifying means is arranged such that said one of the function values is the most optimal stored generated function value, provided that the last succeeding operation of the modifying means which found the rec

Affiliated with

Also associated with

Rating

Optimizer does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimizer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimizer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3148658