Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-08-27
2002-04-23
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C703S001000, C703S002000, C703S014000
Reexamination Certificate
active
06378117
ABSTRACT:
BACKGROUND OF THE INVENTION
Field of Invention
The present invention pertains to the field of cellular encoding. More particularly, this invention relates to cellular encoding using typed development operators.
Art Background
Cellular encoding may be used to develop a variety of structures including electrical circuits and finite automata. A typical prior cellular encoding process generates organisms which represent putative solutions to the problem of developing a desired structure. For example, an organism may be a program for generating an electrical circuit having a set of desired properties from an embryo circuit element. The properties may include desired signal outputs in response to signal inputs.
An organism in cellular encoding is commonly represented as a tree which provides an arrangement of development operators. Each development operator typically replaces a piece of a structure with zero or more other pieces. Typically, each new piece may continue to develop according to the child development operators specified by the tree.
Cellular encoding is typically used with genetic programming to evolve a desire structure. Genetic programming may be defined as a computer-based programming methodology in which computer programs are generated using an iterative process that simulates evolution by natural selection. In the case of cellular encoding, the computer programs generated are programs for developing a desired structure such as an electrical circuit or finite state machine from an embryonic structure.
Genetic programming typically involves the generation of an initial population of organisms. Each organism in the population is typically evaluated as a solution to the particular development problem using a fitness measure. In the example of circuit construction, the fitness measure for an organism may be based on an analysis of the properties of an electrical circuit which is developed by the organism. If a solution developed by an organism in a population is considered good enough in terms of the fitness measure, then it is usually selected as the solution to the particular problem. Otherwise, a subset of the organisms from the population are typically selected to become parents for a population of child organisms.
Child organisms are typically created by combining parent organisms using techniques that are modeled on biological processes such as mutation and crossover. The organisms in the child population are then evaluated as solutions using the fitness measure. The process repeats through generations of child populations until an individual organism that is good enough is found or until it is decided that the process has gone on sufficiently long that it is not worth proceeding.
In prior cellular encoding methods, development operators in a tree usually operate on only one type of structural element. In addition, prior cellular encoding methods typically impose the requirement that any development operator in a tree must accept the ouput of any other development operator in the tree. Typically, this yields an extremely wide range of possible interconnections of development operators in trees. This large number of possible interconnections usually increases the number of organisms that must be evaluated as possible solutions to a particular problem. Unfortunately, this typically slows convergence to a solution thereby increasing the time and cost required to evolve a desired structure.
SUMMARY OF THE INVENTION
Cellular encoding techniques using typed development operators are disclosed in which basic types are determined for the components of a structure being developed. Each development operator for developing the structure is associated with one or more of the basic types. Organisms are generated using tree arrangements of the development operators by matching the basic types associated with connections among the development operators in the trees. The matching among typed development operators reduces the likelihood of creating an unfit organism.
Cellular encoding using typed development operators may be used in conjunction with genetic programming to evolve the structure. For example, a population of organisms having typed development operators may be generated and a set of parent organisms may be selected from the population based on their fitness in generating the structure. A set of child organisms may then be generated by combining portions of the parent organisms such that connections among the development operators in the child organisms match the associated basic types. The type matching reduces the likelihood of creating unfit child organisms, thereby increasing the likelihood and speed of convergence to a solution.
Other features and advantages of the present invention will be apparent from the detailed description that follows.
REFERENCES:
patent: 5760786 (1998-06-01), Marks et al.
patent: 5867397 (1999-02-01), Koza et al.
patent: 08272659 (1996-10-01), None
Tanomaru et al. (“An evolutionary method for automatic wire routing”, 20th International Conference on Industrial Electronics, Control and Instrumentation, 1994, IECON '94, vol. 2, Sep. 5, 1994, pp. 1117-1122).*
Gruau (“Cellular encoding as a graph grammar”, IEE Colloquium on Grammatical Interference: Theory, Applications and Alternatives, 1993, pp. 17/1-10).*
Hussain et al. (“Network generating attribute grammar encoding”, The 1998 IEEE International Joint Conference on Neural Networks Proceedings, vol. 1, May 4, 1998, pp. 431-436).
Kik Phallaka
Smith Matthew
LandOfFree
Cellular encoding using typed development operators does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cellular encoding using typed development operators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cellular encoding using typed development operators will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2907799