Method and apparatus for designing structures

• US 8,356,000 B1
• Filed: 04/13/2000
• Issued: 01/15/2013
• Est. Priority Date: 04/13/2000
• Status: Expired due to Fees

• Current Assignee: John R. Koza
• Original Assignee: John R. Koza
• Inventors: Koza, John R., Stiffelman, Oscar, Bennett, Forrest H. III
• Primary Examiner(s): Wong, Lut
• Application Number:
  US09/548,637
• Time in Patent Office: 4,660 Days
• Field of Search: 706/12, 706/13, 706/14
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A method and apparatus for the automatic creation of novel designs, specifically electronic circuits, controllers, antennas, and mechanical systems to satisfy prespecified design goals, using search procedures, such as genetic programming, genetic algorithms, simulated annealing and hill climbing is described. Further, the techniques include automatically creates designs which do not posses key characteristics of preexisting technology. 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 the structures is evaluated in view of the design goals, and the structures are compared to a preexisting structure. Those structures more closely meeting the design goals and not similar to the preexisting structure are favored further until a structure is generated that either meets the prespecified design goal or some other process completion criteria. In this manner, a novel structure may be obtained.

Claims

1. A computer-implemented process for creating an entity that satisfies a predetermined design requirement that at least one characteristic is not in a reference structure, the process comprising:

initializing a plurality of candidate entities and an iteration count with a predetermined value by supplying, from an external source, at least one candidate entity partially satisfying the predetermined design requirement which includes a characteristic of the reference structure to the initialized plurality of candidate entities, wherein each candidate entity is represented by a tree structure having a plurality of nodes representing a structure of the candidate entity;

performing iterative genetic programming operations, each iteration including;

creating a description of the structure for each of the candidate entities based on its tree structure,

analyzing behavior and characteristics based on the description of the structure of each candidate entity, including a simulation of the structure,

comparing each of the plurality of candidate entities with the reference structure based on the analysis of the behavior and characteristics to obtain an isomorphism value for each candidate entity, the isomorphism value representing a dissimilarity between the respective candidate entity and the reference structure,

determining a fitness value for each of the candidate entities based on a compliance with the predetermined design requirement and the isomorphism value of the respective candidate entity,

selecting at least one candidate entity from the plurality of candidate entities that has a fitness value exceeds a predetermined threshold,

creating at least one new candidate entity by creating a variation in the selected at least one candidate entity if the selected at least one candidate does not satisfy the predetermined design requirement or a number of iterations has not reached the predetermined value of the iteration count, including performing one of a reproduction operation, offspring crossover operation, mutation operation, and an architecture altering operation on the at least one selected candidate entity, and

terminating the iterations if the selected at least one candidate satisfies the predetermined design requirement or a number of iterations has reached the predetermined value of the iteration count, wherein at least one of the selected candidate entities is used to design an end-result structure in view of the predetermined design requirement, wherein the end-result structure does not possess key characteristics of the reference structure; and

updating the iteration count at the end of each iteration.

2. The process defined in claim 1 wherein creating at least one new candidate entity comprises mutating the at least one candidate entity.

3. The process defined in claim 2 wherein selecting the at least one candidate entity is performed by simulating annealing.

4. The process defined in claim 2 wherein selecting at least one candidate is performed by hill climbing.

5. The process defined in claim 1 wherein the at least one candidate entity is a member of a population of entities.

6. The process defined in claim 5 wherein creating at least one new candidate entity comprises performing a crossover operation among a group of candidate entities, the group of entities comprising the selected entity and at least one other entity from the population, the at least one new coordinate entity created by crossover comprising at least a portion of the selected entity and at least a portion of that at least one other entity.

7. The process defined in claim 1 further comprising creating the at least one candidate entity by a random process.

8. The process defined in claim 1 further comprising:

evaluating the selected at least one candidate entity by simulating the selected at least one candidate entity to ascertain whether the selected at least one candidate entity more closely satisfies the design requirement.

9. The process defined in claim 1 further comprising:

evaluating the selected at least one candidate entity by observing a physical realization representing the selected at least one candidate entity to ascertain whether the selected at least one candidate entity more closely satisfies the design requirement.

