US6424959B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for automatic synthesis, placement and routing of complex structures
Assignee: Individual
•
Filing: 1999-06-17
•
Granted: 2002-07-23
•
Expires: 2019-06-17
Abstract
Abstract The present invention consists of a method and apparatus for the automatic creation of the topology, component sizing, placement, and routing of complex structures, such as electronic circuits or mechanical systems, to satisfy prespecified high-level design goals. The present invention uses a population of entities which are evolved over a series of generations by an iterative process involving the application of operations, such as mutation, crossover, reproduction, and architecture-altering operations. The individuals in the population are each developed, in a developmental process, into a structure that may potentially satisfy the design goals. The present invention also determines the placement of components within the developing structure and determining the routing of the connecting means (wires for electrical circuits) between the components. The behavior of the structures is evaluated in relation to the high-level design goals, and those structures more closely satisfying the design goals are evolved further until a structure is generated that either meets the prespecified design goal. In this manner, the topology, component sizing, placement, and routing of a complex structure may be obtained.
Inventors
- 👤 Forrest H. Bennett, III
- 👤 John R. Koza
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 06:08
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/327; G06F30/39; G06F30/392; G06F30/394; Y; Y10; Y10S; Y10S706/00; Y10S706/902; Y10S706/919; Y10S706/921
Claims Analysis
Total Claims: 102
Claim 1
Independent Claim
155 words
In a system having at least one entity, wherein each entity comprises at least one constructing action, a system-implemented iterative process for creating a design of a structure that satisfies prespecified design goals, the iterative process comprising the iteration of a series of steps which comprises: executing at least one constructing action in the at least one entity to develop a structure comprising a plurality of components, the execution of the at least one constructing actions determining both the topological connections between components of the structure and the physical location of each of the components of the structure, ascertaining the degree to which the structure satisfies the prespecified design goals, selecting from among the at least one entity, wherein an entity that satisfies the prespecified design goals to a greater degree than another entity is preferred, creating at least one candidate entity by applying an operation to modify at least one of the selected entities.
Claim 2
Dependent Claim
155 words
In a system having at least one entity, wherein each entity comprises at least one constructing action, a system-implemented iterative process for creating a design of a structure that satisfies prespecified design goals, the iterative process comprising the iteration of a series of steps which comprises: executing at least one constructing action in the at least one entity to develop a structure comprising a plurality of components, the execution of the at least one constructing actions determining both the topological connections between components of the structure and the physical location of each of the components of the structure, ascertaining the degree to which the structure satisfies the prespecified design goals, selecting from among the at least one entity, wherein an entity that satisfies the prespecified design goals to a greater degree than another entity is preferred, creating at least one candidate entity by applying an operation to modify at least one of the selected entities.
Claim 3
Dependent Claim
28 words
The process defined in claim 1 wherein executing at least one constructing action comprises determining at least one value for at least one of the plurality of components.
Claim 4
Dependent Claim
25 words
The process defined in claim 1 wherein executing at least one constructing action comprises determining the physical location of connections between components of the structure.
Claim 5
Dependent Claim
25 words
The process defined in claim 1 wherein creating at least one candidate entity comprises performing a mutation operation on the at least one selected entity.
Claim 6
Dependent Claim
19 words
The process defined in claim 4 wherein selecting from among at least one entity is performed by simulating annealing.
Claim 7
Dependent Claim
19 words
The process defined in claim 4 wherein selecting from among at least one entity is performed by hill climbing.
Claim 8
Dependent Claim
17 words
The process defined in claim 1 wherein said at least one entity comprises a population of entities.
Claim 9
Dependent Claim
65 words
The process defined in claim 7 wherein creating at least one candidate entity comprises performing crossover among a group of at least two entities of the population, the group comprising a selected entity and at least one other entity from the population, wherein crossover is performed so that the new entity created comprises at least a portion of each of the at least two entities.
Claim 10
Dependent Claim
17 words
The process defined in claim 1 , wherein creating at least one candidate entity comprises performing reproduction.
Claim 11
Dependent Claim
18 words
The process defined in claim 7 wherein creating at least one candidate entity comprises performing an architecture-altering operation.
Claim 12
Dependent Claim
21 words
The process defined in claim 7 wherein selecting one of the at least one entity is performed by fitness proportionate selection.
Claim 13
Dependent Claim
20 words
The process defined in claim 7 wherein selecting one of the at least one entity is performed by tournament selection.
Claim 14
Dependent Claim
48 words
The process defined in claim 1 wherein at least one of entity comprises at least one externally invokable sub-entity and at least one internally invokable sub-entity, said at least one externally invokable sub-entity capable of including at least one invocation of said at least one internally invokable sub-entity.
Claim 15
Dependent Claim
44 words
The process defined in claim 13 wherein said at least one entity comprises at least two internally invokable sub-entities and wherein at least one of said internally invokable sub-entities is capable of including at least one invocation of another of said internally invokable sub-entities.
Claim 16
Dependent Claim
17 words
The process defined in claim 1 wherein said at least one entity comprises a randomly created entity.
Claim 17
Dependent Claim
19 words
The process defined in claim 1 wherein said at least one entity comprises an entity supplied to the process.
Claim 18
Dependent Claim
27 words
The process defined in claim 1 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises evaluating the entity by simulating the entity.
Claim 19
Dependent Claim
31 words
The process defined in claim 1 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises evaluating the entity by observing a physical realization of the entity.
Claim 20
Dependent Claim
20 words
The method defined in claim 1 wherein each of said at least one entities conforms to a constrained syntactic structure.
Claim 21
Dependent Claim
18 words
The process defined in claim 1 wherein each of said at least one entities is an electrical circuit.
Claim 22
Dependent Claim
11 words
The process defined in claim 20 wherein the connections comprise wires.
Claim 23
Dependent Claim
18 words
The process defined in claim 1 wherein each of said at least one entities is a mechanical system.
Claim 24
Dependent Claim
19 words
The process defined in claim 2 further comprises using an arithmetic-performing subtree to determine said at least one value.
Claim 25
Dependent Claim
26 words
The process defined in claim 2 further comprising using a number subject to perturbation by a Gaussian probability distribution to determine said at least one value.
Claim 26
Dependent Claim
27 words
The process defined in claim 1 further comprising determining physical location of each of the components of the structure after execution of constructing actions in the entity.
Claim 27
Dependent Claim
30 words
The process defined in claim 1 further comprising determining physical location components of the structure during a developmental process by progressively adjusting the physical location of at least one component.
Claim 28
Dependent Claim
44 words
The method defined in claim 1 further comprising adjusting the topology of the components by: determining a size of a first component within the structure; and adjusting positions of all other components in the structure to compensate for the size of the first component.
Claim 29
Dependent Claim
29 words
The process defined in claim 1 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises considering parasitic effects between the components of said structure.
Claim 30
Dependent Claim
32 words
The process defined in claim 1 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises considering the total area occupied by all the components of the structure.
Claim 31
Dependent Claim
26 words
The process defined in claim 1 wherein executing constructing actions comprises restraining execution of constructing actions to ensure components are physically located inside a prespecified area.
Claim 32
Dependent Claim
50 words
The process defined in claim 1 wherein the at least one entity comprises a population of entities, and further comprising: dividing the population entities into a plurality of groups; performing one or more operations of each iteration with respect to each entity in each group using a separate processing node.
Claim 33
Dependent Claim
57 words
An iterative computer-implemented process for creating a structural design that satisfies prespecified design goals, the process invoking iterations, each iteration comprising: developing a structure by executing constructing actions in an entity to simultaneously specify a topological arrangement of components, component values and placement of components with respect to each other; and determining behavior of the developed structure.
Claim 34
Dependent Claim
57 words
An iterative computer-implemented process for creating a structural design that satisfies prespecified design goals, the process invoking iterations, each iteration comprising: developing a structure by executing constructing actions in an entity to simultaneously specify a topological arrangement of components, component values and placement of components with respect to each other; and determining behavior of the developed structure.
Claim 35
Independent Claim
152 words
An apparatus, for creating a design of a structure that satisfies prespecified design goals, in a system having at least one entity, wherein each entity comprises at least one constructing action, the apparatus comprising: means for executing at least one constructing action in the at least one entity to develop a structure comprising a plurality of components, the execution of the at least one constructing actions determining both the topological connections between components of the structure and the physical location of each of the components of the structure; means for ascertaining the degree to which the structure satisfies the prespecified design goals; means for selecting from among the at least one entity, wherein an entity that satisfies the prespecified design goals to a greater degree than another entity is preferred; and means for creating at least one candidate entity by applying an operation to modify at least one of the selected entities.
Claim 36
Independent Claim
152 words
An apparatus, for creating a design of a structure that satisfies prespecified design goals, in a system having at least one entity, wherein each entity comprises at least one constructing action, the apparatus comprising: means for executing at least one constructing action in the at least one entity to develop a structure comprising a plurality of components, the execution of the at least one constructing actions determining both the topological connections between components of the structure and the physical location of each of the components of the structure; means for ascertaining the degree to which the structure satisfies the prespecified design goals; means for selecting from among the at least one entity, wherein an entity that satisfies the prespecified design goals to a greater degree than another entity is preferred; and means for creating at least one candidate entity by applying an operation to modify at least one of the selected entities.
Claim 37
Dependent Claim
33 words
The apparatus defined in claim 33 wherein the means for executing at least one constructing action comprises means for determining at least one value for at least one of the plurality of components.
Claim 38
Dependent Claim
30 words
The apparatus defined in claim 33 wherein the means for executing at least one constructing action comprises means for determining the physical location of connections between components of the structure.
Claim 39
Dependent Claim
30 words
The apparatus defined in claim 33 wherein the means for creating at least one candidate entity comprises means for performing a mutation operation on the at least one selected entity.
Claim 40
Dependent Claim
21 words
The apparatus defined in claim 36 wherein the means for selecting selects from among at least one entity using simulating annealing.
Claim 41
Dependent Claim
21 words
The apparatus defined in claim 36 wherein the means for selecting selects from among at least one entity using hill climbing.
Claim 42
Dependent Claim
17 words
The apparatus defined in claim 33 wherein said at least one entity comprises a population of entities.
Claim 43
Dependent Claim
70 words
The apparatus defined in claim 39 wherein the means for creating at least one candidate entity comprises means for performing crossover among a group of at least two entities of the population, the group comprising a selected entity and at least one other entity from the population, wherein crossover is performed so that the new entity created comprises at least a portion of each of the at least two entities.
Claim 44
Dependent Claim
21 words
The apparatus defined in claim 33 wherein the means for creating at least one candidate entity comprises means for performing reproduction.
Claim 45
Dependent Claim
23 words
The apparatus defined in claim 39 wherein the means for creating at least one candidate entity comprises means for performing an architecture-altering operation.
Claim 46
Dependent Claim
23 words
The apparatus defined in claim 39 wherein the means for selecting selects one of the at least one entity using fitness proportionate selection.
Claim 47
Dependent Claim
22 words
The apparatus defined in claim 39 wherein the means for selecting selects one of the at least one entity using tournament selection.
Claim 48
Dependent Claim
48 words
The apparatus defined in claim 33 wherein at least one of entity comprises at least one externally invokable sub-entity and at least one internally invokable sub-entity, said at least one externally invokable sub-entity capable of including at least one invocation of said at least one internally invokable sub-entity.
Claim 49
Dependent Claim
44 words
The apparatus defined in claim 45 wherein said at least one entity comprises at least two internally invokable sub-entities and wherein at least one of said internally invokable sub-entities is capable of including at least one invocation of another of said internally invokable sub-entities.
Claim 50
Dependent Claim
17 words
The apparatus defined in claim 33 wherein said at least one entity comprises a randomly created entity.
Claim 51
Dependent Claim
19 words
The apparatus defined in claim 33 wherein said at least one entity comprises an entity supplied to the process.
Claim 52
Dependent Claim
32 words
The apparatus defined in claim 33 wherein the means for ascertaining the degree to which an entity satisfies the prespecified design goals comprises means for evaluating the entity by simulating the entity.
Claim 53
Dependent Claim
36 words
The apparatus defined in claim 33 wherein the means for ascertaining the degree to which an entity satisfies the prespecified design goals comprises means for evaluating the entity by observing a physical realization of the entity.
Claim 54
Dependent Claim
20 words
The apparatus defined in claim 33 wherein each of said at least one entities conforms to a constrained syntactic structure.
Claim 55
Dependent Claim
18 words
The apparatus defined in claim 33 wherein each of said at least one entities is an electrical circuit.
Claim 56
Dependent Claim
11 words
The apparatus defined in claim 52 wherein the connections comprise wires.
Claim 57
Dependent Claim
18 words
The apparatus defined in claim 33 wherein each of said at least one entities is a mechanical system.
Claim 58
Dependent Claim
20 words
The apparatus defined in claim 34 further comprises means for determining said at least one value using an arithmetic-performing subtree.
Claim 59
Dependent Claim
27 words
The apparatus defined in claim 34 further comprising means for determining said at least one value using a number subject to perturbation by a Gaussian probability distribution.
Claim 60
Dependent Claim
29 words
The apparatus defined in claim 33 further comprising means for determining physical location of each of the components of the structure after execution of constructing actions in the entity.
Claim 61
Dependent Claim
32 words
The apparatus defined in claim 33 further comprising means for determining physical location components of the structure during a developmental process by progressively adjusting the physical location of at least one component.
Claim 62
Dependent Claim
55 words
The apparatus defined in claim 33 further comprising means for adjusting the topology of the components, wherein the means for adjusting comprises: means for determining a size of a first component within the structure; and means for adjusting positions of all other components in the structure to compensate for the size of the first component.
Claim 63
Dependent Claim
34 words
The apparatus defined in claim 33 wherein the means for ascertaining the degree to which an entity satisfies the prespecified design goals comprises means for considering parasitic effects between the components of said structure.
Claim 64
Dependent Claim
37 words
The apparatus defined in claim 33 wherein the means for ascertaining the degree to which an entity satisfies the prespecified design goals comprises means for considering the total area occupied by all the components of the structure.
Claim 65
Dependent Claim
31 words
The apparatus defined in claim 33 wherein the means for executing constructing actions comprises means for restraining execution of constructing actions to ensure components are physically located inside a prespecified area.
Claim 66
Dependent Claim
55 words
The apparatus defined in claim 33 wherein the at least one entity comprises a population of entities, and further comprising: means for dividing the population entities into a plurality of groups; and means for performing one or more operations of each iteration with respect to each entity in each group using a separate processing node.
Claim 67
Independent Claim
55 words
An apparatus for creating a structural design that satisfies prespecified design goals, the apparatus comprising: means for developing a structure by executing constructing actions in an entity to simultaneously specify a topological arrangement of components, component values and placement of components with respect to each other; and means for determining behavior of the developed structure.
Claim 68
Independent Claim
55 words
An apparatus for creating a structural design that satisfies prespecified design goals, the apparatus comprising: means for developing a structure by executing constructing actions in an entity to simultaneously specify a topological arrangement of components, component values and placement of components with respect to each other; and means for determining behavior of the developed structure.
Claim 69
Dependent Claim
158 words
A machine-readable medium having stored thereon executable code which causes a machine to perform a method, for creating a design of a structure that satisfies prespecified design goals, in a system having at least one entity, wherein each entity comprises at least one constructing action, the method comprising: executing at least one constructing action in the at least one entity to develop a structure comprising a plurality of components, the execution of the at least one constructing actions determining both the topological connections between components of the structure and the physical location of each of the components of the structure; ascertaining the degree to which the structure satisfies the prespecified design goals; selecting from among the at least one entity, wherein an entity that satisfies the prespecified design goals to a greater degree than another entity is preferred; and creating at least one candidate entity by applying an operation to modify at least one of the selected entities.
Claim 70
Dependent Claim
158 words
A machine-readable medium having stored thereon executable code which causes a machine to perform a method, for creating a design of a structure that satisfies prespecified design goals, in a system having at least one entity, wherein each entity comprises at least one constructing action, the method comprising: executing at least one constructing action in the at least one entity to develop a structure comprising a plurality of components, the execution of the at least one constructing actions determining both the topological connections between components of the structure and the physical location of each of the components of the structure; ascertaining the degree to which the structure satisfies the prespecified design goals; selecting from among the at least one entity, wherein an entity that satisfies the prespecified design goals to a greater degree than another entity is preferred; and creating at least one candidate entity by applying an operation to modify at least one of the selected entities.
Claim 71
Dependent Claim
29 words
The machine-readable medium defined in claim 65 wherein executing at least one constructing action comprises determining at least one value for at least one of the plurality of components.
Claim 72
Dependent Claim
26 words
The machine-readable medium defined in claim 65 wherein executing at least one constructing action comprises determining the physical location of connections between components of the structure.
Claim 73
Dependent Claim
26 words
The machine-readable medium defined in claim 65 wherein creating at least one candidate entity comprises performing a mutation operation on the at least one selected entity.
Claim 74
Dependent Claim
20 words
The machine-readable medium defined in claim 68 wherein selecting from among at least one entity is performed by simulating annealing.
Claim 75
Dependent Claim
20 words
The machine-readable medium defined in claim 68 wherein selecting from among at least one entity is performed by hill climbing.
Claim 76
Dependent Claim
18 words
The machine-readable medium defined in claim 65 wherein said at least one entity comprises a population of entities.
Claim 77
Dependent Claim
66 words
The machine-readable medium defined in claim 71 wherein creating at least one candidate entity comprises performing crossover among a group of at least two entities of the population, the group comprising a selected entity and at least one other entity from the population, wherein crossover is performed so that the new entity created comprises at least a portion of each of the at least two entities.
Claim 78
Dependent Claim
17 words
The machine-readable medium defined in claim 65 wherein creating at least one candidate entity comprises performing reproduction.
Claim 79
Dependent Claim
19 words
The machine-readable medium defined in claim 71 wherein creating at least one candidate entity comprises performing an architecture-altering operation.
Claim 80
Dependent Claim
22 words
The machine-readable medium defined in claim 71 wherein selecting one of the at least one entity is performed by fitness proportionate selection.
Claim 81
Dependent Claim
21 words
The machine-readable medium defined in claim 71 wherein selecting one of the at least one entity is performed by tournament selection.
Claim 82
Dependent Claim
49 words
The machine-readable medium defined in claim 65 wherein at least one of entity comprises at least one externally invokable sub-entity and at least one internally invokable sub-entity, said at least one externally invokable sub-entity capable of including at least one invocation of said at least one internally invokable sub-entity.
Claim 83
Dependent Claim
45 words
The machine-readable medium defined in claim 77 wherein said at least one entity comprises at least two internally invokable sub-entities and wherein at least one of said internally invokable sub-entities is capable of including at least one invocation of another of said internally invokable sub-entities.
Claim 84
Dependent Claim
20 words
The machine-readable medium readable medium defined in claim 65 wherein said at least one entity comprises a randomly created entity.
Claim 85
Dependent Claim
20 words
The machine-readable medium defined in claim 65 wherein said at least one entity comprises an entity supplied to the process.
Claim 86
Dependent Claim
28 words
The machine-readable medium defined in claim 65 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises evaluating the entity by simulating the entity.
Claim 87
Dependent Claim
32 words
The machine-readable medium defined in claim 65 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises evaluating the entity by observing a physical realization of the entity.
Claim 88
Dependent Claim
21 words
The machine-readable medium defined in claim 65 wherein each of said at least one entities conforms to a constrained syntactic structure.
Claim 89
Dependent Claim
19 words
The machine-readable medium defined in claim 65 wherein each of said at least one entities is an electrical circuit.
Claim 90
Dependent Claim
12 words
The machine-readable medium defined in claim 84 wherein the connections comprise wires.
Claim 91
Dependent Claim
21 words
The machine-readable medium defined in claim 65 wherein the method each of said at least one entities is a mechanical system.
Claim 92
Dependent Claim
23 words
The machine-readable medium defined in claim 66 wherein the method further comprises using an arithmetic-performing subtree to determine said at least one value.
Claim 93
Dependent Claim
30 words
The machine-readable medium defined in claim 66 wherein the method further comprises using a number subject to perturbation by a Gaussian probability distribution to determine said at least one value.
Claim 94
Dependent Claim
31 words
The machine-readable medium defined in claim 65 wherein the method further comprises determining physical location of each of the components of the structure after execution of constructing actions in the entity.
Claim 95
Dependent Claim
35 words
The machine-readable medium defined in claim 65 where in the method further comprises determining physical location components of the structure during a developmental process by progressively adjusting the physical location of at least one component.
Claim 96
Dependent Claim
48 words
The machine-readable medium defined in claim 65 wherein the method further comprises adjusting the topology of the components by: determining a size of a first component within the structure; and adjusting positions of all other components in the structure to compensate for the size of the first component.
Claim 97
Dependent Claim
30 words
The machine-readable medium defined in claim 65 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises considering parasitic effects between the components of said structure.
Claim 98
Dependent Claim
33 words
The machine-readable medium defined in claim 65 wherein ascertaining the degree to which an entity satisfies the prespecified design goals comprises considering the total area occupied by all the components of the structure.
Claim 99
Dependent Claim
27 words
The machine-readable medium defined in claim 65 wherein executing constructing actions comprises restraining execution of constructing actions to ensure components are physically located inside a prespecified area.
Claim 100
Dependent Claim
55 words
The machine-readable medium defined in claim 65 wherein the at least one entity comprises a population of entities, and wherein the method further comprises: dividing the population entities into a plurality of groups; and performing one or more operations of each iteration with respect to each entity in each group using a separate processing node.
Claim 101
Dependent Claim
65 words
A machine-readable medium having stored thereon executable code which causes a machine to perform a method, for creating a structural design that satisfies prespecified design goals, the method comprising: developing a structure by executing constructing actions in an entity to simultaneously specify a topological arrangement of components; component values and placement of components with respect to each other; and determining behavior of the developed structure.
Claim 102
Dependent Claim
65 words
A machine-readable medium having stored thereon executable code which causes a machine to perform a method, for creating a structural design that satisfies prespecified design goals, the method comprising: developing a structure by executing constructing actions in an entity to simultaneously specify a topological arrangement of components; component values and placement of components with respect to each other; and determining behavior of the developed structure.
References Cited (Backward Citations)
US5239643A
Cited
US4935877A
Cited
US5148513A
Cited
US5343554A
Cited
US5742738A
Cited
US5136686A
Cited
US5329464A
Cited
US5550839A
Cited
US5535134A
Cited
US5651099A
Cited
US5867397A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-07-22 | 2006-01-21 | 2006-07-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-07-22 | 2010-01-21 | 2010-07-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-07-22 | 2014-01-21 | 2014-07-23 | $7700.00 | Window Closed / Lapsed |