US6360191B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for automated design of complex structures using genetic programming
Assignee: Individual
•
Filing: 1999-01-05
•
Granted: 2002-03-19
•
Expires: 2019-01-05
Abstract
Abstract An automated design process and apparatus for use in designing complex structures, such as circuits, to satisfy prespecified design goals, using genetic operations. The present invention uses a population of entities which may be evolved to generate structures that may potentially satisfy the design goals. The behavior of such generated structures is evaluated in view of the design goals, and those structures more closely meeting the design goals are evolved further until a structure is generated that either meets the prespecified design goal or some other process completion criteria. In this manner, a design complex structure may be obtained.
Inventors
- 👤 John R. Koza
- 👤 Forrest H Bennett, III
- 👤 David Andre
- 👤 Martin A. Keane
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 15:21
CPC Classifications
G; G06; G06N; G06N3/00; G06N3/12; G06N3/126; G06F; G06F30/00; G06F30/30; G06F30/36; G06F2111/00; G06F2111/06; G06F2113/00; G06F2113/16
Claims Analysis
Total Claims: 78
Claim 1
Independent Claim
75 words
An iterative computer-implemented process for creating a structural design that satisfies prespecified design goals, said process invoking iterations, each iteration comprising the system-implemented operations of: developing a structure for each entity in a population of entities of various sizes and shapes by executing constructing actions in said each entity, the structure comprising a plurality of types of components in a topological arrangement with at least one component value, and determining behavior of each developed structure.
Claim 2
Dependent Claim
75 words
An iterative computer-implemented process for creating a structural design that satisfies prespecified design goals, said process invoking iterations, each iteration comprising the system-implemented operations of: developing a structure for each entity in a population of entities of various sizes and shapes by executing constructing actions in said each entity, the structure comprising a plurality of types of components in a topological arrangement with at least one component value, and determining behavior of each developed structure.
Claim 3
Dependent Claim
20 words
The process defined in claim 1 wherein executing the constructing actions comprises applying the constructing actions to an embryonic structure.
Claim 4
Dependent Claim
12 words
The process defined in claim 1 wherein the structure comprises a filter.
Claim 5
Dependent Claim
12 words
The process defined in claim 1 wherein the structure comprises an amplifier.
Claim 6
Dependent Claim
33 words
The process defined in claim 1 wherein executing constructing actions includes executing at least one constructing action to create a value of at least one component without use of an initially provided value.
Claim 7
Dependent Claim
21 words
The process defined in claim 1 further comprising determining the value of a component by executing functions of an arithmetic-performing sub-tree.
Claim 8
Dependent Claim
45 words
The process defined in claim 1 wherein executing at least one of the constructing actions produces an intermediate description of the structure in the form of a list of components, a list of connections between interface points of the components, and values of the components.
Claim 9
Dependent Claim
13 words
The process defined in claim 1 wherein determining behavior comprises simulating the structure.
Claim 10
Dependent Claim
30 words
The process defined in claim 1 wherein determining behavior comprises observing a physical realization representing the structure, the physical realization being constructed in response to execution of the constructing actions.
Claim 11
Dependent Claim
12 words
The process defined in claim 1 wherein the entities are program trees.
Claim 12
Dependent Claim
25 words
The process defined in claim 1 further comprising: choosing a genetic programming operation that creates a new entity, and performing the chosen genetic programming operation.
Claim 13
Dependent Claim
13 words
The process defined in claim 11 wherein the genetic programming operation comprises crossover.
Claim 14
Dependent Claim
28 words
The process defined in claim 1 wherein executing constructing actions comprises executing at least one of the constructing actions to change the topology of the structure being developed.
Claim 15
Dependent Claim
48 words
The process defined in claim 13 wherein executing at least one constructing action comprises duplicating a portion of the topology to create a duplicated portion, coupling the duplicated portion in series with the portion of the topology to form a composition, and replacing the portion with the composition.
Claim 16
Dependent Claim
50 words
The process defined in claim 13 wherein executing at least one of the constructing actions comprises duplicating a portion of the topology to create a duplicated portion, coupling the portion of the topology in parallel to the duplicated portion to create a composition, and replacing the portion with the composition.
Claim 17
Dependent Claim
62 words
The process defined in claim 13 wherein executing at least one of the constructing actions comprises creating at least two duplicated portions of a portion of the topology, coupling a first end of each of the at least two duplicated portions with one end of the portion of the topology to create a radiating composition, and replacing the portion with the composition.
Claim 18
Dependent Claim
64 words
The process defined in claim 13 wherein executing at least one of the constructing actions comprises creating at least two duplicates of a portion of the topology, coupling the at least two duplicates and the portion of the topology in a polygonal loop to create a looping composition comprising at least three portions, and replacing the portion of the topology with the looping composition.
Claim 19
Dependent Claim
34 words
The process defined in claim 1 wherein at least one of the entities in the population has a different hierarchical arrangement of constructing actions than that of another of the entities in the population.
Claim 20
Dependent Claim
34 words
The process defined in claim 1 further comprising removing an entity from the population based on the degree to which a developed structure associated with the entity fails to satisfy said prespecified design goals.
Claim 21
Dependent Claim
55 words
The process defined in claim 1 wherein entities in the population comprises sub-entities, wherein at least one of the sub-entities is externally invokable and at least one of the entities in the population has at least one internally invokable sub-entity, the at least one externally invokable sub-entity capable of including invocations of internally invokable sub-entities.
Claim 22
Dependent Claim
17 words
The process defined in claim 1 wherein at least one writing head is associated with a component.
Claim 23
Dependent Claim
14 words
The process defined in claim 1 wherein entities conform to a constrained syntactic structure.
Claim 24
Dependent Claim
34 words
The process defined in claim 1 wherein one entity of the population of entities comprises a context-sensitive constructing action, and wherein executing constructing actions in the one entity includes executing the context-sensitive constructing action.
Claim 25
Dependent Claim
12 words
The process defined in claim 1 wherein the structure comprises a circuit.
Claim 26
Dependent Claim
51 words
The process defined in claim 1 wherein the structure comprises a circuit, and wherein executing constructing actions in each entity develops a circuit with a topological arrangement of components with at least one component value in which at least one component is a resistor, capacitor, inductor, diode, transistor, or energy source.
Claim 27
Dependent Claim
17 words
The process defined in claim 25 wherein at least one writing head is associated with a component.
Claim 28
Dependent Claim
15 words
The process defined in claim 25 wherein the entities conform to a constrained syntactic structure.
Claim 29
Dependent Claim
28 words
The process defined in claim 25 wherein determining behavior comprises observing a physical realization of the circuit, the circuit constructed in response to execution of the constructing actions.
Claim 30
Dependent Claim
15 words
The process defined in claim 28 wherein the physical realization is a field programmable device.
Claim 31
Dependent Claim
18 words
The process defined in claim 29 wherein the field programmable device is a digital field programmable gate array.
Claim 32
Dependent Claim
17 words
The process defined in claim 29 wherein the field programmable device is a field programmable analog array.
Claim 33
Dependent Claim
17 words
The process defined in claim 29 wherein the field programmable device is a field programmable parts array.
Claim 34
Dependent Claim
47 words
The process defined in claim 1 wherein the structure comprises a circuit that obeys the law that the value of currents into each node where components meet sums to zero and obeys the law that values of voltage around each closed loop of components sums to zero.
Claim 35
Dependent Claim
13 words
The process defined in claim 1 wherein the structure comprises a non-clocked circuit.
Claim 36
Dependent Claim
37 words
The process defined in claim 1 wherein the structure comprises a circuit in which the voltage at each node is dependent on the voltage of all other nodes of said circuit at the same instant in time.
Claim 37
Dependent Claim
38 words
The process defined in claim 1 wherein the structure comprises a non-clocked circuit in which the current through a component is dependent on the current through all other components of the circuit at the same instant in time.
Claim 38
Dependent Claim
25 words
The process defined in claim 1 wherein the structure comprises a non-clocked circuit whose behavior, without considering any time delays in loops, is fully determined.
Claim 39
Dependent Claim
36 words
The process defined in claim 1 wherein the structure comprises a non-clocked circuit in which at least one component provides resistance, provides capacitance, provides inductance, provides bi-directional signal passage, functions like a transistor, or provides energy.
Claim 40
Dependent Claim
34 words
The process defined in claim 1 wherein the structure comprises a non-clocked circuit in which a signal present at one node can take on a value lying in a continuous range of real values.
Claim 41
Dependent Claim
93 words
An iterative computer-implemented process for creating a structural design that satisfies prespecified design goals, the process invoking iterations, each iteration comprising the system implemented operations of: executing constructing actions in each entity of a population of entities of various shapes and sizes to develop a structure for said each entity, the structure comprising a plurality of types of components in a topological arrangement with at least one component value, wherein executing the constructing actions comprises inserting components into a single developing structure for said each entity, and determining behavior of each developed structure.
Claim 42
Dependent Claim
93 words
An iterative computer-implemented process for creating a structural design that satisfies prespecified design goals, the process invoking iterations, each iteration comprising the system implemented operations of: executing constructing actions in each entity of a population of entities of various shapes and sizes to develop a structure for said each entity, the structure comprising a plurality of types of components in a topological arrangement with at least one component value, wherein executing the constructing actions comprises inserting components into a single developing structure for said each entity, and determining behavior of each developed structure.
Claim 43
Independent Claim
69 words
A system for creating a structural design that satisfies prespecified design goals, the system comprising: means for developing a structure for each entity in a population of entities of various sizes and shapes by executing constructing actions in said each entity, the structure comprising a plurality of types of components in a topological arrangement with at least one component value, and means for determining behavior of each developed structure.
Claim 44
Independent Claim
69 words
A system for creating a structural design that satisfies prespecified design goals, the system comprising: means for developing a structure for each entity in a population of entities of various sizes and shapes by executing constructing actions in said each entity, the structure comprising a plurality of types of components in a topological arrangement with at least one component value, and means for determining behavior of each developed structure.
Claim 45
Dependent Claim
24 words
The system defined in claim 41 wherein the means for developing the structure comprises means for applying the constructing actions to an embryonic structure.
Claim 46
Dependent Claim
38 words
The system defined in claim 41 wherein the means for developing the structure comprises means for executing at least one constructing action to create a value of at least one component without use of an initially provided value.
Claim 47
Dependent Claim
45 words
The system defined in claim 41 wherein executing at least one of the constructing actions produces an intermediate description of the structure in the form of a list of components, a list of connections between interface points of the components, and values of the components.
Claim 48
Dependent Claim
12 words
The system defined in claim 41 wherein the entities are program trees.
Claim 49
Dependent Claim
29 words
The system defined in claim 41 further comprising: means for choosing a genetic programming operation that creates a new entity, and means for performing the chosen genetic programming operation.
Claim 50
Dependent Claim
27 words
The system defined in claim 41 further comprising means for executing at least one of the constructing actions to change the topology of the structure being developed.
Claim 51
Dependent Claim
57 words
The system defined in claim 47 wherein the means for executing at least one constructing action comprises means for duplicating a portion of the topology to create a duplicated portion, means for coupling the duplicated portion in series with the portion of the topology to form a composition, and means for replacing the portion with the composition.
Claim 52
Dependent Claim
59 words
The system defined in claim 47 wherein the means for executing at least one of the constructing actions comprises means for duplicating a portion of the topology to create a duplicated portion, means for coupling the portion of the topology in parallel to the duplicated portion to create a composition, and means for replacing the portion with the composition.
Claim 53
Dependent Claim
66 words
The system defined in claim 47 wherein executing at least one of the constructing actions comprises creating at least two duplicated portions of a portion of the topology, means for coupling a first end of each of the at least two duplicated portions with one end of the portion of the topology to create a radiating composition, and means for replacing the portion with the composition.
Claim 54
Dependent Claim
68 words
The process defined in claim 47 wherein executing at least one of the constructing actions comprises creating at least two duplicates of a portion of the topology, means for coupling the at least two duplicates and the portion of the topology in a polygonal loop to create a looping composition comprising at least three portions, and means for replacing the portion of the topology with the looping composition.
Claim 55
Dependent Claim
17 words
The system defined in claim 47 wherein at least one writing head is associated with a component.
Claim 56
Dependent Claim
14 words
The system defined in claim 47 wherein entities conform to a constrained syntactic structure.
Claim 57
Dependent Claim
51 words
The system defined in claim 47 wherein the structure comprises a circuit, and wherein executing constructing actions in each entity develops a circuit with a topological arrangement of components with at least one component value in which at least one component is a resistor, capacitor, inductor, diode, transistor, or energy source.
Claim 58
Dependent Claim
17 words
The system defined in claim 47 wherein at least one writing head is associated with a component.
Claim 59
Dependent Claim
15 words
The system defined in claim 47 wherein the entities conform to a constrained syntactic structure.
Claim 60
Dependent Claim
47 words
The system defined in claim 47 wherein the structure comprises a circuit that obeys the law that the value of currents into each node where components meet sums to zero and obeys the law that values of voltage around each closed loop of components sums to zero.
Claim 61
Dependent Claim
13 words
The system defined in claim 47 wherein the structure comprises a non-clocked circuit.
Claim 62
Dependent Claim
37 words
The system defined in claim 47 wherein the structure comprises a circuit in which the voltage at each node is dependent on the voltage of all other nodes of said circuit at the same instant in time.
Claim 63
Dependent Claim
38 words
The system defined in claim 47 wherein the structure comprises a non-clocked circuit in which the current through a component is dependent on the current through all other components of the circuit at the same instant in time.
Claim 64
Dependent Claim
25 words
The system defined in claim 47 wherein the structure comprises a non-clocked circuit whose behavior, without considering any time delays in loops, is fully determined.
Claim 65
Dependent Claim
36 words
The system defined in claim 47 wherein the structure comprises a non-clocked circuit in which at least one component provides resistance, provides capacitance, provides inductance, provides bi-directional signal passage, functions like a transistor, or provides energy.
Claim 66
Dependent Claim
34 words
The system defined in claim 47 wherein the structure comprises a non-clocked circuit in which a signal present at one node can take on a value lying in a continuous range of real values.
Claim 67
Dependent Claim
89 words
A computer readable medium storing executable instructions thereon, which, when executed by at least one processing device, cause the at least one processing device to create a structural design that satisfies prespecified design goals by invoking interations that comprise: developing a structure for each entity in a population of entities of various sizes and shapes by executing constructing actions in each entity, the said structure comprising a plurality of types of components in a topological arrangement with at least one component value, and determining behavior of each developed structure.
Claim 68
Dependent Claim
89 words
A computer readable medium storing executable instructions thereon, which, when executed by at least one processing device, cause the at least one processing device to create a structural design that satisfies prespecified design goals by invoking interations that comprise: developing a structure for each entity in a population of entities of various sizes and shapes by executing constructing actions in each entity, the said structure comprising a plurality of types of components in a topological arrangement with at least one component value, and determining behavior of each developed structure.
Claim 69
Dependent Claim
20 words
The medium defined in claim 64 wherein executing the constructing actions comprises applying the constructing actions to an embryonic structure.
Claim 70
Dependent Claim
33 words
The medium defined in claim 64 wherein executing constructing actions includes executing at least one constructing action to create a value of at least one component without use of an initially provided value.
Claim 71
Dependent Claim
45 words
The medium defined in claim 64 wherein executing at least one of the constructing actions produces an intermediate description of the structure in the form of a list of components, a list of connections between interface points of the components, and values of the components.
Claim 72
Dependent Claim
12 words
The medium defined in claim 64 wherein the entities are program trees.
Claim 73
Dependent Claim
25 words
The medium defined in claim 64 further comprising: choosing a genetic programming operation that creates a new entity, and performing the chosen genetic programming operation.
Claim 74
Dependent Claim
28 words
The medium defined in claim 64 wherein executing constructing actions comprises executing at least one of the constructing actions to change the topology of the structure being developed.
Claim 75
Dependent Claim
48 words
The medium defined in claim 64 wherein executing at least one constructing action comprises duplicating a portion of the topology to create a duplicated portion, coupling the duplicated portion in series with the portion of the topology to form a composition, and replacing the portion with the composition.
Claim 76
Dependent Claim
50 words
The process defined in claim 64 wherein executing at least one of the constructing actions comprises duplicating a portion of the topology to create a duplicated portion, coupling the portion of the topology in parallel to the duplicated portion to create a composition, and replacing the portion with the composition.
Claim 77
Dependent Claim
62 words
The process defined in claim 64 wherein executing at least one of the constructing actions comprises creating at least two duplicated portions of a portion of the topology, coupling a first end of each of the at least two duplicated portions with one end of the portion of the topology to create a radiating composition, and replacing the portion with the composition.
Claim 78
Dependent Claim
64 words
The process defined in claim 64 wherein executing at least one of the constructing actions comprises creating at least two duplicates of a portion of the topology, coupling the at least two duplicates and the portion of the topology in a polygonal loop to create a looping composition comprising at least three portions, and replacing the portion of the topology with the looping composition.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-03-18 | 2005-09-17 | 2006-03-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-03-18 | 2009-09-17 | 2010-03-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-03-18 | 2013-09-17 | 2014-03-19 | $7700.00 | Window Closed / Lapsed |