Abstract:
An apparatus and method is disclosed for solving optimization problems without the need to build mathematical models or rules. The inventive method combines the structure of a single-loop feedback control system and optimization search engine mechanisms. Running in real-time, a Model-Free Adaptive (MFA) optimizer can automatically search for the optimal operating point for a dynamic system when a parabolic relationship exists between the input and output. The MFA optimizer comprises a user-selected Min/Max setter to define the searching objective, a process acting-mode search engine to determine if the process is running in direct-acting or reverse-acting mode, a maximum search engine and a minimum search engine to find the maximum or minimum. This apparatus and method is useful in fuel-and-air ratio optimization for combustion processes, yield optimization for chemical or biological reactors, and operating efficiency optimization for coal or ore ball mills.

Description:
[0001]     The subject of this patent relates to optimization of systems including industrial processes, equipment, facilities, buildings, homes, devices, engines, robots, vehicles, aircraft, space-vehicles, appliances and other systems, and more particularly to a method and apparatus for automatically optimizing a process or system based on the optimal objectives without using mathematical models of the process or system.  
         [0002]     In the U.S. Pat. Nos. 6,055,524, 6,556,980 B1, and 6,360,131 B1, Model-Free Adaptive (MFA) control technology was introduced. In this patent, we expand the Model-Free Adaptive method from automatic control to automatic optimization.  
         [0003]     Optimization has four key elements: (1) Objectives—the objectives that define what to achieve; (2) Conditions and Constraints—the conditions and constraints that may not allow the achievement of some of the objectives; (3) Acceptable Solutions—all possible solutions that allow the achievement of some or all of the objectives; and (4) Optimal Solution—the solution that makes the most sense after the tradeoff between the conflicts in objectives and constraints.  
         [0004]     Optimization problems can be difficult to solve due to the following reasons: (1) the process input-output relationship is typically dynamic, multivariable, nonlinear, and time-varying; (2) there are multiple operating conditions and constraints; (3) the process signals are frequently contaminated by noises and disturbances; (4) online optimization is required; and most importantly, (5) it is difficult to develop and maintain a process model or a set of rules.  
         [0005]     Traditional optimization is dependent on the first-principle or identification based mathematical models or rules. The Model-Free Adaptive Optimization technology can solve many optimization problems without the need to build such models or rules. Running in real-time, the MFA optimizer can automatically search for the optimal operating point for a dynamic system when a parabolic relationship exists between the input and output. The MFA optimization technology is useful in fuel-and-air ratio optimization for combustion processes, yield optimization for chemical or biological reactors, and operating efficiency optimization for coal or ore ball mills.  
     
    
       [0006]     In the accompanying drawing:  
         [0007]      FIG. 1  is a block diagram illustrating a single-input-single-output (SISO) Model-Free Adaptive (MFA) optimization system where an MFA optimizer optimizes a single-input-single-output (SISO) process.  
         [0008]      FIG. 2  is a drawing illustrating the process input-output relationship, where there is either a maximum or minimum as an optimal point.  
         [0009]      FIG. 3  is a flow chart describing the steps in a process acting mode search engine mechanism in an MFA optimizer.  
         [0010]      FIG. 4  is a flow chart describing the steps in a maximum search engine mechanism in an MFA optimizer.  
         [0011]      FIG. 5  is a flow chart describing the steps in a minimum search engine mechanism in an MFA optimizer.  
         [0012]      FIG. 6  is a flow chart describing the main search engine of an MFA optimizer. 
     
    
       [0013]     The term “mechanism” is used herein to represent hardware, software, or any combination thereof. The term “process” is used herein to represent a physical system or process with inputs and outputs that have dynamic relationships.  
       DESCRIPTION  
       [0000]     A. SISO Model-Free Adaptive (MFA) Optimizer  
         [0014]      FIG. 1  illustrates a single-input-single-output (SISO) Model-Free Adaptive (MFA) optimization system. It comprises a SISO MFA optimizer  10 , a SISO process  12 , signal adders  14 ,  16 , and a Min/Max Setter  18 . The signals shown in  FIG. 1  are as follows: 
        r(t)—Setpoint.     y(t)—Measured Process Variable, y(t)=x(t)+d(t).     x(t)—Process Output.     u(t)—Optimizer Output that is applied to the Process Input.     d(t)—Disturbance, the disturbance caused by noise or load changes.     e(t)—Error between the Setpoint and Measured Variable, e(t)=r(t)−y(t).          
         [0021]     Assume that there is an optimal point in the process input-output relationship, and assume that we can manipulate the process input within its range to allow the process output to reach the optimal point, where the process input range may be bounded by limits or constraints.  
         [0022]     The optimization objective is for the SISO MFA optimizer to produce an output u(t) to force the measured process variable y(t) to reach the optimal point and stay near there under variations in process dynamics, disturbances, noises, and other uncertainties.  
         [0023]     Unlike any other traditional optimization system, the SISO MFA optimization system uses the same structure as a SISO feedback control system. It makes the implementation and use of such a system easy and user-friendly. The SISO MFA optimizer can be implemented in the same environment as SISO feedback controllers including but not limited to PID (proportional-integral-derivative) controllers and SISO MFA controllers. On the other hand, since the SISO feedback control systems are the most popular control systems and most control engineers and process operators are familiar with the structure and variables, the SISO MFA optimizers are easy to learn, use, and maintain.  
         [0024]     The Min/Max Selector  18  allows the user to choose when to use the optimizer to find a minimum or a maximum. Depending on the information, the MFA Optimizer can move the setpoint to its low limit or high limit accordingly. As an example, consider a system where the setpoint and the process variable have a range of 0% to 100%. The low setpoint limit is 5% and the high setpoint limit is 95%. If the Min/Max Selector is set to search for a minimum, setpoint r(t) can be set to 5%. Similarly, if the Min/Max Selector is set to search for a maximum, setpoint r(t) can be set to 95%.  
         [0025]     As another example, consider a system where the setpoint and process variable have a range of 150 degrees Fahrenheit to 650 degrees Fahrenheit. The low setpoint limit is at 200 degrees Fahrenheit and the high setpoint limit is at 600 degrees Fahrenheit. If the Min/Max Selector is set to search for a minimum, setpoint r(t) can be set to 200 degree F.; and if the Min/Max Selector is set to search for a maximum, setpoint r(t) can be set to 600 degree F. This setpoint setting arrangement allows the MFA optimizer to produce an error e(t) so that it will continuously search for the optimal point towards the right direction. This is because the search will not stop unless the process variable y(t) reaches the setpoint r(t) or an optimal point.  
         [0026]     The algorithm for producing the output u(t) for the MFA optimizer will be discussed in the final portion of the description.  
         [0027]      FIG. 2  is a drawing illustrating the process input-output relationship, where there is a maximum or minimum as an optimal point. Curve  20  of the top chart shows that when u(t) starts to increase from 0, y(t) increases. This relationship continues until y(t) reaches a maximum and then it starts to decrease. This type of process can be either direct-acting or reverse-acting depending on the operating point. From a control point of view, the process is not controllable when using regular feedback controllers. Since the process changes its sign, it will cause a negative feedback loop to become a positive feedback loop. An automatic control system is based on negative feedback in order to be closed-loop stable.  
         [0028]     In contrast, from an optimization point of view, this process can be optimized since there exists an optimal point that can be reached. If a process is only direct-acting or reverse-acting, there will be no optimal point to reach. Then, the process may be controllable but cannot be optimized since no maximum or minimum exists.  
         [0029]     Curve  22  of the bottom chart shows that when u(t) starts to increase from 0, y(t) decreases and the relationship continues until y(t) reaches a minimum and then it starts to increase. Similarly, this process changes its sign and cannot be controlled by conventional feedback controllers but can be optimized since there exists a minimum as an optimal point.  
         [0030]      FIG. 3  is a flow chart describing the steps in a process acting mode search engine mechanism in an MFA optimizer. It describes the method for detecting whether the process is in a direct-acting mode or reverse-acting mode. At Block  26 , initialization is taking place including the tasks to clear the direct-acting counter (Let DA_Count=0), clear the reverse-acting counter (Let RA_Count=0), and set the direct-acting flag to its default value (Let DA_Flag=ON). These counters and the flag are variables in the acting mode search engine mechanism. At Block  28 , the optimizer output is increased by Δu(t), and at Block  30 , it waits for a period of time, Tx. This is the estimated delay time between the process input and output, which is user-configurable.  
         [0031]     At Block  32 , the routine checks the measured process variable y(t) to see if its value has increased in comparison to its previous values. If the answer is Yes, the routine goes to Block  34  to increase the direct-acting counter by 1 and clear the reverse-acting counter. If the answer is No, the routine goes to Block  36  to increase the reverse-acting counter by 1 and clear the direct-acting counter. These counters are used to record the number of times the acting type has been detected.  
         [0032]     At Block  38 , DA_Count value is checked. If it is larger than 2, it means that the process has been detected in the direct-acting mode in the past 3 consecutive tries. The routine will move to Block  42  to set the DA_Flag to ON and exit. Notice that the number of tries required to guarantee the detection of the acting mode may depend on the process and is user configurable. Here, we use 3 tries as an example. This applies to all the counters used in the search engines in this patent.  
         [0033]     If the DA_Count value is not larger than 2, the routine goes back to Block  28  to perform one more round of detection. If the routine is branched to Block  36 , it will continue to Block  40  to check the RA_Count. Similarly, if its value is larger than 2, it means that the process has been detected in the reverse-acting mode in the past 3 consecutive tries. The routine will move to Block  44  to set the DA_Flag to OFF to indicate that the process is in the reverse-acting mode and then exit. If the RA_Count value is not larger than 2, the routine goes back to Block  28  to perform one more round of detection.  
         [0034]     Notice that the y(t) signal might be contaminated with noise. It is necessary to use filters such as low pass filters to remove high frequency noises before applying this routine and other search engine routines in this patent.  
         [0035]      FIG. 4  is a flow chart describing the steps in a maximum search engine mechanism in an MFA optimizer. At Block  50 , initialization is taking place including the tasks to clear the maximum counter (Max_Count) and maximum flag (Max_Flag). The counter and flag are variables in the maximum search engine mechanism. At Block  52 , the routine checks the process acting mode. If it is in the direct-acting mode, optimizer output u(t) is increased by Δu(t) at Block  54 . If it is in the reverse-acting mode, optimizer output u(t) is decreased by Δu(t) at Block  56 . Notice that Δu(t) can be a varying value or a fixed value depending on the design of the MFA optimizer, which will be discussed in detail. This applies to all the Δu(t) value presented in this patent.  
         [0036]     At Block  58 , the routine waits for a period of time Tx. This is the estimated delay time between the process input and output, which is user-configurable. At Block  60 , the routine checks the measured process variable y(t) to see if its value is increased compared to previous values. If the answer is Yes, the routine goes to Block  62  to clear the Max_Count since it has not yet reached the maximum. The routine goes back to Block  52  to continue the search.  
         [0037]     If the answer at Block  60  is No, it means that y(t) was going up but now it is starting to decrease. It is a good indication that the maximum has been reached. At Block  64 , the current u(t) is saved as Umax, which is the optimizer output that produced maximum y(t). This step needs to be done only one time when Max_Count is equal to 0. Then the Max_Count is incremented by 1.  
         [0038]     At Block  66 , Max_Count value is checked. If it is larger than 2, it means that y(t) has been declining for the past 3 consecutive tries and it is certain that y(t) has passed its maximum. At Block  68 , the Max_Flag is set to ON to indicate the detection of maximum. Notice that the number of tries required to guarantee the detection of the maximum may depend on the process and is user configurable. Here, we use 3 tries as an example.  
         [0039]     It is a good idea to reset the u(t) to the saved Umax to allow y(t) to get back to its maximum. If the value of Max_Count is not larger than 2, the routine will go back to Block  52  to continue the search.  
         [0040]      FIG. 5  is a flow chart describing the steps in a minimum search engine mechanism in an MFA optimizer. At Block  70 , initialization is taking place including the tasks to clear the minimum counter (Min_Count) and minimum flag (Min_Flag). The counter and flag are variables in the minimum search engine mechanism. At Block  72 , the routine checks the process acting mode. If it is in the direct-acting mode, optimizer output u(t) is increased by Δu(t) at Block  74 . If it is in the reverse-acting mode, optimizer output u(t) is decreased by Δu(t) at Block  76 . At Block  78 , the routine waits for a period of time Tx. This is the estimated delay time between the process input and output, which is user-configurable.  
         [0041]     At Block  80 , the routine checks the measured process variable y(t) to see if its value has decreased in comparison to its previous values. If the answer is Yes, the routine goes to Block  82  to clear the Min_Count since it has not yet reached the minimum. The routine goes back to Block  72  to continue the search. If the answer at Block  80  is No, it means that y(t) was declining but now it is increasing. This is a good indication that the minimum has been reached. At Block  84 , the current u(t) is saved as Umin, which is the optimizer output that produced minimum y(t). This step needs to be done only one time when Min _Count is equal to 0. Then the Min _Count is incremented by 1.  
         [0042]     At Block  86 , Min_Count value is checked. If it is larger than 2, it means that y(t) has been rising for the past 3 consecutive tries and it is certain that y(t) has passed its minimum. Notice that the number of tries required to guarantee the detection of the minimum may depend on the process and is user configurable. Here, we use 3 tries as an example. At Block  88 , the Min_Flag is set to ON to indicate the detection of the minimum. It is a good idea to reset the u(t) to the saved Umin to allow y(t) to go back to its minimum. If the value of Min_Count is not larger than 2, the routine will go back to Block  72  to continue the search.  
         [0043]      FIG. 6  is a flow chart describing the main search engine of an MFA optimizer. At Block  90 , initialization is taking place including the tasks to clear all counters, and set all default flags and parameters. At Block  92 , the process acting mode search routine is run to determine if the process is running in a direct-acting mode or reverse-acting mode.  
         [0044]     At Block  94 , the routine checks to see if the optimizer is searching for a minimum or maximum based on the status set by the Min/Max Setter. If searching for a minimum, the routine goes to Block  96  to run the Minimum Search routine. If it is searching for a maximum, the routine goes to Block  98  to run the Maximum Search routine. Once an optimal point is reached, the routine moves to Block  100 , where the user has the option of leaving the process running for a period of time, which can be set by the parameter Ty.  
         [0045]     During this quiet period, the MFA optimizer is in an idle mode with a fixed output u(t), leaving the process running at the optimal operating condition. This waiting period should be determined by the user. If the process is fast and dynamic, Ty may be set to a small value or even at zero seconds so that the search continues. If the process is relatively slow and steady, Ty can be set for a couple of hours or even days. The rule of thumb here is that the process should be running at its optimal operating condition as long as possible to maximize the economical benefits.  
         [0046]     There are several ways to design the MFA optimizer for generating its output u(t). Without losing generality, three design examples are provided.  
         [0000]     1. MFA Controller-Based MFA Optimizer  
         [0047]     The SISO Model-Free Adaptive (MFA) controllers described in U.S. Pat. Nos. 6,055,524 and 6,556,980 B1 can be used to compute the MFA optimizer. When using this approach, the MFA optimizer can adapt to fit the changing process dynamics and/or operating conditions. The MFA optimizer produces its output u(t) in a similar way to a SISO MFA controller with varying value of u(t). In general, the output velocity limit (OVL) is used to clamp the output to keep it from making too big of a jump at each sample interval. That means, at each sample interval, the calculated Δu(t) is limited by the output velocity limit as described in the following formulas: 
 
