Pattern search algorithm for component layout
First Claim
1. A method of performing a pattern based search, characterized by driving the search with a metric dependent on the change in an objective function.
1 Assignment
0 Petitions
Accused Products
Abstract
A solution to determining the move set ordering in pattern searching is disclosed that involves driving a pattern search algorithm by a metric other than the step size of the patterns. An instance of this metric is the amount of change in an objective function. Preprocessing algorithms are disclosed which quantify the effect each move has on the objective function. Those moves having a greater effect on the objective function are applied before moves having a lesser effect. We call this effect on the object function the sensitivity of the object function to a particular move and present several methods to quantify it. The sensitivity may be expressed as a function or the moves can be ranked and clustered with the pattern search being driven by the ranked moves or the function. The search may also be driven by an expected change in objective function. Because of the rules governing abstracts, this abstract should not be used to construe the claims.
25 Citations
36 Claims
- 1. A method of performing a pattern based search, characterized by driving the search with a metric dependent on the change in an objective function.
-
3. A method, comprising:
-
determining an expected change in value of an objective function due to each of a plurality of patterns; and
performing a pattern based search based on said determining. - View Dependent Claims (4, 5, 6)
-
-
7. A method, comprising:
-
selecting a set of patterns that spans a search space;
for each pattern in said set of patterns, determining a mapping between a step size of a pattern and an expected change in value of an objective function; and
driving a pattern search using the expected change in objective function. - View Dependent Claims (8, 9)
-
-
10. A preprocessing method, comprising:
deriving a mapping that relates step size of a pattern to the expected change in an objective function.
- 11. A storage device carrying an ordered set of instructions which, when executed, performs a pattern based search, characterized by driving the search with a metric dependent on the change in an objective function.
-
13. A storage device carrying an ordered set of instructions which, when executed, performs a method, comprising:
-
determining an expected change in value of an objective function due to each of a plurality of patterns; and
performing a pattern based search based on said determining. - View Dependent Claims (14, 15, 16)
-
-
17. A storage device carrying an ordered set of instructions which, when executed, performs a method, comprising:
-
selecting a set of patterns that spans a search space;
for each pattern in said set of patterns, determining a mapping between a step size of a pattern and an expected change in value of an objective function; and
driving a pattern search using the expected change in said objective function. - View Dependent Claims (18, 19)
-
-
20. A storage device carrying an ordered set of instructions which, when executed, performs a preprocessing method, comprising:
deriving a mapping that relates step size of a pattern to the expected change in an objective function.
-
21. A method, comprising:
-
determining a sensitivity metric due to each of a plurality of patterns; and
performing a pattern based search based on said determining. - View Dependent Claims (22, 23, 24)
-
-
25. A method, comprising:
-
selecting a set of patterns that spans a search space;
for each pattern in said set of patterns, determining a mapping between a step size of a pattern and the sensitivity metric; and
driving a pattern search using the sensitivity metric. - View Dependent Claims (26, 27)
-
-
28. A preprocessing method, comprising:
deriving a mapping that relates step size of a pattern to a sensitivity metric.
-
29. A storage device carrying an ordered set of instructions which, when executed, performs a method, comprising:
-
determining a sensitivity metric due to each of a plurality of patterns; and
performing a pattern based search based on said determining. - View Dependent Claims (30, 31, 32)
-
-
33. A storage device carrying an ordered set of instructions which, when executed, performs a method, comprising:
-
selecting a set of patterns that spans a search space;
for each pattern in said set of patterns, determining a mapping between a step size of a pattern and a sensitivity metric; and
driving a pattern search using the said sensitivity metric. - View Dependent Claims (34, 35)
-
-
36. A storage device carrying an ordered set of instructions which, when executed, performs a preprocessing method, comprising:
deriving a mapping that relates step size of a pattern to a sensitivity metric.
Specification