Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-10-20
2003-01-21
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C709S203000, C706S013000, C700S103000, C345S419000
Reexamination Certificate
active
06510547
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to computer-implemented techniques for evolving a solution to a particular problem, and more particularly to a technique that is a hybrid of evolution-based processing techniques and simulated annealing techniques.
BACKGROUND
Many conventional design methodologies are generally based on a structured design approach. That is, high-level requirements are partitioned, perhaps hierarchically, into lower-level requirements. Teams of engineers are assigned to create designs and sub-designs that meet the requirements at the different levels. The structured design methodology is advantageous because it supports building on past experiences in addressing similar types of requirements, thereby promoting the development of an effective design in an efficient manner. However, a drawback to traditional design methods is that the same experiences that promote quickly satisfying a requirement may blind engineers to alternative, and perhaps better, solutions.
Work is presently underway to fundamentally change the way in which designs are created. The new methodology uses principles of natural selection from the biological world to find hardware and/or software designs. The process is often characterised as using “genetic algorithms” to find a solution. In an example process of evolving a design, a population of designs is first randomly created, tested, and scored based on the suitability to meet the design requirements. Then, based on natural selection principles, certain ones of the designs in the population are selected to “reproduce,” that is, are used to create new designs for the population. The process of testing, scoring, and reproducing is then repeated until a suitable design has evolved.
At present, evolving circuits is very time consuming. Many hours or even days can be spent evolving a circuit, depending on the desired functionality of the circuit. Proposed solutions to accelerate the process of evolving a circuit include the use of super-computers, massive clusters of networked microcomputers working in parallel, and custom computers. While any or all of these solutions may reduce the time required to evolve a suitable circuit, each is expensive in terms of the required hardware.
A system and method that address the aforementioned problems, as well as other related problems, are therefore desirable.
SUMMARY OF THE INVENTION
In various embodiments, method and apparatus are provided for evolving an object using simulated annealing and genetic processing techniques. In each iteration a single object is mutated in proportion to a mutation level, and the mutated object is evaluated relative to the satisfaction of predetermined criteria. With each iteration, the mutation level is reduced if the present solution is better than the best solution thus far achieved. On each iteration, a poorer-performing object is either kept or its mutations are undone for future iterations based on a probabilistic function. As the object approaches a final solution, the probability of keeping and mutating poorer-performing objects is reduced.
It will be appreciated that various other embodiments are set forth in the Detailed Description and Claims that follow.
REFERENCES:
patent: 5511158 (1996-04-01), Sims
patent: 5761484 (1998-06-01), Agarwal et al.
patent: 5897628 (1999-04-01), Kitano
patent: 6185724 (2001-02-01), Ochotta
patent: 6233493 (2001-05-01), Cherneff et al.
patent: 6363368 (2002-03-01), Shinagawa
patent: 6363519 (2002-03-01), Levi et al.
patent: 6378122 (2002-04-01), Levi et al.
patent: 2001/0011258 (2001-08-01), Shinagawa
patent: 2001/0018762 (2001-08-01), Lenzie
Adrian Thompson, “Silicon Evolution”, Proceedings of Genetic Programming 1996 (GP96), J.R. Koza et al., (Eds.), pp. 444-452. MIT Press 1996.
Crawford PLLC
Liu Andrea
Maunu LeRoy D.
Smith Matthew
Xilinx , Inc.
LandOfFree
Method and apparatus for evolving an object using simulated... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for evolving an object using simulated..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for evolving an object using simulated... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3019910