MODELING OF SYSTEMS USING CANONICAL FORM FUNCTIONS AND SYMBOLIC REGRESSION

• US 20070208548A1
• Filed: 03/05/2007
• Published: 09/06/2007
• Est. Priority Date: 03/03/2006
• Status: Active Grant

• Current Assignee: Siemens Industry Software Limited (Siemens AG)
• Original Assignee: Solido Design Automation (Siemens AG)
• Inventors: McConaghy, Trent
• Granted Patent: US 8,332,188 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 30/367 Design verification, e.g. using simulation, simulation program with integrated circuit emphasis [SPICE], direct methods or relaxation methods

Abstract

An apparatus and method to generate and evolve canonical form expressions representing a characteristic of a given system. Static and dynamic behavior of non-linear electrical circuits can be modeled. Searching of canonical form expressions can use evolutionary algorithms, simulated annealing and Tabu searching.

Claims

1. A method to generate at least one expression describing a characteristic of a system, the system associated with variables and with pre-determined data related to the characteristic of the system, the method comprising steps of:

generating at least one initial expression having a pre-defined canonical form and being a function of the variables;

generating calculated data using the at least one initial expression;

calculating an output of a goal function in accordance with the pre-determined data and the calculated data; and

if the output of the goal function is outside a pre-defined range, iteratively;

modifying the at least one initial expression in accordance with a search algorithm to produce at least one modified expression having the canonical form and being a function of the variables;

generating additional calculated data using the at least one modified expression; and

calculating an additional output of the goal function based on the additional calculated data and the pre-determined data, until the additional output of the goal function is within the pre-defined range.

2. The method of claim 1 wherein, the goal function is a single objective goal function for minimizing error.

3. The method of claim 1 wherein, the goal function is a multi-objective goal function for minimizing error and for minimizing complexity.

4. The method of claim 1 wherein, the goal function is a multi-objective goal function for minimizing error and for constraining complexity.

5. The method of claim 1 wherein, the goal function is a multi-objective goal function for constraining error and for constraining complexity.

6. The method of claim 1 wherein, the goal function is at least for minimizing a normalized root mean square error between the pre-determined data and either the calculated data generated using the at least one initial expression or the additional calculated data generated using the at least one modified expressions.

7. The method of claim 1 wherein, the variables of the system are representable as a vector {right arrow over (x)} and the canonical form of a expression F({right arrow over (x)}) is representable as

$F$

( x →

) = w offset + ∑

i = 0 n ⁢

w i ×

f i ⁡

( x →

) ×

NL i ⁡

( x →

) ,

“

n”

being an integer, w_offset being an offset value, w_i being weights, f_i({right arrow over (x)}) including at least one of a polynomial function of the variables and a rational function of the variables, and NL_i({right arrow over (x)}) being a non-linear function of the variables, with NL₀({right arrow over (x)})=1.

8. The method of claim 1 wherein, the pre-defined canonical form of is a sum of product of products of sums.

9. The method of claim 1 wherein, the pre-defined canonical form is a product of sums of sums of products.

10. The method of claim 1 wherein, the canonical form of an expression includes a linear addition having an offset value added to at least one product, each of the at least one product including a weight multiplying at least one of a polynomial function of the variables and a rational function of the variables, and multiplying at least one weighted linear addition.

11. The method of claim 1 wherein, the step of modifying the at least one initial expression in accordance with a search algorithm includes modifying the at least one initial expression in accordance with an evolutionary search algorithm to produce the at least one modified expression.

12. The method of claim 1 wherein, the step of modifying the at least one initial expression in accordance with a search algorithm includes modifying the at least one initial expression in accordance with a simulated annealing search algorithm to produce the at least one modified expression.

13. The method of claim 1 wherein, the step of modifying the at least one initial expression in accordance with a search algorithm includes modifying the at least one initial expression in accordance with a Tabu search algorithm to produce the at least one modified expression.

14. The method of claim 11 wherein, the goal function is an evolutionary multi-objective goal function.

15. The method of claim 1 wherein, a step of simplifying the at least one modified expression is performed before generating additional calculated data.

16. The method of claim 15, wherein the step of simplifying is done in accordance with a predicted sum of squares statistic process.