Δ u ( t )=Δ u ( t ), if |Δ u ( t )|≦OVL   (1a) 
 
Δ u ( t )=SGN(Δ u ( t ))OVL, if |Δ u ( t )|&gt;OVL   (1b) 
 
 where SGN(.) denotes the sign function, SGN(Δu(t)) extracts the sign of Δu(t), and OVL&gt;0 is the output velocity limit, which is user configurable. 
 
 2. PI Controller-Based MFA Optimizer 
 
         [0048]     A PI (proportional-integral) controller can be used to compute the output u(t). Since the derivative function of a PID controller will make the u(t) jump up and down, it cannot be used here. The standard PI algorithm has the following form:  
                 u   ⁡     (   t   )       =       K   p     ⁡     [       e   ⁡     (   t   )       +       1     T   i       ⁢     ∫       e   ⁡     (   t   )       ⁢     ⅆ   t             ]         ,           (   2   )             
 
 where K p  is the Proportional Gain, and T i  is the Integral Time in second/repeat. Since we require a Δu(t), the following digital PI formula can be used. 
 
Δ u=K   p {( e [2] −e [1])+( T   s   /T   i ) e [2]}  (3) 
 
 where Ts is the sample interval, e[1] and e[2] are the time sampled error signals of e(t), e[2] is the current sample of e(t). Similarly, the output velocity limit is used to clamp the output to keep it from making too big of a jump at each sample interval. 
 
 3. Output Step Limit Based MFA Optimizer 
 
         [0049]     A simple design for the MFA optimizer is to allow the user to configure an Output Step Limit (OSL). This is equivalent to the Output Velocity Limit (OVL) used in the feedback controller cases. Since the direction that u(t) is moving is already known by the search engines, we can simple let 
 
 Δu ( t )=OSL   (4) 
 
 where OSL&gt;0 is the user entered output step limit. That means, at each sample interval, u(t) will move up or down by Δu(t) which has the fixed value of OSL. 
 
         [0050]     The concept of the single-input-single-output (SISO) MFA optimizer can be expanded to multi-input-multi-output (MIMO) cases, which will be described in a future patent.