10. The process defined in claim 1 wherein the candidate entity conforms to a constrained syntactic structure.

11. The process defined in claim 1 wherein the candidate entity comprises an electrical circuit.

12. The process defined in claim 1 wherein the candidate entity comprises a controller.

13. The process defined in claim 1 wherein the candidate entity comprises an antenna.

14. The process defined in claim 1 wherein the candidate entity comprises a mechanical system.

15. A computer system, comprising:

a processor; and

a memory coupled to the processor for storing computer executable instructions, which when executed from the memory, cause the processor to perform a process for creating an entity that satisfies a predetermined design requirement that at least one characteristic is not in a reference structure, the process comprising;

initializing a plurality of candidate entities and an iteration count with a predetermined value by supplying, from an external source, at least one candidate entity partially satisfying the predetermined design requirement which includes a characteristic of the reference structure to the initialized plurality of candidate entities, wherein each candidate entity is represented by a tree structure having a plurality of nodes representing a structure of the candidate entity;

performing iterative genetic programming operations, each iteration including;

creating a description of the structure for each of the candidate entities based on its tree structure,

analyzing behavior and characteristics based on the description of the structure of each candidate entity, including a simulation of the structure,

comparing each of the plurality of candidate entities with the reference structure based on the analysis of the behavior and characteristics to obtain an isomorphism value for each candidate entity, the isomorphism value representing a dissimilarity between the respective candidate entity and the reference structure,

determining a fitness value for each of the candidate entities based on a compliance with the predetermined design requirement and the isomorphism value of the respective candidate entity,

selecting at least one candidate entity from the plurality of candidate entities that has a fitness value exceeds a predetermined threshold,

creating at least one new candidate entity by creating a variation in the selected at least one candidate entity if the selected at least one candidate does not satisfy the predetermined design requirement or a number of iterations has not reached the predetermined value of the iteration count, including performing one of a reproduction operation, offspring crossover operation, mutation operation, and an architecture altering operation on the at least one selected candidate entity, and

terminating the iterations if the selected at least one candidate satisfies the predetermined design requirement or a number of iterations has reached the predetermined value of the iteration count, wherein at least one of the selected candidate entities is used to design an end-result structure in view of the predetermined design requirement, wherein the end-result structure does not possess key characteristics of the reference structure; and

updating the iteration count at the end of each iteration.

16. A non-transitory computer-readable storage medium having stored thereon executable code which causes a computer to perform a process, for creating an entity that satisfies a predetermined design requirement that at least one characteristic is not in a reference structure, the process comprising:

initializing a plurality of candidate entities and an iteration count with a predetermined value by supplying, from an external source, at least one candidate entity partially satisfying the predetermined design requirement which includes a characteristic of the reference structure to the initialized plurality of candidate entities, wherein each candidate entity is represented by a tree structure having a plurality of nodes representing a structure of the candidate entity;

performing iterative genetic programming operations, each iteration including;

creating a description of the structure for each of the candidate entities based on its tree structure,

analyzing behavior and characteristics based on the description of the structure of each candidate entity, including a simulation of the structure,

comparing each of the plurality of candidate entities with the reference structure based on the analysis of the behavior and characteristics to obtain an isomorphism value for each candidate entity, the isomorphism value representing a dissimilarity between the respective candidate entity and the reference structure,

determining a fitness value for each of the candidate entities based on a compliance with the predetermined design requirement and the isomorphism value of the respective candidate entity,

selecting at least one candidate entity from the plurality of candidate entities that has a fitness value exceeds a predetermined threshold,

creating at least one new candidate entity by creating a variation in the selected at least one candidate entity if the selected at least one candidate does not satisfy the predetermined design requirement or a number of iterations has not reached the predetermined value of the iteration count, including performing one of a reproduction operation, offspring crossover operation, mutation operation, and an architecture altering operation on the at least one selected candidate entity, and

terminating the iterations if the selected at least one candidate satisfies the predetermined design requirement or a number of iterations has reached the predetermined value of the iteration count, wherein at least one of the selected candidate entities is used to design an end-result structure in view of the predetermined design requirement, wherein the end-result structure does not possess key characteristics of the reference structure; and

updating the iteration count at the end of each iteration.