17. The method of claim 11 wherein, the at least one initial expression and the at least one modified expressions are representable as trees, the trees having a pre-determined depth and a pre-determined branchiness, some of the at least one initial expression and the at least one evolved expressions having introns.

18. The method of claim 11 wherein, the step of generating at least one initial expression and the step of modifying the at least one initial expression are performed in accordance with genetic programming principles.

19. The method of claim 1 wherein, the system is an electrical system.

20. The method of claim 1 wherein, the variables associated with the system include at least one of design variables, environmental variables and random variables.

21. A method to generate at least one expression describing a transient behavior of a system, the system associated with at least one pre-determined transient input waveform and with at least one pre-determined transient output waveform, the method comprising steps of:

generating at least one initial expression having a pre-defined canonical form and being a function of at least one of the at least one pre-determined transient input waveform and the at least one pre-determined transient output waveform;

generating calculated data using the at least one initial expression;

calculating an output of a goal function in accordance with the pre-determined data and the calculated data; and

if the output of the goal function is outside a pre-defined range, iteratively;

modifying the at least one initial expression in accordance with a search algorithm to produce at least one modified expression having the canonical form and being a function of at least one of the at least one pre-determined transient input waveform and the at least one pre-determined transient output waveform;

generating additional calculated data using the at least one modified expression; and

calculating an additional output of the goal function based on the additional calculated data and the pre-determined data, until the additional output of the goal function is within the pre-defined range.

22. A method to model an electrical circuit, the electrical circuit associated with circuit variables, with pre-determined data, with at least one pre-determined transient input waveform and with at least one pre-determined transient output waveform the method comprising steps of:

generating at least one initial expression dependent on at least one of at least one of the variables, at least one of the at least one pre-determined transient input waveform and at least one of the least one pre-determined transient output waveform, the at least one initial expression having a pre-defined canonical form;

generating calculated data using the at least one initial expression;

calculating an output of a goal function in accordance with the pre-determined data and the calculated data; and

if the output of the goal function is outside a pre-defined range, iteratively;

modifying the at least one initial expression in accordance with a search algorithm to produce at least one modified expression dependent on at least one of at least one of the variables, at least one of the at least one pre-determined transient input waveform and at least one of the least one pre-determined transient output waveform, the at least one modified expression having the canonical form;

generating additional calculated data using the at least one modified expression; and

calculating an additional output of the goal function based on the additional calculated data and the pre-determined data, until the additional output of the goal function is within the pre-defined range.

23. The method of claim 22 wherein, the pre-determined data includes at least one of steady-state electrical circuit data, transient electrical circuit data and noise electrical circuit data.

24. The method of claim 22 wherein, the electrical circuit is nonlinear.

25. The method of claim 22 wherein, the at least one initial expression and the at least one modified expression are independent of a connectivity topology of the electrical circuit.

26. The method of claim 22 wherein, the at least one initial expression and the at least one modified expression are symbolic models of the electrical circuit.

27. The method of claim 22 wherein, the at least one initial expression and the at least one modified expression are behavioral models of the electrical circuit.

28. An apparatus to provide a symbolic expression representing a characteristic of a system, the system associated with system variables and with pre-determined data related to the characteristic of the system, the apparatus comprising:

a generation and evolution (GE) module to generate and to evolve symbolic expressions having a pre-defined canonical form;

a first database in communication with the GE module, the first database storing rules regarding the pre-defined canonical form;

a second database in communication with the GE module, the second database storing pre-defined operators for use in generating and evolving the symbolic expressions;

an input connected to the GE module, the input to provide the system variables to the GE module, the GE module generating and evolving the symbolic expressions in accordance with the rules regarding the canonical form and with the pre-defined operators;

a goal function output calculator and evaluator (GFOCE) in communication with the GE module;

a data input in communication with the GFOCE, the data input to provide the pre-determined data to the GFOCE;

a goal function input in communication with the GFOCE, the goal function input to provide a goal function to the GFOCE, the GFOCE for calculating an output of the goal function and for comparing the output with a pre-determined target; and

an exit port in communication with the GFOCE and with the GE module, the exit port to provide the output of the goal function and the symbolic expression corresponding to the output of the goal function upon the output of the goal function concording with the pre-determined target.