Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
5867397
Koza , ; et al.
February 2, 1999
Title
Method and apparatus for automated design of complex structures using genetic programming
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:
Koza; John R.
(Los Altos Hills,
CA
)
, Bennett, III; Forrest H.
(Palo Alto,
CA
)
, Andre; David
(Menlo Park,
CA
)
Assignee:
Koza; John R.
(Los Altos Hills,
CA
)
Appl. No.:
603648
Filed:
February 20, 1996
Current U.S. Class:
703/14
703/2
706/13
Field of Search:
364/488-491,492,468,493,513,489,490 395/10,13 706/13
U.S. Patent Documents
4479241
October 1984
Buckley
4675829
June 1987
Clemenson
4697242
September 1987
Holland et al.
4821333
April 1989
Gillies
4935877
June 1990
Koza
5136686
August 1992
Koza
5343554
August 1994
Koza et al.
5390282
February 1995
Koza et al.
5557533
September 1996
Koford et al.
5581657
December 1996
Lyon
5623418
April 1997
Rostoker et al.
5742738
April 1998
Koza et al.
Foreign Patent Documents
0 254 825A2
Mar., 1988
EP
Other References
Dress, W. B., "Darwinian Optimization of Synethic Neural Systems", IEEE First International Conference on Neural Networks, San Diego, Jun. 1987, vol. No. 3, pp. 769-775. .
Grefenstette, John J., Proceedings of the First International Conference on Genetic Algorithms and Their Applications, Jul. 24-26, 1985, Lawrence Erlbaum Associates, Hillsdale, New Jersey. .
Hicklin, Joseph F., "Application of the Genetic Algorithm to Automatic Program Generation" A Thesis Presented in Partial Fulfillment of the Requirements for the Degree of Master of Science, Apr., 1986, Graduate School of University of Idaho. .
Holland, John H., "Adaptation in Natural and Artificial Systems", The MIT Press, Cambridge Massachusetts, London, England 1992. .
Grefenstette, John J., Proc. of the Second International Conference on Genetic Algorithms, Jul. 28-31, 1987, Lawrence Erlbaum Associates, Hillsdale, New Jersey. .
P.J. Angeline and J. B. Pollack, "The Evolutionary Induction of Subroutines", Proc. of the Fourteenth Annual Conf. of the Cognitive Science Society, Jul. 29-Aug. 1, 1992, pp. 236-241. .
A. S. Bickel and R.W. Bickel, "Tree Structured Rules in Genetic Algorithms", Proc. of the 2nd Int. Conference on Genetic Algrothims, Jul. 28-Jul. 31, 1987, pp. 77-81. .
G.E.P. Box, "Evolutionary Operation:
Primary Examiner:
Tesk; Kevin J.
Assistant Examiner:
Siek; Vuthe
Attorney, Agent or Firm:
Blakely, Sokoloff, Taylor & Zafman LLP
Claims
We claim:
1. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a structure that satisfies prespecified design goals, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity to develop a structure comprising a plurality of types of components in a topological arrangement with at least one component value,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
2. The method defined in claim 1 wherein the step of executing the constructing actions comprises applying the constructing actions to an embryonic structure.
3. The method defined in claim 1 wherein the structure comprises a filter.
4. The method defined in claim 1 wherein the structure comprises an amplifier.
5. The method defined in claim 1 wherein the step of executing constructing actions includes executing at least one constructing action to create a value of at least one of said components without use of an initially provided value.
6. The method defined in claim 5 further comprising the step of determining the value of at least one component by executing functions of an arithmetic-performing sub-tree.
7. The method defined in claim 1 wherein said constructing actions produce an intermediate description of said structure in the form of a list of components, a list of connections between interface points of said components, and values of said components.
8. The method defined in claim 1 wherein the step of determining behavior comprises simulating said structure.
9. The method defined in claim 1 wherein said step of determining behavior comprises observing a physical realization representing said structure, said physical realization constructed in response to execution of said constructing actions.
10. The method defined in claim 1 wherein said entities are program trees of constructing actions.
11. The method defined in claim 1 wherein if said operation is mutation, then selecting one entity and mutating said selected entity, such that at least one portion of said selected entity is replaced by a randomly generated portion to produce a new entity.
12. The method defined in claim 1 wherein if said operation is an architecture altering operation, then altering the architecture of at least one of the population of entities.
13. The method defined in claim 1 wherein the step of executing constructing actions comprises executing at least one of the constructing actions to change the topology of the structure being developed through execution of the constructing actions.
14. The method defined in claim 13 wherein the step of 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.
15. The method defined in claim 13 wherein the step of 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.
16. The method defined in claim 13 wherein the step of 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.
17. The method defined in claim 13 wherein the step of 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.
18. The method defined in claim 1 wherein at least one of said entities in said population has a different hierarchical arrangement of constructing actions than that of another of said entities in said population.
19. The method defined in claim 1 further comprising a step of removing at least one entity based on the degree to which said developed structure associated with said entity fails to satisfy said prespecified design goals.
20. The method defined in claim 1 wherein each of said entities is comprised of sub-entities, wherein at least one of said sub-entities is externally invokable and at least one of said entities in the population has at least one internally invokable sub-entity, said at least one externally invokable sub-entity capable of including invocations of internally invokable sub-entities.
21. The method defined in claim 1 wherein at least one writing head is associated with a component.
22. The method defined in claim 1 wherein said entities conform to a constrained syntactic structure.
23. The method defined in claim 1 wherein the step of executing the constructing actions comprises executing at least one constructing action to reverse polarity of at least one component in the topology.
24. The method defined in claim 2 wherein said embryonic structure has an identifiable property and said constructing actions preserve said identifiable property.
25. The method defined in claim 24 wherein said identifiable property is that components of said structure constitute a graphical structure in which each interface point of each component is connected to either one or two interface points of other components of said structure.
26. The method defined in claim 1 wherein the step of determining the behavior of said developed structure comprises measuring the degree to which behavior of said developed structure satisfies the design goals in terms of a degree of closeness between an output of the developed structure in response to specified input and a desired output in response to the specified input.
27. In a system having a population of entities, wherein each entity comprises at least one context-sensitive constructing action, an iterative process for creating a design of a structure that satisfies prespecified design goals, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity, including said at least one context-sensitive constructing action, to develop a structure in a topological arrangement with component values,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
28. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a circuit that satisfies prespecified design goals, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity to develop a circuit designed to include a plurality of types of components in a topological arrangement with at least one component value,
determining behavior of said developed circuit structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
29. The method defined in claim 28 wherein at least one of said components is a subcircuit.
30. The method defined in claim 28 wherein the circuit comprises a filter.
31. The method defined in claim 28 wherein the circuit comprises an amplifier.
32. The method defined in claim 28 further comprising executing a mutation operation if the chosen operation is mutation.
33. The method defined in claim 28 wherein the step of executing constructing actions includes executing at least one constructing action to create a value of at least one of said components without use of an initially provided value.
34. The method defined in claim 33 further comprising the step of determining the value of at least one component by executing functions of an arithmetic-performing sub-tree.
35. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a circuit that satisfies prespecified design goals, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity to develop 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;
determining behavior of said developed circuit,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
36. The method defined in claim 35 wherein the step of executing the constructing actions comprises applying the constructing actions to an embryonic structure.
37. The method defined in claim 35 wherein the circuit comprises a filter.
38. The method defined in claim 35 wherein the circuit comprises an amplifier.
39. The method defined in claim 35 wherein the step of executing constructing actions includes executing at least one constructing action to create a value of at least one of said components without use of an initially provided value.
40. The method defined in claim 39 further comprising the step of determining the value of at least one component by executing functions of an arithmetic-performing sub-tree.
41. The method defined in claim 35 wherein said constructing actions produce a netlist of said circuit in the form of a list of components, a list of connections between the interface points of said components, and the value of said components.
42. The method defined in claim 35 wherein the step of determining behavior comprises simulating said structure.
43. The method defined in claim 35 wherein said step of determining behavior comprises observing a physical realization representing said structure, said physical realization constructed in response to execution of said constructing actions.
44. The method defined in claim 35 wherein said entities are program trees of constructing actions.
45. The method defined in claim 35 wherein if one of said operations is mutation, then selecting an entity and mutating said selected entity, such that at least one portion of said selected entity is replaced by a randomly generated portion to produce a new entity.
46. The method defined in claim 35 wherein one of said operations alters the architecture of at least one of the population of entities.
47. The method defined in claim 35 wherein the step of executing constructing actions comprises executing at least one of the constructing actions to change the topology of the structure being developed through execution of the constructing actions.
48. The method defined in claim 35 wherein the step of 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.
49. The method defined in claim 35 wherein the step of 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.
50. The method defined in claim 35 wherein the step of 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.
51. The method defined in claim 35 wherein the step of 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.
52. The method defined in claim 35 wherein at least one of said entities in said population has a different hierarchical arrangement of constructing actions than that of another of said entities in said population.
53. The method defined in claim 35 further comprising a step of removing at least one entity based on the degree to which said developed structure associated with said entity fails to satisfy said prespecified design goals.
54. The method defined in claim 35 wherein each of said entities is comprised of sub-entities, wherein at least one of said sub-entities is externally invokable and at least one of said entities in the population has at least one internally invokable sub-entity, said at least one externally invokable sub-entity capable of including invocations of internally invokable sub-entities.
55. The method defined in claim 35 wherein at least one writing head is associated with a component.
56. The method defined in claim 35 wherein said entities conform to a constrained syntactic structure.
57. The method defined in claim 43 wherein said physical realization is a field programmable device.
58. The method defined in claim 57 wherein said field programmable device is a digital field programmable gate array.
59. The method defined in claim 57 wherein said field programmable device is a field programmable analog array.
60. The method defined in claim 57 wherein said field programmable device is a field programmable parts array.
61. The method defined in claim 35 wherein the step of executing the constructing actions comprises executing at least one constructing action to reverse polarity of at least one component in the topology.
62. The method defined in claim 35 further comprising executing a mutation operation if the chosen operation is mutation.
63. The method defined in claim 35 wherein the step of determining the behavior of said developed structure comprises measuring the degree to which behavior of said developed structure satisfies the design goals in terms of a degree of closeness between an output of the developed circuit in response to specified input and a desired output in response to the specified input.
64. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a structure that satisfies prespecified design goals, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity to develop a circuit with a topological arrangement of components with at least one component value, where the circuit 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,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
65. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a structure that satisfies prespecified design goals, said process comprising iterations of a series of steps, each iteration comprising the steps of:
executing constructing actions in said entity to develop a structure with a topological arrangement of components with at least one component value, wherein the structure obeys the law that the forces acting on each node where components meet sums to zero,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
66. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a non-clocked circuit that satisfies prespecified design goals, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity to develop a non-clocked circuit comprising components in a topological arrangement with at least one component value,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
67. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a circuit that satisfies prespecified design goals and 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, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity to develop a circuit comprising components in a topological arrangement with at least one component value, and 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,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation, if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
68. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a circuit that satisfies prespecified design goals in which the current through a component is dependent on the current through all other components of said circuit at the same instant in time, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity to develop a circuit comprising components in a topological arrangement with at least one component value, and in which the current through a component is dependent on the current through all other components of said circuit at the same instant in time,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
69. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a circuit that satisfies prespecified design goals and whose behavior is, without considering any time delays in loops, fully determined, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity to develop a circuit comprising components in a topological arrangement with at least one component value, and whose behavior, without considering any time delays in loops, fully determined,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
70. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a circuit that satisfies prespecified design goals, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity to develop a circuit with a topological arrangement of components with at least one component value in which at least one component provides resistance, provides capacitance, provides inductance, provides bidirectional signal passage, functions like a transistor, or provides energy;
determining behavior of said developed circuit structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said, prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
71. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a circuit that satisfies prespecified design goals and in which a signal present at one node can take on a value lying in a continuous range of real values, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity to develop a circuit that satisfies prespecified design goals comprising components in a topological arrangement with at least one component value and in which a signal present at one node can take on a value lying in a continuous range of real values,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
72. The method defined in claim 71 wherein the step of executing the constructing actions comprises applying the constructing actions to an embryonic structure.
73. The method defined in claim 71 wherein one of said operations alters the architecture of at least one of the population of entities.
74. The method defined in claim 71 wherein each of said entities is comprised of sub-entities, wherein at least one of said sub-entities is externally invokable and at least one of said entities in the population has at least one internally invokable sub-entity, said at least one externally invokable sub-entity capable of including invocations of internally invokable sub-entities.
75. The method defined in claim 71 wherein said entities conform to a constrained syntactic structure.
76. The method defined in claim 71 wherein said step of determining behavior comprises observing a physical realization representing said structure, said physical realization constructed in response to execution of said constructing actions.
77. The method defined in claim 63 wherein the step of executing constructing actions includes executing at least one constructing action to create a value of at least one of said components without use of an initially provided value.
78. The method defined in claim 77 further comprising the step of determining the value of at least one component by executing functions of an arithmetic-performing sub-tree.
79. The method defined in claim 71 wherein the structure comprises a filter.
80. The method defined in claim 71 wherein the structure comprises a amplifier.
81. The method defined in claim 71 wherein the structure comprises a amplifier.
82. The method defined in claim 71 wherein the step of executing the constructing actions comprises executing at least one constructing action to reverse polarity of at least one component in the topology.
83. The method defined in claim 71 wherein at least one of said entities in said population has a different hierarchical arrangement of constructing actions than that of another of said entities in said population.
84. The method defined in claim 71 wherein the step of determining the behavior of said developed structure comprises measuring the degree to which behavior of said developed structure satisfies the design goals in terms of a degree of closeness between an output of the developed structure in response to specified input and a desired output in response to the specified input.
85. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a circuit that satisfies prespecified design goals, said process comprising iterations of a series of steps, each iteration comprising the system-implemented steps of:
executing constructing actions in said entity to develop a circuit comprising components in a topological arrangement with at least one component value and with at least one component having at least three leads,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation, if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
86. The method defined in claim 85 wherein the step of executing the constructing actions comprises applying the constructing actions to an embryonic structure.
87. The method defined in claim 85 wherein one of said operations alters the architecture of at least one of the population of entities.
88. The method defined in claim 85 wherein each of said entities is comprised of sub-entities, wherein at least one of said sub-entities is externally invokable and at least one of said entities in the population has at least one internally invokable sub-entity, said at least one externally invokable sub-entity capable of including invocations of internally invokable sub-entities.
89. The method defined in claim 85 wherein said entities conform to a constrained syntactic structure.
90. The method defined in claim 85 wherein said step of determining behavior comprises observing a physical realization representing said structure, said physical realization constructed in response to execution of said constructing actions.
91. The method defined in claim 85 wherein the step of executing constructing actions includes executing at least one constructing action to create a value of at least one of said components without use of an initially provided value.
92. The method defined in claim 91 further comprising the step of determining the value of at least one component by executing functions of an arithmetic-performing sub-tree.
93. The method defined in claim 85 wherein the structure comprises a filter.
94. The method defined in claim 85 wherein the step of executing the constructing actions comprises executing at least one constructing action to reverse polarity of at least one component in the topology.
95. The method defined in claim 85 wherein at least one of said entities in said population has a different hierarchical arrangement of constructing actions than that of another of said entities in said population.
96. The method defined in claim 85 wherein the step of determining the behavior of said developed structure comprises measuring the degree to which behavior of said developed structure satisfies the design goals in terms of a degree of closeness between an output of the developed structure in response to specified input and a desired output in response to the specified input.
97. In a system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, an iterative process for creating a design of a structure that satisfies prespecified design goals, said process comprising iterations of a series of steps, each iteration comprising the steps of:
executing constructing actions in said entity to develop a circuit with a topological arrangement of components with at least one component value, wherein the circuit includes a portion whose behavior is a continuous function of time without discrete time steps,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
98. A system having a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, the system creating a design of a structure that satisfies prespecified design goals, said system comprising:
means for executing constructing actions in said entity to develop a structure comprising a plurality of types of components in a topological arrangement with at least one component value,
means for determining behavior of said developed structure,
means for choosing an operation that creates a new entity,
means for selecting a group of at least two entities from said population if said chosen operation is crossover, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
means for performing said chosen crossover operation,
means for selecting one entity from said population if said chosen operation is reproduction, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
means for performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
means for adding said entity created by said chosen operation to said population.
99. The system defined in claim 98 wherein the means for executing the constructing actions comprises means for applying the constructing actions to an embryonic structure.
100. The system defined in claim 98 wherein said constructing actions produce an intermediate description of said structure in the form of a list of components, a list of connections between interface points of said components, and values of said components.
101. The system defined in claim 98 wherein the means for determining behavior comprises means for simulating said structure.
102. The system defined in claim 98 wherein the means for determining behavior comprises means for observing a physical realization representing said structure, said physical realization constructed in response to execution of said constructing actions.
103. The system defined in claim 98 wherein said entities are program trees of constructing actions.
104. The system defined in claim 98 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.
105. The system defined in claim 98 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.
106. The system defined in claim 98 wherein the means for executing at least one of the constructing actions comprises means for 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.
107. The system defined in claim 98 wherein the means for executing at least one of the constructing actions comprises means for 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.
108. The system defined in claim 98 wherein at least one of said entities in said population has a different hierarchical arrangement of constructing actions than that of another of said entities in said population.
109. The system defined in claim 98 wherein the step of determining the behavior of said developed structure comprises measuring the degree to which behavior of said developed structure satisfies the design goals in terms of a degree of closeness between an output of the developed structure in response to specified input and a desired output in response to the specified input.
110. A computer readable medium for use with a population of entities of various sizes and shapes, wherein each entity comprises at least one constructing action, said computer readable medium containing executable program instructions for performing an iterative process to create a design of a structure that satisfies prespecified design goals, said process comprising iterations of a series of steps, each iteration comprising the steps of:
executing constructing actions in said entity to develop a structure comprising a plurality of types of components in a topological arrangement with at least one component value,
determining behavior of said developed structure,
choosing an operation that creates a new entity,
if said chosen operation is crossover,
selecting a group of at least two entities from said population, with the selection of at least one of said selected entities based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen crossover operation,
if said chosen operation is reproduction,
selecting one entity from said population, with said selected entity based on the degree to which said developed structure associated with said entity satisfies said prespecified design goals,
performing said chosen reproduction operation, said reproduction operation retaining said selected entity unchanged in said population, and
adding said entity created by said chosen operation to said population.
111. The computer readable medium defined in claim 110 wherein the step of executing the constructing actions comprises applying the constructing actions to an embryonic structure.
112. The computer readable medium defined in claim 110 wherein said constructing actions produce an intermediate description of said structure in the form of a list of components, a list of connections between interface points of said components, and values of said components.
113. The computer readable medium defined in claim 110 wherein the step of determining behavior comprises simulating said structure.
114. The computer readable medium defined in claim 110 wherein said step of determining behavior comprises observing a physical realization representing said structure, said physical realization constructed in response to execution of said constructing actions.
115. The computer readable medium defined in claim 110 wherein the step of executing at least one constructing action causes a portion of the topology to be duplicated and coupled so as to put the portion and the duplicated portion in series with each other and replacing the portion.
116. The computer readable medium defined in claim 110 wherein the step of executing one of the constructing actions to cause change in the topology comprises duplicating a portion of the topology causing a duplicate of the portion to be inserted in the topology so as to be in parallel with the portion.
117. The computer readable medium defined in claim 110 wherein the step of executing comprises duplicating a portion of the topology twice, coupling the two duplicated portions in parallel to each other, and coupling the two parallel duplicated portions in series with the portion.
118. The computer readable medium defined in claim 110 wherein the step of determining the behavior of said developed structure comprises measuring the degree to which behavior of said developed structure satisfies the design goals in terms of a degree of closeness between an output of the developed structure in response to specified input and a desired output in response to the specified input.
Description
FIELD OF THE INVENTION
The field of the invention is the automated design of complex structures, such as electrical circuits; more particularly, the present invention relates to designing complex structures, such as electrical circuits, using computer-implemented genetic algorithms.
BACKGROUND OF THE INVENTION
The automated design of complex structures that satisfy a designer's requirements is a challenging task that is ordinarily thought to require human intelligence.
Electrical engineers are often called upon to design circuits that satisfy certain design goals or requirements. Electrical circuits consist of a wide variety of different types of components, including resistors, capacitors, inductors, diodes, transistors, transformers, and energy sources. The individual components of an electrical circuit are arranged in a particular "topology" to form a circuit.
Various types of components may be inserted at each location within the circuit's topological arrangement. In addition, each component is further specified ("sized") by a set of component values (typically numerical). A complete specification of an electrical circuit includes its topology, the choice of component types to be inserted at each location within the topology, and the sizing of all of its components.
In designing a circuit, the goal is to attain certain desired values of one or more observable quantities (e.g., an observed pattern of voltages at certain times or at certain frequencies at a certain probe point in the circuit). Often there are one or more additional considerations (e.g., number of components in the circuit, cost of the components, etc.).
Similarly, mechanical and civil engineers are often called upon to design physical structures that satisfy certain design goals or requirements. Physical structures, like electrical circuits, consist of a variety of different types of components. These individual components may be arranged in a particular topology to form the overall complex physical structure. Various types of components may be inserted at each location within the topological arrangement. Each component in the overall structure may be further specified by a set of component values (typically numerical). For example, a mechanical engineer may want to design as truss consisting of components such as rigid load-supporting metallic beams and load-supporting flexible cables. The design goals may be to support a particular load or loads and of satisfying a requirement that the stress on each bar or cable is not so great as to cause the rigid bar or flexible cable to break. Finally, there may be an additional design goal that the entire physical structure meets some cost requirement, such as minimizing the total weight of the material contained in the truss. In order to design the desired truss, the designer must create an appropriate topological arrangement of components (i.e., the number of components and how they are joined), choose component types (i.e., rigid beams or flexible cables) to insert into the topological arrangement, and choose appropriate numerical values (i.e., their thickness) for each of the components.
Both the above electrical and mechanical design problems and many other design problems from many other fields share the common feature of requiring the designer to create an appropriate topological arrangement of components, to choose component types to insert into the topological arrangement, and to choose appropriate numerical values for each of the components in the overall complex structure.
THE NATURAL SELECTION PROCESS IN NATURE
In nature, biological entities exhibit a wide variety of structures that survive and prosper in various environments. Nature's methods for designing biological entities to meet the requirements of their natural environment provides a useful model for designing complex structures.
Most structures and behaviors in living things are the consequence of the actions and interactions of proteins. In fact, proteins are responsible for such a wide variety of biological structures and behaviors that it can be said that the structure and functions of living organisms are primarily determined by proteins. Proteins are polypeptide molecules composed of sequences of amino acids. There are 20 amino acid residues (denoted by the letters A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, and Y) from which protein molecules are constructed. Protein molecules are, in turn, made up of an average of about 300 such amino acid residues (with large proteins containing thousands of amino acid residues). Simple bacteria sustain life with as few as 1,800 different proteins while humans have an estimated 100,000 proteins.
Proteins are manufactured in accordance with instructions and information contained in the chromosomal DNA of the organism. DNA (deoxyribonucleic acid) is a long thread-like biological molecule that has the ability to carry hereditary information and the ability to serve as a model for the production of replicas of itself. All known life forms on this planet (including bacteria, fungi, plants, animals, and humans) are based on the DNA molecule. In nature, a gene is the basic functional unit by which hereditary information is passed from parents to offspring. Genes appear at particular places along molecules of deoxyribonucleic acid (DNA).
The so-called "genetic code" involving the DNA molecule consists of long strings (sequences) of 4 possible values that can appear at the various loci along the DNA molecule. For DNA, the 4 possible values refer to 4 "bases" named adenine, guanine, cytosine, and thymine (usually abbreviated as A, G, C, and T, respectively). Thus, the "genetic code" in DNA consists of long strings such as CTCGACGGT. When living cells reproduce, the genetic code in DNA is read. Sub-sequences (called "codons") consisting of 3 DNA bases specify one of 20 amino acids. Thus, the genetic code is used to specify and control the building of proteins from the information and instructions contained in the DNA molecule.
Organisms consist of living cells, each containing thousands of interacting proteins, spend their lives attempting to deal with their environment. Some organisms do better than others in dealing with their environment. In particular, some organisms survive to the age of reproduction and can then thereby pass on their genetic make-up (i.e., their genes) to their offspring. Natural selection is the process by which organisms whose traits facilitate survival to the age of reproduction pass on all or part of their genetic make-up to offspring (Darwin 1859). Over a period of time and many generations, the population as a whole evolves so that the chromosome strings in the individuals in the surviving population perpetuate traits that contribute to the survival of the organism in its environment. That is, the natural selection process tends to evolve, over a period of time, structures that are designed so as to deal effectively with their environment.
GENETIC ALGORITHMS
A genetic algorithm provides a method of improving a given set of objects. The processes of natural selection and survival of the fittest provide a theoretical base for the genetic algorithm. Adaptation in Artificial and Natural Systems, by Professor John H. Holland (1975), summarizes and presents an overall mathematical theory of adaptation for both natural and artificial systems. A key part of Holland's book described a "genetic algorithm" patterned after nature's methods for biological adaptation. In later work, Holland (1986) described a classifier system that employed a genetic algorithm and a bucket brigade algorithm to solve problems. U.S. Pat. No. 4,697,242 (Holland et al.) and U.S. Pat. No. 4,881,178 (Holland et al.) describe classifier systems that use fixed length binary strings in conjunction with a genetic algorithm.
GENETIC PROGRAMMING
"Genetic programming" (also called the "non-linear genetic algorithm" or the "hierarchical genetic algorithm" in previous years) is described in the book entitled Genetic Programming: On the Programming of Computers by Means of Natural Selection (Koza 1992), the book entitled Genetic Programming II: Automatic Discovery of Reusable Programs (Koza 1992) and in U.S. Pat. Nos. 4,935,877, 5,136,686, 5,148,513, and 5,343,554.
Genetic programming is referred to as "non-linear" or "hierarchical" because the original genetic algorithm described by Holland in 1975 operated on linear strings of characters (resembling chromosomes in nature), whereas genetic programming operates on hierarchical program trees of various sizes and shapes.
Genetic programming is capable of evolving computer programs that solve, or approximately solve, a variety of problems from a variety of fields. Genetic programming starts with a primordial ooze of randomly generated programs composed of the available programmatic ingredients and then applies the principles of animal husbandry to breed a new (and often improved) population of programs. The breeding is done in a domain-independent way using the Darwinian principle of survival of the fittest, an analog of the naturally-occurring genetic operation of crossover (sexual recombination), and occasional mutation. The crossover operation is designed to create syntactically valid offspring programs (given closure amongst the set of ingredients). Genetic programming combines the expressive high-level symbolic representations of computer programs with the near-optimal efficiency of learning associated with Holland's genetic algorithm. A program that solves (or approximately solves) a given problem often emerges from this process.
As demonstrated in the book, Genetic Programming II: Automatic Discovery of Reusable Programs (Koza 1994) genetic programming can evolve multi-part programs consisting of a main program and one or more reusable, parameterized, hierarchically-called subprograms (called automatically defined functions or ADFs).
Genetic programming breeds computer programs to solve problems by executing the following three steps:
(1) Generate an initial population of random compositions of the functions and terminals of the problem (i.e., computer programs).
(2) Iteratively perform the following substeps until the termination criterion has been satisfied:
(A) Execute each program in the population and assign it a fitness value using the fitness measure.
(B) Create a new population of computer programs by applying the following operations. The operations are applied to computer program(s) chosen from the population with a probability based on fitness.
(i) Reproduction: Copy an existing program to the new population.
(ii) Crossover: Create new offspring program(s) for the new population by recombining randomly chosen parts of two existing programs.
(iii) Mutation: Create one new offspring program for the new population by randomly mutating a randomly chosen part of one existing program.
(3) The program that is identified by the method of result designation (e.g., the best-so-far individual) is designated as the result of the genetic algorithm for the run. This result may be a solution (or an approximate solution) to the problem.
Other genetic programming processes may utilize additional operations such as "permutation," "define building block" (also called "encapsulation"), or the architecture-altering operations mentioned later.
CELLULAR ENCODING OF NUERAL NETWORKS
A neural network is a structure consisting of one or more neural processing units (neurons). A neural network can be represented by a line-labeled, point-labeled, directed graph. The points of the graph are either neural processing units within the neural network, input points, or output points. The lines are labeled with numerical weights to represent the weighted connections between two points. The neural processing units are labeled with two numbers indicating the threshold and the bias of the processing unit.
The only type of component in a neural network is a neural processing unit. Neural networks are dynamical systems in the sense that the state of the network at a future time depends on the state of the network at the current time and the inputs to the network at the current time. There is a directional flow of information in neural networks. In feedforward neural networks, information flows from the inputs to the network, through the neurons, to the outputs of the network without any cycles within the directed graph representing the network. In recurrent neural networks, the output at a particular instant in time of one or more individual neurons in the network may be sent back to become the input at a future time of another neural processing unit so as to create a cycle within the directed graph representing the network.
The conventional genetic algorithm operating on fixed-length character strings provides a way to search the highly nonlinear multidimensional search space of weight vectors to discover the numerical weights for the connections as well as the thresholds and biases of a neural network; however, the architecture of the neural network must be specified in advance (Schaffer and Whitley 1992). The difficulty in automating the discovery of the architecture using genetic methods has centered on finding a malleable representation for the line-labeled, point-labeled, graph representing the neural network that is receptive to the kinds of operations performed by the genetic algoritam.
Some early work applied genetic programming to the problem of discovering both the architecture and weights of a neural network using the "define building block" (also called "encapsulation") operation of genetic programming (Koza and Rice 1991). The book The Algorithmic Beauty of Plants describes Lindenmayer systems (L-systems) and grammar rewrite rules. These systems provide a way to develop a complex pattern by applying rewriting rules to an initial (or embryonic) pattern.
In his Cellular Encoding of Genetic Neural Networks, Frederic Gruau (1992a) described a technique, called cellular encoding, in which genetic programming is used to concurrently evolve the architecture of a neural network, along with the weights, thresholds, and biases of the individual neurons in the neural network. In this technique, each individual program tree in the population is a specification for developing a complete neural network from a very simple neural network consisting of a single neuron. Genetic programming is applied to populations of these network-constructing program trees in order to evolve a neural network capable of solving the problem at hand. See also Gruau 1992b, 1993, 1994a, 1994b.
In cellular encoding, each program tree is a composition of constructing functions. The program tree is the genotype and the neural network constructed in accordance with the tree's instructions is the phenotype. The fitness of an individual program tree in the population is measured by how well the neural network that is constructed in accordance with the instructions contained in the program tree performs the desired task. This is typically accomplished by exposing the neural network to all (or a large sampling) of possible combinations of inputs and testing whether the output(s) of the neural network matches the correct output(s) for the particular combination of inputs. For many problems, fitness is computed from the number of correct and incorrect output(s) from the neural network. Genetic programming then breeds the population of program trees using the usual genetic operations of Darwinian reproduction, crossover, and mutation.
In cellular encoding, the construction process for a neural network starts from a neural network consisting of a single neuron. This neuron has a threshold of 0; its bias is 0; its input is connected to all of the network's input nodes with connections with weights of +1; its output is connected to all of the network's output nodes. The functions in the program tree then specify how to grow this neuron into the full neural network. Certain context-free functions permit a particular neuron to be subdivided in a parallel or sequential manner. Other functions can change the threshold of a neuron, the weight of a connection, or the bias on a neuron.
THE SPICE SIMULATOR FOR ELECTRICAL CIRCUITS
In many fields of engineering, complex physical phenomena can be simulated using computer-based simulators. In the field of electrical engineering, SPICE (an acronym for Simulation Program with Integrated Circuit Emphasis) is a massive family of programs written over several decades at the University of California at Berkeley for the simulation of analog, digital, and mixed analog/digital electrical circuits.
SPICE3 (Quarles et al. 1994) is the most recent version of SPICE. SPICE3 performs various types of analysis on circuits containing various circuit elements. The circuit elements include resistors, capacitors, inductors, switches, diodes, transistors, voltage and current sources, transmission lines, and many other devices. SPICE can perform DC analysis, transient analysis, pole-zero analysis, small-signal distortion analysis, sensitivity analysis, noise analysis, AC small-signal analysis, and other types of analysis. The SPICE3 program consists of about 6.1 megabytes of source code spread over 878 separate files that contain approximately 217,000 lines of C source code.
The input to a SPICE simulation consists of a netlist describing the circuit to be analyzed and certain commands that instruct SPICE as to the type of analysis to be performed and the nature of the output to be produced.
Similar simulators exist in many fields of engineering. For example, in the field of mechanical engineering, there are numerous simulators that enable the topological arrangement of various types of physical components (each further specified by different numerical and non-numerical parameters) to be provided to a simulator so that the physical structure can then be simulated.
AUTOMATED CIRCUIT DESIGN
Considerable progress has been made in automating certain design problems for purely digital circuits; however, the design of analog circuits and mixed analog-digital circuits has not proved to be as amenable to automation (Rutenbar 1993). In discussing "the analog dilemma," Aaserud and Nielsen (1995) observe,
"Analog designers are few and far between. In contrast to digital design, most of the analog circuits are still handcrafted by the experts or so-called `zahs` of analog design. The design process is characterized by a combination of experience and intuition and requires a thorough knowledge of the process characteristics and the detailed specifications of the actual product."
"Analog circuit design is known to be a knowledge-intensive, multiphase, iterative task, which usually stretches over a significant period of time and is performed by designers with a large portfolio of skills. It is therefore considered by many to be a form of art rather than a science."
Numerous efforts have been made to automate the design process for analog and mixed analog-digital circuits. Some of these efforts are now described below.
In an interactive design tool for analog integrated circuits called IDAC (Degrauwe 1987), the user begins by selecting various possible topologies for the circuit; IDAC then determines the values of the components in each circuit (in relation to the desired behavioral characteristics); and, the user chooses the best circuit.
In OASYS (Harjani, Rutenbar, and Carley 1989) and OPASYN (Koh, Sequin, and Gray 1990), a topology is chosen beforehand based on heuristic rules and the synthesis tool attempts to size the circuit. If the synthesis tool cannot size the chosen topology correctly, the tool creates a new topology using other heuristic rules and the process continues. The success of these systems depends on the effectiveness of the knowledge base of heuristic rules.
In SEAS (Ning, Kole, Mouthaan, and Wallings 1992), evolution is used to modify the topology and simulated annealing is used to size the circuit.
Maulik, Carley, and Rutenbar (1992) attempt to handle topology selection and circuit sizing simultaneously using expert design knowledge.
Nielsen (1995) has developed a continuous-time filter design tool (his "C-T compiler") that can be used to design analog filter circuits. Nielsen's process starts with the design, by hand, of a prototype filter. The values of the components and the topology are then adjusted to achieve compliance with the design requirements of the problem at hand.
GENETIC ALGORITHMS AND AUTOMATED CIRCUIT DESIGN
In DARWIN (Kruiskamp and Leenaerts 1995), operational ampliflier (opamp) circuits are designed using the genetic algorithm operating on binary character strings. In creating the initial population in DARWIN, the topology of each opamp in the population is picked randomly from a preestablished hand-designed set of 24 topologies in order to ensure that each circuit in the initial population behaves as an opamp. In addition, a set of problem-specific constraints are solved to ensure that all transistors operate in their proper range and that all transistor sizes lie between maximal and minimal values. The behavior of each opamp is evaluated using a small signal equivalent circuit and analytical calculations specialized to opamp circuits. The fitness of each opamp is computed using a combination of factors, including the deviation between the actual behavior of the circuit and the desired behavior and the power dissipation of the circuit. A crossover operation and mutation operation for the binary chromosome strings describing the opamps are used to create offspring binary chromosome strings.
Hemmi, Mizoguchi, and Shimohara (1994); Higuchi et al. (1993); and Mizoguchi, Hemmi, and Shimohara (1994) have employed genetic methods to the design of digital circuits using a hardware description language (HDL). In these approaches, a grammar is used to drive the development of the design of a digital circuit.
REFERENCES CITED
U.S. PATENTS
4,697,242, "Adaptive Computing System Capable of Learning and Discovery", issued Sept. 29, 1987, Holland et al.
4,881,178, "Method of Controlling a Classifier System," issued Nov. 14, 1989, Holland et al.
4,935,877, "Non-Linear Genetic Algorithms for Solving Problems," issued Jun. 19, 1990, Koza.
5,136,686, "Non-Linear Genetic Algorithms for Solving Problems by Finding a Fit Composition of Functions," issued Aug. 4, 1992, Koza.
5,148,513, "A Non-Linear Genetic Process for Use with Plural Co-Evolving Populations," issued Sep. 15, 1992, Koza, John R., and Rice, James P.
5,343,554, "A Non-Linear Genetic Process for Data Encoding and for Solving Problems Using Automatically Defined Functions," issued Aug. 30, 1994, Koza, John R., and Rice, James P.
OTHER PUBLICATIONS
Aaserud, O. and Nielsen, I. Ring. 1995. Trends in current analog design: A panel debate. Analog Integrated Circuits and Signal Processing. 7(1) 5-9.
Andre, David and Koza, John R. 1996. Parallel genetic programming: A scalable implementation using the transputer architecture. In Angeline, Peter J. and Kinnear, Kenneth E. Jr. (editors). 1996. Advances in Genetic Programming 2. Cambridge, Mass.: The MIT Press.
Darwin, Charles, 1859, On the Origin of Species by Means of Natural Selection, John Murray.
de Garis, Hugo. 1993. Evolvable hardware: Genetic programming of Darwin machines. In International Conference on Neural Networks and Genetic Algorithms. Lecture Notes in Computer Science. Springer-Verlag.
Degrauwe, M. 1987. IDAC: An interactive design tool for analog integrated circuits. IEEE Journal of Solid State Circuits. 22:1106-1116.
Gruau, Frederic. 1992a. Cellular Encoding of Genetic Neural Networks. Technical report 92-21. Laboratoire de l'Informatique du Parallelisme. Ecole Normale Superieure de Lyon. May 1992.
Gruau, Frederic. 1992b. Genetic synthesis of Boolean neural networks with a cell rewriting developmental process. In Schaffer, J. D. and Whitley, Darrell (editors). Proceedings of the Workshop on Combinations of Genetic Algorithms and Neural Networks 1992. Los Alamitos, Calif.: The IEEE Computer Society Press.
Gruau, Frederic. 1993. Genetic synthesis of modular neural networks. In Forrest, Stephanie (editor). Proceedings of the Fifth International Conference on Genetic Algorithms. San Mateo, Calif.: Morgan Kaufmann Publishers Inc. Pages 318-325.
Gruau, Frederic. 1994a. Neural Network Synthesis using Cellular Encoding and the Genetic Algorithm. PhD Thesis. Ecole Normale Superieure de Lyon.
Gruau, Frederic. 1994b. Genetic micro programming of neural networks. In Kinnear, Kenneth E. Jr. (editor). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press. Pages 495-518.
Haijani, R., Rutenbar, R. A., and Carley, L. R. 1989. OASYS: A framework for analog circuit synthesis. IEEE Transactions on Computer Aided Design. 8:1247-1266.
Hemmi, Hitoshi, Mizoguchi, Jun'ichi, and Shimohara, Katsunori. 1994. Development and evolution of hardware behaviors. In Brooks, Rodney and Maes, Pattie (editors). Artificial Life IV: Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems. Cambridge, Mass.: The MIT Press. Pages 371-376.
Higuchi, T., Niwa, T., Tanaka, H., Iba, H., de Garis, H. and Furuya, T. 1993. Evolvable hardware--Genetic-based generation of electric circuitry at gate and hardware description language (HDL) levels. Electrotechnical Laboratory technical report 93-4, Tsukuba, Ibaraki, Japan.
Holland, John H. 1975. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. Ann Arbor, Mich.: University of Michigan Press. Second edition. Cambridge, Mass.: The MIT Press 1992.
Holland, John H. 1986. Escaping brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems. In Michalski, Ryszard S., Carbonell, Jaime G. and Mitchell, Tom M. Machine Learning: An Artificial Intelligence Approach Volume II. P. 593-623. Los altos, Calif.: Morgan Kaufmann.
Koh, H. Y., Sequin, C. H. and Gray, P. R. 1990. OPASYN: A compiler for MOS operational amplifiers. IEEE Transactions on Computer Aided Design. 9:113-125.
Koza, John R., 1989. Hierarchical genetic algorithms operating on populations of computer programs, Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI), San Mateo, Calif.: Morgan Kaufmann.
Koza, John R., 1990. Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University, Dept. of Computer Science, Report No. STAN-CS-90-1314, June 1990.
Koza, John R. 1992. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, Mass.: The MIT Press.
Koza, John R. 1994. Genetic Programming II: Automatic Discovery of Reusable Programs. Cambridge, Mass.: The MIT Press.
Koza, John R. 1994b. Architecture-Altering Operations for Evolving the Architecture of a Multi-Part Program in Genetic Programming. Stanford University Computer Science Department technical report STAN-CS-TR-94-1528. Oct. 21, 1994.
Koza, John R., and Rice, James P. 1991. Genetic generation of both the weights and architecture for a neural network. In Proceedings of International Joint Conference on Neural Networks, Seattle, July 1991. Los Alamitos, Calif.: IEEE Press. Volume II. Pages 397-404.
Kruiskamp, Wim and Leenaerts, Domine. 1995. DARWIN: CMOS opamp synthesis by means of a genetic algorithm. Proceedings of the 32nd Design Automation Conference. New York, N.Y.: Association for Computing Machinery. Pages 433-438.
Maulik, P. C. Carley, L. R., and Rutenbar, R. A. 1992. A mixed-integer nonlinear programming approach to analog circuit synthesis. Proceedings of the 29th Design Automation Conference. Los Alamitos, Calif.: IEEE Press, Pages 698-703.
Mizoguchi, Junichi, Hemmi, Hitoshi, and Shimohara, Katsunori. 1994. Production genetic algorithms for automated hardware design through an evolutionary process. Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE Press. Volume I. Pages 661-664.
Nielsen, Ivan Riis. 1995. A C-T filter compiler--From specification to layout. Analog Integrated Circuits and Signal Processing. 7(1):21-33.
Ning, Z., Kole, M., Mouthaan, T., and Wallings, H. 1992. Analog circuit design automation for performance. Proceedings of the 14th IEEE CICC. New York: IEEE Press. Pages 8.2.1-8.2.4.
Prusinkiewicz, Przemyslaw, and Lindenmayer, Aristid. 1990. The Algorithmic Beauty of Plants. New York: Springer-Verlag.
Quarles, Thomas, Newton, A. R., Pederson, D. O., and Sangiovanni-Vincentelli, A. 1994. SPICE 3 Version 3F5 User's Manual. Department of Electrical Engineering and Computer Science, University of California, Berkeley, Calif. March 1994.
Rutenbar, R. A. 1993. Analog design automation: Where are we? Where are we going? Proceedings of the 15th IEEE CICC. New York: IEEE Press. Pages 13.1.1-13.1.8.
Schaffer, J. D. and Whitley, Darrell (editors). 1992. Proceedings of the Workshop on Combinations of Genetic Algorithms and Neural Networks 1992. Los Alamitos, Calif.: The IEEE Computer Society Press.
SUMMARY OF THE INVENTION
A method and apparatus for automated design of complex structures, such as, but not limited to, analog and digital circuits. The present invention operates with a system having a population of entities of various sizes and shapes. Entities in the population comprise constructing actions. The present invention includes a method and apparatus for running an iterative process that creates a design of a structure that satisfies prespecified design goals, in which a series of steps is iterated. In one embodiment, the present invention includes a method and apparatus that iteratively executes constructing actions in entities in the population to develop a structure that has multiple types of components arranged in a topology, where each component is associated with a component value. The present invention also includes a method and apparatus for determining behavior of said developed structure.
DESCRIPTION OF THE DRAWINGS
The present invention will be understood more fully from the detailed description given below and from the accompanying drawings of the preferred embodiments of the invention, which, however, should not be taken to limit the invention to the specific embodiments but are for explanation and understanding only.
FIG. 1A is a flow chart diagram of the present invention.
FIG. 1B is a flowchart for genetic programming for designing electrical circuits.
FIG. 2 illustrates one embodiment of a constrained syntactic structure.
FIG. 3 illustrates one embodiment of a one-input, one-output embryonic electrical circuit.
FIG. 4 illustrates a circuit containing a modifiable wire Z0.
FIG. 5 illustrates the result of applying the Resistor (R) function to a modifiable wire.
FIG. 6 illustrates the result of applying the Capacitor (C) function to a modifiable wire.
FIG. 7 shows the result of applying the Diode function to a modifiable wire.
FIG. 8 illustrates the results of applying the grounded-transistor function to a modifiable wire.
FIG. 9 illustrates the result of applying the QP function to a modifiable wire.
FIG. 10 illustrates the result of applying the QT0 function to a modifiable wire.
FIG. 11 illustrates the result of applying the QT8 function to a modifiable wire.
FIG. 12 illustrates a resistor R1 connected to two nodes of degree 2.
FIG. 13 illustrates a result of applying the QT7 function when both the active and inactive nodes are of degree 2.
FIG. 14 illustrates the result of applying the FLIP function to diode D1.
FIG. 15 illustrates the result of applying the series division dunction SERIES to a resistor.
FIG. 16 illustrates a result of applying the parallel division function PSS to a resistor R1.
FIG. 17 illustrates a result of applying the parallel division dunction PSL to a resistor R1.
FIG. 18 illustrates a result of applying either PSS or PSL to a circuit in which nodes 1 and 2 are of degree 2.
FIG. 19 is a circuit containing a resistor R1 in which node 1 is of degree 3 and node 2 is of degree 2.
FIG. 20 illustrates a result of applying either PSS to a circuit in which node 1 is of degree 3 and node 2 is of degree 2.
FIG. 21 illustrates a result of applying the CUT to resistor R1.
FIG. 22 illustrates a result of applying the VIA0 function to resistor R1.
FIG. 23 illustrates the result of applying the THVIA0 function to resistor R1.
FIG. 24 illustrates a program tree for best circuit of generation 0.
FIG. 25 is a one-input, one-output embryonic circuit with the initial two writing heads.
FIG. 26 illustrates a result of executing the C function acting on modifiable wire Z0 to create capacitor C3.
FIG. 27 illustrates a result of executing the FLIP function.
FIG. 28 illustrates a result of executing the SERIES function.
FIG. 29 illustrates a result of executing the FLIP function.
FIG. 30 illustrates a result of executing the SERIES function.
FIG. 31 illustrates a result of executing the L function acting on a capacitor to convert it into a new inductor.
FIG. 32 illustrates a result of executing the L function.
FIG. 33 illustrates a result of executing the L function.
FIG. 34 illustrates a result of executing the L function.
FIG. 35 illustrates the best circuit of generation 0.
FIG. 36 illustrates the parallel genetic programming system.
FIG. 37 illustrates the four processes on each of the 64 processing nodes.
FIG. 38 illustrates the best-of-run "seven-rung ladder" circuit from generation 32.
FIG. 39 illustrates the best-of-run "19-rung ladder" circuit from generation 76.
FIG. 40 illustrates a "bridged T" circuit from generation 64.
FIG. 41 illustrates the best-of-run circuit from generation 58.
FIG. 42 illustrates best-of-run circuit from generation 212.
FIG. 43 illustrates best-of-run circuit from generation 53.
FIG. 44 illustrates a program having four function-defining branches and two result-producing branches.
FIG. 45 illustrates twice-used automatically defined function ADF3 and generation 9.
FIG. 46 illustrates the twice-used automatically defined function ADF0 and generation 9.
FIG. 47 illustrates an automatically defined function ADF0 from generation 31 used five times.
FIG. 48 is the best circuit of generation 31.
FIG. 49 illustrates the generic three-port substructure created by ADF0.
FIG. 50 illustrates an edited version of ADF0 of best-of-run circuit from generation 35.
FIG. 51 illustrates the best-of-run circuit from generation 35.
FIG. 52 illustrates the best-of-run individual from generation 35.
FIG. 53 illustrates one-input, one-output embryonic circuit.
FIG. 54 illustrates the result of executing the C function.
FIG. 55 illustrates the result of executing the THVIA function.
FIG. 56 illustrates the result of executing the FLIP function.
FIG. 57 illustrates the result of executing the three END functions.
FIG. 58 illustrates the result of executing the PSS function.
FIG. 59 illustrates the result of executing the PSS function.
FIG. 60 illustrates the result of executing the PSS function.
FIG. 61 illustrates a result of executing the FLIP function, the END function and the PSS function.
FIG. 62 illustrates a cutaway portion of developing circuit where an ADF is about to be applied.
FIG. 63 illustrates the result of executing the NOP function and the L function in an ADF.
FIG. 64 illustrates the result of executing the first SERIES function in an ADF.
FIG. 65 illustrates the result of executing the second SERIES function in an ADF.
FIG. 66 illustrates the result of executing the L function in an ADF.
FIG. 67 illustrates the result of executing the L function in an ADF.
FIG. 68 illustrates the result of executing the PSS function in an ADF.
FIG. 69 illustrates the result of executing the C function in an ADF.
FIG. 70 is a three-port substructure created by an ADF.
FIG. 71 is different presentation of the best-of-run circuit from generation 35.
FIG. 72 illustrates the automatically defined function ADF0 of best-of-run circuit from generation 77.
FIG. 73 illustrates the best-of-run circuit from generation 77.
FIG. 74 illustrates the best-of-generation circuit from generation 37.
FIG. 75 illustrates a More Parsimonious circuit from generation 52.
FIG. 76 illustrates a one-input, two-output embryo embryonic electrical circuit.
FIG. 77 illustrates the result of executing the L, C, and C functions.
FIG. 78 illustrates the best circuit of generation 0.
FIG. 79 illustrates the best circuit of generation 79.
FIG. 80 illustrates best-of-run circuit from generation 137.
FIG. 81 illustrates one-input, three-output embryo embryonic electrical circuit.
FIG. 82 illustrates embryonic circuit for a two-input, two-output controller for a robot.
FIG. 83 illustrates the result of applying the QVIAC7 function.
FIG. 84 illustrates the result of applying the QVIAB7 function.
FIG. 85 illustrates the result of applying the QVIAE7 function.
FIG. 86 illustrates the result of applying the TRANFORMER 0 function.
FIG. 87 illustrates the result of applying the TRANFORMER 1 function.
FIG. 88 illustrates the result of applying the TRANFORMER 2 function.
FIG. 89 illustrates the result of applying the TRANFORMER 3 function.
FIG. 90 illustrates the result of applying the TRANFORMER 4 function.
FIG. 91 illustrates the result of applying the TRANFORMER 5 function.
FIG. 92 is a circuit with resistor R1.
FIG. 93 illustrates the result of applying the FIVE.sub.-- LEAD.sub.-- OPAMP1 function to resistor R1.
FIG. 94 illustrates the result of applying the STAR 1 division function to resistor R1.
FIG. 95 illustrates the result of applying the TRIANGLE1 division function to resistor R1 when the active node (node 1) is of degree 3.
FIG. 96 illustrates the result of applying the TRIANGLE1 division function to resistor R1 when the active node (node 1) is of degree 2.
FIG. 97 illustrates the best-of-generation genetically evolved amplifier from generation 45.
FIG. 98 illustrates the voltage gain stage of the genetically evolved amplifier.
FIG. 99 illustrates Darlington emitter follower section of the genetically evolved amplifier.
FIG. 100 illustrates another view of the genetically evolved amplifier.
FIG. 101 is a diagram of a truss consisting of eight rigid beams and two flexible cables supporting two loads.
FIG. 102 is a diagram of a mechanical system containing two springs, two dash pots, and two masses.
FIG. 103 is an elliptic 5 lowpass filter subcircuit ELIP5.sub.-- LP.sub.-- 1.
FIG. 104 is an elliptic 5 highpass filter subcircuit ELIP5.sub.-- HP.sub.-- 1.
FIG. 105 illustrates the best-of-generation genetically evolved multi-band-pass filter from generation 45.
FIG. 106 illustrates the result of applying the digital INVERTER function to modifiable wire Z0.
FIG. 107 illustrates the result of applying the digital AND6 function to modifiable wire Z0.
FIG. 108 illustrates the result of applying the digital OR6 function to modifiable wire Z0.
FIG. 109 illustrates the result of applying the THREE.sub.-- LEAD.sub.-- OPAMP1 function to modifiable wire Z0.
FIG. 110 illustrates the result of applying the TWO.sub.-- LEAD.sub.-- OPAMP1 function.
FIG. 111 illustrates the use of a field programmable digital or analog array to physically realize a desired circuit.
FIG. 112 illustrastes an electrical structure consisting of 5 components, 10 interface points, and 7 arcs.
FIG. 113 illustrates a mechanical structure consisting of 7 components, 11 interface points, and 6 arcs.
FIG. 114 illustrates mechanical structure consisting of 13 components and 24 interface points.
DETAILED DESCRIPTION OF THE INVENTION
A method and apparatus for designing complex structures is described. The complex structures that are to be designed may be electrical circuits, physical structures, mechanical structures, or other complex structures consisting of a plurality of types of components that are interfaced in accordance with a particular topological arrangement and that are sized in terms of numerical parameters or other types of parameters.
In the following detailed description of the present invention numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to one skilled in the art that the present invention may be practiced without these specific details. In some instances, well-known structures and devices are shown in block diagram form, rather than in detail, in order to avoid obscuring the present invention.
Some portions of the detailed descriptions which follow are presented in terms of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.
It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussions, it is appreciated that throughout the present invention, discussions utilizing terms such as "processing" or "computing" or "calculating" or "determining" or "displaying" or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.
The present invention also relates to apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general purpose computer selectively activated or reconfigured by a computer program stored in the computer. The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus. Various general purpose machines may be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these machines will appear from the description below. In addition, the present invention is not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the invention as described herein.
OVERVIEW OF THE PRESENT INVENTION
The present invention provides for designing complex structures such as electrical circuits (e.g., analog circuits, mechanical structures, or other physical structures) that satisfy certain design restrictions.
The electrical circuits of the present invention may comprise a wide variety of different types of components, including, but not limited to, resistors, capacitors, inductors, diodes, transistors, and energy sources. The individual components are arranged in a particular "topology" to form a circuit. In addition, each component may be further specified ("sized") by a set of component values (typically numerical). Circuits typically receive input signals from one or more input sources and produce output signals at one or more output ports. In one embodiment, circuits have at least one energy source (e.g., an incoming signal, a power supply, etc.). Thus, the present invention may completely specify an electrical circuit as to both its topology and the sizing of all of its components.
In one embodiment, a "component" is an object that has a type, some number of component values that further specify the component, and some number of interface points. Consider, for example, a resistor. A resistor is a component because it is an object of the type "resistor;" it has a single numerical component value of 1,000 Ohms and it has two interface points (leads, ends).
The interface points of a component may be operationally indistinguishable (as, for example, the two leads of a resistor) or they may be operationally different (as, for example, the collector, base, and emitter of a transistor).
A "circuit" includes (1) a set of components and (2) a set of undirected lines (arcs) between the interface points of the components. Each undirected line indicates the existence of a connection between the interface point of one component and another interface point (typically of another component).
When physical structures (such as a truss) are involved, the different types of components may include, but are not limited to, rigid load-supporting beams and flexible load-supporting cables.
When mechanical structures are involved, the types of components may include, but are not limited to, springs, masses, and dash pots.
Once the user specifies the design goals for a complex structure that is to be designed, the automated design process of the present invention generates a complete design. That is, the present invention is a goal-driven method for creating both the topology and the sizing of the complex structure. The present invention provides a method for accomplishing goal-driven design.
FIG. 1A illustrates the process of the present invention using genetic programming. The process is applied to a population of entities (e.g., program trees) that represent complex structures (e.g., a truss, circuit, etc.). The population may be created in a variety of ways (e.g., randomly) or may be supplied to begin a process. Using the population of entities, the process begins by executing constructing actions in each entity in the population to develop the structure (processing block 101). In the present invention, the structures include a plurality of types of components arranged in a topology. Component values, if any, are associated with the components in the topology. In one embodiment, the constructing actions are applied to an embryonic structure during execution, which may be common to all entities or may differ initially between the different entities.
After execution of the constructing actions, the behavior of each developed structure in the population is determined (processing block 102). This determination may be, for instance, but not limited to, by simulation or observation. Once the behavior is determined, it is compared to prespecified design goals to obtain a fitness measure (processing block 103).
A test then determines if the design goals or termination criteria, as will be discussed further below, have been met (processing block 104). If they have, the process ends. On the other hand, if the design goals or termination criteria have not been met, genetic operations are applied to entities in the population to continue the evolutionary process of the present invention (processing block 105). After applying the genetic operations, a process returns to processing block 101 and the process continues to repeat.
The process of the present invention can be applied to many problems including the problem of designing analog electrical filter circuits. One such filter is a one-input, one-output electronic circuit that receives a signal as its input and passes the frequency components of the incoming signal that lie in a certain specified frequency range (the passband) while stopping the frequency components of the signal that lie in other frequency ranges (the stopband).
Genetic programming breeds a population of rooted, point-labeled trees (i.e., graphs without cycles) with ordered branches. There is a considerable difference between the kind of trees bred by currently known forms of genetic programming and the special kind of labeled cyclic graphs employed in the world of electrical circuits.
Electrical circuits are not trees, but, instead, are cyclic graphs. In fact, electrical circuits are cyclic graphs in which lines belong to a cycle (e.g., there are no loose wires or dangling components). Moreover, the lines of a graph that represents an electrical circuit are each labeled. Usually there are multiple labels on each line. The primary label on each line gives the type of an electrical component (e.g., a wire, resistor, capacitor, in some cases a portion of a component). The secondary label on each line gives the value of the component (with the exception of the components that do not carry any component value, such as diodes). A single numerical value is sufficient to specify many components (e.g., resistors, capacitors, and inductors). Multiple values are required to specify other components (e.g., the frequency and peak voltage of a sinusoidal wave source). Many components in electrical circuits have a polarity (e.g., diodes) or orientation or distinction of their leads (e.g., the collector, base, and emitter of a transistor). Electrical circuits may have at least one energy source (e.g., an incoming signal or an internal power source). Some component values are non-numerical, such as whether an energy source is "AC" or "DC." In addition, a group of component values may be conveniently specified by referring to a "model" that provides numerous values that are applicable to a component. For example, complicated components, such as transistors and diodes, are described by extensive models.
The present invention applies genetic programming to electrical circuits by establishing a mapping between the kind of point-labeled trees found in the world of genetic programming and the line-labeled cyclic graphs that represent electrical circuits.
The developmental growth process used herein begins with a very simple, essentially useless, embryonic electrical circuit. In addition to this embryonic circuit, there is a program tree of the type ordinarily used in genetic programming. The electrical circuit is then developed as the functions in the program tree are executed and progressively applied to the embryonic circuit (and its successors). The functions in the program tree manipulate the embryonic circuit (and its successors) in a way that preserves the essential features of an electrical circuit. The final result of this developmental process is both the topology of the circuit and the sizing of all of its components. FIG. 1B illustrates one embodiment of the process of the present invention for automated design of electrical circuits. (FIG. 1B will be described in more detail below).
The process of the present invention that is described for electrical circuits can be applied to the automated design of other complex structures, such as mechanical structures. Mechanical structures are not trees, but, instead, are graphs. The lines of a graph that represents a mechanical structure are each labeled. The primary label on each line gives the name of a component (e.g., a mass). The secondary label on each line gives the value of the component.
The design that results from the process of the present invention may be fed, directly or indirectly, into a machine or apparatus that implements or constructs the actual structure. Such machines and their construction are well-known in the art. For example, electrical circuits may be made using well-known semiconductor processing techniques based on a design, and/or place and route tools. Programmable devices, such as FPGA, may be programmed using tools responsive to netlists, etc. Other structures, such as mechanical structures, may be physically constructed through the use of computer controlled processing and hardware (e.g., assembly line technology) that performs handling, movement, and attachment of components.
Constrained Syntactic Structure of the Program Trees in the Population
In the present invention, the program trees may contain any or all of the following five categories of functions:
(1) connection-creating functions that modify the topology of circuit from the embryonic circuit,
(2) component-creating functions that insert particular components into locations within the topology of the circuit in lieu of wires (and other components) and whose arithmetic-performing subtrees specify the numerical value (sizing) for each component that has been inserted into the circuit,
(3) automatically defined functions (subroutines) whose number and arity are specified in advance by the user, and
(4) automatically defined functions whose number and arity are not specified in advance by the user, but, instead, come into existence dynamically during the run of genetic programming as a consequence of the architecture-altering operations.
In one embodiment, program trees conform to a constrained syntactic structure. Each component-creating function in a program tree has zero, one or more arithmetic-performing subtrees and one or more construction-continuing subtrees, while each connection-creating function has one or more construction-continuing subtrees. The arithmetic-performing subtree(s), if any, of each component-creating function comprises a composition of arithmetic functions and numerical constant terminals that together yield the numerical value for the component. The construction-continuing subtree specifies how the construction of the circuit is to be continued. FIG. 2 illustrates one constrained syntactic structure for the program trees. This particular figure assumes the existence of two result-producing branches and four automatically defined functions. Note that in other embodiments, program trees may not conform to this particular constrained syntactic structure or any constrained syntactic structure.
By convention, the arithmetic-performing subtree(s) are placed on the left and the construction-continuing subtree(s) are placed on the right.
Both the random program trees in the initial population (generation 0) and any random subtrees created by the mutation operation in later generations are created so as to conform to this constrained syntactic structure. This constrained syntactic structure is preserved by the crossover operation using structure-preserving crossover with "point typing" (as described in Koza 1994).
The One-Input, One-Output Embryonic Circuit
In the present invention, an electrical circuit is created by executing the program tree. Each program tree in the population creates one electrical circuit from an embryonic electrical circuit. The embryonic circuit used on a particular problem depends on the number of input signals and the number of output signals (probe points). It may also incorporate certain fixed components that are required or desired for the circuit being designed.
In one embodiment, the embryonic circuit contains one input signal, one probe point, two modifiable wires, a fixed source resistor, and a fixed load resistor. In the embryonic circuit, the two modifiable wires each initially possess a writing head represented in the figures herein by the circled highlight. A circuit is developed by modifying the component to which a writing head is pointing in accordance with the functions in the circuit-constructing program tree. Each connection-creating and component-creating function in the program tree modifies its associated highlighted component in the developing circuit in a particular way and specifies the future disposition of successor writing head(s), if any.
FIG. 3 illustrates one embodiment of a one-input, one-output embryonic circuit. Referring to FIG. 3, the energy source is a 2 volt voltage source VSOURCE labeled 319 whose negative (-) end is connected to node 300 (ground) and whose positive (+) end is connected to node 301.
Note that the term "end" or "lead" or "interface" is used to describe the places at which a component becomes connected to other components in the overall circuit structure.
There is a fixed 1000-Ohm source resistor RSOURCE labeled 312 between nodes 301 and 302. There is a modifiable wire Z1 (i.e., a wire with a writing head) labeled 306 between nodes 302 and 303 and another modifiable wire Z0 labeled 307 between nodes 303 and 304. There are circles around modifiable wires Z0 and Z1 to indicate that the two writing heads point to them. There is a fixed isolating wire ZOUT labeled 308 between nodes 303 and 305, a voltage probe labeled VOUT labeled 309 at node
305, and a fixed 1000-Ohm load resistor RLOAD labeled 310 between nodes 305 and 300 (ground). There is an isolating wire ZGND labeled 311 between nodes 304 and 300 (ground). At the beginning of the developmental process, there is a writing head pointing to each of the two modifiable wires Z0 and Z1. All subsequent development of the circuit originates from writing heads. A circuit is developed by modifying the component to which a writing head is pointing (and sometimes the component and one of its nodes) in accordance with the associated function in the circuit-constructing program tree.
This particular embryonic circuit is designed so that the number of lines impinging at any one node in the circuit is either two or three. This condition is maintained by all of the functions in the circuit-constructing program tree.
The isolating wire ZOUT 308 protects the probe point VOUT 309 and the load resistor RLOAD 310 from modification during the developmental process and the isolating wire ZGND 311 similarly protects the negative terminal 300 of VSOURCE 319 and the ground.
Note that little domain knowledge went into this embryonic circuit. Specifically, (1) the embryonic circuit is a circuit, (2) the embryonic circuit has one input and one output, and (3) there are modifiable connections between the output and the source and between the output and ground. Note that this embryonic circuit is applicable to any one-input, one-output circuit. It is the fitness measure that directs the evolutionary search process to the desired circuit. This is not to say that there is any guarantee of a successful outcome of any particular run of genetic programming on any particular previously unseen problem. But it does say that the user introduces very little information into the design process other than to specify the nature of the inputs and outputs by means of the embryonic circuit and to describe what is desired by means of the fitness measure.
A human designer may find it advantageous to apply his domain knowledge of a particular field to create the embryonic circuit for a particular problem. Such knowledge would bias the search for a satisfactory design in the direction of particular known or desirable characteristics. Also, some design problems call for the inclusion of particular components (possibly arranged in particular ways) as a part of the overall design.
In one embodiment, the same embryonic circuit is used as a starting point for development for all individual program trees in the population. That is, there is a common embryonic circuit that is the starting point for the developmental process for each individual program tree in the population. The individual entity in the population consists of the program tree. When an individual entity in the population is executed, the execution includes applying the constructing actions of the program tree contained in the particular individual entity to the common embryonic circuit. Note that in alternate embodiments, the program trees may begin with a different embryonic circuits.
For some problems, it may be advantageous to co-evolve concurrently a pair of entities that includes the embryonic circuit and the program tree. That is, each entity in the population has a pair consisting of an embryonic circuit and a program tree. When an individual entity in the population is executed, the execution includes applying the constructing actions of the program tree contained in the particular individual entity to the particular embryonic circuit contained in the particular individual entity. The evolutionary process will favor those entities in the population whose embryonic circuit and program trees that, when acting in conjunction with one another, better satisfy the design goals of the problem.
Although an embyonic circuit is used in one embodiment of the present invention, it should be noted that it is not necessary to have an embryonic circuit at all. Instead, the set of circuit-constructing functions can contain functions that build the entire circuit. It is, however, highly advantageous to separately provide an embryonic circuit since this approach guarantees that the circuit has certain minimum essential features (e.g., access to the incoming signal, inclusion of a ground, inclusion of a probe point, etc.). In the absence of an embryonic circuit, many individuals would lack, for example, any incoming signal source (and hence achieve poor scores in terms of satisfying the design goals of a problem). Evolving such fundamental features would require the expenditure of additional effort. Thus, in one embodiment, these minimal features are provided, in advance, in the form of the embryonic circuit.
Component-Creating Functions
Each individual circuit-constructing program tree in the population generally contains component-creating functions and connection-creating functions.
Components are inserted into the topology of a circuit by the component-creating functions. Components also acquire their sizing from the component-creating functions. Each component-creating function in a program tree points to a highlighted component (i.e., a component with a writing head) in the developing circuit and modifies the highlighted component in some way. Each component-creating function spawns one or more writing heads (through its construction-continuing subtrees).
Each component-creating function leaves the number of lines impinging at any one node in the circuit at either two or three. Note that this is not a requirement.
Some of the component-creating functions are context-free and some are context-sensitive. When a component-creating function is context-free, the outcome depends only on the single highlighted component (i.e., the component with the writing head). When a component-creating function is context-sensitive, the outcome depends not just upon the single highlighted component, but also upon other nearby elements of the circuit structure. The present invention supports the creation of complex structures resulting from the execution of context-sensitive functions as well as context-free functions.
Table 1 lists some illustrative component-creating functions for electrical circuits. The table shows the short name of the function, a longer and more descriptive name for the function, and its arity (i.e., number of arguments that it takes). This table is not an exhaustive list of possible useful component-creating functions for electrical circuits, but is intended to illustrate the nature of possible componen