Method and apparatus for automated design of complex structures using genetic programming

• US 5,867,397 A
• Filed: 02/20/1996
• Issued: 02/02/1999
• Est. Priority Date: 02/20/1996
• Status: Expired due to Term

• Current Assignee: John R. Koza
• Original Assignee: John R. Koza
• Inventors: Andre, David, Bennett, Forrest H. III, Koza, John R.
• Primary Examiner(s): Tesk, Kevin J.
• Assistant Examiner(s): Siek, Vuthe
• Application Number:
  US08/603,648
• Time in Patent Office: 1,078 Days
• Field of Search: 364/488-491, 364/492, 364/468, 364/493, 364/513, 364/489, 364/490, 395/10, 395/13, 706/13
• US Class Current: 703/14
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 2113/16 Cables, cable trees or wire harnesses
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06F 30/36 Circuit design at the analogue level
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or 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.

Claims

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.

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.

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.

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.