Localized simulated annealing

Details Localized simulated annealing Localized simulated annealing

1995-10-26

1998-04-28

Teska, Kevin J.

Boots, shoes, and leggings

395 20, 395920, 364578, 36446828, G06F 1700

Patent

active

057457352

ABSTRACT:
According to the present invention, a method of optimization by simulated annealing is provided that uses a spatial metric to localize the simulated annealing temperature, the move set, and the objects which the moves operate on. The method keeps a local history of the optimization process. The localization allows the simulated annealing process to adaptively control the annealing schedule of each local region independently. This allows the annealing temperature, move set, and the objects upon which the move set operates to each be adjusted for each region independently to maximize efficiency. This results in optimization of all regions in a quick and efficient manner.

REFERENCES:
patent: 3654615 (1972-04-01), Freitag
patent: 4495559 (1985-01-01), Gelatt, Jr. et al.
patent: 4607339 (1986-08-01), Davis
patent: 4615010 (1986-09-01), Davis et al.
patent: 4931944 (1990-06-01), Richter et al.
patent: 5077676 (1991-12-01), Johnson et al.
patent: 5134685 (1992-07-01), Rosenbluth
patent: 5136686 (1992-08-01), Koza
patent: 5153923 (1992-10-01), Matsuba et al.
patent: 5159682 (1992-10-01), Toyonaga et al.
patent: 5200908 (1993-04-01), Date et al.
patent: 5218551 (1993-06-01), Agrawal et al.
patent: 5224056 (1993-06-01), Chene et al.
patent: 5225991 (1993-07-01), Dougherty
patent: 5235521 (1993-08-01), Johnson et al.
patent: 5237514 (1993-08-01), Curtin
patent: 5308798 (1994-05-01), Brasen et al.
patent: 5326659 (1994-07-01), Liu et al.
patent: 5333032 (1994-07-01), Matsumoto et al.
patent: 5339253 (1994-08-01), Carrig et al.
patent: 5349536 (1994-09-01), Ashtaputre et al.
patent: 5359535 (1994-10-01), Djaja et al.
patent: 5363313 (1994-11-01), Lee
patent: 5388055 (1995-02-01), Tanizawa et al.
patent: 5402357 (1995-03-01), Schaefer et al.
patent: 5416718 (1995-05-01), Yamazaki
patent: 5432447 (1995-07-01), Song
patent: 5557533 (1996-09-01), Koford et al.
patent: 5563783 (1996-10-01), Stolfo et al.
patent: 5568636 (1996-10-01), Koford
patent: 5619419 (1997-04-01), D'Haeseleer et al.
patent: 5636125 (1997-06-01), Rostoker et al.
"New Algorithms for the Placement and Routing of Macro Cells", by W. Swartz and C. Sechen, IEEE, Computer-Aided Design, 1990 International Conference, pp. 336-339.
"Techniques for Simultaneous Placement and Routing of Custom Analog Cells in Koan/Anagram II", by J. Cohn et al., IEEE, Computer-Aided Design, 1991 International Conference, Feb. 1991, pp. 394-397.
"Heuristic Technique for Processor and Link Assignment in Multicomputers", by Bollinger et al., IEEE Transactions on Computers, vol. 40, No. 3, Mar. 1991, pp. 325-333.
"Best-So-Far vs. Where-You-Are: New Perspectives on Simulated Annealing for CAD", by K. Boese et al., IEEE, European Design Automation Conference, 1993 and EURO-VHDL 1993, Jan. 1993, pp. 78-83.
"Optimization Based Job Shop Scheduling", by K. Musser et al., IEEE Transactions on Automatic Control, vol. 38, No. 5, May 1993, pp. 808-813.
"Combinatorial Optimization of Distributed Queries", by B. Groselj and Q. Malluhi, IEEE Transactions on Knowledge and Data Engineering, vol. 7, No. 6, Dec. 1995, pp. 915-927.
Kudoh, M., et al., LSI Low Power Oriented Layout Method with Net Switching Factors, IBM Technical Disclosure Bulletin, Jun. 1993, vol. 36, No. 06B, pp. 505-507.
Gonsalves, G. J., Technology Mapping Using Simulated Annealing, IBM Technical Disclosure Bulletin, Aug. 1990, vol. 33, No. 3A, p. 308.
Author Unknown, Method to Achieve Equal Capacitance on a Group of Nets During Circuit Layout and Placement, Research Disclosure, Mar. 1989, No. 299, Kenneth Mason Publications Ltd., England.
Lam, Jimmy, et al., Performance of a New Annealing Schedule, IEEE, 1988, pp. 306-311.
Darema-Rogers, F., et al., Parallel Simulated Annealing Method for Highly Parallel Multiple Computer Processors, IBM Technical Disclosure Bulletin, Dec. 1987, vol. 30, No. 7, pp. 106-107.
Huang, M. D., et al., An Efficient General Cooling Schedule for Simulated Annealing, IEEE, 1986, pp. 381-384.
Kirkpatrick, S., et al., Optimization by Simulated Annealing, Science, May 13, 1983, vol. 220, No. 4598, pp. 671-680.

Affiliated with

Also associated with

Rating

Localized simulated annealing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Localized simulated annealing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Localized simulated annealing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1542542